Robustness and Approximation for the Linear Contract Design

Abstract

We consider the contract design problem where a principal designs a contract to incentivize an agent to undertake n independent tasks. In the contract, the principal decides the payment w={w0,w1,...,wn} . The principal is associated with a non-decreasing revenue function f(k), where k is the number of successful tasks. The objective of the contract design problem is to maximize the principal’s expected profit, i.e., maxs,w{F(s)−W(s,w)} , where s is the agent’s strategy set, F(s) is the expected revenue of the principal and W(s,w) is the expected payment to the agent. Given the payment w , the agent will choose her strategy from s to maximize her expected utility. For each task, the agent may work hard or shirk and her strategy is to decide the number of tasks to work hard on. If the principal knows the strategy set s , the optimum contract can be found by linear programming. In [7], a more complicated model where the strategy set s is unknown to the principal is considered, they showed that the linear contract is robust and presented an 1/N-approximation algorithm given N≤n dominating strategies. In this paper, we further analyze this model and prove the approximation factor can be upper bounded by (1−αN)/(1−αNN) , where αN∈[0,1) is a given constant.