Top

previous chapter Weighted Boolean Formula Games

next chapter On Radiocoloring Hierarchically Specified Plana...

Hint

Swipe to navigate through the chapters of this book

2015 | OriginalPaper | Chapter

On the Implementation of Combinatorial Algorithms for the Linear Exchange Market

Read first chapter

Author: Kurt Mehlhorn

Publisher: Springer International Publishing

Published in: Algorithms, Probability, Networks, and Games

» Get access to the full-text

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.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

inform now

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

Book

Algorithms, Probability, Networks, and Games

Print ISBN: 978-3-319-24023-7

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

https://doi.org/10.1007/978-3-319-24024-4

DOI

https://doi.org/10.1007/978-3-319-24024-4_7

Author:

Kurt Mehlhorn

Publisher

Springer International Publishing

Sequence number

Premium Partner

Image Credits