---
_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: '11668'
abstract:
- lang: eng
  text: "We study multiple keyword sponsored search auctions with budgets. Each keyword
    has multiple ad slots with a click-through rate. The bidders have additive valuations,
    which are linear in the click-through rates, and budgets, which are restricting
    their overall payments. Additionally, the number of slots per keyword assigned
    to a bidder is bounded.\r\n\r\nWe show the following results: (1) We give the
    first mechanism for multiple keywords, where click-through rates differ among
    slots. Our mechanism is incentive compatible in expectation, individually rational
    in expectation, and Pareto optimal. (2) We study the combinatorial setting, where
    each bidder is only interested in a subset of the keywords. We give an incentive
    compatible, individually rational, Pareto-optimal, and deterministic mechanism
    for identical click-through rates. (3) We give an impossibility result for incentive
    compatible, individually rational, Pareto-optimal, and deterministic mechanisms
    for bidders with diminishing marginal valuations."
article_number: '2'
article_processing_charge: No
article_type: original
author:
- first_name: Riccardo
  full_name: Colini-Baldeschi, Riccardo
  last_name: Colini-Baldeschi
- first_name: Stefano
  full_name: Leonardi, Stefano
  last_name: Leonardi
- 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: Colini-Baldeschi R, Leonardi S, Henzinger M, Starnberger M. On multiple keyword
    sponsored search auctions with budgets. <i>ACM Transactions on Economics and Computation</i>.
    2015;4(1). doi:<a href="https://doi.org/10.1145/2818357">10.1145/2818357</a>
  apa: Colini-Baldeschi, R., Leonardi, S., Henzinger, M., &#38; Starnberger, M. (2015).
    On multiple keyword sponsored search auctions with budgets. <i>ACM Transactions
    on Economics and Computation</i>. Association for Computing Machinery. <a href="https://doi.org/10.1145/2818357">https://doi.org/10.1145/2818357</a>
  chicago: Colini-Baldeschi, Riccardo, Stefano Leonardi, Monika Henzinger, and Martin
    Starnberger. “On Multiple Keyword Sponsored Search Auctions with Budgets.” <i>ACM
    Transactions on Economics and Computation</i>. Association for Computing Machinery,
    2015. <a href="https://doi.org/10.1145/2818357">https://doi.org/10.1145/2818357</a>.
  ieee: R. Colini-Baldeschi, S. Leonardi, M. Henzinger, and M. Starnberger, “On multiple
    keyword sponsored search auctions with budgets,” <i>ACM Transactions on Economics
    and Computation</i>, vol. 4, no. 1. Association for Computing Machinery, 2015.
  ista: Colini-Baldeschi R, Leonardi S, Henzinger M, Starnberger M. 2015. On multiple
    keyword sponsored search auctions with budgets. ACM Transactions on Economics
    and Computation. 4(1), 2.
  mla: Colini-Baldeschi, Riccardo, et al. “On Multiple Keyword Sponsored Search Auctions
    with Budgets.” <i>ACM Transactions on Economics and Computation</i>, vol. 4, no.
    1, 2, Association for Computing Machinery, 2015, doi:<a href="https://doi.org/10.1145/2818357">10.1145/2818357</a>.
  short: R. Colini-Baldeschi, S. Leonardi, M. Henzinger, M. Starnberger, ACM Transactions
    on Economics and Computation 4 (2015).
date_created: 2022-07-27T11:54:56Z
date_published: 2015-12-05T00:00:00Z
date_updated: 2024-11-06T12:06:41Z
day: '05'
doi: 10.1145/2818357
extern: '1'
intvolume: '         4'
issue: '1'
keyword:
- Algorithms
- Economics
- Clinching ascending auction
- auctions with budgets
- Sponsored search auctions
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://eprints.cs.univie.ac.at/3510/
month: '12'
oa: 1
oa_version: Submitted Version
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: On multiple keyword sponsored search auctions with budgets
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2015'
...
---
_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'
...
---
_id: '11670'
abstract:
- lang: eng
  text: Auctions are widely used on the Web. Applications range from sponsored search
    to platforms such as eBay. In these and in many other applications the auctions
    in use are single-/multi-item auctions with unit demand. The main drawback of
    standard mechanisms for this type of auctions, such as VCG and GSP, is the limited
    expressiveness that they offer to the bidders. The General Auction Mechanism (GAM)
    of Aggarwal et al. [2009] takes a first step toward addressing the problem of
    limited expressiveness by computing a bidder optimal, envy-free outcome for linear
    utility functions with identical slopes and a single discontinuity per bidder-item
    pair. We show that in many practical situations this does not suffice to adequately
    model the preferences of the bidders, and we overcome this problem by presenting
    the first mechanism for piecewise linear utility functions with nonidentical slopes
    and multiple discontinuities. Our mechanism runs in polynomial time. Like GAM
    it is incentive compatible for inputs that fulfill a certain nondegeneracy assumption,
    but our requirement is more general than the requirement of GAM. For discontinuous
    utility functions that are nondegenerate as well as for continuous utility functions
    the outcome of our mechanism is a competitive equilibrium. We also show how our
    mechanism can be used to compute approximately bidder optimal, envy-free outcomes
    for a general class of continuous utility functions via piecewise linear approximation.
    Finally, we prove hardness results for even more expressive settings.
acknowledgement: We would like to thank Veronika Loitzenbauer and the anonymous referees
  for their valuable feedback.
article_number: '1'
article_processing_charge: No
article_type: original
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: Ingmar
  full_name: Weber, Ingmar
  last_name: Weber
citation:
  ama: Dütting P, Henzinger M, Weber I. An expressive mechanism for auctions on the
    web. <i>ACM Transactions on Economics and Computation</i>. 2015;4(1). doi:<a href="https://doi.org/10.1145/2716312">10.1145/2716312</a>
  apa: Dütting, P., Henzinger, M., &#38; Weber, I. (2015). An expressive mechanism
    for auctions on the web. <i>ACM Transactions on Economics and Computation</i>.
    Association for Computing Machinery. <a href="https://doi.org/10.1145/2716312">https://doi.org/10.1145/2716312</a>
  chicago: Dütting, Paul, Monika Henzinger, and Ingmar Weber. “An Expressive Mechanism
    for Auctions on the Web.” <i>ACM Transactions on Economics and Computation</i>.
    Association for Computing Machinery, 2015. <a href="https://doi.org/10.1145/2716312">https://doi.org/10.1145/2716312</a>.
  ieee: P. Dütting, M. Henzinger, and I. Weber, “An expressive mechanism for auctions
    on the web,” <i>ACM Transactions on Economics and Computation</i>, vol. 4, no.
    1. Association for Computing Machinery, 2015.
  ista: Dütting P, Henzinger M, Weber I. 2015. An expressive mechanism for auctions
    on the web. ACM Transactions on Economics and Computation. 4(1), 1.
  mla: Dütting, Paul, et al. “An Expressive Mechanism for Auctions on the Web.” <i>ACM
    Transactions on Economics and Computation</i>, vol. 4, no. 1, 1, Association for
    Computing Machinery, 2015, doi:<a href="https://doi.org/10.1145/2716312">10.1145/2716312</a>.
  short: P. Dütting, M. Henzinger, I. Weber, ACM Transactions on Economics and Computation
    4 (2015).
date_created: 2022-07-27T12:43:18Z
date_published: 2015-12-02T00:00:00Z
date_updated: 2024-11-06T12:07:05Z
day: '02'
doi: 10.1145/2716312
extern: '1'
intvolume: '         4'
issue: '1'
keyword:
- Computational Mathematics
- Marketing
- Economics and Econometrics
- Statistics and Probability
- Computer Science (miscellaneous)
language:
- iso: eng
month: '12'
oa_version: None
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: An expressive mechanism for auctions on the web
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2015'
...