Skip to main content

Role assignment for game-theoretic cooperation

Publication ,  Conference
Moon, C; Conitzer, V
Published in: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
January 1, 2016

In multiagent systems, often agents need to be assigned to different roles. Multiple aspects should be taken into account for this, such as agents' skills and constraints posed by existing assignments. In this paper, we focus on another aspect: when the agents are self-interested, careful role assignment is necessary to make cooperative behavior an equilibrium of the repeated game. 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.

Duke Scholars

Published In

Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

EISSN

1558-2914

ISSN

1548-8403

ISBN

9781450342391

Publication Date

January 1, 2016

Start / End Page

1413 / 1414
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Moon, C., & Conitzer, V. (2016). Role assignment for game-theoretic cooperation. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS (pp. 1413–1414).
Moon, C., and V. Conitzer. “Role assignment for game-theoretic cooperation.” In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, 1413–14, 2016.
Moon C, Conitzer V. Role assignment for game-theoretic cooperation. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS. 2016. p. 1413–4.
Moon, C., and V. Conitzer. “Role assignment for game-theoretic cooperation.” Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2016, pp. 1413–14.
Moon C, Conitzer V. Role assignment for game-theoretic cooperation. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS. 2016. p. 1413–1414.

Published In

Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

EISSN

1558-2914

ISSN

1548-8403

ISBN

9781450342391

Publication Date

January 1, 2016

Start / End Page

1413 / 1414