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] http://www.ephraimkishon.de/en/my_favorite_stories.htm (english)