Test of Time 2012 Awards

Niv Buchbinder, Moran Feldman, Joseph Naor, Roy Schwartz:
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

This paper gives a ½-approximation algorithm for the fundamental problem of maximizing a submodular set function. The approximation factor of ½ matches the lower bound established by Feige, Mirrokni, and Vondrák for any algorithm that makes a subexponential number of calls to a value oracle. The algorithm runs in linear time and the algorithm and analysis are simple, elegant and innovative. The generality and importance of the problem, and the optimality and ingenious simplicity of the algorithm makes this a classic result in the theory of algorithms.

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg:
Optimal Multi-dimensional Mechanism Design: Reducing Revenue to Welfare Maximization

This paper presents a general reduction that converts a large class of revenue maximization problems in multidimensional mechanism design to a class of welfare maximization problems in the general framework of the Vickrey-Clarke-Groves (VCG) mechanism in the Bayesian setting. The VCG mechanism is incentive compatible, so the transformation takes care of all the incentive and pricing issues hence freeing the designer from handling these issues allowing him to focus on the algorithmic problem of solving the resulting optimization problem. The methods introduced in this paper provide a crucial bridge between two areas of economic mechanism design, and play an important role in the modern treatment of algorithmic methods in mechanism design.