Role assignment for game-theoretic cooperation

Published

Conference Paper

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 Authors

Cited Authors

  • Moon, C; Conitzer, V

Published Date

  • January 1, 2016

Published In

Volume / Issue

  • 2016-January /

Start / End Page

  • 416 - 423

International Standard Serial Number (ISSN)

  • 1045-0823

Citation Source

  • Scopus