Random Games

Alice and Bob compete in a game of skill, making moves alternately until one or other reaches a winning position, at which the game ends. Or, perhaps neither player can force a win, in which case optimal play continues forever, and we say that the game is drawn. What is the outcome of a typical game? That is, what happens if the game itself is chosen randomly, but is known to both players, who play optimally? I will provide some answers (any many questions) in several settings, including trees, directed and undirected lattices, and point processes. The competitive nature of game play frequently brings out some of the subtlest and most fundamental properties of probabilistic models. We will encounter continuous and discontinuous phase transitions, hard-core models, probabilistic cellular automata, bootstrap percolation, maximum matching, and stable marriage. (Based on joint works with Riddhipratim Basu, Maria Deijfen, Irene Marcovici, James Martin and Johan Wastlund.)

Date:

February 4, 2016

Speakers:

Alexander E. Holroyd

Affiliation:

Microsoft Research