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 Creators ORCiD Ch, Sobhan Babu UNSPECIFIED
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:	Users 3 not found.
Date Deposited:	13 Oct 2014 07:09
Last Modified:	17 Mar 2015 10:21
URI:	http://raiithold.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:	Google Scholar

Actions (login required)

View Item

Statistics for this ePrint Item