Assessing the robustness of Cremer-McLean with automated mechanism design
Copyright © 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. In a classic result in the mechanism design literature, Cremer and 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.".
Albert, M; Conitzer, V; Lopomo, G
Proceedings of the National Conference on Artificial Intelligence
Volume / Issue
Start / End Page
International Standard Book Number 13 (ISBN-13)