Top

Published in:

2015 | OriginalPaper | Chapter

On the Implementation of Combinatorial Algorithms for the Linear Exchange Market

Author : Kurt Mehlhorn

Published in: Algorithms, Probability, Networks, and Games

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Duan and Mehlhorn and Duan, Garg, and Mehlhorn presented polynomial time combinatorial algorithms [DM13, DGM15] for the computation of equilibrium prices in linear exchange markets. I am currently implementing these algorithms. I discuss the questions that I hope to answer through the implementation.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Weighted Boolean Formula Games

next chapter On Radiocoloring Hierarchically Specified Planar Graphs: -completeness and Approximations

Clearly \(b_1 \ge |r(B)|/n\). Also, \({r(b_j)}/{r(b_{j+1})}\le 1+1/n\) for \(j<\ell \), and hence \(r(b_\ell )\ge r(b_1)/(1+1/n)^{-n} \ge r(b_1)/e \ge |r(B)|/(e \cdot n)\).

[DGM15]

Duan, R., Garg, J., Mehlhorn, K.: A improved combinatorial algorithm for the linear arrow-debreu marketTODO (2015). Forthcoming

[DM13]

Duan, R., Mehlhorn, K.: A combinatorial polynomial algorithm for the linear arrow-debreu market. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 425–436. Springer, Heidelberg (2013) CrossRef

[DPSV08]

Devanur, N.R., Papadimitriou, C.H., Saberi, A., Vazirani, V.V.: Market equilibrium via a primal-dual algorithm for a convex program. J. ACM 55(5), 22:1–22:18 (2008)MathSciNetCrossRefMATH

[Edm67]

Edmonds, J.: Systems of distinct representatives and linear algebra. J. Res. Nat. Bur. Stan.(B) 71, 241–245 (1967)MathSciNetCrossRefMATH

[GGT89]

Gallo, G., Grigoriadis, M.D., Tarjan, R.E.: A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18, 30–55 (1989)MathSciNetCrossRefMATH

[Jai07]

Jain, K.: A polynomial time algorithm for computing an Arrow-Debreu market equilibrium for linear utilities. SIAM J. Comput. 37(1), 303–318 (2007)MathSciNetCrossRefMATH

[Wal74]

Walras, L.: Elements of Pure Economics, or the Theory of Social Wealth (1874)

[Ye07]

Ye, Y.: A path to the Arrow-Debreu competitive market equilibrium. Math. Program. 111(1), 315–348 (2007)MathSciNetCrossRefMATH

Title: On the Implementation of Combinatorial Algorithms for the Linear Exchange Market
Author: Kurt Mehlhorn
Publisher: Springer International Publishing
Book: Algorithms, Probability, Networks, and Games
Print ISBN: 978-3-319-24023-7

Electronic ISBN: 978-3-319-24024-4

Copyright Year: 2015
DOI: https://doi.org/10.1007/978-3-319-24024-4_7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner