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 [1].
Complexity of Computing the Shapley Value in Games with Externalities
Authors: Oskar Skibski2244-2251
AAAI 2020 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we fill a gap in the literature by determining what is the complexity of computing all the five extensions of the Shapley value in games represented as embedded and weighted MC-nets. Specifically, we show that only two out of five extensions can be computed in polynomial time for embedded MC-nets and only one can be computed in polynomial time for weighted MC-nets (unless P = NP). For all other values we show that computation is #P-complete (see Table 1). Interestingly, our results are strongly based on graph theory techniques. |
| Researcher Affiliation | Academia | Oskar Skibski Institute of Informatics, University of Warsaw, Poland EMAIL |
| Pseudocode | No | The paper describes algorithmic approaches (e.g., dynamic programming) but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not mention releasing open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper and does not use datasets for training. |
| Dataset Splits | No | This is a theoretical paper and does not discuss data splits for validation. |
| Hardware Specification | No | This is a theoretical paper and does not mention any hardware specifications used for experiments. |
| Software Dependencies | No | This is a theoretical paper and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper and does not describe an experimental setup with hyperparameters or training settings. |