Borel meets Games

GAMENET Training school on Borel Games

Date and Venue: 2021 August 2-4 on Zoom.

Speakers: Galit Ashkenazi-Golan (Tel-Aviv University), János Flesch (Maastricht University), Erez Nesharim (Hebrew University), Ron Peretz (Bar Ilan University), Arkadi Predtetchinski (Maastricht University), Eran Shmaya (Stony Brook University), Eilon Solan (Tel-Aviv University)

Topic: In even stages 0,2,4,... Player 1 selects a bit (0 or 1), and in odd stages 1,3,5,... Player 2 selects a bit (0 or 1). This way the two players select (the binary representation of) a number in the unit interval x. Player 1 wins if x is in some given target set A, and Player 2 wins otherwise. Does necessarily one of the players have a winning strategy, namely, a strategy that guarantees that that player wins, regardless of the choices of the other players? The game we just described is an infinite-horizon extensive-form game. The determinacy of this game, namely, the existence of a winning strategy to one of the players, is an extension of the famous Zermelo's Theorem to this setup, and was fully answered in 1975 by Donald Martin.

Borel games are two-player alternating-move games where the action sets of each player after each history may be an arbitrary set, and the winning set is a Borel set of plays. The determinacy of Borel games is a momentous result. It has numerous applications in set theory, topology, logic, computer science, and, of course, in game theory. In 1998 Martin extended his determinacy result to two-player zero-sum simultaneous-move games with both players have finite action sets. The two results were then unified and extended by Eran Shmaya in 2011, who studied alternating-move games with eventual perfect monitoring.

In this training school we intend to go over some of the determinacy results and their applications. Our approach is didactic, and our ambition is to guide the participants through the details of the results and the proofs. We also present very recent papers with applications of Borel games to game theory and analysis.

Some readings: This, this and this.

Welcome: PhD students, MSc students, researchers, anybody who is interested.

Registration: It is free but required: Please send an e-mail to BorelGames2021TS at protonmail dot com.

Program: Hours meant in CEST (Paris time).

Day 1: Monday, August 2

08:50: Miklós Pintér: Welcoming words

09:00-10:30: Ron Peretz: Martin 75: the seminal paper of Martin, proving that in alternating-move games with a winning set are determined: Video

11:00-12:30: Arkadi Predtetchinski: EFKNPP2020: games whose payoff function is the limsup functions: Video

13:30-15:00: Erez Nesharim: On Schmidt games and some applications in dynamics and number theory: Video

Day 2: Tuesday, August 3

09:00-10:30: János Flesch: Mertens-Neyman 86: Equilibrium in multiplayer nonzero-sum alternating-move games: Video

11:00-12:30: Ron Peretz: Martin 98: Existence of the value in two-player zero-sum simultaneous-move games: Video

13:30-15:00: Eran Shmaya: Shmaya 11: Determinacy of two-player alternating-move games with a winning set, when information on the other player's move is obtained with delay: Video

Day 3: Wednesday, August 4

09:00-10:30: Galit Ashkenazi-Golan: AFPS 21: Regularity of the value and equilibrium in games with finitely many players and tail-measurable payoffs: Video

11:00-12:30: János Flesch: AFPS 21: Repeated games with countably many players and tail-measurable payoffs: Video

13:30-15:00: Eilon Solan: AFPS 21: Big Match games/Absorbing games with tail-measurable payoffs: Video

15:00: Miklós Pintér: Ending words