Damian Niwinski

### Algorithmic aspects of game theory

Lecture: Monday 8:30--10, room 4050
Tutorials: Monday 10:15--12, room 3170 Henryk Michalewski
Course 2014
Course 2012
Course 2009
Course 2005
USOS
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 games on graphs of possibly infinite duration, which can be viewed as an abstraction of social games.
Such games 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.

Teoria gier zostala zapoczatkowana przez von Neumanna i Morgensterna jako matematyczna teoria racjonalnego zachowania.
Gra sklada sie z opisu mozliwych posuniec i definicji funkcji zysku dla kazdego z graczy. Oczywiscie, kazdy z graczy stara sie
wybrac taka strategie, jaka maksymalizuje jego zysk. Najczesciej w teorii gier przyjmuje sie, ze racjonalne zachowanie graczy
jest dobrze opisywane pojeciem rownowagi Nasha.

Bardzo wiele rzeczywistych sytuacji pasuje do ogolnego schematu teorii gier. W ekonomii uzywa sie gier do modelowania
ewolucji rynku. W socjologii do modelowania konfliktow grup spolecznych. W informatyce gra moze modelowac
wspolzawodnictwo procesow o zasoby komputera, interakcje serwera z otoczeniem, lub zachowanie uzytkownikow Internetu.