Online Algorithms for the Santa Claus Problem
Authors: Max Springer
MohammadTaghi Hajiaghayi
Debmalya Panigrahi
MohammadReza Khani
Venue: NeurIPS 2022 Accept (2022)
Keywords: fair allocation
online algorithm
maxmin
random order model
optimal competitive ratio

Abstract: The Santa Claus problem is a fundamental problem in {\em fair division}: the goal is to partition a set of {\em heterogeneous} items among {\em heterogeneous} agents so as to maximize the minimum value of items received by any agent. In this paper, we study the online version of this problem where the items are not known in advance and have to be assigned to agents as they arrive over time. If the arrival order of items is arbitrary, then no good assignment rule exists in the worst case. However, we show that, if the arrival order is random, then for $n$ agents and any $\varepsilon > 0$, we can obtain a competitive ratio of $1-\varepsilon$ when the optimal assignment gives value at least $\Omega(\log n / \varepsilon^2)$ to every agent (assuming each item has at most unit value). We also show that this result is almost tight: namely, if the optimal solution has value at most $C \ln n / \varepsilon$ for some constant $C$, then there is no $(1-\varepsilon)$-competitive algorithm even for random arrival order.

Online Algorithms for the Santa Claus Problem
MohammadTaghi Hajiaghayi
MohammadReza Khani Microsoft Bing Ads Microsoft Corporation Redmond, WA khani878gmail.com
Department Computer Science
University of Maryland College Park, MD hajiagha@umd. edu
Debmalya Panigrahi
Max Springer
Department of Computer Science
Department of Mathematics University of Maryland College Park, MD mss4230und, edu
Duke University
Durham, NC
debmalya@cs duke. edd
Abstract
The Santa Claus problem is fundamental problem in fair division: the goal is to partition set of heterogeneous items among heterogeneous agents so as to maximize the minimum value of items received by any agent. In this paper, we study the online version of this problem where the items are not known in advance and have be assigned agents as they arrive over time. If the arrival order of items is arbitrary, then no good assignment rule exists in the worst case. However, we show that, if the arrival order random, then for n agents and any 0, we can obtain a competitive ratio of 1 - when the optimal assignment gives value least (log n/e²) to every agent (assuming each item has at most unit value). We also show that this result is almost tight: namely, if the optimal solution has value at most C' In n/c for some constant C, then there is no compettiiveee algorithm even for random arrival order.
Introduction
Fair allocation of resources one of the central themes of algorithmic faimess and game theory. In fact, the theory of fair division has its roots in mathematics going back to as early as 1948 [56]. In the general setting, this problem comprises set of items that must be divided among a set of agents in an egalitarian manner, where each agent has a (possibly non-uniform) valuation for each item. A natural objective capture the goal of fair division received by any agent. This gives rise to the famous "Santa Claus problem" that we describe below.
maximize the minimum total value of items
In the Santa Claus problem, originally described by Bansal and Sviridenko in 2006 12 (although it was studied under different names or assumptions prior to this), the Santa Claus is said to have set of presents be distributed equitably among n children. Each child [n] has some arbitrary non-negative value Vij for present j E [m]. Santa's 's goal is to distribute the presents in way that makes the least satisfied child maximally satisfied. More formally, this means that the assignment seeks to maximize the minimum total value of the presents received by any child, where the total value presents received by child is the sum of her values for the presents that she received. The Santa Claus problem can be formalized as the following integer program:
m
n
max
min [Ein
Jij S Vj E [m], x E {0, 1m
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

There is substantial literature going back more than 50 years that studies variants of this problem in the offline setting (see related work). In many practical situations, however, the set of items to be allocated is not known in advance. For example, in online advertising, ad-space providers will receive monetary bids from competing agents for the display of their advertisements in real-time for The provider must then make irrevocable decisions as to which advertiser's s bid to accept based only on knowledge of prior allocations and the current bids for the available space TO [2). Beyond advertising, online allocation procedures have been useful in the study of donation distribution, wireless charging networks, organ donor matching, etc (see [ for survey of these applications).
an available space on a webpage [17
15
38 59
Motivated by these applications, we consider the online Santa Claus problem in this paper. In this setting, the items arrive in an online sequence and must be allocated to one of the agents imme- diately upon arrival. As in the offline problem, our goal is to maximize the minimum total value among all agents. To illustrate the problem, con- sider the simple example in Figure on the right where edges represent unit value of an agent for an item. At the time of the first arriving (left- most) item, all agents can be matched to this item and therefore with probability& 1/ any agent will receive it. However, as we continue forward with the input stream, we in retrospect that the only nonzero max-min solution corresponds to the case where the first item was allocated to the rightmost agent (as it is the only item for which they have a nonzero value).
Agezzs
Japot stresm
Figure I: Example online problem instance. Fixed agents are presented in the top row and the arriving items are arranged from left to right in correspon- dence with their arrival order. An edge indicates a nonzero item valuation for a given agent.
Following standard terminology for online algorithms (see, e.g., [6] we define the competitive ratio of an online algorithm as the minimum ratio between the value of the (maximization) objective in the algorithm's 's solution to that in the optimal (offline) solution in hindsight. We furthermore discuss the additive regret as the additive loss factor of our algorithm. More formally, we say our algorithm, AL.G, has competitive ratio and additive regret if ALG 2 OPT b.
Prior work on the max-min objective in the online setting required various relaxations of the problem, such allowing for some reordering in the allocation process PS] restricting the number of agents 39 57 (58) or allowing migration of items after assignment
This is because of two reasons. First, even in the offline setting, there remains significant gap between the best upper and lower bounds on the approximation ratio of the Santa Claus problem, and bridging this gap is major open problem. Second, as will soon see, there is simple construction for the online problem that shows the competitive ratio cannot be better than n. To bypass these bottlenecks, our first assumption in this paper is that the items arrive in random order. This is a standard assumption that has been used to 45), But, even with this assumption, we show that obtaining a competitive solution is impossible in general for small problem instances. This motivates our second assumption: that the objective value of the optimal solution is sufficiently large (with respect the values of individual items). With these two assumptions, we give an algorithm that obtains a competitive ratio of (1 E) for any e >> O. We note that using standard techniques, the assumption about the optimal objective being sufficiently large can be replaced by corresponding additive regret in the competitive ratio.
simplify many related online problems 9 24 32
RE
We now formally define the two online input models that we consider in this paper: adversarial and random order input.
Definition 1.1 (Adversarial Input). An adversary selects the value vector v E [0, 11"h of each arriving item for all the agents, well as the order in which these vectors arrive.
Definition 1.2 Handom--Ordr Input). An adversary selects the value vector v 10, of each arriving item for all the agents, but these vectors are randomly permuted to determine their arrival order.
Note that in the literature, the independent and identically distributed (i.id.) input model is also often studied for related problems distribution over inputs that is unknown to the algorithm and arriving items are sampled i..dd from
551 (52) In this model, the adversary picks a
2

---

Table 1: Online Results for the Santa Claus Problem
Our Results
Input Model
Algorithm
Competitive Ratio
Adversarial
RANDOM
(--² OPT
log
g²
Random Order
GREEDY WR
(1 =)OPT 0
log
The random order model is stronger than the i.i.d. model the sense that any algorithmic result for the random order model automatically extends to the i.id. setting as well. This includes the algorithmic results that we obtain in this paper for the random order arrival model.
this distribution.
1.1 Problem Definition
We here introduce the notation that we will use in the rest of the paper. Let v'...., t E [0, 1 denote the input sequence of items arriving in random order where v is the value of the t-th item to the i-th agent. We additionally denote by x" E [0, 1J" the fractional allocation of each item by the algorithm. We further let the corresponding allocations of a fixed (offline) optimal solution be denoted as x',...,''' x". [0, 1]"h and let OPT denote the max-min objective value of the optimal solution. For simplicity, we slightly abuse notation by letting V = (ufz),.... x1 and
V (ofz)-- 11 for [m]. Our algorithm thus seeks to maximize the coordinate-wise minimum of 2 V*.
1.2 Our Contributions
First, we give simple construction show that if the arrival order the items is adversarial, then the best competitive ratio that can be achieved is only 1/n. (In fact, we also match this competitive ratio using a simple algorithm in the supplementary material.)
Theorem 1.3 (Adversarial Input). In the adversarial setting, no algorithm can obtain a competitive ratio better than 1/n.
This motivates us to consider the random order model, where an adversary again selects the set of items but they are then presented in random permutation order. For this setting, give an algorithm that obtains a fractional assignment that is nearly optimal:
Theorem 1.4 (Random Order: Algorithm). For any s > 0, there is an online fractional algorithm for the Santa Claus problem that has a competitive ratio of -) in the random order inpul model under the assumption that OPT 2 Ω (log n/=").
We further show that, through randomized rounding, we can give an integral allocation that retains the near optimality of this fractional allocation.
Finally, we show that the lower bound on the value of OPT in the above theorem necessary:
Theorem 1.5 (Random Order: Impossibility Result). For any ε (0, 1), there no online algorithm for the Santa Claus problem in the random order input model that has competitive ratio of (1 s) when OPT < C. In for some (absolute) constant C > 0.
The reader will note that the lower bound on OPT precise as function of n, but there is slight mismatch between the upper and lower bounds as a function of 9 - bridging this gap is interesting open question.
We summarize our results for the online Santa Claus problem in Table 1.2
1.3 Related Work
The general case of the Santa Claus problem was initially explored (under different name) in the field of algorithmic game theory for the fair allocation of goods [7]. By studying the assignment L.P of [Í for the dual "makespan" problem, Bezakova and Dani I derived an additive approximation of maxi Vig, i.c., the objective in the algorithm's solution is at least OPT max, Viy where

---

OPT is the objective value of the optimal solution. They also extended the hardness result on the dual makespan minimization problem 46 to demonstrate that the Santa Claus problem is NP-hard and cannot be approximated to a factor better than 2. Later, Bansal and Sviridenko [12] demonstrated that the integrality gap of the configuration I.P for this problem (((m)), while Asadpour and Saberi 7 complimented this result with a (vmm log m) upper bound for the same LP relaxation. To date, the best algorithmic result for the Santa Claus is an (n"")(approooo >-approximate algorithm. where E = [lol log n/ log n)) in quasi-polynomic time obtained by Chakrabarty, Chuzhoy, and Khanna 18.
For the special case of restricted assignment, i.e. Vi E {0, h/ Bansal and Sviridenko 12 provided an 5 (log log log m/ log log m) approximaae algorithm that relies on rounding a configuration LP. Later, Feige gave a non-constructive proof that this LP relaxation was within constant factor of OPT [29]. Asadpour, Feige, and Saberi [6] made this constructive, obtaining a 1/ /4-aaprroximation via a rounding algorithm based on local search, but the algorithm is not known to converge in polynomial improved upon the running
time. Further work has since improved this constant factor 40
20
23 5
time [21,, and extended the setting beyond additive valuations
Online Assignment. The study of online assignment is expansive, but much of the classical work is for adversarial arrival order. Even in the random order setting, broad range of problems have been considered in recent years including the secretary problem (9 45). AdWords 22
online etc. One example of max-min online assignment in the random order setting the work of Gollapudi and Panigrahi B6 who considered revenue maximization with faimess objectives. Another related work is that of Molinaro [5T] for the dual min-max objective, who builds on prior work leveraging the experts framework from online learning 3 to give algorithms that simultaneously perform well in the adversarial and random-order settings. A third line of work relevant to our paper is that of online packing problems in the random arrival order (c.g.. EC 2 44 [55] 52 In particular, the results of Agrawal et al. [ have a similar flavor to ours: they obtain (1 - competitiies assuming a large
matching [32 L1, online packing
37
3C 44, online scheduling [51 48
enough optimal value for the online packing problem in the random order setting.
2 Online Algorithm for the Santa Claus Problem in the Random Order Model
In this section, we present the approximately greedy algorithm, Algorithm | and analyze its competi- tive ratio in the random order model. Building on the work of Molinaro for online scheduling 551, we use a greedy algorithm for a smoothed version of our objective function and a restart procedure during the online allocation process to reduce the impact of correlations that arise in this input model.
A natural strategy for our problem is allocate the arriving item to the least satisfied agent. However, one can show this strategy has too high an additive regret [37 [1 as the change in our solution value can vary quickly from one iteration to the next. Instead, we use smoothed version of the greedy algorithm. The algorithm is designed as follows: we first define Φ to be a re-scaled variant of the LOGSUMEXP function that serves as a smoothed minimum. For the first half of the input stream, we select an allocation for each arriving item that maximizes the increase in our smoothed objective function. This stage can be thought of as approximately greedy with respect to the gradient of de. After m items have been allocated, we "restart" the allocation by maximizing the increase in our 2 objective with respect to the f >>> 2 allocations only. This restart procedure is essential for reducing the correlations that arise in sampling without replacement in the random order model since at each iteration of the allocation procedure, our decision depends on at most m items. The pseudocode of this procedure is presented in Algorithm
2
2.1 Algorithm Analysis
In the analysis of the competitive ratio of Algorithm D we will leverage several key facts about the smoothed minimum function dh. This smoothness implies that the gradient nicely captures incremental increase in the objective function, thus allocating with respect to this produces an
essentially greedy process, allowing us to follow the analysis of 0 24 51 to get the desired
guarantees for the radde model. We now state our main result in Theorem 2.1

---

ALGORITHM 1: SMOOTH GREEDY WITH RESTART
Input: 0 < < 1, input stream M of m items Define d2 (u)
In (E, e-r));
for | -= to m/2 do
Select x" E A to maximize de - V*):
end
for t m/2 + do
Select x" E A to maximize de (E+=
V*):
end
Theorem 2.1. For any s > O, Algorithm L guarantees in the randon-order input model that the expected value of the allocation assigned any agent is at least
log
(1 =) OPT OP
Note that this theorem immediately implies the following corollary since the additive regret term can be absorbed in the multiplicative error for sufficiently large OPT:
Corollary 2.2. For any Algorithm has competitive ratio of (1- OPT 2 2(log n//²)..
In order to prove this theorem, we first show some properties of the smoothed minimum function de utilized by Algorithm D theorem.
We will then prove some technical lemmas that will help establish
Lemma 2.3 effectively defines the additive error with respect our true objective, the agent-wise minimum, and stability of the smooth function following each allocation decision. As was shown in prior work, allocating with respect to the order statistics even the LP norm produces either too high of regret factor, or instability in the derivative value under small perturbations to the input value. As such, the smoothing and the following properties are critical maintaining our regret and competitive ratio bounds.
Lemma 2.3. For all u E R., U 1]" and e > O. the function (c(x) = - In EE= E0%) satisfies the following:
(a) mine(u) In < (1) min;
(b) Vue(u+u) E etc. (u)
Furthermore, u, 2 v; for each E [n]. we have
(c) (u v) 0z (u) (v)
The proof of these properties deferred to Appendix due space constraints.
Now utilizing these two properties we can prove the following important bound on the inner product of the smoothed minimum's 's gradient. This will be used throughout analysis bound the incremental change in the objective MAXMIN value after each allocation decision, and the summation these changes be seen as the accumulated "reward" at any given stage of the input stream. The proof is by direct integration of stability property (b) and is thus deffered to Appendix A
Lemma 2.4. For u E Ra and v, v' E 1]", if du + v) 2 Φe(u + v') then (Voz(u),)) 2 28 (V). v²).
We now follow in the intuition of Agrawal and Devanur [ to prove Theorem 2. by bounding the By implementing
incremental increase our "reward" both before and after the restart at this restart in the allocation procedure, we segment the stream into two portions that have identical probabilistic guarantees and reduce the correlation between input elements to allow for an optimal competitive ratio and low additive regret.
5

---

Proof of Theorem 2.7 We note again that in the approximately greedy procedure of Algorithm I we are essentially seleting items greedily according to the gradient of Φe maximize the incremental changes. Due to the restart at m/2, we define
V Voe
Σv V
m for t S
and V = VO.
Σ
V
> m for t
2
2
r=m/2+1
We now proceed by deriving bound min, (E V in terms of our smoothed-approxiiation function Φe. thus bounding the accumulated error by the algorithm when estimating our true objective. By the concavity of &e and Lemma 2.4
we have that
+
V
Pe
Ev
VT
VΦL
Σ
V
V
(Concavity)
We
Vos
Σ
V
V
E FV' vo). (Lemma 2.4
Without loss of generality proceed by considering the first half of the input sequence $ 2) By summing this inequality over the input prior to the restart (from to 2
in we have
mf
/2 V
m/2 Σ V
2 VV.
In n
Φ
6- (0) de
(1)
Now, taking into account the allocation before and after the restart at m and invoking Eq. I for each half of the input stream with the concavity of de. we obtain
2
m/2
2
Σ
V
V
Φ
Σ
ΦE
V
(Ineq. T
1=1
r=m/221
2 2
< e
dr
Σ
V
(Lemma 2.3
r=l
Iln
I
e
min
V
+
(Lemma 2.3
Lastly, by rearranging terms we can bound the element-wise minimum as
2 21n
min Σ V 2
Σ vo)
(2)
Thus, the output of our algorithm will approximate the actual objective function within multiplicative factor of e - R 1 - and an additive regret on the order of In n/c.
We now proceed bound the gap between our algorithmic solution that of the optimal offline solution which, combined with the above error, will give the final result. As such, the final step of our analysis will be take the expectation of this inequality to get the final bounds in Theorem 2.1 Due to the restart and random order input model, the expected increase in maximal value over the first and second half is equivalent.
m
E
V
V
Σ t=m/2+1
V V9)
so without loss of generality we need only bound the first half's value and apply this bound to both portions. The benefit of this restart will yield a tolerable error as compared to the optimal offline solution in each half of the allocation procedure, rather than a continuously accumulating divergence between the two solutions: each arriving job's allocation only dependent upon (at most) a other decisions. We leverage this randomness to obtain the final competitive guarantees [22
2

---

Now, by the nature of greedy selection to maximize our objective function, we must have that in each iteration our algorithm's selection produces an increase in value that least good as that of the
optimal offline solution: &e ( Lemma 2.4
VT)
2 de (E== V + V for each ! Combining this with
we must have
VO
Furthermore, since VΦ. E E probabilistic result that in Appendix will be used bound the above summations derive the final result.
6% and V independent of V we prove the following purely
Lemma 2.5. Consider a of vectors """"""""""" E [0, 1J" and let (Y") replacement. Let Z Ej be a random vector that depends only on [Y')k=]
Fi=1 be sampled without
Fi=1
Then for all
In m
B(Y Z) 2 2 min [EY
(m +
Using this lower bounding result, we can now bound the sum of rewards as
E (V' v') e min I V
Inn
E(m +
Adding this inequality over all & < 2 in combination with min; LE(V
OPT we conclude that
e
2c
E
Σ
2 E
(Lemma 2.3
S
In c(m - +
2
min
E
(Ineq.
(PTT)
Inn
Due to the restart at t extend the sum to t by simply doubling the above RHS. Finally, invoking inequality
we see that
( log
(1 ((=)) OPT O (og n
E
2 OPT O
2
8
8
by the Taylor approximation
E.
2.2 Online Rounding Algorithm
The previous algorithm produces an online fractional solution for the Santa Claus problem. We now show that using simple randomized rounding, we convert this into integer solution.
Theorem 2.6. Fix any > O. Given a (1 e)competitivee online fractional algorithm for the Santa Claus problem, there an online (integral) algorithm whose competitive ratio is (1 (1=O(s)), provided logn
OPT
Proof. The algorithm is simply randomized rounding. If an item is allocated with fraction Zi to agent such that ΣT= Zig I by the fractional solution, then we assign item to agent j with probability Tig. Note that since Vij [0, 1], the fractional value derived by agent from an item j. given by Viyii is also [o, 1]. Thus, by Chernoff bounds, the probability that total value of agent i in the rounded assignment is less than (1 E) Σm DijTii is at most
m
2 _ -1- - 8) OPT)
|lg e²
exp
S exp
(-3
for OPT 2
n
'The optimal offline algorithm may allocate in manner that does not maximize the objective function's increase at iteration in anticipation of better allocation options later in the input sequence.

---

Thus, with probability at least 1 n² we have
m
Miyai 2 (1 ( OPT (1 - (e) OPT.
It follows that the probability that the total value of agent in the rounded assignment is less than (1 - 2e). OPT is at most / Using the union bound over the agents, we get that the probability
that the total value of any agent in the rounded assignment is less than (1 2e) OPT is at most :
Thus, the expected value of the objective is least (1 )1 26)- OPT (1 3c) OPT for large enough n.
Random Order Lower Bound
We here present impossibility result on the Santa Claus problem under the random order input models.
Theorem 3.1. For any y 1), a randomized algorithm ALG for the online Santa Claus problem with random order input satisfies
ALG 2 (1 (1-7).00 OPT,
then OPT Clan for some (absolute) constant C > 0.
We use the following construction from the proof of Theorem There are n agents, of which 1 are private agents and the remaining one a public agent. Every private agent has k distinct private items for which their valuation is each, and the valuation for every other agent O. In addition, there i public items, each of which has valuation of for every agent. The optimal solution is to assign the private items the corresponding private agents, and the public items to the public agent. Thus, OPT
Now, when the items are presented in uniform random order, consider the first e fraction of presented items call this the e-prefix. Our main claim is that with constant probability, the following statements both hold:
there about fraction of public items in this e-prefix
(b) there is at least one type of private item that is missing from this e-prefix.
For property (a), we need the following concentration inequality from Devanur and Hayes
24
Lemma 3.2 (Lemma 3 in (24). ). Let Y (Y1,.... Ym) be vector of real numbers, and let E (0, 1).
Let be a random subset of [m] of size em, and set Ys == Ejes Y, Then, for every (0, 1).
2 I In 3
(2)
2
25 In (2)
Pr Ys E|ys]|
|
Property (a) concerning the fraction of public items in the e-prefix follows almost immediately from the above lemma:
Lemma 3.3. The probability that there are are fewer than 12 fraction of public items in the e-prefix is at most 2 exp (-ek/8).
Proof. We invoke 3.2 with the following setting of variables. Let be a binary vector where Y, for i E [k] and Y, 0 otherwise. (Y, is the indicator for whether an item is public item.) S represents the set of indices in the e-prefix. Then, Ys counts the number of public items in the E-prefix in a random ordering of the items. Clearly, E[Ys] = sk, ||Y| = 1, and Y l|2 = v
Finally, set 8 = 2e 4 or more so In (2) = ck Now, by 3.2 we have
8
2
ek 8 Ys Ek| 2
7
Pr Ys ek| z
3 8 + Vk. | 2
= Pr
ek
< 2e 2e-
12
and the lemma follows.

---

Now, we show property (b) to demonstrate the non non-existence of at least one type of private item in the e-prefix.
Lemma 3.4. The probability that all the n 1 types of private items appear in the e-prefix is at most exp
(- 41-=
Proof. Fix type of private item, say those of type-j. i.e. only agent j (for some j E [n 1) has unit value for this type of item while all other agents have 0 value. First, we bound the probability that no item of type-j appears the e-prefix. To do this, note that this probability can be written, using the chain rule for conditional probabilities, of the ithh item in the E-prefix not being type-j item under the condition that the first were not type-j items either. Clearly, this probability, for any i S enk, is at least 1 (I-E)ø since there are items of type-j among at most (1 - E)nkk items overall after the conditioning. Thus, the probability that no item of type-j appears in the e-prefix is at least
the product (over i from 1 to enk) of the probabilities
items
cnk
1 1 (1 -
by choosing n 1
Denote p- = - Consider the events that at least one item of type-j appears the e-prefix. These events are negatively correlated and therefore, the probability that at least one item of type-j appears in the E-prefix for every j E [n - 1] is at most
(1 p)- S (1 (1-4rth)" n-1 I ee-di=e (n-1)
Now, by setting k = L-g Ig(n - 1) we obtain 2t
1) 44-- (n 1) 2 -he "0.""""" -g(nnnn1) (n - 1) 18(n-1)
and furthermore,
1
Ig(n - 1).
16
Plugging these expressions into 3 appearing the e-prefix at most and the probability of fewer than 12
and
3.4
we get that the probability of every private item type
še fraction of public items
appearing in the e-prefix is most 2e I=
1g(n-1), The latter probability can be further simplified to
1-r
2e - Ig(n-1) 2e - 1n(n-1)
TE
for large enough n.
n
Using the union bound over these two events, we conclude that with probability at least 2 5c
there is at least one missing private item type in the e-prefix, and also at least TV fraction of private items appear in the e-prefix. In this case, in the e-prefix, the algorithm cannot distinguish between the private agent whose item type is missing and the public agent. Thus, in expectation (over the randomness of the algorithm),, at least half the public items in the E-prefix are assigned to the private agent whose item type is missing. As a consequence, at least 24
5s fraction of the public items are not allocated to the public agent in the entire algorithm, which means that the total valuation of the public agent is at most (1 5:) k. Thus, in order to guarantee
ALG 2 (1 - 7) OPT,
we need 7 2 21 i.c.,
2
5. This implies by the set value of that
247
5
1) C. Inn
OPT = k 2s
(g(n-1)
-g(ng 1)
247
Ig(n-1)
for some constant C.
?
This completes the proof of 3.T
In the current work, we have presented impossibility results for the online Santa Claus problem in adversarial and random order input models, as well as near optimal algorithm for the random order setting. These results effectively address the necessary assumptions on the problem to obtain optimal online solutions, and furthermore obtain these results via simplistic algorithms. Since the MAXMIN objective function is the dual of MINMAX used in the makespan and load balancing literature, we hope that the impossibility results presented here can be carried over to address the remaining open questions regarding their tightest additive terms in competitive ratio analysis.

---

4 Acknowledgements and Disclosure of Funding
MohammadTaghi Hajiaghayi was upported in part by NSF CCF grants 21 2114269 and 2218678. Debmalya Panigrahi was supported in part by NSF grants CCF-1750140 (CAREER) and CCF- 1955703 and ARO grant W91 10230. Max Springer was supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE 1840340. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
References
[1] AGRAWAL, S., AND DEVANUR, N. R. Fast algorithms for online stochastic convex program- ming. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms (2014), SIAM, pp. 1405-1424.
[2] AGRAWAL, S., WANG, Z., AND YE, Y. A dynamic near-optimal algorithm for online linear programming, 2014.
[3] ALAEI, S., HAJIAGHAY,, M., AND LIAGHAT, V. The online stochastic generalized assignment problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithmss and Techniques. Springer, 2013, pp. 11-25.
[4] ALEKSANDROV, M., AND WALSH, T. Online fair division: A survey. In Proceedings of the AAAI Conference on Artificial Intelligence (2020), vol. 34, pp. 13557-13562.
[5] ANNAMALAI, C., KALAITZIS, C., AND SVENSSON, O. Combinatorial algorithm for restricted max-min fair allocation, 2016.
[6] ASADPOUR, A., FEIGE, U., AND SABERI, A. Santa claus meets hypergraph matchings. ACM Trans. Algorithms 8, 3 (jul 2012).
[7] ASADPOUR, A., AND SABERI, A. An approximation algorithm for max-min fair allocation of indivisible goods. SIAM Journal on Computing 39, 7 (2010), 2970-2989.
[8] AZAR, Y., AND EPSTEIN, I., On-line machine covering. Journal of Scheduling 1, 2 (1998), 67-77.
[9] BABAIOFF, M., IMMORLICA, N., KEMPF, D., AND KLEINBERG, R. A knapsack secretary problem with applications. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Springer, 2007, pp. 16-28.
[10] BALSEIRO, S. R., AND GUR, Y. Learning in repeated auctions with budgets: Regret minimiza- tion and equilibrium. Management Science 65, (2019), 09622-968..
[11] BAMAS, E., GARG, P., AND ROHWEDDER, L. The submodular santa claus problem in the restricted assignment case, 2020.
[12] BANSAL, N., AND SVIRIDENKO, M. The santa claus problem. In Proceedings of the Thirty- Eighth Anmual ACM Symposium Theory of Computing (New York, NY, USA, 2006), STOC '06, Association for Computing Machinery, p. 31-40.
[13] BEZÁKOVÁ, I., AND DANI, V. Allocating indivisible goods. ACM SIGecom Exchanges 5, 3 (2005), 11-18.
[14] BLANCHARD, P., HIGHAM, D. AND HIGHAM, N. Accurately computing the log- sum-exppp and softmax functions. IMA Journal of Numerical Analysis 41, 4 (2021). 231 1-330..
[15] BLUM, A., SANDHOLMM T., AND ZINKEVICH, M. Online algorithms for market clearing.
Journal of the ACM (JACM) 53, 5 (2006), 845-879.
[16] BORODIN, A., AND EL- YANIV, R. Online compulation and competitive analysis. cambridge university press, 2005.
[17] BUCHBINDER, N., JAIN, K., AND NAOR, S. Online primal-dual algorithms for maximizing ad-auctions revenue. In European Symposium on Algorithms (2007), Springer, pp. 253-264.
[18] CHAKRABARTY, D., CHUZHOY, J., AND KHANNA, S. On allocating goods to maximize fairness. In 50th Annual IEFE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA (2009), IEEE Computer Society, pp. 107-116.
10

---

[19] CHEN, X., AND QIN, S. On-line machine covering two machines with local migration.
Computers Mathematics with Applications 62, 5 (2011). 2336-2341.
[20] CHENG, S.-W., AND MAO, Y. Restricted max-min fair allocation, 2018.
[21] CHENG, S.-W., W., AND MAO, Y. Restricted max-min allocation: Approximation and integrality gap, 2019.
[22] CONITZER, V., KROER, C., SODOMKA, E., AND STIER-MOSES, N. E. Multiplicative pacing
equilibria in auction markets. Operations Research (2021).
[23] DAVIES, S., ROTHVOSS, T., AND ZHANG, Y. A tale of santa claus, hypergraphs and matroids, 2019.
[24] DEVANUR, N. R., AND HAYES, T. P. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce (2009). pp. 71-78.
[25] DEVANUR, N. R., AND JAIN, K. Online matching with concave returns. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing (2012), pp. 137-144.
[26] DEVANUR, N. R., JAIN, K., SIVAN, B., AND WILKENS, C. A. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In Proceedings of the 12th ACM conference on Electronic commerce (2011), 1), pp. 29-38.
[27] EPSTEIN, L.. A survey on makespan minimization in semi-online environments. Journal of Scheduling 21, (2018), 269-284.
[28] EPSTEIN, L., LEVIN, A., AND VAN STEE, R. Max-min online allocations with reordering buffer. SIAM Journal on Discrete Mathematics 25, (2011), 1230-1250.
[29] FEIGE, U. allocations that maximize fairness. In SODA (2008), vol. 8, Citeseer, pp. 287-293.
[30] FELDMAN, J.. HENZINGER, M., KORULA, N., MIRROKNI, V. S., AND STEIN, C. Online stochastic packing applied to display ad allocation. In European Symposium on Algorithms (2010), Springer, pp. 182-194.
[31] FELDMAN, J., KORULA, N., MIRROKNI, V., MUTHUKRISHNAN, S., AND PÁL, M. Online ad assignment with free disposal. In International workshop on internet and network economics (2009), Springer, pp. 374-385
[32] FELDMAN, J., MEITA, A., MIRROKNI, V., AND MUTHUKRISHNNN, S. Online stochastic matching: Beating 1-1/e. In 2009 50th Anmual IEEE Symposium on Foundations of Computer
Science (2009), IEEE, pp. 117-126.
[33] GAO, B., AND PAVEL, L. On the properties of the softmax function with application in game theory and reinforcement learning. arXiv preprint arXiv: aeee:104.000000 (2017).
[34] GOEL, G., AND MEHTA, A. Online budgeted matching in random input models with applica- tions to adwords. In SODA (2008), vol. 8, Citeseer pp. 982-991.
[35] GOEL, G., AND MEUIA, A. Online budgeted matching in random input models with applica- tions to adwords. In SODA (2008), vol. 8, Citeseer, pp. 982-991.
[36] GOLLAPUDI, S., AND PANIGRAHI, of the 23rd ACM International Conference on Conference on Information and Knowledge Management (2014), pp. 1179-1188.
Fair allocation in online markets. In Proceedings
[37] GUPTA, A., AND MOLINARO, M. How experts can solve Ips online. European Symposium on Algorithms (2014), Springer, pp. 517-529.
[38] HAJIAGHAYI, M. T., KLEINBERG, R., AND SANDHOLM, T. Automated online mechanism design and prophet inequalities. In AAAI (2007), vol. 7, pp. 58-65.
[39] HE, Y., AND JIANG, Y. Optimal semi-online preemptive algorithms for machine covering two uniform machines. Theoretical Computer Science 339, 2-3 (2005), 293-314.
[40] JANSEN, K., AND ROHWEDDER, L. A note on the integrality gap of the configuration lp for restricted santa claus, 2018
[41] KARANDE, C., MEHTA, A., AND TRIPATHI, P. Online bipartite matching with unknown distributions. In Proceedings of the forty-third annual ACM symposium on Theory of computing (2011). pp. 587-596.
11

---

[42] KARP, R. M., VAZIRANI, U. V., AND VAZIRANI, V. V. An optimal algorithm for on- on-line bipartite matching, In Proceedings of the twenty-second annual ACM symposium on Theory of computing (1990), pp. 352-358.
[43] KAWASE, Y., AND SUMITA, H. Online max-min fair allocation. arXiv preprint arXiv:2111.07235 (2021).
[44] KESSELHEIM, T., TÖNNIS, A., RADKE, K., AND VÖCKING, B. Primal beats dual on online packing Ips in the random-order model. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing (2014), pp. 303-312.
[45] KLEINBERG, R. A multiple-choice secretary algorithm with applications to online auctions. In Proceedings of the sixteenth amnual ACM-SIAM symposium on Discrete algorithms (2005), Citeseer, pp. 631-
[46] LENSTRA, J. K., SHMOYS, D. B., AND TArdoS, É. Approximation algorithms for scheduling unrelated parallel machines. Mathematical programming 46, (1990), 259-271.
[47] LIPTON, R. J., MARKAKIS, E., MOSSEL, E., AND SABERI, A. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (2004), pp. 125-131.
[48] LIU, F.-H., LIU, H.-H., AND WONG, W. Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs. Theory of Computing Systems 65, 6 (2021), 1009-1032.
[49] MAIDDIAN, M., AND YAN, Q. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In Proceedings of the forty-third annual ACM symposium on Theory of computing (2011), 1), pp. 597-606.
[50] MEHTA, A., SABERI, A., VAZIRANI, U., AND VAZIRANI, V. Adwords and generalized online matching. Journal of the ACM (JACM) 54, 5 (2007), 22-es.
[51] MOLINARO, M. Online and
load balancing simultaneously. In Proceedings of the Tiihty-Eighth Annual ACM-SIAM Symposium Discrete Algorithms (2017), SIAM, pp. 1638-1650.
[52] MOLINARO, M., AND RAVI, R. The geometry of online packing linear programs. Mathematics of Operations Research 39, 1 (2014), 46-59.
[53] NIELSEN, F., AND SUN, K. Guaranteed bounds on information-theoretie measures of univariate mixtures using piecewise log-sum-exp inequalities. Entropy 18, 12 (2016), 442.
[54] PANIGRAIII, D., DAS SARMA, A., AGGARWAL, G., AND TOMKINS, A. Online selection of diverse results. Proceedings of the fifth ACM international conference on Web search and data mining (2012), pp. 263-272.
[55] SEIDEN, S. S. On the online bin packing problem. Journal of the ACM (JACM) 49, 5 (2002). 640-671.
[56] STEIHAUS, H. The problem of fair division. Econometrica 16 (1948), 101-104.
[57] TAN, Z., AND CAO, S. Semi-online machine covering on two uniform machines with known total size. Computing 78, (2006), 369-378.
[58] WU, Y., CHENG, T., AND M. Optimal algorithms for semi-online machine covering on two hierarchical machines. Theoretical Computer Science 531 (2014), 37-46.
[59] ZHOU, Y., CHAKRABARTY, D., AND LUKOSE, R. Budget constrained bidding in keyword auctions and online knapsack problems. In International Workshop on Internet and Network Economics (2008), Springer, pp. 566-576.
12


Reviews:
[{"review_id": "nZgMmQdUeLV", "reviewer": "Reviewer_TiYu", "summary": "This paper studies the maxmin fair allocation problem in the online setting where items have to be assigned immediately upon arrival. The players have additive valuations and the goal is to maximize the minimum valuation accross all players.\n\nThe author first show that in adversarial order, not much can be done: no algorithm has competitive ratio better than 1/n where n is the number of players. This motivates the fact that one has to relax the model a little bit to hope for something interesting. The authors then consider the random arrival order. In this setting, they give a greedy-like algorithm that guarantees a competitive ratio $1-\\epsilon$ under the assumption that OPT is at least $\\Omega(\\log(n)/\\epsilon^2)$ (item have values at most $1$). Finally, they show that if OPT is not at least $\\Omega(\\log(n)/\\epsilon)$ then it is impossible to obtain such a guarantee. Hence there result is tight up to one extra $1/\\epsilon$.", "questions": "First I have a few questions regarding the proof of Theorem 3.1.\n\n- Line 215: Could you elaborate on how you use the concavity in the second line? To me it seems you use the fact that $\\phi$ is superadditive but shouldn't it be subadditive?\n\n- Line 223: Should you replace $\\phi_\\epsilon (V^t)\\geq \\phi_\\epsilon (\\overline{V^t})$ by $\\phi_\\epsilon (\\sum_{\\tau=1}^t V^\\tau)\\geq \\phi_\\epsilon (\\sum_{\\tau=1}^{t-1} V^\\tau+ \\overline{V^t})$ ?\n\n- Line 223-227: you say that \"$\\nabla^t$ is independent of $V^t$\" but it seems that you need  \"$\\nabla^t$ is independent of $\\overline{V^t}$\" to use Lemma 3.5. And also either way, why is this independence property true? \n\n- Line 223-227: More generally, could you elaborate more on the setting of the random experiment and how you apply Lemma 3.5? \n\nMinor comments/questions:\n\n- Maybe specify more clearly that you assume that all items have valuation at most 1. Otherwise the assumption that OPT is at least $\\log(n)$ does not make much sense.\n\n- Line 168: you say that splitting the instance in 2 halves is \"essential for reducing correlations\". Is this technique actually necessary? Or could it be that without splitting in half it would still work?\n\n- References [2],[5],[11],[20],[21],[23],[40] appear only with the year but not the conference/journal it was published in.\n\n\n", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strengths of the paper are (in my opinion) the following: \n\n- the problem is interesting and this is an important problem in the field of approximation algorithms. It is nice to see this problem studied in the online model.\n\n- the results are almost tight.\n\n- Overall the paper is well-written and easy to read.\n\nThe weaknesses are (in my opinion) the following:\n\n- the techniques do not seem really surprising.\n\n- some parts of the proof of the main result are unclear to me (see questions to clarify). I am a little bit worried about this part but I am willing to change my score if the authors clarify.\n\n- Although the results are tight, I am not sure exactly of how significant they are. This assumption that OPT is at least log(n) makes the results a little bit less interesting in my opinion (even though the authors show this is necessary).", "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": "TrQ8oY9j7l", "reviewer": "Reviewer_42k9", "summary": "The paper considers the online version a scheduling problem known as the Santa Claus problem. one is given m jobs that are to be distributed (integrally) among n processors. Each job has a given non-negative value for each machine that is obtained if the job is assigned to that machine. The goal is to assign the jobs so as to maximise the minimum total value of the jobs assigned to any machine. Since the paper considers the online variant of the problem, the jobs arrive one by one and the algorithm must assign each job irrevocably without prior knowledge of jobs that will arrive in the future. \n\nIt can be easily seen that if the arrival order of the jobs is adversarial, then any algorithm performs arbitrarily bad in the worst case. The paper however shows that under the assumption that there is a specific lower bound on the value of the optimal assignment, then there exists an algorithm with a competitive ratio arbitrarily close to 1, and this is \"essentially\" tight. The algorithm is based on first producing a fractional assignment in two stages the first stage is \"greedy\" and also aims to \"observe\" the input instance before trying to maximise the objective further in the second stage. A rounding scheme is provided to produce an integral assignment.", "questions": "- Why is this particular problem of interest to the NeuRIPS community?", "limitations": "No ethical considerations.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well written, the proofs are non-trivial and the obtained results as well as techniques employed are definitely of interest. To summarise, this is overall  a very nice paper.\n\nNevertheless, I hesitate to give a stronger score because it is not clear to me (and neither argued in the paper as far as I can tell) why these results within scope for NeuRIPS and of interest to this particular community.\n\nMinor comments:\n- I would prefer \"uniformly random\" instead of just \"random\". Same on definition 1.2, how are the vectors \"randomly permuted\"?\n- Lines 38-39. You do mention before that the Santa Claus problem was studied before but this sentence seems to suggest that perhaps you introduce it.\n- I understand that the assumption on the lower bound regarding the value that OPT assigns to any machine is necessary, but it would be nice to also provide some intuition on where and how exactly it is used.", "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": "REr-6x36F5t", "reviewer": "Reviewer_QYda", "summary": "The paper considers the online version of a scheduling problem known as the Santa Claus Problem. Similarly as in unrelated machine scheduling, here there are jobs whose running times are machine-dependent. However, rather than minimizing makespan, the goal is to maximize the least loaded machine. The new feature in this paper is that an online model, in which jobs arrive over time, is considered. It is straightforward to observe that if the arrival order is adversarial then, not much can be done, so the paper is mostly about the random order model. The main result of the paper is an algorithm that generates a solution within a factor 1-eps of the offline optimum minus an additive term of log(n)/eps. This is when all values (or processing times) are between 0 and 1 and n is the number of machines. The result implies that if OPT is sufficiently large (say log(n)/eps^2) then the algorithm is truly 1-eps competitive. This result is complemented by Thm 1.5 stating that if OPT is smaller than log(n)/eps then a 1-eps approximation is not possible.   \n\n", "questions": "This is a theory paper and as such, I would like the authors to clearly state what are the key technical innovations. My understanding is that the key is to use LOGSUMEXP as a smoothed minimum. But, are you the first to do this?\n\nThe intuitive explanation of the restarting in your algorithm is not clear to me. Can you elaborate?\n\nYou mention at the end that you would expect your results to somehow extend to the MinMax objective (which is probably more natural). Do you have further thoughts? while I agree that there are similarities in the problems they are still very different.", "limitations": "no comments", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The algorithm is clever. It first finds an online fractional assignment by greedily maximizing the min load... but here instead the authors use the log of the sum of exp as smoothing. Then they note that simple randomized rounding can be used to obtain an integer solution online. While I am not completely sure, I think the algorithmic idea is not novel. Still, making it work precisely requires nontrivial work. \n\nIt is nice to have a nearly tight lower bound and the construction here is nice and simple. ", "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": {}}, {"review_id": "EYi1TdqI_kl", "reviewer": "Reviewer_pZpD", "summary": "The paper considers an online version of the well studied Santa Claus problem - a classical problem in fair division. There are n agents and m items that arrive online. When an item arrives, its value for each agent is revealed and the algorithm needs to assign the item to one of the agents. The goal of the algorithm is to find an allocation to maximize the minimum total value obtained by any agent.\nThe paper proposes a (1-epsilon)-competitive algorithm for this problem under two assumptions, (i) the items arrive in a uniformly random order, and (ii) the instance is sufficiently large, i.e., the optimal solution has a value of Omega(log n/epsilon^2).\n", "questions": "None", "limitations": "None", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The Santa Claus problem is a well-studied problem in fair division and the online generalization studied here is very natural and important. The paper is well-written and is fairly easy to read and follow. \n\nThe algorithm presented is an adaptation of Molinaro’s algorithm for online scheduling for load balancing and is a natural greedy algorithm that assigns the online item so as to maximize a “smoothed” minimum of the agent valuations. The key insight (adapted from prior work) is to effectively restart the algorithm after half the items have been seen so as to reduce the correlations between arriving items.\n\nThe paper also provides a lower bound to demonstrate that the additive factor in the analysis (or the lower bound on OPT) is necessary to obtain a (1-\\epsilon)- competitive algorithm even in the random arrival model.\n\nI am not fully convinced of the relevance of the subject matter to Neurips however. I feel that the paper would be more at home at a theoretical venue.\n", "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": {}}]

Author rebuttal:

Decision: Accept