Complexity of stability-based solution concepts in multi-issue and MC-net cooperative games


Conference Paper

Copyright © 2014, International Foundation for Autonomous Agents and Multiagent Systems ( All rights reserved. MC-nets constitute a natural compact representation scheme for cooperative games in multiagent systems. In this paper, we study the complexity of several natural computational problems that concern solution concepts such as the core, the least core and the nucleolus. We characterize the complexity of these problems for a variety of subclasses of MC-nets, also considering constraints on the game such as superadditivity (where appropriate). Many of our hardness results are derived from a hardness result that we establish for a class of multi-issue cooperative games (SILT games); we suspect that this hardness result can also be used to prove hardness for other representation schemes.

Duke Authors

Cited Authors

  • Li, Y; Conitzer, V

Published Date

  • January 1, 2014

Published In

  • 13th International Conference on Autonomous Agents and Multiagent Systems, Aamas 2014

Volume / Issue

  • 1 /

Start / End Page

  • 581 - 588

International Standard Book Number 13 (ISBN-13)

  • 9781634391313

Citation Source

  • Scopus