The Complexity of Mechanism Design Approximation

Abstract

In the field of theoretical computer science we often reason about algorithm design, the process of constructing solutions for problems based upon fixed input. In real-world situations, however, the structure of an algorithm often impacts the way that agents interact with it. Mechanism design describes the problem of constructing algorithms that consider strategic input. Many important problems in fields from auction theory to policy development necessitate mechanisms that guarantee good behavior. Thus, understanding how to solve these problems, and how hard it is to solve them, is a crucial area of research. In this paper, we strengthen and extend results found in Matthew Weinberg’s Algorithms for Strategic Agents. Weinberg provides a framework for transforming mechanism design problems into algorithmic form. His work centers upon a reduction from a mechanism design approximation problem (BMeD) to an algorithmic problem (GOOP). Furthermore, he provides a hardness of approximation result for some valuation classes. However, this reduction was not shown to be tight. Here we complete the circle of reductions between mechanism design and algorithm design that Weinberg worked towards, guaranteeing that the original reduction does not increase the complexity of the original problem. We do so through an approximation-preserving reduction between two related problems, ODP and SADP. In addition, we provide more principled and specific hardness of approximation results for multiple valuation classes.