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

Reinder B. Lok, Dolores Romero Morales, Dries Vermeulen

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

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.
Original languageEnglish
JournalStatistica Neerlandica
Volume61
Issue number1
Pages (from-to)156–171
ISSN0039-0402
DOIs
Publication statusPublished - 2007
Externally publishedYes

Cite this

@article{8a30085aebd544eb9d86f586fb192a65,
title = "Note on the Applicability of the VCG Mechanism to Capacitated Assignment Problems and Extensions",
abstract = "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.",
keywords = "Equilibria, VCG outcome, Buyers-are-substitutes condition, Concavity",
author = "Lok, {Reinder B.} and {Romero Morales}, Dolores and Dries Vermeulen",
year = "2007",
doi = "10.1111/j.1467-9574.2007.00356.x",
language = "English",
volume = "61",
pages = "156–171",
journal = "Statistica Neerlandica",
issn = "0039-0402",
publisher = "Blackwell Publishing",
number = "1",

}

Note on the Applicability of the VCG Mechanism to Capacitated Assignment Problems and Extensions. / Lok, Reinder B.; Romero Morales, Dolores ; Vermeulen, Dries.

In: Statistica Neerlandica, Vol. 61, No. 1, 2007, p. 156–171.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

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

AU - Lok, Reinder B.

AU - Romero Morales, Dolores

AU - Vermeulen, Dries

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

KW - Equilibria

KW - VCG outcome

KW - Buyers-are-substitutes condition

KW - Concavity

U2 - 10.1111/j.1467-9574.2007.00356.x

DO - 10.1111/j.1467-9574.2007.00356.x

M3 - Journal article

VL - 61

SP - 156

EP - 171

JO - Statistica Neerlandica

JF - Statistica Neerlandica

SN - 0039-0402

IS - 1

ER -