skip to main content

Linde Institute/SISL Seminar: Leonard Schulman, Caltech

Friday, October 28, 2016
12:00pm to 1:00pm
Add to Cal
Baxter 127
The Duality Gap for Two-Team Zero-Sum Games
Leonard Schulman, Professor of Computer Science, Engineering & Applied Science, Caltech,

We consider multiplayer games in which the players fall in two teams of size $k$, with payoffs equal within, and of opposite sign across, the two teams. In the classical case of $k=1$, such zero-sum games possess a unique value, independent of order of play, due to the von Neumann minimax theorem. However, this fails for all $k>1$; we can measure this failure by a duality gap, which quantifies the benefit of being the team to commit last to its strategy. In our main result we show that the gap equals $2(1-2^{1-k})$ for $\m=2$ and $2(1-\m^{-(1-o(1))k})$ for $\m>2$, with $\m$ being the size of the action space of each player. At a finer level, the cost to a team of individual players acting independently while the opposition employs joint randomness is $1-2^{1-k}$ for $k=2$, and $1-\m^{-(1-o(1))k}$ for $\m>2$.

This class of multiplayer games is motivated from the Weak Selection model of evolution.

Joint work with Umesh Vazirani (UC Berkeley)

For more information, please contact Sheryl Cobb by phone at x4220 or by email at