# Simple versus Optimal Contracts <!-- Put the link to this slide here so people can follow --> Orign paper: By Paul Paul Dütting (LSE) Extended: By Cheng, GeCheng --- ## Overview 1. The model 2. Property of Linear Action 3. The result * Robust Optimality * Approximation Guarantees of Linear Contracts 4. Future Work --- ## The model: Principal-Agent Model * Player: Principal and Agent * Agent has $n$ actions $A = \{a\}$. The agent may cause $m$ outcome $\Omega = {x}$ to the principal. * So each action $a_n = \{ F_n,c_n \}$, with $F_n$ is the distribution over $\Omega$, and $c_n$ is the cost of this action. ---- ## The model: Principal-Agent Model (2) * Goal of The Principal: Design an payment scheme $\phi$ s.t. $\phi(x)$ is how much he should pay to the Agent. His is to maximise $x - \phi(x)$ * Goal of The Agent: Under the payment scheme $\phi$, maximise $\phi(x(a)) - c_a$. * $a$ can be mix strategy ---- ## The model: The Hidden Model * In our model, we suppose principle and agent know all the $c_n$ and $R_n = E(X(a_n))$. #### Other assumption * No $R_a > R_b$, and $c_a < c_b$ case * There is a unique action a with maximum welfare R_a − c_a. * Implement $R_0, c_0 = 0$ --- ## What is Linear and Optimal Contract * If $\phi(x) = a x + b$, it is an affine contract, $b=0$ and it is linear contract. * It can be any shape. This is a game of max-min property. --- ## Robust Optimality * For every ambiguous principal-agent setting, an optimal linear contract has **maximum worst-case expected payoff** (to the principal) among all limited liability contracts. * limited liability contract: $\phi(R_n) - c_n > 0$ for all $n$ --- ## Observations for Robust Optimality 1. For any contract $t$, we may construct an $\{F_n\}$ and a linear contract $t'$ that $E_p(t) = E_p(t')$ 2. Suppose the linear contract is $t'$, and expect payoff is $R(t'(x_a)) = t'(E(x_a))$. --- ## Sketch of the proof of Robust Optimality * From 1., we have $E_p(t) = E_p(t')$ for all $t$ * From 2., we have $E_p(t') = t'(E(x_a))$ for any distribution. --- ## Approximation Guarantees of Linear Contracts Take $\rho$ is the worst-case ratio between the expected principal payoff under an **optimal contract** and under the best **linear contract** 1. $\rho = n$, $n$ is number of actions. 2. $E(hightest\ reward)/E(lowest\ reward) = H$, $\rho = \Theta(H)$ 3. $E(hightest\ cost)/E(lowest\ cost) = C$, $\rho = \Theta(C)$ 4. $m ≥ 3$ outcomes, $\rho$ can be arbitrarily large. ---- ## Proof of 1. * Permute $a$ with $R_a -c_a$,and $\alpha_{a',a} = \frac{c_a-c_{a'}}{R_a - R_a'}$, $\alpha_{i} = \alpha_{i-1,i}$ $$ OPT \leq R_N -c_N \leq \sum_{i\leq N} (1-\alpha_{i-1,i}) R_i $$ $$ \leq N \max (1-\alpha_i) R_i \leq N\dot ALG $$ --- ## Proof of 2. * Put each $R_i$ to $[2^i,2^{i+1})$ bucket, $h(k), l(k)$ is the actions with highest and lowest $R_i$ in bucket $k$. * $R_{h(k)}/2 < R_{l(k)} \leq _{h(k)}$ * So we have $OPT \leq R_{h(K)} -c_{h(K)} \leq \sum (1-\alpha_{h(k-1),h(h)}) R_{h(K)}$ ---- Finally $$ OPT \leq \sum_{k\leq N} (1-\alpha_{l(k)}) R_{h(k)} $$ $$ \leq 2 \sum_{k\leq K} (1-\alpha_{l(k)}) R_{l(k)} $$ $$ \leq 2 K \max (1-\alpha_{l(k)}) R_{l(k)} \leq 2K \cdot ALG $$ --- ## Proof of 3. Similar to 2. --- ## Future Work: 1. Barganing ?? 2. Contract with two segement ??