Eo∼F|a∗(b)[t(cid:96)(b, o)] ∀b ∈ V (Claim 2).

(cid:96)∈[n]

contract t that satisﬁes LL, i.e., ka∗(b) ≤(cid:80)
ka∗(b) ≤ (cid:88)

It follows that if there exists an IIVCG contract that is both LL and IR for the given setting, then

(3)

m(cid:96)(b) ∀b ∈ V.

(cid:96)∈[n]

16

Surprisingly, the reverse direction is also true, i.e., if the predicate in Eq. (3) holds, one can construct

an IIVCG contract that is both LL and IR (Claim 3 and Algorithm 1). Section 4.2 shows that this

predicate can be computed in polynomial time.

4.1 Proof of Theorem 5

In this section we explain Algorithm 1 and prove Theorem 5 step by step. As a ﬁrst step, we

provide the following upper bound on principals’ payments.

Claim 1. Consider a common agency setting. Deﬁne:

m(cid:96)(b) = min
˜v(cid:96)∈V (cid:96)

Wela∗(b−(cid:96),˜v(cid:96))(b−(cid:96), ˜v(cid:96)) − Wela∗(b)(b−(cid:96), 0) ∀(cid:96) ∈ [n], b ∈ V.
Incomplete Information VCG Contracts for Common Agency