A Graphical Representation for Games in Partition Function Form
Authors: Oskar Skibski, Tomasz Michalak, Yuko Sakurai, Michael Wooldridge, Makoto Yokoo
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. [...] We propose a novel representation for coalitional games with externalities, called Partition Decision Trees. This representation is based on rooted directed trees, in which 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, i.e., it can represent any game with externalities. It can also be significantly more concise than the extensive representation. Most importantly, our representation is the first concise formalism in the literature that facilitates polynomial computation of almost all the aforementioned extensions of the Shapley value. In particular, the externality-free, the Mc Quillin, the Macho-Stadler et al. and the Myerson values can all be computed in time O(n |T |), whereas the Hu-Yang value can be computed in time O(n3 |T |), where |T | is the size of the representation. [...] In this section, we prove that, given the PDT representation, five out of the six extended Shapley values can be calculated in polynomial time. |
| Researcher Affiliation | Collaboration | Oskar Skibski1, Tomasz P. Michalak2,3, Yuko Sakurai1,4, Michael Wooldridge2, Makoto Yokoo1 1Department of Informatics, Kyushu University, Japan 2Department of Computer Science, University of Oxford, UK 3Institute of Informatics, University of Warsaw, Poland 4JST PRESTO, Japan |
| Pseudocode | No | The paper does not include explicit pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not mention using or providing access to any dataset for training experiments. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments requiring training/validation/test splits. |
| Hardware Specification | No | The paper is theoretical and does not mention any hardware specifications for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training settings. |