Eisenberg-Gale markets: Algorithms and game-theoretic properties

We define a new class of markets, the Eisenberg-Gale markets. This class contains Fisher's linear market, markets from the resource allocation framework of Kelly [Kelly, F.P., 1997. Charging and rate control for elastic traffic. Europ. Transactions Telecommunications 8, 33-37], as well as numerous interesting new markets. We obtain combinatorial, strongly polynomial algorithms for several markets in this class. Our algorithms have a simple description as ascending price auctions. Our algorithms lead to insights into game-theoretic properties of these markets, such as efficiency, fairness, and competition monotonicity. They also help determine if these markets always have rational equilibria. A classification of Eisenberg-Gale markets w.r.t. these properties reveals a surprisingly rich set of possibilities.