Preliminaries
: the set {0âŠk - 1} : set of all probability distributions over
agent chooses from actions, and there are possible outcomes
- each action associated w/ distribution of outcomes as well as cost
- is privately known only to the agent
- also assume =
reward for each outcome is known to both agent and principal (person giving the contract)
- also assume
Contract Classes
a contract is linear if (that is, agent is rewarded with constant fraction of reward produced)
Lemma
Expected reward only changes at most times as increases from to . Moreover, expected reward is non-decreasing.
Recall that utility = expected reward - expected payment.
For instance, if for any agent, the best linear contract were only 0.25 worse than the best bounded contract, would be a 0.25 approximation of .
visualization of this condition (solid is sampled distribution, solid is true distribution). x-axis is -axis, and for all there is at most error.
visual proof:
if we pick our strategy at the red dot, we can incur at worst error from the true answer.