More Like this

1. Robust Resource Allocation via Competitive Subsidies

   https://doi.org/10.4230/lipics.itcs.2026.96  

   Lin, David X; Fikioris, Giannis; Banerjee, Siddhartha; Tardos, Éva (January 2026, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Saraf, Shubhangi (Ed.)

   Abstract: 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≈ 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) ≈ 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. 

   more » « less
2. Online Resource Sharing: Better Robust Guarantees via Randomized Strategies

   https://doi.org/10.24963/ijcai.2025/21  

   Lin, David X; Hall, Daniel; Fikioris, Giannis; Banerjee, Siddhartha; Tardos, Éva (September 2025, International Joint Conferences on Artificial Intelligence Organization)

   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. 

   more » « less
3. Non-Quasi-Linear Agents in Quasi-Linear Mechanisms (Extended Abstract)

   https://doi.org/10.4230/LIPIcs.ITCS.2021.84  

   Babaioff, Moshe; Cole, Richard; Hartline, Jason; Immorlica, Nicole; Lucier, Brendan (January 2021, Leibniz international proceedings in informatics)

   null (Ed.)

   Mechanisms with money are commonly designed under the assumption that agents are quasi-linear, meaning they have linear disutility for spending money. We study the implications when agents with non-linear (specifically, convex) disutility for payments participate in mechanisms designed for quasi-linear agents. We first show that any mechanism that is truthful for quasi-linear buyers has a simple best response function for buyers with non-linear disutility from payments, in which each bidder simply scales down her value for each potential outcome by a fixed factor, equal to her target return on investment (ROI). We call such a strategy ROI-optimal. We prove the existence of a Nash equilibrium in which agents use ROI-optimal strategies for a general class of allocation problems. Motivated by online marketplaces, we then focus on simultaneous second-price auctions for additive bidders and show that all ROI-optimal equilibria in this setting achieve constant-factor approximations to suitable welfare and revenue benchmarks. 

   more » « less
4. Optimally Auditing Adversarial Agents

   https://doi.org/10.1609/aaai.v40i20.38722  

   Das, Sanmay; Yu, Fang-Yi; Zhang, Yuang (March 2026, Proceedings of the AAAI Conference on Artificial Intelligence)

   Fraud can pose a challenge in many resource allocation domains, including social service delivery and credit provision. For example, agents may misreport private information in order to gain benefits or access to credit. To mitigate this, a principal can design strategic audits to verify claims and penalize misreporting. In this paper, we introduce a general model of audit policy design as a principal-agent game with multiple agents, where the principal commits to an audit policy, and agents collectively choose an equilibrium that minimizes the principal’s utility. We examine both adaptive and non-adaptive settings, depending on whether the principal's policy can be responsive to the distribution of agent reports. Our work provides efficient algorithms for computing optimal audit policies in both settings and extends these results to a setting with limited audit budgets. 

   more » « less
5. Information Design in Spatial Resource Competition

   Yang, Pu; Iyer, Krishnamurthy; Frazier, Peter I. (December 2019, Lecture notes in computer science)

   We consider information design in spatial resource competition, motivated by ride sharing platforms sharing information with drivers about rider demand. Each of N co-located agents (drivers) decides whether to move to another location with an uncertain and possibly higher resource level (rider demand), where the utility for moving increases in the resource level and decreases in the number of other agents that move. A principal who can observe the resource level wishes to share this information in a way that ensures a welfare-maximizing number of agents move. Analyzing the principal’s information design problem using the Bayesian persuasion framework, we study both private signaling mechanisms, where the principal sends personalized signals to each agent, and public signaling mechanisms, where the principal sends the same information to all agents. We show: 1) For private signaling, computing the optimal mechanism using the standard approach leads to a linear program with 2 N variables, rendering the computation challenging. We instead describe a computationally efficient two-step approach to finding the optimal private signaling mechanism. First, we perform a change of variables to solve a linear program with O(N^2) variables that provides the marginal probabilities of recommending each agent move. Second, we describe an efficient sampling procedure over sets of agents consistent with these optimal marginal probabilities; the optimal private mechanism then asks the sampled set of agents to move and the rest to stay. 2) For public signaling, we first show the welfare-maximizing equilibrium given any common belief has a threshold structure. Using this, we show that the optimal public mechanism with respect to the sender-preferred equilibrium can be computed in polynomial time. 3) We support our analytical results with numerical computations that show the optimal private and public signaling mechanisms achieve substantially higher social welfare when compared with no-information and full-information benchmarks. 

   more » « less