Graph-Based Coalitional Games - An Analysis Via Characteristics

Download Now Date Added: May 2011
Format: PDF

In this paper, the authors motivate a new approach to analyze the computational complexity of solution concepts and player-based properties, as well as other properties of coalitional games. This approach is based on the idea to abstract away from detailed game representations to analyze games via standard complexity proofs, towards a more abstract approach, where games are analyzed by focusing on influential characteristics of related games. The core of this structure-centered perspective on coalitional games is to determine and systematically analyze promising characteristics, so that they can be used later to analyze games of a similar type.