Computer Science/Discrete Mathematics Seminar I
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,2] 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.
- http://www.ephraimkishon.de/en/my_favorite_stories.htm (english)
- https://gesherfilmfund.org.il/documents/מקבץ%20יצירות%20%20-%20אפרים%20… (hebrew, third story)