Assessing the Robustness of Cremer-McLean with Automated Mechanism Design

Authors

  • Michael Albert The Ohio State University
  • Vincent Conitzer Duke University
  • Giuseppe Lopomo Duke University

DOI:

https://doi.org/10.1609/aaai.v29i1.9293

Keywords:

Mechanism Design, Automated Mechanism Design, Simple Mechanisms, Incomplete Information, Optimal Mechanisms

Abstract

In a classic result in the mechanism design literature, Cremerand McLean (1985) show that if buyers’ valuations are sufficiently correlated, a mechanism exists that allows the seller to extract the full surplus from efficient allocation as revenue. This result is commonly seen as “too good to be true” (in practice), casting doubt on its modeling assumptions. In this paper, we use an automated mechanism design approach to assess how sensitive the Cremer-McLean result is to relaxing its main technical assumption. That assumption implies that each valuation that a bidder can have results in a unique conditional distribution over the external signal(s). We relax this, allowing multiple valuations to be consistent with the same distribution over the external signal(s). Using similar insights to Cremer-McLean, we provide a highly efficient algorithm for computing the optimal revenue in this more general case. Using this algorithm, we observe that indeed, as the number of valuations consistent with a distribution grows, the optimal revenue quickly drops to that of a reserve-price mechanism. Thus, automated mechanism design allows us to gain insight into the precise sense in which Cremer-McLean is “too good to be true.”

Downloads

Published

2015-02-16

How to Cite

Albert, M., Conitzer, V., & Lopomo, G. (2015). Assessing the Robustness of Cremer-McLean with Automated Mechanism Design. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9293

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms