A canonical setting for non-monetary online resource allocation is one where agents compete over multiple rounds for a single item per round, with i.i.d. valuations and additive utilities across rounds. With $n$ symmetric agents, a natural benchmark for each agent is the utility realized by her favorite $1/n$-fraction of rounds; a line of work has demonstrated one can robustly guarantee each agent a constant fraction of this ideal utility, irrespective of how other agents behave. In particular, several mechanisms have been shown to be $1/2$-robust, and recent work established that repeated first-price auctions based on artificial credits have a robustness factor of $0.59$, which cannot be improved beyond $0.6$ using first-price and simple strategies. In contrast, even without strategic considerations, the best achievable factor is $1-1/e\approx 0.63$. In this work, we break the $0.6$ first-price barrier to get a new $0.625$-robust mechanism, which almost closes the gap to the non-strategic robustness bound. Surprisingly, we do so via a simple auction, where in each round, bidders decide if they ask for the item, and we allocate uniformly at random among those who ask. The main new ingredient is the idea of competitive subsidies, wherein we charge the winning agent an amount in artificial credits that decreases when fewer agents are bidding (specifically, when $k$ agents bid, then the winner pays proportional to $k/(k+1)$, varying the payment by a factor of 2 depending on the competition). Moreover, we show how it can be modified to get an equilibrium strategy with a slightly weaker robust guarantee of $5/(3e) \approx 0.61$ (and the optimal $1-1/e$ factor at equilibrium). Finally, we show that our mechanism gives the best possible bound under a wide class of auction-based mechanisms.

We consider repeated allocation of a shared resource via a non-monetary mechanism, wherein a single item must be allocated to one of multiple agents in each round. We assume that each agent has i.i.d. values for the item across rounds, and additive utilities. Past work on this problem has proposed mechanisms where agents can get one of two kinds of guarantees: (\(i\)) (approximate) Bayes-Nash equilibria via linkage-based mechanisms which need extensive knowledge of the value distributions, and (\(ii\)) simple distribution-agnostic mechanisms with robust utility guarantees for each individual agent, which are worse than the Nash outcome, but hold irrespective of how others behave (including possibly collusive behavior). Recent work has hinted at barriers to achieving both simultaneously. Our work however establishes this is not the case, by proposing the first mechanism in which each agent has a natural strategy that is both a Bayes-Nash equilibrium and also comes with strong robust guarantees for individual agent utilities. Our mechanism comes out of a surprising connection between the online shared resource allocation problem and implementation theory, and uses a surprising strengthening of Border’s theorem. In particular, we show that establishing robust equilibria in this setting reduces to showing that a particular subset of the Border polytope is non-empty. We establish this via a novel joint Schurconvexity argument. This strengthening of Border’s criterion for obtaining a stronger conclusion is of independent technical interest, as it may prove useful in other settings.

We study the problem of fair online resource allocation via non-monetary mechanisms, where multiple agents repeatedly share a resource without monetary transfers. Previous work has shown that every agent can guarantee 1/2 of their ideal utility (the highest achievable utility given their fair share of resources) robustly, i.e., under arbitrary behavior by the other agents. While this 1/2-robustness guarantee has now been established under very different mechanisms, including pseudo-markets and dynamic max-min allocation, improving on it has appeared difficult. In this work, we obtain the first significant improvement on the robustness of online resource sharing. In more detail, we consider the widely-studied repeated first-price auction with artificial currencies. Our main contribution is to show that a simple randomized bidding strategy can guarantee each agent a 2 - √2 ≈ 0.59 fraction of her ideal utility, irrespective of others' bids. Specifically, our strategy requires each agent with fair share α to use a uniformly distributed bid whenever her value is in the top α-quantile of her value distribution. Our work almost closes the gap to the known 1 - 1/e ≈ 0.63 hardness for robust resource sharing; we also show that any static (i.e., budget independent) bidding policy cannot guarantee more than a 0.6-fraction of the ideal utility, showing our technique is almost tight.