Reducing Revenue to Welfare Maximization: Approximation Algorithms and Other Generalizations by Cai, Yang, Daskalakis, Konstantinos, Weinberg, Seth Matthew

“…In this paper, we extend the reduction to accommodate approximation algorithms, providing an approximation preserving reduction from (truthful) revenue maximization to (not necessarily truthful) welfare maximization. …”
Get full text
Get full text

Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms by Daskalakis, Konstantinos, Weinberg, Seth Matthew

“…Our mechanisms are obtained by establishing a polynomial-time approximation-sensitive reduction from the problem of designing approximately optimal mechanisms for some arbitrary objective O to that of designing bi-criterion approximation algorithms for the same objective O plus a linear allocation cost term. …”
Get full text
Get full text

Revenue Maximization and Ex-Post Budget Constraints by Daskalakis, Konstantinos, Devanur, Nikhil R., Weinberg, S. Matthew

“…Our main technical contribution is a computationally efficient 3-approximation algorithm for the algorithmic problem that results from an application of their framework to this problem. …”
Get full text

Sparse covers for sums of indicators by Papadimitriou, Christos, Daskalakis, Konstantinos

“…We discuss the implications of our construction for approximation algorithms and the computation of approximate Nash equilibria in anonymous games.…”
Get full text
Get full text