Structural Tractability of Shapley and Banzhaf Values in Allocation Games
Authors: Gianluigi Greco, Francesco Lupia, Francesco Scarcello
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The main result is that, over the class of allocation games, the Shapley value and the Banzhaf value can be computed in polynomial time when interactions among agents can be formalized as graphs of bounded treewidth. This is shown by means of technical tools that are of interest in their own and that can be used for analyzing different kinds of coalitional games. Tractability is also shown for games where each good can be assigned to at most two agents, independently of their interactions. |
| Researcher Affiliation | Academia | Gianluigi Greco and Francesco Lupia and Francesco Scarcello University of Calabria, Italy ggreco@mat.unical.it, {lupia,scarcello}@dimes.unical.it |
| Pseudocode | No | The paper does not contain structured 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 mentions an analysis of publications from the University of Calabria as an instantiation but does not provide concrete access information (link, DOI, formal citation) for a publicly available or open dataset used for training/evaluation experiments. |
| Dataset Splits | No | The paper is theoretical and does not report on empirical experiments that would involve dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not report on experiments that would require specific hardware details. |
| Software Dependencies | No | The paper is theoretical and does not report on experiments that would require specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not include specific experimental setup details like hyperparameter values or training configurations. |