Research map / Multi-agent systems and games / Games and equilibria
Contract Design Under Approximate Best Responses
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies hidden-action principal-agent (contract design) when the agent plays a worst-case delta-approximate best response; gives a polynomial-time exact algorithm for optimal robust contracts and a no-regret online learning algorithm.
Problem
Designing optimal contracts when the agent may select any action that is up to delta suboptimal (approximate best response), a robustness setting where prior contract theory assumed exact best responses.
Approach
Shows that, unlike Stackelberg and Bayesian persuasion settings, optimal delta-robust contracts can be computed in polynomial time by guessing the exact and worst delta-best-response action pair and solving O(n) LPs whose hyperplanes are parallel; also bounds the price of robustness independently of the inducibility gap and gives a UCB1-based no-regret algorithm over a discretized contract grid.
Key results
- Optimal delta-robust contract computable in polynomial time by solving O(n^3) LPs.
- Upper bound max{0, SW - delta} on robust principal utility is tight; lower bound OPT - 2sqrt(delta) + delta is tight up to O(1/n).
- No-regret algorithm (UCB1 over a grid of contracts) with regret O~(T^{1-1/(2(m+1))}) against optimal delta-robust contract.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the approximate-best-response parameter δ | Optimal robust contract design · Hidden-action principal-agent problems | principal utility: \textnormal{OPT}(\delta) is non-increasing in \delta | Hurt |
| Design contracts robust to any δ-best response instead of relying on an exact best response | Optimal contract design · Hidden-action principal-agent problems | principal utility: \textnormal{OPT}(\delta) \ge \textnormal{OPT} - 2 \sqrt{\delta} + \delta | Hurt |
| Use the uniform contract grid and UCB1 | Learning δ-robust contracts · Typed hidden-action principal-agent problems | regret: \mathcal{\widetilde{O}} \left( T^{1- \frac{1}{2(m+1)}} \right) | Helped |
| Use δ-robust responses while comparing against an optimal non-robust contract | Learning contracts · Typed hidden-action principal-agent problems | regret: \mathcal{\widetilde{O}} \left( T^{1- \frac{1}{2(m+1)}} \right) + 2 \sqrt{\delta} T | Mixed |
| Shift payments toward the principal's reward vector when converting a δ-robust contract to a (δ + ε)-robust contract | Robust contract utility · Typed hidden-action principal-agent problems | principal utility: 2 \sqrt{\epsilon} | Hurt |
| Set δ to \nicefrac{1}{T^\alpha} with α>0 | UCB1 contract-learning algorithm · Typed hidden-action principal-agent problems | regret against an optimal non-robust contract: sublinear | Helped |
Surprising findings
- Unlike Stackelberg games and Bayesian persuasion, computing optimal robust contracts is tractable in polynomial time despite a continuous contract space.
- Robust principal utility bounds do not depend on the inducibility gap, and OPT(delta) is continuous in delta.
Limitations
- Regret bound depends exponentially on the number of outcomes m, and a lower bound shows this dependence is unavoidable.
- Learning results assume stochastic agent types and a fixed, known finite type set; the adversarial extension is only a remark.
- Regret against the non-robust optimum requires delta to shrink with the horizon T.
Experimental setup
Metrics: principal utility cumulative pseudo-regret
Baselines: non-robust optimal contract Stackelberg robust commitment (QPTAS) prior online contract learning algorithm
Builds on: Stackelberg games robust commitment Bayesian persuasion robust signaling UCB1
Closest papers by meaning
- Learning Optimal Contracts: How to Exploit Small Action Spaces (ICLR 2024 · similarity 0.91)
- Contracting with a Learning Agent (NeurIPS 2024 · similarity 0.90)
- Generalized Principal-Agent Problem with a Learning Agent (ICLR 2025 · similarity 0.88)
- Learning in Online Principal-Agent Interactions: The Power of Menus (AAAI 2024 · similarity 0.87)
- Scalable Neural Incentive Design with Parameterized Mean-Field Approximation (NeurIPS 2025 · similarity 0.84)
- Online Information Acquisition: Hiring Multiple Agents (ICLR 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.