A simplex-like algorithm for fisher markets

Adsul, B and Ch, Sobhan Babu and Garg, J and Mehta, R and Sohoni, M (2010) A simplex-like algorithm for fisher markets. Lecture Notes in Computer Science, 6386 (M4D). pp. 18-29. ISSN 0302-9743

Full text not available from this repository. (Request a copy)

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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Ch, Sobhan BabuUNSPECIFIED
Item Type: Article
Uncontrolled Keywords: Convex cost function; Non-linear; Optimization formulations; Polyhedral convex set; Polytopes; Strongly polynomials
Subjects: Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Mr. Siva Shankar K
Date Deposited: 13 Oct 2014 07:09
Last Modified: 17 Mar 2015 10:21
URI: http://raiith.iith.ac.in/id/eprint/182
Publisher URL: http://dx.doi.org/10.1007/978-3-642-16170-4_3
OA policy: http://www.sherpa.ac.uk/romeo/issn/0302-9743/
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 182 Statistics for this ePrint Item