Cooperative Games With Bounded Dependency Degree
Authors: Ayumi Igarashi, Rani Izsak, Edith Elkind
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we incorporate complexity measures recently proposed by Feige and Izsak (2013), called dependency degree and supermodular degree, into the complexity analysis of cooperative games. We show that many computational problems for cooperative games become tractable for games whose dependency degree or supermodular degree are bounded. In particular, we prove that simple games admit efficient algorithms for various solution concepts when the supermodular degree is small; further, we show that computing the Shapley value is always in FPT with respect to the dependency degree. Finally, we observe that, while determining the dependency among players is computationally hard, there are efficient algorithms for special classes of games. |
| Researcher Affiliation | Academia | Ayumi Igarashi University of Oxford Oxford, UK ayumi.igarashi@cs.ox.ac.uk Rani Izsak Weizmann Institute of Science Rehovot, Israel ran.izsak@weizmann.ac.il Edith Elkind University of Oxford Oxford, UK edith.elkind@cs.ox.ac.uk |
| 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. It only refers to a technical report on arXiv for omitted proofs. |
| Open Datasets | No | This is a theoretical paper and does not involve the use of datasets for training. |
| Dataset Splits | No | This is a theoretical paper and does not involve data validation or dataset splits. |
| Hardware Specification | No | This is a theoretical paper and does not specify any hardware used for running experiments. |
| Software Dependencies | No | This is a theoretical paper and does not list any specific software dependencies with version numbers for experimental replication. |
| Experiment Setup | No | This is a theoretical paper and does not describe an experimental setup with hyperparameters or training configurations. |