Game Theory (MSc)

People

Prof. Dr. Jürgen Dix

Niklas Fiekas, M.Sc.

Overview of the course

This course is about decision making between several agents: How to reach a conclusion? How to sell goods? Assuming that all agents are self-interested, are there protocols (i.e. games) that ensure an outcome that is globally optimal? How to design such games (Mechanism Design)?

We start by considering decisions of individual agents: what strategy should an agent apply when entering in a game and when all information about other agents are public? Such games are called complete information games and are dealt with in Chapter 1. Repeated games are considered in Chapter 2. Chapter 3 considers the case where agents form teams and work together. How should the payoff of such a coalition be distributed?

Chapter 4 considers classical voting mechanisms and auctions. Chpater 5 extends games to the case where agents do not know about the payoffs of other agents and thus are not sure about how they behave and what strategies are appropriate. The design of suitable mechanisms to optimize the global good when all agents are selfish and do not reveal their true interests is the focus of Chapter 6.

Finally, in Chapter 7 we introduce a particular logic, ATL, where we can express the notion that "agents are able to bring about something". We define an extension of this logic, ATLP, where we can express solution concepts that we introduced in previous chapters. The logic allows then to reason about these concepts within the logic and to do, e.g. model checking.

Important: First Lecture: 25.10.2017
Registration: Please subscribe in the StudIP system.

Content

Chapter 1: Complete Information  Games

Evaluation criteria: how to evaluate the quality of protocols? After  investigating several examples, we define the formal framework of non-cooperative games in normal form (moves are done simultaneously). We prove von Neumann's max-min theorem and Nash's generalization of it. We then consider games in extensive form which allow for strategies based on the history of the game. We distinguish between perfect and imperfect recall. Finally we discuss a model for a general equilibrium for a market, where goods are consumed and manufactured.

Chapter 2: Repeated Games

What if a game is not played once, but several times? And players may use strategies that take into account the past games? This area is called Repeated Games and the analysis of such games heavily depend on whether they are played only a finite number of times or infinitely often. A well-known (empirical) result from Axelrod is the tit-for-tat strategy for the iterated prisoners dilemma game.

Chapter 3: Coalitional Game Theory 

Up to now we have considered agents that act alone and are selfish. Sometimes agents  form coalitions (if their individuel payoff in the coalition is greater than when acting alone). So the questions arise, which coalitions form and how the achieved payoff should be distributed to the agents. The two main solution concepts are the Shapley value and the Core (and their refinements)

Chapter 4: Social Choice and Auctions

Letting agents vote for decision making seems reasonable. However, most voting systems are far from being perfect. Social choice theory is a general  framework to consider election mechanisms and their properties. Arrow's theorem shows, that under reasonable rational assumptions there always exists a dictator. We end this chapter with auctions, particular mechanisms that have been designed to achieve binding contracts between a pair of agents. They are classical examples of  applying  mechanism design (which will be treated in  Chapter 6).

Chapter 5: Incomplete Information Games

The games in previous chapters were complete information games: all agents were aware of the payoffs of all other agents and the rules of the games (e.g. actions of the players). This is in general not the case. Agents have  private information (their type) that they do not disclose. How can we model such games and define notions of equilibria? How can they be computed?

Chapter 6: Mechanism Design

Agents might also lie (vote tactically) to get what they want. Is it possible to implement a non-manipulable voting system? This area is called mechanism design or inverse game theory: one looks at designing a protocol that ensures particular properties of the equilibria states, no matter what the secret preferences of the agents are.

Chapter 7: Strategic Logics 

(Here we come back to the first chapter and show how to express strategic reasoning **within** a logic (ATLP). ATL and ATL* are steps on this way. In ATLP we can formalize the equilibrium concepts from Chapter 1 and do model checking.)

Note: In the lecture, we will treat chapter 4 before chapter 3!