Approximately Optimal Mechanisms With Correlated Buyer Valuations

Conitzer, Vincent

Albert, Michael Joseph

2013-05-13T15:37:36Z

2013-05-13T15:37:36Z

2013

Computer Science

Cremer and McLean 1985 shows that if buyers valuations are suciently correlated, there is a mechanism that allows the seller to extract the full surplus from the buyers. However, in practice, we do not see the Cremer-McLean mechanism employed. In this thesis, I demonstrate that one reason that the Cremer-McLean mechanism

is not implemented in practice is because the mechanism requires very precise assumptions about the underlying distributions of the buyers. I demonstrate that a small mis-estimation of the underlying distribution can have large and signicant effects on the outcome of the mechanism. I further prove that the Cremer-McLean mechanism cannot be approximated by a simple second price auction, i.e. there is no approximating factor when using a second price auction with reserve in either outcome or expectation for the Cremer-McLean mechanism. Further, I show that there is no mechanism that approximates the Cremer-McLean mechanism for bidders with

regular distributions in a single item auction if the correlation among buyers is not considered. Finally, I introduce a new mechanism that is robust to distribution mis-estimation and show empirically that it outperforms the Cremer-McLean mechanism on average in cases of distribution mis-estimation and I show that the mechanism can

be determined in polynomial time in the number of types of the buyers.

https://hdl.handle.net/10161/7298

Computer science

Economic theory

Approximate mechanism

Mechanism design

Approximately Optimal Mechanisms With Correlated Buyer Valuations

Master's thesis