Mechanism Design for Correlated Valuations: Efficient Methods for Revenue Maximization

Michael Albert (), Vincent Conitzer (), Giuseppe Lopomo () and Peter Stone ()
Additional contact information
Michael Albert: Darden School of Business, University of Virginia, Charlottesville, Virginia 22903
Vincent Conitzer: Department of Computer Science, Duke University, Durham, North Carolina 27708
Giuseppe Lopomo: Fuqua School of Business, Duke University, Durham, North Carolina 27708
Peter Stone: Department of Computer Science, University of Texas at Austin, Austin, Texas 78712

Operations Research, 2022, vol. 70, issue 1, 562-584

Abstract: Traditionally, the mechanism design literature has been primarily focused on settings where the 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.

Keywords: Machine Learning and Data Science; mechanism design; robust optimization; revenue maximization; correlated valuations (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.2092 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:1:p:562-584

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().