In the first part of this thesis we show the limitations of algorithmic mechanism design. We introduce a novel class of problems which are approximable in the absence of strategic constraints, and have an optimal incentive compatible solution when no computational constraints are enforced; we show that, under standard computational assumptions, for this class of problems there is no algorithm with a reasonable approximation ratio that is both computationally feasible and incentive compatible. This settles the central open question in algorithmic mechanism design which, since its inception, has been focused on trying to show the hardness of polynomial time incentive compatibility.
In the second part of this thesis we show the possibilities of algorithmic mechanism design. We introduce a novel class of problems where the bottleneck for implementation is the constraint on payments. We show that for a broad class of these problems, there are incentive compatible mechanisms with desirable approximation guarantees that do not require overpayments. By resulting to approximations, this result circumvents well known impossibility results from classical mechanism design theory that deem incentive compatibility to be infeasible under a budget.