Mechanism Design via Dantzig-Wolfe Decomposition

Abstract. In random allocation rules, typically first an optimal frac-tional point is calculated via solving a linear program. Lying in the feasible region of the linear program, the fractional point satisfies the underlying constraints. In effect, the point represents a fractional as-signment of objects or more generally packages of objects to agents. In order to implement an expected assignment, one must decompose the point into integer solutions, each satisfying underlying constraints. The resulting convex combination can then be viewed as a probability dis-tribution over feasible assignments out of which a random assignment can be sampled. This approach has been successfully employed in com-binatorial optimization [1] as well as mechanism design with or without money [2–4]. In this paper, we show that both finding the optimal fractional point as well as its decomposition into integer solutions can be done at once. We propose an appropriate linear program which provides the desired solution. We show that the linear program can be solved via Dantzig-Wolfe decomposition. The resulting convex decomposition is tight in terms of the number of integer points according to Carathéodory the-orem. Dantzig-Wolfe decomposition is a direct implementation of the revised simplex method which is well known to be highly efficient in practice. The method can also find a decomposition into integer solutions when the fractional point is readily present perhaps as an outcome of other algorithms rather than linear programming