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

Perfect information games. Examples: chess, checkers, Hex.
Solving Hex: strategy stealing argument.
A geometrical lemma explaining why there are no draws.

Infinite games. Example: Choquet's games.

6 March 2019

Why determinacy is an issue. An example of a 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: arenas, moves, plays, traps, Gardens of Eden.

Knaster-Tarski theorem. Game equations and their least and greatest fixed points. Decomposition of an arena into fixed points corresponding to the winning (or draw) regions.

13 March 2019

Mathematical definition of a strategy: a (partial) function that suggests next move to a player.
It is defined for a partial play provided that the player has obeyed the strategy so far.

Alternatively: a set of plays, where the player never loses although the oponent is free in his (her) choices.

Positional (memoryless) strategies. Example that in general memory is needed.

Winning in finite time --- a player who cannot move, loses. An infinite play means survival of both players.

Determinacy theorem. For any position, either one of the players has a strategy to win in finite time, or both have strategies to survive.

20 March 2019

Polynomial time algorithm to compute winning regions and positional strategies in reachability games by an approximation of fixed points.
An improvement to a linear algorithm.

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

27 March 2019

Positional determinacy of parity games. Proof for finite arenas.
See notes, sect. 7.1; for arbitrary arenas see notes (in Polish).

Naive algorithm to compute winning regions and winning strategies in time 2^n poly(n). Note that the problem is is NP and co-NP.

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

3 April 2019:

An informal presentation of a progress measure algorithm for parity games.

A public defence of the PhD thesis by Marcin Przybyłko: Stochastic games and their complexities.
More information about the thesis, and presentation.

10 April 2019

A quasi-polynomial algorithm for solving parity games (after Karoliina Lehtinen).

Reduction of a parity game to a parity game using k registers and ranks in 0,1,...,2k+1.
The equivalence of these game, for a sufficiently large k.

17 April 2019

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.

24 April 2019

Mean payoff games. While passing an edge ranked x, Adam pays x to Eve (may be negative).
Each player wants to maximize her/his income.

Finite variant: the value of a (finite) play is the mean on the first loop formed in this play.
Infinite variant: the value is the asymptotic mean.

Observation: a strategy from the finite game can be used in the infinite game!
Conclusion: for each position, there is a compromise value, the same in both games.

8 May 2019

Mean payoff games continued.
On finite arenas, both players have optimal positional strategies.

A pseudo-polynomial algorithm computing the game values on an arena with n vertices and weights in [-d,d]
in time polynomial on n and d, where d is given in unary.

15 May 2019

The general inequality max min f(x,y) vs. min max f(x,y). A characterization of
determinacy of a zero-sum game in terms of the equality max min f(x,y) = min max f(x,y) (if it holds).

Strategic games and equilibria -- informally.

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

22 May 2019

More examples: auctions (mechanism design), rock-paper-scissor, matching pennies (equilibria may not exist).

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.

29 May 2019

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.

Symmetric games and symmetrization of arbitrary two-player games.

5 June 2019

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 this tab is borrowed from a song by Tom Paxton.