We present a new flow-type convex program describing equilibrium solutions to linear Arrow-Debreu markets. Whereas convex formulations were previously known ([Nenakov and Primak 1983; Jain 2007; Cornet 1989] ), our program exhibits several new features. It provides a simple necessary and sufficient condition and a concise proof of the existence and rationality of equilibria, settling an open question raised by Vazirani [2012]. As a consequence, we also obtain a simple new proof of the result in Mertens [2003] that the equilibrium prices form a convex polyhedral set. special case, the linear Fisher model, that was formulated by Fisher in 1891, who also studied the computability of equilibrium via a hydraulic machine no less! (See Brainard and Scarf [2000] for a fascinating account.) In this model, the agents are separated into two types, buyers and sellers; buyers arrive to the market with a certain amount of money that they wish to spend on goods offered by the sellers. This model turned out to be substantially easier from a computational perspective than the linear Arrow-Debreu model. A convex programming formulation was given by Eisenberg and Gale [1959]. The problem of equilibrium computation was introduced to the theoretical computer science community by Devanur et al. [2008], who presented a polynomial time combinatorial primal-dual algorithm. This initiated an intensive line of research, most notable among which is a strongly polynomial time algorithm by Orlin [2010]; for a survey, see Nisan et al. [2007, Chapter 5] or Vazirani [2012]. Also, Shmyrev [2009] presented a new type of convex program (which was discovered independently by Birnbaum et al. [2011] ) capturing the equilibria. Let us now turn to the linear Arrow-Debreu model. The first important algorithmic result was a finite Lemke-type path-following algorithm for finding an equilibrium solution by Eaves [1976]. A remarkable consequence of this algorithm is that, when the utilities are given by rational numbers, there also exists an equilibrium among rational numbers. The history of convex programming formulations for the linear Arrow-Debreu model is somewhat convoluted. Jain [2007] formulated a convex program whose solutions correspond to market equilibria; this can be used to obtain a polynomial-time algorithm via the Ellipsoid algorithm. It turned out later that the same convex program was already formulated by Nenakov and Primak [1983]. Interestingly, the computer science community so far seems to have been unaware of the paper by Cornet [1989] presenting a similar, yet better, convex program. This is not mentioned even in the survey paper by Codenotti et al. [2004] exploring the background of the problem. (These convex programs will be covered in Section 3.) An unsatisfactory aspect of the program in Jain [2007] and Nenakov and Primak [1983] is that it fails to show the existence of an equilibrium; it only shows that if there exists an equilibrium, then any feasible solution to the convex program is one. In contrast, Cornet's program provides a proof of existence assuming that a stronger sufficient condition in Gale [1957] holds. However, it fails to show it for the weaker necessary and sufficient condition in Gale [1976]. An efficient interior point algorithm to compute an equilibrium was given by Ye [2008] based on the convex program in Jain [2007] and Nenakov and Primak [1983] . An important recent result is a combinatorial primal-dual algorithm by Duan and Mehlhorn [2015]; this does not rely on the convex programming formulation, but rather adapts techniques from the algorithm by Devanur et al. [2008] for linear Fisher markets. The convex programs of Nenakov and Primak [1983], Jain [2007], and Cornet [1989] for the linear Arrow-Debreu model are of a substantially different nature from those of Eisenberg and Gale [1959 ], Shmyrev [2009 ], and Birnbaum et al. [2011 for the linear Fisher model. The latter ones have linear constraints only, with separable convex objectives, in contrast to the nonlinear constraints in Nenakov and Primak [1983] and Jain [2007]. Whereas Cornet [1989] is formulated with only very simple linear constraints, the max-min type objective, in fact, hides similar nonlinear constraints. The feasible region for both formulations for the linear Fisher model are classical polyhedra, Eisenberg and Gale [1959] a generalized flow polyhedron, and Shmyrev [2009] and Birnbaum et al. [2011] a circulation polyhedron. This also explains why for the linear Fisher model, classical flow techniques are applicable (see Végh [2013, 2012]) and strongly polynomial time algorithms exist. Also, interestingly, the convex programs of Eisenberg and Gale [1959], Shmyrev [2009], and Birnbaum et al. [2011]
Devanur et al. REF formulated a rational convex program for the linear Arrow-Debreu model to characterize a market equilibrium.
A Rational Convex Program for Linear Arrow-Debreu Markets
TEAC
Mathematics Economics Computer Science