Incentive-Aware Dynamic Resource Allocation under Long-Term Cost Constraints
Authors: Yan Dai
Negin Golrezaei
Patrick Jaillet
Venue: NeurIPS 2025 poster ()
Keywords: Mechanism Design
Online Resource Allocation
Strategic Agents
Primal-Dual
Online Learning
Primary area: theory

Abstract: Motivated by applications such as cloud platforms allocating GPUs to users or governments deploying mobile health units across competing regions, we study the constrained dynamic allocation of a reusable resource to a group of strategic agents. Our objective is to simultaneously (i) maximize social welfare, (ii) satisfy multi-dimensional long-term cost constraints, and (iii) incentivize truthful reporting. We begin by numerically evaluating primal-dual methods widely used in constrained online optimization and find them to be highly fragile in strategic settings -- agents can easily manipulate their reports to distort future dual updates for future gain. To address this vulnerability, we develop an incentive-aware framework that makes primal-dual methods robust to strategic behavior. Our primal-side design combines epoch-based lazy updates -- discouraging agents from distorting dual updates -- with dual-adjust pricing and randomized exploration techniques that extract approximately truthful signals for learning. On the dual side, we design a novel online learning subroutine to resolve a circular dependency between actions and predictions; this makes our mechanism achieve $\tilde{\mathcal{O}}(\sqrt{T})$ social welfare regret (where $T$ is the number of allocation rounds), satisfies all cost constraints, and ensures incentive alignment. This $\tilde{\mathcal{O}}(\sqrt{T})$ performance matches that of non-strategic allocation approaches while additionally exhibiting robustness to strategic agents.

Incentive-Aware Dynamic Resource Allocation under Long-Term Cost Constraints
Yan Dai
Negin Golrezaei Sloan School of Management
Patrick Jaillet Department of EECS MIT jaillet@mit.edu
Operations Research Center MIT yandai20@mitt.cm edu
MIT golrezae@mit.edu
Abstract
Motivated by applications such as cloud platforms allocating GPUs to users or governments deploying mobile health units across competing regions, study the constrained dynamic allocation a reusable resource to a group of strategic agents. Our objective is to simultancously (i) maximize social welfare, (ii) satisfy multi- dimensional long-term cost constraints, and (iii) incentivize truthful reporting. We begin by numerically evaluating primal-dual methods widely used in constrained online optimization and find them to be highly fragile in strategic settings agents easily manipulate their reports distort future dual updates for future gain. To address this vulnerability, we develop an incentive-aves aware framework that makes primal-dual methods robust strategic behavior. Our primal-side design combines epoch- base lazy updates discouraging agents from distorting dual updates with dual-adjust pricing and randomized exploration techniques that extract approximately truthful signals for learning. On the dual side, we design a novel online learning subroutine resolve circular dependency between actions and predictions; this makes our mechanism achieve Ö(VT) social welfare regret (where T is the number of allocation rounds), satisfies all cost constraints, and ensures incentive alignment. This Ö(VT)) performance matches that of non-strategic allocation approaches while additionally exhibiting robustness to strategic agents.
Introduction
Modern platforms and public agencies often face the challenge of allocating limited, reusable resources over time to self-interested agents, who may hide their true desire sake of more favorable allocations. For example, cloud providers must decide how to distribute scarce GPUs to competing jobs under compute and energy constraints (Buyya et al., 2008; Nejad et al., 2014). Govermments may deploy mobile health units or medical devices such as ventilators across regions, where needs vary over time and access is constrained by staffing or capacity (Stummer et al., 2004; Adan et al., 2009). In these settings, some multi-dimensional long-term cost constraints such as energy or staffing while accounting for the strategic behavior of agents with private information.
unit of resource is reallocated across time, and the allocation must respect
central challenge these dynamic environments is being both efficient Lee, maximizing social welfare subject to constraints and robust to agents' strategic manipulation. Focusing on efficiency, primal-dual methods serve as powerful tool in online resource allocation, offering principled ways to handle constraints while adapting to changing demand (Devanur and Hayes, 2009; Golrezaei et al., 2014; Molinaro and Ravi, 2014; Balseiro et al., 2023). These methods maintain dual variables that act as shadow prices resource usage, guiding allocations based on both values and costs. However, these approaches typically assume truthful agents and ignore any strategic responses agents make.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

agenes
weelare narmallzed
30.9%
800%
04
C460
c400
Dlwwning Fina Gcoregg) OLTTU.
Cllarrnng Glisaree as
11M
Figure 1: We simulate a 7-round game for 1000 trials, during which agents use Q-learning to optimize their reporting strategy. Under the vanilla primal-dual algorithm of Balseiro et al. (2023), agents learn to frequently misreport their values, resulting in reduced social welfare and low budget utilization (blue). In contrast, under our incentive-aware mechanism, agents gradually learn report truthfully, leading to significantly improved social welfare while adhering to cost constraints (green).
Indeed, as we illustrate numerically in Figure 1, classical primal-dual mechanisms are highly vulnera- ble to manipulation (see Section 5 for the detailed setup): Strategic agents game the learning process by distorting their current reports influence future dual updates, thereby improving their individual utility but giving low budget utilization and less welfare. This fragility raises a natural question:
With strategic agents, is it still possible to optimize social welfare subject to long-term constraints?
To our knowledge, the only prior work addressing strategic agents in constrained online allocation is that of Yin et al. (2022). While their framework is a valuable step, it has two key limitations. First, it focuses on homogeneous agents with identical value distributions an assumption critical for their equilibrium argument, but unrealistic in many applications. Second, their mechanism focuses a specific type of cost constraint based on some "fair share" per agent, which requires knowing ideal allocation proportions in advance. These assumptions limit the practical applicability of their results. Due to space limitations, more discussions on related works are postponed to Appendix
This paper goes beyond these limitations and yields an incentive-aware primal-dual framework - one that is robust strategic manipulation. To limit agents' influence on the future, we stabilize dual updates through epoch-based lazy updates (fixing dual variables within each epoch), which reduce the impact of any individual report future duals and allocations. To further deter manipulation, we combine dual-adjusted pricing rounds with randomized exploration which imposes immediate utility loss on untruthful agents, thereby creating localized incentives for truthful reporting. We show that, when the dual variables are updated via the classical
Leader (FTRL) algorithm, our mechanism (i) achieves sublinear regret of ( w.r.f. offline optimal allocations, where is the number of rounds, (ii) satisfies all resource constraints exactly, and (iii) admits a Perfect Bayesian Equilibrium (PBE) in which agents have no incentives to misreport in most rounds.
We show that FTRL unable to get 2/32/3) regret: however, we observe that property (ili) allows the planner treat historical reports as reliable estimates of true values, thus enabling optimistic predictions of future outcomes. Building on this, we introduce a novel online learning algorithm -Optimistic FTRL with Fixed Points (O-FTRL-FP)- which solves a small number of fixed-point problems across the time horizon to incorporate such predictive structure." This gives an improved regret bound of O / VT), matching the Ω VT) lower bound for non-strategic constrained allocation (Arlotto and Gurvich, 2019). In doing so, we bridge the gap between online constrained optimization and dynamic mechanism design, enabling robust docision-making in complex, strategic environments.
2 Preliminaries
Notations. For an integer n > 1, [r]] denotes the set {1, .,....,,n.. For a set X,, the probabilistic simplex (X) contains all probability distributions over X. We use bold letters like v denote
n).
Due to a circular dependency between actions and predictions, the O-FTRL framework (Rakhlin and Sridharan, 2013) is not applicable. Our newly proposed O-FTRL-FP framework resolves this issue, and we expect to be of independent interest to the online learning literature; see Section 4.2.4 for more context.

---

Protocol Interaction Protocol for Repeated Resource Allocation
Input: Number of rounds T, number of agents K, value distributions {Va cost distributions [CK), mechanism M (Mr))e(TT) agents' strategy profile (TT,,)) sE[K]
1: Initialize public history: H1.0 f- 2
2: Initialize private history for each agent H1,5 +- ((V))C
3: for each round: = =,,,2 1.2....,7
4: Each agent E [K] observes:
Private value: V/,i V/
Public cost vector: Ct,i ~ C;
5:
Agent i submits report: H4, ( Ct: He,))
6:
Planner applies mechanism: (it, Pt,s,) ) ~ Mi c;; He,0)
7:
Update public history: add (u, Cts lt: Pr,i.) ) to 144100
8:
Each agent updates private history: add oe and (Ue, Ce, des Pr...) to Ho+1.
vector, and use normal letters like 0; for element therein. For random variable X, we (XF to denote its probability density function (PDF). We use O to hide all absolute constants, O to additionally hide all logarithmic factors, and Ör to focus on the polynomial dependency of T,
Setup. We consider the problem of allocating indivisible resources over T rounds from central planner to K strategic agents, indexed by 1,2,.... K. In each round, the planner allocates a single indivisible resource to of the agents, aiming to maximize social welfare while satisfying d long-term cost constraints simultaneously; more details on this objective can be found in Section 2.3.
2.1 Agents' Values and Costs, Planner's Allocation and Payment
In each round f E [T], agent i E [K] has a private scalar value U2 E [0, 1] and a public d-dimensional cost vector Ct2, E [0, 1]a Allocating the resource to agent round yields a value Vr, to the agent and incurs Cr,i, units of cost along dimension j for all j [d]. We assume that values and costs are independent across agents and rounds; specifically, U4.; and Ct,; are i..dd. samples from fixed but unknown distributions Vi E A(0,, 1)) and C, E A 1]"). respectively, for all E [T] and í E [K].
Every agent i E |K], after observing their own private value Ut strategically generates a report U4,; E [0, 1] which may differ from Vt,i. We defer the generation rule of such reports Section 2.2. After observing agents' strategic reports u, and cost vectors c, (but without access to the true values vt), the planner either irrevocably allocates the resource to one the agents i, [K] or forfeits it.
After the allocation, the planner decides payment charged from the winner i, denoted by Pt.fe For all remaining agents + it, the payment Pt, 0. The planner maximizes the Touud cumulative social welfare Σ Vt,ú, subject to long-term constraints that the T -round average costs are no more than pre- specifidd threshold p E [0, 1] i..,, + ΣT= Ct I p. where is compared element-wise.
2.2 History, Planner's Mechanism, and Agents' Strategies
At the beginning of round t E [T]. the public history is given by He.o := {(ur, Cry ir Prai Pr.,)) rrer Each agent E [K] additionally has access to their own past values and all agents" value and cost distributions. Thus, the private history available to agent at the beginning of round is
He Ho,o U (wra)ree U (01,C)))
Vt E (T), E (K].
In each round E [7), the planner determines the allocation and payment (ie, Pt.s,) based on agents' reports u4, cost vectors ct, public history H4 and possibly some internal randomness used to break ties or randomize decisions. We write i, = Pt.i. = 0 when the allocation forfeited. Formally,
(ie, Pt...) ~ Me c;; He,0), where My: (u,, C22 H4,0) + PD.(...P..))
Vt E [T].
We assume the distributional information is known across the agents since such information (or at least some prior) is necessary for the definition of Perfect Bayesian Equilibrium (PBE) in Definition 2. We adopt this mutually known setup as it is most challenging for the planner terms of information asymmetry.

---

The collection of decision rules M = (Mr is referred to as the planner's s mechanism. We emphasize that the planner does not know the agents' value or cost distributions, whereas the mechanism M is publicly known to the agents, as is standard in the literature.
For each agent [ their report ", is determined based their private value Vt,s, the cost vector Ce. their private history He, and potentially some internal randomness. Formally, we write
"1, Le,a (v C3 H,,)), where Te,s (VL.s) Ct2 H4,:) PDF( E [T], i E [K].
Agent i's decision rules collectively form their strategy π, := (Te)) The agents' strategies together constitute a joint strategy π == (T))ee]K- We summarize the interaction as Protocol 1.
2.3 Agents' Behavior and Planner's Regret
To model agents' behavior in dynamic environment, adopt the y-immatient agent framework introduced by Golrezaci et al. (202 la 2023) which captures the idea that agents often prioritize immediate rewards over long-term gains due to bounded rationality, uncertainty about future rounds, or limited planning horizons - while the planner is more patiently optimizing the long-run welfare. Assumption 1 (y-IImaateet Agents). For some fixed constant y E (0, 1) unknown to the planner, every agent E [K] is "yimpatient in the sense that they maximize their y-discounted T T-round gain
(T: =
E Protocol
Σ
- -i =
Vi E [K], E II,
(I)
In this paper, we study the equilibrium concept of Perfect Bayesian Equilibrium (PBE):
Definition 2 (Perfect Bayesian Equilibrium). Fix mechanism M (M1, M2...., Mr). An agents' joint strategy w a Perfect Bayesian Equilibrium (PBE) under M, if any single agent's 's unilateral deviation from π does not increase their own gain. Formally, joint strategy π II is PBE if
V77 (m; o π - M) 2 V. (T( R), Vi E [K], Vagent i's strategy x[c
The planner aims to maximize social welfare, namely the expected total value yielded from allocations BI>i= d. while satisfying the long-term cost constraints Σ Cr, p simultaneously. To evaluate a mechanism's performance, we compare the allocations against the following offine optimal benchmark, which performs a hindsight optimization using agents' values and costs:
1 E T
{ he(T)
argmax [(JUUK]
subject to
C S.p
(2)
We remark that benchmark in Eq. (2) depends on the full sequence of true values (v:)T= and costs (ce |7 which are not observable to the planner. This distinguishes from typical online learning benchmarks, which fixes policy before the game; (Balseiro et al., 2023) for a related discussion. Since Eq. (2) relies on information unavailable at decision time, cannot be matched exactly. Instead, we assess the mechanism's performance by measuring its regret relative to the oflline optimal:
Ry M) =
E Protocal
Σ (UE o2.c))
(3)
where the expectation is over the randomness in the mechanism, agent strategies, and value/cost realizations. This regret notion generalizes the one studied in the non-strategic setting of Balseiro et al. (2023), where agents report truthfully (i.e., π = TRUTH such that uy = Ut, for all t and i). In that setting, their mechanism M achieved regret (TRUTH, MD) Ō Ö(vT). However, if agents are strategic, they may deviate from truthful reporting. In contrast, our mechanism in Algorithm guarantees the existence of Perfect Bayesian Equilibrium (PBE) strategy profile such that
agent benefits from unilateral deviation, and under which the regret remains O (TT) (Theorem 3.2).
'Two special cases of Assumption I are 0-impatient agents, who only care about their gains in the current round (often referred to as myopic agent), and 1 l-impatient agents, who care about their total gains over the entire T round game (as is typical in extensive- form games).

---

Algorithm 2 Primal-Dua -ual Mechanism Robust to Strategic Manipulations
Input: Number rounds T, agents K, resources d, cost constraint p e [0, 1] Epochs {E learning rates {n+}==1 regularizer V: IR - IR, sub-routine A
Output: Allocations 81 8....... ................................ êT, where & 0 denotes no allocation
1: Define dual region A = {X E R '3 E [0. P,
2: for epoch f 1, 2, ..... L do Update dual variable Ae E A via the sub-routine A: A A(e. ne. V. for each round & & do
3:
4:
5:
Each agent [K] observes their value Ut, ~ V/ and costs C₁ C
6:
Agent reports U4, E [0, 1] according to Protocol 1; u, and become public. if round is selected for exploration (w.p. 1/|Ee] independently) then
7:
8:
Sample tentative agent i ~ [nif((K) and payment p ~ Unif((0, 1))
9:
u 2 p. set & i and Pr,se p. Otherwise, set i
10:
else
11:
Compute adjusted cost टt, = X Ct.i and adjusted report Ue == WeTi Tr Vi E [K] Allocate to agent i == arg max; Uess with payment Pt, = Cr... + maxjji We.j cost constraint is violated: Σạ<t Ca.,, + Ct.. I Tp then Reject allocation by setting 0
12:
13:
14:
In parallel, the planner also aims minimize constraint violations, which we define
By T (T) ==
| (cr. - p))
(4)
Protocul
where (.)+ is the coordinate-wee wise maximum with zero, i.e., 2+ == [max(x;; O) 14.. Our mechanism M, presented Algorithm 2, guarantees BT(T, M) = 0; that is, cost constraints are satisfied.
We conclude this section with smoothness assumption cost distributions. The idea is to ensure that projected costs (linear combinations of the cost vector) do not place excessive probability mass on any single value. This smoothness condition prevents pathological behaviors where small change in an agent's ' report could drastically alter outcomes due to spiky distributions. Such assumptions common in strategic settings ensure robustness to perturbations, including in bilateral trades (Cesa-Bi BiancB et al., 2024a), first-price auctions (Cesa-Bianchi et al., 2024b), second-price auctions with reserves (Golrezaei al., 2021a), and smoothed revenue maximization (Durvasula et al., 2023).
Assumption 3 (Smooth Costs). For any agent E [K]. the cost distribution C, satisfies the following: for all X E A := (X Edd > E p0, 13, the density of the projected cost PDF c.--C, (A T c.) is uniformly bounded above by some universal constant c > 0. We do not assume this c. to be known.
3 Primal-Dual Mechanism Robust to Strategic Manipulation
We introduce incentive-awand primal-dual mechanism, Algorithm 2, which overcomes the fragility of standard primal-dur methods to strategic agents. As demonstrated in Figure 1, vanilla primal-dus methods allow agents to manipulate future dual updates by misreporting, leading misaligned incentives and degraded performance. Our mechanism addresses this challenge through three key innovations: epoch-based lazy dual updates, dual-adjusted allocation and payments, and randomized exploration rounds, which we describe below before presenting the algorithm and its guarantees.
Spoch-Based Lazy Updates. We divide the game horizon [I'] into L epochs [T]] E .... U and fix a single dual variable X₂ within each epoch &,. These dual variables act as implicit prices on resource consumption and adjust reported values accordingly. By holding A constant within each epoch, we reduce agents' ability to manipulate future allocations through misreports. This "lazy update" scheme is central ingredient in limiting intertemporal strategic behavior.
Dual-A djusted Allocation and Payments. each round E [T], agents submit reports based on their private values and observed costs. With high probability, the mechanism enters a standard round, allocating the resource the agent with the highest dual-adjusted report (reported value minus dual- weightee cost), and charging them their cost plus the second -highst dual-adjusted report.
5

---

Algorithm 3 Dual Update Sub-Routine using Selloo-the-Regulrizzete
(FTRL)
Input: Current epoch number lcarning rate Ne > 0, regularizer Vr: RS + R
I: Solve the following optimization problem for Ar E A and return Ae-
Σ E( (p,r)))) ) A 1 ((A).
A = argmin AEA EEET
(5)
Algorithm 4 Dual Update Sub-Routine using Optimistic FTRL with Fixed Points (O-FTRL-FP)
Input: Current epoch number é, learning rate лe > 0, regularizer wr R2 + R I: Solve the following fixed point problem for (Ae,ge) E A x R and return Ac.
X = argmin Σ Σ (p- (-,,,,,) (((()))) DEA PEtTEE
++ 1 ((A),
T
9: (Ac) E1d Eectlel Eel
e'clTEEy
(Ac) = argmaa
(ur, (ur, -eers)) AP <li E
(6)
[E[K]
This payment rule, inspired by boosted recond-price auctions (Golrezaei et al., 2021b), is incentive- compatible static (one-shot) settings and encourages truthful reporting in our dynamic setup. If the allocation would violate the cumulative cost constraint, it is rejected to ensure feasibility.
Randomized Exploration Rounds. With small probability, the mechanism initiates an exploration round, offering random price to a randomly selected agent. This structure penalizes misreports by imposing a direct utility loss when the reported value deviates from the true value (see Theorem 4.2). These rounds act incentive-compatibe signal extractors and are essential for maintaining the accuracy of dual updates based on strategic reports. The idea of randomized pricing has been explored in repeated second- accond-price auctions (Amin al., 2013; Golrezaei et al., 2021a, 2023), but to our knowledge, our work is the first to leverage it for robust primal- dual learning.
Dual Updates via Online Learning. In the beginning of each epoch, the planner updates the dual variable AS via an online learning approach. Equipped with BeeowwtheRReguaaiiee Leader (FTRL), we prove (12333 is attainable; however, the epoch- structure also poses an (2T22/3 online learning barrier (Theorem 4.4). To go beyond the ( regret of FTRL, we leverage the near- truthfulness induced by our mechanism to make predictions about future behavior. Our Optimistic FTRL with Fixed Points (O-FTRL-FP) augments classical FTRL with a forward-lookie term that estimates how the current dual variable X; would perform if agent behavior remains consistent.
Specifically, O-FTRL-FP solves fixed-point problem: it chooses A to minimize a combination of past constraint violations (p C,,,,) X, prediction term ge (Xe) X based on simulated
allocations using prior reports, and regularization term ( Since ge (Ax) itself depends on Ae. the
7//
optimization forms a self-consistent loop. We show that this method achieves Ö(VT) regret while maintaining feasibility and incentive alignment.
Main Results. We now state our two main theoretical guarantees, corresponding to different dual update strategies. Full formal statements and proofs are provided in Appendix B.
Theorem 3.1 (Algorithm 2 with FTRL). Under appropriate choice of epoch lengths and learning rates, Algorithm 2 using FTRL in Eq. (5) as the dual dual-update sub-routine A guarantees the existence of PBE π such that Ry( ( Algorithhm 2) = ((T2/3) and (Algorithh 2)
Theorem 3.2 (Algorithm 2 with O-FTRL-FP). Under appropriate choice of epoch lengths and learning rates, Algorithm 2 using O-FTRL-FP Eq. (6) as the dual-update sub-routine guarantees A
the existence of PBE π such that Ry (T"" .Algorithm 2) = O(VT) and BT .Algorithm 2)
Remarkably, Arlotto and Gurvich (2019) proved that even when agents are non-strategic, with unknown value and cost distributions, it is unavoidable to suffer Q (((TT) social welfare regret in the worst case. Therefore, our mechanism while additionally being robust strategic agents matches this lower bound when focusing on poly(T") dependencies.

---

4 Analysis Sketch of Theorems 3.1 and 3.2
The safety property of Algorithm 2, namely that By = 0, follows directly from Line 14. Thus, we focus on analyzing the regret Ry = [ E²= (vt,17 - -v,,,) which measures the expected difference between our allocation {ir herry and the offline optimal allocation {iz Jeeryy defined in Eq. (2). To help control this regret, we introduce intermediate allocation that maximizes the dual-adjusted values (rather than the actual allocation i maximizing dual-adjusted reports, which may be strategic);
? :- argmax (vr, Mens) <E(K]
vl [L], &
Define a stopping time To minst [T] E-= Cr. +1 1 Tp) (T as the last round where it is impossible for Line 14 to reject it We decompose the regret Ry as
To
Rx E
Σ (oL vese)
SE
PRIMALALLOC
DUALVAR
4.1 Misallocations Due to Agents' Strategic Behavior (PRIMALALLOOC)
As discussed in Section 3, agents' strategic reports in epoch can influence future dual variables Ae+1. which in turn affect subsequent allocations potentially creating feedback loops that lead to misallocation. We give example of this scenario:
Example 4 (Agents are able to strategically affect X4t1). Consider two agents with identical value distributions, i.e., V1 = V/2 Suppose the cost vectors are fixed as Ct e, for all t and i, and the cost budget is p 1122, If both agents report truthfully during epoch &,, the resource is allocated approximately equally. As a result, the dual vector X2, computed via Eq. (6), has similar values across its coordinates. However, suppose that agent I strategically under-reports their value throughout epoch 1, causing all allocations to go to agent (i.e., it = 2 for all I E E1). This skews the observed cost consumption toward the second type, causing 22,2 >> 22,1. Consequently, agent 2 whose actions incur the second cost type- will face significantly higher penalties in future epochs.
To understand this effect, decompose the total inefficiency due to agents' strategic behavior, namely the PRIMALALLLOC in Eq. (7), into two parts: (i) INTRAEPOCH measuring misallocations arisen due agents' incentives for immediate short-term gains, and (öi INTEREPOCH measuring misallocations caused by agents influencing dual updates for future-epoch benefits. To isolate them, we introduce two behavioral models for agents, where Model I exactly Assumption 1:
T Σ (vra -P.. 1) Model 2: max E
Model 1: max E
Σ rEE..22
(vra -.r.- =1] (8)
Model 2 essentially assumes agents only optimize over the current epoch &,, ignoring long-term impact. Let (it hE([] be the allocations that would occur under Algorithm if agents followed Model 2. Our goal is to first analyze this hypothetical setting to understand EPOCH, then examine the deviation introduced by agents following the realistic Model 1, which leads to INTEREPOCI effects.
4.1.1 INTRAEPOCH: Misalignment Within Epochs
Under Model 2, each epoch & E [Z] can be treated independently, which we call an "epoch-& game". The planner selects allocations to maximize the total adjl-adjested value Eies, Ve, where
Vt,; Ut,i AJ Ct, In contrast, agents care about their true value Ut,; rather than the aual-adjusted objective. This introduces mismatch between the planner's and agents' optimization criteria. Despite this mismatch, we show that our mechanism's 's dual- dual-adjusted allocation rule in Line 12 incentivizes truthful reporting within each epoch:
Theorem 4.1 (INTRAEPOCII Guarantee; Informal Theorem C.2). In the epoch-l game under Model 2. the allocation rule th arg max; Ut,s with payment Pt. = XTC, o + 2nd-highest We, ensures that truthful reporting is PBE. Under this equilibrium, [[[TTRAPPOCH]] = 0.
7

---

4.1.2 INTEREPOCH: Strategic Manipulation of Future Duals
We now return to Model I, where agents optimize over the entire horizon t E (T). In this setting, an agent can misreport the current epoch to influence the next epoch's dual variable A thereby improving their chances of allocation in future rounds. This creates new avenue for strategic behavior that was not captured under Model 2.
To mitigate this, our mechanism introduces randomized exploration rounds, which penalize deviations from truthful reporting through stochastic pricing: Reporting Ut,i > vt, means paying a price higher than value when p E (Ve,s, ut,²): reporting Ue, < ot, means missing an opportunity to make profits when p E (Ma,s, u4,s). These rounds by ensuring misreports carry immediate utility losses that do not outweigh the future gains reduce agents' willingness to manipulate dual updates.
Theorem 4.2 (PRIMALALLOC Guarantee; Informal Theorem C.5). There exists a PBE nt" such that I for any epoch E [L], the number of round-agent (t, ip-pirss where |ue,i ve,il 2 Eel is O(1) with high probability: That is, agent reports under Models and rarely differ. Moreover, the resulting allocations {&t and {&t hee, differ in at most (1) rounds with high probability. Consequently, this equilibrium ensures E|PRIMALALLOC] Ö()).
4.2 Inaccurate Dual Variables Due to Incomplete Information (DUALVAR)
The second source of inefficiency comes from sub- sub-optimal dual variables or more precisely, the gap between the dual-adjusted allocation ū == arg max; (Ut.i Cec,,) that our mechanism maximizes and the offline optimal benchmark E defined Eq. (2) - which call DUALVAR in Eq. (7).
4.2.1 Translating DUALVAR to Online Learning Regret
Using primal-dual analysis similar to that of Balseiro et al. (2023), we relate this gap the online learning regret over dual variables Å1 A År. E A (where A == (> E Rd: >3 E [0, pj is chosen such that Pj e E A for all j E [d]) as follows, which an informal version of Lemma D.1:
Lemma 4.3 (AUALVAR as Online Learning Regret). Let argmax, (", 1.kxx-Jaa. ([css) denote the best allocation under dual prices and it denote the offline optimal benchmark. Then,
T
To
DUALLVAR =
E
sup A t=1 11E
(p casi)) - x²) + +T....
t=1
That is, VARL reduces to an online learning problem where the planner selects a dual vector As E A at the beginning of each epoch l and incurs linear loss based on constraint violations of (ir)e Specifically, the loss function in epoch is given by Fe(A) = Σ. (p Ct.i,) ) X.
4.2.2 Achievements and Limitations of FTRL
Using FTRL, the planner selects de by minimizing a regularized sum of historical losses, namely (A) where Yi is strongly convex regularizer. This choice
A, = argminxe^ Erer Fg (A) + Tie
yields regret Rे δ (v VE L
P).. Choosing L = 1/3 epochs each of size 2/33 minimizes
_ + L, giving total regret (T3) shown in Theorem 3.
However, vanilla FTRL fundamentally limited due to epoch-based structures: Frequent updates to A would enable faster learning, but break incentive compatibility. Conversely, fewer updates protect incentives, but slow learning. This tradeoff formalized in the following hardness result:
Theorem 4.4 (Hardness for -ow-swithhing Online Learning (Dekel al., 2014)). Consider an online learning algorithm that guarantees regrer 2े = O(T") for some a E [1/2, 1). Then, it must switch decisions at least (1(T2()))) times. In our setting, this means that the number of dual updates - i.e., the number of epochs L - must satisfy L (1-)2) This infers that the R + L term in Lemma 4.3 suffers worst-case bound of Z (min.e(1/2.1) T (())-oo) = 2/32/33)

---

Dual-optimal allocations (it) (Lid. given Ar)
Hypothetical alloca- tions {sr (myopic agenis under Model 2)
4.2
Actual allocations [6] (strategic agents under Model 1)
Figure 2: From dual-optimal to actual allocations: fixing dual X mechanism ensures that the actual allocations {& closely follow the dual-optimal {27} via intermediate myopic model { }.
4.2.3 Exploiting Incentive Alignments for Boosted Regret
The hardness result in Theorem 4.4 applies to the worst-case senario, i.e., when the loss functions Fi, F2. ..... F2 can be any arbitrary linear functions. But in our setting, due to the incentive- compatible primal allocations (Theorems 4.1 and 4.2), the loss Fe(A) has an almost-i..d structure:
Claim 4.5 (Loss Structure; Informal), Fix any Xe E A. Then for all but O(1) rounds epoch & the actual allocations in match the dual- autaloptimal choices i = arg max; (Vr, - XJ ct,i). Thus,
VxFe(A)=
E(e c,ss)) BEE2
E(p- G,5g),
REE
which behaves is the sum of EE] i.i.d. samples and thus has variance of order ((EE)).
Proof Idea. To understand how our mechanism enables accurate dual updates despite incomplete information and strategic behavior, we illustrate in Figure 2 the connection between three key allocation sequences within fixed epoch. First, the sequence {iž } represents the dual-optimal allocations computed in hindsight, assuming access to true valuations and a fixed dual vector Ag- Second, { denotes the hypothetical allocations made under Model 2, where agents are myopic and only optimize within single epoch. By Theorem 4.1, these allocations align with (ip} } under our cocemtive-oomptibbe subroutine. Lastly, the actual sequence } generated by strategic agents under Model 1, is shown to be close to {it') } via Theorem 4.2. Together, these approximations establish that { behaves almost like an i.i.d. sample from the dual-adjusted best responses.
This low-variance structure is essential for achieving Õ(vT) regret. In general, linear losses with gradients of norm ((Eg)) can have variances as large as ((EE) which explains the 22/3 regret scaling of FTRL in Theorem 3.1 and the lower bound in Theorem 4.4. Even more importantly, because this near-i.idd structure holds across previous epochs well, it enables us to accurately estimate losses associated with new dual choices using only historical data without requiring access to agents' true values or distributions. These two insights provides predictability ahead of time, which enables the application optimistic online learning algorithms, for example, Optimistic FTRL (O-FFF (O-FTRL) by Rakhlin and Sridharan (2013). O-FTRL ensures that if the actual loss Fe is well-predieted by some predicted loss Fe, such that the expected squared error in gradients of order Ö(Eee), then one can break the (T2333 regret barrier and attain ((VT) performance (Lemma E.2).
4.2.4 Resolving Circular Dependencies between Actions and Predictions
The final issue stopping us from obtaining Theorem 3.2 is that, O-FTRI. framework requires to construct the predicted loss F(( before deciding action Xg; however, in case, recall that
Pe(A) (- c >,, where i, is the primal allocation given dual Açe
BE
In words, to construct good (A) R Fr(A) and decide A we need to know A first because Fz(A) depends on Ae. This circular dependency between action A and prediction Fe(A) stops from applying O-FTRL, circumvent this issue, we instead allow the prediction to have form Fr(): Xe) such that Fe(:; Ax) 2 Fe(-) if we really chose X as our action for epoch é and decide the action via a fixed point problem (as in Eq. (6)). We call this novel online learning algorithm Optimistic FTRL with Fixed Points (O-FTRL-FP in short). In Lemma D.4, we prove that if a small perturbation in Xe docsn't It change F. Xe) by a lot, O-FTRL-FP always admits approximate fixed point.

---

To get the Ö(VT) social welfare regret claimed in Theorem 3.2, it only remains to i) verify our Fg in Eq. (6) indeed makes Lemma D.4 applicable; ii) show that Fe - Ae: despite agents' misreports in the current epoch &,, the statistical barrier in reconstructing ((V. and agents' historical misreports; and iii) properly tune all hyper-parameters, Due to space limitations, these steps are deferred to Theorem D.3 in the appendix.
((E)))
5 Numerical Study
Basic Setup. We simulate a game with T = 1000 rounds, K = 3 agents, a single resource dimension 1, and discount factor y = 0.9. Each agent's ' valuation is drawn from V; = Unif(0, 1]. and their cost is drawn from C, = Unif[0.7p. 1.3p], for all i = 1, 2.
Agents' Model. To reflect agents' strategic behaviors, we assume that every agent i 2, 3 models the game as Markov Decision Process (MDP) with state defined as (f, A vt,4) - i.e. round number t, current dual variable A, and their own private value Ur. and the action defined as We,s. The reward for agent after playing report We, is 7" the values, duals, and reports to the nearest multiple of 0.1. We repeat the same game for N = 1000 independent trails, where every agent keeps refining their strategy via Q-learning (Watkins and Dayan, 1992). In the re-h trial, every agent uses en -greedy with a geometrically decaying schedule of 0.995". We update Q-tables using Q(s, a) & Q(s, a) + a(r + (maxxa Q(s', a') Q(s,a)) where a = 0.1, r' is the instantaneous reward, and s' is the new state (t + 1, A,11 0t+1,1).
pt,,) 1 [ = i] in Assumption 1. We discretize all
The vanilla primal-dual algorithm we use is Algorithm of Balseiro et al. (2023), which ensures constraint satisfaction by rejecting any allocation that would violate the budget. When implementing the O-FTRL-FP update rule in Eq. (6), instead of solving the fixed-point problem
Mechanisms.
A = (-.. (g: _> A + "(A)), ). we solve argming (... - (A) x+
ne v(A) for numerical
simplicity. The validity of this approximation is due to Lemma D.5, which says A\1, A2 E A s.t. [A -22l11 (x,) (A2) w.h.p. Thus the two objectives agree locally around the true Ae-
Results. Figure demonstrates that our mechanism significantly outperforms the standard primal- dual method in the presence of strategic agents, both adhering to cost constraints. Under the primal- dual approach of Balseiro et al. (2023, Algorithm 1) which plotted blue, agents systematically over-report their valuations (left), hurting the overall social welfare (middle), and resulting in lower budget utilization when agents submit similar reports, the impact of cost minimization amplified (right). In contrast, our mechanism equipped with O-FTRL-FP (in green) incentivizes near-truthful reporting, as shown by the alignment between reported and true values, resulting in a substantial increase in long-term social welfare. These findings highlight the fragility of standard primal-dual methods in strategic settings and the robustness of our proposed incentive-awarc mechanism.
Computational Resources. Every illustration executes on a M1 MacBook Air 2020 in 10 minutes.
6 Conclusion and Future Directions
This paper investigates the dynamic allocation of reusable resources to strategic agents under multi- dimensional long-term cost constraints. We show that standard primal-dual methods, though effective in non-strategic settings, vulnerable manipulation when agents act strategically. To address this, we introduce novel incentive-aware mechanism that stabilizes dual updates via an epoch-basee structure and leverages randomized exploration rounds to extract truthful signals. Equipped with computationally efficient FTRL dual update rule, our mechanism guarantees sublinear regret with respect to offline benchmark, satisfies all cost constraints, and admits PBE; further leveraging a novel O-FTRL-FP framework for dual updates, we boost the regret to ((VT) which is near- optimal even in non-strategic constrained dynamic resource allocation settings. Looking ahead, several promising research directions remain open. For example, while our mechanism uses monetary transfers to ensure incentive compatibility, many real-world applications, e.g., organ matching, school admissions, or vaccine distribution, operate under non-mon monetary constraints. Extending our framework to such settings is important step toward more broadly applicable mechanism design.
"Since mechanism M is public and every agent knows every information the planner has, ie.. H4,0 S He,s. agents are able calculate d their end.
10

---

Acknowledgements
P.J. and Y.D. are partially funded by the Office of Naval Research (ONR) under Award ID N00014- 24-1-2470. N.G. and Y.D. are partially supported by the MIT Junior Faculty Research Assistance Grant and by the Office of Naval Research (ONR) under Award ID N00014-23-1-2584, The authors thank the anonymous reviewers for their constructive feedback.
References
Ivo Adan, Jos Bekkers, Nico Dellaert, Jan Vissers, and Xiaoting Yu. Patient mix optimisation and stochastic resource requirements: A case study in cardiothoracic surgery planning. Health care management science, 12:129-141, 2009.
Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A dynamic near-optimal algorithm for online linear programming. Operations Research, 62(())876-88)) 2014.
Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Learning prices for repeated auctions with strategic buyers. Advances in neural information processing systems, 26, 2013.
Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Repeated contextual auctions with strategic buyers. Advances in Neural Information Processing Systems, 27, 2014.
Alessandro Arlotto and Itai Gurvich. Uniformly bounded regret in the multisccretary problem. Stochastic Systems, 9(3):231-266 2019.
Kenneth Arrow. difficulty in the concept of social welfare. Journal of political economy, 58(4): 328-346 1950.
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. Journal of the ACM (JACM), 65(3):1-55, 2018.
Santiago Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Regret minimiza- tion and equilibrium. Management Science, 650))339523398, 2019.
Santiago Balseiro, Huseyin Gurkan, and Peng Sun. Multiagent mechanism design without money. Operations Research, 67(5):1417-1436, 2019.
Santiago R Balseiro, Haihao Lu, and Vahab Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. Operations Research, 71(1):101-119, 2023.
Siddhartha Banerjee, Giannis Fikioris, and Eva Tardos. Robust psrudo-markets for reusable public resources. Proceedings of the 24th ACM Conference on Economics and Computation, pages 241-241, 2023.
Damien Berriaud, Ezzat Elokda, Devansh Jalota, Emilio Frazzoli, Marco Pavone, and Florian Dörfler. To spend or to gain: Online learning in repeated karma auctions. arXiv preprint arXiv:2403.04057, 2024.
Dimitri Bertsekas, Angelia Nedic, and Asuman Ozdaglar. Convex analysis and optimization, volume 1. Athena Scientific, 2003.
Moise Blanchard and Patrick Jaillet. Near-optimal mechanisms for resource allocation without monetary transfers. arXiv preprint arXiv:2408. 00044088.0006. 10066, 2024.
Rajkumar Buyya, Chee Shin Yeo, and Srikumar Venugopal. Market-oriented cloud computing: Vision, hype. and reality for delivering it services as computing utilities. In 2008 10th IEEE international conference on high performance computing and commumications, pages 5-13. Icee. 2008.
Matteo Castiglioni, Andrea Celli, and Christian Kroer. Online learning with knapsacks: the best of both worlds. In International Conference Machine Learning, pages 2767-2783, PMLR, 2022.
11

---

Nicolò Cesa- Basa-Bianchi, Tommaso Cesari. Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Regret analysis of bilateral trade with a smoothed adversary. Journal of Machine Learning Research, 25(23))11-36, 2024a.
Nicolò Cesa- Besa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. The role of transparency in repeated first-price auctions with unknown valuations. Proceedings of the 56th Annual ACM Symposium on Theory of Compuling, pages 223-236, 2024b.
Edward H Clarke. Multipart pricing of public goods. Public choice, pages 17-33, 1971.
Richard Cole, Vasilis Gkatzelis, and Gagan Goel. Positive results for mechanism design without money. In Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems, pages 166--116, 2013.
Yan Dai, Moise Blanchard, and Patrick Jaillet. Non- Non- monetary mechanism design without distribu- tional information: Using scarce audits wisely. arXiv preprint (tt.::25520.84422,, 2025.
Ofer Dekel, Jian Ding, Tomer Koren, and Yuval Peres. Bandits with switching costs: T 2/3 regret. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 459-467, 2014.
Nikhil R Devanur and Thomas Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce, pages 71-78, 2009.
Nikhil R Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A Wilkens. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Journal of the ACM (JACM), 66 66(1):1-41 2019.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Naveen Durvasula, Nika Haghtalab, and Manolis Zampetakis. Smoothed analysis of online non- parametrie auctions. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 540-560, 2023.
Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S Mirrokni, and Cliff Stein. Online stochastic packing applied to display ad allocation. In European Symposium on Algorithmss, pages 182-194. Springer, 2010.
Giannis Fikioris, Siddhartha Banerjee, and Éva Tardos. Online resource sharing via dynamic max-min fairness: efficiency, robustness and non-stationarity. arXiv preprint arXiv:23 10.022310.0881,, 2023.
Rigel Galgana and Negin Golrezaei. Learning in repeated multiunit pay-as-bid auctions. Manufactur- ing& & Service Operations Management, 27(1):200-25) 2025.
A. Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41(())5877601, 1973.
Negin Golrezaci, Hamid Nazerzadeh, and Paat Rusmevichientong. Real-time optimization of personalized assortments. Management Science, 6036)1153-1 2014.
Negin Golrezaei, Patrick Jaillet, and Jason Cheuk Nam Liang. No-regret learning in price competitions under consumer reference effects. Advances in Neural Information Processing Systems, 33:21416- 21427, 2020.
Negin Golrezaei, Adel Javanmard, and Vahab Mirrokni. Dynamic incentive-aware learning:: Robust pricing in contextual auctions. Operations Research, 69(1):297-314, 2021a.
Negin Golrezaei, Max Lin, Vahab Mirrokni, and Hamid Nazerzadeh. Boosted second price auctions: Revenue optimization for heterogeneous bidders. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pages 447-457, 2021b.
Negin Golrezaei, Patrick Jaillet, and Jason Cheuk Nam Liang. Incentive-aware contextual pricing with non-parametric market noise. In International Conference on Artificial Intelligence and Statistics, pages 9331-9361. PMLR, 2023.
12

---

Artur Gorokh, Siddhartha Banerjee, and Krishnamurthy Iyer. The remarkable robustness of the re- peated fisher market. In Proceedings of the 22nd ACM Conference on Economics and Computation. pages 562-562, 2021a. 2021a.
Artur Gorokh, Siddhartha Banerjee, and Krishnamurthy Iyer. From monetary nonmonetary mechanism design via artificial currencies. Mathematics of Operations Research, 46(3):835-88) -55, 2021b.
Theodore Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, pages 617-631, 1973.
Mingyu Guo and Vincent Conitzer. Strategy-prost allocation multiple items between two agents without payments priors. In AAMAS, pages 881-888, 2010.
Anupam Gupta and Marco Molinaro. How the experts algorithm can help solve Ips online. Mathe- matics of Operations Research, 41( 1404:11444 2016.
Li Han, Chunzhi Su, Linpeng Tang. and Hongyang Zhang. On strategy-proof allocation without payments or priors. In International Workshop on Internet and Network Economics, pages 182-193. Springer, 2011.
Devansh Jalota, Matthew Tsao, and Marco Pavone. Catch me if you can: Combatting fraud in artificial currency based government benefits programs. arXiv preprini wrXi::2402.1616. 2024.
Yash Kanoria and Hamid Nazerzadeh. Dynamic reserve prices for repeated auctions: Learning from bids. In Web and Internet Economics: 10th International Conference, volume 8877, page 232.
Springer, 2014.
Thomas Kesselheim, Klaus Radke, Andreas Tonnis, and Berthold Vocking. Primal beats dual on online packing Ips in the random-order model. SIAM Journal on Computing, 47(5):1939-199) 1964, 2018.
Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled cubic regularization for non-convex opti- mization. In International Conference on Machine Learning, pages 1895-1904. PMLR, 2017.
Christos Koufogiannakis and Neal E Young. A nearly linear-time ptas for explicit fractional packing and covering linear programs. Algorithmica, 70:648-674 2014.
Xiaocheng Li, Chunlin Sun, and Yinyu Ye. Simple and fast algorithm for binary integer and online linear programming. Mathematical Programming, 200(2):831-85,, 2023.
Antonio Miralles. Cardinal bayesian allocation mechanisms without transfers. Journal of Economic Theory, 147(1):179-28) 2012.
Marco Molinaro and Ramamoorthi Ravi. The geometry of online packing linear programs. Mathe- matics of Operations Research, 39(1):46-59, 2014.
J.R. Munkres. Topology. Featured Titles for Topology. Prentice Hall, Incorporated, 2000. ISBN 9780131816299. httttttss://boos google comm///okkss/EE-Xo22AAAAAAAAA.
Mahyar Movahed Nejad, Lena Mashayekhy, and Daniel Grosu. Truthful greedy mechanisms for dynamic virtual machine provisioning and allocation clouds. IEEE transactions on parallel and distributed systems, 26(2):594-603, 2014.
Francesco Orabona. A modern introduction online learning. arXiv preprint arXiv:1912.1321: 2019.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993-1019. PMLR, 2013.
N.A. Satterthwaite. Strategy and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10(2): 187-217, 1975.
13

---

Christian Stummer, Karl Doerner, Axel Focke, and Kurt Heidenberger. Determining location and size of medical departments hospital network: A multiobjective decision support approach. Health care management science, 7:63-71, 2004.
Rui Sun, Xinshang Wang, and Zijie Zhou. Near-optimal primal-dual algorithms for quantity- network revenue management. arXiv preprint arXiv:2011.06337/ 2020.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8-3 37, 1961.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8:279-292, 1992.
David Williams, Probability with martingales. Cambridge university press. 1991.
Zongjun Yang, Luofeng Liao, Yuan Gao, and Christian Kroer. Online fair allocation with best-of- many-worlds guarantees. arXiv preprint arXiv:2408.0244 2024.
Steven Yin, Shipra Agrawal, and Assaf Zeevi Online allocation and learning in the presence of strategic agents. Advances in Neural Information Processing Systems, 35:6333-6344 6344, 2022.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In Figure 1, we illustrated the fragility of primal-dual framework to agents' strategic behaviors. In Theorems 3.1 and 3.2 (with formal versions appearing as Theorems B. and B.2), prove the claimed performance guarantee of our proposed mechanism in Algorithm 2.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals motivation long it is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification:
All assumptions clearly stated. These limitations discussed in the Conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification,
asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will specifically instructed to not penalize honesty concerning limitations.
Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Our main claims, Theorems 3.1 and 3.2, have their sketched proofs in Section 4 and their full proofs in Appendices B to D.
Guidelines:
15

---

The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The numerical illustration setup is clearly explained in Section 5, with codes attached as supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility can also provided via detailed instructions for how to replicate the results, access to a hosted model (c.g.. in the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
example, the contribution
While NeurIPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-soure dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited some way (e.g.. registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The code used for simulation is attached in the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
16

---

Please see the NeurIPS code and data submission guidelines https////iipsccppuliii.pooo Saaeee//CooSuumissseeee soioiooicyyy for more details.
While we encourage the release code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https http://pps..pcpuiiiiie///// Saadeee/oodSSumii wwwssssssiliooooooooooooooooooii cy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide seripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reprodueible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended. but including URLs to data and code is permitted.
Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: They are described in Section 5. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material. Experiment statistical significance
Question: Does the paper report eπror bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The claim regarding agents' truth-reporting, egg., the first plot in Figure 1, is plotted using repeated sampling and error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of eтrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments compute resources
17

---

Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory. time of execution) needed reproduce the experi-
ments?
Answer: [Yes]
Justification: See Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
Code of ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //terri/////pp.../ee httpp//icc/tttcccccccciieeeeeeee
Question:
Answer: [Yes]
Justification: Work of purely theoretical nature.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., if there a special consideration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Work of purely theoretical nature.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied par- ticular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point out. For example, an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
legitimate to point that
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative socictal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI).
11. Safeguards
18

---

Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g.. pretrained language models, image generators. or scraped datasets)?
Question:
Answer: [NA]
Justification: Work of purely theoretical nature.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled to usage guidelines or restrictions to access the model or implementing safety filters.
of the model, for example by requiring that users adhere
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: In our numerical illustrations, we reproduced the algorithm designed by Balseiro al. (2023) with proper citations.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets released.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/modell as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
19

---

Answer:
[NA]
Justification:
No crowdsourcing and research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human
subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (TRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing and research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non- standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: Work of purely theoretical nature without LLM involvement.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer our LLM policy (https://neutl) cc/ LC/C/ for what should or should not be described.
20

---

Appendices
More Discussions on Related Work
21
Proof of Main Theorems
22
B.1 Main Theorem for Algorithm 2 with FTRL
22
B.2 Main Theorem for Algorithm 2 with O-FTRL-FP
24
C PRIMALALLOC:: Regret due to Agents' Strategic Reports
26
C.1 INTRAEPOCH: Agents Lie Affect Current-Epoch Allocations
C.2 INTEREPOCH: Agents Lie to Affect Next-Epoch Dual Variables
27
DUALVAR: Regret due to Primal-Dual Framework
D.1 DUALVAR and Online Learning Regret
31
D.2
DUAL.VR Guarantee for FTRL in Eq. (5)
D.3
DUALVAR Guarantee for O-FTRL-FP in Eq. (6)
36
D33.1
O-FTRL-FP Framework for Non-Continuous Predictions
40
D.3.2
Approximate Continuity of Predictions in O-FTRL-FP
43
D.3.3
Stability Term Bounds in O-FTRL-FP
44
Auxiliary Lemmas
49
A More Discussions on Related Work
Dynamic Resource Allocation with Non-Strategic Agents. With non-strategic agents, dynamic resource allocation, or more generally, online linear programming, was first studied under the random permutation model where adversary selects set of requests that presented in random order (Devanur and Hayes, 2009; Feldman et al., 2010; Gupta and Molinaro, 2016), which is more general than our i.idd. model where all values and costs identically distributed. For the ii.d. model, various primal-dual -unaal-dallbased algorithms were proposed with the main focus of refining computational efficiency (Agrawal al., 2014; Devanur et al., 2019; Kesselheim et al., 2018; Li al., 2023); specifically, Li et al. (2023) proposed fast O (er-rgrrtt reegret algorithm for the online linear programming problem, which matches the ((TT/22) online resource allocation lower bound (Arlotto and Gurvich, 2019).
Recent progress on this problem includes 1/2 regret with known distributions (Sun et al., 2020) or better robustness and adaptivity to adversarial corruptions (Balseiro al., 2023; Yang al., 2024). Another closely related problem is Bandits with Knapsacks (BwK), where the planner makes allocations without observing the values or costs in advance but only learns via post-decision feedback (Badanidiyuru et al., 8018; Castiglioni et al., 2022). Nevertheless, none of them considers strategic behaviors of the agents but assume the values and costs are fully truthful. contrast, our main focus is to be robust to agents' strategic behaviors while remaining efficient and obcying all the constraints.
Dynamic Resource Allocation with Strategic Agents. When agents are strategic, ensuring both efficiency and dncentive-coppatibne provide foundation for static truthful allocation with monetary transfers. static (one-shot) allocations when money can be redistributed, the celebrated VCG mechanism (Vickrey. 1961; Clarke, 1971; Groves, 1973) provides foundation way to achieve both. We study the repeated setup where money can only be charged but not redistributed, the so-called "money-burning" setup. A related problem is learning prices in repeated auctions (Amin et al., 2013, 2014; Kanoria and Nazerzadeh, 2014; Golrezaei et al., 2021a, 2023). These works focus on a seller learning prices to maximize revenue where the agents strategically react to these prices, sometimes
21

---

subject to buyer's ss budget constraints. In our work, we study the different social welfare maximization task and consider more general nulti-dimennional cost constraints.
We also briefly discuss the settings where monetary transfers are completely disallowed. In static setups,
is in general hard due to the Arrow's s impossibility theorem (Arrow, 1950; Gibbard, 1973; Satterthwaite, 1975), though some positive results exist under restricted as- sumptions (Miralles, 2012; Guo and Conitzer, 2010; Han al., 2011; Cole et al., 2013). Many recent efforts have been made to ensure efficiency and compatibility in repeated non-monetary allocations, which have very different setups from ours, for example when agents' value distributions are known (Balseiro et al., 2019; Gorokh et al.. 2021b; Blanchard and Jaillet, 2024), when a pre-detemmiee "fair share" is revealed to the planner (Gorokh al., 2021a; Yin et al., 2022; Banerjee al., 2023; Fikioris et al., 2023), or when the planner has extra power like audits (Jalota et al., 2024; Dai et al., 2025). We also remark that they either do not consider constraints or only have specific "fair share" constraint that we discuss later. In contrast, we consider general multi-dimensional constraints.
Multi-Agent Learning. While our planner learns for better allocation mechanisms, the agents are also learning in reaction to it (e.g., in our numerical illustration in Figure I, we consider agents who use Q-learning to learn the best reporting strategies under different dual variables). There is a rich literature investigating this dynamics as well, for example Balseiro and Gur (2019); Golrezaei et al. (2020): Berriaud et al. (2024); Galgana and Golrezaei (2025) studying the convergence to equilibria when multiple agents deploy no-regret online learning algorithms in reaction to some mechanism the same time. While such results are stronger than our existence of equilibrium results in the sense that agents find such an equilibrium on their own, we remark that the main focus of this work is designing robust mechanisms for the planner instead of designing learning algorithms for the agents.
Comparison with (Yin et al., 2022). Yin et al. (2022) also study the problem of ensuring efficiency and nucentivecooppatiility in the dynamic constrained resource allocation problem. The first critical difference is that they assume all the agents have identical value distributions, which is crucial for irrentvvecoompatiblig By comparing one agents' reports to all the opponents', unilateral deviation from TRUTH is easily caught and thus TRUTH is a PBE even without using monetary transfers. In contrast, we need more delicate algorithmic components, including epoch- bashd lazy updates, random exploration rounds, and dual-adjusted allocation and payment plans, to ensure the near- pear-truthfulnes of agents. Another main difference is the type of constraints. They study a specific "fair share" type resource constraint, which says given some E A(K)), the number of allocations that agent i receive should be roughly Tp, Vi E [K]. In contrast, our minti-dimeensooall long-teng constraint strictly more general than theirs, which can be written as E ei, S p in our language.
B Proof of Main Theorems
B.1 Main Theorem for Algorithm with FTRL
Theorem B.1 (Formal Version of Theorem 3.1: Algorithm 2 with FTRL). In Algorithm 2, let
-1/2
T ||p-1|1 ll2
L T-33 & (e (T + 1, "
Σ 1&1
V(A) = - 1112:
2d
and the sub-routine A chosen as FTRL (Eq. (5)). Then under Assumptions and 3, there exists PBE of agents" joint strategies under Algorithm 2, denoted by π such that
Ry(T"' Algorithmm 2 with Eq. (5))
< 2/3 4 4K2 +
1/3 Ell 5
log(1+ + 4(1 + 1 1/33333
+ /2dll="1la) + '11,
log--1
and Br(n", ,Agorrithm with Eq. (5)) 0.
Specifically, when only focusing on polynomial dependencies on d, K, and T, we have Ri (T'", Allorrithm 2 with Eq. (5)) = (0..,T((K2 + vdyr2/s),
By ( .Algorithm 2 with Eq. (5)) 0.
22

---

Proof. As mentioned in the main text, we introduce an intermediate allocation:
argmax (vr,i - c(.)) Ai [4], E &c. (E(K]
(9)
Define stopping time To as the last round where no constraint violations can happen:
Te = min E [T]
Σ
Crai + 112Tp)
U (T
(10)
r=1
Thus in rounds 1 < To Line 14 never rejects our allocation it. Decompose the regret Ry as
T
Ta
My = Σ
vesse)
S
E
Σ (0. - 43. (T - Tw)
PRIMALALLOC
DUALVAR
NOACT
From Theorem C.5 presented later in Appendix C, there exists PBE x such that
E PPRIMALALLOC $ (N₂ + 3),
N₁ =1 4K 111 + loggE + +1+ 4(1 (11+
This the first main technical contribution of our paper, namely justifyyng that Algorithm 2 equipped with epoch-based lazy updates, uniform exploration rounds, and dual-adjusted allocation and payment plans is robust to agents' strategic manipulations.
From Theorem D.2 presented later in Appendix D, when setting
-1/2
1|-
Σ
((A) = -
11 "e
E2l
V2d
and under the same n², the E[[UALVAR] term is bounded by
E[DUALVAR] S v '12a
Σ E&P - E(Ne
(Ne + 3-pp)ppp000 111 + 112-
Thus it only remains to balance the E/_1 N₂ = ((L) term and v Σl | term. Setting L = 22/3
and [Ee] 1/3 for all E [Z. ensures / V 2 VT2/3 T2/3 22/3 and thus
Rr(n", Algorithm with Eq. (5)) < PRIMALALLOC + (UUALVAR
(Ne + 3) + v2d 1|2 T2/3 Σ
(Ne + 3)1le -/ |p 1|1
Σ +N (1++ + 2d p 111 2233 + |
Plugging our specific epoching rule that L = 2/3 and [Egl 1/3 into Ne, we get
Σ (Ne (3)+3) (4 (4+483
(4+4K2colpp 4K<4 1/2 + 5 1/3 log(1 + 4(1 ||| 11-~1
log
which gives our claimed bound after rearrangement. For Br, since Line rejects every infeasible allocation, trivially have By(T", Algorithm 2 with Eq. (5)) = 0.
D
23

---

B.2 Main Theorem for Algorithm 2 with O-FTRL-FP
Theorem B.2 (Formal Version of Theorem 3.2: Algorithm 2 with O-FTRL-FP). In Algorithm 2, let
1/2
1|
L [log T,, & E 1 min((2 1,)) Me V112dk2
Σ EEl p==1
v())
2
and the sub-routine A chosen as O-FTRL-FP (Eq. (6)). Then under Assumptions I and 3, there exists
PBE of agents' joint strategies under Algorithm 2, denoted by TT', such that
Rr(
"rr(""Algooiitiee A.goorithm with Eq. (6))
|| + -d + 48d + 48d
dKeeTT
$ 2VT
log
+ 16d + 10
2
Tpj
(2N2 + () 1) 8dM?) + 3 111,,
and (T( Algorritmm 2 with Eq. (6)) = 0,
where N; and Me defined as follows for all { [L].
Ne- 1 + 4K e "I11 + Eog|E2 log,- 4(1 + llp ([1)))
4
dK2e.T
Mr flog.-1 (1 + 4(1 11)
46callp +4 log(dT) + Σ
log
Pge
f=1
Specifiially, when only focusing on polynomial dependencies on d, K, and I, we have (r Algorithm 2 with Eq. (6)) = O.. r (d +**), Br(m", Algorithm with Eq. (6)) 0.
Proof. The proof follows the same structure as the previous one, but the treatment of the DUDAALVRR) extremely challenging and requests delicate analytical tools; refer the readers to Theo- rem D.3 for more details. We still include full proof of this theorem for completeness.
As mentioned in the main text, introduce intermediate allocation:
= argmax (Vi,i - A.c..). Vl E [T], E &
<E(K)
Define stopping time T, as the last round where no constraint violations can happen:
To = min tE [T] Σ c.,. +1 T +
Thus in rounds t < Te, Line 14 never rejects our allocation it Decompose the regret Pt as
T
T
T.
Ry
Σ
(vr.
SE
E
(w. - Uz )+
Σ (ULa - + (T - To)
PRIMALALLOC
DUALVAR
NoACT
For the PRIMALALLOC term, we still use Theorem C.5 presented later in Appendix C (which holds regardless to the dual update rules). Theorem C.5 asserts that there exists a PBE nt such that
E/PRIMALALLOC S Σ (N₂ +3),
where
N: 1
4K2eollp 11pp-11111 5log|Ee + log (1 + 4(1 |pp - (11)))&
24

---

For the DUALVAR term, the O-FTRL-FP analysis is substantially harder. This is the second main technical contribution of our paper. We first recall the O-FTRL-FP update rule from Eq. (6):
d argmin C (
1 ((A),
AEA ectrEE
Me
9e ge = Eeel Ee<olell
E
- (p-c))))))
MitTTEEy
7 (Ae) argmax (ur, - Nfc,,))
VI' < Eg.
iE[K]
We highlight the main technical challenges here and refer the readers to Theorem D.3 for more details:
1. Since 7- (Ae) not continuous w.t.. X due the argmax, the predicted loss function (A; A.) :=
@e(Ne) À is non-continoous w.r.t. Ag as well which means an exact fixed point may not exist. In Lemma D.4, we prove that our O-FTRL-FP framework only requires an approximate continuity, which we show ensures the existence of an approximate fixed point.
In Lemma D.5, utilizing the smooth cost condition in Assumption 3 and an e-based uniform smoothness argument, we prove that our ge (>g) X is indeed approximately continuous.
3. As agents can misreport in epoch Es, the actual epoch-l loss function Fe == Σiee, (p
Cr,i,) T X may differ from the predicted Fe A; Xz). We control this effect in Lemma D.6.
4. Due to the unknown distributions, namely {V, [E]kE] and {C, HE(K). the planner can only use finite number of samples (more preciously, Ee<e Eg.l ones) in 7 (Ae). We control the statistical error in Lemma D.7; however, since X is not measurable in round uniform smoothness analysis to ensure the statistical error is small for every possible X E A. 5. Finally, since agents could also misreport in the past, namely epoch & where é' < E, the reports used in i, (Ae) can also be very different from the true values. In Lemma D.8, we analyze this type of error, again incorporating an e-net based uniform smoothness analysis.
develop e-net based
Via careful investigation, Theorem D.3 proves that when configuring
-1/2
(A) = |A|2 L= log = 12in1, - -1,T)}, me =
Σ
|Eerl
2
we can control the E[DUALVAR] as
|p |
dK2E.T
E[DUALVAR] < 2VT
&d + 4Addlog(dTL) + 48d
log
+ 16d + 10
2
TPj
j=1
(2N² + (Ne + 3)1p -11 SdM?) + +31pp 1111
where (the definition of Ne is the same that PRIMALALLOC)
N 4K2c, p "11 + loglE:1 log,- 4 + Ile (11))11119
dKZc.T
M, = Elogy-1 (1 + 4(1 + P| 11ppp~~111100000 11 1 ( + 4cculpp 11 +4 log(dT) +
> log
pge
Putting two parts together, we get
RT(T", Algorithm 2 with Eq. (6)) < ERRMAALALLOC E|DUALVAR]
p 1--1|
d
dK2e.T 16d + 10
< T
8d + 48d log (dLL) + 48d
Σ log
2
Tp;
1=1
25

---

(2N2 + 33)+ + 1) + 8dM + 3/1pp
The bound that Br Algorithm 2 with Eq. (6)) = 0 directly follows from Line 14 of Algorithm 2. For the Ōa,K, version, since L S [log2 T Od,,,r(1) and [& - T for all E, we know Ne Oa,,T((K²) and Mr- = 0 O a.K.T (1). This gives Ry O, VT K*).
C PRIMALALLOC: Regret due to Agents' Strategic Reports
C.1 INTRAEPOCH: Agents Lie to Affect Current-Epocll Allocations
Lemma C.1 (Truthfulness of a Cost-Adjusted Second-Price Auction). Consider a one-shot monetary allocation setting with K agents. Each agent [K] privately observes their value vs Vi and publicly incurs a known cost G; ~ C, Agents submit scalar reports u, E [0, 1l, and the planner allocates the item to one agent 4 [K] and charges payment Pi. The utility of the selected agent
Vi. Pii, while all others receive zero utility.
Suppose the planner implements the following mechanism:
argmax(u, ci), Pi, = Ci. + max((u; - Cy). sE[K]
jF
Then:
(i) For any agent E [K] aiming to maximize their expected utility (u; - Pt) 1[b = i). truthful reporting is weakly dominant strategy.
(ii) When all agents report truthfillly (u, Uz). the allocation is argmax;((K]) (14 c4), i.e.,
maximizes the value-mine miiee--iius-oost C4 across all the agents.
Define each agent's pseudo-report ü; = 0, C, and let in v2 Gj be the truthful pseudo-report. Fix any agent i [K] and suppose all other agents' reports {u, hiss are fixed. We evaluate the utility Us that agent obtains under various reporting strategies.
Proof.
Case 1: Truthfully report in = U; so that ū; = ū7:
max ny then & = i, and U4 = U; - max Ūj = ū; mmxx Uj.
If ?
< max Uy. then & * i, and U1 = 0.
Case 2: Over-reporting u, > v so u; > u,:
ù; > प5 > maxjại Uy 44; = पे max ūy (same as truthful). If max ب ūy > 14 > úi Ug = 0 (same as truthful).
Otherwise if ü; > maxjại üj > मū Ui पं maxj ūj < 0 (worse than truthful).
Case 3: Under-reporting
< so ū, ū
If / > ã; > maxjøi Ug U; = ūi max ūy (same as truthful).
If maxxy4 ūj > i. ü; U; = 0 (same as truthful).
Otherwise, if पi max ū, ū; U4 0. But they originally get ūद max ūj 2 0.
In all cases, deviating from truth-telling does not improve agent i's utility, and may strictly reduce it. Hence, truthfuul reporting is a weakly dominant strategy, proving claim (i).
For claim (i), when all agents report truthfully (w; v;). the planner allocates the resource to i = arg max; (v: - c;), which maximizes net social value.
Theorem C.2 (Intra-Epoch Truthfulness; Formal Theorem 4.1). Fix any epoch & S [T] and dual variable De A. Suppose that all the agents, when crafting their reports only consider their discounted gains within the current epoch (Model in Eq. (8)), namely Eq. (11), To highlight the
26

---

different reports, allocations, and payments due to the different agent model, we add superseript h.
pi..) - 11. =0] .1. E [
max (a hree
E
(11)
LIEE
The planner, on the other hand, uses the allocation and payment rule in Line 12. Formally, in round t E & the planner allocates to the agent with maximal dual-au hual-adjusted report which we denote by it to highlight its difference with &t due to the different agent model and sets payments accordingly:
argmax((u uh,, cTc,,), Pest C. + max(ul X[ Vt E Ec. xE[K]
Then, truthful reporting ue = for all E & and E [K] a joint strategy denoted as TRUTH constitutes Perfect Bayesian Equilibrium (PBE). Furthermore, under this PBE, the planner always chooses the optimal agent according to dual-adjusted value:
arg max (v2,, c1,)) sE[K]
and the regret due to intra-epoch misallocations is zero, ie., E|NTRAEPOCH]]
Proof. For any round E &g, we observe that the planner's allocation and payment plan (it p!) depends only on the current reports u,, current costs C₁2 and the fixed dual variable Xę. Specifically, does not depend on historical reports [ past allocations (1t) ) or payments (p Jrs--
Likewise, for any fixed agent E [K]. suppose that all the opponents follow truthful reporting TRUTH-., i.e. (ut, = Vt.j for all E & and j A i). In this case, for any round t E & whose value is Vr, E [0, 1], the expected gain of any tentative report ue [0, does not depend on the history but only on ut. Ct. de. and ur Therefore, agent does not benefit from unilaterally deviating to "history-dependent" strategy that depends on previous public private information, namely {u Jree. (ih [p])ree and {dr,irr<
Therefore we only need to consider agent i's potential unilateral deviation to distory-indepenan policies, which means we can isolate each round E & From Lemma C.I, we know that in any such round given fixed costs and fixed dual Xe, truthful reporting maximizes agent's expected utility regardless of opponents' actions. Hence, no agent can benefit from deviating whether using history-independent
history-dependent strategy
and thus TRUTH is PBE.
Finally, under PBE TRUTH, the planner allocates to the agent with maximal u2 A.C,, Le, 1 Therefore, there is no misallocation in the epoch and thus INTRAEPOCH = 0.
C.2 INTEREPOCH: Agents Lie to Affect Next-Epoch Dual Variables
The key ideas of Lemmas C.3 and C.4 are largely motivated by Golrezaei al. (2021a, 2023). The main difference is due to the costs {ce (er) which forbids us from using their results as black-boxes.
For epoch é E [T.), consider the "epoch-l game with exploration rounds" induced by Lines 4 to 12 in Algorithm/ 2. Theorem C.2 proves that under Model 2 in Eq. (8) (i.e., agents only care about current-epoch gains) and when there are no exploration rounds, TRUTH a PBE. Now, we claim that under Model in Eq. (8) (i.e., agents optimize over the whole future) and the actual mechanism with exploration rounds (Lines 4 to 12 in Algorithm 2), there exists a PBE of agents' joint strategies π that is not too far from TRUTH. Formally, we present Lemma C.3.
Lemma C.3 (Large Misreport Happens Rarely). For epoch & E [L]. consider the agent Model I in Eq. (8) and the "epoch-l game with exploration rounds" " specified by Lines 4 to 12 in Algorithm There exists PBE of agents' joint strategies such that for all E [K].
1 EE
Pr
Juni
log, (1 (11 2
[3
LEE
where (ue,teee, are the reports made by agent i under π.
27

---

Proof. Consider the for every round E,, agent E [K] is only allowed craft their reports u,, based on current-epoch dual variable Xe, round number current-round private value Ut,i, and current-round public costs Cy-
auxiliary game defined in the proof of Theorem C.2, where
Let be PBE in this history-indeppendnt auxiliary game. Using same arguments from Theorem C.2, unilaterally deviating to a history-dependent strategy is not beneficial as all opponents' strategies т and the mechanism (Lines 12 Algorithm 2) are history-independent. Hence, remains a PBE in the actual "epoch-e game with exploration rounds" where history dependency is allowed.
To prove the claim for this PBE π, consider the unilateral deviation of any agent i [K] to the nuth-telling policy, i.e., n²' := TRUTH, on Since π is a PBE, π:' no better than π under Model 1 (the actual model). That is, for 8æ min(t t E and any history Her always have
0 S
Σ 7 (UTA Pr,) = i]
Hog
E
7 (vr. pr,)) =
Har
E
y (U+, Pr,)) i]
Hos
E
Σ Lreee
r (Ur,s - Pr.c) = o) Hay +
7EE
Current-Fpoch Epoch Difference
E
Σ EStTEEE
(VT, PT,)
Hoe
E m
Σ
( -W,))
Hse
P'St,EEE
Future-Epoch Difference
(12)
For the second term, fix any l' > l and Eg. Since the values et, reports u, and costs e, all
bounded by [0, 1), and that Ag E A 2 10_110,p [0, Pj (which infers ||>e |I S IIi), we have
Pr. AT. + max(urs ()ers) c
2|1eel11
max Cr. no. 2 1| max | jE[K]
3/4
SE[K]
for all L' T Ep. Since V1 E [0, 1), this suggests that u [-1-2||p for all E [K], and thus
|l 1 [11]
L
Future-Epoch Difference
ΣΣT
Σ
Err.
Σ
-
2 111) 2(1 211p
1-11~1111 84+1
where the second inequality uses the fact that ΣJ 7" S
111 1-7
We now focus on the current-epoch difference part. Since both æ and अ/ are history independent (recall that a joint strategy from the history-independent auxiliary game and म TRUTH, o.. the conditioning on H., is redundant and consequently
Current-Eooch Difference
E
Σ LCE
-.. -E
LTCE2
For any round & &,, we control this difference utilizing the exploration rounds:
Suppose that round e Eg is an exploration round for agent i (which happens with probability * the expected gain of reporting ut, rather than U2.s (i.e., under versus under n ) is
[d
1 [Vr, 1 2 p] - (vr, - 1(o, 2 pl = (un, -
( v2,)
(0.11)
If round t an exploration round but not for agent i, then reporting de and Uz, both give gain. Finally, suppose that round / & is not an exploration round. Notice that i) both π and . are history-indepeendnt, and üi) if round / & is not an exploration round, then the epoch- game Lines in Algorithm coincides with Line 12. Therefore, via Lemma C. 1, the gain of reporting u is no larger than that of reporting Ut iee. the expectation difference is non-positive
28

---

Let Mes := {t Ee |e, - - 1 } be the of large misreports from agent (regardless of whether I turns out to be exploration round, since reports happen before it). Let the last round in epoch & be et = max
[ee
Et). Since EieMer 7² Di=er |MM, 7", we have
Current-Epoch Difference S -B
Σ "
[El K (Wr, - vo,))
BEMr,
Meiit
(1 -yMMe,ll)
S E
1-y
[& K 2
In order for xO' be inferior when compared with π,, Le., Eq. (12) holds, therefore must have
2(1 + 21l 7 8t-1
per-lMe.l+ 1011-1MMs M.Me.))))
2 E
1-7
[2 K 2|E
104 -- 2 Pr[lMed 2 e)
Ve 0,
(13)
2K|
where the last step uses the fact that 8841 = ex 1.
Picking such that 2(1 + 2|1p~1111)
2K| ( 7- |8
reach our conclusion that
1 EE
Pr (IMeal 2 1og 4(1 + -1-
This completes the proof.
Still focusing fixed epoch & [L]. Lemma C.3 bounds the number of rounds with large misreports. We now turn the remaining rounds, i.e., those E & such that |ue: Wt.al S [e] for all i [K]. We claim that misallocations are rare among these rounds, formalized in Lemma C.4.
Lemma C.4 (Misallocation with Small Misreports Happens Rarely). Consider an epoch E [4] with dual variable dE A. We have
Pr
Σ
argmax(uu, Aec.. argmax((r,, -aae---TA.. sTers) [[1.x va,ll 5 KE[K]
vi [K]
Eel
L37,
iE(K)
2 Egl
< c. + +1log|Es| 2
Proof. For any round E &g, bound the probability that the allocation based on reported utilities differs from that based on true values, even when reports are close truthful. Specifically, consider the event
1 E
argmax((u: U1. [E[K]
C.... # argmax((1, A.c..)) and (4, UeSil S (E[K]
Vi E [K].
Such mismatch can only happen if there exists pair of indices i 3 j whose true dual-adjusted values are very close within |e so that small deviations in reported utilities (bounded by [2y]
are able to flip the argmax decision. We apply a union bound over all such pairs to upper bound this probability:
Pr argmax Ue,i KE|K]
CT,),) * argmax((Ut, XJcr,) A |ue,i iE[K]
vt,1l -
[E
2K2
Σ Pr 1002 2. (Vi, {(ar))ls ISKjJK
E3 <
<a
Aellle
(14)
[3
29

---

where the second inequality comes from Assumption 3: Since it assumes that PDF ( ca,)) is uniformly upper bounded by e. where de A, we know
{
2 [& S A ca.s [Ur, vs + \ {(er,)
4
Pr C
- [E
EEl
Now consider the martingale difference sequence {X: B[X₁ Fi-illees where
1 [
x=
argmax((u.. - argmax((r, U1, cf..,) (E[K]
KE(K]
and (Fi); is the natural filtration defined as F, = (x1 X x,).
We apply the multiplicative Mauma-Hoeffdinng inequality restated Lemma E.4 (Koufogiannakis and Young. 2014, Lemma 10) with Y; = [[Xx F2-1l. e = 2. and A = 2 Log|Er) . Since X; E [0. 1] and E[X; Yt Ft-1] E[X, E[X Fi-1] Fi-1] 0, the two conditions in Lemma E.4
hold and thus
1 Σ Pr
X
Σ 1Et2
E[X, Fi-1] log|EE /
S
2
LEÊ2
From Eq. (14), we know E[X, Fi-1l = Pr(X, Fi-1) - the above concentration result gives
2K²
Aella. Therefore, rearranging
Teel
Pr
Σ
X 4K 4K2 (eell1 4log|eel
21 [7
LE9
Plugging back the definition of X, completes the proof.
Putting the previous parts together for all E [T.] gives the following theorem.
Theorem C.5 (INTEREPOCH Guarantee; Formal Theorem 4.2). Under the mechanism specified in Algorithum 2, there exists PBE of agents' strategies π², such that the PRIMALALLOC term (which the sum of INTRAEPOCH and INTEREPOCH terms) is bounded as
To
E PRRIMALAALLOC E
Σ
S Σ
(Ne +3)
where N = 1 44K2 <al -
111
log Eel + log, (1 + 4(1 + +1pp~ ve (Z..
Proof. Applying Lemma C.3 to every epoch E [L]. we get PBE Ny for every "epoch-l game with exploration rounds" (Lines 4 to 12 in Algorithm 2). By definition of Te, the safety constraint is never violated before that and thus Line 14 has no effect. Furthermore, since Algorithm 2's allocations and payments within every epoch anything else from the past, using the same auxiliary game arguments as in Theorem C.2, there is PBE πt for the whole game under mechanism Algorithm 2 that matches (TTa (E([)) up to T...
[7.] only directly depend the current dual variable X but not
For every epoch Eg, can be either exploration round, which happens w.p. [ि independently. ii) a standard round with large misreports: 3i E [K] such that [u,, Vt,i 2 e. or iii) standard round with only small misreports. For ii), apply Lemma C.3; for iii), we apply Lemma C.4. For i), applying Chernoff inequality,
Σ 1s exploration round] > 1 1 < exp LEE&
Pr
Ve > 0.
2 2
2c/3
Setting c = Log|Ee| so that the RHS is no more than
[ we get
1
Pr
Σ 1st exploration round] < + log(Ee|
21
1
(15)
[3
rEe
30

---

Now we put the aforementioned three cases together:
E/PRIMALALLOC
E
Σ
ie]
(6)
L
1
exploration round]
Fi E [K], lug, 01,12 2
[32
1331
1 argmax(u,, ue,s xfcr,) # argmax xfer,) A 14,,s -e,sl - .E[K]
vi E [K]
=E[K]
Eel
1
+ 1og|Er| + +4K2 + 4log|e + log,-1 (1 4(1 + 1100 ||)=(11))(((11)+ 3/E
[8
(16)
(N,+3) 1= fe ||| logg[E1 -o (1 + 4(1 [1 10llllp1))00))) -1)
where (a) uses the fact that vr, E [0, 1] for all and i, (b) uses the above discussions of (i), (ii), and (iii), and (c) applied Line 9 to (i), Lemma C.3 to (ii), Lemma C.4 to (iii), and the trivial bound that Eiee, 1 # 4/] [Ee] if any of the conclusions in Line or Lemmas C.3 and C.4 do not hold (every conclusion holds with probability
TET and thus a Union Bound controls the overall failure probability by [8 ). This completes the proof.
D DUALVAR: Regret due to Primal-Dual Framework
D.1 DUALVAR and Online Learning Regret
Lemma D.1 (DUALVAR and Online Learning Regret; Formal Lemma 4.3), Under Algorithm 2, the DUALVAR term can be controlled follows:
E D[DALVAAR]
E
To
L Σ
p- c (() x3)
< E
sup AAEA
(Ne+ 3)111 + IIl.
E=1
where
No = 4K² Ec 11
11 + log|EEl + 1og,-1 (1 4(1 + |pp "111(11))))111
Proof. This lemma largely adopts Theorem 1 of Balseiro et al. (2023), but incorporate some arguments of Castiglioni et al. (2022) to fix a measurability issue in the original proof.
Slightly abusing the notations, for any round belonging to epoch &g, we define X == A Let (Fi)c2o be the filtraionn specified as F, = (Ai....,, A, V1...., Me CI,C,,...,,.).
For any & E [Z]] let of be the convex conjugate (Fenchel dual) function of vr, namely
"x (A)
max (V1,- A AT,,), AAAA, iE[K]
which convex in À since it's the maximum of convex functions. We further define 8 (A) Ep-y,e [max (v) X AT))), which is an expectation of convex function and thus also convex.
Step 1: Lower bound the values collected by (i ((phet))) By definition of i from Eq. (9) that
i = arg - X1 c.,), we have
M1. = v. (Ae) + XJ C, W S Te.
31

---

Since 7 is Fi-1 --ee-urraerb but Us and o₁ are sampled from V and C independently to Fi-1.
E
Fi-1 = E o7 (Xe) \o c5 Fi-1 o² (Xx)
+ E
X C,;;
Fi-1]
Put this equality in another way, the stochastic process (Xt)+21 adapted to (Ft) defined as
X, " X N. - (x,), AI S To:
ensures E[
Fi-1] = and is thus a martingale difference sequence, Since To T + 1 a.s. by
definition from Eq. (10), Optional Stopping Time theorem (Williams, 1991, Theorem 10.10) gives
To
To
To
To
E
X
2
E
Σ
We now utilize the convexity of v", which is the expectation of convex function, and conclude that
E
E
T
T
t=1
1=1
(a)
To
To
EE
Ty v²
A
lo C
To
(6)
To
[T)
inf o' (A)
+
E
Σ
C2,31
(17)
XEA
:=1
where (a) uses Jensen's inequality and (b) uses the fact that X
to ETe
A, E because A, E A
for all r and the fact that A P. is convex.
Step 2: Upper bound the offline optimal social welfare Ein 0e,4z We now work the other
term in [[[UAALVR), namely E E dt,z7-- For any fixed À E A, since of (A) (aX
A AT...) 2 2t,4 - AT cr,s for all t E [T]. we have
T
+
X cL.
A.AΛ.
(18)
Further recall from Eq. (2) that { ke()) is the optimum of the offline optimization problem
T
T
max
s.t.
Ca.
S P.
T
(=1
ensures $ Ei=1 Ca S p. Therefore, for any fixed A, we further know
T
T
E
U15
E
(t)
+
AT CL.
X
T
T
1=1
(b)
E
Tw
2 (2)
T
1
Cr,4
T
(c)
T
E
To
of ((A))+TT7
T
(d) E ET. (A) + AAEA.
where (a) uses Eq. (18), (b) rearranges the terms, (c) uses Σ Ct,t S p. (d) uses the definition
that 8² (A( -E-ry, [max A Ac.)) (and thus El (A)] 0² (A) for any fixed À A).
32

---

Taking infimum of À E A and further recalling that all the values D2,57 are [0, 1] bounded, we get
T
T
S
E
VL, + (T)
T
t=1
T
inf (u" (X) +
+ E Tel
AEA
S E
Tol
inf v*(A) + [T inf X p E - Tel.
(19)
A
xA
Step 3: Combine Steps 1 and 2. Putting Eqs, (17) and (19) together, we get
T
E|DUALVAR E
2,5
t=1
T
inf 0² (A) + B[T
inf X P
E
Te)
AEA
T Σ
TTll inf AEA
o*(2)+ +
A
C
To
E[To] inf A -
Σ No
+ +E[T - To)l
AEA
Consider the following stochastic process (Yı)121 adapted to (Fi)12u
Y = inf X ATp X.P. 11 S To
AEA
we must have E[Y, Fr-1l < 0 since A E A, which means (Y))12 is a super-martingee difference
sequence. Again utilizing the fact that To S (T + 1) a.s. and the Optional Stopping Time theorem (Williams, 1991, Theorem 10.10), we know
To
T.
E
Y2
T
inf AEA
p
E
inf A XEA
S
E
AT
p
1=1
This reveals that
Tv Σ
)
E[DUALVAR]
E
X P
E
x C
EE[T Tol
Lt=1
To
E
AT (p-
-G,7)
+R[T - TTo
(20)
Comparing Eq. (20) to our conclusion, it only remains to associate A o. with AJ Cr, and control
E|T To). We first focus on the former objective.
Step 4: Relate AT G,3;) to XT (p- - C, Using Eq. (16) from Theorem C.5, with probability
1
3 B. the sequence (Gt hes, and fith only differs by no more than Nj, where
NO = 1 4K 111 + Log/ + log,-- (1 + 4(1 + (11) VE [L].
That is, have shown than E Th I liz # ii] Et= (N₂ 3) where the 3 comes from the [eत1 failure probability and the fact that Eiee, 1 li; + it] < Eg/. Combining it with the observation that
IT,,A, Ar 5 || | ||cr,s c,,i |I S 1|p~~11:. ||r,
Vi +
where we shall recall that Cr,i, Ct.j E [0, 1 and that A E A 8 d
10 [0, P 11. Eq. (20) gives
To
XT(p - (
E|DUALVAR] SE
+ +ET - Tn)
33

---

T5
S E
(AT c,ú.) + 11--111 16 + irl)
+ +E - Tel
$ E
(p ccti))
+ +|lp~111 Σ
(Ne + 3) + - Tel
(21)
8=1
Step 5: Control E[T - Tol. We recall the definition of T, from Eq. (10):
T. min [
Σ Crai + +1 Tp ((T+1).
T. = 1, then (T (TTT) To) is trivially bounded. Otherwise, suppose that E Cr.i, + 1 1 Tp violated for the j E [d]-th coordinate (if there are multiple j's, pick one arbitrarily). We have
T
To Σ (oz (ase)) <1 (T -To))pp
Cas +1> Tpj
(22)
Let X* ej where ej is the one-hot vector over coordinate j, we know X A and that Ps
To Σ p Ca,,.) 1 1=1
To Σ
Pj
(22)
(T T.) = Pj -T-To)
Pg
1=1
Rearranging gives
To (p C..i,) (x,) )
(T - To) S max Pj
sup A
Σ
Final Bound. Taking expectation and plugging back to Eq. (21), we yield
T P ce. A
1
DUALVAR
S E
+
Σ
(Ne + +3)1e- + E Tol
T
(p-cre ce.i ) }
<
E
+ -
(Ne +3)1pp 1111
E
Pj jE(d
max
sup
Σ
X-EA
1=1
To
1
<
E
sup
p Ct,s, cr,s.) Ta: -20)
+ Σ (Ne 3)11p~ 111 + 1
1=1
This completes the proof.
D.2 DUALVAR Guarantee for FTRL in Eq. (5)
Theorem D.2 (DUALVAR Guarantee with FTRL). When using Follow-the Beeoow-th-Reggueee Rehee-egglarize--LLaeeeee (FTRL) in Eq. (5) to decide {De)te(L)) the online learning regret no more than
.º = sup X-EA
Σ
(0- c.,
x3)
sup A
v(*) π
+
ne
Eel2
Specifically, when setting
-1/2
(A) _ ||
1
|| 112
Σ Exr 2
ne
22d
34

---

the E[DUALVAR] term is bounded by
E|DUALVAR] & 2 Σ
E - Σ
(N₂ + 3) -11 + -1-01111 ||,,
t=1
t=1
where
NE 1 ce 1p "p-0-11 + 5 Egl + log.y1 -1 (1 + 4(1 + |p 1111)))))(11)
Proof. We apply the FTRL guarantee stated as Lemma E.1 with their decision region X' as our dual decision region A - X 10 p7'), "J their norm ||-|| as f2-norm, their round number Rt as our epoch number L, their round-f loss function as observed loss (x( = Eiee, (p Cr...) T A, the FTRL decisions (Λe)eE(L) suggested by Lemma F.1 recover dual-decision rule in Eq. (5), Le.,
00
d = argmin
-
x ne
(A), AA [4].
dEd EECTEE
Since VA Fe(A)
Exec, (p- Ca,s)) and the dual norm of Enrnorm is still fn-norm, Lemma E, gives
E
sup XEEA
Σ
To
(p-ca Cr,s. T c
x²)
sup X
((*)
L Σ
E E
Σ
c,a,
t=1
LEē:
Recalling that p, E [0, 1 we have 11 (p
11. 3 S dlE 2 and hence
P(AA))
I.
RE < sup
+ d
ne Eel
X.EA
1=1
This gives the first conclusion in this theorem.
We now move on to the second conclusion this theorem, namely the online learning regret under the given configuration of (A) 1 and m/p
1e=illa
(Er (E=118013))
-1/2
First of all,
V2d
1 トリ | p
v(x))
12
XX
E
x 0, p3 1
2
Plugging in the specific choice that ||ا
n)
(Ee=1EE113)
1/2
therefore have
v2d
2d
|l
l12
|3
113
E
1pp
1l2
2
V2d
Σ
Eee
(a)
1
||p~
2d
S
2d
|le
11p-1112
1112
Σ
Ex/2
+
Σ E2l2
2
22d
2
1=1
22
p
-1
12
EEp
where (a) uses the folklore summation lemma that ΣT VE=n..
2
ΣT=
xn for all
T2. 2T Rz0 (Duchi et al., 2011, Lemma and (b) follows from rearranging the terms.
Plugging the online learning regret 9i into Lemma D.I, we therefore get
D[DAALVAR] S 2 111p-111,,
112
Σ 1=1
+
(Ne + +3) 3333pppp1111 + 1--1-
t=1
35

---

where
e. N₂ 1 1- 11 + 5 + log, 4(1 + ||p ||=-()))))
This finishes the proof.
D.3 DUALVAR Guarantee for O-FTRL-FP in Eq. (6)
Theorem D.3 (DUALVAR Guarantee with O-FTRL-FP). When using Optimistic Follow-the- Begularized-Leadee with Fixed-Points (O-FTRL-FP) in Eq. (6) to decide (Xe)te(L)> the online learning regret is no more than"
RE = E
sup
E(e (p-
a, (h: -27)
A-EA
(A*)
EE
sup
+
118
4d + (odlog(dTT)) 24d
Σ log
X
Ee e'
<t
E3
Pj
(=1
3=1
L
M
1e6) + 10)
+
Σ
ne
2N
+ 111,
1 1xr1))
F=1
where for any l E [T], Ne and Me defined as follows:
N₂ 1+ 444 ecl '11 + log|Ee] log,- (1 +1++ 4(1 + (1)x
d Σ
dK3eaT
Mr Elogg-1 (1 4(1 - 1 166-1) Alcellp
log(dT)
log
Pje
Specifically, when setting
-1/2
1 1112. L lo & === 12 minm2n 1,T)), me (A) 2
1|- 1
Evrl
V112dK2
the E|DUALVAR] term is bounded by
|
dK2eeT
E[DUALVAR] < 2VT
8d + 48ddlog()LL) + 48d Σ
log
+ 16d + 10
2
Tpj
j=1
(2N + (Ne + 3) - 8dM2) + 112.
Proof. We would like to apply the O-FTRL-FP guarantee stated as Lemma D.4. One main challenge we face is the discontinuity of our predictions; recall the O-FTRL-FP dual update rule from Eq. (6):
1 ((A,,
A argmin XEA
E (At))(AA)TAA
PETTEE
ge (Ac) = EEel. Exer Eel H.C.TEEy
Σ
(Xc) arggax (UrS - -JT..)) (E[K]
VE' < <l, E Ev.
Step 1: Make sure Lemma D.4 is applicable. Since predicted loss term gr(A,) where gr (Az) the estimated gradient from historical reports and costs is not continuous w.rt. D; due to the argmax i, (Ae), we cannot directly apply the Brouwer's Fixed Point theorem (Munkres, 2000,
For the readers to better interpret this long inequality, we provide Öz version Eq. (29) in the proof.
36

---

Theorem 55.6) to conclude the existence of an exact fixed point X₁. Fortunately, in Lemma D.4, we prove the existence of an (Ny (epp::ee-aproxximal fixed point given (ce, approxxmmee continuity, which requires the existence of two constants (Eg, Te) such that
T ( ( Le,
AX' A s.t. ||' 22ll S ee.
We refer the readers to Lemma D.4 for a more general version of the (eg, LE) -approxxxee continuity condition that we propose, which generalizes to non-linear predicted losses. In Lemma D.5, we prove
( (e(22)l12 S 4|E cecod+ 4|Ee|(log oe Ej=
log vd
pire
Vd.
EecelEel
A2 A S.L. || A2ll2 S Eg,
w.p. 1
(23)
for any fixed constant <e and de E (0, 1). Roughly speaking. Lemma D.5 first picks an 2 -net of A and then utilizes the smooth cost condition (Assumption 3) to conclude that close X's give similar i. (A)'s for all which consequently give similar (A('s within every small ball in the net.
Properly tuning Eę to minimize the RHS in Eq. (23), translates to the (Ee, Le) apprrxxxxte continuity of prediction (Xe) X W.E.t de where
Vd = K2eE <<>o Ee<elEp LE
4/EeVVd ExeelE
Vd Pi&t
d log de
log
vl [4].
Under this specific configuration of and Le, we call the event defined in in Eq. (23) Ge. Conditioning on ..,...: Gr. which happens with probability at least 1 - òe (the conditioning valid because Gr only depends on fixed - -net of A and historical reports and costs, and is thus measurable before the start of epoch Ee), we can apply the O-FTRL-FP guarantee stated Lemma D...
j=1 [0, p, their norm |I-Il as fn-norm, their round number R. as our epoch number L, their round-& loss function fe as our observed loss FA(A) = Eies, (p ) X, their prediction fe A) as our ( (x))) The O-FTRL-FP decisions (Ae)eE(L) suggested by Lemma D.4 recover our dual-decision rule in Eq. (5):
Specifically, set their decision region X' our dual decision region
A = argmin
(o- + A+ A+ (Ax)
(A),, TJ8
E [L].
XEA
PECTEEE
where the R means the (1)eLe) approxitta fixed point suggested by Lemma D.4.
Further noticing that (AF EiEe, (p- Ct...) (Ae)) = (Ae), the loss (A( is V since (p Ct.;,) j0, 1) the loss and predictions are (-smooth w.rlf X since they are linear, and the dual norm Eg norm is still fn-norm, Lemma D.4 gives
To p cr.5.)
(Aa)) A
2
sup A
<
sup EE
Σ ne IE
Σ (p cr,..) (c) REE,
Dianeter
Stability,
I. ValEee
1.
Σ
82
2 11
(24)
Fixed Point Error
where the last term considers the failure probability of GI,..., .as.....ry GL, in which bound that IT ct,,,) T() X-) T (max,, lp oo supxex Alli) s 2T| '111. where the last inequality is due to C,, E 1-1, and 10.1100711
use the trivial
Step 2: Control the Stability terms. For analytical convenience, we add a superscript u to notation (A) to highlight it is yielded from reports {u, ee Analogous to g (A), which
37

---

is computed from agents' strategic reports {urte<t,rEE, we define 9; (A) using the true values {Ur)ect.TEEg> and gi (A) using the underlying true distributions V [VihelR] and C [C.)bE(R]
(A) = =16el- Excelen Epl
Σ Bcd,eEyy
(p C
(A) argmaax (ur, - 21 (E[K]
(A) = 118el- Eese Epl
E
(p- c22)00))
(p
(A)) argmax (17,4 (17,1-10 -Tcraa) sE[K]
97 = 1121
JE
P (
(A) argmaa (v. AT.,.). (25) (E(K]
We now decompose the Stability, term above as
Stability, =E
Σ
(p-)))))-
- - 92 (Ae)
REE2
2
E(p- ct..)) D6 (Ax)
+2E [1g) (1))
+2E [19 9 AAe)
LEE
Empiriaal Fstimatiin
Untruchful Reports
Difference between (ir (ich and (i) heee
In Lemmas D.6 to D.8 presented immediately after this theorem, we control these three terms one by one. Specifically, Lemma D.6 relates gi (Xe) first to Exes, (p C,,5, ) and then to Eie,, (p Ct.i.)
which gives
E
E -....))) - 97 (Ab) NEE
S (d + 3) + N2,
(26)
where N2 =2=10 + 4K2ecllp p + 5 Eo + log, (1+ 4(1 + (1)
|||
Meanwhile, in Lemmas D.7 and D.8, by an e-net argument, we first prove g; (A) ~ (A) (resp. T (A) ~ 9 (A)) for all X's in the c-net and then extend this similarity to all À E A using the smooth cost condition; we refer the readers to corresponding proofs for more details. Summing up their conclusions and taking Union Bound, they together ensure that for any c > 0 and 8 E (0, 1), with probability 1 65, we have
sup (l17 (A) T. 2 AEA
(g) - 9" (A)
log 1 + Σラ log PyE
d d
I Ed 2 (K2cE.)) + 10d|
M3
(27)
Σ EErl
( 1 12
where
d log + > j=1
log d
Mr = Elog (1 (1+4(11+ + 1|p-~ ( 428-1) + -4cccllp 1 +
pjc
Step 3: Plug Stability back to O-FTRL-FP guarantee. Now we plug the Stability bounds from Eqs. (26) and (27) into the online learning regret bound derived in Eq. (24). For every E [T..
Eq. (27) happen with probability 1 65; in case it does not hold, we use the trivial bound that
l (A) g ()) 2 + 9 (A) 9 (A) < E ? Therefore, Eq. (24) translates to:
To
Ω E
sup
pp
Ct,5,) ) T().
x
A
t=1
((X')
1
< sup
+
(d (d+3) N2 + 7d/E.12 (K²cc.)²
A-EA
7
t=1
38

---

log 1 + ΣØ= j=1
log d
d/Epp
+ 10dlE 2
Pyc
M2
+ +6 2d|Ed
Er.1)
4/E,| Va EecelErl
1
d
Vd
1
d+ log
log
+
Σ
8z
1T
dz
Pjft
j=1
where Et = K²e, Ee E and {ōr ke [z], e, and å are some parameters that we can tune. We also recall the definitions of Ne and My:
N₂ = 11 4K2 1|1 + 5 logled + log, 1(1 + 4(1 + 11)
Mr- = fog (1 + 4(1 + 1 |1) 1 4)6-1) + 4lea p
||1 + 4
log
+
log
5
Pjc
Step 4: Deriving first half of this theorem. We now configure 6, and 8 's as follows:
8 TT.
VTK2
GdT
We remark that we did not make every effort to make the overall online learning regret small as possible. Instead, the above tuning mainly focuses on polynomial dependencies on T and L.
Under this specific tuning and simplifying using the fact that 1E=1EE S T, we get
(A*)
RY
sup X'
n
log(dT)) + Ei-1 log dKte.T
d|E
710 2
5)(ee + N2 + E/
Ed]Eel2
K2cc Evecleel
Vlt Σ 1l Eecclee Eerl
d (o+log(TL) +
log
+2210-1111
Pj
j=1
v(x')
EE
d
dK2e.T
+ Σn
4dt + 24d 24d + 24d Σ log
sup
n
n1
Ee
Ecr
Pj
j=1
L +
2
+
E1 + 10)
Σ
n
2N
+ 2||p 11
(28)
For the readers to better interpret, annotate the order of every term in terms of Ör, which only highlights the polynomial dependency on T, and consequently, also L, {|Ee/hee(r) and (neheetre
.º Ör 1T.
1
E
L
The
Ed +
me + )
(29)
Ee
1=1
Step 5: Plug in specific tuning of V, L, &Ee heeee and {ne 1eeee specific configuration:
We now plug in the following
11/2
(AA) マ |al2 L log E 122-11 1-in=1,
-1, mmnn(2211,T))) me
Σ EEel
Due to the doubling epoch length structure, we observe that
13
(20-1)
<2 2, A4 > 1.
Σ111
E3
22-1-1
39

---

Therefore the informal bound in Eq. (29) becomes Or(nE' + +E nelEe)). This explains our choice
==
that v/e = (E To make it formal, substituting Σ/
EE
S into Eq. (28):
(())
dk2
RY 2 sup
Σ t=1
Me Eel
8d 48dlog(dTL) + 48d Σ log
+ 16d 10
X m
Tp
ne (2N? + 8dM,) 2 -
Under the specific choice of ((X))
2/11111 and that ny -E(==1Eel)> get
1/2
10
1
RE
Σ
Eel
2
Eel
dKREcT
+
8d + 48dlog(dTL) + 48d
Σ
log
+ 16d + 10
E
Tjj
1=1
,=1
+
Ne
(2Nz + 8dM3) + --11p-111
||0-113
c.2
< 2
Σ 1=1
Eel
+ 8d + 48dlog(dTL) + 48d
log
+ 16d + 10
2
Tpj
j=1
+ Em1
(2N?
&dM,)) + 211p-
where the second inequality again uses the folklore summation lemma that Σ VE
2 EL= Ie for all T1. $2. 2T Rz0 (Duchi al., 2011, Lemma 4); we also used the trivial bound that ve S 1 for the non-dominant terms. Once again, we remark that the final bound is only optimized w.r.t poly(T") dependencies.
To translate the online learning regret Ri to the V[DUALLVR)] guarantee, we use Lemma D.1 (we also usd the fact that Σt_ E&rl TT:
To Σ
Cr T x3) + Σ (Ne + +311pp 2111 + 11p-1111
E[DUALVAR]
E
sup A-EA
(p
t=1
||-1||2
d
dK2c.T
S 2/T
8df + (88dlog(dTT)) + 48d
log
+ 16d + 10
2
Tpj
j=1
L
(2N? + () + 8dM?) + +311p -11-
This finishes the proof.
D.3.1 O-FTRL-FP Framework for Non-Continuous Predictions
Lemma D.4 (O-FTRL-FP Guarantee). For convex and compact region within an Euclidean space Rdd, an 1-strongly-convex regularizer v: X + IR w.r.t. some norm [|-I] with min ( = 0, a sequence of continuous, differentiable, convex, L-Lipschitz, and Ly-soooth losses fI, f2...., Sn-
sequence of learning rates Th 7/2 2 2 πA 2 0, a (stochastic) action-dependen prediction sequence ff:: X X + R]rE[R] such that the following conditions hold:
40

---

1. fr is F--1- where (Fr)e is the natural filtration that F, = ff...f....... 2. For any fixed y E X, -) is continuous, differentiable, convex, and Ly-soooth. and
3. (y) is (cr, L...:approimmacly--ootmnnee w.r.t. its first parameter y in the sense that
(2).(v). V22r Te: Vy,, y2 E X s.t. I1 - -y2l < cr:
sup mEX
where Vife is the gradient of fr x) taken only w.r.t. the second parameter æ, and I|- is the dual norm of I1-I]-
Then, for all 1,2, 2, ...... R. consider the following
system:
x, argmin #EX
Σ f+(x) (x), v(z))
(30)
First of all, the argmin in the RHS of Eg. (30) exists and is unique. Furthermore, Eq. (30) allows approxxaape fixed point By such that
||
(((z))
Dr
argmin EEx
+f Fr(ex, x) + T/r
S Smnbe
E
Using this { we have the following guarantee for all x E X:
n
(x)
Σ - fx(x))
Σ 7h (V,)(x vf,(,,)1 + +21322,)
2
7
We first study the system Eq. (30) for any fixed [R]. For simplicity, we drop the subscripts r from F(x) and G(yy defined soon. Since (x) is l-strongly-convex and fi(x) is convex, Vr <
Proof.
F(x) == E((w)) (x) is n, strooggly-coneex, Vr E [R].
f/r
Fix any 41, 3/2 E X' such that ll - 82ll < cy. From Condition 2 of J... and H2(=) == F(x) + fr x) are continuous, differentiable, and "stronnggyyy Hence 21 = argmin H1 (ar) and 22 == argmin H2(æ) exist and are unique. Further utilizing the n, ----ssson-cooveeiiii H1, we have (Bertsekas et al., 2003, Exercise 1.10)
fr
mr 1|2 - 2211 x
(V HH (x1) - (x2), I1 - xx2)
(V H1 (m)) x2) + ( x2 -x1)
WVE
(VH (x22, xi)
IΛ IAG
(VH((x)), x2 x1) + VV (z2)))) क1 x22)
|| -==-l V (m)) H [22 )1+
where (a) uses the first-order condition of (x) that V H ( xi > 0, (b) uses the first-order condition of H2(22) that (VH2( inequality. Using Condition 3 of fr and rearranging terms, we further have
222 > and (c) applies Cauchy-Schward
[ x2l1 < T7 (x)) (Hb((z))1
TH (12 V2f x2)1 S L,L..
For any y E X, due to strong convexity of F(x) + (. x)) the following G(y) is well-defined:
G(y) == argmin
Σ ((()) + (,y +
1 - v(x)
argmin =EX
(F(x) +r F1)
7r
41

---

Eq. (30) translates to 2, = ( ). and the aforementioned G())), = G(y2). Thus
[G((y) G2yz)) ||| ø2| S 17, Lr Vy y2 E X s.t. lly y2l < c,. (31)
We now utilize the partitions of unity tool in topology. Consider an - of X, whose size is finite since X' is compact subset of the Euclidean space. Denote by X S U ==1 B, where B, a ball with radius centered at some y E X. It induces a continuous partition of unity fØr B; + J0, []M
such that Di (:( for all y E X (Munkres, 2000, Theorem 36.1). Consider
M
Gly)== = Σ (
E
which is continuous since every d, is. Furthermore, G(ū,) X for all i [M], know G is a continuous map from X' to X. As X' is non-empty, convex, and compact set, the Brouwer's Fixed Point theorem (Munkres, 2000, Theorem 55.6) suggests the existence of y" X' such that G(y") = y². This y² E X' then ensures
M o (v) -Gy))
-(y' -
Σ
M
(a)
M
-
Σ oi(y") Mehr S m Mp
where (a) uses the fact that if (:("") * O, then y" E B, and hence 1 - Yil < cr. which gives [G((y") G(ū S Ty from Eq. (31). Therefore, for any round [R). the system Eq. (30) indeed allows an (1) appproxmaaee fixed point æ, E X.
After proving the existence of approximate fixed points in Eq. (30), we utilize the vanilla O-FTRL result stated as Lemma E.2. Since every term in Eq. (30) is measuubaee,,l the approximate fixed point Φ, and its induced prediction (-) == Ey (2). are meeasurblle Therefore, the {erree(n serves valid prediction required by Lemma E.2. Applying Lemma E.2, for the sequence
1 w(o)) G(ær), Vr [R), 7
x.. argmin xEX
Σ felx)) Po( +
we have
(xxx)
1
R
Σ
<
Th
(z))); -V Vx" e x.
TR 2
Since x, is an L,, -app.x.iappooimttte fixed point of G, we know ||0,- 1 G(x,))l S Enp I.
Further realizing that (fr( = V2Je(ar, .)) by definition of fr(-) = fr( :) we get
( (x;)) L. L.
[V - Vf. 5 Ly Th V x.) V2J 0;)11- S Ly Tyb Vr E [R].
where the first inequality uses the L-Lipschitzness of fr, and the second and third inequalities use the -yssoohhhssss of fr and (x -). Plugging back gives our conclusion that for any x e X.
Σ -
R
((x')
1
Σ nr (x)(
vf(t,,)1 + Σ (L + 2127
7R
2
This finishes the proof.
42

---

D.3.2 Approximate Continuity of Predictions in O-FTRL-FP
Lemma D.5 (Approximate Continuity of Predictions). Recall the definition of (e(A) from Eq. (6):
(x) = |&g] Ee<elel
Σ
(p (0-C)t(N):
(A): = argmaa (ura -ora-xoah - iE(K]
ve' <L,t E
For any fixed >> O and å E (0, 1), with probubility at least 1 - -, 4|Eg| 3 + E
vdl log
(g)( - g2(22)ll2 2 ecdd+ AYA, E A - A2112 e.
pje
Vd.
EecclEel
Proof. Take an 5 net of A defined Lemma E.3, and denote by A. (which we slightly abused the notation; note that n-nets are also e-nets since < e). Then we have |A.] s I (2d/ p3c).
Fix Re Ag and consider the stochastic process (X7)+21 adapted to (F+)
:= Vel = (A.) S.L. 7 (A) + (A.)), VE' <
where (Fr)r20 is defined F, af ((Uk(()J(KK Hr+1,)), i.e., the smallest o-algebra containing all revealed history up the end of round т. Then X, is F.-msuuuralle. Using the Multiplicative Azuma-Hoeffding inequality given as Lemma E,4 with Y, = E[X, Fi-1l and 1/2
Pr
Σ BElTEEy
X,
Σ P'CTTEE
1| A Sexp
A AA > 0.
For any l' < l and t E Ev, the distribution u, conditional on all previous history, namely (ie(g] H7 is meesuublle (i.e., follows a F=-r-measurable joint distribution U A(OO, 1)9).. X E A₂ is fixed before the game and thus also - -mesurrbll... Lemma E.3 gives
E|X, Fr-1] Pr AE B. s.t. argmaa (ur,i - X CT.s)) # argmax (ur,i - X! cT.)) KE(K]
<E[K]
< K2eee
Ve < E
where the Pr is taken w.r.. the randomness of generating u, according to the conditional joint distribution u, UiE(oju[K] Her and the independent sampling of c, ~ C.
Hence, for any failure probability 8 > 0 that we determine later, with probability 1 - 8.
Σ
1 B. S.L. 7 (A) (
Σ 111 KZee, + 4log
1
Taking Union Bound over d Ac, with probability - 6 I11 (2d/ pfe). the above good event
holds for all X E A at the same time. Consider any \1 A2 E A such that ||>| - >a2la S 2vd which immediately gives | delli c. Take X A. such that A (A,) (recall that A, is in fact a -net), we therefore have | Aellı S e, which means \ d2 E (X..) Thus
Egl. Keee. 4log 1 Vd,
Σ (0- ( PECTEEE
Σ (--c
<
2
Σ C'l
ectTEEy
TThis EX B, (A.) ) is pivotal because we cannot afford to take Union Bound over all X E B. (A.)). We call this step "uniform smoothness". since it ensures the similarity holds uniformly in the neighborhood of Ac.
43

---

12 |Ai >2212 _
6
w.p. II
(2d pc)):
2vd
j=1
where we used the fact that Cr, E [0, 1]dt for any [K]. This ensures that
EEcl
1 KPee, + 4log 8) vd
(( @e(22)ll2
leal
Exceleel
Pcce
2/E2|KK EE vd + 4|Ex/ log 1 Vd,
E || A2/12 S 2vd
Σ Ee EEr
with probability at least - - - (2d/ pzc). Substituting d' 2v7 the conclusion.
(2d/ p3c) gives and 8 8 =
D.3.3 Stability Term Bounds in O-FTRL-FP
Lemma D.6 (Difference between {iehee, and (ifheEs)) For any epoch & [L].
E
Σ
(p ct.i.) (Xe)
S (d (dd+3) +) Eel + N
NEE
where Ne is defined as in Lemma D.I:
N₂ = 1 + 4K2 Peelee || + 5 loggEEl + -1 11)11++11111)11111]]))11
and we recall that
-- - (A argmax (Ua,s - X cl..).
ge (A) = 113l
E V.-Vee ~C
(E[K]
E|ll - 9 (1)) i.e., the squared er-error of [Ee] random vectors from their mean which is of order [Eg] because they are i.i.d. We then relate it to EEll, (p c,,i.) 0 (Ax [|2] by utilizing the similarity between (iz hee, and Hee, that we derived in Theorem C.S.
Proof. In this proof, we first control
Step 1: Control EI (p- C₁3t g7 (1))
Recall the definition of (ot hetry from Eq. (9);
argmax
(ve. cl.), Vt E Ec,
=E[K]
and noticing that v, and e₁ are i..dd. samples from and C, have PDF(1t) PDF (Xt)) for all t E &g. Therefore.
E c c
1
E c.
[3 9/
(Ae). Vt Ee,
where the last equation is precisely the definition of 07 (Ae). Since for d-dimensional random vector X, [[[]X - [[X][3] = E|
E[X,])?] = dd Var(X,) Tr(Cov(X)) where Tr the
trace and Cov is the covariance matrix, we have
E
Ce-
- 9i (A,) = Tr (1E6l
Cov V.-Ve
(p- C,,7 S EE
1EE.
using the fact that it's are independent from each other and that p and C,,i are all within [0, 1]d. Step 2: Relate Eies (p c,37) to Eies, (p Cr,s.). Recall Eq. (16) from Theorem C.5:
Pr
Σ 1l
3 No < 11
(32)
3EE2
44

---

where No = 1 4K c 1|1 - log, 4(1+ + lle 11=))|
As (p c(,) E 1,, we have
E
Σ (p-
-,,,,)) -
KEE2
2
)
S E
Σ( (p C(,5g)
96 (X+)
+E
1(
1EE
MEEt
E
< EEld No
where the last term considers the failure probability of Eq. (32), in which case the trivial bound (Eres, 1 [iv * 22 [ Rearranging gives the desired conclusion.
Lemma D.7 (Empirical Estimation). For any l [L]. and å E (0, 1), with probability 28,
log _ + >
log d Pyc
| (A) (A) s 3d|Eap (K2
+ 6dlEz/2
Σ 8 Eeel
= δ
[EE/e? +
[33 2
log Σ log
d
d PJc )) AY
Σ =1 Exrl
/=1
where we recall that
(A) = 11el ExellEr e'eTTEE
E
p
(TTE((A)
(A) = argmax (Mr,5 - A xc..)):
{E|K]
g7
|&el v. v.-Vean
(p - -..77-12))
(A) argmax (Vo,) - -TTco,)
iE[K]
Proof. contrast Lemma D.6 where we directly applied concentration bounds at realized dual iterate Ae, here cannot proceed in the same way. The reason is that the value samples used to compute gi (Ae) were drawn in the past, and X itself computed based on reports dependent on these values. As result, conditioning the event that g (Ae) x gi (Ae) introduces dependence on future information from the perspective those past realizations, violating valid conditioning.
To overcome this, we establish uniform concentration over all A E A by discretizing the domain. Specifically, we construct an c-net A, A and first show that for every X E Ac, the approximation (x,) ~ 02'AA (A.) holds with high probability. We then extend this guarantee to all À E A by considering the stochastic process AL B. (Ac) (A) # i (2.)]]e<ctre, where (X.) is the c-radius ball centered at X The proof goes three steps.
Step I: Cover A with e-net. From Lemma E.3, for any >> 0, there exists e-net A, S A of size ((d/e)d), such that every À E A has some X E A, with ||> - >elli S e. We remark that our final guarantee does not have d-exponent, because the dependency
[A. is logarithmic.
Step Yield concentration for any fixed X E A.. Fix A E A.. Let
(p- (p-c.7-(2)) AE' <<, E
E xr = -P= Cr,T((2)) v.vVieree
Since x, only depends v, and c, which are i.i.d. samples from V and C, these vectors are i.i.d. zero-mean, and ensures ||æ||| < /d a.s. since p c, []1, Applying the vector Bernstein inequality (Kohler and Lucchi, 2017, Lemma 18) restated as Lemma E.5 gives:
{
Eestrre
(- Eeel
+
Pr [ (2.) 37 (A.)l2 2 Ed|c = Pr Pr|
2 c < exp
-
Excoler
8d
Pet
45

---

Taking union bound over all X E Ac, we obtain that
d
2²
1 1).
Pr max g (Ae) g (2:)) 2 |EeP3c2 ALEA.
II i=1
Pye
-xp
-2 -22
Eel
8d 4
Ve
F=1
Therefore, for the given failure probability 6, with probability least 1 - 6,
log d
-j=1 log d
(x.) (2:)1
| 4d
PJc
Ay. A,-
(33)
Σ -1= Egll
Step 3: Extend the similarity to all À E A. We now fix X E A. and try to ensure uniform
concentration guarantee for all X E B, (A.). Using boundedness |pp Cr,ill2 S Vd, we have:
(( + =
(A) 9e ( S
Σ
Eect Eel
Pei,TEEp
[ (A) - gi ( d (E)) (ABB(()))
From Lemma E.3, we know
Pr e-V.
st. i * I (e),, a), E A
(34)
where we remark that the AY E (A.) clause is important since it ensures "uniform smoothness" in the neighborhood of X, If instead fix À and its corresponding A, and apply concentration to this specific X, we need to do an prohibitively expensive Union Bound afterwards; see also Footnote 6.
Hence the error between 9 (A) and 9 (7.) is bounded by
max (A..
g (A)
gi (2)) < d&A (K²c a.s.
(35)
For the error between D. (A) and g (X.). consider stochastic process (X+) adapted to (Fr)
X, = 1 E B, (x)) s.t.
75 (A) # (A))), AE' < f, E
where F, = ((Uik()) +,,+, = a (Ui...., Ur U1,... Ur CI...., Cr, 27, i.....,,.PP..................... Pi..... PPr) the smallest o-algebra containing generated history up the end of round r.? Then X, is F,, measurable, and we have
E[X, Fr-il=
Pr VnV.
aIx B.le) s.t. + *T()) & (R(c..c).
where the last step uses Eq. (34). Applying Azuma-Houee Hoeffding to martingale difference sequence (X, E| F.-1lBexx, we know for any >
Pr Evctres, 1B3x E (A.)) st. (A) + (A)) K2e6 &Reeo t S exp
-20 2 Σ EE
E1-1 12
p=11
Applying a Union Bound over all X E A, and recalling the expression of g - 9/ (>x)
Pr (3 E A (A) क. (AJI (E + tc]3} s II
d
(222 Σ Exl
exp
Pge
"In fact, the X, 's here are i.idd. variables since v, ~ V and c, ~ C' are independent. However, when controlling ! (A) ge (2 in Lemma D.8, since reports u, can be history-dependeut, to make Lemma E.3 still applicable we need make sure the conditional distribution of reports H, is m-mesurrabll..
46

---

Therefore, with probability at least 1 ò, we have
v log 8 Σj=1 log d Dje
gi () 98 (2.) s d/Eep K20eat
vd, E (A.))
EE= 1eel
(36)
Final Bound. Via Union Bound, with probability 1 - 20, Eqs, (33), (35) and (36) are all true and 0 D2 (A)1 3d/E (KKee.)) -dle log 1 +
دi= log
d
Pac
AYAΛ
[3
This finishes the proof.
Lemma D.8 (Untruthful Reports). For any l [L], and 6 E (0, 1), with probability 46,
19 (A) 9. (2)
Clog,-1 (1 4(1 4(1 + 1p " 1 488-1 + 40ecllp 1111 + (lg 3 + EØ= log d
$ 2
p.c
20 1E
log 1/2
Σ/= log
d
+Ad|E/?
(K'eec)*
Aje
Σr=1 Erl
log Pjc )) AA
[8/12
=
|80/302 +
T++ log
[rrl
where we recall that
Te (A) EEel Ex
1
Σ e'CTTEE
p c-50(2))
(A) argmax (ur,i - A ATr.:): <E[K]
g (A)
1Eal
1
E E'cTTEEE
(p (
(A) argmax (Ur A dCc,,)..
Exceler
sE[K]
Proof. We now bound the impact of untruthful reporting, specifically the difference between past reported values and true values v,. Similar to the reason in Lemma D.7, we cannot directly apply concentration inequalities to A which unmeasurable when the reports are generated. Therefore, we still consider an e-net A, of A, ensure that 9 (X,) ~ (X,, for all X, E A,, and then extend it to all X E A via Chernoff-Hoeffding
inequalities.
Step I: Cover A with an e-net. From Lemma E.3, for any >> 0, there exists an e-net A. C A of size ((d/e))*), such that every À A has some A E A. with || >xlli We remark that our final guarantee does not have d-exponent, because the dependency on |A,] is logarithmic.
Step 2: Yield concentration for any fixed X A.. Fix X E Ac- From Lemma C.3, which underpins the INTEREPOCH analysis Theorem C.5, we know that for any previous epoch E E,
the event |uy. 2,,1 2 [zll occurs in only ((1) rounds (with 5 E Ex. with probability at least
1 E Following the approach in Lemma C.4, we now leverage the smoothness of costs in Assumption 3 in combination with Azuma-Hoeffdiin inequalities to conclude that 9 (>.) 9 (A.).
Formally. to compare g (Ae) and g (A.). we need only control the number of previous rounds such that 1 (2e) + Th (2)) We decompose such events by whether large misreports happen:
Σ
F S
Σ 3i [K] s.t. |uc, Vr,al 2
TEE
TEL
2
Σ
1 3iijE [K] s.t. (V7 - - - X. - cr.s) E
0.
(37)
Ep
47

---

where the second term plugs |ur, - u
E Vi [K] into definitions of (X,) and (A.)
For the first term, we use the following inequality which appeared as Eq. (13) in Lemma C.3:
Pr
Σ
|
ural
1 E31
2 c
S 2( + 21p (1))
2K| 1 7-
Ae < <l
rEEp
For any fixed failure probability 8 E (0, 1), for every l' picking so that the RHS is & gives
Pr
Σ
|
Uz
1
2 Elog, (1 4(1 ||p
-1- 1 to 66-1) S.
Ee
E'cETEEE
For the second term, under Assumption 3 that PDF(A. Cr,s) is uniformly bounded by cc. Vi E [K],
2
Pr - Un.) - (crr -
E
0,
to Delli, vi #ije [K], l <L,T Er.
Ep
E3
Although are now standing epoch e, the e-nets are fixed before the game (as it only depends on A). Hence, the indicator X, := [[(,, - Ur.5) - AT(c, - Cr,)) E [0, | ]1 is indeed F,- measurable back in the past when E Er and L' L, where (Fr)r20 is the natural filtration F, o (X1,... .,)). ). Thus, applying multiplicative Szuma-Hoeffdee inequality in Lemma E.4 to the martingale difference sequence (X, - E[X, Fe get
2
I
Pr
1 Σ PELTEEE
X
Σ PeeTEEE
E|X, [F + 24 S exp(-AA,, VAER.
Since X, only involves e- and e, which are ii.d., we know E[X, lee <elll dellAell Setting the RHS |A,KK and taking Union Bound over X E Ac, we have
s
{
2
Pr
max A.EA
Σ
(UT, Ut.)) - (CT. -to)
0.
PettFEEN
Σ )
d
2 4lcellp +
log
+
log
Vi j E
[K].
K2
Pse
j=1
Using another Union Bound over all + E [K] and plugging it back into Eq. (37), we get
Σ
(
max A.EA. ecetTEE
1 + log d PjC
d
< Eflog, (1 (1+4(1+ || ||)) 448511 -deell="*11 +4 log ④
Σ
with probability at least 26. Therefore, with probability at least 28, we have
Eel
max | (A.) 77 (2,)l <d x.er,
Σ
(2)( + +2
ErcelEcl
d
(logy-1 1 |+4(11 + 11p 101111111 (1) .40-11 + +1ecolpp 1111
5 [
d +4 log + > log
d
) 2
PjE
j=1
48

---

where the first inequality uses the boundedness of -
Step 3: Extend the similarity to all À E A. After yielding the similarity that 9. (X,) (Ace)) for all X E A., we extend to all E A using the arguments already derived Lemma D.7. Recall from Eq. (36) that already proved that with probability 1 d,
2
V log +
E/= log d Ajr
g ())
T. ( & d&&
AA A.EEAEEBB.
EE=11Ee1 EErl
Using exactly the same arguments (see Footnote 7 for the reason why Lemma E.3 still applicable when reports {u, CE, be history- deeteredd) with probability 6,
log + EE= log d
V
| (X) De ( d
Rea+
Pjc
AA A
-r== [3
Final Bound. Putting the three incqualities together and taking Union Bound,
sup 19 (A) 92 (A)l
AEA
elog,-1 (1 + 4(1 10 11 (1) (488--1-)-00))) 4etelll 1|1 + (log + log d p.* 2
$ <dEii?
1E-1
log 1/ 5d log Psc
(Keee)) +AdlEr?
: w.p. 1 45.
E1-1 Erl
This completes the proof.
E Auxiliary Lemmas
We first include several classical online learning guarantees.
Lemma F.1 (FTRL Guarantee (Orabona, 2019, Corollary 7.7)). For a convex region X, an 1-strongly- convex regularizer T X R w.r.t norm II-Il with min Va 0, sequence of convex and differentiable losses fI, 12...,,R.. a sequence of learning rates n 2 2 ... 2 TJ 2 0,
Ty argmin #EX
Σ f((x)+
1 ((()) dr
Vr 1,2, 1.2,..., R.
have the following regret guarantee where ||.11 is the dual norm of ||-||:
R
(xx')
R
Σ -
2 mr (
Σ 1=1
Vx² E X.
1=1
Lemma F.2 (O-FTRL. Guarantee (Orabona, 2019, Theorem 7.39)). For a conver region X, 1 1-strongly-convex regularizer V X + IR w.r.t. some norm ||-|| with mingex (x)) = 0, a sequence of convex and differentiable losses f1, f2..... a sequence of learning rates m 2 122
VR 2 0, a (stochastic) prediction sequence (sr: X + Rree that is F,- -----uraaabblle (where (F,)e is the natural filtration that J,, fe.. f.)). and
Ei + 2x(x) + 1 L.((s) Tre
Ct argmin EEX
Vr = 1, R,
we have the following regret guarantee where
||. is the dual norm 11-1::
Σ (fx(x))) - fx(x))) < ((xx))
R
R
m -fa f.) Væ E
2
r=1
49

---

We now present covering of the dual variable space A. Lemma E.3 (Covering of Dual Variables). For any fixed constant > O, there exists a subset A, of
A
X 10 that has size no more than (d/ and ensures
A AYE A. S.f. I| della Sc.
Furthermore, for any c-net A. such that A S UX.EA. (e()e) where B.(d.) A X,ll1 S E) is the neighborhood of X, Ao, under Assumption have for all de Ar and any distribution U E (10,1) that
EE Bc(e) s.t. argmax(u; A c;)) * argmax(u; Ncai) Pr uilleer
- (K2(c.
sE[K]
sE[K]
Proof. The first claim is standard from covering arguments and the fact that A 8 30-100, bounded. For the second part, we make use Assumption 3: For any fixed * E [],
Pr { E (aee) s.t. (u, A c, > Uj X/ (u: A'c < <u A c,))
u-Mleer
S
{0= (u; - x. - (u, 2,) < Sc. u-lllar
Pr
where the first inequality uses (A, 5 |A -call- S e for all X E (A.).). while the second uses Assumption and the independence of e; and cj: If two independent real- valued random variables X Y have their PDFs f'x and fy uniformly bounded by e.. then
fx-r(=)= = I
30 fx(2 (u)dy S co J fr fr S cc. E
Applying Union Bound to the K2 pairs of (i,j) E [K] [K] gives the second conclusion.
Finally, introduce some martingale or random variable concentration inequalities.
Lemma E.4 (Multiplicative Huum-HHoffdding Inequality (Koufogiannakis and Young, 2014, Lemma 10)). Let T be a stopping time such that [ co. Let {X,)221 and (Ye)e2) be two sequence of random variables such that
[X, vils1ss. X Yt
Σ nst
X,, ΣV
Y TCt
50, VISIST
then for any E [0, 1] and A RR we have
T
(1 - (1-6)
x, x
Σ Y + A S eeep(=eAh
Lemma E.5 (Vector Bernstein Incquality (Kohler and Lucchi, 2017, Lemma 18)). Let Φ Ø2 Fy
be independent random d-dimensional vectors such that they are zero-mean E[ 0, uniformly
bounded ||x l2 < C a.s. for some > O, and have bounded variance B||| || < o² for some
0. Let z Di=1 Dú, then
d² C + +1) VO < (-m 800
2
Pr[112112 2 20) S exp
50


Reviews:
[{"review_id": "xLuy3L01Fl", "reviewer": "Reviewer_hUTT", "summary": "This paper studies the dynamic allocation of reusable resources to strategic agents under multi-dimensional long-term cost constraints. Since standard primal-dual methods are vulnerable to agents' strategic misreporting, to address this, the authors propose a novel incentive-aware mechanism designed to be robust against such behavior. Through a careful and detailed analysis, they show that the proposed mechanism achieves sublinear regret of $\\mathcal{O}(\\sqrt{T})$, matching the performance of allocation approaches that assume non-strategic agents.", "questions": "1. What is the rationale for choosing the dual region $\\Lambda$ as $[\\boldsymbol{0}, \\boldsymbol{\\rho}^{-1]}]$?\n2. Are the two approximations for solving Eq.6 computationall efficient in practice?", "limitations": "see Weaknesses.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The problem is well-motivated, and the gap in the existing literature is clearly articulated.\n2. The paper is well-written and easy to follow. The intuition behind the proposed mechanism is clearly explained and supported by detailed proofs in the full version.\n3. The theoretical analysis is technically deep and appears to introduce several novel ideas, such as the decomposition of regret into PrimalAlloc and DualVar, and the use of different behavioral models (Model 1 & Model 2) to facilitate the analysis.\n\nWeaknesses:\n1. There may be a tractability issue in the fixed point problem in Algorithm O-FTRL-FP, as acknolwedged by the authors. Although they propose two approximation solutions for numerical purposes, this issue remains unresolved at a theoretical level.\n2. The proposed incentive-aware algorithm is tailored to a special allocation rule in which the payment the planner offers depends on the 2nd-highlight value $\\max_{j\\neq i_t}\\tilde{u}_{t,j}$. This may limit the algorithm's applicability to broader settings or alternative allocation mechanisms.", "was_revised": true, "final_justification": "I believe the studied problem is interesting, and the techniques used for the analysis are novel and deep. I have no further questions and support acceptance.", "rebuttal": "Thank you for your detailed review! Here are our responses:\n\n---\n\n**W1 & Q2 (Computational Efficiency of Fixed Point Problem).** Indeed, our proposed O-FTRL-FP does not directly allow a computationally efficient implementation. However, it\n1. **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.\n1. **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.\n1. **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.\n1. **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.\n\nThank you very much for raising this concern. We will move more discussions from the Appendix to the main text in the revision.\n\n---\n\n**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.\n\n---\n\n**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.\n\nFor 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.\n\n---\n\nWe thank you once again for such a valuable review of our paper. We are more than happy to answer any further questions."}, {"review_id": "th0ffGNWh9", "reviewer": "Reviewer_Bw7E", "summary": "This paper studies the dynamic allocation of reusable resources to strategic agents under multiple dimensional long-term cost constraints. The goal is to design mechanisms to determine the allocations that achieve good efficiency guarantees (i.e., maximizing the social welfare) and satisfy the long-term constraints. Moreover, the mechanism is required to be robust to strategic manipulation of strategic agents. This paper develops a novel “incentive-aware” mechanism that makes primal-dual methods robust to strategic behaviors.", "questions": "In addition to the incentive compatibility and the experiment setup, a few questions below that I would like to see answered.\n \n1. In Line 37, it is claimed that in the classic mechanism the agents can improve “their individual utility at the expense of feasibility”. I do not see how this happens in Figure 1, because it looks everything is feasible.\n \n2. In Line 162, the paper claims that “this structure penalizes misreport by imposing a direct utility loss when.....”. I also do not see how this happens.", "limitations": "N.A.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The authors are the first to consider the strategic environment in the setting of dynamic allocation of reusable resources under multi-dimensional long-term cost constraints.\n2. The new method proposed in this paper is proved to guarantee sublinear regret with respect to offline benchmark (sublinear in the sense of number of rounds T), satisfy all cost constraints, and admit a PBE (perfect Bayesian equilibrium).\n3. Compared with traditional standard primal-dual algorithms, simulation experiments demonstrate that the new method has better social welfare, and the agents are less likely to misreport.\n \n \nWeaknesses:\nThe presentations on the key concepts and the contributions are not clear enough.\nFirst, the paper uses the terms “incentive-aware” and “incentive compatible” interchangeably, but without any specific definition or explanation on these two. Do they have the same meaning? Usually, an incentive compatible mechanism means that truthful reporting is a (weakly) dominant strategy for all agents. However, this paper only proves the existence of a PBE for the game induced by the proposed mechanism (Algorithm 2), where it’s known that PBE is weaker concept than incentive compatibility.\n \nSecond, the experiments are limited and not that convincing. I have seen lots of limitations, like it only simulates the behaviors of 3 agents, 1 dimension constraint (while the paper claims multi-dimenisonal constraints), and T=1000 rounds. N=1000 trials mean the 1000 epochs?\nThe setup is a bit insufficient to support the claims (like a better social welfare, less misreports, etc.). I am also not clear why to assume all agents use the Q-learning as their strategies, which is not justified, because the self-interested agents can choose any strategy to maximize their utility.\n \nSome other issues: The figure 1 on page 2 conveys less meaningful information, because the reader does not know the setting yet, for example, what is the planner average cost?\n \nIn Abstract, O(\\sqrt{T}) social welfare regret is unclear because we do not know what T is.\n \nTheorem 3.1. The math symbol of R and B are different from (3).", "was_revised": true, "final_justification": "I am satisfied with author responses to my questions but not sure about the final revision quality of the paper. However, given other reviewers’ support, I believe the authors can do a good job.", "rebuttal": "Thank you for your careful and insightful comments! Here are our responses:\n\n---\n\n**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.\n\n> Additional References:\n> * Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni, and Song Zuo. Incentive-Aware Learning for Large Markets. In WWW 2018: The 2018 Web Conference, 2018.\n> * Negin Golrezaei, Adel Javanmard, and Vahab Mirrokni. Dynamic incentive-aware learning: Robust pricing in contextual auctions. Advances in Neural Information Processing Systems, 2019.\n> * Hanrui Zhang and Vincent Conitzer. Incentive-Aware PAC Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 2021.\n\n---\n\n**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.\n\nMotivated 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.\n\n---\n\n**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.\n\n---\n\n**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.\n\nAs 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:\n1. “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).\n2. “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.\n\nThus, 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.\n\n---\n\n**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.\n\n---\n\nWe thank you once again for such a valuable review of our paper. We are more than happy to answer any further questions."}, {"review_id": "TnJ8LK09p3", "reviewer": "Reviewer_EKwN", "summary": "This papers studies the problem of allocating resources (to agents) in an online fashion under cost constraints, where the agents can misreport their evaluations. The objective is to maximise the social welfare, that is, the total utility of the agents, while both incentivising the truthfulness of the mechanism and satisfying the overall cost constraints. The authors propose a dual algorithm which employing techniques such as epoch-based learning and random exploration attains $\\widetilde{O}(T^{2/3})$ regret (with respect to Perfect Bayesian Equilibrium) with a computationally efficient algorithm. The bound can be improved to $\\widetilde{O}(\\sqrt{T})$ but a fixed point problem must be solved for each epoch.", "questions": "1. Could you better discuss the computational complexity of the O-FTRL-FP update (both for the actual update and the approximated one explained in the appendix) ?\n2. I would like a better comparison between the setting studied in this paper with respect to the standard online allocation one described in (Balseiro et al. 2023). Specifically, why this setting should be of greater interest than the standard one?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is clear and well-written. The results seem to be both novel and interesting, and overall, the key ideas on the analysis are easy to follow. I particularly enjoyed Section 4 since I believe the authors did a good job of providing the key components of their analysis.\n\nRegarding weaknesses, the discussion on computational complexity to find the fixed point could be improved. While the discussion in the appendix is more detailed, I suggest incorporating some parts in the main. From an algorithmic perspective, the paper indeed exploits existing ideas such as the primal-dual scheme, the payments rule, and optimistic FTRL. Overall, I do not believe this is a huge problem since the way these ideas are combined is interesting and, to the best of my knowledge, novel.", "was_revised": true, "final_justification": "The responses did not particularly change my evaluation of the paper. Overall, to the best of my knowledge, the results are new and the technical novelty is sufficient. Thus, while acknowledging that the presentation could be improved as pointed out by Reviewer Bw7E, I support the acceptance of the work. Nonetheless, I strongly encourage the authors to incorporate in the final version of the paper a precise comparison with both the stochastic and the adversarial online allocation literature.", "rebuttal": "Thank you for your insightful review! Here are our responses.\n\n---\n\n**W1 & Q1 (Computational Efficiency of Fixed Point Problem).** Indeed, our proposed O-FTRL-FP does not directly allow a computationally efficient implementation. However, it\n1. **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.\n1. **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.\n1. **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.\n1. **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.\n\nThank you very much for raising this concern. We will move more discussions from the Appendix to the main text in the revision.\n\n---\n\n**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.\n\nFor 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.\n\n---\n\n**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**.\n1. **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).\n1. **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.\n1. **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.\n\nTherefore, 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.\n\n> Additional References:\n> * 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.\n> * 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.\n> * 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.\n> * Sebastian Perez-Salazar, Ishai Menache, Mohit Singh, and Alejandro Toriello. Dynamic Resource Allocation in the Cloud with Near-Optimal Efficiency. Operations Research, 2022.\n> * 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.\n\n---\n\nWe thank you once again for such a valuable review of our paper. We are more than happy to answer any further questions."}]

Author rebuttal:

Meta-review: **Summary**

This papers studies the problem of allocating resources (to agents) in an online fashion under cost constraints, where the agents can misreport their evaluations. The objective is to maximise the social welfare, that is, the total utility of the agents, while both incentivising the truthfulness of the mechanism and satisfying the overall cost constraints. The authors propose a dual algorithm which employing techniques such as epoch-based learning and random exploration attains regret (with respect to Perfect Bayesian Equilibrium) with a computationally efficient algorithm.

**Strengths**

The problem introduced in the paper is interesting and relevant for the literature on online resource allocation.

**Weaknesses**

The presentation and clarity could be improved, as noted by some Reviewers.

**Decision**

All the Reviewers agree that the paper deserves acceptance to NeurIPS. Thus, I recommend **acceptance**.
Decision: Accept (poster)