The Complexity of Contracts

DOI10.1137/20M132153XOpenAlexW3133464581MaRDI QIDQ5856150

Tim Roughgarden, Paul Dütting, Inbal Talgam-Cohen

Publication date: 24 March 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2002.12034

zbMATH Keywords

computational complexitycontract theorymoral hazardprincipal-agent problemhardness of approximationFPTAS

Mathematics Subject Classification ID

Related Items (3)

Learning approximately optimal contracts ⋮ Learning approximately optimal contracts ⋮ Designing menus of contracts efficiently: the power of randomization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for directed Steiner forest
• Combinatorial agency
• A generic approach to proving NP-hardness of partition type problems
• Computing optimal contracts in combinatorial agencies
• ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation
• General approximation algorithms for some arithmetical combinatorial problems
• The menu-size complexity of revenue approximation
• Polynomial-time computation of exact correlated equilibrium in compact games
• A \((1-1/e)\)-approximation algorithm for the generalized assignment problem
• Bayesian incentive compatibility via matchings
• Tight Approximation Algorithms for Maximum Separable Assignment Problems
• Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems
• Optimal Auction Design
• An Analysis of the Principal-Agent Problem
• Randomized metarounding
• Computational principal-agent problems
• Bernoulli factories and black-box reductions in mechanism design
• Algorithmic Bayesian Persuasion
• A Simple and Approximately Optimal Mechanism for an Additive Buyer
• Bounding the menu-size of approximately optimal auctions via optimal-transport duality
• A duality based unified approach to Bayesian mechanism design
• Constrained Signaling in Auction Design
• An algorithmic characterization of multi-dimensional mechanisms
• Some optimal inapproximability results
• Computing correlated equilibria in multi-player games

This page was built for publication: The Complexity of Contracts