Coalitional affinity games

ABSTRACT

We present and analyze coalitional affinity games, a family of hedonic games that explicitly model the value that an agent receives from being associated with other agents. We provide a characterization of the social-welfare maximizing coalition structures, and study the stability properties of affinity games, using the core solution concept. Interestingly, we observe that members of the core do not necessarily maximize social welfare. We introduce a new measure, the stability-gap to capture this difference. Using the stability gap, we show that for an interesting class of coalitional affinity games, the difference between the social welfare of a stable coalition structure and a social-welfare maximizing coalition structure is bounded by a factor of 2, and that this bound is tight.

REFERENCES

• 1: Xiaotie Deng , Christos H. Papadimitriou, On the complexity of cooperative solution concepts, Mathematics of Operations Research, v.19 n.2, p.257-266, May 1994 [doi>10.1287/moor.19.2.257]
• 2: Noam Nisan , Tim Roughgarden , Eva Tardos , Vijay V. Vazirani, Algorithmic Game Theory, Cambridge University Press, New York, NY, 2007
• 3: B. Peleg and P. Sudhölter. Introduction to the Theory of Cooperative Games. Springer, 2003.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Theory

Keywords:
coalitions