Applications of α-strongly regular distributions to bayesian auctions

Richard Cole, Shravas Rao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Two classes of distributions that are widely used in the analysis of Bayesian auctions are the Monotone Hazard Rate (MHR) and Regular distributions. They can both be characterized in terms of the rate of change of the associated virtual value functions: for MHR distributions the condition is that for values v < vʹ, ø (vʹ) − ø (v) ≥ vʹ − v, and for regular distributions, ø (vʹ) − ø(v) ≥ 0. Cole and Roughgarden introduced the interpolating class of α-Strongly Regular distributions (α-SR distributions for short), for which ø (vʹ) − ø (v) ≥ α(vʹ− v), for 0 ≤ α ≤ 1. In this paper, we investigate five distinct auction settings for which good expected revenue bounds are known when the bidders’ valuations are given by MHR distributions. In every case, we show that these bounds degrade gracefully when extended to α-SR distributions. For four of these settings, the auction mechanism requires knowledge of these distribution(s) (in the other setting, the distributions are needed only to ensure good bounds on the expected revenue). In these cases we also investigate what happens when the distributions are known only approximately via samples, specifically how to modify the mechanisms so that they remain effective and how the expected revenue depends on the number of samples.

Original languageEnglish (US)
Title of host publicationWeb and Internet Economics - 11th International Conference, WINE 2015, Proceedings
EditorsGuido Schäfer, Evangelos Markakis
PublisherSpringer Verlag
Pages244-257
Number of pages14
ISBN (Print)9783662489949
DOIs
StatePublished - 2015
Event11th International Conference on Web and Internet Economics, WINE 2015 - Amsterdam, Netherlands
Duration: Dec 9 2015Dec 12 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9470
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other11th International Conference on Web and Internet Economics, WINE 2015
CountryNetherlands
CityAmsterdam
Period12/9/1512/12/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Applications of α-strongly regular distributions to bayesian auctions'. Together they form a unique fingerprint.

Cite this