Incentive-Aware Dynamic Resource Allocation under Long-Term Cost Constraints

Thank you for your insightful review! Here are our responses.

W1 & Q1 (Computational Efficiency of Fixed Point Problem). Indeed, our proposed O-FTRL-FP does not directly allow a computationally efficient implementation. However, it

1. significantly boosts performance. Our first algorithm in Theorem 3.1 (which uses the computationally efficient FTRL) only ensures $\tilde{\mathcal O}(T^{2/3})$ social welfare regret. Furthermore, as indicated by Theorem 4.4, this $\Omega(T^{2/3})$ is unbreakable by standard Online Learning methods. Therefore, our O-FTRL-FP framework is pivotal for breaking the $\Omega(T^{2/3})$ barrier and yielding $\tilde{\mathcal O}(T^{1/2})$ regret.
2. solves an extremely hard problem. The introduction of the Fixed Point problem is due to an extremely hard problem that makes O-FTRL (which is more efficient) inapplicable: For the boosted $T^{1/2}$ regret one need to predict the epoch-$\ell$ loss function $F_\ell(\boldsymbol \lambda)$ before deciding the epoch-$\ell$ dual $\boldsymbol \lambda_\ell$. However, the new loss function $F_\ell(\boldsymbol \lambda)$ also depends on $\boldsymbol \lambda_\ell$, which means a prediction is unavailable before actually deciding $\boldsymbol \lambda_\ell$ – this makes the existing O-FTRL framework inapplicable, and our novel O-FTRL-FP framework resolves this issue. We also incorporate meticulous analysis to ensure the existence of approximate fixed points given approximate continuity of the predicted loss w.r.t. $\boldsymbol \lambda_\ell$. We believe it can be of independent interest to other Online Learning problems where such circular dependencies exist.
3. allows solvable and good approximations. As noticed by the Reviewer, we also provide approximations of our O-FTRL-FP which are numerically solvable by, for example, Newton’s method. In the Supplementary Materials we have attached our codes for reproducibility, and since our executions of 1000 repeated trials (each with 1000 rounds) only takes ~1min on our MacBook M1 Air, we believe the approximations can be efficiently implemented in practice. In addition, we remark that we also numerically plotted the quality of our approximation in Figure 2 (in Appendix). Therefore, we believe our provided approximations are both efficient in practice and of good quality.
4. is only invoked rarely. Finally, we would like to mention that due to our lazy update designs, such Fixed Point problems are only rarely solved (for $o(T)$ times) throughout the $T$ rounds.

Thank you very much for raising this concern. We will move more discussions from the Appendix to the main text in the revision.

W2 (Technical Contributions). Indeed, the primal-dual analysis and the primal allocation algorithm exploit quite a few existing (or similar) ideas; thank you for noticing the way we combine them together is interesting and novel! We would like to further mention that, compared to the non-strategic setting of, for example, Balseiro et al. (2023), the dual update part faces highly non-trivial challenges that require novel technical contributions – in strategic settings, the vanilla FTRL used by Balseiro et al. (2023) no longer works; instead, we propose a technically meticulous O-FTRL-FP framework to ensure $\tilde{\mathcal O}(T^{1/2})$ regret, which can be of independent interest.

For more context, to suppress agents’ incentives to frequently distort dual updates, we propose “lazy updates” that only update the dual every $\text{poly}(T)$ rounds. However, while this eases primal allocations, it raises algorithmic challenges for the dual updates. Indeed, as shown in Theorems 3.1 and 4.4, this yields an $\Omega(T^{2/3})$ barrier. We then propose our novel O-FTRL-FP framework – which solves an extremely hard problem as detailed in the second bullet of our previous response – to get the desirable $\tilde{\mathcal O}(T^{1/2})$ regret. We believe O-FTRL-FP can be of independent interest to other Online Learning problems where a similar circular-dependency challenge presents.

Q2 (Comparison between Our and Standard Settings). That’s a great question! When comparing our setting with the Stochastic Input Model in standard online allocation, e.g., Theorem 1 of Balseiro et al. (2023), our setup additionally allows agents to strategically manipulate their reports in an arbitrary way.

1. Such incentives are common in reality. For example, during the COVID-19 pandemic, the shortage of ventilators required governments to make high-stakes allocation decisions under uncertainty, where regions had varying needs and are strategically reacting for more stakes (Mehrotra et al. 2020, Yin et al. 2023, Pathak et al. 2024). The same also applies to cloud-based research platforms that need to allocate scarce GPUs to support AI and scientific workloads (Perez-Salazar et al. 2022, Chen et al. 2023).
2. Such incentives present highly non-trivial algorithmic challenges. As detailed in our previous two responses, such incentives force us to deploy the “lazy update” technique, which presents an $\Omega(T^{2/3})$ barrier to the dual updates. This barrier, as we discussed in the paper, is unavoidable by general Online Learning algorithms and we propose a novel O-FTRL-FP framework for bypassing it.
3. We give a good solution for such incentives. Although these incentives are common in practice and hard to tackle, no previous work gives satisfactory solutions. On the contrary, by carefully designing the incentive-aware primal allocation framework together with the O-FTRL-FP framework for dual updates, we prove that $\tilde{\mathcal O}(T^{1/2})$ regret is achievable – which matches the non-strategic $\Theta(T^{1/2})$ bound up to logarithmic factors (Balseiro et al. 2023, Arlotto and Gurvich 2019) – and thus giving a good solution for such incentives.

Therefore, we believe that our setup, algorithms, and results – which extend the classical Online Resource Allocation setup by allowing strategic agents – are of great interest to the community.

Additional References:

• Sanjay Mehrotra, Hamed Rahimian, Masoud Barah, Fengqiao Luo, and Karolina Schantz. A model of supply-chain decisions for resource sharing with an application to ventilator allocation to combat covid-19. Naval Research Logistics (NRL), 2020.
• Xuecheng Yin, I Esra Büyüktahtakın, and Bhumi P Patel. COVID-19: Data-Driven optimal allocation of ventilator supply under uncertainty and risk. European Journal of Operational Research, 2023.
• Parag A. Pathak, Tayfun Sönmez, M. Utku Ünver, and M. Bumin Yenmez. Fair Allocation of Vaccines, Ventilators and Antiviral Treatments: Leaving No Ethical Value Behind in Healthcare Rationing. Management Science, 2023.
• Sebastian Perez-Salazar, Ishai Menache, Mohit Singh, and Alejandro Toriello. Dynamic Resource Allocation in the Cloud with Near-Optimal Efficiency. Operations Research, 2022.
• Shi Chen, Kamran Moinzadeh, Jing-Sheng Song, and Yuan Zhong. Cloud Computing Value Chains: Research from the Operations Management Perspective. Manufacturing & Service Operations Management, 2023.

We thank you once again for such a valuable review of our paper. We are more than happy to answer any further questions.

Thank you for your careful and insightful comments! Here are our responses:

W1 (Wording of Incentives). Thank you for sharing your concerns! We remark that all our formal results, for example those in Theorems 3.1 and 3.2, are written in a clear and rigorous way. We prove the existence of a PBE of the agents that ensures $\tilde{\mathcal O}(T^{2/3})$ or $\tilde{\mathcal O}(T^{1/2})$ regret, with 0 constraint violations. We acknowledge that in some places, the usage of “incentive-compatibility” might not be fully accurate, and we will proofread and revise the full paper to ensure a clear and accurate usage. On the other hand, we use the word “incentive-aware” only to highlight the fact that our proposed primal allocation algorithm takes agents’ incentives into consideration. Such usages are also found elsewhere in the literature, e.g., by Epasto et al. (2018), Golrezaei et al. (2019), Zhang and Conitzer (2021). In the revision, we will clearly explain the meaning of “incentive-aware” in our paper.

Additional References:

• Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni, and Song Zuo. Incentive-Aware Learning for Large Markets. In WWW 2018: The 2018 Web Conference, 2018.
• Negin Golrezaei, Adel Javanmard, and Vahab Mirrokni. Dynamic incentive-aware learning: Robust pricing in contextual auctions. Advances in Neural Information Processing Systems, 2019.
• Hanrui Zhang and Vincent Conitzer. Incentive-Aware PAC Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 2021.

W2 (Experimental Setup). Thank you for mentioning this! We would like to emphasize that we use experiments only to complement our theoretical results. That is, instead of supporting the effectiveness of our algorithm (which is already well-justified by the rigorous theorems and lemmas), we use it to illustrate the fragility of vanilla primal-dual methods. Therefore, the easier the setup is, the more convincing our claim that “primal-dual methods fail in really simple setups” is.

Motivated by this philosophy, we give a toy example with very simple ingredients -- 3 agents all using Q-learning (the simple, easy-to-implement, and model-free RL algorithm), 1-dimensional costs, and 1000 trials and rounds. Under this very simple toy example, the vanilla primal-dual method indeed fails. Therefore, we motivate the importance of a new “incentive-aware” primal-dual method that handles agents’ distinct incentives.

Q1 (“Feasibility”). Thank you for pointing this out! The “at the expense of feasibility” was a typo and we actually meant the opposite: In vanilla primal-dual methods, agents report their $u_{t,i}$ as high as possible (as depicted in Figure 1 left), and consequently the minimization of dual-adjusted reports $u_{t,i}-\boldsymbol \lambda_t^T \boldsymbol c_{t,i}$ contains no information about the true value $v_{t,i}$. In this way, the vanilla primal-dual method degenerates to a minimization of costs, and thus the average cost decays (Figure 1 right) – therefore, the allocations become more feasible but far less welfare-efficient. Thank you once again for noticing this, and we will proofread the paper in the revision to make sure no similar typos occur.

Q2 (“Randomized Exploration”). This is a great question and is the key to the randomized exploration part! The following argument is an informal argument of Lemma D.3 in the Appendix (more specifically, Line 736). We will add more explanations to the main text (i.e., around Line 162) in the next revision.

As a recap, randomized exploration does the following: In each round $t$, with a low probability (roughly $1/\text{poly}(T)$), we enter a randomized exploration round -- where we sample a tentative agent $i_t$ uniformly from $[K]$, and also a random price $p$ uniformly from $[0,1]$. We allocate to $i$ at payment $p$ if and only if their report $u_{t,i}\ge p$. In this way:

1. “Over-reporting” $u_{t,i}>v_{t,i}$ means that when $p\in (v_{t,i},u_{t,i})$, the agent pays more than their value (i.e., the revenue is negative).
2. “Under-reporting” $u_{t,i}<v_{t,i}$, on the other hand, means that when $p\in (u_{t,i},v_{t,i})$ the agents loses an opportunity of getting the resource at a lower price.

Thus, in both cases, agents suffer an immediate utility loss of $\frac 12(u_{t,i}-v_{t,i})^2$ in expectation -- which is what we mean by “imposing a direct utility loss”. Therefore, in addition to our other algorithmic component ensuring agents do not gain more by misreporting (dual-adjusted allocation and payment rule), this component makes misreporting further harmful.

Other Issues. Thank you very much for your constructive comments regarding the terminologies in Figure 1, the missing $T$ in the abstract, and the inconsistent $\mathfrak R_T,\mathfrak B_T$ vs $\mathcal R_T,\mathcal B_T$ notations. We will revise them in the next version.

We thank you once again for such a valuable review of our paper. We are more than happy to answer any further questions.

I am satisfied with the response to my second question. However, in general the presentation is not clear enough, because there are many inconsistent terminologies and notations. I am not sure whether the authors are able to fix all these paces and present it in a clean way.

Thank you for your detailed review! Here are our responses:

W1 & Q2 (Computational Efficiency of Fixed Point Problem). Indeed, our proposed O-FTRL-FP does not directly allow a computationally efficient implementation. However, it

1. significantly boosts performance. Our first algorithm in Theorem 3.1 (which uses the computationally efficient FTRL) only ensures $\tilde{\mathcal O}(T^{2/3})$ social welfare regret. Furthermore, as indicated by Theorem 4.4, this $\Omega(T^{2/3})$ is unbreakable by standard Online Learning methods. Therefore, our O-FTRL-FP framework is pivotal for breaking the $\Omega(T^{2/3})$ barrier and yielding $\tilde{\mathcal O}(T^{1/2})$ regret.
2. solves an extremely hard problem. The introduction of the Fixed Point problem is due to an extremely hard problem that makes O-FTRL (which is more efficient) inapplicable: For the boosted $T^{1/2}$ regret, one needs to predict the epoch-$\ell$ loss function $F_\ell(\boldsymbol \lambda)$ before deciding the epoch-$\ell$ dual $\boldsymbol \lambda_\ell$. However, the new loss function $F_\ell(\boldsymbol \lambda)$ also depends on $\boldsymbol \lambda_\ell$, which means a prediction is unavailable before actually deciding $\boldsymbol \lambda_\ell$ – this makes the existing O-FTRL framework inapplicable, and our novel O-FTRL-FP framework resolves this issue. We also incorporate meticulous analysis to ensure the existence of approximate fixed points given approximate continuity of the predicted loss w.r.t. $\boldsymbol \lambda_\ell$. We believe it can be of independent interest to other Online Learning problems where such circular dependencies exist.
3. allows solvable and good approximations. As noticed by the Reviewer, we also provide approximations of our O-FTRL-FP which are numerically solvable by, for example, Newton’s method. In the Supplementary Materials we have attached our codes for reproducibility, and since our executions of 1000 repeated trials (each with 1000 rounds) only takes ~1min on our MacBook M1 Air, we believe the approximations can be efficiently implemented in practice. In addition, we remark that we also numerically plotted the quality of our approximation in Figure 2 (in Appendix). Therefore, we believe our provided approximations are both efficient in practice and of good quality.
4. is only invoked rarely. Finally, we would like to mention that due to our lazy update designs, such Fixed Point problems are only rarely solved (for $o(T)$ times) throughout the $T$ rounds.

Thank you very much for raising this concern. We will move more discussions from the Appendix to the main text in the revision.

W2 (Specific Payment Rule). While we use a specific second-price payment rule to align incentives, we emphasize that it is our novel algorithmic design – specifically, selecting payments based on the second-highest adjusted reports – that ensures misreporting is not beneficial (and through the use of Randomized Exploration rounds, we make misreporting further harmful; see our response to Reviewer Bw7E’s Q2). This design reflects a strength of our approach, not a limitation. Moreover, we believe our other techniques – such as leveraging Randomized Exploration to penalize misreporting – can extend to settings with other allocation and payment rules as well.

Q1 (Choice of Dual Region). That’s a great question! A more natural choice of $\boldsymbol \Lambda$ would be the full non-negative quadrants $\mathbb R_{\ge 0}^d$, which is unfortunately infeasible because we need some $\epsilon$-net arguments over the dual region and thus it must be bounded. The validity of limiting the dual region $\boldsymbol \Lambda$ to the bounded $[\boldsymbol 0,\boldsymbol \rho^{-1}]$ lies deeply in our primal-dual analysis (as we detail below). We will add more explanations in the revision.

For more context, Lemma 4.3 (or Lemma E.1 in the Appendix) relates the quality of dual variables to an Online Learning problem where we compete with all $\boldsymbol \lambda_j^\ast:=\rho_j^{-1} \boldsymbol e_j$ for all $j=1,2,\ldots,d$ at the same time, where $\boldsymbol e_j$ is the one-hot vector on coordinate $j$. Therefore, we pick $\boldsymbol \Lambda$ as the minimal convex set containing all these $\boldsymbol \lambda_j^\ast$’s – and from Online Learning theory the projection onto this $\boldsymbol \Lambda$ indeed ensures a good performance w.r.t. all these $\boldsymbol \lambda_j^\ast$’s.

We thank you once again for such a valuable review of our paper. We are more than happy to answer any further questions.

I would like to thank the authors for the responses. I will keep my rating.

Update on 6 Aug:

Dear AC,

The authors' response has resolved my concern regarding Weakness 2. Although the Weakness 1 (computational efficiency) remains, the merits of the proposed approach outweigh this minor drawback. Therefore, I keep my rating and support acceptance.