Role Assignment for Game-Theoretic Cooperation
Authors: Catherine Moon, Vincent Conitzer
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We formalize this problem and provide an easy-to-check necessary and sufficient condition for a given role assignment to induce cooperation. However, we show that finding whether such a role assignment exists is in general NP-hard. Nevertheless, we give two algorithms for solving the problem. The first is based on a mixed-integer linear program formulation. The second is based on a dynamic program, and runs in pseudopolynomial time if the number of agents is constant. Minor modifications of these algorithms also allow for determination of the minimal subsidy necessary to induce cooperation. In our experiments, the IP performs much, much faster. |
| Researcher Affiliation | Academia | Catherine Moon Duke University Durham, NC 27708, USA csm17@duke.edu Vincent Conitzer Duke University Durham, NC 27708, USA conitzer@cs.duke.edu |
| Pseudocode | No | The paper describes algorithms (Integer Program, Dynamic Program) but does not provide pseudocode or a clearly labeled algorithm block. |
| Open Source Code | No | The paper does not provide any links to open-source code for the described methodology or state that it will be made publicly available. |
| Open Datasets | No | For a given number n of players, a given number |G| of minigames, and a given game generator in GAMUT, we generate an instance by drawing |G| n-player games with payoffs in the interval [ 5, 5] from the generator. The paper describes how data instances were *generated* but does not provide access information (link, citation, etc.) for a publicly available dataset. |
| Dataset Splits | No | The paper describes the generation of game instances for simulation analysis but does not specify training/validation/test dataset splits as commonly found in empirical machine learning research. |
| Hardware Specification | No | The paper states: "CPLEX 12.6.0.0 and g++ 4.8.4 were used for IP and DP respectively." It does not provide any specific hardware details such as GPU/CPU models, memory, or cloud resources used for the experiments. |
| Software Dependencies | Yes | CPLEX 12.6.0.0 and g++ 4.8.4 were used for IP and DP respectively. |
| Experiment Setup | Yes | For a given number n of players, a given number |G| of minigames, and a given game generator in GAMUT, we generate an instance by drawing |G| n-player games with payoffs in the interval [ 5, 5] from the generator. (Though we have done the simulation on many different families of games (dispersion, coordination, N-player chicken, etc.), the runtimes do not appear to depend on the family, so we omit them due to limited space.) Because the DP algorithm requires payoffs to be integers, we round all the payoffs in each game to integers in { 5, 4, . . . , 5}. We evaluate the IP algorithm on nondiscretized payoffs. The experimental results for when the target action is determined as the action profile maximizing the social welfare. |