  Linear Fisher markets are a fundamental economic model with applications in
fair division as well as large-scale Internet markets. In the
finite-dimensional case of $n$ buyers and $m$ items, a market equilibrium can
be computed using the Eisenberg-Gale convex program. Motivated by large-scale
Internet advertising and fair division applications, this paper considers a
generalization of a linear Fisher market where there is a finite set of buyers
and a continuum of items. We introduce generalizations of the Eisenberg-Gale
convex program and its dual to this infinite-dimensional setting, which leads
to Banach-space optimization problems. We establish existence of optimal
solutions, strong duality, as well as necessity and sufficiency of KKT-type
conditions. All these properties are established via non-standard arguments,
which circumvent the limitations of duality theory in optimization over
infinite-dimensional Banach spaces. Furthermore, we show that there exists a
pure equilibrium allocation, i.e., a division of the item space. When the item
space is a closed interval and buyers have piecewise linear valuations, we show
that the Eisenberg-Gale-type convex program over the infinite-dimensional
allocations can be reformulated as a finite-dimensional convex conic program,
which can be solved efficiently using off-the-shelf optimization software based
on primal-dual interior-point methods. Based on our convex conic reformulation,
we develop the first polynomial-time cake-cutting algorithm that achieves
Pareto optimality, envy-freeness, and proportionality. For general buyer
valuations or a very large number of buyers, we propose computing market
equilibrium using stochastic dual averaging, which finds approximate
equilibrium prices with high probability. Finally, we discuss how the above
results easily extend to the case of quasilinear utilities.

Computer Science and Game Theory;Theoretical Economics;Optimization and Control