Coping with Hardness of Welfare Maximization by Introducing Useful Complexity Measures

Rani Izsak (Weizmann Institute of Science)

Abstract

We introduce complexity measures for set functions and apply them to the welfare maximization problem.