The proof relies on the following examples.

Example 1 (Price of anarchy). There are three actions a1, a2, a3 and three outcomes o1, o2, o3.
Action ai deterministically yields outcome oi. The costs are: ψ(a1) = 0, ψ(a2) = (cid:15), ψ(a3) = γ,
where 0 < (cid:15) < γ < 1. There are n > 3 principals with the following valuation domains: V 1 =
{(0, 0, v) | v ≥ 0}, V 2 = {(0, v, 0) | v ≥ 0}, and V (cid:96) = {(v, 0, 0) | v ≥ 0} ∀(cid:96) > 2. The valuations are:
v1 = (0, 0, 1 + γ), v2 = (0, 1 + (cid:15), 0), and v(cid:96) = (1, 0, 0) ∀(cid:96) > 2.
Incomplete Information VCG Contracts for Common Agency