---
_id: '11667'
abstract:
- lang: eng
  text: The focus of classic mechanism design has been on truthful direct-revelation
    mechanisms. In the context of combinatorial auctions, the truthful direct-revelation
    mechanism that maximizes social welfare is the Vickrey-Clarke-Groves mechanism.
    For many valuation spaces, computing the allocation and payments of the VCG mechanism,
    however, is a computationally hard problem. We thus study the performance of the
    VCG mechanism when bidders are forced to choose bids from a subspace of the valuation
    space for which the VCG outcome can be computed efficiently. We prove improved
    upper bounds on the welfare loss for restrictions to additive bids and upper and
    lower bounds for restrictions to non-additive bids. These bounds show that increased
    expressiveness can give rise to additional equilibria of poorer efficiency.
article_number: '5'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Paul
  full_name: Dütting, Paul
  last_name: Dütting
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Martin
  full_name: Starnberger, Martin
  last_name: Starnberger
citation:
  ama: Dütting P, Henzinger MH, Starnberger M. Valuation compressions in VCG-based
    combinatorial auctions. <i>ACM Transactions on Economics and Computation</i>.
    2018;6(2). doi:<a href="https://doi.org/10.1145/3232860">10.1145/3232860</a>
  apa: Dütting, P., Henzinger, M. H., &#38; Starnberger, M. (2018). Valuation compressions
    in VCG-based combinatorial auctions. <i>ACM Transactions on Economics and Computation</i>.
    Association for Computing Machinery. <a href="https://doi.org/10.1145/3232860">https://doi.org/10.1145/3232860</a>
  chicago: Dütting, Paul, Monika H Henzinger, and Martin Starnberger. “Valuation Compressions
    in VCG-Based Combinatorial Auctions.” <i>ACM Transactions on Economics and Computation</i>.
    Association for Computing Machinery, 2018. <a href="https://doi.org/10.1145/3232860">https://doi.org/10.1145/3232860</a>.
  ieee: P. Dütting, M. H. Henzinger, and M. Starnberger, “Valuation compressions in
    VCG-based combinatorial auctions,” <i>ACM Transactions on Economics and Computation</i>,
    vol. 6, no. 2. Association for Computing Machinery, 2018.
  ista: Dütting P, Henzinger MH, Starnberger M. 2018. Valuation compressions in VCG-based
    combinatorial auctions. ACM Transactions on Economics and Computation. 6(2), 5.
  mla: Dütting, Paul, et al. “Valuation Compressions in VCG-Based Combinatorial Auctions.”
    <i>ACM Transactions on Economics and Computation</i>, vol. 6, no. 2, 5, Association
    for Computing Machinery, 2018, doi:<a href="https://doi.org/10.1145/3232860">10.1145/3232860</a>.
  short: P. Dütting, M.H. Henzinger, M. Starnberger, ACM Transactions on Economics
    and Computation 6 (2018).
date_created: 2022-07-27T11:46:46Z
date_published: 2018-05-01T00:00:00Z
date_updated: 2022-09-09T12:04:42Z
day: '01'
doi: 10.1145/3232860
extern: '1'
external_id:
  arxiv:
  - '1310.3153'
intvolume: '         6'
issue: '2'
keyword:
- Theory of computation
- Algorithmic game theory and mechanism design
- Applied computing
- Economics
- Simplified mechanisms
- Combinatorial auctions with item bidding
- Price of anarchy
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1310.3153
month: '05'
oa: 1
oa_version: Preprint
publication: ACM Transactions on Economics and Computation
publication_identifier:
  eissn:
  - 2167-8383
  issn:
  - 2167-8375
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Valuation compressions in VCG-based combinatorial auctions
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6
year: '2018'
...