Menagerie of games. Relevant features: #players, perfect information, randomness, simultaneous moves.

Perfect information games. Examples: chess, checkers, Hex.
Solving Hex: strategy stealing argument.

Infinite games. Example: Choquet's games.

7 March 2018

Example of perfect information indeterminate game: infinite XOR (no player has a winning strategy).

Zermelo's theorem. In chess, either White has a winning strategy, or Black has a winning strategy, or both players have strategies to achieve at least a draw.

Modeling games by graphs. Basic concepts: arena, moves, play, trap, Garden of Eden.

Knaster-Tarski theorem. Game equations and their fixed points (to be continued).

14 March 2018

Mathematical definitions of a strategy: a (partial) function over plays, or a set of plays, that
guarantees that the player owning the strategy cannot loose.

Positional strategies. Example that it is not always so.

Winning in finite time. Finitely winning positions vs. safe positions.

Zermelo's theorem in general setting, i.e., for arbitrary perfect information game. (Proof.)

21 March 2018

Polynomial time algorithm to compute the winning sets and positional strategies in reachability games.
Mentioning of a linear time algorithm.

Games over colored arenas. Isomorphism of games. Parity games.

Games with memory.

4 April 2018

Muller games -- the winning criterion for Eve is specified by a family of sets of colors that can appear infinitely often in a play.
(This captures parity games and many others.)

Reduction of Muller games to parity games via the concept of latest appearance record (LAR).

Positional determinacy of parity games. Proof for finite arenas (start).

11 April 2018

Positional determinacy of parity games. Proof for finite arenas (cf. notes, sect. 7.1).
Naive algorithm in time 2^n poly(n).

Towards a more efficient algorithm. Reduction of parity game with d ranks to a reachability/survival game with ca. n^{d/2} positions (cf. slides, pages 18-27).

18 April 2018

Towards a yet more efficient algorithm. Reduction to register games
(cf. paper by Karoliina Lehtinen).

25 April 2018

Continuation. The log n + const upper bound on the number k of registers in a register game equivalent to a given parity game with n positions.

This yields a quasi-polynomial (n^{O( log n) }) bound on the computation time of solving parity games.
Previously known algorithms were exponential (n^{O( sqrt n) }).
It is an open problem whether a polynomial algorithm exists.

9 May 2018

Strategic games. Equilibrium -- informally.

Examples: Prisoners' dillema, Tragedy of the commons, Routing congestion game -- Braess's paradox, Battle of the sexes.

16 May 2018

Strategic games more formally. Pure strategies, utility functions, profiles. Best answers, Nash equilibria.

Randomized (mixed) strategies, randomized equilibria. Nash's theorem: randomized equilibria always exist.

23 May 2018

Proof of Nash's theorem via Brouwer's fixed point theorem.

Towards an algorithm: reducing the continuous problem to a discrete problem of determining supports.

30 May 2018

Lemke-Howson algorithm to find Nash equilibrium in 2-player game. Version for symmetric games, where a symmetric equilibrium exists.

A distribution p=(p_1,...,p_n) defines a Nash equilibrium if any p_i is either 0, or the pure strategy a_i is the best answer to p.
Therefore it can be represented as a solution of n linear equations.
Geometrically, it makes a vertex of an n-dimensional polytope, which can be reached from a vertex (0,...,0) by an appropriate walk on the edges.

Note. The title of the site is borrowed from a song by Tom Paxton.