## 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

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 *P*_{i}, her utility *w*_{i}
depends only on the set of items she receives. The goal is to find a
feasible allocation that maximizes social welfare, that is,
maximizing ∑*w*_{i}(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.