A simple and fast algorithm for convex decomposition in relax-and-round mechanisms

Abstract Most allocation problems on markets are computationally hard. Approximation mechanisms aim for truthfulness and polynomial runtime with provable solution quality. In a seminal contribution, Lavi and Swamy (2011) provide a black-box reduction from approximation algorithms to approximation mechanisms that are truthful-in-expectation without degrading the approximation ratio. This yields a very general approach to designing approximation mechanisms for many market design problems. However, the framework requires a convex decomposition of fractional linear programming solutions. Until recently, the only known polynomial-time decomposition technique relied fundamentally on the notoriously inefficient ellipsoid method. To address this issue, we present a simple and much faster decomposition technique based on an effective geometric algorithm. After a formal comparison of the worst-case performance with a recently published alternative decomposition technique, we conduct an extensive experimental evaluation based on a coordination problem in logistics to show the advantages of the geometric algorithm. The evaluation illustrates runtimes one can expect in a realistic environment and simplifies the application of relax-and-round mechanisms in practice.