Online Allocation and Learning in the Presence of Strategic Agents
Authors: Steven Yin
Shipra Agrawal
assaf zeevi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Online Learning
Incentive Compatibility
Resource Allocation

Abstract: We study the problem of allocating $T$ sequentially arriving items among $n$ homogenous agents under the constraint that each agent must receive a prespecified fraction of all items, with the objective of maximizing the agents' total valuation of items allocated to them. The agents' valuations for the item in each round are assumed to be i.i.d. but their distribution is apriori unknown to the central planner.vTherefore, the central planner needs to implicitly learn these distributions from the observed values in order to pick a good allocation policy. However, an added challenge here is that the agents are strategic with incentives to misreport their valuations in order to receive better allocations. This sets our work apart both from the online auction mechanism design settings which typically assume known valuation distributions and/or involve payments, and from the online learning settings that do not consider strategic agents. To that end, our main contribution is an online learning based allocation mechanism that is approximately Bayesian incentive compatible, and when all agents are truthful, guarantees a sublinear regret for individual agents' utility compared to that under the optimal offline allocation policy.

Online Allocation and Learning in the Presence of Strategic Agents
Steven Yin
Department of Industrial Engineering and Operations Research Columbia University
New York, NY 10027
sy2737@columiia edu
Shipra Agrawal
Department of Industrial Engineering and Operations Research
Columbia University
New York, NY 10027 sa3305@columbia edu
Assaf Zeevi Graduate School of Business Columbia University New York, NY 10027 assaf columbia. edu
Abstract
We study the problem of allocating T sequentially arriving items among homo- geneous agents under the constraint that each agent must receive a pre-specified fraction of all items, with the objective of maximizing the agents' total valuation of items allocated to them. The agents' valuations for the item in each round are assumed to i.i.d but their distribution a priori unknown to the central planner. Therefore, the central planner needs to implicitly learn these distributions from the observed values order pick good allocation policy. However, an added challenge here is that the agents are strategic with incentives to misreport their valuations in order to receive better allocations. This sets our work apart both from the online auction design settings which typically assume known valuation distri- butions and/or involve payments, and from the online learning settings that do not consider strategic agents. To that end, our main contribution is an online learning based allocation mechanism that is approximately Bayesian incentive compatible, and when all agents are truthful, guarantees sublinear regret for individual agents' utility compared to that under the optimal offline allocation policy.
Introduction
A classic sequential resource allocation problem is to allocate T sequentially arriving items to agents, where each agent must receive a predetermined fraction of the items. The goal is to maximize social welfare, i.e., the agents' total valuation of the items allocated to them. This problem is non- trivial even when the agents' valuations are stochastic and i.i.d. with a known distribution, the main difficulty being that the allocations must be performed in real-time; specifically, an item must be allocated to an agent in the current round without knowledge of their future valuations.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

A more challenging (and quite useful) extension of the problem which has been the focus of recent literature considers the case where the distribution of the agents' valuations is apriori unknown to the planner. In such settings, algorithms based on online learning can be used to adaptively learn the valuation distribution from observed valuations in previous rounds, and improve the allocation policy over time (see ( 10 5 for some examples). However, these mechanisms implicitly assume that the agents report their valuations truthfully, so that the mechanism can directly learn from the reported valuations in order to maximize the social welfare.
Many practical resource allocations settings do not conform with the truthful reporting assumption. In particular, selfish and strategic agents may have an incentive to misreport their valuations if that can lead individual utility gain (possibly the expense of social welfare). Hence, an allocation policy that does not take such misreporting incentives into account can incur significant loss in social welfare in presence of strategic agents. For example, consider a simple setting with two agents whose true valuations are i.i.d. and uniformly distributed between 0 and 1. That is,
X1, X2 Lid. Uniform[0,1]
Each agent is pre-determined to receive an equal fraction of all the items. The optimal welfare maximizing allocation policy is to allocate the item to the agent with higher valuation in (almost) every round. This policy results in T/3 expected utility [ > X2)/2) for each agent, and a social welfare of 2T/3. However, suppose that the first agent chooses to misreport in the following way: the agent reports a high valuation of 1 whenever her true valuation is in [0.5, 1] and a low valuation of 0 whenever her true valuation is in [0, 0.5]. Assuming the other agent remains truthful, this will lead to the first agent receiving all the items in her top 1/2 quantile, and therefore significantly increased utility of 38/8 (E[X) X, > 0.5l/2) compared to T/3 under truthful reporting. The social welfare however, goes down to 5T /8 in this case. Thus under the optimal policy, each agent has an incentive to misreport her valuations in order to gain individual utility. The incentives to misreport may be further amplified under an online learning based allocation algorithm that learns approximately optimal policies from the valuations observed in the previous rounds. In such settings, the agents can potentially mislead the online learning algorithm learn a more favorable policy over time by repeatedly misreporting their values.
Motivated by these shortcomings, in this paper, consider the problem of designing online learning and allocation mechanism in the presence of strategic agents. Specifically, we consider strategic agents. The problem proceeds in T
the problem of sequentially allocating T items rounds. In each round = 1, 1,.... T, the agents' true valuations X i = 1, 1,.... n for the 8th item are generated i.i.d. from distribution F a priori unknown to the central planner. However, the central planner can only observe value Xx,, reported by each agent i, which may may not be the same as her true valuation X for the item. Using the reported valuations from the current and previous rounds, the central planner needs make irrevocable decision of who allocate the current item. The allocations should be made in a way such that each agent at the end receives a fixed fraction pt of the T items, where Pf > 0, Σi= p 1. The objective of the central planner is to maximize the total utility of the agents, where utility of each agent is defined as the sum total true valuations of items received by the agent.
Our main contribution is a mechanism that achieves both: (a) Bayesian incentive compatibility, i.e., assuming all the other agents are truthful, with high probability no single agent can gain significant utility by deviating from the truthful reporting strategy, and; (b) near-optimal regret guarantees, namely, the utility of each individual agent under the online mechanism is "close" to that achieved under the optimal offline allocation policy.
Organization After discussing the related literature in some further detail in Section 2 we formally introduce the problem setting and some of the core concepts in Section 3 Section 4 describes our online learning and allocation algorithm and provides formal statements of our main results (Theorem [nd Theorem Section 5 and Section 6 provide an overview of the proofs of the above theorems. All the missing details of the proofs are provided in the appendix. Finally, in Section 7 we discuss some limitations and future directions.
2

---

2 Literature review
Our work lies at the intersection of online learning and mechanism design. From online learning perspective, our setting is closely related to the recent work on constrained online resource allocation under stochastic i.i.d. rewards/costs (e.g., [TO] 2 I g 5J). However, crucial assumption in those settings is that the central planner can observe the true rewards/costs of an allocation, which in our setting would mean that the central planner can observe agents' true valuations of the items being allocated. Our work extends these settings to allow for selfish and strategic agents who may have incentives to misreport their valuations. As discussed in the introduction, unless the online allocation mechanism design takes these incentives into account, selfish agents may significantly misreport their valuations cause significant loss in social welfare.
Incentives and strategic agents have been previously considered in online allocation mechanism design, however, most of that work has focused on auction design where payments are used as key mechanism for limiting rational agents' incentives to misreport their valuations. For example, Amin, Rostamizadeh, and Syed (3) study posted-price mechanism in repeated auction setting where buyers' valuations are context dependent. Golrezaci, Javanmard, and Mirrokni (12) extend this work to multi-buyer setting, using second-price auction with dynamic personalized reserve prices. Kanoria and Nazerzadeh (17) study a similar problem in a non-contextual setting. (There is also a significant literature that studies learning in repeated auction settings from the bidder's perspective. Since our paper focuses on the central planner's point of view, we omit references to that literature. ) All of the money/payments as a key instrument for eliciting private information about the bidder's ' valuations for the items. In this paper, we are concerned with online allocation without money, and the goal is to maximize each agent's 's utility.
works are concerned with maximizing revenue for the seller, and use
Recently, there has been some work studying reductions from mechanism design with money to those without money. Gorokh, Banerjee, and Iyer [13] provided a black-box reduction from any one- shot, BIC mechanism with money, an approximately BIC mechanism without money. However, their reduction relies crucially on knowing the true value distribution of agents and therefore is not applicable to setting. Procaccia and Tennenholtz [18] consider specific (one-round) facility allocation problem and explicitly formulate the idea of designing mechanisms without money to achieve approximately optimal performance against mechanisms with money. Subsequently, there is series of papers that extended the results on mechanism design without money in a single shot setting, when the bidders' value distribution is unknown [14 I6
8). These papers either use a very restricted setting with just two agents, or use very specific/sipple valuation functions for the agents. Even in these basic settings, they show that the best one can hope for is constant approximation to what one can achieve with a mechanism that uses money. It is not clear what kind of regret guarantees such reductions imply in a repeated online learning setting. Therefore, we do not consider such reductions from auction mechanisms with money to be a fruitful direction for achieving our goals of both incentive compatibility and low (sublinear) regret for our online allocation problem.
Finally, in a repeated allocation settings with known valuation distribution, there are more positive results for truthful mechanism design without money. For example, Guo, Conitzer, and Reeves (15) and later Balseiro, Gurkan, and Sun (7) studied the problem of repeatedly allocating items to agents with known value distributions; both use a state-based "promised utility" framework.
To summarize, to the best of our knowledge, this is the first paper to incorporate strategic agents' incentives in the well-studied online allocation problem with stochastic i.i.d. rewards and unknown distributions. Thus, it bridges the gap between the online learning and allocation literature which focuses on non-strategic inputs, and the work learning in repeated auctions which focuses allocation mechanisms that utilize money (payments) to achieve incentive compatibility.
3 Problem formulation
The offline problem
We first state the offline version of the problem which will serve as our benchmark for the online
problem. There is set of agents, and a distribution F over X == [].. Each draw X F from this distribution represents the agents' valuations of one item: X [X "i....,Ke X.]. We assume that
3

---

the agents' valuations are ii.d., i.e.
F=
A matching policy (aka allocation policy) maps, potentially with some exogenous randomness, value vector X to one of the agents i E {l...., ]. Specifically, given a realized value vector X E "0, (possibly randomized) policy maps X agent n X)) E (1....; nt), with the probability of agent i receiving an allocation given by (x = v). The offline optimization problem is to find a social
policy n² such that each agent i in expectation receives predetermined
fraction P of the pool of items, where p. > 0, >; P. 1. The problem of finding optimal policy can therefore be stated the following
max E
Σ (,I(T(X)
(I)
s.t. (P = P. Vi
where the expectations are taken both over X ~ F and any randomness in the mapping made by policy и given X. Solving the offline problem is non-trivial, as it is an infinite dimensional optimization problem as stated in its' current form in (T. But it turns out to be closely related to Semi-Discrete Optimal Transport, and that the dual of 11 can be written
min EA,, F) = E/ (X+ x.) ATp p AER"
iE(n) (.;
where II, is what is sometimes referred to as the Laguerre cell:
(A()) (X X, A X,
(3)
Let X (F) denote an optimal solution 2
When is clear from the context, omit the distribution
F. It is known that an optimal solution to T is given by the following deterministic policy defined
by the Laguerre cell partition (Proposition 2.1 (4):
π T(x) = for all X E i
(4)
More generally, we will refer to any policy defined by Laguerre cell partition as greedy policy. Definition 1 (Greedy allocation policy). Consider any allocation policy that partitions the domain [0, _ as (A) (as defined in (4) for some X E R". We refer to such a policy as the greedy allocation policy with parameter X.
Note that there are efficient algorithms for solving 2 (see 4) when the distribution F is known. Therefore we will treat (-) as a black-box that can be computed efficiently for any given input distribution F.
The online problem: approximate Bayesian incentive compatibility and regret
We are interested in the case when items are sequentially allocated over T rounds, and that the distribution F is initially unknown. Specifically, in each round / 1, ...... T, the agents' true valuations X, (Xi,,, i ,,..., n.) are generated i.i.d. from the distribution F a priori unknown to the central planner. However, the central planner does not observe X, but only observes the reported valuations X, (Xi,, ,......)) 12) which may may not be the same as the true valuations.
An online allocation mechanism consists of a sequence of allocation policies Ti.... My where the policy Te at time t may be adaptively chosen based on the observed information until before time t:
H4 {X1. X,-1, #1...., T-
(5)
Given allocation policy at time I, the agent i's utility at time / is given by
u. (, X,, .T) = X,, (T, i]
an agent has already reached his target allocation of T items, then he cannot be allocated more items. Note that since the allocation policy may be randomized, for any given value vector X, <x(X) a random variable. To ensure truthful reporting in presence strategic agents, we are interested in mechanisms that are (approximately) Bayesian incentive compatible.

---

Definition 2 (Approximate-BIC) BIC), For an online allocation mechanism, let Te. = 1..... . be the sequence of allocations when all agents report truthfully, i.e., when X, = Xt, and let Ti, t = ,,. be the sequence when all agents except i report truthfully, i.e., X,,t= = X3s, Vj + i. Then the online allocation mechanism called (a. ap-pprooxmeate Bayesian Incentive Compatible if.
for all i =...... n, with probability at least 1 6,
T Σ Lu(X.
T
Σ 1=1
u (X, TT) Sa
Here, the probability is with respect to the randomness in true valuations X, and any ran- domness in the online allocation policy, For the online policy to be approximate-BIc. the statement should hold for all possible misreporting of valuations X + Xix-
Therefore, if a is small, then an individual agent has little incentive to strategize. Note that approximate-BIC also implies that truthful reporting for all agents constitutes approximate- Nash equilibrium. Assuming that all agents are truthful, we are also interested in bounding each individual agent's regret.
Definition (Individual regret). We define an individual agent i's regret under an online allocation mechanism as the difference between agent i's realized utility over T rounds and the expected utility achieved in the offline expected problem. That is,
T Regret, (T) = (X, uu: (x
Xe, ,u,
(6)
[=1
Here T...... FT denote the allocation policies used by the online allocation mechanism round 1 I.......
Note that since social welfare is given by the sum all agents' utilities, a bound on individual regret implies bound on the regret in social welfare of the mechanism.
4 Algorithm and main results
We present an online allocation mechanism that is approximately-BIe and further achieves low regret guarantees individual regret when all agents are truthful. Our algorithm contains two components: a learner, and a detector. Intuitively, the detector makes sure that the mechanism is approximately BIC, and the leamner adaptively learns utility- miliit-iaxmmizing allocation policies assuming truthful agents.
The learner runs in epochs with geometrically increasing lengths. The starting time of each epoch is given by T. = 2* k = 0, 1. which is also when the allocation policy is updated. At the end of each epoch (i.e., at time from all the agents, and uses them to construct empirical distribution of the agents' valuations. The learner implicitly assumes truthful agents its computations. Therefore, since the agents' true valuations are i.i.d., it first constructs a single, -ieedimensional empirical distribution Fú, and then uses it to construct the corresponding n-dimensional distribution F.:
L for epoch k), the learner takes all the previously reported values
1
f.(x) = in
1[x s
i=1
F. P= F.
The learning algorithm then solves the offline problem 2 using F,, and uses the resulting greedy allocation policy characterized by (²FF,) to allocate the items in the following epoch.
In parallel the learner, the detector constructs and monitors, in each time step f, and for each agent i, two empirical distributions. One using the reported valuations from agent i: Fe, and one using the reported valuations from all the other agents: F.. The detection algorithm then computes the supremum between the two empirical CDFs, sup,, (F: (x:).. If this difference is greater than a predetermined threshold A,, then the detector raises a flag that there has been a violation of truthful reporting and the entire allocation game stops. Otherwise, the process continues.
5

---

The threshold A, needs to be chosen such that if everyone is truthful, then with high probability the detection algorithm will not pull the trigger. the same time. if someone deviates from truthful reporting significantly, then it should detect this with high probability. The typical concentration result used in comparing empirical CDFs is the mooretzk--Kiefer -ieeer--iefe--oofoiiiz (DKW) inequality [1]. However, since strategic agent can adaptively change its' misreporting strategy, we cannot directly apply the DKW inequality, which assumes i.i.d. samples. Instead, we use martingale version of the DKW inequality (Lemma [], and use that to choose appropriate threshold A, The details are given Algorithm and Algorithm 2
Algorithm 1: Epoch Based Online Allocation Algorithm
Input: T,
Initialize: À [0,.... 0). 0, K (T). Lx 2t, = 0,....... K; for f x- 1, 2, ...... T do
Observe X, Run Detection Algorithm (Algorithm 2 with sample set (X1..... X,}.
and threshold A, = 64V i log( 256ct
Detection Algorithm Return Reject then L Terminates.
if one of the agents E {l...., n has reached the allocation capacity P then Allocate randomly among agents who have not reached capacity else
L
L Allocate item using greedy allocation policy À
La+1 then
Compute E from samples ( X,) as in
10
II
A < (F)
12
+ k ++1
Algorithm 2: Detection Algorithm
Input: Sample set S = (X X,). threshold A.. for i 4 I,..., .....,, do
Compute F((x) = Ei=1 1[ S x²] as the empirical CDF of the samples collected from
agent i
Compute (x( ((n-1) E.=1 E 1[x æ|] be the empirical CDF of all reported
values from the other agents.
if'sup (z) (x)) 2 A then
Return Reject
Return Accept
Our main results are the following guarantees on incentive compatibility and regret of our online allocation algorithm.
Theorem (Approximate-BIC) Algorithm
8) -ppproxxie BIC.
Since truthful reporting constitutes an approximate equilibrium, is reasonable to then assume that agents will act truthfully. We show the following individual regret bound assuming truthfulness.
Theorem 2 (Iniividual Regret). Assuming all agents report their valuations truthfully, then under the online allocation mechanism given by Algorithm ] regret can be bounded as:
with probability 1 ô, every agent i's individual
4/2
log, T nT
Regret, (T) S
/2 nf log(
}
0 / nnf log(nI/0))

---

Showing approximate incentive compatibility, and then guaranteeing regret under the assumption of truthfulness, is an approach commonly seen in the online mechanism design literature (e.g. Theorem in (7).. In the next section, we describe the high level proof ideas for the main results above.
Proof ideas
We establish that the mechanism is approximately BIC by showing that no single agent has incentive to significantly deviate from reporting true valuations if all the other agents are truthful. The proof consists of two parts. In Step 1, we prove that any significant deviation from the truth can be detected and will lead the mechanism to terminate. In Step 2,3, we prove that in order to achieve a significant gain in utility, an agent indeed has to report values that significantly deviate from the truth.
Proof ideas for Theorem I
Assuming that there is only one (unidentified) strategic agent while all the other agents are truthful, we first show that if the detector does not trigger violation by time / then with high probability, the empirical distribution of valuations reported by the strategic agent is no more than O(1/VE) away from the true distribution (Lemma 3p. The key observation here is that since the agents' valuations are i.i.d,, we can compare their reported values to detect if any single agent's distribution is significantly different from everyone else's. A technical challenge in making statistical comparisons here is that the strategic agent can adaptively change their reporting strategy over time based on the realized outcomes. Therefore, we derive a novel martingale version of the DKW inequality to show concentration of the empirical distribution relative to the true underlying distribution.
Step 1
Step In a given round, given the history, the mechanism's allocation policy a fixed greedy allocation policy given by X. If the distribution of strategic agent's 's reported values differs from the true distribution by at most A, then the agent's expected utility gain in that round, compared to reporting truthfully, is at most O(A). (see Lemma
Step 3
If over / rounds, the distribution of the strategic agent's 's reported values is at most A away from the true distribution, then the learning algorithm will, with high probability find an allocation policy that is at most O(vri) away (in terms of individual utility) from what it would have learned all the agents were truthful instead (see Lemma 2
To understand the significance and distinction between results in Step 2 vs. Step 3, note that strategic agent has two separate ways to gain utility. The first is to report valuations in way that the agent immediately wins more/better items under the central planner's s current allocation policy. However, since the central planner is updating its' allocation policy over time, the strategic agent can also misreport in a way that benefits its' future utility, by "tricking" the central planner into learning policy that favors him later on. Together, Step and Step show that the agent cannot gain significant advantage over being truthful in either manner.
In many existing works on online auctions mechanisms design, where the central planner dynamically adjusts the reserve price over time, these two types of strategic behaviors are in conflict: the agent either sacrifices future utility to gain immediate utility: or sacrifices near-term utility for future utility. The results in those settings therefore often rely on this observation to show approximate incentive compatibility. our case however, since there is no money involved, it is not clear if such conflict between short and long term utility exists. Nonetheless, we are able to bound the agents' ability to strategize. Step 2 bounds the agent's short term incentive to be strategic, whereas Step bounds the longer term incentive to be strategic. Combining these steps gives us proof for Theorem |
Proof ideas for Theorem two main steps.
2 Recall that here we assume all agents' are truthful. The proof involves
Step We show that uniformly for any t 1...., with high probability, the empirical dis- tribution constructed from the first samples is close (within a distance of ((1/Vnt)) to the true distribution F. Here, the factor of 1//n comes from the fact that in each round we observe independent samples from the value distribution, one from each of the agents. This also implies that all the agents are reporting truthfully, then, with high probability, the detector will not falsely trigger.
7

---

Step 2 We show that the allocation policy learned under the empirical distribution estimated from the samples is close the the optimal allocation policy (Lemma 2 Specifically, after rounds if the empirical CDF is at most OLL/Vnu away from the distribution, then each agents' expected utility in one round under the learned allocation policy most /n/t away (both from above and from below) from the optimal. By using epoch based approach we can then show that each agents' individual regret is with high probability bounded by O OVVnT) over the entire planning horizon T.
Proof details
We will now outline our proof in more detail. All missing proofs can be found the Appendix. First we state the following martingale variation of the well-known Dvoretzky- Dvoretzky-Kiefer- soerr--olfoiizz (DKW) inequality| [1] This critical when dealing with strategic agents as they can adapt their strategy over time, resulting in non-independent (reported) values.
Lemma 1 (Martingale Version of DKW Inequality). Given sequence of random variables Y1,..., YT, let Fc oVYi....................... Y;), 1 I,...,T I be the fittatioon representing the information
in the first I variables. Let Fr(v) = Pr(Y, S v(Fr-1), and Pr(y) = + Σi= 1[y S v). Then,
T
128e e TTa2/123
P sup y
Pr(y)
Σ
Fe(y)
2
Next we introduce new notation to to denote the fraction of allocation that j receives under the greedy allocation policy with parameter and valuation distribution F:
Py (F == Px~F(X (A))))
We start with proving Theorem 2. as we will use this to prove Theorem later.
6.1 Individual Regret Bound (Theorem 2
In Algorithm 1 the allocation policy is trained on the empirical distribution constructed from samples. We want to show that this difference between empirical and population distribution will not impair the performance of the resulting allocation policy too much.
Lemma 2. Let G = G X & G", and F = F' .... & F be two distributions over [0. ø|" where the marginals on each coordinate are independent. Suppose sup,, (F' G (z) A Vi. Let X = X² (G), and X = (F)). Then
Ex~ /u, (X X, A)] - Ex X X X"]] < nAF
Proof of Theorem 2
We the DKW inequality to show that the empirical distribution constructed in (7) is close to the true distribution w.h.p. Then use Lemma to show that the allocation policy selected by the learner based the empirical distribution is almost optimal in expectation. The details can be found in the Appendix B
Now we have the main ingredients for Theorem 2
6.2 Smprroximate-Byyesin Incentive Compatibility (Theorem
Theorem 2 says that online utility of each agent cannot be too far below the offline optimum everyone behaves truthfully. In order to show approximate-BIC, it suffices to show that the strategic agent cannot gain too much more than the offline optimum. To do so, we need to bound both the short term and longer term incentives for the agent be strategic.
6.2.1 Short term incentive
We start with bounding the short term strategic incentive. We first show that if agent reports from an average distribution that is very different from the truthful distribution, then with high probability Algorithm 2 can detect that. Note that given the strategic agent's 's strategy in a given round, his reported value is drawn from distribution potentially different from F.

---

Lemma 3. Fix time step t. Let A 6 log( (1)))) Let Fss -....,, be the strategic agent's
reported value distributions in each time step given the history, i.e, F2(2)) = P(X.., S x+H{,) If the average distribution F ; - ===11, Fs is such that sup,, -(x)) 2 A, then Algorithm 1
will terminate at or before time t with probability at least
Next, we show that the agent restricts the reported distribution to not deviate more than A from the true distribution (so that the deviation may go undetected by the detection algorithm), then the potential gain the agent's 's utility compared to truthful reporting is upper bounded by æA. This bounds the agent's s incentive to be strategic.
Lemma 4. Fix a round t and a single strategic agent i, so that the remaining agents are truthful, i.e., Xj.t- = Xja, Vj + i, Let F-(.) denote the marginal distribution of values Xi, reported by the stralegic agent time conditional on the history, i.e.,
F,(x) == PXX,, S x xlH)
Suppose that sup, [F(x) Fx(x)) S A. Then, at any time t. given any greedy allocation policy X,
Blu, X1, X A) Elu X, A) ZA
Note that F, specifies only the marginal distribution of x,, Hi, and not the joint distribution of (X,, (.) Indeed the above lemma claims that the given bound on utility gain holds for all possible joint distributions as long as the marginal F, of X He is at most A away from F.
Intuitively, Lemma 3 and Lemma together bound the agent's 's short term incentive to be strategic:
the agent deviates from the truthful distribution too much, then the mechanism will terminate early and the agent will lose out on all the future utility (Lemma 3: and given any greedy allocation strategy set by the central planner, we have that the agents deviates within the undetectable range of Algorithm 2 then the gain in utility compared to acting truthfully is small (Lemmal 4h. Next, bound an agent's s incentive to lie in order to make the mechanism learn suboptimal greedy allocation policy that is more favorable to the agent.
6.2.2 Long term incentive
In order to bound the longer term incentive to be strategic, we want to show that despite agent i being strategic, the central planner can still learn an allocation policy that closely approximates the offline optimal allocation policy. This means that the agent's 's influence over the central planner's allocation policies is limited.
Lemma 5. Fix round T' S T and a strategic agent i. If agent i the only one being strategic, and Algorithm has not been triggered by the end of time T", then with probability 1 - d, Å == X (Frr satisfies
Elu, (X, X, {)] 1u X, X, x²) S nAT
where AT -81
1 log(
256 T') and X* (F).
7777
In particular, consider T = LR. Then the lemma above shows that if an agent was not kicked out by the end of epoch k 1, then with high probability the greedy allocation policy in epoch will be such that the agents' expected utility by being truthful is close to what he would have received in the offline optimal solution (Lemma (5). We can now combine this result with Lemma and Lemma to bound the utility that any single strategic agent can gain over the entire trajectory.
Lemma 6. If agent is the only one being strategic, then with probability 1 ô, agent i's online utility is upper bounded by
T
286 22-1
256e log, T
Σ
TE
nT log(
)
8
Here ki denotes the epoch number that time step lies in, and Xe, denotes the allocation policy used by the central planner in that epoch.

---

Proof of Theorem 1 We have already proven Theorem Wwhich bounds individual regret defined as the difference [ X, [,,' - (X,,, X )R,), i.e., the difference between the utility of agent under the offline optimal policy and that under the allocation policy learned by the algorithm when all the agents are truthfill The proof of Theorem I follows from plugging in the upper bound on 1E/u((X (X, (x,xx)) from this theorem into Lemma 6 to obtain the desired bound on the expression Ei= U1 (x, X At,) Σi= u, (X,,, Xt, Ab. ) i.e., on the total gain in utility achievable by misreporting under our mechanism. Further details are in Appendix C
Limitations and Future Directions
Although our goal is to develop mechanisms that are robust to selfish and strategic agents, real applications often involve bad faith actors that have extrinsic motivation to behave adversarially. As such, deployment of such resource allocation mechanisms critical applications requires significant additional validation. In future work we would like to explore the limit of relaxing the i.i.d. assumption that we place the distribution of valuations across agents. This is natural relaxation because if one agent thinks the item is good then it's likely that other agents would like the item as well. Furthermore it is also conceivable that agents are heterogeneous and have different value distributions for the items. However this seems to require a completely different strategy for detecting, and disincentivize strategic behaviors, as we can no longer catch the strategic agent through comparing each agent's reported distribution with that of others.
Acknowledgement
This work was supported part by an NSF CAREER award [CMMI 1846792) awarded to author Agrawal.
References
[1] Shipra Agrawal and Nikhil R Devanur. "Fast algorithms for online stochastic convex pro- gramming". In: Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. SIAM. 2014, pp. 1405-1424
[2] Shipra Agrawal. Zizhuo Wang, and Yinyu Ye. "A Dynamic Near- Optrmml Algorithm for Online Lincar Programming" In: Operations Research 62.4 (2014), 876-890. ISSN: 0030-364X.
[3] Kareem Amin, Afshin Rostamizadeh, and Umar Syed. "Repeated contextual auctions with strategic buyers". In: Advances in Neural Information Processing Systems 27 (2014).
[4] Genevay Aude et "Stochastic optimization for large-scale optimal transport". In: arXiv preprint arXiv: SeeXiv::600... /605088527 (2016).
[5] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni.
"Regularized online allocation problems: Fairness and beyond". In: International Conference on Machine Learning. PMLR. 2021,
pp. 630-639.
[6] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. "The best of many worlds: Dual mirror descent for online allocation problems". : In: arXiv preprint arXiv:2011. (2020).
[7] Santiago R Balseiro, Huseyin Gurkan, and Peng Sun. "Multiagent mechanism design without money". In: Operations Research 67.5 (2019), pp. 1417-1436.
[8] Richard Cole, Vasilis Gkatzelis, and Gagan Goel. "Mechanism design for fair division: allocat- ing divisible items without payments". In: Proceedings of the fourleenth ACM conference on Electronic commerce. 2013, 13, pp. 251-268.
[9] Richard Cole, Vasilis Gkatzelis, and Gagan Goel. "Positive results for mechanism design without money". In: (2013).
[10] Nikhil R. Devanur et al. "Near Optimal Online Algorithms and Fast Approximation Algorithms
for Resource Allocation Problems". In: J. ACM 66.1 1 (2019). ISSN: 0004-5411. DOT: 10. 1 1145/ 3284177 URL.: htt.::htts::/// /tto:.
10. 1145/32881111
[11] Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. "Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator". In: The Annals of Mathematical Statistics (1956), pp. 642-669.
10

---

[12] Negin Golrezaei, Adel Javanmard, and Vahab Mirrokni. "Dynamic incentive-aware learning: Robust pricing contextual auctions". In: Advances in Neural Information Processing Systems 32 (2019).
[13] Artur Gorokh, Siddhartha Banerjee, and Krishnamurthy Iyer. "From monetary to nonmonetary mechanism design via artificial currencies". In: Mathematics of Operations Research (2021) 1).
[14] Mingyu Guo and Vincent Conitzer. "Strategy-proof allocation of multiple items between two agents without payments or priors." " In: AAMAS. Citeseer. 2010, pp. 881-885
[15] Mingyu Guo, Vincent Conitzer, and Daniel M Reeves. "Competitive repeated allocation without payments".. In: International Workshop on Internet and Network Economics. Springer. 2009, pp. 244-255.
[16] Li Han et al. "On strategy-proof allocation without payments or priors". In: International Workshop on Internel and Network Economics. Springer. 2011, pp. 182-193.
[17] Yash Kanoria and Hamid Nazerzadeh. "Incentive-compatbble learning of reserve prices for repeated auctions". In: Operations Research 69.2 (2021), pp- 509-524.
[18] Ariel Procaccia and Moshe Tennenholtz. "Approximate mechanism design without money".
In: ACM Transactions Economics and Computation (TEAC) 1.4 (2013), pp. 1-26.
[19] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. "Sequential complexities and uniform martingale laws of large numbers". In: Probability Theory and Related Fields 161.1-2 (2015), pp- 111-153.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 7
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section 7
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
11

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "jGQyPrCR8Q4", "reviewer": "Reviewer_XRjf", "summary": "The paper studies a repeated online allocation of a single type of good to agents who have the same but unknown valuation distribution for the good. Unlike the prior work, the paper assumes the agents are strategic and no monetary payments can be used to incentivize truthfulness.  The goal of the allocation is to maximize social welfare. The paper provides an algorithm that satisfies approximate Bayesian incentive compatibility (i.e. no single agent can deviate from truthfulness to gain much if the other agents are truthful) and also achieves no regret (the social welfare will approach the highest possible welfare as the number of allocation rounds goes to infinity).", "questions": "-- Can the authors propose a motivating example to justify repeated strategic interactions where monetary compensation is not allowed to incentivize truthfulness? \n\n-- Can the authors provide more insight on how the offline optimal allocation is solved? Does this require new tools or the problem has been solved by prior work? Why the allocation is called \"Greedy\" in Definition 1?\n\n-- The regret over all agents grow as $n\\sqrt{nT}$. Is this standard? Are there any lower bounds?\n\n-------------------------------------\nMinor comments:\n-------------------------------------\n-- Please sort the numbers for the references (e.g., line 27) in the paper.\n\n-- Change \"Literature Review\" to \"Literature review\" to be consistent with other section headers.\n\n-- Is there any reason to have an upper bound of $\\bar{x}$ for valuations instead of 1?", "limitations": "The discussion of the limitations is sufficient. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "-------------------------------------\nStrengths:\n-------------------------------------\n-- The paper studies a novel allocation setting where strategic interactions are allowed by the agents but the allocator cannot use payments to incentivize truthfulness.\n\n-- The exposition and presentation of the paper were excellent. The setting was clearly discussed. And the high-level ideas of the algorithms/proofs can be easily followed throughout the paper. \n\n-------------------------------------\nWeaknesses:\n-------------------------------------\n-- The setting of the paper is rather strange. Unlike the traditional online learning setting, there is no immediate feedback to the allocator on the quality of the allocation at each round. Hence, I am not sure about the applicability of the results in any interesting domains.\n\n-- The analysis does not seem to provide any interesting insights. The paper is interested in enforcing Bayesian incentive compatibility and the authors compare the reported bids of any specific user to the rest to check whether the user is untruthful (given that the users all have the same valuation distribution). This might be okay if to goal is to detect untruthfulness. But the mechanism simply stops if untruthfulness is detected. The analysis of the regret is only for the case that all agents are truthful. This also significantly weakens the guarantees provided by the paper. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JjE72lkB0o", "reviewer": "Reviewer_x5pZ", "summary": "This work considers an online allocation problem with learning and strategic agents. Previous works already studied this problem, but proposed BIC policies either using payments/transfers between the players and the central planner, or assuming that the planner knows beforehand the valuation distribution of the players. This work is thus the first to propose an approximate BIC policy, with sublinear regret, when neither of these conditions hold.\n\n--------\n\nAfter the discussion with the authors and reviewers, I decided to raise my score as I believe this paper to be well written and to deal with an interesting problem. As suggested in the discussion with the authors, I think that adding a rigorous result stating that a no regret BIC policy cannot be derived in the heterogeneous setting without further assumption.", "questions": "My main questions to the authors are related to my concerns mentioned above:\n\n1) Could you show some impossibility result on the heterogeneous case (without payment or distribution knowledge), or do you believe that a good BIC policy is possible in that case?\n2) Can you show some guarantees on the respect of the predetermined fractions p_i^* ?\n\nI also have some other questions:\n3) The proposed policy is robust to the deviation of a single player. It even seems it could be extended to the possible deviation of a significant fraction of players (eg as in the Byzantine problem). It however might lead to considerable computational costs. Could you develop on this point?\n\n----- Minor comments -----\n\n4) After Definition 2, it could be great to relate the notion of Approximate-BIC to approximate-Nash equilibria\n5) The algorithm works in epochs of doubling sizes. Why is it needed? It seems the same algorithm could work with constant epoch size 1 (eg anytime)?\n", "limitations": "No concern", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I find this work interesting and overall well written. The considered problem is of interest, since the central planner might have very small leverages in real life situations when allocating resources to multiple agents.\n\nThe proposed algorithm is rather simple and natural. It mostly relies on the DKW concentration inequality.\n\nAs a main weakness, the proposed algorithm crucially relies on the fact that the players are homogeneous, ie have the same valuation distribution. The case of heterogeneous seems much harder as mentioned by the authors in the conclusion. Actually, I believe that some impossibility result can be shown for heterogeneous players when the player neither knows the players' distribution nor can use payments. Showing such a result would significantly support this work (and I believe it is not that hard).\nFor a similar reason, the main result claims that truthful bidding by the players is an approximate Nash equilibrium, but I would believe that drastically different strategies could also be approximate Nash equilibria (actually almost any strategy where the players report the same fake distribution).\n\nA second concern I have: the current paper is lacking some theoretical guarantee on how the repartition of the items by the central planner respects the predetermined fraction p_i^*. Having some guarantee on the differences between p_i^* and \\hat{p}_i would make the analysis of the policy complete in my opinion.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "260r6fL0G-9", "reviewer": "Reviewer_jFe4", "summary": "The paper studies an online allocation setting where arriving items\nare allocated among $n$ agents who are \"promised\" a prespecified\nfraction of the items. The goal of the planner is to maximize the\nagents' total valuation. As opposed to the standard setting, the\nplanner not only does not know the realized valuation at each period,\nbut also the distribution of the values (which are assumed to be iid\nacross agents and time). Furthermore, the agents are strategic and\nmisreport their values to affect future allocations. The paper\nproposes an online-learning based allocation mechanism that is\napproximately BIC and achieves sublinear regret (under truthful\nreporting) against the optimal allocation policy that knows the\ndistribution.\n", "questions": "While the offline problem requires that the allocation satisfy the\npromised fraction $p_i^*$ exactly, there is no specific constraint\nplaced on the online problem. In particular, while the algorithm\nensures that all but one agent's allocation is below the capacity\n$p_i^* T$, is it possible to show that the allocations of all agents\nare close to $p_i^*T$, given the regret bounds?", "limitations": "None", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies an important resource allocation problem inspired\nfrom practical considerations, and proposes a mechanism to decrease\nthe informational requirements on the planner. If the common iid\ndistribution were known to the planner, the paper shows that the\nproblem reduces to an offline optimization problem related to an\noptimal transport problem, whose solution is parametrized by the dual\nvariables $\\lambda$. Thus, the online problem is reduced to learning\nthe optimal dual values $\\lambda$ from the reports, while ensuring\nthat the reports remain truthful.\n\nThe main insight behind the mechanism is to use the reports of other\nagents to detect if an agent is reporting truthfully, and if not, stop\nthe allocation. This uses the fact that the valuation distributions\nare not only independent, but also identical, a major weakness of the\napproach in terms of its applicability. This approach also bears\nsimilarity to implementation theory (Caillaud & Roberts 2005, Maskin\n1998), and the reader would be helped by connecting to this\nliterature.\n\nTo summarize, the paper proposes an interesting mechanism to overcome\nthe ignorance of the valuation distribution. However, this approach is\nsomewhat hampered by its reliance on the iid assumption. In\nparticular, the approach fails even if the valuation distribution is\nindependent but not identical. \n\n\nTerminology: The abstract as well as the introduction characterizes\nthe contribution as achieving near-optimal regret against the \"optimal\noffline allocation policy\". This is somewhat imprecise, as the offline\npolicy can be construed as one that knows the instance (for instance,\nin the definition of competitive ratio). However, the guarantees are\nagainst the \"offline policy\" that knows the distribution but not the\nrealization. Perhaps a more explicit terminology might be useful.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept