Infinite-Dimensional Fisher Markets and Tractable Fair Division

Linear Fisher markets are a fundamental economic model with diverse applications. In the finite-dimensional case of n buyers and m items, a market equilibrium can be computed using the celebrated Eisenberg-Gale convex program. Motivated by large-scale Internet advertising and fair division applications, we consider a generalization of a linear Fisher market where there is a finite set of buyers and a measurable item space. We introduce generalizations of the Eisenberg-Gale convex program and its dual to this setting, which leads to infinite-dimensional Banach-space optimization problems. We show that these convex programs always have optimal solutions, and these optimal solutions correspond to market equilibria. In particular, a market equilibrium always exists. We also show that Karush-Kuhn-Tucker–type optimality conditions for these convex programs imply the defining properties of market equilibria and are necessary and sufficient for a solution pair to be optimal. Then, we show that, similar to the classical finite-dimensional case, a market equilibrium is Pareto optimal, envy-free, and proportional. Moreover, when the item space measure is atomless (e.g., the Lebesgue measure), we show that there always exists a pure equilibrium allocation, which can be viewed as a generalized fair division, that is, a Pareto optimal, envy-free, and proportional partition of the item space. This leads to generalizations of classical results on the existence and characterizations of fair division of a measurable set. When the item space is a closed interval and buyers have piecewise linear valuations, we show that the infinite-dimensional Eisenberg-Gale–type convex program can be reformulated as a finite-dimensional convex conic program, which can be solved efficiently using off-the-shelf optimization software. Based on the convex conic reformulation, we also develop the first polynomial-time algorithm for finding a fair division of an interval under piecewise linear valuations. For general buyer valuations or a very large number of buyers, we propose computing market equilibria using stochastic optimization and give high-probability convergence guarantees. Finally, we show that most of the above results easily extend to the case of quasilinear utilities.