B - Algorithms and Complexity

Summary

Most allocation problems in part III of the book can be modeled as mixed integer linear programs. We now discuss algorithms for pure linear programs and integer linear programs. While pure LPs can be solved in polynomial time, integer linear programs are computationally hard, as we will see. First, though, we introduce computational complexity and important complexity classes.

Computational Complexity

Complexity theory is important for market design, because many allocation and payment rules are computationally hard integer programming problems. For very practical reasons, it is important to understand whether a problem is tractable and we can hope to find exact solutions in a reasonable time. Sorting a series of bids by price for a single object auction is a computationally simple task. In contrast, the WDP of a combinatorial auction or some allocation problems described in section 7.5 are computationally hard problems, where we cannot hope for a fast and exact algorithm. A complexity class is a set of problems of related complexity (see Papadimitriou (1993) for an extensive treatment). Here, we introduce basic terminology and restrict ourselves to the two wellknown complexity classes P and NP.

A decision problem is a question in a formal system with a yes-or-no answer. For example, the decision version of the WDP in a combinatorial auction refers to a WDP in which the auctioneer wants to know only if there is an allocation with a revenue larger than a particular amount. In contrast, an optimization problem is the problem of finding the best solution from all feasible solutions. There are techniques for transforming optimization problems into decision problems, and vice versa, that do not significantly change the computational difficulty of these problems. For this reason, complexity theory has typically focused on decision problems.

For decision problems in the class P, there are algorithms where the “yes” instances can be accepted in polynomial time by a deterministic Turing machine. The worst-case running time of a polynomial algorithm is of order O(g) for some polynomial g.