predicate, it suﬃces to test only O(q) bid proﬁles as follows (where q is the number of actions).

(cid:96)∈[n] m(cid:96)(b) ∀b ∈ V if and

(cid:96)∈[n] m(cid:96)(b)} ∀a.

19

ALGORITHM 1: Returns the payments of an IIVCG contract that satisﬁes IR and LL for the setting,
or Impossible if no such contract exists.
Input: Bid proﬁle b ∈ V, outcome o ∈ O and an access to the setting (A,O,V, F, ψ).

1 for (cid:96) ∈ [n] do

2

3

5 if ka∗(b) >(cid:80)

Solve LP1 to ﬁnd h(cid:96);
m(cid:96) ← h(cid:96) − {F|a∗(b) · b−(cid:96) − ψ(a∗(b))};

4 Solve LP2 to ﬁnd ka∗(b) and wb;

(cid:96)∈[n] m(cid:96) then return Impossible;

6 Solve LP3 to ﬁnd x.
7 for (cid:96) ∈ [n] do
9 return {t(cid:96)(b, o)}(cid:96)∈[n];

8

t(cid:96)(b, o) ← h(cid:96) − {F|a∗(b) · (b−(cid:96) + xb

(cid:96) · wb) − ψ(a∗(b))} + xb

(cid:96) · wb(o);

Observation 4 follows directly from the deﬁnition of Va, and will be used in the proof of Theorem 6.
Incomplete Information VCG Contracts for Common Agency