Cooperative Games - 2010 (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).
Prerequisite
none.
Course material.
There is no textbook for this course. The slides will be posted shortly before each class, additional handouts will also be posted.

Week date topic course work
1 February 1st Introduction (8up): 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 8st The core (8up): The core is a stability solution concept. We will look at some examples, and we will show that some games have empty core. We will also present a class of games with a non-empty core: the convex games. The proof of the theorems done in class are in the following handout.  
3 February 15th The core (8up)(continuation). We will characterize the set of games with non-empty core (Bondareva Shapley theorem). We will apply the theorem to market games. We will present some other classes of games with non-empty core. We will talk about the computational complexity of computing an element in the core. The proof made in class are in the following handout. Homework 1
due February 22nd.
4 February 22nd Games with coalition structures and the bargaining set (8up). We will consider games where the set of agents is already partitioned into coalitions, and where agents need to share the value of their coalitions. We will consider the definition of the core for such games. The core is also not guaranteed to be non-empty, hence, it would be good to relax some stability requirements. 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 certain objection and counter objection.  
5 March 1st The nucleolus (8up).We introduce another stability solution concept called the nucleolus. This solution concept is also a member of the bargaining set family as it can be defined using objections and counter-objections. We will see that the nucleolus has two nice properties: it is non-empty when the set of imputations is non-empty, and it contains at most one element! Hence, the agents have one way to reach an agreement. We will prove both properties, which requires quite some work.  
6 March 8th End of the nucleolus, and the kernel (8up). We finish to prove that the nucleolus has at most one element. Then, we introduce the kernel, another stability concept from the bargaining set family. As the nucleolus, its definition uses the excess of a coalition, though in a different way. We will prove that both the kernel and the bargaining set are non-empty, and we will look at an algorithm to compute a kernel-stable payoff distribution. Homework 2
due March 15th.
7 March 15th End of the Kernel, and start of the Shapley value (8up).We will finish the discussion about the kernel. We will prove that the kernel is included in the bargaining set, and then we will consider an algorithm to obtain a kernel-stable payoff distribution. Then, we will discuss a final solution concept that is promoting fairness, and not necessarily stability: the Shapley value.  
exam week March 22nd no lecture  
8 March 29th End of the Shapley value and Simple games (8up). Then, we will start to have a closer look at TU games that model voting, and we will consider ways to measure the power of players. Homework 3
due April 12th.
Tweede Paasdag April 5th no lecture  
9 April 12th Representation and complexity (8up):We will finish the discussion about power indices. Then, we will consider the issue of representation of coalitional games and the complexity of computing the solution concepts.  
10 April 19th Hedonic and NTU games (8up): We provide a brief introduction to games where it is not possible to exchange utility. Instead of a valuation function, agents have a preference relation. We first study hedonic games, a special type of NTU games. Then, we introduce the general definition of an NTU games, and we define the core of such games. We will study the exchange economy game.  
11 April 26th Deriving cooperative games from non-cooperative ones and the matching game. Homework 4
due Friday May 7.
12 May 3rd Games with externalities and short survey of issues in coalition formation (8up)  
13 May 10th no lecture  
14 May 17th Presentation day
Morning session: A1.08, 11h-13h
  • Annamieke and Ole [slides]
    • Enumeration and exact design of weighted voting games.
    • The distribution of power in the European Constitution.
  • Costin and Matthias [slides]
    • Sequential decision making in repeated coalition formation under uncertainty
    • Bayesian coalitional games
  • Irma [slides]
    • Overlapping Coalition Formation
  • Pål and Sylvia [slides]
    • On the complexity of cooperative solution concepts
    • Computing shapley values, manipulating value division schemes, and checking core membership in multi-issue domains
Afternoon session: A1.06, 15h-17h
  • Erik and Navid
    • Marginal contribution nets: a compact representation scheme for coalitional games [slides]
    • A Logic-Based Representation for Coalitional Games with Externalities [slides]
  • Helen and Øystein [slides]
    • A Compact Representation Scheme for Coalitional Games in Open Anonymous Environments
    • Coalitional games in open anonymous environments
  • João and Karun
    • An algorithm for distributing coalitional value calculations among cooperating agents.[slides]
    • An anytime algorithm for optimal coalition structure generation [slides]
  • Bardia and Magnus [slides]
    • Feasible Formation of Coalitions Among Autonomous Agents in Nonsuperadditive Environments
    • On safe kernel stable coalition forming among agents.
 


Papers for the final paper/presentation.
Last modified: Fri May 28 12:46:33 CEST 2010