properties whenever such a contract exists. There is a conceptual diﬀerence between this contract

design and Auction-Inspired IIVCG (presented in Section 3.4) or Weighted IIVCG (presented in
Section 5). In the latter classes, the contract mapping t : V × O → Rn is expressed using a short
mathematical formula. We introduce Algorithmic IIVCG contracts, in which t is algorithm-based:
Deﬁnition 4 (Contract ALG1). For a given common agency setting, ALG1 : V × O → Rn is the
contract that for every bid proﬁle b ∈ V and outcome o ∈ O, maps (b, o) to Algorithm 1’s output
on b and o for this setting.

The following two theorems constitute our main results:

Theorem 5. For every common agency setting for which an IIVCG contract that satisﬁes LL
and IR exists, contract ALG1 is such a contract. Furthermore, for every bid proﬁle b ∈ V and
outcome o ∈ O, Algorithm 1 computes the payment proﬁle ALG1(b, o) in polynomial time.
Incomplete Information VCG Contracts for Common Agency