research-article

Public Access

Dynamics of Distributed Updating in Fisher Markets

Authors:

Yun Kuen Cheung,

Yixin TaoAuthors Info & Claims

EC '18: Proceedings of the 2018 ACM Conference on Economics and Computation

Pages 351 - 368

https://doi.org/10.1145/3219166.3219189

Published: 11 June 2018 Publication History

Abstract

A major goal in Algorithmic Game Theory is to justify equilibrium concepts from an algorithmic and complexity perspective. One appealing approach is to identify natural distributed algorithms that converge quickly to an equilibrium. This paper established new convergence results for two generalizations of proportional response in Fisher markets with buyers having CES utility functions. The starting points are respectively a new convex and a new convex-concave formulation of such markets. The two generalizations correspond to suitable mirror descent algorithms applied to these formulations. Several of our new results are a consequence of new notions of strong Bregman convexity and of strong Bregman convex-concave functions, and associated linear rates of convergence, which may be of independent interest. Among other results, we analyze a damped generalized proportional response and show a linear rate of convergence in a Fisher market with buyers whose utility functions cover the full spectrum of CES utilities aside the extremes of linear and Leontief utilities; when these utilities are included, we obtain an empirical $O(1/T)$ rate of convergence.

Supplementary Material

MP4 File (p351.mp4)

Download
411.70 MB

References

[1]

Kenneth J. Arrow, H. D. Block, and Leonid Hurwicz. 1959. On the Stability of Competitive Equilibrium, II. Econometrica 27, 1 (1959), 82--109.

[2]

Benjamin Birnbaum, Nikhil R. Devanur, and Lin Xiao. 2011. Distributed Algorithms via Gradient Descent for Fisher Markets. In Proceedings of the 12th ACM Conference on Electronic Commerce (EC '11). ACM, 127--136.

Digital Library

[3]

Lawrence E. Blume. 1993. The Statistical Mechanics of Strategic Interaction. Games and Economic Behavior 5, 3 (1993), 387--424.

[4]

Eric Budish. 2011. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy 119, 6 (2011), 1061--1103.

[5]

Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. 2016. The Unreasonable Fairness of Maximum Nash Welfare. In Proceedings of the 2016 ACM Conference on Economics and Computation (EC '16). ACM, 305--322.

Digital Library

[6]

Gong Chen and Marc Teboulle. 1993. Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions. SIAM Journal on Optimization 3, 3 (1993), 538--543.

[7]

X. Chen, D. Dai, Y. Du, and S. H. Teng. 2009. Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. 273--282.

Digital Library

[8]

Xi Chen, Xiaotie Deng, and Shang-Hua Teng. 2009. Settling the Complexity of Computing Two player Nash Equilibria. J. ACM 56, 3, Article 14 (May 2009), 57 pages.

Digital Library

[9]

Xi Chen, Dimitris Paparas, and Mihalis Yannakakis. 2017. The Complexity of Non-Monotone Markets. J. ACM 64, 3 (2017), 20:1--20:56.

Digital Library

[10]

Xi Chen and Shang-Hua Teng. 2009. Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria. In Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16--18, 2009. Proceedings. 647--656.

Digital Library

[11]

Yun Kuen Cheung, Richard Cole, and Nikhil Devanur. 2013. Tatonnement Beyond Gross Substitutes?: Gradient Descent to the Rescue. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing (STOC '13). ACM, 191--200.

Digital Library

[12]

Yun Kuen Cheung, Richard Cole, and Ashish Rastogi. 2012. Tatonnement in Ongoing Markets of Complementary Goods. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC '12). ACM, 337--354.

Digital Library

[13]

Bruno Codenotti, Benton McCune, and Kasturi Varadarajan. 2005. Market Equilibrium via the Excess Demand Function. In Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing (STOC '05). ACM, 74--83.

Digital Library

[14]

Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, and Yinyu Ye. 2006. Leontief Economies Encode Nonzero Sum Two-player Games. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm (SODA '06). Society for Industrial and Applied Mathematics, 659--667.

Digital Library

[15]

Richard Cole, Nikhil Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V. Vazirani, and Sadra Yazdanbod. 2017. Convex Program Duality, Fisher Markets, and Nash Social Welfare. In Proceedings of the 2017 ACM Conference on Economics and Computation (EC '17). ACM, 459--460.

Digital Library

[16]

Richard Cole and Lisa Fleischer. 2008. Fast-converging Tatonnement Algorithms for One-time and Ongoing Market Problems. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (STOC '08). ACM, 315--324.

Digital Library

[17]

Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. 2009. The Complexity of Computing a Nash Equilibrium. SIAM J. Comput. 39, 1 (2009), 195--259.

Digital Library

[18]

Xiaotie Deng and Ye Du. 2008. The Computation of Approximate Competitive Equilibrium is PPAD-hard. Inf. Process. Lett. 108, 6 (Nov. 2008), 369--373.

Digital Library

[19]

Xiaotie Deng, Christos Papadimitriou, and Shmuel Safra. 2003. On the complexity of price equilibria. Journal of Computer System Sciences (JCSS) 67 (2003), 311--324.

Digital Library

[20]

Nikhil R. Devanur. 2004. The Spending Constraint Model for Market Equilibrium: Algorithmic, Existence and Uniqueness Results. In Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing (STOC '04). ACM, 519--528.

Digital Library

[21]

Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, and Vijay V. Vazirani. 2008. Market equilibrium via a primal-dual algorithm for a convex program. J. ACM 55, 5 (2008), 22:1--22:18.

Digital Library

[22]

Krishnamurthy Dvijotham, Yuval Rabani, and Leonard J. Schulman. 2017. Convergence of Incentive-driven Dynamics in Fisher Markets. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '17). Society for Industrial and Applied Mathematics, 554--567.

Digital Library

[23]

E. Eisenberg. 1961. Aggregation of Utility Functions. Management Sciences 7 (1961), 337--350.

Digital Library

[24]

E. Eisenberg and D. Gale. 1959. Consensus of subjective probabilities: the Pari-Mutuel method. The Annals of Mathematical Statistics 30 (1959), 165--168.

[25]

Rahul Garg and Sanjiv Kapoor. 2006. Auction Algorithms for Market Equilibrium. Math. Oper. Res. 31, 4 (Nov. 2006), 714--729.

Digital Library

[26]

Gauthier Gidel, Tony Jebara, and Simon Lacoste-Julien. 2017. Frank-Wolfe Algorithms for Saddle Point Problems. In The 20th International Conference on Artificial Intelligence and Statistics.

[27]

Aanund Hylland and Richard Zeckhauser. 1979. The Efficient Allocation of Individuals to Positions. Journal of Political Economy 87, 2 (April 1979), 293--314.

[28]

Kamal Jain and Vijay V. Vazirani. 2007. Eisenberg-Gale Markets: Algorithms and Structural Properties. In Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing (STOC '07). ACM, 364--373.

Digital Library

[29]

Mamoru Kaneko and Kenjiro Nakamura. 1979. The Nash social welfare function. Econometrica (1979), 423--435.

[30]

Frank Kelly. 1997. Charging and rate control for elastic traffic. European Transactions on Telecommunications 8, 1 (1997), 33--37.

[31]

Dave Levin, Katrina LaCurts, Neil Spring, and Bobby Bhattacharjee. 2008. Bittorrent is an Auction: Analyzing and Improving Bittorrent's Incentives. SIGCOMM Comput. Commun. Rev. 38, 4 (Aug. 2008), 243--254.

Digital Library

[32]

Steven H Low and David E Lapsley. 1999. Optimization flow control. I. Basic algorithm and convergence. IEEE/ACM Transactions on networking 7, 6 (1999), 861--874.

Digital Library

[33]

Jason R. Marden and Jeff S. Shamma. 2012. Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation. Games and Economic Behavior 75, 2 (2012), 788--808.

[34]

L. W. McKenzie. 2002. Classical General Equilibrium Theory. The MIT press.

[35]

J. F. Nash. 1950. The Bargaining Problem. Econometrica 18 (1950), 155--162.

[36]

Arkadi Nemirovski. 2004. Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems. SIAM Journal on Optimization 15, 1 (2004), 229--251.

Digital Library

[37]

Yurii Nesterov. 2005. Excessive Gap Technique in Nonsmooth Convex Minimization. SIAM Journal on Optimization 16, 1 (2005), 235--249.

Digital Library

[38]

Yurii Nesterov. 2005. Smooth minimization of non-smooth functions. Math. Program. 103, 1 (2005), 127--152.

Digital Library

[39]

Yurii Nesterov. 2007. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming 109, 2--3 (2007), 319--344.

[40]

Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press, New York, NY, USA.

Digital Library

[41]

Christos H. Papadimitriou and Mihalis Yannakakis. 2010. An Impossibility Theorem for Price-adjustment Mechanisms. PNAS 5, 107 (2010), 1854--1859.

[42]

Alexander Rakhlin and Karthik Sridharan. 2013. Optimization, Learning, and Games with Predictable Sequences. In Advances in Neural Information Processing Systems 26: Twenty-seventh Annual Conference on Neural Information Processing Systems 2013. 3066--3074.

Digital Library

[43]

H. Scarf. 1960. Some examples of global instatibility of the competitive equilibrium. International Economic Review 3, 13 (1960), 157--172.

[44]

Vadim I Shmyrev. 2009. An algorithm for finding equilibrium in the linear exchange model with fixed budgets. Journal of Applied and Industrial Mathematics 3, 4 (2009), 505.

[45]

Hirofumi Uzawa. 1960. Walras' Tatonnement in the Theory of Exchange. Review of Economic Studies 27, 3 (1960), 182--194.

[46]

H.R. Varian. 1974. Equity, envy, and efficiency. Journal of Economic Theory 9, 1 (1974), 63--91.

[47]

Vijay V. Vazirani and Mihalis Yannakakis. 2011. Market equilibrium under separable, piecewise-linear, concave utilities. J. ACM 58, 3 (2011), 10:1--10:25.

Digital Library

[48]

Léon Walras. 1874. Eléments d' Economie Politique Pure. Corbaz. (Translated as: Elements of Pure Economics. Homewood, IL: Irwin, 1954.).

[49]

Fang Wu and Li Zhang. 2007. Proportional Response Dynamics Leads to Market Equilibrium. In Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing (STOC '07). ACM, 354--363.

Digital Library

[50]

Li Zhang. 2011. Proportional response dynamics in the Fisher market. Theor. Comput. Sci. 412, 24 (2011), 2691--2698.

Digital Library

Cited By

Cheng YDeng XLi YYan X(2024)Tight Incentive Analysis of Sybil Attacks against the Market Equilibrium of Resource Exchange over General NetworksGames and Economic Behavior10.1016/j.geb.2024.10.009Online publication date: Nov-2024
https://doi.org/10.1016/j.geb.2024.10.009
Kolumbus YLevy MNisan NOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Asynchronous proportional response dynamicsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667226(25409-25434)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667226
Garg JHusić EVégh L(2023)An Auction Algorithm for Market Equilibrium with Weak Gross Substitute DemandsACM Transactions on Economics and Computation10.1145/3624558Online publication date: 14-Sep-2023
https://dl.acm.org/doi/10.1145/3624558
Show More Cited By

Index Terms

Dynamics of Distributed Updating in Fisher Markets
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
      1. Market equilibria

Recommendations

Proportional Dynamics in Exchange Economies
EC '21: Proceedings of the 22nd ACM Conference on Economics and Computation

We study the proportional dynamics in exchange economies, where each player starts with some amount of money and a good. Every day, players bring one unit of their good and submit bids on goods they like, each good gets allocated in proportion to the ...
Distributed algorithms via gradient descent for fisher markets
EC '11: Proceedings of the 12th ACM conference on Electronic commerce

Designing distributed algorithms that converge quickly to an equilibrium is one of the foremost research goals in algorithmic game theory, and convex programs have played a crucial role in the design of algorithms for Fisher markets. In this paper we ...
Proportional response dynamics in the Fisher market

We show that the proportional response dynamics, a utility based distributed dynamics, converges to the market equilibrium in the Fisher market with constant elasticity of substitution (CES) utility functions. By the proportional response dynamics, each ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '18: Proceedings of the 2018 ACM Conference on Economics and Computation

June 2018

713 pages

ISBN:9781450358293

DOI:10.1145/3219166

General Chair:
Eva Tardos
Cornell University, USA
,
Program Chairs:
Edith Elkind
University of Oxford, UK
,
Rakesh Vohra
University of Pennsylvania, USA

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF

Conference

EC '18

Sponsor:

SIGecom

EC '18: ACM Conference on Economics and Computation

June 18 - 22, 2018

NY, Ithaca, USA

Acceptance Rates

EC '18 Paper Acceptance Rate 70 of 269 submissions, 26%;

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
493
Total Downloads

Downloads (Last 12 months)127
Downloads (Last 6 weeks)33

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cheng YDeng XLi YYan X(2024)Tight Incentive Analysis of Sybil Attacks against the Market Equilibrium of Resource Exchange over General NetworksGames and Economic Behavior10.1016/j.geb.2024.10.009Online publication date: Nov-2024
https://doi.org/10.1016/j.geb.2024.10.009
Kolumbus YLevy MNisan NOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Asynchronous proportional response dynamicsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667226(25409-25434)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667226
Garg JHusić EVégh L(2023)An Auction Algorithm for Market Equilibrium with Weak Gross Substitute DemandsACM Transactions on Economics and Computation10.1145/3624558Online publication date: 14-Sep-2023
https://dl.acm.org/doi/10.1145/3624558
Goktas DZhao JGreenwald ALeyton-Brown KSamuelson LHartline J(2023)Tâtonnement in Homothetic Fisher MarketsProceedings of the 24th ACM Conference on Economics and Computation10.1145/3580507.3597746(760-781)Online publication date: 9-Jul-2023
https://dl.acm.org/doi/10.1145/3580507.3597746
Zhu HCheung YXie L(2023)Stability and Efficiency of Personalised Cultural MarketsProceedings of the ACM Web Conference 202310.1145/3543507.3583315(3447-3455)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583315
Cao WKottmann FMa R(2023)Towards a Bandwidth Market for the Metaverse2023 IEEE International Conference on Metaverse Computing, Networking and Applications (MetaCom)10.1109/MetaCom57706.2023.00066(345-349)Online publication date: Jun-2023
https://doi.org/10.1109/MetaCom57706.2023.00066
Cheung YLeonardos SSridhar SPiliouras G(2023)Market Equilibria and Risk Diversification in Blockchain Mining EconomiesMathematical Research for Blockchain Economy10.1007/978-3-031-18679-0_2(23-46)Online publication date: 19-Feb-2023
https://doi.org/10.1007/978-3-031-18679-0_2
Liao LGao YKroer CKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Nonstationary dual averaging and online fair allocationProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602963(37159-37172)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3602963
Zhao HDeng SLiu ZXiang ZYin JDustdar SZomaya A(2022)DPoS: Decentralized, Privacy-Preserving, and Low-Complexity Online Slicing for Multi-Tenant NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2021.307493421:12(4296-4309)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TMC.2021.3074934
Brânzei S(2021)Exchange marketsACM SIGecom Exchanges10.1145/3505156.350516119:2(37-45)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1145/3505156.3505161
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents