Timezone: »

 
Poster
Nonstationary Dual Averaging and Online Fair Allocation
Luofeng Liao · Yuan Gao · Christian Kroer

Thu Dec 01 02:00 PM -- 04:00 PM (PST) @ Hall J #315
in Poster Session 6 »

We consider the problem of fairly allocating sequentially arriving items to a set of individuals. For this problem, the recently-introduced PACE algorithm leverages the dual averaging algorithm to approximate competitive equilibria and thus generate online fair allocations. PACE is simple, distributed, and parameter-free, making it appealing for practical use in large-scale systems. However, current performance guarantees for PACE require i.i.d. item arrivals. Since real-world data is rarely i.i.d., or even stationary, we study the performance of PACE on nonstationary data. We start by developing new convergence results for the general dual averaging algorithm under three nonstationary input models: adversarially-corrupted stochastic input, ergodic input, and block-independent (including periodic) input. Our results show convergence of dual averaging up to errors caused by nonstationarity of the data, and recover the classical bounds when the input data is i.i.d. Using these results, we show that the PACE algorithm for online fair allocation simultaneously achieves ``best of many worlds'' guarantees against any of these nonstationary input models as well as against i.i.d. input. Finally, numerical experiments show strong empirical performance of PACE against nonstationary inputs.

Keywords: Fisher markets · fair division · market equilibrium · online convex optimization · online fair allocation

Author Information

Luofeng Liao (Columbia University)
Yuan Gao (Columbia University)

I am a PhD student in Operations Research (IEOR) at Columbia University working on large-scale optimization in machine learning and decision-under-uncertainty. I have also passed the CFA Level I Exam.

Christian Kroer (Columbia University)

More from the Same Authors