Peter Stone's Selected Publications

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


Mechanism Design for Correlated Valuations: Efficient Methods for Revenue Maximization

Mechanism Design for Correlated Valuations: Efficient Methods for Revenue Maximization.
Michael Albert, Vincent Conitzer, Giuseppe Lopomo, and Peter Stone.
Operations Research, March 2021.

Download

[PDF]692.5kB  

Abstract

Traditionally, much of the focus of the mechanism/auction design community has been on revenue optimal mechanisms for settings where bidders' valuations are independent. However, in settings where valuations are correlated, much stronger results are possible. For example, the entire surplus of efficient allocations can be extracted as revenue. These stronger results are true, in theory, under generic conditions on parameter values. However, in practice, they are rarely, if ever, implementable because of the stringent requirement that the mechanism designer knows the distribution of the bidders types exactly. In this work, we provide a computationally efficient and sample efficient method for designing mechanisms that can robustly handle imprecise estimates of the distribution over bidder valuations. This method guarantees that the selected mechanism will perform at least as well as any ex post mechanism with high probability. The mechanism also performs nearly optimally with sufficient information and correlation. Furthermore, we show that when the distribution is not known and must be estimated from samples from the true distribution, a sufficiently high degree of correlation is essential to implement optimal mechanisms. Finally, we demonstrate through simulations that this new mechanism design paradigm generates mechanisms that perform significantly better than traditional mechanism design techniques given sufficient samples.

BibTeX Entry

@article{OR21-Albert,
author={Michael Albert and Vincent Conitzer and Giuseppe Lopomo and Peter Stone},
title={Mechanism Design for Correlated Valuations: Efficient Methods for Revenue Maximization},
journal={Operations Research}, 
doi={10.1287/opre.2020.2092},
month="March",
year="2021",
abstract={
          Traditionally, much of the focus of the mechanism/auction
          design community has been on revenue optimal mechanisms for
          settings where bidders' valuations are independent. However,
          in settings where valuations are correlated, much stronger
          results are possible. For example, the entire surplus of
          efficient allocations can be extracted as revenue. These
          stronger results are true, in theory, under generic
          conditions on parameter values. However, in practice, they
          are rarely, if ever, implementable because of the stringent
          requirement that the mechanism designer knows the
          distribution of the bidders types exactly. In this work, we
          provide a computationally efficient and sample efficient
          method for designing mechanisms that can robustly handle
          imprecise estimates of the distribution over bidder
          valuations. This method guarantees that the selected
          mechanism will perform at least as well as any ex post
          mechanism with high probability. The mechanism also performs
          nearly optimally with sufficient information and
          correlation. Furthermore, we show that when the distribution
          is not known and must be estimated from samples from the
          true distribution, a sufficiently high degree of correlation
          is essential to implement optimal mechanisms. Finally, we
          demonstrate through simulations that this new mechanism
          design paradigm generates mechanisms that perform
          significantly better than traditional mechanism design
          techniques given sufficient samples.
},
}

Generated by bib2html.pl (written by Patrick Riley ) on Wed Nov 17, 2021 22:18:57