Options
A simplex-like algorithm for linear Fisher markets
Journal
Current Science
ISSN
00113891
Date Issued
2012-11-10
Author(s)
Adsul, Bharat
Babu, Ch Sobhan
Garg, Jugal
Mehta, Ruta
Sohoni, Milind
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 nonlinear; however, 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 algorithm which is provably strongly polynomial for many special cases. The algorithm can also be interpreted as a complementary pivot algorithm resembling the classical Lemke–Howson algorithm for computing Nash equilibrium of two-person bimatrix games.
Subjects