Videos

Algorithms, Approximation, and Learning in Market and Mechanism Design: "Algorithmic Contract Design"

November 8, 2023
Keywords:
  • market design
  • mechanism design
  • auctions
  • matching
  • approximation
  • equilibrium analysis
  • algorithmic game theory
  • complexity
  • economic theory
  • discrete optimization
  • graph theory
  • mathematical programming
Abstract
Contract design captures situations where a principal delegates the execution of a costly task to an agent. To complete the task, the agent chooses an action from a set of costly actions. The principal can only observe the outcome, which is stochastically determined by the chosen action. The principal incentivizes the desired action through a contract, that specifies payments based on the observed outcome. In this talk, I will survey several papers on combinatorial contracts, which highlight different sources of complexity that arise in contract design. The first (FOCS’21,SODA’24) is where the agent can choose any subset of a given set of actions; the second (STOC’23) is where the principal motivates a team of agents. We provide (approximation) algorithms and hardness results for the optimal contract problem in these scenarios. Based on joint work with Paul Duetting, Tomer Ezra, Yoav Gal Tzur and Thomas Kesselheim.