if ka ≤(cid:80)

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

(cid:80)

whether a “good” IIVCG contract exists.

15To set b ∈ Va as a linear constraint we use the constraints of La (as in Algorithm 1) with weak and strict
inequalities according to the tie-breaking in a∗(·). A standard technique for strict inequalities in a linear program is
adding a small constant that depends on the bit precision, see e.g., [11].

20

ALGORITHM 2: Determines if there exists an IIVCG contract that satisﬁes LL and IR for a given
setting.
Input: Setting (A,O,V, F, ψ)

1 for a ∈ A do

2

3

Solve LP4 to ﬁnd arg minb∈Va
if Algorithm 1 on b and arbitrary o returns Impossible then

(cid:96)∈[n] m(cid:96)(b);

(cid:80)

return Impossible;

4
5 return Possible;
Incomplete Information VCG Contracts for Common Agency