ICS Theory Group

CompSci 269S, Fall 2006: Theory Seminar

Nov 3, 2006, in CS 253

On maximizing welfare when utility functions are subadditive

Authored by Uriel Feige, appeared in STOC 2006

Presented by Matthew Ba Nguyen


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.