Cooperative Games - 2011 (MoL, ILLC)

Course description
This course is about the analysis of cooperation, a field of game theory. The study of conflicts is taught in the course "strategic games". The main part of the course will consist in the study of solution concepts from the game theory literature. In particular we will study: the core, the kernel, the nucleolus, the Shapley value, (weighted) voting games and power indices, games with externalities. We will also study some additional topics: Coalitional logic and some issues raised by the multiagent systems community (search of optimal coalition structure, uncertainty, safety, manipulation, overlapping coalition). This course is of theoretical nature, we will rely on our intuition and on examples to introduce the different solution concepts, but we will also study the proofs that guarantee that a solution concept satisfies some properties.
Prerequisite
none, though I will assume some knowledge in Mathematics (few proof rely on elements of analysis).
Course material.
There is no textbook for this course. The slides and a handout for the lecture will be posted shortly before each class.

Week date topic course work
1 February 4th Introduction (Lecture 1): In the first part, we present the two main classes of games (TU games and NTU games) and we provide some examples of TU games. In the second part of the course, we will discuss some desirable solution properties.  
2 February 11th The core (Lecture 2): The core is the most natural solution concept for promoting stability. We will first define the core and provide some examples and some geometric representations. Then we will see that the core of some games may be empty. We will then consider some games that are guaranteed to have a non-empty core.  
3 February 18th The core part 2 (Lecture 3, slides [8-up]): We are going to present a characterization of the games with non-empty core and apply this theorem to market games. If time permits, we will present games with coalition structures and present the definition of the core for this type of games. Homework 1
due on Friday February 25th, 11am.
4 February 25th The bargaining set (Lecture 4, slides [8-up]): The core is not guaranteed to be non-empty, hence, by relaxing some stability requirements, one could end up with a stability concept that is guarantee to be non-empty. We will then introduce the bargaining set, which is defined for games with coalition structure. We will see how this stability concept is defined using objections and counter-objections.  
5 March 4th The nucleolus (Lecture 5, slides [8-up]): We introduce a new concept called the nucleolus. The goal of the excess is to minimize the amount of complaints about a payoff distribution. For the nucleolus, a complaint is represented by the vector of the excesses of all the coalitions.  
6 March 11th The kernel (Lecture 6, slides [8-up]): We introduce the last stability concept of the course: the kernel. It is also based on the excess, but unlike in the nucleolus, we interpret the kernel as a potential to generate some surplus, and consequently, as some measure of strenght of a player. The kernel is the set of payoff distributions for which agents have equal strength. Homework 2 due on Friday 18th, 11am.
7 March 18th The Shapley value (Lecture 7, slides [8-up]): This concept is about promoting fairness. We will present the concept of fairness used in two ways. In the first, we will present a set of axioms. In the second, we propose to use a coalition formation protocol in which agents enter a coalition one by one and gets their marginal contribution as payoff. To make a fair payoff distribution, one can take the averaget payoff of the protocol over all possible joining orders.  
8 April 1st Voting games (Lecture 8, slides [8-up]): coalition is a term we use in politics. In this lecture, we show how we can model some voting situations using cooperative game theory. For example, we can describe what is a dictator, how we can represent the veto power, etc. We will see that this study allows one to measure the voting power of players in a game.  
9 April 8th Representation and complexity (Lecture 9, slides [8-up]): We wonder about how hard is it to compute some solution concepts. To deal with this question, we first need to know how the game is represented. We will introduce some succinct representations that allows for some efficient computations.  
10 April 12th Hedonic games and NTU games (Lecture 10, slides [8-up]): So far, we considered the case in which agents could compare their utility and transfer utilities. We look at the case in which this is not possible: agents cannot compare their utilities, hence transfer of utility does not make sense. To represent these games, the preferences of the agents are represented using ordinal preferences. We will first introduce hedonic games and then the more general definitions of non transferable utility (NTU) games. We will study an application which is similar to the market games for TU games: the exchange economy game.  
11 April 29th Other types of games, some issues for application (Lecture 11, slides [8-up]): this lecture consists of many different topics. We will start by considering the problem of searching for an optimal coalition structure, which uses AI techniques. Then, we will consider some games that are extensions of TU games. Finally, we will look at different issues that are not taken into account in TU games and that may play a role in practice.  

Papers for the final paper/presentation.

Last modified: Thu Apr 28 18:08:03 CEST 2011