Graphical Hedonic Games of Bounded Treewidth

Authors

  • Dominik Peters University of Oxford

DOI:

https://doi.org/10.1609/aaai.v30i1.10046

Keywords:

hedonic games, bounded treewidth, structural tractability, preference restrictions

Abstract

Hedonic games are a well-studied model of coalition formation, in which selfish agents are partitioned into disjoint sets and agents care about the make-up of the coalition they end up in. The computational problems of finding stable, optimal, or fair outcomes tend to be computationally intractable in even severely restricted instances of hedonic games. We introduce the notion of a graphical hedonic game and show that, in contrast, on classes of graphical hedonic games whose underlying graphs are of bounded treewidth and degree, such problems become easy. In particular, problems that can be specified through quantification over agents, coalitions, and (connected) partitions can be decided in linear time. The proof is by reduction to monadic second order logic. We also provide faster algorithms in special cases, and show that the extra condition of the degree bound cannot be dropped. Finally, we note that the problem of allocating indivisible goods can be modelled as a hedonic game, so that our results imply tractability of finding fair and efficient allocations on appropriately restricted instances.

Downloads

Published

2016-02-21

How to Cite

Peters, D. (2016). Graphical Hedonic Games of Bounded Treewidth. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10046

Issue

Section

Technical Papers: Game Theory and Economic Paradigms