Algorithmic aspects of game theory

elective monographs

Game theory was initiated by von Neumann and Morgenstern as a mathematical theory of rational behaviour. A game comprises description of possible moves and payoffs for each of the players. Typically, each player searches for a strategy maximizing her payoff. The rational behaviour of players is well described by the concept of Nash equilibrium.

Game theory was initiated by von Neumann and Morgenstern as a mathematical theory of rational behaviour. A game comprises description of possible moves and payoffs for each of the players. Typically, each player searches for a strategy maximizing her payoff. The rational behaviour of players is well described by the concept of Nash equilibrium.

Many real-life phenomena can be described by games. In computer science games can model,e.g., processes competing for shared resources, or a system interacting with environment. In economy, games model behaviour of market, and in sociology behaviour of social groups.

The course will present the basic concepts of game theory including the Nash equilibrium, games with perfect or imperfect information (like chess or bridge, respectively), zero-sum games, social choice theory (e.g., voting), and auctions.

We will give special attention to infinite games on graphs, which have been proposed for use in computer-aided verification, and are connected to automata theory. Computing the winning or optimal strategies in such games constitutes a challenging open problem in algorithmics.

Guillermo Owen, Game theory, Emerald Group Publishing Limited; 3rd edition, 1995,

Philip D. Straffin, Game Theory and Strategy, The Mathematical Association of America, 1996,

E. Graedel, W. Thomas, and T. Wilke, Automata, Logics, and Infinite Games, Lecture Notes in Computer Science 2500, Springer 2002.

N.Nisan, T.Roughgarden, E.Tardos, V.Vazirani eds., Algorithmic Game Theory, Cambridge U.Press, 2007.

Knowledge

Student

1. recognizes both extensive-form games and strategic games and understands the concepts of determinacy and equilibria proper to both cases,

2. learns the theorems about the determinacy of some relevant games (e.g. parity games), and the existence of a Nash equilibria, and understands the algorithmic consequences of these results,

3. learns algorithms applicable to extensive games, including infinite games and mean-payoff games; learns the problems related to computational complexity of such games,

4. learns algorithmic difficulty of finding the Nash equilibria, and the Lemke-Howson algorithm.

Skills

Student is able

1. to find a mathematical structure behind social games, and construct algorithms solving such games,

2. to adapt the learned techniques to solve infinite games with various winning conditions,

3. to model some informatics situation in terms of games,

4. to implement at least one method of finding the Nash equilibrium.

Competence

Student

1. understands the increasing role of games in modeling informatics scenarios, especially those related to distribution and interaction, like e.g. Internet and social networks,

The exam consists of solving some number of problems within an indicated term (usually a few days).

In the case of completing the course by a doctoral student, the student will prepare a short report proposing some original research problems related to the course and relevant literature. A chat with a lecturer about the report will be a part of the exam.