An Alternating Algorithm for Finding Linear Arrow-Debreu Market Equilibrium
share
Motivated by the convergence of mirror-descent algorithms to market equilibria in linear Fisher markets, it is natural to consider designing dynamics (specifically, iterative algorithms) for agents to arrive at linear Arrow-Debreu market equilibria. Jain reduced equilibrium computation in linear Arrow-Debreu markets to that in bijective markets, where everyone is a seller of only one good and also a buyer for a bundle of goods. In this paper, we simply design algorithms to solve a rational convex program for bijective markets. Our algorithm for computing linear Arrow-Debreu market equilibrium is based on solving the rational convex program formulated by Devanur et al., repeatedly alternating between a step of gradient-descent-like updates and a follow-up step of optimization. Convergence can be achieved by a new analysis different from that for linear Fisher markets.
READ FULL TEXT