Multi-attribute coalitional games

ABSTRACT

We study coalitional games where the value of cooperation among the agents are solely determined by the attributes the agents possess, with no assumption as to how these attributes jointly determine this value. This framework allows us to model diverse economic interactions by picking the right attributes. We study the computational complexity of two coalitional solution concepts for these games -- the Shapley value and the core. We show how the positive results obtained in this paper imply comparable results for other games studied in the literature.

REFERENCES

• 1: J. M. Bilbao, J. R. Fernández, and J. J. López. Complexity in cooperative game theory. http://www.esi.us.es/~mbilbao.
• 2: V. Conitzer and T. Sandholm. Complexity of determining nonemptiness of the core. In Proc. 18th Int. Joint Conf. on Artificial Intelligence, pages 613--618, 2003.
• 3: V. Conitzer and T. Sandholm. Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains. In Proc. 19th Nat. Conf. on Artificial Intelligence, pages 219--225, 2004.
• 4: I. J. Curiel, J. J. Derks, and S. H. Tijs. On balanced games and games with committee control. OR Spectrum, 11:83--88, 1989.
• 5: 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]
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: Samuel Ieong , Yoav Shoham, Marginal contribution nets: a compact representation scheme for coalitional games, Proceedings of the 6th ACM conference on Electronic commerce, p.193-202, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064030]
• 8: E. Kalai and E. Zemel. Totally balanced games and games of flow. Math. Oper. Res., 7:476--478, 1982.
• 9: A. Mas-Colell, M. D. Whinston, and J. R. Green. Microeconomic Theory. Oxford University Press, New York, 1995.
• 10: M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press, Cambridge, Massachusetts, 1994.
• 11: L. S. Shapley. A value for n-person games. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games II, number 28 in Annals of Mathematical Studies, pages 307--317. Princeton University Press, 1953.
• 12: O. Shehory and S. Kraus. Task allocation via coalition formation among autonomous agents. In Proc. 14th Int. Joint Conf. on Artificial Intelligence, pages 31--45, 1995.
• 13: O. Shehory and S. Kraus. A kernel-oriented model for autonomous-agent coalition-formation in general environments: Implentation and results. In Proc. 13th Nat. Conf. on Artificial Intelligence, pages 134--140, 1996.
• 14: J. von Neumann and O. Morgenstern. Theory of Games and Economic Behvaior. Princeton University Press, 1953.
• 15: M. Yokoo, V. Conitzer, T. Sandholm, N. Ohta, and A. Iwasaki. Coalitional games in open anonymous environments. In Proc. 20th Nat. Conf. on Artificial Intelligence, pages 509--515, 2005.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics

Keywords:
coalitional game theory, compact representation, multi-attribute model