Coalitional Games
Stéphane Airiau
Summary
The first goal of this course is to introduce the coalition formation problem from a game theoretical perspective. Then, we will survey some of the issues encountered by practical use, and how they can be addressed in the field of multiagent systems.
Coalition formation is an important means for enabling cooperation in agent societies. Social sci- entists and economists have studied situations where individuals and businesses benefit from joining forces. Whether we consider a set of people in an economy, a set of self-interested agents, or a set of web services in the semantic web, any subset is a coalition with a potential for serving individual or group interests.
The process of coalition formation has been extensively studied in game theory, and as a result, many solution concepts have been proposed. Naturally, there are pros and cons for each of them and no unique and accepted one. For instance, the most intuitive solution concept (the core) according to which no agent or group thereof has an incentive to leave its current coalition to form a new one, is not guaranteed to be non-empty.
Over the last decade, coalition formation has received increased attention in the multiagent sys- tems community: forming dynamic coalitions may lead to more efficient agent societies. Game theory prescribes ways to share a payoff obtained by a coalition in a stable manner, but it does not describe how to form efficient coalitions.
Our first goal is to introduce the basic solution concepts from game theory. Then, we discuss the challenges of coalition formation in the context of multiagent systems: communication, dynamic envi- ronments, uncertainty about knowledge or tasks, protocols and manipulation, etc. We survey proposed solutions to these issues, and finally we discuss the problem of searching for efficient coalition struc- tures.
Level of the course, intended audience and required background knowledge
This is a beginners’ course intended for Master and first year PhD students as we intend to introduce the basic concepts of cooperative game theory and survey the main issues of coalition formation in multiagent systems. We assume basic discrete mathematics, but no knowledge of game theory or cooperative games.
Outline
• Introduction to basic Cooperative Game Theory
– Games with and without transferable utility (examples of TU and NTU games, characteristic function, some representations (e.g., weighted voting games)).
– Solutions concepts:
∗ The core and other stability concepts (Kernel, Nucleolus)
∗ The Shapley value
∗ Computational aspects (checking for non-emptiness of the core, computing Shapley value or Kernel-stable payoff distribution, etc.)
– Hedonic coalition formation, endogenous coalition formation.
• Issues in multiagent systems:
– Examples of application in multiagent systems (task allocation problems, Electronic Mar- ketplace, information agents)
– Process of coalition formation: protocols, manipulation, communication, dynamic environ- ments, short term/long term coalitions, overlaping coalitions
– Uncertainty (agents may not know some tasks or the value of some coalitions, Bayesian Core)
– Search of the optimal coalition structure (efficient algorithm searching for coalition structure maximize utilitarian social welfare)
Information regarding the course material
We will provide the slides to the participants of the class. The first part of the tutorial, i.e., the in- troduction to cooperative game theory, will follow the classic textbook A Course in Game Theory by Osborne and Rubinstein. The second part of the tutorial about issues and contributions from multia- gent systems will be based on a working survey paper based on the related work section of Stéphane’s dissertation Forming efficient agent coalitions for endogenous coalition structures.
Duration
We propose a typical 4 hours course.
About the tutor
Stéphane Airiau is a postdoctoral fellow at the Institute for Logic, Language and Computation (ILLC) at the University of Amsterdam. He graduated from the University of Tulsa under the supervision of Sandip Sen, and wrote his PhD thesis on fair payoff distribution in various settings of coalition formation. In between, he visited the Agents group at RMIT university in Melbourne. Stéphane has been a program committee member for AAMAS-08 and AAMAS-09. He has teaching experience as a teaching assistant for mathematics and computer science undergraduate courses.
