Combinatorial Algorithms for General Linear Arrow-Debreu Markets

Authors Bhaskar Ray Chaudhury, Kurt Mehlhorn



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2018.26.pdf
  • Filesize: 0.48 MB
  • 16 pages

Document Identifiers

Author Details

Bhaskar Ray Chaudhury
  • MPI for Informatics, Saarland Informatics Campus, Graduate School of Computer Science Saarbrücken, Germany
Kurt Mehlhorn
  • MPI for Informatics, Saarland Informatics Campus, Saarbrücken, Germany

Cite AsGet BibTex

Bhaskar Ray Chaudhury and Kurt Mehlhorn. Combinatorial Algorithms for General Linear Arrow-Debreu Markets. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FSTTCS.2018.26

Abstract

We present a combinatorial algorithm for determining the market clearing prices of a general linear Arrow-Debreu market, where every agent can own multiple goods. The existing combinatorial algorithms for linear Arrow-Debreu markets consider the case where each agent can own all of one good only. We present an O~((n+m)^7 log^3(UW)) algorithm where n, m, U and W refer to the number of agents, the number of goods, the maximal integral utility and the maximum quantity of any good in the market respectively. The algorithm refines the iterative algorithm of Duan, Garg and Mehlhorn using several new ideas. We also identify the hard instances for existing combinatorial algorithms for linear Arrow-Debreu markets. In particular we find instances where the ratio of the maximum to the minimum equilibrium price of a good is U^{Omega(n)} and the number of iterations required by the existing iterative combinatorial algorithms of Duan, and Mehlhorn and Duan, Garg, and Mehlhorn are high. Our instances also separate the two algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Mathematical optimization
Keywords
  • Linear Exchange Markets
  • Equilibrium
  • Combinatorial Algorithms

Metrics

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

References

  1. Kenneth J. Arrow and Gérard Debreu. Existence of an equilibrium for a competitive economy. Econometrica, 22:265-290, 1954. URL: http://www.jstor.org/stable/1907353.
  2. B. R. Chaudhury and K. Mehlhorn. Combinatorial Algorithms for General Linear Arrow-Debreu Markets. ArXiv e-prints, October 2018. URL: http://arxiv.org/abs/1810.01237.
  3. Bruno Codenotti, Benton McCune, and Kasturi R. Varadarajan. Market equilibrium via the excess demand function. In STOC, pages 74-83. ACM, 2005. Google Scholar
  4. Omar Darwish. Market Equilibrium Computation for the Linear Arrow-Debreu Model. Master’s thesis, Fachbereich Informatik, Saarland University, 2016. Google Scholar
  5. Omar Darwish and Kurt Mehlhorn. Improved Balanced Flow Computation Using Parametric Flow. . Information Processing Letters, pages 560-563, 2016. URL: http://arxiv.org/abs/1512.05974.
  6. Omar Darwish and Kurt Mehlhorn. Linear Arrow-Debreu Markets: The General Case. Unpublished, 2016. Google Scholar
  7. Nikhil R. Devanur, Jugal Garg, and László A. Végh. A Rational Convex Program for Linear Arrow-Debreu Markets. arXiv:1307.803, 2013. Google Scholar
  8. Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, and Vijay V. Vazirani. Market equilibrium via a primal-dual algorithm for a convex program. J. ACM, 55(5):22:1-22:18, November 2008. URL: http://dx.doi.org/10.1145/1411509.1411512.
  9. Nikhil R. Devanur and Vijay V. Vazirani. An improved approximation scheme for computing Arrow-Debreu prices for the linear case. In FSTTCS, pages 149-155, 2003. Google Scholar
  10. Ran Duan, Jugal Garg, and Kurt Mehlhorn. An improved combinatorial algorithm for linear Arrow-Debreu markets. . In SODA, pages 90-106, 2016. URL: http://arxiv.org/abs/1510.02694.
  11. Ran Duan and Kurt Mehlhorn. A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market. . Information and Computation, 243:112-132, 2015. a preliminary version appeared in ICALP 2013, LNCS 7965, pages 425-436. URL: http://arxiv.org/abs/1212.0979.
  12. B. Curtis Eaves. A Finite Algorithm for the Linear Exchange Model. Journal of Mathematical Economics, 3:197-203, 1976. Google Scholar
  13. Jugal Garg, Ruta Mehta, Milind Sohoni, and Vijay V. Vazirani. A Complementary Pivot Algorithm for Markets Under Separable, Piecewise-linear Concave Utilities. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC '12, pages 1003-1016, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2213977.2214068.
  14. Rahul Garg and Sanjiv Kapoor. Auction Algorithms for Market Equilibrium. In Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, STOC '04, pages 511-518, New York, NY, USA, 2004. ACM. URL: http://dx.doi.org/10.1145/1007352.1007430.
  15. Kamal Jain. A Polynomial Time Algorithm for Computing an Arrow-Debreu Market Equilibrium for Linear Utilities. SIAM J. Comput., 37(1):303-318, April 2007. URL: http://dx.doi.org/10.1137/S0097539705447384.
  16. Kamal Jain, Mohammad Mahdian, and Amin Saberi. Approximating Market Equilibria, 2003. Google Scholar
  17. E. I. Nenakov and M. E. Primak. One algorithm for finding solutions of the Arrow-Debreu model. Kibernetica, 3:127-128, 1983. Google Scholar
  18. A. Wald. Über einige Gleichungssysteme der mathematischen Ökonomie. Zeitschrift für Nationalökonomie, 7:637-670, 1936. Translated: Econometrica, Vol. 19(4), p.368-403, 1951. Google Scholar
  19. Léon Walras. Elements of Pure Economics, or the theory of social wealth. Porcupine Press, 1874. Google Scholar
  20. Yinyu Ye. A path to the Arrow-Debreu competitive market equilibrium. Math. Program., 111(1):315-348, June 2007. URL: http://dx.doi.org/10.1007/s10107-006-0065-5.
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