RATIONALITY AND STRONGLY POLYNOMIAL SOLVABILITY OF EISENBERG-GALE MARKETS WITH TWO AGENTS

摘要

Inspired by the convex program of Eisenberg and Gale which captures Fisher markets with linear utilities, Jain and Vazirani [K. Jain and V. V. Vazirani, Games and Economic Behavior, 70 (2010), pp. 84-106] introduced the class of Eisenberg-Gale (EG) markets. We study the structure of EG(2) markets, the class of EG markets with two agents. We prove that all markets in this class are rational, that is, they have rational equilibrium, and they admit strongly polynomial time algorithms whenever the polytope containing the set of feasible utilities of the two agents can be described via a combinatorial linear program (LP). This helps positively resolve the status of two markets left as open problems by Jain and Vazirani: 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 Jain and Vazirani; whereas they use the primal-dual schema, our main tool is binary search powered by the strong LP-duality theorem.