Wealth Inequality and the Price of Anarchy

Authors Kurtuluş Gemici, Elias Koutsoupias, Barnabé Monnot, Christos H. Papadimitriou, Georgios Piliouras



PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.31.pdf
  • Filesize: 0.53 MB
  • 16 pages

Document Identifiers

Author Details

Kurtuluş Gemici
  • Department of Sociology, National University of Singapore, Singapore
Elias Koutsoupias
  • Department of Computer Science, University of Oxford, United Kingdom
Barnabé Monnot
  • Engineering Systems & Design, Singapore University of Technology and Design, Singapore
Christos H. Papadimitriou
  • Department of Computer Science, Columbia University, United States of America
Georgios Piliouras
  • Engineering Systems & Design, Singapore University of Technology and Design, Singapore

Acknowledgements

Kurtuluş Gemici acknowledges NUS Strategic Research Grant (WBS: R-109-000-183-646) awarded to Global Production Networks Centre (GPN@NUS). Elias Koutsoupias acknowledges ERC Advanced Grant 321171 (ALGAME). Barnabé Monnot acknowledges the SUTD Presidential Graduate Fellowship. Christos Papadimitriou acknowledges NSF grant 1408635 "Algorithmic Explorations of Networks, Markets, Evolution, and the Brain". Georgios Piliouras acknowledges SUTD grant SRG ESD 2015 097, MOE AcRF Tier 2 Grant 2016-T2-1-170, NRF grant NRF2016NCR-NCR002-028 and a NRF fellowship. Barnabé Monnot and Georgios Piliouras would like to thank the other members of the National Science Experiment team at SUTD: Garvit Bansal, Francisco Benita, Sarah Nadiawati, Hugh Tay Keng Liang, Nils Ole Tippenhauer, Bige Tunçer, Darshan Virupashka, Erik Wilhelm and Yuren Zhou. The National Science Experiment is supported by the Singapore National Research Foundation (NRF), Grant RGNRF1402.

Cite AsGet BibTex

Kurtuluş Gemici, Elias Koutsoupias, Barnabé Monnot, Christos H. Papadimitriou, and Georgios Piliouras. Wealth Inequality and the Price of Anarchy. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.STACS.2019.31

Abstract

The price of anarchy quantifies the degradation of social welfare in games due to the lack of a centralized authority that can enforce the optimal outcome. It is known that, in certain games, such effects can be ameliorated via tolls or taxes. This leads to a natural, but largely unexplored, question: what is the effect of such transfers on social inequality? We study this question in nonatomic congestion games, arguably one of the most thoroughly studied settings from the perspective of the price of anarchy. We introduce a new model that incorporates the income distribution of the population and captures the income elasticity of travel time (i.e., how does loss of time translate to lost income). This allows us to argue about the equality of wealth distribution both before and after employing a mechanism. We establish that, under reasonable assumptions, tolls always increase inequality in symmetric congestion games under any reasonable metric of inequality such as the Gini index. We introduce the inequity index, a novel measure for quantifying the magnitude of these forces towards a more unbalanced wealth distribution and show it has good normative properties (robustness to scaling of income, no-regret learning). We analyze inequity both in theoretical settings (Pigou’s network under various wealth distributions) as well as experimental ones (based on a large scale field experiment in Singapore). Finally, we provide an algorithm for computing optimal tolls for any point of the trade-off of relative importance of efficiency and equality. We conclude with a discussion of our findings in the context of theories of justice as developed in contemporary social sciences and present several directions for future research.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
Keywords
  • congestion games
  • inequality

Metrics

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

References

  1. Tilak Abeysinghe and Keen Meng Choy. The Aggregate Consumption Puzzle in Singapore. Journal of Asian Economics, 15(3):563-578, June 2004. URL: http://dx.doi.org/10.1016/j.asieco.2004.05.007.
  2. Pedro AL Abrantes and Mark R Wardman. Meta-analysis of UK values of travel time: An update. Transportation Research Part A: Policy and Practice, 45(1):1-17, 2011. Google Scholar
  3. Anthony B Atkinson et al. On the measurement of inequality. Journal of economic theory, 2(3):244-263, 1970. Google Scholar
  4. Jens Beckert. Beyond the Market: The Social Foundations of Economic Efficiency. Princeton University Press, Princeton, NJ, 2002. Google Scholar
  5. Umang Bhaskar, Katrina Ligett, Leonard J Schulman, and Chaitanya Swamy. Achieving target equilibria in network routing games without knowing the latency functions. Games and Economic Behavior, 2018. Google Scholar
  6. Vittorio Bilò and Cosimo Vinci. Dynamic taxes for polynomial congestion games. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 839-856. ACM, 2016. Google Scholar
  7. Avrim Blum, Eyal Even-Dar, and Katrina Ligett. Routing without regret: On convergence to Nash equilibria of regret-minimizing algorithms in routing games. In Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 45-52. ACM, 2006. Google Scholar
  8. Maria Börjesson, Mogens Fosgerau, and Staffan Algers. On the income elasticity of the value of travel time. Transportation Research Part A: Policy and Practice, 46(2):368-377, 2012. Google Scholar
  9. Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, Maria Kyropoulou, and Evi Papaioannou. The Impact of Altruism on the Efficiency of Atomic Congestion Games. In Martin Wirsing, Martin Hofmann, and Axel Rauschmayer, editors, Trustworthly Global Computing, pages 172-188, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  10. Po-An Chen, Bart De Keijzer, David Kempe, and Guido Schäfer. The robust price of anarchy of altruistic games. In International Workshop on Internet and Network Economics, pages 383-390. Springer, 2011. Google Scholar
  11. Zhou Chen, Qi Qi, and Changjun Wang. Balancing Efficiency and Equality in Vehicle Licenses Allocation. In International Conference on Web and Internet Economics. Springer, 2017. Google Scholar
  12. Zhou Chen, Qi Qi, Changjun Wang, and Wenwei Wang. Mechanism Design with Efficiency and Equality Considerations. In International Conference on Web and Internet Economics, pages 120-132. Springer, 2017. Google Scholar
  13. George Christodoulou and Elias Koutsoupias. The price of anarchy of finite congestion games. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 67-73. ACM, 2005. Google Scholar
  14. Beng-Huat Chua. Communitarian Ideology and Democracy in Singapore. Routledge, London, 1995. Google Scholar
  15. Richard Cole, Yevgeniy Dodis, and Tim Roughgarden. Pricing network edges for heterogeneous selfish users. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 521-530. ACM, 2003. Google Scholar
  16. José R Correa, Andreas S Schulz, and Nicolás E Stier-Moses. Selfish routing in capacitated networks. Mathematics of Operations Research, 29(4):961-976, 2004. Google Scholar
  17. Robert H. Edelstein and Sau Kim Lum. House Prices, Wealth Effects, and the Singapore Macroeconomy. Journal of Housing Economics, 13(4):342-367, December 2004. URL: http://dx.doi.org/10.1016/j.jhe.2004.09.006.
  18. Lisa Fleischer, Kamal Jain, and Mohammad Mahdian. Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, pages 277-285. IEEE, 2004. Google Scholar
  19. Dimitris Fotakis, Laurent Gourvès, and Jérôme Monnot. Selfish transportation games. In International Conference on Current Trends in Theory and Practice of Informatics, pages 176-187. Springer, 2017. Google Scholar
  20. Dimitris Fotakis, Spyros Kontogiannis, and Paul Spirakis. Selfish unsplittable flows. Theoretical Computer Science, 348(2–3):226-239, 2005. Automata, Languages and Programming: Algorithms and Complexity (ICALP-A 2004)Automata, Languages and Programming: Algorithms and Complexity 2004. URL: http://dx.doi.org/10.1016/j.tcs.2005.09.024.
  21. Kurtuluş Gemici. The Neoclassical Origins of Polanyi’s Self-Regulating Market. Sociological Theory, 33(2):125-147, June 2015. URL: http://dx.doi.org/10.1177/0735275115587389.
  22. Kurtuluş Gemici, Elias Koutsoupias, Barnabé Monnot, Christos Papadimitriou, and Georgios Piliouras. Wealth inequality and the price of anarchy. URL: http://arxiv.org/abs/1802.09269.
  23. Corrado Gini. Measurement of inequality of incomes. The Economic Journal, 31(121):124-126, 1921. Google Scholar
  24. Sun Sheng Han. Polycentric Urban Development and Spatial Clustering of Condominium Property Values: Singapore in the 1990s. Environment and Planning A: Economy and Space, 37(3):463-481, March 2005. URL: http://dx.doi.org/10.1068/a3746.
  25. Tobias Harks, Ingo Kleinert, Max Klimm, and Rolf H Möhring. Computing network tolls with support constraints. Networks, 65(3):262-285, 2015. Google Scholar
  26. W. Gregg Huff. The Developmental State, Government, and Singapore’s Economic Development Since 1960. World Development, 23(8):1421-1438, 1995. Google Scholar
  27. Christopher Jencks. Does Inequality Matter? Daedalus, 131(1):49-65, 2002. Google Scholar
  28. Elias Koutsoupias and Christos H. Papadimitriou. Worst-case Equilibria. In STACS, pages 404-413, 1999. Google Scholar
  29. Barnabé Monnot, Francisco Benita, and Georgios Piliouras. Routing Games in the Wild: Efficiency, Equilibration and Regret. In International Conference on Web and Internet Economics, pages 340-353. Springer, 2017. Google Scholar
  30. Barnabé Monnot, Erik Wilhelm, Georgios Piliouras, Yuren Zhou, Daniel Dahlmeier, Hai Yun Lu, and Wang Jin. Inferring Activities and Optimal Trips: Lessons From Singapore’s National Science Experiment. In Michael-Alexandre Cardin, Saik Hay Fong, Pao Chuen Lui, and Yang How Tan, editors, Complex Systems Design &Management Asia, pages 247-264. Springer, 2016. Google Scholar
  31. Arthur Cecil Pigou. The economics of welfare. Palgrave Macmillan, 1920. Google Scholar
  32. Thomas Piketty. Capital in the 21st Century. Harvard University Press Cambridge, MA, 2014. Google Scholar
  33. Karl Polanyi. The Great Transformation: The Political and Economic Origins of Our Time. Beacon Press, Boston, MA, 1957. Google Scholar
  34. John Rawls. A Theory of Justice. Belknap Press, Cambridge, MA, rev. edition, 1999. Google Scholar
  35. John Rawls. Justice as Fairness: A Restatement. Harvard University Press, Cambridge, MA, 2001. Google Scholar
  36. Sean F. Reardon and Kendra Bischoff. Income Inequality and Income Segregation. American Journal of Sociology, 116(4):1092-1153, January 2011. URL: http://dx.doi.org/10.1086/657114.
  37. Tim Roughgarden. Intrinsic robustness of the price of anarchy. In Proc. of STOC, pages 513-522, 2009. Google Scholar
  38. Tim Roughgarden and Éva Tardos. How bad is selfish routing? Journal of the ACM (JACM), 49(2):236-259, 2002. Google Scholar
  39. Joseph E Stiglitz. The price of inequality: How today’s divided society endangers our future. WW Norton &Company, 2012. Google Scholar
  40. H Theil. Economics and information theory. North-Holland, Amsterdam, 1967. OCLC: 710718565. Google Scholar
  41. Carl A. Trocki. Singapore: Wealth, Power and the Culture of Control. Psychology Press, 2006. Google Scholar
  42. Erik Wilhelm, Don MacKenzie, Yuren Zhou, Lynette Cheah, and Nils Ole Tippenhauer. Evaluation of Transport Mode Using Wearable Sensor Data from Thousands of Students. In Proceedings of the Transportation Research Board 96th Annual Meeting, pages 1-18. Transportation Research Board, 2017. Google Scholar
  43. Erik Wilhelm, Yuren Zhou, Nan Zhang, Jacksheng Kee, George Loh, and Nils Tippenhauer. Sensg: Large-scale deployment of wearable sensors for trip and transport mode logging. In Transportation Research Board 95th Annual Meeting, 2016. 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