Abstract:
The author considers the problem of maximizing welfare when allocating m items to n players. In this problem, a feasible allocation allocates every item to at most one player. For every player Pi, her utility wi depends only on the set of items she receives. The goal is to find a feasible allocation that maximizes social welfare, that is, maximizing ∑wi(S).
The author presents a rounding technique that converts a fractional LP solution to a feasible allocation resulting in a 1/2 approximation. More importantly the author shows this is true even when utility functions are subadditive.