ECCC-Report TR06-029https://eccc.weizmann.ac.il/report/2006/029Comments and Revisions published for TR06-029en-usSat, 04 Mar 2006 16:53:23 +0200
Paper TR06-029
| Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity |
Diptarka Chakraborty,
Nikhil R. Devanur,
Vijay V. Vazirani
https://eccc.weizmann.ac.il/report/2006/029We study the structure of EG[2], the class of Eisenberg-Gale markets
with two agents. We prove that all markets in this class are rational and they
admit strongly polynomial algorithms whenever
the polytope containing the set of feasible utilities of the two agents can be described
via a combinatorial LP. This helps resolve positively the status of two markets left as
open problems by [JV]: the capacity allocation market in a directed graph with two
source-sink pairs and the network coding market in a directed network with two sources.
Our algorithms for solving the corresponding nonlinear convex programs are fundamentally
different from those obtained by [JV]; whereas they use the primal-dual schema,
we use a carefully constructed binary search.
We also settle a third open problem of [JV], that of determining whether the
notion of competition monotonicity characterizes the class of SUA markets within UUA markets.
We give a positive resolution of this problem as well.
Sat, 04 Mar 2006 16:53:23 +0200https://eccc.weizmann.ac.il/report/2006/029