Institute for Logic, Language and Computation

2 October 2009, Computational Social Choice Seminar, Frank Nebel

Speaker: Frank Nebel
Title: Complexity Issues in Coalitional Game Theory: An Introduction
Date: Friday 2 October 2009
Time: 14:00
Location: Room A1.04, Science Park 904, Amsterdam


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 or contact Ulle Endriss ().

The websites of the UvA make use of cookiesThis site uses cookies More informationMore info Hide this message XHide X