• shareshare
  • link
  • cite
  • add
auto_awesome_motion View all 4 versions
Publication . Article . Other literature type . Preprint . 2019

Cooperative games with bounded dependency degree

Igarashi, Ayumi; Izsak, Rani; Elkind, Edith;
Open Access
Published: 09 Jan 2019
Publisher: Association for the Advancement of Artificial Intelligence Publications
Country: United Kingdom

Cooperative games provide a framework to study cooperation among self-interested agents. They offer a number of solution concepts describing how the outcome of the cooperation should be shared among the players. Unfortunately, computational problems associated with many of these solution concepts tend to be intractable---NP-hard or worse. In this paper, we incorporate complexity measures recently proposed by Feige and Izsak (2013), called dependency degree and supermodular degree, into the complexity analysis of cooperative games. We show that many computational problems for cooperative games become tractable for games whose dependency degree or supermodular degree are bounded. In particular, we prove that simple games admit efficient algorithms for various solution concepts when the supermodular degree is small; further, we show that computing the Shapley value is always in FPT with respect to the dependency degree. Finally, we note that, while determining the dependency among players is computationally hard, there are efficient algorithms for special classes of games.

10 pages, full version of accepted AAAI-18 paper


General Medicine, Computer Science - Computer Science and Game Theory, Computer Science and Game Theory (cs.GT), FOS: Computer and information sciences

31 references, page 1 of 4

Bachrach, Y., and Rosenschein, J. S. 2008. Power in threshold network flow games. Autonomous Agents and MultiAgent Systems 18(1):106.

Berry, A., and Simonet, G. 2017. Computing a clique tree with the algorithm maximal label search. Algorithms 10(1):20.

Chalkiadakis, G.; Elkind, E.; and Wooldridge, M. 2011.

Chalkiadakis, G.; Greco, G.; and Markakis, E. 2016. Characteristic function games with restricted agent interactions: Core-stability and coalition structures. Artificial Intelligence 232:76-113. [OpenAIRE]

2015. Parameterized Algorithms. Springer.

Das, A., and Kempe, D. 2011. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In ICML'11, 1057-1064.

Deng, X., and Papadimitriou, C. H. 1994. On the complexity of cooperative solution concepts. Mathematics of Operations Research 19(2):257-266.

Elkind, E.; Rahwan, T.; and Jennings, N. R. 2013. Computational coalition formation. In Weiss, G., ed., Multiagent Systems. MIT Press. [OpenAIRE]

Feige, U., and Izsak, R. 2013. Welfare maximization and the supermodular degree. In ITCS'13, 247-256.

Feige, U.; Feldman, M.; Immorlica, N.; Izsak, R.; Lucier, B.; and Syrgkanis, V. 2015. A unifying hierarchy of valuations with complements and substitutes. In AAAI'15, 872-878.

Funded by
Algorithms for Complex Collective Decisions on Structured Domains
  • Funder: European Commission (EC)
  • Project Code: 639945
  • Funding stream: H2020 | ERC | ERC-STG
Download fromView all 4 sources