Theory Seminar: On the Complexity of Revenue Maximizing Bayesian Auctions

Friday, April 1, 2016 - 2:00pm
CS 4310

Speaker Name: 

Dimitris Paparas

Speaker Institution: 

Columbia University



Cookies Location: 

CS 4310


We consider the problem of designing Revenue Maximizing Bayesian Auctions for a Unit-demand buyer in both the Deterministic and the Randomized setting.

For the Deterministic setting, we obtain a polynomial time algorithm for the case that the valuations of the buyer are drawn from a discrete product distribution of support size 2. On the negative side, we prove that the problem is NP-complete in the general case. For the Randomized setting, we study the menu-size complexity of the problem, presenting cases were a small menu suffices as well as cases that require an exponentially large menu. Regarding the computational complexity of the problem, we prove that the problem is #P-hard.

Based on joint work with Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Xiaorui Sun, and Mihalis Yannakakis.

Brief Bio: Dimitris Paparas is a final year PhD student at Columbia University. His research interests broadly revolve around Algorithms, Optimization, and Computational Economics with emphasis on Mechanism Design and Equilibrium Computation. Prior to Columbia University he obtained a MSc in Theoretical Computer Science and a BSc in Computer Science and Telecommunications, both from the University of Athens, Greece.