Contract theory is one of the pillars of microeconomic theory. A principle delegates the execution of a costly task to one or multiple agents. The principal cannot observe which actions are being taken but only the outcome, for example, if a project succeeds. By defining a contract, which defines a compensation to the agents in the case of a success, they shall be incentivized to exert effort.

In this talk, we will study two different variants of computing optimal contracts. First, we consider one agent and multiple actions, who can choose between all subsets of actions available to them. Then, we consider multiple agents with one action each. In either case, the number of possible choices of actions is exponential in the input representation. We therefore discuss the question under what assumption efficient exact or approximation algorithms exist.

Based on joint work with Paul Dütting, Tomer Ezra, and Michal Feldman in FOCS 2021 and STOC 2023.

We present a new approximation algorithm for the (metric) prize-collecting traveling salesperson problem (PCTSP). In PCTSP, opposed to the classical traveling salesperson problem (TSP), one may not include a vertex of the input graph in the returned tour at the cost of a given vertex-dependent penalty, and the objective is to balance the length of the tour and the incurred penalties for omitted vertices by minimizing the sum of the two. We present an algorithm that achieves an approximation guarantee of 1.774 with respect to the natural linear programming relaxation of the problem. This significantly reduces the gap between the approximability of classical TSP and PCTSP, beating the previously best known approximation factor of 1.915. As a key ingredient of our improvement, we present a refined decomposition technique for solutions of the LP relaxation, and show how to leverage components of that decomposition as building blocks for our tours.