---
_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 MH, 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. H., &#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 H 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. H. 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 MH, 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.H. 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: 2023-02-09T10:08:41Z
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'
...