Multi Agent Systems and Mechanism Design
A multi-agent system, sometimes refer to a self organized system, corresponds to a scenario where multiple entities interact within a given environment to achieve individual or collective goals. Co-operative systems are been studied extensively while situations where the individual objectives do not align with each other or the common goal have been much less studied.
Computational problems involving multiple interacting agents have exploded in significance along with the rise of the Internet and the social networks due to the massive volume of applications they provide or generate. As communication between entities becomes easier, the number of interested parties in any situation rises. From a computational point of view, the presence of multiple agents not only introduces strategic and temporal issues, but also enhances the difficulties of optimizing the coordination among the agents, hence the motivation for mechanism design.
Mechanism design is the sub-field of microeconomics and game theory that considers how to implement good system-wide solutions to problems that involve multiple self-interested agents, each with private information about their preferences. In recent years mechanism design has found many important applications; e.g., in electronic market design, in distributed scheduling problems, and in combinatorial resource allocation problems.
Classical mechanism design deals with the design of incentives for a distributed population of agents to behave in a way that will lead to an optimal global outcome. The meaning of \optimal" depends on the mechanism designer's interests. These are represented by a social choice function that maps any type prole of the agents to the outcome that the designer would like to see occur if that type prole is realized.
While classic mechanism design has not directly deal with the computational questions of the process, such as the representations of the outcome and preference spaces, or the complexity of choosing the optimal outcome , the idea of computational mechanism design is to maintain useful economic properties but also achieve useful computational properties.