TY - GEN

T1 - A simplex-like algorithm for fisher markets

AU - Adsul, Bharat

AU - Babu, Ch Sobhan

AU - Garg, Jugal

AU - Mehta, Ruta

AU - Sohoni, Milind

PY - 2010/12/6

Y1 - 2010/12/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=78649595188&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78649595188&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-16170-4_3

DO - 10.1007/978-3-642-16170-4_3

M3 - Conference contribution

AN - SCOPUS:78649595188

SN - 3642161693

SN - 9783642161698

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 18

EP - 29

BT - Algorithmic Game Theory - Third International Symposium, SAGT 2010, Proceedings

T2 - 3rd International Symposium on Algorithmic Game Theory, SAGT 2010

Y2 - 18 October 2010 through 20 October 2010

ER -