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.
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.
LanguageEnglish
JournalStatistica Neerlandica
Volume61
Issue number1
Pages156–171
ISSN0039-0402
DOIs
StatePublished - 2007
Externally publishedYes

Keywords

    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 Morales, {Dolores Romero} 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.; Morales, Dolores Romero; 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 - Morales,Dolores Romero

    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

    T2 - Statistica Neerlandica

    JF - Statistica Neerlandica

    SN - 0039-0402

    IS - 1

    ER -