PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Matteo Bollini, Matteo Castiglioni, Alberto Marchesi

arXiv:2610.31002v1cs.GT

TL;DR

Task assignment with private types and hidden effort makes optimal contract design difficult, and standard auction characterizations do not directly cover the setting. The paper uses the cost-to-success-probability ratio to characterize and compute a single-task optimum, while for multiple tasks it studies approximation because an optimum may not exist.

  • Problem

    Bayesian contract design with hidden types and hidden actions is generally computationally challenging, and existing implementability conditions go beyond ordinary auction monotonicity.

    Source: §1 · p. 3

  • Method

    The paper reduces single-task reporting incentives to a critical value based on cost divided by success probability, then uses monotone allocation and virtual utilities in a Myerson-style approach.

    Source: §1.1 · p. 4, §3 · p. 9

  • Results

    A single-task optimal mechanism is characterized and efficiently computable; for multiple tasks, an ε-optimal mechanism can be computed in polynomial time when the number of agents is constant, although an optimum may not exist.

    Source: §3.2 · p. 17, §5.2 · pp. 27–28

  • Takeaways & Limitations

    The single-task setting admits a simple optimal mechanism despite hidden types, hidden effort, and multiple competing agents.

    Source: §1.1 · p. 4

    The mechanisms considered are Bayesian incentive-compatible and individually rational, and the stated multi-task approximation argument assumes SUP > 0.

    Source: §2.1 · p. 7, §5.2 · p. 29

Abstract

from arXiv · show

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 $\Theta(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.

1 Introduction

The paper studies task assignment when agents privately know their types and choose hidden effort, asking when these features permit simple, tractable mechanisms. It gives a Myerson-style optimal mechanism for one task and an approximation approach for multiple tasks, where optimal mechanisms may not exist.

1.2 Related Work

  • The paper studies exclusive task assignment with private information about both effort costs and success probabilities, alongside prior work on contract design with hidden information and hidden actions.It distinguishes its model from work allowing multiple agents per project with known costs and success functions, by restricting each task to one agent while introducing private information about both characteristics.Source: §1 · p. 3, §1.2 · p. 6

1.1 Our Contributions

  • For one task, incentive constraints depend on the ratio of effort cost to success probability, enabling a monotonicity-based characterization and an efficient Myerson-style optimal allocation.The allocation selects the agent with the largest positive ironed virtual utility, and the mechanism can be computed without enumerating joint type profiles.Source: §1.1 · p. 4
  • The single-task allocation also admits a dominant-strategy implementation with the same expected profit as the Bayesian implementation.The paper states that neither randomized allocations nor weaker Bayesian reporting improves optimal profit in this setting.Source: §1.1 · p. 4
  • For multiple tasks, an optimal mechanism may not exist because making some assignments increasingly rare while raising their success payments can approach an unattained profit supremum.For a constant number of agents, a linear-programming approach computes an incentive-compatible, individually rational mechanism with profit at least (1 − ϵ)SUP in time polynomial in input size and log(1/ϵ).Source: §1.1 · p. 5

2 Preliminaries

The preliminaries define single-task and multi-task assignment mechanisms and the incentive requirements they must satisfy. In both settings, the principal commits to an allocation and success-contingent payments while agents privately report types and choose effort after assignment.

2.1 Single-Task Setting

  • In the single-task setting, independently drawn private types determine agents’ success probabilities and effort costs, and the principal assigns at most one agent to a unit-reward task.A selected agent chooses whether to exert effort after receiving the contract; Bayesian incentive compatibility and individual rationality require truthful reporting and effort to be incentivized.Source: §2.1 · pp. 6–7
  • A single-task mechanism maps reported type profiles to an allocation distribution and success-contingent payments to selected agents.The principal seeks to maximize expected reward minus expected payments among Bayesian incentive-compatible and individually rational mechanisms.Source: §2.1 · p. 7

2.2 Multi-Task Setting

  • In the multi-task setting, feasible allocations match agents to tasks, with each agent and each task assigned at most once.Types specify task-specific costs and success probabilities, and mechanisms can coordinate assignments across agents rather than assigning tasks independently.Source: §2.2 · p. 8
  • The multi-task mechanism specifies a distribution over feasible allocations and contracts conditional on the reports and realized allocation.When there is one task, this representation reduces to the single-task allocation and payment mechanism.Source: §2.2 · p. 8

3 An Optimal Mechanism for a Single Task

This section characterizes and computes an optimal mechanism for the single-task problem, using critical values and ironed virtual utilities to determine the allocation. It also describes payments that make the allocation DSIC without reducing the optimal BIC mechanism’s profit.

3 An Optimal Mechanism for a Single Task

  • Incentive constraints depend only on the critical value, yielding monotonicity conditions and a Myerson-style mechanism design approach.The critical value is the minimum payment needed for a type to obtain nonnegative utility from exerting effort.Source: §3 · p. 9, §3.1 · pp. 9–10

3.1 Ordering the types

  • An optimal regular mechanism exists with allocation non-increasing in critical value, breaking ties by assigning higher allocation to types with greater success probability.Regular mechanisms restrict contracts to depend on an agent’s reported type, while others’ reports affect only the probability of receiving the task.Source: §3.1 · pp. 10–12

3.2 Computing an optimal mechanism

  • For any monotone allocation rule, a recursive payment scheme makes the mechanism BIC and IR and maximizes profit among mechanisms with that allocation rule.The scheme binds incentive constraints between consecutive types and completes payments to ensure individual rationality.Source: §3.2 · pp. 14–15
  • The resulting profit is expressible through virtual utilities that account for both critical values and success probabilities, so optimal allocation is found by maximizing their total over feasible allocation rules.The optimal mechanism’s contracts are then computed using the recursive payment scheme.Source: §3.2 · pp. 15–16
  • An optimal regular BIC and IR mechanism assigns the task to the agent with the highest positive ironed virtual utility, breaking ties consistently, and uses the specified contracts.If no agent has positive ironed virtual utility, the task is left unassigned.Source: §3.2 · p. 17
  • The optimal mechanism can be computed in polynomial time by recomputing ironed virtual utilities and contracts and then applying the allocation rule.The optimal BIC mechanism need not be DSIC, and the optimal DSIC mechanism need not be regular.Source: §3.2 · p. 17
  • Changing payments makes the optimal BIC allocation rule IR and DSIC while preserving its profit, so relaxing DSIC to BIC does not improve profit.In the DSIC mechanism, payments depend on the types of all agents other than the one performing the task.Source: §3.2 · p. 17

4 Price of Incentive Compatibility

This section measures the profit loss from eliciting agents’ true types relative to a clairvoyant mechanism. The worst-case loss is tight: incentive-compatible profit can be only a Θ(1/(NK)) fraction of the clairvoyant benchmark.

4 Price of Incentive Compatibility

  • PIC measures the profit loss from eliciting true types, against a clairvoyant benchmark that sees the agents’ types and ignores incentive constraints.The clairvoyant assigns the task to the best agent and offers the corresponding success-contingent payment.Source: §4 · pp. 18–19
  • A fixed contract for one chosen agent and type guarantees at least a 1/(NK) fraction of clairvoyant profit.The mechanism assigns the task only when the agent reports a critical value no greater than the chosen contract, which satisfies IR and BIC.Source: §4 · p. 19
  • In the worst case, PIC = Θ(NK), so incentive-compatible profit is only a Θ(1/(NK)) fraction of clairvoyant profit.The upper bound holds for every instance with positive clairvoyant profit, and a constructed instance gives the matching lower bound on PIC.Source: §4 · pp. 19–20

5 Multiple Tasks

The section examines multiple-task settings where an optimal mechanism may not exist because the supremum profit can be unattained. For a constant number of agents, it develops polynomially representable feasible mechanisms that approximate the supremum profit.

5 Multiple Tasks

  • With 2 agents, 2 tasks, and at most 2 types per agent, an instance has no optimal mechanism: small-probability large contracts raise profit toward an unattained supremum.Task 2 can distinguish types, but assigning it with positive probability incurs a loss that shrinks as its probability tends to zero; every mechanism assigning it can be improved.Source: §5 · pp. 21, 22, 25

5.1 Computing an approximately optimal mechanism

  • For any ϵ > 0 and constant N, an ϵ-optimal mechanism achieving at least (1 − ϵ)SUP can be computed in time polynomial in instance size and log(1/ϵ).The scheme is multiplicative, unlike the additive approximation approach of [Cac+24].Source: §5.1 · p. 25, §5.2 · p. 28
  • Expected-contract variables and auxiliary deviation-utility variables yield a linear-program formulation whose value equals SUP and whose feasible solutions recover BIC and IR mechanisms.The formulation uses expected contracts ν_i(t|θ) = y(t|θ)σ_i(t|θ) and linearizes incentive constraints with auxiliary variables.Source: §5.1 · pp. 25–26

5.2 An upper bound on the contracts

  • For constant N, an ϵ-optimal mechanism exists with contracts bounded by B, whose size is polynomial in instance size and 1/ϵ, and can be computed in polynomial time in instance size and log(1/ϵ).The proof constructs a bound by combining feasible linear-program solutions so allocations with positive expected contracts have positive probability.Source: §5.2 · pp. 27–28
  • The argument assumes SUP > 0; if SUP = 0, an optimal mechanism can leave every task unassigned.It also defines S as the number of selected LP optima and establishes S ≥ 1 when a valid mechanism collects positive profit.Source: §5.2 · p. 29
  • A convex combination of the Program 29 solution and selected LP optima yields a feasible, ε-optimal solution to Program 27.The combination uses weight 1 − ε on the Program 29 solution and weight ε/S on each selected optimum.Source: §5.2 · p. 29
  • For constant N, the resulting mechanism has contracts with polynomial encoding length.The two programs have polynomially many variables and constraints; the construction bounds contract sizes using polynomial-bit bounds on their solutions.Source: §5.2 · pp. 29–30

A Omitted Proofs from Section 3

The omitted proofs establish monotonicity of feasible allocation rules and show how the payment choice enforces incentive compatibility while maximizing profit for a fixed allocation rule.

A Omitted Proofs from Section 3

  • If one type has a lower critical value than another, its allocation probability must be at least as high in any IR and BIC mechanism.This is the monotonicity condition used in the characterization.Source: A Omitted Proofs from Section 3 · p. 33
  • For a regular mechanism with a monotone allocation rule, payments chosen by Equation (14) make the mechanism BIC and IR.The proof checks the interim constraints across types.Source: A Omitted Proofs from Section 3 · pp. 33–34
  • Equation (14) minimizes payments among BIC and IR mechanisms with the same allocation rule, and therefore maximizes profit for that rule.The proof establishes that the relevant incentive constraints bind, preventing lower ex-interim payments.Source: A Omitted Proofs from Section 3 · p. 34

B Ironing

Ironing transforms the allocation program into one with the same optimal solution and value. The resulting optimal allocation, paired with payments from Equation (14), gives an optimal mechanism.

B Ironing

  • Ironing the virtual utilities yields a program with the same optimal solution and value as Program (17).The construction substitutes suitable ironed virtual utilities into the allocation objective.Source: B Ironing · pp. 34–35
  • The allocation rule defined by Equation (18), paired with payments satisfying Equation (14), is optimal.The allocation rule is an optimal feasible solution to Program (17).Source: B Ironing · p. 35
  • The proof establishes optimality by bounding the original program’s value with the relaxed program’s value and showing equality for the ironed allocation.For that allocation, the difference between the two objective values is zero.Source: B Ironing · p. 36

C Deterministic Payment Schemes Are Optimal

Randomized payment schemes do not increase profit: every BIC and IR mechanism with randomized payments has a deterministic-payment counterpart with the same profit.

C Deterministic Payment Schemes Are Optimal

  • Consequently, randomized payment schemes are unnecessary for maximizing profit.The conclusion concerns payment randomization, not randomization over allocations.Source: C Deterministic Payment Schemes Are… · p. 37
  • Every BIC and IR mechanism with randomized payments has a deterministic-payment counterpart with the same allocation rule and profit.The proposition preserves both incentive compatibility and individual rationality.Source: C Deterministic Payment Schemes Are… · p. 37
  • The deterministic counterpart preserves truthful-report utility while giving agents no greater utility from misreporting.This establishes that the counterpart remains BIC and IR.Source: C Deterministic Payment Schemes Are… · p. 37

D Details Omitted from the Proof of Lemma 5.1

Lemma D.1 shows that multi-task payments can be made dependent on an agent’s own assigned task, but not on the tasks assigned to others, without reducing profit. The proof averages payments across allocations assigning that agent the same task, preserving individual rationality and incentive compatibility.

Lemma D.1

  • A BIC and IR mechanism can be replaced by one with at least the same profit whose payment to each agent depends on that agent’s assigned task, not others’ assignments.The lemma applies to every BIC and IR mechanism in the multi-task problem.Source: D Details Omitted from the Proof of… · p. 37

Payment construction

  • For allocations assigning agent 1 task 1, the proof averages the original payments, leaving payments in other cases unchanged.This construction is made for a report and allocation set where agent 1 receives task 1.Source: D Details Omitted from the Proof of… · p. 37

Incentives and profit

  • Truthful expected utility is unchanged, while Jensen’s inequality bounds misreport utility under the new scheme by its original level, preserving BIC and IR.The proof also states that the new mechanism gives the same principal profit as the original mechanism.Source: D Details Omitted from the Proof of… · p. 38
Loading 2610.31002v1…