Strategic Multi-Agent Resource Allocation via Statistical Contracts

Ben Chugg; Michael I. Jordan; Aaditya Ramdas

cs.MAOct 13, 2026

Strategic Multi-Agent Resource Allocation via Statistical Contracts

Authors: Ben Chugg, Michael I. Jordan, Aaditya Ramdas

Organizations: Carnegie Mellon University · UC Berkeley, ÉNS, & Inria · Stanford University

Abstract

We study a class of strategic hypothesis testing problems in which a principal aims to allocate resources among competing agents who possess data or data-generating mechanisms that may be relevant to the principal's goals. Each agent can pay a participation cost to opt into a statistical contract, in which case they generate data from a private distribution and receive an allocation based on a predetermined (and publicly known) mechanism. Each agent is either "null" or "non-null" and the principal's goal is to design the contract to limit the allocation to the former while maximizing transactions with the latter. Using e-values, we define a "continuous-closure," a set of allocations which prevents null agents from profiting in expectation and provides post-hoc risk control for general loss functions under arbitrary dependence. When the loss is the fraction of resources allocated to null agents, the region admits polynomial-time linear optimization. We also give explicit, interpretable closed-form approximations, and we analyze participation from a non-null agent's perspective, giving conditions under which entry into the contract is profitable. Finally, we extend the framework to support online arrival of the agents, in which case the principal has to make irrevocable on-the-fly decisions, and provide a method which gives time-uniform error-control in this setting.

Figures & tables

Figure 1: Strategic multi-agent resource allocation. The principal publicly announces the mechanism $\mathcal{M}$ , an optional budget $B$ , and the costs $(c_{i})$ . Each agent can enter the contract, at which point they pay $c_{i}$ and generate data from their private distribution. The mechanism $\mathcal{M}$ then computes an allocation for each agent.

Panel of Figure 2 — Figure 2: The polytopes $\mathsf{P}_{\Delta}(E)$ (blue) and $\mathsf{Q}_{\Delta}(E)$ (red) for $m=3$ agents with $c_{i}=1$ , $E=(8,20,18)$ , $\Delta=0.1$ , and $B=40$ , along with the allocations selected by $\mathcal{M}^{\textnormal{{cum}}}_{\Delta}$ , $\mathcal{M}^{\textnormal{{AoN}}}_{\Delta}$ , and $\mathcal{M}^{\textnormal{{e-bh}}}_{\Delta}$ . Both regions satisfy the caps $A_{i}\leq c_{i}E_{i}$ and the budget. $\mathcal{M}^{\textnormal{{AoN}}}_{\Delta}$ funds all three agents, $\mathcal{M}^{\textnormal{{e-bh}}}_{\Delta}$ drops agent 1, whose evidence is weakest, and $\mathcal{M}^{\textnormal{{cum}}}_{\Delta}$ funds agent 2 fully and gives agent 3 the remainder needed to reach $C/\Delta$ .

Figure 3: The relative optimality gap of various mechanisms compared with optimizing over the full continuous-closure region $\mathsf{P}_{\Delta}$ , as the dispersion $\sigma_{v}$ of the weights varies, for linear utility (left) and logarithmic utility (right). Lines show medians and shaded bands show interquartile ranges over 150 independently generated active instances with $m=30$ , $B=30$ , and $\Delta=0.1$ . The same instances are used at every value of $\sigma_{v}$ , and $\sigma_{v}=0$ corresponds to equal weights.

Figure 4: Relative optimality gap as the number of agents varies, for linear utility (left) and logarithmic utility (right). Lines show medians and shaded bands show interquartile ranges over 150 independently generated active instances at each size, with $B=30$ , $\Delta=0.1$ , and $\sigma_{v}=0.8$ fixed. As in Figure 3 , the gap is measured relative to optimization over $\mathsf{P}_{\Delta}$ .

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Loss	Definition	Interpretation
Null allocation proportion	$\textnormal{{NAP}}_{N}(A)=\sum_{i\in N}A_{i}/\sum_{j\in[m]}A_{j}$	Share of total allocation going to null agents.
Total null allocation	$\ell_{N}(A)=\sum_{i\in N}A_{i}$	Absolute amount allocated to null agents.
Budget-normalized null allocation	$\ell_{N}(A)=B^{-1}\sum_{i\in N}A_{i}$	Fraction of a fixed budget allocated to null agents.
Weighted null allocation proportion	$\ell_{N}(A)=\sum_{i\in N}w_{i}A_{i}/\sum_{j\in[m]}w_{j}A_{j}$	Weighted share of allocation going to null agents.
Weighted null allocation	$\ell_{N}(A)=\sum_{i\in N}w_{i}A_{i}$	Weighted absolute allocation to null agents.
Maximum null allocation	$\ell_{N}(A)=\max_{i\in N}A_{i}$	Largest allocation made to any null agent.

Appendix

Table 1: Examples of loss functions the principal may consider.

Mechanism Design

Mechanism design studies rules for allocating resources and shaping incentives when participants hold private information or act strategically.

See all 142 papers

Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation
Jul 13, 2025Yan Dai, Negin Golrezaei, Patrick JailletGame Theory Online Convex Optimization
Operations Research Center, MIT. · Sloan School of Management, MIT. · Department of EECS, MIT.
Strategyproof Deep Reinforcement Learning for Online Resource Allocation
Oct 27, 2026Fariba Dehghan, Sebastian Stein, Vahid Yazdanpanah +1Online Resource Allocation Mechanism Design
University of Southampton
Minimax-Optimal Online Contract Design with Unrestricted Bounded Contracts
Sep 17, 2026Rui Ai, David Simchi-Levi, Han ZhongMechanism Design Minimax Regret
Massachusetts Institute of Technology · Shanghai Jiao Tong University

Jul 13, 2025J/K move · Enter open · S save

Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation

Yan Dai, Negin Golrezaei, Patrick Jaillet

Operations Research Center, MIT. · Sloan School of Management, MIT. · Department of EECS, MIT.

Game Theory Online Convex Optimization Mechanism Design Primal-Dual Optimization Online Resource Allocation Constrained Optimization+1

Open paper AskPDF arXiv

We study the dynamic allocation of indivisible resources to strategic agents under long-term constraints, where the planner aims to maximize social welfare, satisfy multiple constraints, and elicit near-truthful reports. We find standard primal-dual methods fragile in this setting: agents easily manipulate their reports to distort dual variables, sacrificing social efficiency for individual utility. To address this, we propose the Incentive-Aware Primal-Dual (IAPD) framework. On the primal side, we integrate three components to suppress manipulation: a VCG-based payment neutralizes immediate misreporting benefits, while epoch-based lazy updates and random exploration together ensure potential future gains are outweighed by immediate penalties. On the dual side, to overcome a learning barrier due to lazy updates -- which we call the "price of incentives" -- we design a novel optimistic online learning algorithm, O-FTRL-FP. It utilizes a fixed-point oracle to resolve the circular dependency between optimistic dual variables and the resulting allocations. Ultimately, our mechanism attains

\tilde{\mathcal O}(\sqrt T)

social welfare regret, satisfies all long-term constraints, and induces a near-truthful equilibrium. It also smoothly generalizes to multi-unit multi-demand allocation problems. Notably, this

\tilde{\mathcal O}(\sqrt T)

regret near-matches the non-strategic

Ω(\sqrt T)

lower bound, demonstrating that incentive-awareness can be accommodated at nearly no cost.

Abstract

Mechanism Design

Explore similar work

Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation

Strategyproof Deep Reinforcement Learning for Online Resource Allocation

Minimax-Optimal Online Contract Design with Unrestricted Bounded Contracts