that satisﬁes LL and IR for every setting where such a contract exists. Truthfulness and social

eﬃciency follow from the deﬁnition of IIVCG. By Lemma 3, Algorithm 1 computes the payments

of ALG1 in polynomial time.

Remark 7. One may consider relaxing the LL constraint, by requiring that only the aggregate

payment from all principals to the agent is non-negative. The proof of Claim 2 shows that requiring

the payments from each individual principal to the agent to be non-negative is without loss of

generality.

4.2 Proof of Theorem 6

In this section we prove Theorem 6, providing a method for determining when there exists an IIVCG

contract that is both LL and IR. According to the characterization in Lemma 2, there exists such
(cid:96)∈[n] m(cid:96)(b) ∀b ∈ V. A key observation is that in order to test this

a contract if and only if ka∗(b) ≤(cid:80)
Observation 4. Deﬁne Va = {v ∈ V | a = a∗(v)} ∀a. Then ka∗(b) ≤(cid:80)
only if ka ≤ minb∈Va{(cid:80)
Incomplete Information VCG Contracts for Common Agency