Abstract

A set of self-interested and rational agents in a social network want to distribute their initial set of resources among themselves to obtain the set of resources they desire the most. Each agent,
being self-interested and rational has incentive to lie about its preferences towards the resources to manipulate the outcome of the system to its advantage. In the context of multi-agent systems,
Automated Mechanism Design (AMD), is a computer based design of rules that allows the reach of an equilibrium despite the selfishness of its agents.
Most of the multi-agent and AMD research has focused on one-to-one bilateral exchanges that only allow two agents to exchange resources.
Very few studies have been conducted on multilateral (many-to-many) types of trade. While several multi-agent algorithms exist for the one-to-one case, very few algorithms exists for the many-to-many case, which is more often encountered in social networks. AMD algorithms lack scalability as they rely on the enumeration of the resource allocation combinations.
We first propose three new optimization models for the AMD problem using a decomposition technique to create mechanisms that are not only scalable, i.e., one could use them to solve the
AMD problem for data sets consisting of hundreds of agents and resources in seconds, but also support different types of trades between different numbers of agents (one-to-one, many-to-one
and many-to-many). Then we illustrate a new mathematical model with a polynomial number of variables corresponding to the compact formulation of the current model of the literature that
supports the many-to-many type of trade.
Numerical experiments show that we can solve significantly larger data sets than the ones existing in the literature, i.e., up to 2,000 agents and 2,000 resources for the many-to-many type of trade in less than 24 seconds.