The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOCS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of error, while blowing up the communication by only a constant factor. Since these seminal works, there have been many follow-up works which improve the error rate, the communication rate, and the computational efficiency.
Computer Science and Discrete Mathematics (CSDM)
We provide a duality framework for Bayesian Mechanism Design. Specifically, we show that the dual problem to revenue maximization is a search over virtual transformations. This approach yields a unified view of several recent breakthroughs in algorithmic mechanism design, and enables some new breakthroughs as well. In this talk, I'll:
1) Provide a brief overview of the challenges of multi-dimensional mechanism design.
2) Construct a duality framework to resolve these problems.