Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Seminar Today ay 415

Shashwat Silas silas at stanford.edu
Thu Oct 5 10:52:41 PDT 2017


Hi all,

Just a reminder that there will be theory seminar at 4:15pm today at Gates 463A. The talk will be given by Rad Niazadeh and we will have tea and cake. Hope you'll make it!

Bernoulli Factories and Blackbox Reductions in Mechanism Design
In this talk, I am going to talk about a recent polynomial-time reduction from Bayesian incentive-compatible mechanism design to Bayesian algorithm design for welfare maximization problems. Unlike prior results, our reduction achieves exact incentive compatibility for problems with multi-dimensional and continuous type spaces. The key technical barrier preventing exact incentive compatibility in prior black-box reductions is that repairing violations of incentive constraints requires understanding the distribution of the mechanism’s output, which is typically #P-hard to compute. Reductions that instead estimate the output distribution by sampling inevitably suffer from sampling error, which typically precludes exact incentive compatibility. We overcome this barrier by employing and generalizing the computational model in the literature on Bernoulli Factories. In a Bernoulli factory problem, one is given a function mapping the bias of an “input coin” to that of an “output coin”, and the challenge is to efficiently simulate the output coin given only sample access to the input coin. I will show how to incorporate Bernoulli factories to design a polynomial time algorithm for the following selection problem: a ground set of elements and sampling oracles for each element are given (for unknown input distributions), expected values of the input distributions correspond to the weights of the elements in the set, and we wish to select an element with probability proportional to an exponential function of its weight by efficient sampling. I then show how this algorithm solves a simple single agent truthful mechanism design problem. This truthful mechanism is the key ingredient that can be used to make the approximately incentive compatible reduction of Hartline et al. (2015) exactly incentive compatible.

Thanks,
Shashwat

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20171005/6750be13/attachment.html>


More information about the theory-seminar mailing list