A classic sequential resource allocation problem is to allocate $T$ sequentially arriving items to $n$ 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.

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 [2, 10, 6, 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 to individual utility gain (possibly at 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,

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 ($\mathbb{E}[X_{1}|X_{1}>X_{2}]/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 a significantly increased utility of $3T/8$ ($\mathbb{E}[X_{1}|X_{1}>0.5]/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 to learn a more favorable policy over time by repeatedly misreporting their values.

Motivated by these shortcomings, in this paper, we consider the problem of designing an online learning and allocation mechanism in the presence of strategic agents. Specifically, we consider the problem of sequentially allocating $T$ items to $n$ strategic agents. The problem proceeds in $T$ rounds. In each round $t=1,\ldots,T$, the agents’ true valuations $X_{i,t},i=1,\ldots,n$ for the $t^{th}$ item are generated i.i.d. from a distribution $F$ a priori unknown to the central planner. However, the central planner can only observe a value $\tilde{X}_{i,t}$ reported by each agent $i$, which may or may not be the same as her true valuation $X_{i,t}$ for the item. Using the reported valuations from the current and previous rounds, the central planner needs to make an irrevocable decision of who to allocate the current item. The allocations should be made in a way such that each agent at the end receives a fixed fraction $p^{*}_{i}$ of the $T$ items, where $p^{*}_{i}>0,\sum_{i=1}^{n}p^{*}_{i}=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 a 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.

Our work lies at the intersection of online learning and mechanism design. From an 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., see [10, 2, 1, 6, 5]). However, a 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 to 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 a key mechanism for limiting rational agents’ incentives to misreport their valuations. For example, [3] study a posted-price mechanism in a repeated auction setting where buyers’ valuations are context dependent. [12] extend this work to multi-buyer setting, using second-price auction with dynamic personalized reserve prices. [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 above-mentioned works are concerned with maximizing revenue for the seller, and use 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 utility.

Recently, there has been some work on studying reductions from mechanism design with money to those without money. [13] provided a black-box reduction from any one-shot, BIC mechanism with money, to 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 our setting. [18] consider a 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 a 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, 16, 8, 9, 8]. These papers either use a very restricted setting with just two agents, or use very specific/simple valuation functions for the agents. Even in these basic settings, they show that the best one can hope for is a 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, [15] and later [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 on learning in repeated auctions which focuses on allocation mechanisms that utilize money (payments) to achieve incentive compatibility.

We present an online allocation mechanism that is approximately-BIC, and further achieves low regret guarantees on 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 learner adaptively learns utility-maximizing allocation policies assuming truthful agents.

The learner runs in epochs with geometrically increasing lengths. The starting time of each epoch $k$ is given by $L_{k}=2^{k},k=0,1,\ldots$, which is also when the allocation policy is updated. At the end of each epoch (i.e., at time $t=L_{k}-1$ for epoch $k$), the learner takes all the previously reported values from all the agents, and uses them to construct an empirical distribution of the agents’ valuations. The learner implicitly assumes truthful agents in its computations. Therefore, since the agents’ true valuations are i.i.d., it first constructs a single, one-dimensional empirical distribution $\hat{F}_{t}$, and then uses it to construct the corresponding $n$-dimensional distribution $\hat{\bm{F}}_{t}$:

The learning algorithm then solves the offline problem (2) using $\hat{\bm{F}}_{t}$, and uses the resulting greedy allocation policy characterized by $\lambda^{*}(\hat{\bm{F}}_{t})$ to allocate the items in the following epoch.

In parallel to the learner, the detector constructs and monitors, in each time step $t$, and for each agent $i$, two empirical distributions. One using the reported valuations from agent $i$: $\bar{F}_{t}$, and one using the reported valuations from all the other agents: $\tilde{F}_{t}$. The detection algorithm then computes the supremum between the two empirical CDFs, $\sup_{x}|\bar{F}_{t}(x)-\tilde{F}_{t}(x)|$. If this difference is greater than a predetermined threshold $\Delta_{t}$, 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.

The threshold $\Delta_{t}$ needs to be chosen such that if everyone is truthful, then with high probability the detection algorithm will not pull the trigger. At 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 Dvoretzky-Kiefer-Wolfowitz (DKW) inequality[11]. However, since a 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 1), and use that to choose an appropriate threshold $\Delta_{t}$. The details are given in Algorithm 1 and Algorithm 2.

Our main results are the following guarantees on incentive compatibility and regret of our online allocation algorithm.

Since truthful reporting constitutes an approximate equilibrium, it is reasonable to then assume that agents will act truthfully. We show the following individual regret bound assuming truthfulness.

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 4 in [17]). In the next section, we describe the high level proof ideas for the main results above.

We will now outline our proof in more detail. All missing proofs can be found in the Appendix. First we state the following martingale variation of the well-known Dvoretzky-Kiefer-Wolfowitz (DKW) inequality[11]. This is critical when dealing with strategic agents as they can adapt their strategy over time, resulting in non-independent (reported) values.

Next we introduce a new notation to to denote the fraction of allocation that $j$ receives under the greedy allocation policy with parameter $\lambda$ and valuation distribution $\bm{F}$:

We start with proving Theorem 2, as we will use this to prove Theorem 1 later.

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 to 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 on the distribution of valuations across agents. This is a 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 so 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.

This work was supported in part by an NSF CAREER award [CMMI 1846792] awarded to author S. Agrawal.