A Caltech Library Service

The duality gap for two-team zero-sum games

Schulman, Leonard J. and Vazirani, Umesh V. (2017) The duality gap for two-team zero-sum games. In: 8th Innovations in Theoretical Computer Science Conference. Leibniz International Proceedings in Informatics. No.67. Dagstuhl Publishing , Saarbrücken, Germany, Art. No. 56. ISBN 978-3-95977-029-3.

[img] PDF - Published Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


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, apart from being a natural bridge between two-player zero-sum games and general multiplayer games, is motivated from Biology (the weak selection model of evolution) and Economics (players with shared utility but poor coordination).

Item Type:Book Section
Related URLs:
URLURL TypeDescription ItemJournal Article
Additional Information:© 2017 Leonard Schulman and Umesh Vazirani; licensed under Creative Commons License CC-BY. LJS was supported in part by NSF grants 1319745/1618795 and BSF grant 2012333; UVV was supported in part by NSF Grant CCF-1410022.
Funding AgencyGrant Number
Binational Science Foundation (USA-Israel)2012333
Classification Code:1998 ACM Subject Classification: G.1.6 Optimization
Record Number:CaltechAUTHORS:20190402-143205523
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94377
Deposited By: Tony Diaz
Deposited On:02 Apr 2019 21:44
Last Modified:04 Apr 2019 21:26

Repository Staff Only: item control page