Improved algorithms for computing fisher's market clearing prices

James B. Orlin

87 citations0/0 files storedACM Symposium on Theory of Computing (STOC)

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Game Theory and Voting Systems Complexity and Algorithms in Graphs Economic theories and models

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 ei of money. The integral utility for buyer i of good j is Uij. We first develop a weakly polynomial time algorithm that runs in O(n4 log Umax + n3 emax) time, where n = |B| + |G|. We further modify the algorithm so that it runs in O(n4 log n) time. These algorithms improve upon the previous best running time of O(n8 log Umax + n7 log emax), due to Devanur et al.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 87 citations exist upstream.

References

1954Existence of an Equilibrium for a Competitive Economy 2008Existence of an equilibrium for a competitive economy 1959Consensus of Subjective Probabilities: The Pari-Mutuel Method 2005How to Compute Equilibrium Prices in 1891

Cited by

2015Approximating the Nash Social Welfare with Indivisible Items 2014Network Cournot Competition

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.