nach oben

vorheriges Kapitel Weighted Boolean Formula Games

nächstes Kapitel On Radiocoloring Hierarchically Specified Plana...

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2015 | OriginalPaper | Buchkapitel

On the Implementation of Combinatorial Algorithms for the Linear Exchange Market

Erstes Kapitel lesen

Autor: Kurt Mehlhorn

Verlag: Springer International Publishing

Erschienen in: Algorithms, Probability, Networks, and Games

» Jetzt Zugang zum Volltext erhalten

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.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Jetzt einloggen Kostenlos registrieren

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

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.

Jetzt informieren

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.

Jetzt informieren

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.

Jetzt informieren

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

Titel

On the Implementation of Combinatorial Algorithms for the Linear Exchange Market

Buch

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

Autor:

Kurt Mehlhorn

Verlag

Springer International Publishing

Sequenznummer

Premium Partner

Bildnachweise