2 October 2009, Computational Social Choice Seminar, Frank Nebel

Abstract

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.

For more information, see http://www.illc.uva.nl/~ulle/seminar/ or contact Ulle Endriss (ulle.endriss at uva.nl).