Nonstationary Dual Averaging and Online Fair Allocation
Authors: Luofeng Liao
Yuan Gao
Christian Kroer
Venue: NeurIPS 2022 Accept (2022)
Keywords: online fair allocation
Fisher markets
fair division
online convex optimization
market equilibrium

Abstract: 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. 

Nonstationary Dual Averaging and Online Fair Allocation
Luofeng Liao, Yuan Gao, Christian Kroer IEOR, Columbia University (113530, ck294))columbia edu
Abstract
We consider the problem of fairly allocating sequentially arriving items to set of individuals. For this problem, the recently-introduced PACE algorithm lever- ages 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 non- stationary 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 alock-independet (including peri- odic) 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 allo- cation simultaneously achieves "best of many worlds" guarantees against any of these nonstationary input models well against i..d. input. Finally, numerical experiments show strong empirical performance of PACE against nonstationary inputs.
Introduction
In fair division, the goal to allocate a set of items, typically assumed divisible, among a set of agents with heterogeneous preferences, while guaranteeing fairness and efficiency properties. In this paper we are interested in how to fairly and efficiency allocate items that arrive online: at every time step one item arrives, and we must irrevocably assign it to agent. Recently, there has been a growing literature on such online fair allocation problems (AzarcLal
MUGG
Balseuo ellll umu
Gao uizal Batent al, ыиıл] Sinclarr μIZA| Baneriee et
112 Real-world systems
that can be captured by such settings include Internet advertising systems, job recommender systems, cloud computing platforms, and many more. One of the key challenges in such problems to
balance the (often conflicting goals of overall efficient resource utilization with faimess guarantees
for the individual agents.
For this setting, efal (M0zal) shows that a simple mechanism called PACE (Pace According to Current Estimated utility) generates asymptotically fair and efficient allocations when the item ar- rivals are drawn in an i.i.d. manner. PACE gives each agent a per-tinne per-time-step budget of faux currency, and the fair allocation is achieved by having agents participate first-price auctions for each item, using the faux money. By guaranteeing that each agent asymptotically spends their budget at the cor- rect rate, the resulting allocations and prices converge to what is known competitive equilibrium from equal incomes (CEEI), which guarantees both fairness and efficiency. In PACE, each agent maintains pacing multiplier control their spending over time, and the pacing multipliers are up- dated based on buyers' budgets and cumulative utilities. This is similar to how mudge--maaggement
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

systems work in Internet ad auctions. PACE is highly decentralized due to its auction- based alloca- tion, it does not require dividing the item, and it is also completely parameter free. This makes suitable for large-scale practical implementation.
Yet in many large-scale settings, such as the context of fair recommender systems ror
Kroer and Sher-Mosess MIRM or Internet advertising, we would not expect items to be drawn i.idd from single distribution. One alternative is assume that data arrives adversarially, However, this leads to very pessimistic negative results and is not an accurate representation of the data one would expect see in practice. Instead, one would expect the data to have strong stochastic component, but with changes over time, e.g., due to flow of traffic, breaking news events, or system updates (Esindan all MOIK Halseuro et (IZ().
Motivated by the above considerations, we study online fair allocation when the data exhibits non- stationary behavior. In particular, we focus on the performance of the PACE algorithm of Ga
(2))))) We ask
How does PACE behave when nonstationarity is present in the stream of items?
We show that, under several data-input models, the faireess and efficiency guarantees of the PACE algorithm are still preserved, up to errors due to the nonstationarity of the data input. In this sense, significantly extend the main results in aan (ZIzι). To show these results, we first consider the more general setting of nonstationary stochastic optimization and develop new performance guarantees for dual averaging in this setting. Given the ubiquitous use of dual averaging in online and stochastic optimization, our results are of broader interest beyond (fair) resource allocation.
1.1 Summary Contributions
Novel convergence results for dual averaging under three nonstationary settings.
We analyze the dual averaging (DA) algorithm for nonstationary stochastic optimization under differ- ent data input models, namely, (1) mildly corrupted, (2) ergodic and (3) periodic input data. Specif- ically, we consider the composite dual averaging algorithm, where the composite term is strongly convex. We show that, in all cases, the iterates generated by dual averaging (DA) converge to the optimal solution in mean square, where the bound on the meean-squre error decomposes into two terms: i) the typical (log t/t) guarantee known from the i.i.d. case, and ii) term that depends on the amount of nonstationarity in the data input model. Our results recover the classical bounds under i.i.d. data input as a special case.
Theoretical fairness and efficiency guarantees of PACE for nonstationary item arrivals.
We consider the online fair allocation problem where item arrivals follow any of the three data in- put models that consider for DA; these settings generalize the i.i.d. setting in Gao of (EIZI). Utilizing our convergence results for DA under nonstationary data input models, we show that, for item arrivals following these models, PACE ensures convergence of the pacing multipliers, again with a decomposition into a Olog t/t) term as well as a term depending on the nonstationarity. We then show that the agents' realized utilities, envy, regrets, and expenditures all obtain convergence bounds based on the convergence of pacing multipliers. Our results show that PACE as an online fair resource allocation algorithm is robust against distributional uncertainty of the input and auto- matically adapts to many different data input models without any parameter tuning. In Appendix E we provide numerical experiments which corroborate the above theory and demonstrate the practical efficiency of PACE under different data input models.
An extensive review of related work is provided in Appendix A
Notation. We use 1, to denote the vector of ones of length and ej to denote the vector with one in the j-th entry and zeros in the others. We use A(O) to denote the space of probability measures on a measurable space θ and A, to denote the simplex R" To measure the nonstationarity in the input data, we will use the total variation distance. Given two probability measures P and Q, it is defined as ||P- Q| = (1/2) f I
dQ
du du where μ is supporting measure.

---

2 Preliminaries on Online Fair Allocation
An online fair allocation instance with infinitely divisible items with agents and finite horizon t consists of a tuple = (n, t, O Q, v), where @ is the (possibly uncountable) measurable space of all possible items, with associated o-algebra M and a probability measure ja, the distribution Q E ((+") is the distribution over possible sequences of items y = (0I,..., .......6 8,) E O', each of unit supply, and the set v (v),...,, Un) E L (+)" is the set of valuation functions of the agents. Here 1.4 (e) is the space of positive integrable functions on O. Agent sees utility of (0) in item
denote the valuation for agent i of items in the sequence Let Q" be the marginal distribution of the item H" at time We assume Se u;dQ = 1 for all i E [n]. We further assume |0 == max; ||e |oo < oc. We stress that the PACE algorithm that we study is not going to require access either the valuation functions v or the set of possible items O; these are only required in order to discuss the resulting bounds.
+ Abusing notation we let v3(7)
T and Q = (1/t)
Given instance A, the decision maker allocates the stream of items y one at time, in inrevo- cable manner. At time T when item 8, is revealed, the decision maker must choose an allocation xx (ii ; ..,) E An based information available at that time, and allocate accordingly. Here the i-th entry of x" is the fraction of item 0 allocated to agent i. On receiving her fraction, agent i realizes a utility of of == (0 )a: We let x (x ......... .=) denote the sequence of allocations made over time. For agent i, let H, = (x: ..) E R denote the fraction of items given to agent i across time. With this notation, the total utility of agent is (a vz(7)). The goal of the decision maker is to choose, in an online fashion, an allocation æ such that it achieves some form of both efficiency and fairness guarantees.
2.1 Benchmark: The Hindsight Allocation
As benchmark, we will consider the hindsight-optimal allocation. Suppose all items are presented to the decision maker opposed to arriving one by one. In that case, a fair and efficient allocation can be found by allocating using the Eisenberg-Gann (1953).. EG picks the allocation that maximizes the sum of weighted logarithmic utilities (which is equivalent to maximizing the weighted geometric mean of utilities):
(EG) convex program Fisenberg and Gale
EB. log(U)) U, S (r)) Vi E [m] ES VT E
max 22200200
The weights B, represent the priority given to each agent, and they they can be interpreted as budgets in market-based interpretation of the EG allocation. We will focus on the case where B; t/n for all i, but all our results extend directly to the case of unequal weights. which can be useful in
settings such as when buyers have quasilinear utilities Gao all (212 Contzer et when it is desirable to give larger allocation to certain agents.
or
The PACE algorithm asymptotically converges to the optimal dual solution, which is
8" == arg min 320
max (er;(0T) REIN
Σ log 3
(2)
We will also be interested in the underlying problem implied by the average item supplies Se u:z; du, this leads to the infiniteddimensional analogue of (I))
=
/Q/ dur. Letting (u,,2;) ==
log(u:) u4 S (1,, Vi E [no]. ES.5s
(0),
We let u² denote the optimal utilities in Eq. (B). The infinite-dimensional analogue of the dual ( the following. For any do > The infiniteddimensional analogue of (D) is the following. For any
6p > 0,
([(npax max 3,00 (,x,(())) iE(m
1
8* arg min
log 3
ko SP51+60 5o
'The hindsight allocation Eq. ( can be interpreted as competitive equilibrium from equal incomes (CEEI) in the corresponding Fisher market; Appendix B for more details this interpretation.
3

---

A rigorous mathematical treatment of the infiniteddimensinn program can be found in Gao and
Stree (IZAI) and Lao al Section 2). Note the additional constraint in Eq. (H) on does
not affect the optimal solution since 1/n S g S 1; see Lemma in Gao and Kroei (2IZA))
It is well-known that the hindsight allocation generated by the EG program enjoys the following efficiency and fairness properties:
1. Pareto optimality: we cannot strictly increase any agent's utility without decreasing some other agents' utility.
2. Envy-freeness: each agent prefers their own allocation to that of any other agent: (u,()), 2 (1)) for all k *
3. Proportionality: every agent achieves least as much utility under the uniform alloca- tion, i.e. (v;(1), 2 (vi(7), (1/n)1z).
Therefore the hindsight EG allocation the gold standard that we assume the decision maker would use if she had known the sequence of items y in advance. However, in the online setting the decision maker does not know this sequence, and must therefore instead attempt to approximate an equally good allocation in online fashion.
For item sequence 7, we let x² denote the optimal hindsight allocation, which is an optimal solution to Eq. (M)) and we denote the resulting total and average utility as
0p
=- = (v.()),)))) =
x 2 (0)),, of =
(5)
2.2 Performance Metrics
We measure the performance of an online allocation rule x on the instance 7 via the following two quantities. The regret of agent i is the difference between the total hindsight equilibrium utility U? and their realized utilities uf under
(7g = U?-
Σ of
(6)
The envy of agent is the maximal extent which they prefer the allocation of any other agent:
(n) == max { (x) - (1)()),=))
kEjm]
We seek to understand the worst-case behavior of an algorithm when facing a certain class of input distributions. For given input distribution class C C A(O"), we will develop bounds the worst- case regret and envy under any distribution in C:
sup Ey~Q (egg, QEC
sup E (Envy,,(<)) QEC
2.3 The PACE Algorithm
In this section, review the PACE (Pace According to Current Estimated Utility) dynamics (GA Fmal ((ZII). In PACE, each item is allocated via first-price auction, and each agent constructs bids by scaling their value by pacing multiplier. The pacing multipliers are maintained using simple, distributed updates that can be handled either by the agents or by the platform.
Algorithmic details are displayed in Algorithm M Here 11 11 [a]] min h.). At every time step т an item Hr is revealed. At that point every agent comes up with a bid for that item, which is equal to their value for the item multiplied by their current pacing multiplier ST. Then, the agents submit these bids to a first-price auction, and the item is allocated to the highest bidder. For concreteness, choose the bidder with the smallest index if tie occurs, but any rule works. Each agent then observes their realized utility, updates their average utility received so far, and updates their pacing multiplier accordingly. As pointed out in all (илеа), PACE is instantiation of dual averaging Nea ( applied to the dual of the hindsight allocation program in (H)
PACE has many attributes desirable in woaldworld applications.

---

Algorithm 1: PACE(n, t, 0,)
Input: number of agents n, horizon t, algorithm parameter do >
Initialize: Set 3² = (1 + 6o) In.
10',...,04 from the distribution Q. 3 for T = -...... f when item H² is revealed do
Environment draws the item sequence
00}
Agent bids (07), the whole item H is allocated to the highest bidder i" (with arbitrary tie breaking) i" == min arg [ [ 0. (
Agent updates current average utility of (.())) 1 (7) Agent updates the pacing multiplier (87 me [n/(n where the interval
77 = of
[e, h] (1+60)m +
Highlight 1. Decentralization. The PACE dynamics can be run in either centralized (by having the mechanism designer emulate the pacing process for each agent) or decentralized fashion (since the auction-based allocation the only centralized step at each iteration), and are therefore suitable for Internet-scale online fair division and online Fisher market applications.
Highlight Pure Allocation. PACE allows each item be fully allocated to single agent, even though the hindsight performance metric is allowed to utilize fractional allocations. While fractional allocations can be interpreted as randomized allocations many large-scale settings, this may not always be desirable, for example when allocating food to food banks.
Highlight 3. Tuning-free. An important fact about the PACE dynamics is that each agent has stepsize parameter whatsoever, which means that no stepsize tuning is required. Moreover, PACE robust against the types of item arrivals since the algorithm needs neither knowledge of the item distribution P nor the input type C.
In addition to the regret and the envy performance metrics, we will also derive results for the fol- lowing two quantities that characterize the long-run behavior of PACE. Let a' (1/t) E (1/t)-Er= be the vector average realized utilities for all agents. We will show that the agents' utilities con- verge those associated the underlying offline fair allocation problem, u", defined in Eq. (E), in a mean-square sense, i.e., E|]
u²" 12] + 0, as long as the error due to nonstationarity grows sublinearly in the number of time periods. Secondly, define the expenditure of agent at time by bi : 3] ie (0r) 1 {i }7). We will show (1/t) -t= by 1/n in mean square well, long as the error due to nonstationarity grows sublinearly in the number of time periods.
3 Main Results
This section introduces the main results of this paper: the behavior of PACE under three different
types of nonstationary input models. All prior results on fair online allocation have been either for worst-case inputs (with much more conservative guarantees and not for the PACE algorithm) (Azar
MIG Banerjee et all 2 or for i.i.d. input data Gao et all (IZZI)..
We first introduce some notation that will be useful for describing these input models. For & > T 2 1 let (*((i)r) denote the conditional distribution of 6 given (0-,..., 0" For subset I of [t] let Q' denote the joint distribution of the variables ((T)TE.. Let Q = (1/t) E mixture of }Q").. We study three types of input: independent input with adversarial corruption, ergodic and Markov input, and periodic input. For each input setting, we describe our main theorem for the performance guarantees of PACE here. The proofs are given in Appendix D. because these results rely on developing a theory of nonstationary performance of DA, which is done in Section
Et=r Q" be the uniform
3.1 Independent Input with Adversarial Corruption
Adversarial perturbation of a fixed item distribution models scenarios where the items generally behave predictable manner, but for some time steps the input behaves erratically. Typically this is assumed to happen only for a small number of time steps. Such perturbation could be malicious,
5

---

for example when item arrivals are manipulated in favor of certain agents; or non-malicious, such as unpredictable surges of certain keywords on search engines (standaan
We study a type of adversarial perturbation where the item distribution at each time step might be corrupted by arbitrary amount, but distributions at different time steps are independent of each other. We assume the average corruption is bounded by ó, as measured in TV distance. The set of distributions over sequences that we consider then:
(0) = QE - - @llvv $
(8)
We use Ô to hide numeric constants and polynomials of n, |0 and logt. Our main fair online allocation result for the adversarial corruption case is:
Theorem (Independent Case), For the adversarially corrupted and independent case, Algorithm guarantees that for instance A = tn, O Q, v), we have
sup E [egg,, (ECIP
sup (EC
E Envy, = +v(v+ v
(9)
and
su By (1/x)(11))) (u B [| [1]]] ssupeecl By -u [ =
The result shows that the regret and envy performance metrics degrade linearly in the average corrup- tion 8. In the i.i.d. case where 8 = O, we recover the vl regret rate and the 1/t rate of convergence for utilities and expenditures terms of the mean-square error from et (uIRAT). If out of the t distributions items each time step only (VVt) are corrupted, each by a constant amount, then the v regret and envy bounds, as well as 1/t convergence rates, are also preserved.
3.2 Ergodic Input and Markov Processes
To handle correlation across time, we next study ergodic inputs. For these inputs, strong correlation might be present for items sampled at nearby time steps, but the correlation between items decays as they are separated in time. For any integer such that 1 S S 1,
1, we measure the z-step deviation
from some distribution Il E A()) by the quantity
8(L) == sup sup y -=1....t-_
11Q
II ||
Intuitively, this definition tells us that, no matter where and when we start the item arrival process, it takes only steps get 8(1)-close to the distribution II. We will consider the set of ergodic input distributions whose t-step deviation is bounded by 6:
(8, = {o Q ((0) sup sup
11Q I| I 6, for some II E A(6)) (10)
? r=1...,l-
Theorem 2 (Ergodic Case). For the ergodic case, Algorithm guarantees that for an instance A (n, t, θ Q, v), have
sup QECE((.)
E (Reg,
sup QECE((.))
E Envy, - V8.t)
(11)
and (u, 2 [ (1/))_1 SuPQEER
Ey-oq Remark (Markov Input). We can specialize the result in Theorem D to fast mixing or Markov item sequences. Fast mixing means the deviation ő decreases exponentially. i.e.. for all 1 S < 1,
[1'1] .SuP Bynaq [|la' - 1 =b(++//)
sup
sup
1|QT+((11r)) II] S Mp',
(12)
for some M 0, p [0, 1), and II is the stationary distribution. Examples include finite state- space time-homogeneous Markov chains and uniformly ergodic Markov chains on general state log logt+ing
spaces Meyn and Tweedid ZunA Chapter 16). In these cases, setting 1 = loglo-1>
0
log Tog(o-T))
implies 5 < 1/t. This means the Markov chain from which Y is generated takes O t) steps to get (1/t)-close to stationarity. The dominant term for the regret in Theorem D (further ignoring M) is then (1 + Togtp 17) 122 Vt. The term in the parenthesis reflects the inflation caused by input dependency. To recover the case of i.idd. input, we simply send p - and the usual vt regret and envy rates and 1/t utility and expenditure convergence rates are again recovered.

---

3.3 Periodic Input
Item sequences often exhibit statistical periodic structure. For example, when allocating compute time to requestors, there will be more requests during weekdays and less on weekends. The com- pute request patterns vary throughout the week, and yet the weekly pattern would repeat over time. Similarly, Internet traffic typically exhibits periodic structure.
Formally, assume that the horizon & divides into K blocks of time, each of size q. This divides the item sequence 7 into consecutive blocks of length q. Within each block, we allow distribution with arbitrary dependence between time steps, but we assume that the blocks, as a whole, are identically and independently distributed. We define the set of periodic input distributions as follows:
c²) = (( A(09)* Qu
= Q0+1:22
Q'
(13)
Theorem 3 (Periodic Case). For the periodic case, Algorithm D guarantees that for an instance A (n, E, O Q, v), we have
sup (eC
Ex~ (Rgg., (eC*(a)
sup
Enn Envy,, Ö(Vgt)
(14)
and
suPgecP(w) (v) R [IB] (005-(1/// (1/1)),.113] muPpreP T [Inl [w]]] (o En- [1la' -0-1]]=1]]]] -06 /0).
If the length of the blocks is of order o(t) then the time-averagee regret and envy are both vanishing. For the i.i.d. case, we can set q = 1 to recover the previous results.
Now we comment on dependence on the period length q. Suppose the item sequence consists of K blocks, and blocks are i.i.d. We still allow arbitrary dependence within a block. The proof of Theorem B essentially relies on the result (Theorem E that DA produces iterates whose squared error is of order (qq2/t). Consider dual averaging with the knowledge of the block structure g. Then the rate 1/K = q/tt can be achieved by executing DA using one randomly chosen data point within a block, throwing away the rest that same block. Such selection produces K i.i.d. samples from the distribution. In comparison, the rate in Ogg² /t) is worse off by factor of due to not knowing the block-structun information.
4 Proof Technique: Nonstationary Dual Averaging
MI applied to the dual of the The PACE dynamics can be cast online dual averaging (aaa
hindsight allocation program in (I)) This will be discussed in more detail in Section t and Ap- pendix czy. However, in order to characterize its performance under various types of nonstationary input, we first extend the general convergence results for dual averaging to incorporate nonstationary input. The convergence results that we developed for dual averaging under three different types of input models are novel and are of independent interest.
We remark that the results for the stochastic setting given by X180
cannot be used directly, consider ergodic mirror descent
20300
since they rely on the stringent i.i.d. assumption. aisi (MD) for convex problems under some (but not all) of our nonstationary input models. Their results and analysis cannot be used in our case either, since their results do not allow using the composite structure, whose strong convexity we leverage. Moreover, unlike DA, an MD-based approach would require tuning parameters such as stepsizes.
In this section, after introducing the setup of DA in Section result for independent but not identical input in Section B for which we outline the proof idea and technical challenges in Section 3 Due to space limitations, we present DA convergence results for ergodic and periodic inputs Appendix D
present DA convergence
In the nonstationary setup of DA, we emphasize that whenever we mention convergence, we mean convergence of DA iterates to the population-level optimum wi (or sometimes the hindsight opti- mum), up to some error caused by nonstationarity.
7

---

4.1 Review:
The DA Algorithm
We review the dual averaging setup in the strongly convex case stochastic optimization problem of the form
(Kan RABER $1.1). Consider
min ((w) == Ez-11 [((c, 2)] = EE [J(,, 2)] + V ((w)
(15)
where E (R., || is the variable, V is closed convex function with closed domain Dom V := {w R (w: < )o). ). The expectation is taken over probability distribution on a measurable
space Z. For each E Z, the function f(; 2) is convex and subdifferentiable (a subgradient always exists) on Dom V. Let F(w, =) - f(z, w) + V (w:).
Assumptions. Let G(w, =) be fixed element in the set of subgradients 0 (w, =). For almost every 2, it holds [|G(w, 2)||- G. where || ||I max wil (s, w) is the dual norm.
2. There exists an F E R such that F(w, z) v F for all w E Dom v and (almost every) z.
3. is o-strongly convex, i... Vaaw + (1 - a))) < (w)) + (1 - a) V()) a a)]l u| for w, u E Dom V.
Because our strong convexity assumption, the solution to unique. Associated with define wi == arg min Eg-11 (w, 2)]
The dual averaging algorithm (DA) [Xad
иии Algorithm 1) aims produce sequence converg-
ing to the optimal point wi or minimize the associated regret Kind M0R
$1.2). The algorithmic
details for DA presented in Algorithm Note that although KEAn (Z00 only considers the
of i.i.d. data, DA iterates are defined for every input sequence {2, V regardless of any distribu- tional properties of the sequence.
The first step in our analysis is a relationship between regret and the suboptimality ||w, - wi derived by Kiad ( Consider the dual averaging algorithm with data { We denote the one-step subgradient by 9r := G(w,, 27) and the average subgradient by 9. -2 s=1 9z)/T. Given
data {2, 1 we define the regret and the sum of squared subgradient norms
R((w) = Σ (F(w,,,) 2,) ) - F(w, 27)) A, = 2a
(5
Σ (19++11//7)
The bound A, S (6 + log l)G² (20) holds in a deterministic manner due to the bounded subgradi- ent assumption.
Xia
( shows the following bound on suboptimality of we
Lemma (Regret Bound, Section B.2 in Xiad (τTTC).. For any sequence (2+}t=1 any w Dom V
any = 1,2,..., holds [|W - w|| oft A Re(w))
4.2 Review: PACE as Dual Averaging
In this section we review how to cast PACE as dual averaging applied to the problem (8) This deriva-
= - Σ log 8, " - log Fol- piecewise linear function, a subgradient G(3,0) 0) = Ug- (0)er f(3 0) where 8 = min (arg max, (0)} is the index of the winning agent (see, e.g., Heak
tion was originally given in Gan all (Z0ZI). Let f(3, 0) max; B,u; (,;(()) (0). V (B)
in which case we get F(3,0 8)
f(3.0) 0) + ( = maxie[1] (,),
lowing (Gan and roed.
$5), since f(,0))
M Theorem 3.50). Based on this instantiation of DA, we get that the iter- ates {19T 18r)++ generated by the PACE dynamics (Algorithm M) are exactly the iterates w, generated by DA V 7) (Algorithm D) A proof is given in Appendix
Before moving to showing results, let us first touch the fact that dual averaging provides worst-case regret guarantees. Naively, one may expect that these regret guarantees would directly translate into regret guarantees on the primal performance, meaning a bound on sup,, (1)).
2 See the first equation on page 2584 in NAT M0 3o plug in the bound h(w2)) S 2 /// and have the expression of A, in paper.
In MAR (M11 notation, set B, = 0 all r 2 1 and

---

Algorithm 2: DA(G, V (2r1==1)
Input: subgradient G, regularizer v and data { 1
Initialize: set 90 0 and w1 = arg min V.
for 7 =
........... 1,.......
3
Observe 2, and compute 9r = =( 2,).
4 Average subgradients (the dual average) via 0r = --1 ---1 Pr
5
Compute the next iterate w = arg min (gr, w) + [(w}
However, such dual regret bounds do not imply a worst-case primal regret bound. From a technical perspective, is unclear how regret bound on the dual objective would translate regret bound on envy or utilities. Secondly, based results in the online fair allocation literature (Azar ef all UTT. Banerjee et anl (OZA), known that not only can we not get no-regret guarantee on the primal performance, it is not even possible to achieve a constant competitive ratio in the worst-case setting.
4.3 Independent Data with Adversarial Corruption
We present a DA convergence result with independent data in this section. Theorem statements for the ergodic case and periodic case are presented in Appendix D Discarding the i.i.d. assumption on the data { } we let P be the joint distribution of { and let P be the marginal dis- tribution of 2y. We study the relationship between the DA iterates w141 and wi by bounding the mean-square difference 1t_. [|4411 will l and thus demonstrate in what sense the data distribution P should stay close the i.i.d. distribution IT in order to preserve DA convergence.
We first introduce a variant of (d) with target distribution
C (8:1111) = P PE)(O)
(
1
EIer 11 so)
(16)
Theorem 4 (DA Convergence, Independent Data with Adversarial Corruption). If (2)) P and E (8 I). Then for 11
B( [[lwe++ will (6+ Gogt)
8F - - Ō(6 1/1).
o2l
Moreover, the rate ((8+1/t) applies to B[1le411- -100:-1-w;1100 [2
and [[ll will (See Appendix D
Remark 2. From this result we tell when DA retains last-iterate convergence. Suppose the number of corrupted data points of order o(1) (assuming corruption on each data is of the same order), then the corruption per item is 8 o(1) and DA converges to the optimal solution ast t co. Furthermore, if the corruption per data point is of order = O(1/t), then the fast rate 1/t is retained.
By Section to the diinite-dimensiona dual program (8)) This is the building block for our results Section B
get corollary that the PACE iterates { will converge to 8*, the solution
While the full proof is too long to fit in the paper, we now give proof sketch to show the main ideas behind how we derive Theorem EL We begin the proof by noticing Lemma D is deterministic and valid for any {2 J Now set w wi in Lemma MI If the input data {2, ) were i.i.d. from II, i.., 1 then (woii) would be greater than zero, and we would obtain
2 E [[ - wi 1 < at
(6 + logt)
[EA.1] E E[[((wii))
a²t
However, in the nonstationary case, the regret E ((R((W))) might be negative. At high level, our re- sults are achieved by introducing appropriate measures of the nonstationarity and then lower bound- ing [[R((w]))] based on those measures.

---

To this end, we decompose the regret as follows. Write
(e(wii) (F(w,, 2+) - @n((w))) (ón(wi)) F(wii: 2+))
(őn(w>) on (i((w)))
By optimality of w we have 11 O. Using the bound on the TV distance between {PT) J. and II, and boundedness of F we can control the other two terms. The key is, conditional on F,-1, the iterate W deterministic and the distribution of 2, is P due independence assumption. For each term in the first summation, we condition on Fr-1 and obtain
[E[F 2+) (u((w)]]=+-)
F( 2) (dz (1:-11 - F( 2) dII(2))F+-1
F(w,,,)) 2P)
F( 2)d)))))
$ E |/ 2(Tx)))P((d))
F( 2) dII(2) F
2F 2F -IllTy
The second sum can be handled similarly. For the detailed proof and a generalization see Ap- pendix D in Appendix D
We now discuss how this paper handles nonstationarity differently from the existing literature. Let us use Halsero ef all (2(021) as a reference point, since they consider very similar categories of nonstationary inputs. From a online constrained optimization perspective, Balseiro er all (2IZZ) relies on the fact that their objective is separable across timesteps in order to handle nonstationarity. In contrast, this structure does not exist for the online fair allocation problem, because the objective
takes the logarithm of the utility over time. Concretely, in Baisemn et all [ the objective is
of the form Ex=1 (x). This type of time-separability occurs in all works that we are aware of for non-stationary inputs, also e.g. the ergodic mirror descent paper Duchr el all (2IT Daem ar (Bлиτ) is not online setting, but the expectation in their objective is analogous to time separability). Time separability is used as a key property for deriving regret bounds in those papers. The separability enables translating dual regret primal regret by weak duality argument (see e.g. where a time-separable dual allows weak duality).
Prop. in Falseroo et all
In contrast, our problem has time-separability only in the dual formulation, but not in the primal one, which where we ultimately want guarantees (since we are interested in utilities converging). Our contribution to handling nonstationarity in online fair allocation is showing that a dual approach works even without the separability structure. We begin by deriving convergence guarantees on the last dual iterate. which we achieve by modifying the dual averaging proof to take into account nonstationarity and analyzing the stability of the dual variables in dual averaging. We note that this technique depends on strong convexity, unlike for the time-separable case. Next, go from dual last-iterate convergence to primal regret bounds we use the first-order optimality condition for EG program, which are specific techniques for our problem (such techniques were also used in the previous PACE paper ef (2024))
Conclusion
We established new convergence results for dual averaging under nonstationary data input models, namely, adversarial corruption, ergodic, and aleck-independent input models. Leveraging these re- sults, we showed that, for online fair allocation problems with item arrivals generated from the above nonstationary data input models, the PACE algorithm automatically adapts them and achieves asymptotic fairness and efficiency without any parameter tuning. Numerical experiments demon- strated the effectiveness of PACE under these data input models.
Acknowledgments and Disclosure of Funding
This research was supported by the Office of Naval Research Young Investigator Program under grant N00014-22-1-255 1-2530, and the National Science Foundation award IIS-2147361.
10

---

References
Azar, Y., Buchbinder, N., and Jain, (2016). How to allocate goods in an online market? Algorith- mica, 74(2):589-601.
Balseiro, S., Lu, H., and Mirrokni, V. (2020). The best of many worlds: Dual mirror descent for online allocation problems. arXiv preprint arXiv:2011.10124
Balseiro, S. and Gur, Y. (2019). Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, 65(9):3952-390
Banerjee, S., Gkatzelis, V., Gorokh, A., and Jin, B. (2022). Online nash social welfare maximiza- tion with predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1-19. SIAM.
Bateni, M., Chen, Y., Ciocan, D. F., and Mirrokni, V. (2021). Fair resource allocation in a volatile marketplace. Operations Research.
Beck, A. (2017). First-Order Methods in Optimization, volume 25. SIAM.
Besbes, O., Gur, Y., and Zeevi, A. (2015). Non-stationary stochastic optimization. Operations Research, 1227-144244
Birnbaum, B., Devanur, N. R., and Xiao, L. (2011). Distributed algorithms via gradient descent for fisher markets. In Proceedings the 12th ACM Conference Electronic Commerce, pages 127-136. ACM.
Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A. D., Shah, N., and Wang, J. (2019). The unreasonable fairness of maximum nash welfare. ACM Transactions Economics and Compu- tation (TEAC), 7-3)
Cheung. Y. K., Cole, R., and Devanur, N. R. (2020). Tatonnement beyond gross substitutes? Gradi- ent descent to the rescue. Games and Economic Behavior, 123:295-326.
Cheung, Y. K., Cole, R., and Tao, Y. (2018). Dynamies of distributed updating in fisher markets. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 351-368.
Cole, R., Devanur, R., Gkatzelis, V., Jain, K., Mai, T., Vazirani, V. V., and Yazdanbod, (2017). Convex program duality, fisher markets, and Nash social welfare. In 18th ACM Conference on Economics and Computation, EC 2017. Association for Computing Machinery, Inc.
Conitzer, V., Kroer, C., Panigrahi. D., Schrijvers, O., Sodomka, E.,, Stier-Moses, N. E., and Wilkens, C. (2019). Pacing equilibrium in first-price auction markets. In Proceedings of the 2019 ACM Conference on Economics and Computation. ACM.
Conitzer, V., Kroer, C., Sodomka, E., and Stier-Moses, N. E. (2021). Multiplicative pacing equilibria in auction markets. Operations Research.
Duchi, J. C., Agarwal, A., Johansson, M., and Jordan, M. I. (2012). Ergodic mirror descent. SIAM Journal on Optimization, 2244):159-
Eisenberg, E. and Gale, D. (1959). Consensus of subjective probabilities: The pari-mutuel method.
The Annals of Mathematical Statistics, 30(1):165-168.
Esfandiari, H., Korula, N., and Mirrokni, V. (2018). Allocation with traffic spikes: Mixing ad- versarial and stochastie models. ACM Transactions Economics and Computation (TEAC), 6(3-4):1-23.
Gao, Y. and Kroer, C. (2020). First-order methods for large-scale market equilibrium computation. In Neural Information Processing Systems 2020, NeurIPS 2020.
Gao, Y. and Kroer, C. (2021), Infinite-dimension fisher markets and tractable fair division. arXiv preprint arXiv:2010.03025
Gao, Y., Kroer, C., and Peysakhovich, (2021). Online market equilibrium with application to fair division. arXiv preprint a7X1v:2103.12936

---

Gkatzelis, V., Psomas, A., and Tan, X. (2021). Fair and efficient online allocations with normalized valuations. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5440-5447.
Harper, F. M. and Konstan, J. A. (2016). The movielens datasets: History and context. ACM Transactions on Interactive Intelligent Systems (TIS), 5(4):19.
Kroer, C., Peysakhovich, A., Sodomka, E., and Stier-Moses, N. E. (2021). Computing large com- petitive equilibria using abstractions. Operations Research.
Kroer, C. and Stier-Moses, N. E. (2022). Market equilibrium models large-scale internet markets. Innovative Technology at the Interface of Finance and Operations. Springer Series in Supply Chain Management. Springer Natures, Forthcoming.
Manshadi, Niazadeh, R., and Rodilitz, (2021). Fair dynamic rationing. In Proceedings of the 22nd ACM Conference Economics and Computation, pages 694-6955
Meyn, S. P. and Tweedie, R. L. (2012). Markov Chains and Stochastic Stability. Springer Science & Business Media.
Nesterov, Y. (2003). Introductory Lectures on Convex Optimization: A Basic Course, volume 87. Springer Science & Business Media.
Sinclair, S. R., Banerjee, S., and Yu, (2021), Sequential fair allocation: Achieving the optimal envy-efficiency tradeoff curve. arXiv preprint arXiv:2105.0533 0..000.
Varian, H. R. (1974). Equity, envy, and efficiency. Journal of Economic Theory, (1)663--1
Xiao, L. (2010). Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11:2543-2596.
Zhang, L. (2011). Proportional response dynamics in the fisher farket. Theoretical Computer Sci- ence, (12(24)):691-2699
12

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], , [No] or [N/A]. You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section
(b) Did you describe the limitations of your work? [No] Our work is mostly theoretical and studies the fair-allocation algorithm PACE under various nonstationary settings.
(c) Did you discuss any potential negative societal impacts of your work? [No] Not appli-
cable.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We read them.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes) See Section and Section !!
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix Appendix D and Appendix E.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either the supplemental material or URL)? [Yes] See Ap- pendix E
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix B
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No] No applicable.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [No] We synthetic
data.
(b) Did you mention the license of the assets? [No] N/A.
(c) Did you include any new assets either in the supplemental material or as a URL? [No] N/A.
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [No] N/A.
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [No] N/A.
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [No] N/A.
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [No] N/A.
13

---

(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [No] N/A.
14


Reviews:
[{"review_id": "klgwfEjMH9b", "reviewer": "Reviewer_2nRt", "summary": "This paper extends PACE [Gao et al 2021]  for online fair allocation to nonstationary settings. In particular, adversarially-corrupted stochastic, ergodic and periodic input are studied. Technically, this is done by using the connection of PACE with dual averaging (DA), and the new derivations of DA regret.", "questions": "Typo: line 112 \"they they\"", "limitations": "The main application domain is related to fairness. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "(+) This work extends PACE, which was designed for stochastic problems, to non-stationary settings.\n\n(-) The online learning version of DA, aka follow the regularized leader (FTRL, see section 5 of https://arxiv.org/pdf/1909.05207.pdf) is capable of handling adversarial settings. Hence, it is not surprising that DA or PACE works for the nonstationary setting studied in this work. Can the authors discuss more on this? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "L4Gk92FbZvm", "reviewer": "Reviewer_dWex", "summary": "The paper discusses the problem of online fair allocation under nonstationary data distributions. The authors describe the problem of fair item allocation at stake and the PACE algorithm they base their analysis on. Then, they derive several regret bounds under several types of nonstationarity, namely adversarial input, ergodic and periodic distributions. Then, they provide a summary of the proof techniques used to achieve these results.", "questions": "In the original study of dual averaging for strongly convex objectives, Xiao et al. provided a method that could be sped-up with a surrogate function $h$, leading to a refined regret bound (at the cost of the introduction of a new hyperparameter $\\beta_t$). Would such a function be conceivable in this case to improve the PACE performance?\n\nIs there an intuition as to why a soft allocation will not lead to better rates for the PACE algorithm? Pure allocation does sound necessary in some settings but I wonder why a partial allocation could not be better if the setting allows it. Is it because we only care about expected regret here, and not about the variance?", "limitations": "The limitations of the different assumptions are clearly discussed throughout the paper.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and introduces carefully the setup of the problem. Every assumption is justified and seems reasonable.\nThe resulting regret bounds are clear and provided with a quick interpretation.\n\nThe main issue of the paper comes from the empirical study: although the bounds are interesting, it would have been a preferable sanity-check to have toy experiments evidencing that the dependence in the ergodicity/TV-norm/etc.  reflects the true behavior of the regret. The proposed experiments are not in the main paper (and I believe that some results could be shortened/factorized to leave additional space in the main paper) and even the experiments provided in the supplementary materials are not very convincing. They show that PACE algorithm still holds under some nonstationary settings, but they fail to evidence the impact of increasing corruption/deviation from a stationary distribution, which is exactly what the theoretical results state. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FwldoFFyTmD", "reviewer": "Reviewer_4sGJ", "summary": "As I have notified the AC, this paper is certainly beyond my expertise. In addition, I’m not familiar with most paper in references. I'm simply making an educated guess.", "questions": "Is there any connection between the nonstationary setting in this paper and nonstationary reinforcement learning?\n\nRef:\n\nNon-stationary reinforcement learning without prior knowledge: An optimal black-box approach\n\nNonstationary reinforcement learning with linear function approximation\n", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "From an outsider view, I think this paper is clearly written. \n\nThe box around the reference is a little annoying, probably it is better to drop it.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3jSaf48WXA", "reviewer": "Reviewer_nihF", "summary": "This paper considered the problem of fair allocation of sequential items arrivals.  In particular, this paper extended the existing PACE algorithms, which requires i.i.d. item arrivals, to non-stationary cases.  To this end, this paper studied three non-stationary input models: adversarially-corrupted stochastic input, ergodic input, and block-independent input.  For each case, this paper presented new convergence results for PACE with dual averaging algorithm. Finally, numerical results are presented to validate the performance of the PACE against non-stationary inputs. ", "questions": "See limitations above. ", "limitations": "N.A.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n- Generalization of the PACE to practical setting, i.e., non-stationary data.  This is critical and makes PACE more applicable in practice.  In particular, three non-stationary models are investigated. \n- Strong theoretical performance analysis:  For each of the non-stationary model, new convergence results are provided.  The convergence analysis for dual averaging under these three input models are novel and of independent interests.  This will benefit the community at large. \n\nLimitations:\n\nThe reviewer does not identify any major issues in this paper but has some minor comments that can be found below.\n\nOverall, this paper is well written and relatively easy to follow, despite its very theoretical nature. The proposed new ideas and algorithms are clearly presented.  \n\n- However, some good intuitions are missing in some parts for readers to better interpret the theoretical results, e.g., no discussions for Theorem 3 and Theorem 4. The paper seems to end unexpectedly after Theorem 4.  \n- The background of the paper goes almost to page 5, which does not leave enough space to present and discuss the main results in the paper.  It may be better to make the background concise and some may be moved to the supplementary material.  \n- The abstract mentioned the numerical results of the paper; however, the experiments are not presented, until the end of the supplementary material.   ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept