  We consider the problem of fairly allocating items to a set of individuals,
when the items are arriving online. A central solution concept in fair
allocation is competitive equilibrium: every individual is endowed with a
budget of faux currency, and the resulting competitive equilibrium is used to
allocate. For the online fair allocation context, the PACE algorithm of Gao et
al. [2021] leverages the dual averaging algorithm to approximate competitive
equilibria. The authors show that, when items arrive i.i.d, the algorithm
asymptotically achieves the fairness and efficiency guarantees of the offline
competitive equilibrium allocation. However, real-world data is typically not
stationary. One could instead model the data as adversarial, but this is often
too pessimistic in practice. Motivated by this consideration, we study an
online fair allocation setting with nonstationary item arrivals. To address
this setting, we first develop new online learning results for the dual
averaging algorithm under nonstationary input models. We show that the dual
averaging iterates converge in mean square to both the underlying optimal
solution of the "true" stochastic optimization problem as well as the
"hindsight" optimal solution of the finite-sum problem given by the sample
path. Our results apply to several nonstationary input models: adversarial
corruption, ergodic input, and block-independent (including periodic) input.
Here, the bound on the mean square error depends on a nonstationarity measure
of the input. We recover the classical bound when the input data is i.i.d. We
then show that our dual averaging results imply that the PACE algorithm for
online fair allocation simultaneously achieves "best of both worlds" guarantees
against any of these input models. Finally, we conduct numerical experiments
which show strong empirical performance against nonstationary inputs.
