Shortest Path Games: Computational Complexity of Solution Concepts
Frank Nebel

Abstract:
Over the last few years a series of papers has been published that
analyse the computational complexity of solution concepts applied to
different types of coalitional games, which are expressed by more or
less concise representation languages. However, the coalitional games
that have been analysed in a computational context typically have fixed
and restricted characteristics and were studied in isolation from each
other. For instance, results for related classes of games, like
graph-based games, have not been systematically compared with respect
to computational complexity or expressive power.
If we are exclusively interested in a specific type of game, this is
certainly adequate, whereas a one by one analysis of complexity
theoretic problems is impractical when we want to analyse a wide range
of more or less distantly related coalitional games. To tackle this
issue, we want to motivate in this thesis a more abstract approach,
which is based on the characteristics of related types of coalitional
games. For this reason, we have chosen an interesting graph-based
coalitional game, namely shortest path game, to demonstrate the
proposed approach on a sample game.
In particular, we study the computational complexity of solution
concepts applied to different variants of shortest path games, as well
as the expressive power of those variants. Based on these results, we
then analyse the influence of different characteristics of shortest
path games with respect to both aspects. Furthermore, we conduct a
case study, where we relate our results on shortest path games to
known results on different types of graph-based coalitional games.
But apart from having an interesting sample game, we want to stress
that shortest path games are worthwhile to consider for their own sake
as well.