Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Orlin, James B. License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-26720

Improved Algorithms for Computing Fisher's Market Clearing Prices



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

  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 =		{},
  annote =	{Keywords: Market equilibrium, Fisher, strongly polynomial}

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

DROPS-Home | Fulltext Search | Imprint Published by LZI