Note on the Applicability of the VCG Mechanism to Capacitated Assignment Problems and Extensions

Reinder B. Lok, Dolores Romero Morales, Dries Vermeulen

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstrakt

For the allocation of heterogeneous items, it is known that the buyers-are-substitutes condition is necessary and sufficient to ensure that a pricing equilibrium can yield the same allocation and payments as the VCG mechanism. Furthermore, concavity of the corresponding transferable utility TU-game guarantees that this VCG outcome can also be achieved by an ascending price auction. We show that concavity, and hence the buyers-are-substitutes condition, holds for the TU-game of the assignment problem with general capacities. Therefore, the VCG mechanism is supported by a pricing equilibrium which can also be achieved by an ascending auction. We also show that the buyers-are-substitutes condition, and hence concavity, does not hold anymore for very natural and straightforward extensions of this problem. This shows that the necessity of the substitutes property is a considerable restriction on the applicability of the VCG mechanism.
OriginalsprogEngelsk
TidsskriftStatistica Neerlandica
Vol/bind61
Udgave nummer1
Sider (fra-til)156–171
ISSN0039-0402
DOI
StatusUdgivet - 2007
Udgivet eksterntJa

Emneord

  • Equilibria
  • VCG outcome
  • Buyers-are-substitutes condition
  • Concavity

Citationsformater