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
Go to the corresponding Portal

Orlin, James B.

Improved Algorithms for Computing Fisher's Market Clearing Prices

10171.OrlinJames.Paper.2672.pdf (0.2 MB)


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 =	{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 =		{},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI