NeurIPS-22 Rebuttal: Proportionally Fair Online Allocation of Public Goods Using Machine-Learned Predictions

# NeurIPS-22 Rebuttal: Proportionally Fair Online Allocation of Public Goods Using Machine-Learned Predictions :::info 5000 characters per reviewer. ::: ## Comment to Reviewer 1 (f52j) Thank you for your valuable feedback. --- **Regarding the technical novelty compared to Banerjee et al.:** *Algorithm Design* While we adopt the “set-aside greedy” framework, our more general setting introduces challenges which require new ideas to overcome. We touch on these below. Banerjee et al. act on the private good in each round by allocating half of it equally among the agents and the other half greedily to maximize the predicted NSW objective. In our model, the overall budget $B$ crucially connects the different rounds. A natural extension of their approach would be to decouple the rounds by setting an “artificial” per-round budget of $B/T$, but it is easy to see that this would incur $\Omega(T/B)$ proportional fairness (for example, if all agents have value $\epsilon$ for the public good in every round but the last, and a high value for the public good in the last round), which is much worse than the $O(\log(T/B))$ approximation we obtain. To achieve our optimal approximation guarantee for public goods, we instead need to 1) Implement the “set-aside step” in a more careful way (see Algorithm 1), and 2) Dynamically control the amount of budget used by the "greedy step" by adding a linear penalty to the optimization problem solved in each stage. The resulting algorithm is qualitatively quite different from the previous work: whereas the previous algorithm always spent $\frac12$ the budget in each round on the greedy allocation, our algorithm may spend as little as 0 (in rounds where the values are low), as much as $1-\frac{B}{2T}$ (in rounds where the values are high), or any amount in between. It was a priori not obvious how to dynamically adjust the amount of budget used in each round, and the fact that it can be accomplished using a linear penalty may prove helpful to future researchers working on online algorithms that address a global constraint. *Lower Bounds* Our lower bounds (Theorem 1 and 4) are novel and non-trivial. The worst-case instances we design have a very different structure than the instances used by Banerjee et al. because in our instances some of the agents “cooperate” (i.e., they want the algorithm to allocate to the common public goods they like), which is an aspect missing in the context of private goods. We also point out that their lower bounds are slightly loose ($\Omega(\log^{1-\epsilon} N)$ and $\Omega(\log^{1-\epsilon} T)$) whereas ours are asymptotically tight ($\Omega(\log N)$ and $\Omega(\log (T/B))$). --- **In response to your Question 1:** > What is a setting where public goods are appearing online and have to be irrevocably discarded? We believe that online allocation to public goods is practically just as important a problem as online division of private goods. Its most common application is budget allocation over time at various levels of organization. To give you a concrete example, imagine that a company wants to spend its budget for the welfare of its employees. The HR keeps an eye on the deals that emerge every day, for example, high quality coffee beans, printer ink, or cloud storage available at discount on black Friday. Based on the estimated (or elicited) utilities of these deals to the different employees, the HR must decide whether to allocate a portion of the budget to these deals or pass on them. This type of budget allocation over time occurs within households, companies, universities, and even governments. --- **In response to your Questions 2 & 3:** > What are natural examples of divisible public goods? Or is the fractional allocation a stepping stone toward an integer allocation (after rounding of some sort)? Are linear utilities justified? We provide various justifications to study fractional allocations in Section 2 (Lines 138-144). In particular, note that even when the public goods are indivisible (projects which must be either funded or not), fractional allocations naturally help model randomized allocations --- linear utilities are simply the consequence of linearity of expectation (assuming agents are risk-neutral). This is without considering any derandomization, though studying desirable randomized allocations is often the first step in the literature to studying desirable deterministic allocations. --- **In response to your remark about the use of the term "allocation" for public goods:** This is a very valid point. The term "allocating public goods" can get quite confusing, even though there is a sense in which the principal is allocating each funded public good to all the agents (simultaneously). We believe that a slight rephrasing --- "allocating (a portion of the available budget) to a public good" --- would allow us to simultaneously reduce the amount of confusion and stay consistent with the use of the term "allocation" in the literature. In fact, we already used this phrasing sometimes in our submission, alas not consistently. We are happy to consistently use this phrasing in our revision, but are also open to other suggestions. ## Comment to Reviewer 2 (q7D2) Thank you for your valuable feedback. --- **Regarding the tightness of Corollary 1:** > the guarantees in Corollary 1 are when $c_i-s are constant and $d_i$-s are of the order $\log⁡(T/B)$. We don't believe this to be true; Corollary 1 provides guarantees for all possible $c_i$'s and $d_i$'s. Theorem 4 shows a lower bound of $\Omega(\log(T/B))$ that holds even when $c_i=d_i=0$ (perfect prediction), and the bound in Corollary 1 matches this even when $c_i$'s and $d_i$'s are constant (in fact, the $d_i$'s can be as high as $O(T/B)$). This is the sense in which Corollary 1 provides a tight bound: $O(\log(T/B))$ proportional fairness is the best one can hope for with total value predictions, even those that are perfectly accurate (and it can be achieved with predictions that have constant additive and multiplicative error). That said, you are correct that there is an interesting open question regarding what level of proportional fairness can be achieved when only extremely inaccurate predictions are available. We will mention this in our revision. --- **Regarding how the predictions become available:** Indeed, we do not elaborate on how to produce the total value predictions we utilize in our algorithms. This is because this task can be very application-specific: different machine learning algorithms can be well-suited to producing accurate predictions in different applications. Hence, it is commonplace in the literature on online algorithms with predictions --- which we build on in our work --- to assume that predictions of reasonably simple quantities (such as the total value in our case) are available. We also emphasize that while much of this literature only provides "robustness" and "consistency" guarantees, which tell us what happens when the predictions are either perfectly accurate (best case) or utterly garbage (reverting to worst case), we provide parameterized performance guarantees in terms of the accuracy of the predictions, which is more general. --- **In response to your Questions 1 & 2 regarding the differences between binary and non-binary cases:** In the applications that motivate our work, the time horizon $T$ is typically much larger than the number of agents $N$ (which is often fixed). Hence, guarantees that are independent of $T$ (and depend only on $N$) are very compelling. For the case of general valuations, Theorem 4 shows that such guarantees cannot be achieved, even with perfect predictions of total values ($\Omega(\log(T/B))$ is unavoidable). For the case of binary valuations, it just so happens that one can achieve proportional fairness that is independent of $T$ (the $O(\log N)$ proportional fairness in Theorem 2). Thus, our results for binary valuations should be seen as an improvement over the results for general valuations that are achievable precisely due to restricted valuations. Achieving this improvement in the binary case requires slight modifications to the algorithm (for example, using a $1/(2N)$ set-aside budget in certain rounds instead of a $B/(2T)$ set-aside budget in every round). To answer your precise question, one can certainly use Algorithm 1 (general valuations) when valuations are binary and obtain $O(\log(T/B))$ proportional fairness, but this would be weaker than $O(\log N)$ proportional fairness achieved by Algorithm 2. On the other hand, Algorithm 2 isn't well-defined for general valuations, and we do not believe any reasonable proportional fairness guarantee can be achieved by somehow using $1/(2N)$ set-aside budget for general valuations. ## Comment to Reviewer 3 (Lenm) Thank you for your valuable feedback. --- **In response to your Question 1:** > Please clarify why to choose 1/2 as the factor to divide the overall budget? Why not other factors? Will the chosen factors affect the bounds? Any constant factor instead of $1/2$ would result in the same asymptotic results. We use $1/2$ because it is easier to imagine half of the budget being used to guarantee a minimum utility to each agent and the other half being used for myopic optimization. But this is a very good point, and we will discuss this in our revision. --- **In response to your Question 2:** > Have you conducted any experimental analysis on the motivating applications? How about the performance of empirical proportional fairness? There are several reasons why we did not perform experiments. First, our setting is more abstract, and meaningful experiments would require limiting to a specific practical application of our setting. Second, so far, we have found it difficult to obtain real-world data about multiple agents' utilities for public projects in online settings. We are not sure if synthetic experiments would provide useful insights regarding the performance of the algorithms in practical applications. We leave this interesting direction to future work.