Abstract: We consider the problem of maximizing welfare when allocating $m$ items to $n$ players with subadditive utility functions. Our main result is a way of rounding any fractional solution to a linear programming relaxation to this problem so as to give a feasible solution of welfare at least $1/2$ that of the value of the fractional solution. This approximation ratio of $1/2$ is an improvement over an $\Omega(1/\log m)$ ratio of Dobzinski, Nisan, and Schapira [Proceedings of the 37th Annual ACM Symposium on Theory of Computing (Baltimore, MD), ACM,...
(read more)
Topics: 
Discrete mathematics
Mathematical economics
Combinatorics