English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the problem of fairly allocating items to a set of individuals,when the items are arriving online. A central solution concept in fairallocation is competitive equilibrium: every individual is endowed with abudget of faux currency, and the resulting competitive equilibrium is used toallocate. For the online fair allocation context, the PACE algorithm of Gao etal. [2021] leverages the dual averaging algorithm to approximate competitiveequilibria. The authors show that, when items arrive i.i.d, the algorithmasymptotically achieves the fairness and efficiency guarantees of the offlinecompetitive equilibrium allocation. However, real-world data is typically notstationary. One could instead model the data as adversarial, but this is oftentoo pessimistic in practice. Motivated by this consideration, we study anonline fair allocation setting with nonstationary item arrivals. To addressthis setting, we first develop new online learning results for the dualaveraging algorithm under nonstationary input models. We show that the dualaveraging iterates converge in mean square to both the underlying optimalsolution of the "true" stochastic optimization problem as well as the"hindsight" optimal solution of the finite-sum problem given by the samplepath. Our results apply to several nonstationary input models: adversarialcorruption, ergodic input, and block-independent (including periodic) input.Here, the bound on the mean square error depends on a nonstationarity measureof the input. We recover the classical bound when the input data is i.i.d. Wethen show that our dual averaging results imply that the PACE algorithm foronline fair allocation simultaneously achieves "best of both worlds" guaranteesagainst any of these input models. Finally, we conduct numerical experimentswhich show strong empirical performance against nonstationary inputs.

Nonstationary Dual Averaging and Online Fair Allocation