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.
- lecturer: Stéphane Airiau
- dates/location: one class weekly Monday 15-17, Science Park B0.206.
- evaluation: coursework (~biweekly homework assignments) and presentation of a paper at the end.
- the course is worth 6ECTS
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 6th | Introduction (notes slides [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 13th | The core (notes for lecture 2 and 3 slides [8up]). We will see the definition of the core, we will visualize it for games of two or three players, we will discuss some classes of games with non-empty core. We will end the lecture by presenting a characterization of the games with non-empty core. | |
| 3 | February 20th | A characterization of the core: the Bondareva Shapley theorem (slides [8up]). We will study a characterization of the core, which follows from the application of a theorem in linear optimization. We will apply this theorem to market games. If time permits, we will consider a slight variant of games: games with coalition structure. | H1 due Feb 27th |
| 4 | February 27th | The bargaining set (notes slides [8up]). Since some games have an empty core, we want to weaken the stability constraints of the core to obtain a stable solution concept that is always non-empty. We start with the bargaining set, in which agents bargain for finding a stable payoff distribution. | |
| 5 | March 5th | The nucleolus (notes slides [8up]). 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 12th | The kernel (notes slides [8up]): this is the last stability concept we will study. It is also based on the excess, but this time measuring a power to gain payoff. | H2 Homework 2 due Friday March 23rd, 5pm |
| 7 | March 19th | The Shapley value (notes slides [8up]): This lecture is about a solution concept that promotes fairness: agents should receive a payoff that reflects her contribution. The idea of the Shapley value is that agents receives a payoff that is proportional to her contribution. We will see how to formalise this idea, and we will see that we can also define the Shapley value using the axiomatic method. | |
| 8 | April 2rd | Voting games (notes slides [8up]). Politicians form coalitions in parliament. In this lecture, we are going to see how we can use cooperative games to talk about elections. We will also see that the Shapley value can be a good way to measur the voting power of a voter in an election. | |
| 9 | April 16th | No class||
| 10 | April 23rd | Representation and complexity (notes slides [8up]). | |
| 11 | May 7th | Hedonic games and NTU games(notes slides [8up]). | h4 due May 14th |
| 12 | May 14th | Other types of games, some issues for application (notes slides [8up]) |
Friday June 8th, room B0.208
- First session
- 13:00 -- 13:10 opening remarks
- 13:10 -- 13:35 Michal Gianluigi Greco, Enrico Malizia, Luigi Palopoli, Francesco Scarcello. On the Complexity of the Core over Coalition Structures
- 13:35 -- 14:00 Apostolos H. Aziz and F. Brandl. Existence of Stability in Hedonic Coalition Formation Games.
- 14:00 -- 14:25 Alexander Georgios Chalkiadakis, Vangelis Markakis, Nick Jennings. Coalitional Stability in Structured Environments
- 14:25 -- 14:50 Femke Reshef Meir, Jeffrey S. Rosenschein, Enrico Malizia. Subsidies, Stability, and Restricted Cooperation in Coalitional Games
- Second Session
- 15:10 -- 15:35 Justin H. Aziz, Y. Bachrach, E. Elkind and M. Paterson. False-Name Manipulations in Weighted Voting Games.
- 15:35 -- 15:00 Maximilian Yoram Bachrach, Edith Elkind, Piotr Faliszewski. Coalitional Voting Manipulation: A Game-Theoretic Perspective
- 16:00 -- 16:25 Andreea Yoram Bachrach. Honor among thieves: collusion in multi-unit auctions
- 16:25 -- 16:50 Callum Valentin Goranko, Wojciech Jamroga. State and Path Coalition Effectivity Models for Logics of Multi-Player Games
- 16:50 -- 17:15 Zeno E. Algaba, J.M. Bilbao, J.L. Fernández, The distribution of power in the European Constitution
Last modified: Thu Feb 9 18:01:32 CET 2012