EconCS Seminar

 

Lecturer: 

Yoav Gal-Tzur (Tel Aviv University)

Title: 

Combinatorial multi-action contracts

Abstract: 

Algorithmic contract design is an emerging frontier in the intersection of economics and computation, with combinatorial contracts being a core problem in this domain. A central model within combinatorial contracts explores a setting where a principal delegates the execution of a project, which can either succeed or fail, to an agent. The agent can choose any subset among a given set of costly actions, where every subset is associated with a success probability of the project, given by a set function $f$. The principal incentivizes the agent through a contract that specifies the payment upon success of the project.

We provide results on the complexity of the associated optimization problem --- finding the contract that maximizes the principal’s utility. On the positive side, we show that when the principal has access to a demand oracle for $f$, the optimal contract can be computed efficiently, if there are poly-many breakpoints in the agent's piece-wise utility function. A direct corollary is a poly-time algorithm for the optimal contract in settings where $f$ is supermodular. On the negative side, we show that for submodular $f$, exponentially-many demand oracle calls may be required to find the optimal contract.

Joint work with Paul Dütting, Michal Feldman and Aviad Rubinstein.

Location: 

Room 130, Feldman Building, Edmond J. Safra Campus.

 

Click here to add the EconCS Seminar to your Google Calendar