Sequential Linear Contracts Under Matroid Constraints
1 : University of Waterloo [Waterloo]
We study linear contracts in principal-agent settings, where the agent is allowed to take several actions and observe the outcome of each action before taking the next action. Each action of the agent corresponds to an element in the ground set of a given matroid. Once the agent decides to not take any further actions, the agent returns a collection of elements that is an independent set in the matroid. After that, the principal observes only the total value of the elements returned by the agent, but not the taken actions themselves or the returned elements. Also as a reward, the principal obtains the total value of the returned elements. To take each action the agent incurs a cost, and so naturally the agent requires a fraction of the principal's reward as an incentive for taking actions. The principal needs to decide what fraction of their reward to give to the agent so that the principal's expected utility is maximized. In this work, we study connections of sequential contracts under matroid constraints to other problems and show important cases when the optimal contract can be efficiently computed or can be efficiently approximated.