Date:
Mon, 29/11/202115:00-17:00
Location:
B400 (CS\Engineering building)
HUJI Combinatorics Seminar
When: Monday November 29th, 2021, at 3PM (Israel time)
Where: B400 in the CS\Engineering building
Speaker: Shay Moran (Technion)
Title: A Combinatorial Characterization of Minimax in 0/1 Games
Abstract:
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,2] below), where 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)
[2] https://gesherfilmfund.org.il/documents/מקבץ%20יצירות%20%20-%20אפרים%20קישון.pdf (hebrew, third story)
When: Monday November 29th, 2021, at 3PM (Israel time)
Where: B400 in the CS\Engineering building
Speaker: Shay Moran (Technion)
Title: A Combinatorial Characterization of Minimax in 0/1 Games
Abstract:
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,2] below), where 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)
[2] https://gesherfilmfund.org.il/documents/מקבץ%20יצירות%20%20-%20אפרים%20קישון.pdf (hebrew, third story)