The Duality Gap for Two-Team Zero-Sum Games

Authors Leonard Schulman, Umesh V. Vazirani



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.56.pdf
  • Filesize: 433 kB
  • 8 pages

Document Identifiers

Author Details

Leonard Schulman
Umesh V. Vazirani

Cite AsGet BibTex

Leonard Schulman and Umesh V. Vazirani. The Duality Gap for Two-Team Zero-Sum Games. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 56:1-56:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ITCS.2017.56

Abstract

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).
Keywords
  • multi-player games
  • duality gap
  • zero-sum games
  • evolution

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. H Akashi. Inferring weak selection from patterns of polymorphism and divergence at "silent" sites in Drosophila DNA. Genetics, 139(2). Google Scholar
  2. R Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1:67-96, 1974. Google Scholar
  3. E Chastain, A Livnat, C Papadimitriou, and U Vazirani. Algorithms, games, and evolution. Proc. National Academy of Sciences, 2014. Google Scholar
  4. R H Coase. The nature of the firm. Economica, New Series, 4(16):386-405, Nov. 1937. Google Scholar
  5. P Erdös. On a problem in graph theory. Math. Gaz., 47:220-223, 1963. Google Scholar
  6. R L Graham and J H Spencer. A constructive solution to a tournament problem. Canad. Math. Bull., 14(1):45-48, 1971. Google Scholar
  7. R Mehta, I Panageas, and G Piliouras. Natural selection as an inhibitor of genetic diversity: Multiplicative weights updates algorithm and a conjecture of haploid genetics. In Proc. ITCS, page 73. ACM, 2015. Google Scholar
  8. T Nagylaki. The evolution of multilocus systems under weak selection. Genetics, 134(2):627-647, 1993. Google Scholar
  9. MA Nowak, A Sasaki, C Taylor, and D Fudenberg. Emergence of cooperation and evolutionary stability in finite populations. Nature, 428:646-650, 2004. URL: http://dx.doi.org/10.1038/nature02414.
  10. T Ohta. Near-neutrality in evolution of genes and gene regulation. Proc. National Academy of Sciences, 99(25):16134-16137, 2002. URL: http://dx.doi.org/10.1073/pnas.252626899.
  11. T Roughgarden and E Tardos. Ch. 17: Introduction to the inefficiency of equilibria. In N Nisan, T Roughgarden, E Tardos, and V V Vazirani, editors, Algorithmic Game Theory. Cambridge U Press, 2007. Google Scholar
  12. J Von Neumann. Zur theorie der gesellschaftsspiele. Math. Ann., 100:295-320, 1928. Google Scholar
  13. B Wu, PM Altrock, L Wang, and A Traulsen. Universality of weak selection. Physical Review E, 82:046106, 2010. Google Scholar
  14. B Wu, J García, C Hauert, and A Traulsen. Extrapolating weak selection in evolutionary games. PLoS Comput Biol, 9(12), 2013. URL: http://dx.doi.org/10.1371/journal.pcbi.1003381.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail