---
_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 M, 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., &#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 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. 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 M, 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. 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: 2024-11-06T12:06:28Z
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'
...
---
_id: '11669'
abstract:
- lang: eng
  text: We study individual rational, Pareto-optimal, and incentive compatible mechanisms
    for auctions with heterogeneous items and budget limits. We consider settings
    with multiunit demand and additive valuations. For single-dimensional valuations
    we prove a positive result for randomized mechanisms, and a negative result for
    deterministic mechanisms. While the positive result allows for private budgets,
    the negative result is for public budgets. For multidimensional valuations and
    public budgets we prove an impossibility result that applies to deterministic
    and randomized mechanisms. Taken together this shows the power of randomization
    in certain settings with heterogeneous items, but it also shows its limitations.
article_number: '4'
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 M, Starnberger M. Auctions for heterogeneous items and
    budget limits. <i>ACM Transactions on Economics and Computation</i>. 2015;4(1).
    doi:<a href="https://doi.org/10.1145/2818351">10.1145/2818351</a>
  apa: Dütting, P., Henzinger, M., &#38; Starnberger, M. (2015). Auctions for heterogeneous
    items and budget limits. <i>ACM Transactions on Economics and Computation</i>.
    Association for Computing Machinery. <a href="https://doi.org/10.1145/2818351">https://doi.org/10.1145/2818351</a>
  chicago: Dütting, Paul, Monika Henzinger, and Martin Starnberger. “Auctions for
    Heterogeneous Items and Budget Limits.” <i>ACM Transactions on Economics and Computation</i>.
    Association for Computing Machinery, 2015. <a href="https://doi.org/10.1145/2818351">https://doi.org/10.1145/2818351</a>.
  ieee: P. Dütting, M. Henzinger, and M. Starnberger, “Auctions for heterogeneous
    items and budget limits,” <i>ACM Transactions on Economics and Computation</i>,
    vol. 4, no. 1. Association for Computing Machinery, 2015.
  ista: Dütting P, Henzinger M, Starnberger M. 2015. Auctions for heterogeneous items
    and budget limits. ACM Transactions on Economics and Computation. 4(1), 4.
  mla: Dütting, Paul, et al. “Auctions for Heterogeneous Items and Budget Limits.”
    <i>ACM Transactions on Economics and Computation</i>, vol. 4, no. 1, 4, Association
    for Computing Machinery, 2015, doi:<a href="https://doi.org/10.1145/2818351">10.1145/2818351</a>.
  short: P. Dütting, M. Henzinger, M. Starnberger, ACM Transactions on Economics and
    Computation 4 (2015).
date_created: 2022-07-27T12:09:15Z
date_published: 2015-12-05T00:00:00Z
date_updated: 2024-11-06T12:06:53Z
day: '05'
doi: 10.1145/2818351
extern: '1'
external_id:
  arxiv:
  - '1209.6448'
intvolume: '         4'
issue: '1'
keyword:
- Algorithmic game theory
- auction theory
- Clinching auction
- Pareto optimality
- Budget limits
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1209.6448
month: '12'
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: Auctions for heterogeneous items and budget limits
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2015'
...