License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.10171.2
URN: urn:nbn:de:0030-drops-26720
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2672/
|
Go to the corresponding Portal |
Orlin, James B.
Improved Algorithms for Computing Fisher's Market Clearing Prices
Abstract
We give the first strongly polynomial time algorithm for computing
an equilibrium for the linear utilities case of Fisher's market model.
We consider a problem with a set $B$ of buyers and a set $G$ of divisible goods.
Each buyer $i$ starts with an initial integral allocation
$e_i$ of money. The integral utility for buyer $i$ of
good $j$ is $U_{ij}$. We first develop a weakly polynomial
time algorithm that runs in $O(n^4 log U_{max} + n^3 e_{max})$ time, where
$n = |B| + |G|$. We further modify the algorithm so that it runs
in $O(n^4 log n)$ time. These algorithms improve upon the
previous best running time of
$O(n^8 log U_{max} + n^7 log e_{max})$, due to Devanur et al.
BibTeX - Entry
@InProceedings{orlin:DagSemProc.10171.2,
author = {Orlin, James B.},
title = {{Improved Algorithms for Computing Fisher's Market Clearing Prices}},
booktitle = {Equilibrium Computation},
pages = {1--19},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2010},
volume = {10171},
editor = {Edith Elkind and Nimrod Megiddo and Peter Bro Miltersen and Vijay V. Vazirani and Bernahrd von Stengel},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2010/2672},
URN = {urn:nbn:de:0030-drops-26720},
doi = {10.4230/DagSemProc.10171.2},
annote = {Keywords: Market equilibrium, Fisher, strongly polynomial}
}
|
Keywords: |
|
Market equilibrium, Fisher, strongly polynomial |
|
Collection: |
|
10171 - Equilibrium Computation |
|
Issue Date: |
|
2010 |
|
Date of publication: |
|
15.07.2010 |
