Linde Institute/SISL Seminar: Leonard Schulman, 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)