Computing stable outcomes in weighted voting games

Edith Elkind ( University of Southampton/ Nanyang Technological University )

In coalitional games, agents work in teams, and need to distribute the profits that arise from their joint activities. Weighted voting games are a simple, but expressive class of coalitional games that can be used to model decision-making in political bodies as well as collaboration in multi-agent systems. In such settings, stability of the grand coalition, i.e., the coalition that consists of all agents, is an important consideration: the gains from the collaboration should be distributed in such a way that the agents' incentives to deviate from the grand coalition are minimized. In this talk, we will discuss the computational complexity of several stability-related solution concepts in weighted voting games, such as the epsilon-core, the least core and the nucleolus. While computing many of these solution concepts appears to be hard, we will describe recent pseudopolynomial and approximation algorithms that mitigate the hardness results. The talk is self-contained; in particular, no background in game theory is assumed.

Based on joint work with Leslie Ann Goldberg, Paul Goldberg, Michael Wooldridge (U of Liverpool) and Dmitrii Pasechnik (NTU, Singapore).