A Truthful Mechanism for the Generalized Assignment Problem
A Truthful Mechanism for the Generalized Assignment Problem
We propose a truthful-in-expectation, (1-1/ e )-approximation mechanism for a strategic variant of the generalized assignment problem (GAP). In GAP, a set of items has to be optimally assigned to a set of bins without exceeding the capacity of any singular bin. In the strategic variant of the problem we …