English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Market Equilibrium Computation for the Linear Arrow-Debreu Model

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

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-002C-41D0-C Version Permalink: http://hdl.handle.net/11858/00-001M-0000-002C-41D6-F
Genre: Thesis

Files

show Files
hide Files
:
2016_Master's_Thesis_OmarDarwish.pdf (Any fulltext), 920KB
 
File Permalink:
-
Name:
2016_Master's_Thesis_OmarDarwish.pdf
Description:
-
Visibility:
Restricted (Max Planck Institute for Informatics, MSIN; )
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Darwish, Omar1, 2, Author              
Mehlhorn, Kurt2, Advisor              
Hoefer, Martin2, Referee              
Affiliations:
1International Max Planck Research School, MPI for Informatics, Max Planck Society, Campus E1 4, 66123 Saarbrücken, DE, ou_1116551              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: 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.

Details

show
hide
Language(s): eng - English
 Dates: 2016-03-312016-03-31
 Publication Status: Published in print
 Pages: 73 p.
 Publishing info: Saarbrücken : Universität des Saarlandes
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: DarwishMaster2016
 Degree: Master

Event

show

Legal Case

show

Project information

show

Source

show