License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-26720
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2672/

Orlin, James B.

Improved Algorithms for Computing Fisher's Market Clearing Prices

pdf-format:
Dokument 1.pdf (246 KB)


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:DSP:2010:2672,
  author =	{James B. Orlin},
  title =	{Improved Algorithms for Computing Fisher's Market Clearing Prices},
  booktitle =	{Equilibrium Computation},
  year =	{2010},
  editor =	{Edith Elkind and Nimrod Megiddo and Peter Bro Miltersen and Vijay V. Vazirani and Bernahrd von Stengel},
  number =	{10171},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2672},
  annote =	{Keywords: Market equilibrium, Fisher, strongly polynomial}
}

Keywords: Market equilibrium, Fisher, strongly polynomial
Seminar: 10171 - Equilibrium Computation
Issue date: 2010
Date of publication: 15.07.2010


DROPS-Home | Fulltext Search | Imprint Published by LZI