Revenue Optimization for Correlated Bidders via Sampling
- Dr. Hu Fu, University of British Columbia
- Time: 2020-01-14 15:00
- Host: Prof. Xiaotie Deng
- Venue: Room 102, Courtyard No.5, Jingyuan
Correlation among buyers' valuations enables a revenue maximizing seller to fully extract the social surplus, with no money left to the buyers. This was shown in a classic work by Crémer and McLean. The model has been criticized for allowing arbitrary dependence of the mechanism on the prior: any uncertainty on the prior disrupts the mechanism. We examine this criticism from a learning point of view. We allow uncertainty on the prior but grant the seller sample access from the true prior, and study the number of samples that suffice for surplus extraction. We give precise bounds on the number of samples needed, which show that surplus extraction needs much less information than learning the prior itself. In a sense, this is because the buyers "collaborate" in the learning, driven by their incentives. Our upper bound on the number of samples is by an algebraic argument.
This is joint work with Bobby Kleinberg, Nima Haghpanah and Jason Hartline.
Hu Fu is Assistant Professor at Department of Computer Science, University of British Columbia in Vancouver. He works on computational problems arising from economic contexts, including auction theory, pricing and market design. Prior to joining UBC, he obtained his PhD from Cornell University, advised by Bobby Kleinberg. He also worked as postdoc at Microsoft Research New England Lab and at Caltech.