User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse





Market Equilibrium Computation for the Linear Arrow-Debreu Model


Darwish,  Omar
International Max Planck Research School, MPI for Informatics, Max Planck Society;
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Darwish, O. (2016). Market Equilibrium Computation for the Linear Arrow-Debreu Model. Master Thesis, Universität des Saarlandes, Saarbrücken.

Cite as: http://hdl.handle.net/11858/00-001M-0000-002C-41D0-C
The problem of market equilibrium is defined as the problem of finding prices for the goods such that the supply in the market is equal to the demand. The problem is applicable to several market models, like the linear Arrow-Debreu model, which is one of the fundamental economic market models. Over the years, various algorithms have been developed to compute the market equilibrium of the linear Arrow-Debreu model. In 2013, Duan and Mehlhorn presented the first combinatorial polynomial time algorithm for computing the market equilibrium of this model. In this thesis, we optimize, generalize, and implement the Duan-Mehlhorn algorithm. We present a novel algorithm for computing balanced ows in equality networks, which is an application of parametric ows. This algorithm outperforms the current best algorithm for computing balanced ows; hence, it improves Duan-Mehlhorn's algorithm by almost a factor of n, which is the size of the network. Moreover, we generalize Duan-Mehlhorn's algorithm by relaxing some of its assumptions. Finally, we describe our approach for implementing Duan-Mehlhorn's algorithm. The preliminary results of our implementation - based on random utility instances - show that the running time of the implementation scales significantly better than the theoretical time complexity.