Article

Proportional response dynamics leads to market equilibrium

Authors:

Li ZhangAuthors Info & Claims

STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

Pages 354 - 363

https://doi.org/10.1145/1250790.1250844

Published: 11 June 2007 Publication History

Abstract

One of the main reasons of the recent success of peer to peer (P2P)file sharing systems such as BitTorrent is their built-in tit-for-tat mechanism. In this paper, we model the bandwidth allocation in a P2P system as an exchange economy and study a tit-for-tat dynamics, namely the proportional response dynamics, in this economy. In aproportional response dynamics each player distributes its good to its neighbors proportional to the utility it received from them in thelast period. We show that this dynamics not only converges but converges to a market equilibrium, a standard economic characterization of efficient exchanges in a competitive market. In addition, for some classes of utility functions we consider, it converges much faster than the classical tat process and any existingalgorithms for computing market equilibria.

As a part of our proof we study the double normalization of a matrix, an operation that linearly scales the rows of a matrix sothat each row sums to a prescribed positive number, followed by a similar scaling of the columns. We show that the iterative double normalization process of any non-negative matrix always converges. This complements the previous studies in matrix scaling that has focused on the convergence condition of the process when the row and column normalizations are considered as separate steps.

References

[1]

K. Arrow, H.D. Block, and L. Hurwicz. On the stability of the competitive equilibrium, II. Econometrica, 27(4):82--109, 1959.

[2]

K. Arrow and G. Debreu. Existence of a competitive equilibrium for a competitive economy. Econometrica, 22(3):265--290, 1954.

[3]

K. Arrow and L. Hurwicz. On the stability of the competitive equilibrium, I. Econometrica, 26(4):522--552, 1958.

[4]

K.J. Arrow and L. Hurwicz. Competitive stability and weak gross substitutability: the Euclidean distance approach. International Economic Review, 1(1):38--49, 1960.

[5]

R.A. Brualdi, S.V. Parter, and H. Schneider. The diagonal equivalence of a nonnegative matrix to a stochastic matrix. Journal of Mathematical Analysis and Applications, 16:31--50, 1966.

[6]

B. Codenotti, B. McCune, S.V. Pemmaraju, and K.R. Varadarajan. Market equilibrium for CES exchange economies: existence, multiplicity, and computation. In FSTTCS, pages 505--516, 2005.

Digital Library

[7]

B. Codenotti, B. McCune, and K.R. Varadarajan. Market equilibrium via the excess demand function. In STOC, pages 74--83, 2005.

Digital Library

[8]

B. Codenotti, S.V. Pemmaraju, and K.R. Varadarajan. On the polynomial time computation of equilibria for certain exchange economies. In SODA, pages 72--81, 2005.

Digital Library

[9]

X. Deng, C. Papadimitriou, and S. Safra. On the complexity of equilibria. In STOC, pages 67--71, 2002.

Digital Library

[10]

N. Devanur, C. Papadimitriou, A. Saberi, and V. Vazirani. Market equilibrium via a primal-dual-type algorithm. In FOCS, pages 389--395, 2002.

Digital Library

[11]

B.C. Eaves. A finite algorithm for the linear exchange model. Journal of Mathematical Economics, 3:197--203, 1976.

[12]

M. Feldman, K. Lai, and L. Zhang. A price-anticipating resource allocation mechanism for distributed shared clusters. In Proceedings of ACM Conference on Electronic Commerce, 2005.

Digital Library

[13]

D. Gale. The linear exchange model. Journal of Mathematical Economics, 3:205--209, 1976.

[14]

K. Jain. A polynomial time algorithm for computing the Arrow-Debreu market equilibrium for linear utilities. In FOCS, pages 286--294, 2004.

Digital Library

[15]

K. Jain, M. Mahdian, and A. Saberi. Approximating market equilibria. In RANDOM-APPROX, pages 98--108, 2003.

[16]

R. Johari and J.N. Tsitsiklis. Efficiency loss in a network resource allocation game. Mathematics of Operations Research, 2004.

Digital Library

[17]

F.P. Kelly. Charging and rate control for elastic traffic. European Transactions on Telecommunications, 8:33--37, 1997.

[18]

N. Linial, A. Samorodnitsky, and A. Wigderson. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. In FOCS, pages 644--652, 1998.

Digital Library

[19]

A. Mas-Colell, M.D. Whinston, and J.R. Green. Microeconomic Theory. Oxford University Press, 1995.

[20]

H. Nikaido and H. Uzawa. Stability and non-negativity in a Walrasian Tatonnement process. International Economic Review, 1(1):50--59, 1960.

[21]

C.H. Papadimitriou. Algorithms, games, and the internet. In STOC, pages 749--753, 2001.

Digital Library

[22]

M.E. Primak. A converging algorithm for a linear exchange model. Journal of Mathematical Economics, 22:181--187, 1993.

[23]

U.G. Rothblum and H. Schneider. Scalings of matrices which have prespecified row sums and columns sums via optimization. Linear Algebra and Its Applications, 114/115:737--764, 1989.

[24]

H. Scarf. The Computation of Economic Equilibria. Yale University Press, New Haven, CT, 1973.

[25]

L. Shapley and M. Shubik. Trade using one commodity as a means of payment. Journal of Political Economy, 85:937--968, 1977.

[26]

R. Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann. Math. Statist., 35:876--879, 1964.

[27]

R. Sinkhorn. Diagonal equivalence to matrices with perscribed row and column sums. The American Mathematical Monthly, 74(4):402--405, 1967.

[28]

R. Sinkhorn and P. Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):343--348, 1967.

[29]

H. Uzawa. Walras' tatonnement in the theory of exchange. Review of Economic Studies, 27(3):182--194, 1960.

[30]

Y. Ye. A path to the Arrow-Debreu competitive market equilibrium. Mathematical Programming, to appear.

Digital Library

Cited By

Branzei SMehta RNisan N(2025)Tit-for-tat strategies drive growth and inequality in production economiesProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences10.1098/rspa.2024.0533481:2306Online publication date: 22-Jan-2025
https://doi.org/10.1098/rspa.2024.0533
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
Show More Cited By

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 ...
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 ...
Equilibrium Values in a Competitive Power Exchange Market
Special issue on finance and variational inequalities

We consider an open electricity market with demand uncertainty. In this market, the generators each decide on a bidding price to maximize profit. Units are dispatched in order of the bid from lowest to highest until demand is satisfied. The market clearing ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

June 2007

734 pages

ISBN:9781595936318

DOI:10.1145/1250790

General Chair:
David Johnson
AT&T Labs - Research
,
Program Chair:
Uriel Feige
Microsoft Research and Weizmann Institute

Copyright © 2007 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC07

Sponsor:

STOC07: Symposium on Theory of Computing

June 11 - 13, 2007

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

70
Total Citations
View Citations
781
Total Downloads

Downloads (Last 12 months)51
Downloads (Last 6 weeks)6

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Branzei SMehta RNisan N(2025)Tit-for-tat strategies drive growth and inequality in production economiesProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences10.1098/rspa.2024.0533481:2306Online publication date: 22-Jan-2025
https://doi.org/10.1098/rspa.2024.0533
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
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
Cheng YDeng XLi YYan XPennock DSegal ISeuken S(2022)Tight Incentive Analysis on Sybil Attacks to Market Equilibrium of Resource Exchange over General NetworksProceedings of the 23rd ACM Conference on Economics and Computation10.1145/3490486.3538378(792-793)Online publication date: 12-Jul-2022
https://dl.acm.org/doi/10.1145/3490486.3538378
Yan XZhu W(2022)Efficiency and Fairness in Resource ExchangeIEEE Transactions on Cloud Computing10.1109/TCC.2021.306629110:4(2538-2549)Online publication date: 1-Oct-2022
https://doi.org/10.1109/TCC.2021.3066291
Chen ZCheng YDeng XQi QYan X(2022)Tight Bound on Incnetive Ratio for Sybil Attack in Resource Sharing SystemIEEE Transactions on Cloud Computing10.1109/TCC.2020.298476010:2(913-924)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TCC.2020.2984760
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten