Nonstationary Dual Averaging and Online Fair Allocation

We consider the problem of fairly allocating sequentially arriving items to a set of individuals. For this problem, the recently-introduced P ACE algorithm leverages the dual averaging algorithm to approximate competitive equilibria and thus generate online fair allocations. P ACE is simple, distributed, and parameter-free, making it appealing for practical use in large-scale systems. However, current performance guarantees for P ACE require i.i.d.