---
_id: '11791'
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 VCG 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 the welfare
    loss increases in expressiveness. All our bounds apply to equilibrium concepts
    that can be computed in polynomial time as well as to learning outcomes.
alternative_title:
- LNCS
article_processing_charge: No
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. In: <i>9th International Conference on Web and Internet
    Economics</i>. Vol 8289. Springer Nature; 2013:146–159. doi:<a href="https://doi.org/10.1007/978-3-642-45046-4_13">10.1007/978-3-642-45046-4_13</a>'
  apa: 'Dütting, P., Henzinger, M. H., &#38; Starnberger, M. (2013). Valuation compressions
    in VCG-based combinatorial auctions. In <i>9th International Conference on Web
    and Internet Economics</i> (Vol. 8289, pp. 146–159). Cambridge, MA, USA: Springer
    Nature. <a href="https://doi.org/10.1007/978-3-642-45046-4_13">https://doi.org/10.1007/978-3-642-45046-4_13</a>'
  chicago: Dütting, Paul, Monika H Henzinger, and Martin Starnberger. “Valuation Compressions
    in VCG-Based Combinatorial Auctions.” In <i>9th International Conference on Web
    and Internet Economics</i>, 8289:146–159. Springer Nature, 2013. <a href="https://doi.org/10.1007/978-3-642-45046-4_13">https://doi.org/10.1007/978-3-642-45046-4_13</a>.
  ieee: P. Dütting, M. H. Henzinger, and M. Starnberger, “Valuation compressions in
    VCG-based combinatorial auctions,” in <i>9th International Conference on Web and
    Internet Economics</i>, Cambridge, MA, USA, 2013, vol. 8289, pp. 146–159.
  ista: 'Dütting P, Henzinger MH, Starnberger M. 2013. Valuation compressions in VCG-based
    combinatorial auctions. 9th International Conference on Web and Internet Economics.
    WINE: International Conference on Web and Internet Economics, LNCS, vol. 8289,
    146–159.'
  mla: Dütting, Paul, et al. “Valuation Compressions in VCG-Based Combinatorial Auctions.”
    <i>9th International Conference on Web and Internet Economics</i>, vol. 8289,
    Springer Nature, 2013, pp. 146–159, doi:<a href="https://doi.org/10.1007/978-3-642-45046-4_13">10.1007/978-3-642-45046-4_13</a>.
  short: P. Dütting, M.H. Henzinger, M. Starnberger, in:, 9th International Conference
    on Web and Internet Economics, Springer Nature, 2013, pp. 146–159.
conference:
  end_date: 2013-12-14
  location: Cambridge, MA, USA
  name: 'WINE: International Conference on Web and Internet Economics'
  start_date: 2013-12-01
date_created: 2022-08-11T11:05:14Z
date_published: 2013-12-01T00:00:00Z
date_updated: 2023-02-13T11:20:42Z
day: '01'
doi: 10.1007/978-3-642-45046-4_13
extern: '1'
external_id:
  arxiv:
  - '1310.3153'
intvolume: '      8289'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1310.3153
month: '12'
oa: 1
oa_version: Preprint
page: 146–159
publication: 9th International Conference on Web and Internet Economics
publication_identifier:
  isbn:
  - '9783642450457'
  issn:
  - 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Valuation compressions in VCG-based combinatorial auctions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8289
year: '2013'
...