A Graphical Representation for Games in Partition Function Form

Oskar Skibski, Tomasz P. Michalak, Yuko Sakurai, Michael J. Wooldridge, Makoto Yokoo

AAAI 2015 pp. 1036-1042

doi:10.1609/AAAI.V29I1.9306 /aaai/2015/skibski2015aaai-graphical/

Abstract

We propose a novel representation for coalitional games with externalities, called Partition Decision Trees. This representation is based on rooted directed trees, where non-leaf nodes are labelled with agents' names, leaf nodes are labelled with payoff vectors, and edges indicate membership of agents in coalitions. We show that this representation is fully expressive, and for certain classes of games significantly more concise than an extensive representation. Most importantly, Partition Decision Trees are the first formalism in the literature under which most of the direct extensions of the Shapley value to games with externalities can be computed in polynomial time.

PDF AAAI Semantic Scholar

Cite

Text

Skibski et al. "A Graphical Representation for Games in Partition Function Form." AAAI Conference on Artificial Intelligence, 2015. doi:10.1609/AAAI.V29I1.9306

Markdown

[Skibski et al. "A Graphical Representation for Games in Partition Function Form." AAAI Conference on Artificial Intelligence, 2015.](https://mlanthology.org/aaai/2015/skibski2015aaai-graphical/) doi:10.1609/AAAI.V29I1.9306

BibTeX

@inproceedings{skibski2015aaai-graphical,
  title     = {{A Graphical Representation for Games in Partition Function Form}},
  author    = {Skibski, Oskar and Michalak, Tomasz P. and Sakurai, Yuko and Wooldridge, Michael J. and Yokoo, Makoto},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2015},
  pages     = {1036-1042},
  doi       = {10.1609/AAAI.V29I1.9306},
  url       = {https://mlanthology.org/aaai/2015/skibski2015aaai-graphical/}
}