A simplex-like algorithm for fisher markets

Bharat Adsul, Ch Sobhan Babu, Jugal Garg, Ruta Mehta, Milind Sohoni

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We propose a new convex optimization formulation for the Fisher market problem with linear utilities. Like the Eisenberg-Gale formulation, the set of feasible points is a polyhedral convex set while the cost function is non-linear; however, unlike that, the optimum is always attained at a vertex of this polytope. The convex cost function depends only on the initial endowments of the buyers. This formulation yields an easy simplex-like pivoting algorithm which is provably strongly polynomial for many special cases.

Original languageEnglish (US)
Title of host publicationAlgorithmic Game Theory - Third International Symposium, SAGT 2010, Proceedings
Number of pages12
StatePublished - 2010
Externally publishedYes
Event3rd International Symposium on Algorithmic Game Theory, SAGT 2010 - Athens, Greece
Duration: Oct 18 2010Oct 20 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6386 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd International Symposium on Algorithmic Game Theory, SAGT 2010

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A simplex-like algorithm for fisher markets'. Together they form a unique fingerprint.

Cite this