Combinatorics Seminar - Spring '22

When: Sunday, March 13, 10am

Where: Schreiber 309

Speaker: Shay Moran, Technion

Title: A Combinatorial Characterization of Minimax in 0/1 Games


We will discuss a generalization of the celebrated Minimax Theorem (von Neumann, 1928) for binary zero-sum games. A simple game which fails to satisfy Minimax is Ephraim Kishon's "Jewish Poker" (see [1] below). In this game, each player picks a number and the larger number wins. The payoff matrix in this game is *infinite triangular*. We show this is the only obstruction: if a game does not contain triangular submatrices of unbounded sizes then the Minimax Theorem holds. This generalizes von Neumann's Minimax Theorem by removing requirements of finiteness or compactness. The talk will be self contained; in particular no background in game-theory will be assumed.

Joint work with Steve Hanneke and Roi Livni.

[1] (english)