Robust Resource Allocation via Competitive Subsidies

Consider an indivisible resource shared between multiple selfish agents over time, e.g., a telescope shared by different research labs. Over multiple rounds, a principal needs to decide which agent gets allocated, aiming to allocate to each agent when their value is the highest. The mechanism used by the principal should be: $(i)$ non-monetary, as the resource is being shared, and no one agent owns it, $(ii)$ fair, in that each agent is individually satisfied with the utility they get, $(iii)$ simple and understandable, so that participating in the mechanism is straightforward, $(iv)$ robust, i.e., each individual has utility guarantees that hold independent of the behavior of others. Under these properties, any agent following a simple strategy is able to guarantee high utility regardless of how the other agents behave. Standard techniques in mechanism design, like the VCG mechanism, cannot be applied due to the lack of money. In addition, such techniques often ignore fairness in allocation and instead focus on efficiency, i.e., maximizing the total allocated value, which in this setting is ill-defined: the lack of money makes agents’ values incomparable.

We study this problem via a canonical model, first introduced by [9]: $n$ agents compete over $T$ rounds for a single indivisible resource in each round. Agent $i$ has (random) private values $V_i[t]$ for the resource in round $t$; these values are i.i.d. across rounds and independent across agents. The principal can award the item in each round to a single agent, or not award at all. Early work on this model looked at welfare approximations, with symmetric agents or known value distributions. More recent work on this setting has focused on the design of share-based mechanisms, where each agent $i$ is endowed with a “fair share” ${\alpha }_i$ (with ${\sum }_i{\alpha }_i=1$) indicating the nominal fraction of items they should be allocated. This was first suggested by [8], who showed that under a repeated first-price auction with artificial credits, each agent can robustly guarantee at least $1/2$ of her ideal utility (i.e., her maximum utility under her nominal share of the resource – see Definition 1), under arbitrary behavior by other agents. Recently, using the same mechanism, [13] improved this to $2-\sqrt{2}\approx 0.59$ fraction of ideal utility, using a more complicated strategy where the agent has to use a randomized bid; they also show that for the first-price auction, no static bidding strategy can be better than $0.6$ robust. In contrast, a natural upper bound on the robustness factor is $1-1/e$, which follows from ignoring strategic considerations – consider $n$ agents with equal fair shares $1/n$ and $\mathrm{Bernoulli}(1/n)$ values, wherein each agent should ideally get $T/n$ rounds, but there are at most $(1-{(1-1/n)}^n)T$ rounds in which any agent has non-$0$ utility. Thus, it appears fundamentally new ideas are required to make progress towards this bound.

We consider the following canonical setting for repeated online allocation, introduced by [9]. There are $T$ rounds, and in each round $t$, a single indivisible item is available for allocation among $n$ agents. At the start of round $t$, each agent $i$ realizes a private value $V_i[t]$ for the item, drawn from a fixed distribution ${ℱ}_i$, independently across both agents and time. The value $V_i[t]$ becomes known to agent $i$ at the start of round $t$, but is unknown to the principal and other agents. We assume the value distribution ${ℱ}_i$ is nonnegative and bounded by some constant not depending on $T$ (which we take to be 1 without loss of generality).

At the end of each round $t$, following some mechanism, the principal chooses an agent to allocate the item to, or to not allocate. Let $W_i[t]$ be an indicator of whether agent $i$ wins the round-$t$ item or not, resulting in utility $U_i[t]=V_i[t]W_i[t]$. Each agent seeks to maximize their average per-round utility, $\frac{1}{T}{\sum }_{t=1}^T{U}_i[t]$.

With symmetric agents (i.e., with identical distributions ${ℱ}_i$ and equal importance), a natural aim for the principal is to allocate to the agent with the highest value. To extend this to heterogeneous agents in the absence of money, we use the benchmark of ideal utility introduced by [8]. Roughly speaking, the ideal utility is the highest expected per-round utility an agent could obtain if they are restricted to winning the item only for a pre-specified fraction of the rounds. Formally, we assume each agent has an exogenously given fair share ${\alpha }_i>0$, where ${\sum }_i{\alpha }_i=1$, and define their ideal utility as:

An agent’s fair share measures an exogenously defined importance of this agent; symmetric fair shares ${\alpha }_i=1/n$ mean each agent is equally important. If ${ℱ}_i$ has an absolutely continuous CDF $F_i$, then $v_i^{\ast }$ is just the portion of the expectation of $V_i\sim {ℱ}_i$ that comes from the top ${\alpha }_i$-quantile of ${ℱ}_i$, i.e., $v_i^{\ast }={𝔼}_{V_i\sim {ℱ}_i}[V_i{\mathrm{𝟙}}_{V_i\ge F_i^{-1}(1-{\alpha }_i)}]$. This is thus a natural benchmark for what an agent can hope to receive. Moreover, with identical ${ℱ}_i$ and equal shares, summing ideal utilities gives the so-called ex-ante welfare [1], which is an upper bound for overall welfare widely used in approximate mechanism design.

Fix a mechanism used to allocate the item. As in prior work, [8, 4, 6, 13, 11], we are interested in robust strategies, strategies that guarantee a certain fraction of the agent’s ideal utility, regardless of the other agents’ strategies (even if the other agents adversarially collude).

Robust strategies are nice in that they guarantee utility for the agent without assumptions the behavior of other agents. In addition, if all agents have a $\lambda$-robust strategy, then at any equilibrium, they must obtain at least a $\lambda$-fraction of their ideal utility; if not, they can deviate to the $\lambda$-robust strategy to gain more utility. In particular, for identical ${ℱ}_i$ and equal shares ${\alpha }_i=1/n$, if each agent has a $\lambda$-robust strategy, then the ratio of the optimal social walfare and the achieved welfare (price of anarchy) is at most $1/\lambda$.

Our primary focus in this work is on getting mechanisms with good robustness bounds. A secondary goal is to realize such robustness bounds under equilibrium strategies. Unfortunately, robust strategies are not guaranteed to form an equilibrium, as it is possible that agents may want to deviate to an even higher payoff strategy. Indeed, for natural mechanisms, known robust strategies do not admit any equilibrium [14]. In such cases, a $\lambda$-robust strategy may not help in understanding a mechanism’s performance under real agent behavior. To this end, [11] offers a mechanism where $\frac{1}{2}$-robust strategies do form an equilibrium, which motivates the following definition.

By definition, a ${\lambda }_{\mathrm{𝚁𝙾𝙱}}$-robust ${\lambda }_{\mathrm{𝙽𝙰𝚂𝙷}}$-good approximate-equilibrium has ${\lambda }_{\mathrm{𝙽𝙰𝚂𝙷}}\ge {\lambda }_{\mathrm{𝚁𝙾𝙱}}-o(1)$, but ${\lambda }_{\mathrm{𝙽𝙰𝚂𝙷}}$ could potentially be substantially higher. In Sections 5 and 6 we improve the result of [11] by offering a mechanism where $0.61$-robust strategies form a $(1-1/e)$-good equilibrium.

In our mechanism, Competitive Subsidy Mechanism, each agent $i$ is endowed with ${\alpha }_{i}T$ tokens of artificial credits. At each time $t$, each agent must either bid or not. As we mention in the introduction, having a binary action space limits the possible adversarial behavior of other agents, which is crucial for the improved guarantee over [13]. The item is allocated uniformly at random among bidding agents. The winning agent must pay $\overline{b}k/(1+k)$ artificial tokens where $k$ is the number of bidding agents, and $\overline{b}$ is a scale factor, chosen later. As we show in Section 4, this payment scheme is optimal, in that we cannot get better robustness guarantees. When an agent’s budget of artificial tokens becomes non-positive, she is barred from bidding in future rounds. We formally specify our mechanism in Algorithm 1.

Next, we describe our proposed robust strategy. We adopt the notion of an $\alpha$-aggressive strategy from [6], whereby an agent bids only for the values that realize her ideal utility.

Our main result of this section is as follows, which says that an ${\alpha }_i$-aggressive strategy is $(0.625-o(1))$-robust, i.e., each agent $i$ guarantees that fraction of ideal utility regardless of other agents’ behavior.

We prove the theorem formally in the full version of the paper and give a proof sketch here.

In this section, we consider payment schemes different than the ones in Section 3, and show that the one used in our Competitive Subsidy Mechanism achieves optimal robustness under static strategies. We come up with an optimization problem that bounds this robustness factor and then solve it numerically to get the desired upper bound.

Consider the generalization of the Competitive Subsidy Mechanism where agents pay some $p_k\ge 0$ when there are $k$ bidding agents (with our mechanism being a special case where $p_k=\overline{b}\cdot k/(1+k)$). We call this generalization General Cost Mechanism and bound its performance under any payment scheme.

We consider an agent $i$ following the ${\alpha }_i$-aggressive strategy and all other agents (with a combined budget $(1-{\alpha }_i)T$) coordinating so that at each time, exactly $k$ agents other than $i$ bid. Under such simple strategies, we can explicitly calculate how many rounds agent $i$ wins in expectation, which is equal to the fraction of ideal utility she receives by the definitions of ideal utility and ${\alpha }_i$-aggressive strategy. Given the commitment to these strategies, agents $j\ne i$ are picking $k$ to minimize $i$’s utility, while the mechanism picks the payment scheme to maximize it. The harder part is limiting the search space of this optimization problem. We consider agents $j\ne i$ only bidding $1$ or $2$ at a time, making only the payments $p_1,p_2,p_3$ relevant for the mechanism designer. While in principle considering more agents bidding at the same time could harm agent $i$ more, we show below that even with this strategy by the other players, we can argue that the $0.625$ bound is best possible. Next, we prove upper bounds on these three payments, given that having them too high can make agents run out of budget even without adversarial competition.

This process is shown in the next theorem, where $\mu (p_1,p_2,p_3,k)$ is the number of rounds agent $i$ wins, which is minimized over $k$ and maximized over $p_1,p_2,p_3$. In the computation of $\mu (\cdot )$, $\gamma$ is the fraction of rounds where agents $j\ne i$ still have budget remaining out of all the rounds that agent $i$ still has budget remaining. In the full version of the paper, we work out and prove the above computation in detail, which considers agents with equal fair shares $1/n$ and $n\to \mathrm{\infty }$.

We numerically brute-force optimized the optimization problem in Theorem 6 by discretizing the space of $(p_1,p_2,p_3)$ and evaluating the objective function at each $(p_1,p_2,p_3)$ in the discretized space. In our code, we found no $(p_1,p_2,p_3)$ such that the objective is more than $0.625$, giving numerical evidence that the value of the optimization problem is $0.625$.⁴⁴4Our code can be found at https://github.com/davidxlin/optimization-problem-for-robustness.

While robust strategies like in the previous section are nice, they do not always form an equilibrium. Previous work [8, 6, 4, 13] proposed robust strategies in different mechanisms for this setting that do not form an equilibrium. On the other hand, [14] designed strategies that form an equilibrium but offer no robustness. [11] achieve both types of results by designing a mechanism that has a $1/2$-robust $\left(1-{\prod }_{j\in [n]}(1-{\alpha }_j)\right)$-good equilibrium (see Definition 3). They also note that the $1-{\prod }_j(1-{\alpha }_j)$ factor is optimal in that even if the principal is able to see all the values, they cannot guarantee a higher fraction of ideal utility than $1-{\prod }_j(1-{\alpha }_j)$ to every agent in expectation.

In this section, we explore if our mechanism achieves similar results. First, we shall argue that in our mechanism, if we choose $\overline{b}$ as suggested by the previous section, each player using an ${\alpha }_i$-aggressive strategy does not form an equilibrium. However, if we choose $\overline{b}$ slightly differently and make a slight modification of the mechanism by forcing players to bid at least an ${\alpha }_i$ fraction of the time, we can make the ${\alpha }_i$-aggressive strategies form an equilibrium at the expense of sacrificing the robustness factor a little bit. Here, we demonstrate how to make this modification to $\overline{b}$ in the symmetric case where ${\alpha }_i=1/n$. In Section 6, we give a reduction from the general ${\alpha }_i$ case to the symmetric case.

First, let us argue why when choosing the payment constant $\overline{b}=8/3$ as in the previous section, everyone playing the robust strategy is not necessarily an equilibrium. Assume every agent is playing the robust strategy, so they each bid with probability $1/n$ independently across agents and time, so long as they have budget. Then, at any given time that everyone has budget remaining, for any agent $i$, the number of other agents $j\ne i$ that bid is distributed as $X\sim \mathrm{Binomial}(n-1,1/n)$. Therefore, conditioned on agent $i$ bidding, agent $i$’s expected payment is $𝔼\left[\frac{\overline{b}}{2+X}\right]$ since conditioned on the number of other agents bidding $X$, agent $i$ wins with probability $\frac{1}{1+X}$, in which case they pay $\overline{b}\cdot \frac{1+X}{2+X}$. By substituting in $\overline{b}=8/3$ and computing $𝔼[1/(2+X)]$, which we show is equal to $(n+1)/(1+n{(1-1/n)}^{n+1}$ in the full version of the paper, we can show that this expected payment is less than $1$ for $n\ge 3$. Since this is less than $1$, agents have $T/n$ budget, and are bidding with probability $1/n$, this means that agents will have $\mathrm{\Omega }(T)$ budget remaining at the end of the mechanism with high probability. Clearly, for value distributions that are nonzero with probability greater than $1/n$, the agents are not best responding: they should bid more to use more of their budget.

However, the above calculation suggests the following idea. We should set $\overline{b}=1/𝔼[1/(2+X)]$, and then agents will be spending their budget exactly in expectation. We still obtain high robustness beating all previous work with this choice of $\overline{b}=1/𝔼[1/(2+X)]=(n+1)/(1+n{(1-1/n)}^{n+1})\approx e$: the robustness factor (using the calculations in the proof of Theorem 5) becomes

Notice that the mechanism allocates the item so long as there is at least one bidder. Each bidder playing a $1/n$-aggressive strategy bids with probability $1/n$ as long as they have budget remaining. If everyone plays a $1/n$-aggressive strategy, by the fact that agents spend their budget exactly in expectation and by concentration inequalities, no agent runs out of budget too early with high probability. Then, there are $1-{(1-1/n)}^n$ rounds in which the item is allocated in expectation. By the strategies and symmetry, this will be the fraction of ideal utility each agent achieves, matching the optimal as shown in [11].

What is left to do is to argue that choosing $\overline{b}$ in this way is indeed an equilibrium. Intuitively, for a fixed agent $i$, they have two potential deviations: they could bid more often, or they could bid less often. By bidding more often, agent $i$ spends more artificial currency. We can also see that agent $i$ bidding more often decreases the spending of other agents as follows. In a given round, conditioned on there being $k$ bidders, the expected payment of a bidder is $\overline{b}/(k+1)$: each bidder wins with probability $1/k$ in which case they pay $\overline{b}k/(k+1)$. Hence, fixing the strategies of agents $j\ne i$, agent $i$ bidding more often increases the number of bidders $k$ at each timestep, lowering the other agents’ payments. Therefore, agent $i$ will run out of money quicker with the same probability of winning each round (conditioned on bidding), so they will obtain more lower-valued rounds at the beginning instead of spacing their wins.

Whether or not agent $i$ should bid less is slightly more nuanced. In fact, if we retain the same mechanism as in Competitive Subsidy Mechanism, agent $i$ may want to bid less. For example, if agent $i$’s value distribution were ${ℱ}_i=\mathrm{Bernoulli}(1/(2n))$, then a $1/n$-aggressive strategy would imply that agent $i$ is bidding sometimes when they have $0$ value. Instead, they should not bid when they have $0$ value, which would cause others’ payments to go up (using the previous reasoning about the other agents’ spending), and then when other agents run out of budget, agent $i$ will have a higher probability of winning on rounds that they actually have value $1$.

To accommodate this, we modify the mechanism to enforce that at each time $t$, each agent must have bid at least $t/n-o(T)$ times; otherwise, the principal will force them to bid. Then, attempting to underbid is not a helpful strategy. We describe the mechanism formally in Algorithm 2, where the only difference from Algorithm 1 is the enforcement of the minimum bidding requirement.

Our main result of this section is as follows, proved formally in the full version of the paper.

In this section, we generalize Section 5 to asymmetric fair shares. The issue with Competitive Subsidy Mechanism is that it allocates the item uniformly at random among the bidding agents. While this is not an issue for robustness claims (all such results of previous sections hold for arbitrary fair shares), it is an issue for the equilibrium claim. In fact, to get better than $1/2$ ideal utility guarantees in equilibrium, we have to allocate the item asymmetrically. As before, to get equilibrium guarantees, we want a payment scheme such that agents use their budget exactly in expectation. Consider such a scheme and the following simplified setting: two agents with fair shares $\alpha$ and $1-\alpha$ that request the item with probabilities $\alpha$ and $1-\alpha$, respectively. Allocating uniformly at random makes the agent with fair share $\alpha$ win $\alpha (\alpha +(1-\alpha )/2)=\alpha (1+\alpha )/2$ fraction of the rounds. This results in $1/2$ fraction of her ideal utility when $\alpha$ is small, which is smaller than the robustness guarantee when not setting $\overline{b}$ to obtain an equilibrium.

To remedy this issue and extend our mechanism, we simulate agents with different fair shares with multiple “small” agents. The basic idea is that if the fair shares ${\alpha }_i$ are all rational with common denominator $m$⁵⁵5If the fair shares ${\alpha }_i$ are irrational, or if the common denominator is large, we can approximate the fair shares with rational fair shares with small denominators and obtain approximate guarantees. Specifically, we show in the full version of the paper that it suffices to approximate the fair shares with rational numbers with denominators at least $1/(2{\min }_i{\alpha }_iϵ)$ to obtain a $(1-ϵ)$-fraction of our guarantees on the achieved fraction of ideal utility., we run Competitive Subsidy Mechanism with Bidding Minimum with $m$ agents where agent $i$ gets to control $k_i:={\alpha }_{i}m$ simulated agents in Competitive Subsidy Mechanism with Bidding Minimum.

Implementing this idea naively does not quite work to obtain the same equilibrium behavior, where each simulated agent is bidding independently across rounds with probability $1/m$. There is no particular reason why an agent $i$ controlling multiple simulated agents should have the simulated agents bid independently of each other. Instead, we shall have the principal force some level of independence by only allowing an agent to request whether they want at least one simulated agent bidding or not. If agent $i$ requests to bid at time $t$, then the principal shall sample requests to bid $({\widehat{r}}_{(i,1)}[t],\mathrm{\dots },{\widehat{r}}_{(i,k_i)}[t])$ distributed as i.i.d. $\mathrm{Bernoulli}(1/m)$ conditioned on at least one of them being nonzero to use as the requests in the simulated agents that $i$ controls.

If agent $i$ uses a $\left(1-{\left(1-\frac{1}{m}\right)}^{k_i}\right)$-aggressive strategy, where a $\beta$-aggressive strategy is as before, requesting whenever the value is in the top $\beta$-quantile of the value distribution, then the ${\widehat{r}}_{(i,i^{\prime })}[t]$ will be i.i.d. $\mathrm{Bernoulli}(1/m)$. This emulates each simulated agent playing a $1/m$-aggressive strategy. If each simulated agent wins at least ${\lambda }_i/m$ rounds, then agent $i$ will win ${\lambda }_i{k}_i/m$ rounds, which then implies robustness and equilibrium utility lower bounds. In particular, if we use $\overline{b}=(m+1)/(1+m{(1-1/m)}^{n+1})$ as in Section 5, a $\left(1-{\left(1-\frac{1}{m}\right)}^{k_i}\right)$-aggressive strategy is $(5/(3e)-o(1))$-robust, and if each agent $i$ plays a $\left(1-{\left(1-\frac{1}{m}\right)}^{k_i}\right)$-aggressive strategy, each agent obtains a $1-{\left(1-\frac{1}{m}\right)}^m-o(1)\ge 1-1/e-o(1)$ fraction of their ideal utility.

Using the same arguments as in Section 5, if we put a minimum bidding constraint, each agent playing this $\left(1-{\left(1-\frac{1}{m}\right)}^{k_i}\right)$-aggressive strategy is an equilibrium. The way we have set the mechanism up, agents can only control the frequency at which they bid. They can’t underbid by enforcement, and overbidding does not help because this only decreases the payments of others while winning worse rounds for the overbidder.

Our full mechanism for asymmetric fair shares is as follows. Given the fair shares ${\alpha }_i=k_i/m$, create a set of simulated agents $\widehat{N}=\{(i,i^{\prime }):i\in [n],i^{\prime }\in [k_i]\}$. Initialize an instance $\widehat{ℳ}$ of Competitive Subsidy Mechanism with the agent set $\widehat{N}$ and equal fair shares: ${\widehat{\alpha }}_{(i,i^{\prime })}=1/m$ for each $(i,i^{\prime })\in \widehat{N}$. At each time $t$, each real agent $i$ can request to bid or not. Let $r_i[t]$ denote the indicator that agent $i$ requests to bid. We enforce a bidding minimum that ${\sum }_{s=1}^t{r}_i[s]\ge \left(1-{\left(1-\frac{1}{m}\right)}^{k_i}\right)t-o(T)$. Let $S[t]=\{i:r_i[t]=1\}$ be the set of bidding agents. For $X_1,\mathrm{\dots },X_k$ i.i.d. $\mathrm{Bernoulli}(1/m)$ random variables, let ${𝒟}_{k,m}$ be the distribution of $(X_1,\mathrm{\dots },X_k)$ conditioned on the event that at least one of the $X_i=1$. For each bidding agent $i\in S[t]$, we sample $({\widehat{V}}_{(i,1)}[t],\mathrm{\dots },{\widehat{V}}_{(i,k_i)}[t])\sim {𝒟}_{k_i,m}$. Set $\widehat{S}[t]=\{(i,i^{\prime }):i\in S[t],{\widehat{V}}_{(i,i^{\prime })}=1\}$, which we set as the set of requesting simulated agents at time $t$, and we simulate $\widehat{ℳ}$ at time with bidding agents $\widehat{S}[t]$. From $\widehat{ℳ}$, there is simulated agent $(i,i^{\prime })$ who won the item, and we give the item to the real agent $i$. (We fully simulate $\widehat{ℳ}$, so the budgets of the simulated agents also get updated within $\widehat{ℳ}$, and they are enforced in $\widehat{ℳ}$ when the simulated agents request to bid.)

We formally describe this mechanism in Algorithm 3 and prove the following theorem in the full version of the paper.