Measuring power in coalitional games with friends, enemies and allies

Oskar Skibski, Takamasa Suzuki, Tomasz Grabowski, Yuko Sakurai, Tomasz Michalak, Makoto Yokoo

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

We extend the well-known model of graph-restricted games due to Myerson to signed graphs. In our model, it is possible to explicitly define not only that some players are friends (as in Myerson's model) but also that some other players are enemies. As such our games can express a wider range of situations, e.g., animosities between political parties. We define the value for signed graph games using the axiomatic approach that closely follows the celebrated characterization of the Myerson value. Furthermore, we propose an algorithm for computing an arbitrary semivalue, including the extension of the Myerson value proposed by us. We also develop a pseudo-polynomial algorithm for power indices in weighted voting games for signed graphs with bounded treewidth. Moreover, we consider signed graph games with a priori defined alliances (unions) between players and propose algorithms to compute the extension of the Owen value to this setting.

Original languageEnglish
Article number103792
JournalArtificial Intelligence
Volume313
DOIs
Publication statusPublished - Dec 2022

All Science Journal Classification (ASJC) codes

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Measuring power in coalitional games with friends, enemies and allies'. Together they form a unique fingerprint.

Cite this