This paper considers a  linear Fisher market with n buyers and a continuum of items. In order to compute market equilibria, we introduce (infinite-dimensional) convex programs over Banach spaces, thereby generalizing the Eisenberg-Gale convex program and its dual . Regarding the new convex programs, we establish existence of optimal solutions, the existence of KKT-type conditions , as well as strong duality . All these properties are established via non-standard arguments, which circumvent the limitations of duality theory in optimization over infinite-dimensional vector spaces. Furthermore, we show that there exists a pure equilibrium allocation, i.e., a division of the item space. Similar to the finite-dimensional case, a market equilibrium under the infinite-dimensional Fisher market is Pareto optimal, envy-free and proportional. We also show how to obtain the (a.e. unique) equilibrium price vector and a pure equilibrium allocation from the (unique) n-dimensional equilibrium bang-per-buck vector. When the item space is the unit interval 0,1 and buyers have piecewise linear utilities , we show that \epsilon-approximate equilibrium prices can be computed in time polynomial in the market size and \log \frac{1{\epsilon}. This is achieved by solving }  a finite-dimensional convex program using the ellipsoid method. To this end, we give nontrivial and efficient subgradient and separation oracles. For general buyer valuations  , we propose computing market equilibrium using stochastic dual averaging, which finds an approximate equilibrium price vector with high probability  .
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 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 {\epsilon}. This is achieved by solving } 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. For general buyer valuations or a very large number of buyers , we propose computing market equilibrium using stochastic dual averaging, which finds an approximate equilibrium price vector with high probability . Numerical experiments illustrate the efficiency and stability of the approaches .
R
This
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
A
generalization of
R
with n
where there is a finite set of
R
In order to compute market equilibria, we introduce (infinite-dimensional) convex programs over Banach spaces, thereby generalizing
We introduce generalizations of
R
. Regarding the new convex programs, we
to this infinite-dimensional setting, which leads to Banach-space optimization problems. We
R
the existence of KKT-type conditions
strong duality
R
strong duality
necessity and sufficiency of KKT-type conditions
R
vector
Banach
D
Similar to the finite-dimensional case, a market equilibrium under the infinite-dimensional Fisher market is Pareto optimal, envy-free and proportional. We also show how to obtain the (a.e. unique) equilibrium price vector and a pure equilibrium allocation from the (unique) n-dimensional equilibrium bang-per-buck vector.
D
the unit interval
R
0,1
a closed interval
R
utilities
valuations
D
\epsilon-approximate equilibrium prices can be computed in time polynomial in the market size and \log \frac{1
A
the Eisenberg-Gale-type convex program over the infinite-dimensional allocations can be reformulated as
R
program using the ellipsoid method. To this end, we give nontrivial and efficient subgradient and separation oracles.
conic program, which can be solved efficiently using off-the-shelf optimization software based on primal-dual interior-point methods.
A
or a very large number of buyers
A
. Numerical experiments illustrate the efficiency and stability of the approaches