10 - Approximation Mechanisms

Summary

Many real-world markets require the solving of computationally hard allocation problems, and realistic problem sizes are often such that they cannot be solved optimally. For example, there have been spectrum auctions using the combinatorial clock auction with 100 licenses. The allocation problems are modeled as integer programs intended to produce an exact solution (see section 7.2), but this cannot always be guaranteed without restrictions. Actually, the number of bids in combinatorial spectrum auctions is typically restricted to a few hundred. Section 7.5 provides examples of allocation problems in other domains, sometimes using compact bid languages, which also cannot be solved optimally for larger instances. Sometimes it is acceptable to settle for suboptimal solutions. Often, heuristics are used to solve computationally hard problems. However, with heuristics we do not have worst-case bounds on the quality of the solution. In contrast, approximation algorithms provide worst-case bounds on the solution quality and a polynomial runtime. For this discussion, we expect the reader to have some basic familiarity with approximation algorithms; we provide an overview of the field and the necessary terminology and concepts in appendix B.4.

In this section, we analyze approximation mechanisms which provide good approximation ratios, which run in polynomial time, and which are also incentive-compatible. This leads to new notions of incentive compatibility beyond strategy-proofness (i.e., dominant-strategy incentive compatibility) and new types of mechanism. We often talk about truthfulness instead of incentive compatibility, both terms referring to different solution concepts setting incentives to reveal preferences truthfully.

One can think of the VCG mechanism as a black-box transformation from exact algorithms solving the allocation problem to a strategy-proof mechanism. A central question in this chapter is whether there is a similar black-box transformation, from approximation algorithms to truthful approximation mechanisms, which maintains the approximation ratios of non-truthful approximation algorithms.We show that black-box transformations for quite general allocation problems are possible with strong forms of truthfulness, when we use randomization.

Approximation algorithms are typically only available for idealized models such as knapsack problems or bin-packing problems. In practice, many allocation problems are quite messy and have many complicating side constraints that make it hard to find an approximation algorithm with a good performance guarantee.