CS Paper Radar

Matching Tasks to Agents: Mechanism Design for Multi-Agent Contracts

Matteo Bollini, Matteo Castiglioni, Alberto Marchesi

cs.GT ·submitted 2026-10-22 09:42 UTC · v1
benchmark

Abstract

We study task assignment under adverse selection and moral hazard. In the single-task setting, agents privately know their types, which determine their success probabilities and effort costs. Based on the agents' reported types, the principal selects an agent to perform the task and offers a success-contingent payment. Although optimal Bayesian contract design is generally computationally intractable and Myerson's characterization does not directly extend to settings with hidden actions and multidimensional private information, we show that the single-task problem admits a simple Myerson-style characterization. Our key insight is that incentive constraints depend only on the ratio between effort cost and success probability. We characterize an optimal mechanism and show that it can be computed in polynomial time. We also establish a tight $Θ(1/(NK))$ worst-case bound on the ratio between the optimal profit and the full-information benchmark, where $N$ is the number of agents and $K$ is the number of types per agent. We then extend our analysis to multiple tasks, showing that an optimal mechanism may not exist. Nevertheless, for a constant number of agents, we provide a polynomial-time approximation scheme for the supremum profit.

Closest papers

Nearest neighbours by meaning across the whole index.

Strategic Disclosure of Action Space in Principal-Agent Contracts

cs.GT econ.TH ·2026-09-21 ·Xiaotie Deng, Ningyuan Li
theory similarity 0.72
Abstract · Full version of the manuscript accepted at WINE 2026. A one-page extended abstract will appear in the conference proceedings. A substantiall…

We study strategic disclosure of the action space in principal-agent contracting, where an agent selects a disclosed action set to shape the principal's perception of her capabilities before contract design. Unaware of the strategic disclosure, the principal designs a revenue-optimal contract as if the disclosed action set were complete and accurate. We consider two variants distinguished by cost verifiability. When costs are unverifiable, the agent can extract the entire first-best surplus, leaving the principal with zero revenue. When costs are verifiable, we characterize the agent's optimal disclosure strategy in binary-outcome settings and, more generally, when the principal is restricted to linear contracts, reducing the agent's problem to a two-variable convex optimization problem. We prove that the agent can secure utility of at least a $1/e$ fraction of the first-best surplus, which also yields a $1/e$ welfare guarantee under optimal disclosure. While the principal's revenue can be arbitrarily small compared to the first-best surplus, when the ratio of maximum to minimum expected reward among non-null base actions is at most $L$, we establish a revenue guarantee of $Θ(1/\log L)$ relative to the first-best surplus. We also compare utilities and welfare under strategic disclosure with their counterparts in the canonical model. Finally, we extend the agent's $1/e$ utility guarantee to general outcome spaces without restricting the principal to linear contracts. Our results show how strategic action-space disclosure changes the distribution of surplus while preserving a constant-factor welfare guarantee under the agent's optimal disclosure.

0.31

Transparency in Team Contracts

cs.GT econ.TH ·2026-11-05 ·Paul Dütting, Yingkai Li, Inbal Talgam-Cohen, Jinzhao Wu
similarity 0.72
Abstract

In contract design, the principal is often better informed about the project's chances of succeeding than the agents. To incentivize effort, the principal has two main tools: first, to design a contract, sharing part of the project's success among the agents; second, to design a (Bayesian) persuasion scheme, selectively sharing information with the agents. In this work we are interested in the optimal combination of both these tools. We tackle the joint problem through the prism of simplicity vs. optimality, and establish a stark dichotomy: The simple disclosure scheme of full transparency achieves a tight $4/3$-approximation to the optimal combination of information disclosure and team contract, when the team's production function is submodular. In contrast, full transparency can be arbitrarily far from optimal when production is supermodular. The techniques that we develop to bound the gap for submodular functions, also yield a new deterministic polynomial-time approximation algorithm for pure multi-agent contract design, with a significantly improved approximation ratio of $2.311$, and thus a $3.081$-approximation algorithm for the joint information and contracting problem.

0.40

Welfare in Envy-free Contracts: When Agents Have Sparse Interests

cs.GT ·2026-11-08 ·Junjie Chen, Cong Chen, Takuro Yamashita
similarity 0.71
Abstract

We study welfare maximization under envy-free contracts, where a principal assigns tasks and offers success-contingent payments to heterogeneous agents with hidden effort. For unit-demand agents, we establish a sharp complexity boundary: the problem is polynomial-time solvable when each agent is interested in at most two tasks, but NP-hard with at most three interests. Our algorithm analyzes tree-structured dependencies among forced assignments and reduces optimization to maximum-weight independent set in a perfect graph. When agents may receive multiple tasks, no polynomial-time constant-factor approximation exists unless $\mathrm{P}=\mathrm{NP}$. Finally, with homogeneous success probabilities and rewards, we establish a welfare- and revenue-preserving equivalence between unit-demand contract design and envy-free pricing. This yields polynomial-time welfare maximization without restricting interests, while revenue maximization remains NP-hard.

0.11

An Introduction to Contract Theory for Computer Scientists

cs.GT ·2026-10-12 ·Paul Duetting, Michal Feldman, Inbal Talgam-Cohen
publishedsurvey similarity 0.71
Abstract

This survey introduces contract design to computer scientists: using outcome-based payments to incentivize effort. We discuss applications that motivate a computational approach to contract design, ranging from online labor markets, to incentive-aware algorithmic classification, to emerging ecosystems of AI agents. We present the classic principal-agent model and introduce basic concepts. We show how optimal contracts are computable via linear programming, and why they can be opaque and brittle. Motivated by this we turn to simpler contract formats, specifically linear contracts. We discuss approximation guarantees, and robust (max-min) optimality of such contracts. We then move beyond the single-agent setting to combinatorial contract settings with multiple agents, mapping the algorithmic landscape of tractability and approximation. Finally, we discuss partial information settings through the lens of learning algorithms, and outline open directions. The goal is a concise, accessible entry point that connects economic foundations with algorithmic tools and highlights opportunities for new theory and applications.

0.59

BROCADE: Broker-based Contract Design for the Multi-Agency Model

cs.GT ·2026-10-26 ·Yangguang Shi, Ron Lavi, Jie Zhang
benchmarktheory similarity 0.71
Abstract

We study welfare maximization in a contract model with $m$ principals who privately value a public project's success and $n$ agents whose costly effort is unobservable. Contracts induce truthful dominant strategies for principals and equilibrium effort by agents, maximizing the expected total value of eligible principals. We develop three tools: a broker that separates payments from principals and payments to agents, an extension of Myerson's Lemma characterizing dominant-strategy incentive compatibility (DSIC), and a black-box reduction to budget-constrained single-principal contract design. When the success probability is a strictly monotone XOS function of agents' actions, these tools yield three results. First, a deterministic DSIC contract achieves a constant approximation against a benchmark that qualifies every principal and maximizes success probability using budget $\sum_j v^j$, but may violate budget balance (BB). Second, against benchmarks with budgets at least the largest principal value, deterministic DSIC and BB contracts admit no finite approximation guarantee, even with two agents. Universally DSIC and universally BB randomized contracts have an $Ω(n)$ approximation lower bound, even for a fixed number of principals. Third, using one quarter of the optimal fixed-price revenue supported by at least two principals as the benchmark budget, we obtain a universally DSIC and universally BB randomized contract with an $O(\log m)$ approximation ratio independent of $n$.

0.11

Approximating Combinatorial Contracts with Arbitrary Costs

cs.GT cs.DS ·2026-09-18 ·Xiaotie Deng, Hanyu Li, Chenghua Liu
theory similarity 0.70
Abstract

We study single-agent combinatorial contracts under linear payments. Under a reward share $α\in[0,1]$, an agent chooses a subset $S$ of $n$ hidden actions, generating reward $f(S)$ at cost $c(S)$, to maximize $αf(S)-c(S)$, while the principal receives $(1-α)f(S)$. For nonnegative additive rewards and monotone supermodular costs, Dütting et al. (SODA 2026) proved an exponential supply-query lower bound for exact optimization and left open whether a representation-independent approximation is possible. We resolve this question in a stronger form, removing all structural assumptions on the cost function: for nonnegative additive rewards, arbitrary normalized nonnegative set costs, and every $\varepsilon\in(0,1)$, we give a deterministic $(1-\varepsilon)$-approximation using $O(n\log(n+1)/\varepsilon)$ supply queries, with query complexity independent of numerical bit lengths and breakpoint separation. More generally, the same guarantee and asymptotic query complexity hold for normalized monotone subadditive rewards and arbitrary normalized nonnegative costs under exact best-response and value-query access. The key idea is a cost-independent, reward-side scale certificate. The algorithm tries all singleton rewards as candidate anchors; one of them brackets the optimal retained share within a factor $n^2$. Geometric search and monotonicity of the induced response reward then yield the approximation without enumerating best-response breakpoints.

0.26

Sharp Bounds for Truthful-in-Expectation Scheduling

cs.GT ·2026-11-03 ·Yunpeng Li
theory similarity 0.67
Abstract

We study randomized mechanisms for scheduling indivisible jobs on $n$ unrelated machines. Each machine is controlled by a selfish agent who privately knows its processing time for each job. A mechanism assigns every job to a machine and makes payments. We require truthfulness in expectation: no agent can increase its expected payment minus its expected processing cost by misreporting, regardless of the other agents' reports. The makespan is the maximum total processing time assigned to a machine; the objective is to minimize its expectation. We prove that the optimal approximation ratio is $(n+1)/2$ for every $n\ge7$, relative to the minimum makespan of an integral assignment. The lower bound holds for every $n$ and allows unrestricted computation and arbitrary correlations among assignments, assuming finite expected payments and a guarantee uniform over all finite job counts. The matching mechanism uses correlated rounding and runs in expected polynomial bit time on rational inputs. These guarantees hold for all finite nonnegative processing times. For two machines, we characterize the optimal approximation ratio exactly as an analytic constant, approximately $1.505995705434$, and give a mechanism attaining it. For three machines the optimal ratio is $2$. For four, five, and six machines we obtain upper bounds of $3$, $105/32$, and $29/8$, respectively, compared with the general lower bound $(n+1)/2$. The proofs for $n\ge7$ do not rely on computer-assisted certificates; the two- and three-machine results use exact rational computer-assisted certificates.

0.18

Strategic Multi-Agent Resource Allocation via Statistical Contracts

cs.MA cs.GTstat.ME ·2026-10-13 ·Ben Chugg, Michael I. Jordan, Aaditya Ramdas
similarity 0.66
Abstract · 36 pages, four figures

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.

0.53