Dynamics of Distributed Updating in Fisher Markets

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.

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.
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.
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.
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.
9. Xi Chen, Dimitris Paparas, and Mihalis Yannakakis. 2017. The Complexity of Non-Monotone Markets. J. ACM 64, 3 (2017), 20:1--20:56.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
23. E. Eisenberg. 1961. Aggregation of Utility Functions. Management Sciences 7 (1961), 337--350.
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.
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.
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.
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.
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.
37. Yurii Nesterov. 2005. Excessive Gap Technique in Nonsmooth Convex Minimization. SIAM Journal on Optimization 16, 1 (2005), 235--249.
38. Yurii Nesterov. 2005. Smooth minimization of non-smooth functions. Math. Program. 103, 1 (2005), 127--152.
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.
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.
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.
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.
50. Li Zhang. 2011. Proportional response dynamics in the Fisher market. Theor. Comput. Sci. 412, 24 (2011), 2691--2698.

Index Terms

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design

      • Market equilibria