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.

  1. http://www.ephraimkishon.de/en/my_favorite_stories.htm (english)
  2. https://gesherfilmfund.org.il/documents/מקבץ%20יצירות%20%20-%20אפרים%20 (hebrew, third story)

Date & Time

October 16, 2023 | 11:15am – 12:15pm

Location

Simonyi 101 and Remote Access

Speakers

Shay Moran, Technion