2 October 2009, Computational Social Choice Seminar, Frank Nebel
In this talk, I will give an overview of research contributions
regarding the complexity of problems arising in coalitional game
theory. Over the last few years a series of papers has been published,
which analyse the computational complexity of problems regarding the
application of solution concepts to different classes of coalitional
games that are expressed by more or less concise representation
languages. These complexity results basically depend on three aspects,
namely which class of coalitional games is involved, what
representation language is chosen, and which solution concept is
applied, which is why we refer to them as “triplets”.
I will do three things: (1) I will introduce various basic concepts of cooperative game theory and representation languages. So, previous exposure to these areas is not assumed. (2) I will give an overview of several complexity results in the field. Then, based on this set of results, I point out some interesting (open) problems arising in this context and motivate further activities to detect possible patterns. (3) I will give an overview of my own work in this area, namely the effort to analyse the computational complexity of different solution concepts in shortest path games, a class of coalitional games that is similar to the well known class of flow games.