Robust Equilibria in Shared Resource Allocation via Strengthening Border's Theorem
David X. Lin, Siddhartha Banerjee, Giannis Fikioris, Éva Tardos
Abstract
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: () (approximate) Bayes-Nash equilibria via linkage-based mechanisms which need extensive knowledge of the value distributions, and () 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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Collaborative Mean Estimation Among Heterogeneous Strategic Agents: Individual Rationality, Fairness, and Truthful ContributionAlex Clinton, Yiding Chen, Jerry Zhu, Kirthevasan KandasamyICML 2025
- Plant-and-Steal: Truthful Fair Allocations via PredictionsIlan Reuven Cohen, Alon Eden, Talya Eden, Arsen VasilyanNeurIPS 2024 · 9 citations
- Online Allocation and Learning in the Presence of Strategic AgentsSteven Yin, Shipra Agrawal, Assaf ZeeviNeurIPS 2022 · 3 citations
- Multidimensional Bayesian Utility Maximization: Tight Approximations to WelfareKira Goldner, Taylor LundyNeurIPS 2025 · 3 citations
- Mechanism Design via the Interim RelaxationKshipra Bhawalkar, Marios Mertzanidis, Divyarthi Mohan, Alexandros PsomasNeurIPS 2025 · 2 citations
