---
_id: '11864'
abstract:
- lang: eng
  text: Auctions are widely used on the Web. Applications range from internet advertising
    to platforms such as eBay. In most of these 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 [1] is
    taking a first step towards 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 piece-wise linear utility functions with non-identical slopes and multiple
    discontinuities. Our mechanism runs in polynomial time. Like GAM it is incentive
    compatible for inputs that fulfill a certain non-degeneracy requirement, but our
    requirement is more general than the requirement of GAM. For discontinuous utility
    functions that are non-degenerate 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 piece-wise linear approximation.
    Finally, we prove hardness results for even more expressive settings.
article_processing_charge: No
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. In: <i>Proceedings of the 20th International Conference on World Wide
    Web</i>. Association for Computing Machinery; 2011:127-136. doi:<a href="https://doi.org/10.1145/1963405.1963427">10.1145/1963405.1963427</a>'
  apa: 'Dütting, P., Henzinger, M. H., &#38; Weber, I. (2011). An expressive mechanism
    for auctions on the web. In <i>Proceedings of the 20th international conference
    on World wide web</i> (pp. 127–136). Hyderabad, India: Association for Computing
    Machinery. <a href="https://doi.org/10.1145/1963405.1963427">https://doi.org/10.1145/1963405.1963427</a>'
  chicago: Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “An Expressive Mechanism
    for Auctions on the Web.” In <i>Proceedings of the 20th International Conference
    on World Wide Web</i>, 127–36. Association for Computing Machinery, 2011. <a href="https://doi.org/10.1145/1963405.1963427">https://doi.org/10.1145/1963405.1963427</a>.
  ieee: P. Dütting, M. H. Henzinger, and I. Weber, “An expressive mechanism for auctions
    on the web,” in <i>Proceedings of the 20th international conference on World wide
    web</i>, Hyderabad, India, 2011, pp. 127–136.
  ista: 'Dütting P, Henzinger MH, Weber I. 2011. An expressive mechanism for auctions
    on the web. Proceedings of the 20th international conference on World wide web.
    WWW: International Conference on World Wide Web, 127–136.'
  mla: Dütting, Paul, et al. “An Expressive Mechanism for Auctions on the Web.” <i>Proceedings
    of the 20th International Conference on World Wide Web</i>, Association for Computing
    Machinery, 2011, pp. 127–36, doi:<a href="https://doi.org/10.1145/1963405.1963427">10.1145/1963405.1963427</a>.
  short: P. Dütting, M.H. Henzinger, I. Weber, in:, Proceedings of the 20th International
    Conference on World Wide Web, Association for Computing Machinery, 2011, pp. 127–136.
conference:
  end_date: 2011-04-01
  location: Hyderabad, India
  name: 'WWW: International Conference on World Wide Web'
  start_date: 2011-03-28
date_created: 2022-08-16T09:05:34Z
date_published: 2011-04-01T00:00:00Z
date_updated: 2023-02-17T10:21:18Z
day: '01'
doi: 10.1145/1963405.1963427
extern: '1'
language:
- iso: eng
month: '04'
oa_version: None
page: 127 - 136
publication: Proceedings of the 20th international conference on World wide web
publication_identifier:
  isbn:
  - 978-145030632-4
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...