ML Anthology

Complexity of Computing the Shapley Value in Partition Function Form Games

Oskar Skibski
JAIR 2023 pp. 1237-1274
doi:10.1613/JAIR.1.14648 /jair/2023/skibski2023jair-complexity/

Abstract

We study the complexity of computing the Shapley value in partition function form games. We focus on two representations based on marginal contribution nets (embedded MC-nets and weighted MC-nets) and five extensions of the Shapley value. Our results show that while weighted MC-nets are more concise than embedded MC-nets, they have slightly worse computational properties when it comes to computing the Shapley value: two out of five extensions can be computed in polynomial time for embedded MC-nets and only one for weighted MC-nets.

PDF JAIR Semantic Scholar

Cite

Text

Skibski. "Complexity of Computing the Shapley Value in Partition Function Form Games." Journal of Artificial Intelligence Research, 2023. doi:10.1613/JAIR.1.14648

Markdown

[Skibski. "Complexity of Computing the Shapley Value in Partition Function Form Games." Journal of Artificial Intelligence Research, 2023.](https://mlanthology.org/jair/2023/skibski2023jair-complexity/) doi:10.1613/JAIR.1.14648

BibTeX

@article{skibski2023jair-complexity,
  title     = {{Complexity of Computing the Shapley Value in Partition Function Form Games}},
  author    = {Skibski, Oskar},
  journal   = {Journal of Artificial Intelligence Research},
  year      = {2023},
  pages     = {1237-1274},
  doi       = {10.1613/JAIR.1.14648},
  volume    = {77},
  url       = {https://mlanthology.org/jair/2023/skibski2023jair-complexity/}
}