Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Reports, Documentation, and Standards
  4. An Expressive Mechanism for Auctions on the Web
 
report

An Expressive Mechanism for Auctions on the Web

Dütting, Paul  
•
Henzinger, Monika  
•
Weber, Ingmar
2011

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 Aggarwal et al. (WWW'09) 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 assumption, 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.

  • Files
  • Details
  • Metrics
Type
report
Author(s)
Dütting, Paul  
Henzinger, Monika  
Weber, Ingmar
Date Issued

2011

Total of pages

32

Subjects

VCG

•

GSP

•

General Auction Mechanism

•

Expressiveness

•

Envy Freeness

•

Bidder Optimality

•

Competitive Equilibrium

Written at

EPFL

EPFL units
LTAA  
Available on Infoscience
October 29, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/56405
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés