Complexity of Computing the Shapley Value in Partition Function Form Games
Authors: Oskar Skibski
JAIR 2023 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. For all other values, we show on that computation is #P-hard (see Table 1). |
| Researcher Affiliation | Academia | Oskar Skibski EMAIL Institute of Informatics, University of Warsaw 02-097 Warsaw, Poland |
| Pseudocode | No | The paper describes mathematical definitions, lemmas, and theorems, focusing on theoretical complexity analysis. It does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository. |
| Open Datasets | No | The paper is a theoretical work on computational complexity and does not involve experiments with datasets, thus no information about open datasets is provided. |
| Dataset Splits | No | The paper is a theoretical work and does not use datasets, therefore no information about training/test/validation splits is provided. |
| Hardware Specification | No | The paper is a theoretical work and does not describe any experimental hardware specifications. |
| Software Dependencies | No | The paper is a theoretical work focusing on computational complexity and does not list any specific software dependencies with version numbers for implementation. |
| Experiment Setup | No | The paper is a theoretical work analyzing computational complexity and does not describe an experimental setup with hyperparameters or system-level training settings. |