Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Complexity of Computing the Shapley Value in Partition Function Form Games
Authors: Oskar Skibski
JAIR 2023 | Venue PDF | 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. |