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

Abstract

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
Pages18-29
Number of pages12
EditionM4D
DOIs
StatePublished - Dec 6 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)
NumberM4D
Volume6386 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd International Symposium on Algorithmic Game Theory, SAGT 2010
Country/TerritoryGreece
CityAthens
Period10/18/1010/20/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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

Cite this