Document Open Access Logo

Game Efficiency Through Linear Programming Duality

Author Nguyen Kim Thang

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.66.pdf
  • Filesize: 490 kB
  • 20 pages

Document Identifiers

Author Details

Nguyen Kim Thang
  • IBISC, Univ Evry, University Paris Saclay, Evry, France

Funding

Research supported by the ANR project OATA no ANR-15-CE40-0015-01.

Cite AsGet BibTex

Nguyen Kim Thang. Game Efficiency Through Linear Programming Duality. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 66:1-66:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ITCS.2019.66

Abstract

The efficiency of a game is typically quantified by the price of anarchy (PoA), defined as the worst ratio of the value of an equilibrium - solution of the game - and that of an optimal outcome. Given the tremendous impact of tools from mathematical programming in the design of algorithms and the similarity of the price of anarchy and different measures such as the approximation and competitive ratios, it is intriguing to develop a duality-based method to characterize the efficiency of games. In the paper, we present an approach based on linear programming duality to study the efficiency of games. We show that the approach provides a general recipe to analyze the efficiency of games and also to derive concepts leading to improvements. The approach is particularly appropriate to bound the PoA. Specifically, in our approach the dual programs naturally lead to competitive PoA bounds that are (almost) optimal for several classes of games. The approach indeed captures the smoothness framework and also some current non-smooth techniques/concepts. We show the applicability to the wide variety of games and environments, from congestion games to Bayesian welfare, from full-information settings to incomplete-information ones.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory and mechanism design
Keywords
  • Price of Anarchy
  • Primal-Dual

Metrics

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

Related Versions

References

  1. Robert J Aumann. Subjectivity and correlation in randomized strategies. Journal of mathematical Economics, 1(1):67-96, 1974. Google Scholar
  2. Kshipra Bhawalkar, Martin Gairing, and Tim Roughgarden. Weighted congestion games: the price of anarchy, universal worst-case examples, and tightness. ACM Transactions on Economics and Computation, 2(4):14, 2014. Google Scholar
  3. Kshipra Bhawalkar, Sreenivas Gollapudi, and Kamesh Munagala. Coevolutionary opinion formation games. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 41-50. ACM, 2013. Google Scholar
  4. Kshipra Bhawalkar and Tim Roughgarden. Welfare guarantees for combinatorial auctions with item bidding. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 700-709. SIAM, 2011. Google Scholar
  5. Vittorio Bilo. A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. In International Workshop on Approximation and Online Algorithms, pages 215-228, 2012. Google Scholar
  6. Niv Buchbinder and Joseph Naor. The design of competitive online algorithms via a primal: dual approach. Foundations and Trendsregistered in Theoretical Computer Science, 3(2-3):93-263, 2009. Google Scholar
  7. Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, Maria Kyropoulou, Brendan Lucier, Renato Paes Leme, and Eva Tardos. Bounding the inefficiency of outcomes in generalized second price auctions. Journal of Economic Theory, 156:343-388, 2015. Google Scholar
  8. Roberto Cominetti, José R Correa, and Nicolás E Stier-Moses. The impact of oligopolistic competition in networks. Operations Research, 57(6):1421-1437, 2009. Google Scholar
  9. José R Correa, Andreas S Schulz, and Nicolás E Stier-Moses. A geometric approach to the price of anarchy in nonatomic congestion games. Games and Economic Behavior, 64(2):457-469, 2008. Google Scholar
  10. Constantinos Daskalakis and Vasilis Syrgkanis. Learning in auctions: Regret is hard, envy is easy. In 57th Annual Symposium on Foundations of Computer Science (FOCS),, pages 219-228, 2016. Google Scholar
  11. Michal Feldman, Hu Fu, Nick Gravin, and Brendan Lucier. Simultaneous auctions are (almost) efficient. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 201-210. ACM, 2013. Google Scholar
  12. Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, and Vasilis Syrgkanis. The price of anarchy in large games. In Proc. 48th Symposium on Theory of Computing (STOC), pages 963-976, 2016. Google Scholar
  13. Tobias Harks. Stackelberg strategies and collusion in network games with splittable flow. Theory of Computing Systems, 48(4):781-802, 2011. Google Scholar
  14. Avinatan Hassidim, Haim Kaplan, Yishay Mansour, and Noam Nisan. Non-price Equilibria in Markets of Discrete Goods. In Proc. 12th ACM Conference on Electronic Commerce, pages 295-296, 2011. Google Scholar
  15. Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. Computer science review, 3(2):65-69, 2009. Google Scholar
  16. Vijay Krishna. Auction theory. Academic press, 2009. Google Scholar
  17. Janardhan Kulkarni and Vahab Mirrokni. Robust price of anarchy bounds via LP and fenchel duality. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1030-1049. SIAM, 2015. Google Scholar
  18. Renato Paes Leme, Vasilis Syrgkanis, and Éva Tardos. Sequential auctions and externalities. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 869-886. SIAM, 2012. Google Scholar
  19. Giorgio Lucarelli, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. Online Non-preemptive Scheduling in a Resource Augmentation Model based on Duality. In European Symposium on Algorithms, 2016. Google Scholar
  20. Konstantin Makarychev and Maxim Sviridenko. Solving optimization problems with diseconomies of scale via decoupling. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 571-580. IEEE, 2014. Google Scholar
  21. Hervé Moulin and J-P Vial. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3-4):201-221, 1978. Google Scholar
  22. Uri Nadav and Tim Roughgarden. The limits of smoothness: A primal-dual framework for price of anarchy bounds. In International Workshop on Internet and Network Economics, pages 319-326, 2010. Google Scholar
  23. John F Nash. Equilibrium points in n-person games. Proc. Nat. Acad. Sci. USA, 36(1):48-49, 1950. Google Scholar
  24. Tim Roughgarden. Intrinsic robustness of the price of anarchy. Journal of the ACM (JACM), 62(5):32, 2015. Google Scholar
  25. Tim Roughgarden. The price of anarchy in games of incomplete information. ACM Transactions on Economics and Computation, 3(1):6, 2015. Google Scholar
  26. Tim Roughgarden and Florian Schoppmann. Local smoothness and the price of anarchy in splittable congestion games. Journal of Economic Theory, 156:317-342, 2015. Google Scholar
  27. Tim Roughgarden, Vasilis Syrgkanis, and Eva Tardos. The Price of Anarchy in Auctions. Journal of Artificial Intelligence Research, 59:59-101, 2017. Google Scholar
  28. Tim Roughgarden and Éva Tardos. How bad is selfish routing? Journal of the ACM (JACM), 49(2):236-259, 2002. Google Scholar
  29. Tim Roughgarden and Éva Tardos. Bounding the inefficiency of equilibria in nonatomic congestion games. Games and Economic Behavior, 47(2):389-403, 2004. Google Scholar
  30. Vasilis Syrgkanis and Eva Tardos. Bayesian sequential auctions. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 929-944. ACM, 2012. Google Scholar
  31. Vasilis Syrgkanis and Eva Tardos. Composable and efficient mechanisms. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 211-220. ACM, 2013. Google Scholar
  32. Nguyen Kim Thang. Game Efficiency through Linear Programming Duality. CoRR, 2017. URL: http://arxiv.org/abs/1708.06499.
  33. Rakesh V Vohra. Mechanism design: a linear programming approach, volume 47. Cambridge University Press, 2011. Google Scholar
  34. David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge university press, 2011. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact