Optimal task assignment methods improve multi-agent contract design
Matching Tasks to Agents: Mechanism Design for Multi-Agent Contracts
Computer Science and Game Theory
Summary
Assigning tasks to agents who know their own abilities and costs can be tricky because they might hide information or not put in effort. The authors studied this problem and found a simpler way to design contracts for one task that considers how costly effort is relative to the chance of success. They also showed how to find the best method efficiently and understand its limits. For multiple tasks, they found that the perfect method might not exist but gave ways to get close when dealing with a few agents.
What this means in practice
- •For contract designers: Design task contracts that handle private agent types and hidden efforts efficiently for tasks requiring a single agent.
- •For project managers: Approximate optimal task assignments across multiple agents when the number of agents is small to improve contract outcomes.
A theory result. No direct application yet.
Authors
Matteo Bollini, Matteo Castiglioni, Alberto Marchesi
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.