  Computing market equilibria is a problem of both theoretical and applied
interest. Much research to date focuses on the case of static Fisher markets
with full information on buyers' utility functions and item supplies. Motivated
by real-world markets, we consider an online setting: individuals have linear,
additive utility functions; items arrive sequentially and must be allocated and
priced irrevocably. We define the notion of an online market equilibrium in
such a market as time-indexed allocations and prices which guarantee buyer
optimality and market clearance in hindsight. We propose a simple, scalable and
interpretable allocation and pricing dynamics termed as PACE. When items are
drawn i.i.d. from an unknown distribution (with a possibly continuous support),
we show that PACE leads to an online market equilibrium asymptotically. In
particular, PACE ensures that buyers' time-averaged utilities converge to the
equilibrium utilities w.r.t. a static market with item supplies being the
unknown distribution and that buyers' time-averaged expenditures converge to
their per-period budget. Hence, many desirable properties of market
equilibrium-based fair division such as no envy, Pareto optimality, and the
proportional-share guarantee are also attained asymptotically in the online
setting. Next, we extend the dynamics to handle quasilinear buyer utilities,
which gives the first online algorithm for computing first-price pacing
equilibria. Finally, numerical experiments on real and synthetic datasets show
that the dynamics converges quickly under various metrics.
