Graph-based Coalitional Games - An Analysis via Characteristics

In this paper we motivate a new approach to analyse 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 analyse games via standard complexity proofs, towards a more abstract approach, where games are analysed by focusing on influential characteristics of related games. The core of this structure-centered perspective on coalitional games is to determine and systematically analyse promising characteristics, so that they can be used later to analyse games of a similar type. This may be particularly interesting in a well-restricted class of games, like in the context of networks. To give a first example of this approach, we concentrate on a specific type of game, namely graph-based games. In the course of our analysis we will provide various results for shortest path games, results also interesting for their own sake.