Peter Stone's Selected Publications

Classified by TopicClassified by Publication TypeSorted by DateSorted by First Author Last NameClassified by Funding Source


Robust Automated Mechanism Design

Michael Albert, Vincent Conitzer, and Peter Stone. Robust Automated Mechanism Design. In Proceedings of the EC 2016 2nd Algorithmic Game Theory and Data Science Workshop, July 2016.

Download

[PDF]374.2kB  

Abstract

We introduce a new class of mechanisms, robust mechanisms, that is an intermediary between ex-post mechanisms and Bayesian mechanisms. This new class of mechanisms allows the mechanism designer to incorporate imprecise estimates of the distribution over bidder valuations in a way that provides strong guarantees that the mechanism will perform at least as well as ex-post mechanisms, while in many cases performing better. We further extend this class to mechanisms that are with high probability incentive compatible and individually rational, $\epsilon$-robust mechanisms. Using techniques from automated mechanism design and robust optimization, we provide an algorithm polynomial in the number of bidder types to design robust and $\epsilon$-robust mechanisms. We show that while no mechanism in this class can guarantee better performance than an ex-post mechanism in all cases, experimentally this new class of mechanisms can significantly outperform traditional mechanism design techniques when the mechanism designer has an estimate of the distribution and the bidder's valuation is correlated with an externally verifiable signal.

BibTeX Entry

@InProceedings{EC16-Albert,
  author    = {Michael Albert and Vincent Conitzer and Peter Stone},
  title     = {Robust Automated Mechanism Design},
  booktitle = {Proceedings of the EC 2016 2nd Algorithmic Game Theory and Data Science Workshop},
  year      = {2016},
  month     = {July},
  location  = {Netherlands},
  abstract  = {We introduce a new class of mechanisms, robust mechanisms, that is an
    intermediary between ex-post mechanisms and Bayesian mechanisms. This new
      class of mechanisms allows the mechanism designer to incorporate imprecise
      estimates of the distribution over bidder valuations in a way that provides
      strong guarantees that the mechanism will perform at least as well as ex-post
      mechanisms, while in many cases performing better. We further extend this
      class to mechanisms that are with high probability incentive compatible and
      individually rational, $\epsilon$-robust mechanisms. Using techniques from
      automated mechanism design and robust optimization, we provide an algorithm
      polynomial in the number of bidder types to design robust and $\epsilon$-robust
      mechanisms. We show that while no mechanism in this class can guarantee better
      performance than an ex-post mechanism in all cases, experimentally this new
      class of mechanisms can significantly outperform traditional mechanism design
      techniques when the mechanism designer has an estimate of the distribution and
      the bidder's valuation is correlated with an externally verifiable signal.},
}

Generated by bib2html.pl (written by Patrick Riley ) on Wed Sep 06, 2017 22:17:33