Group:Student Seminar
Title: How Well Does Fairness Approximate Social Welfare?
Speaker: Xiaohui Bei University
Time: 2011-11-22 16:00-2011-11-22 17:00
Venue: FIT 1-222


Fairness and efficiency (a.k.a. social welfare) are among the most critical conditions in resource allocation. In most settings one cannot achieve optimal fairness and social welfare simultaneously, and a fair allocation may result in a loss in social welfare. We study the interconnection and trade off between fairness and social welfare. The question we would like to address is that "What is the best possible approximation of social welfare one can achieve while ensuring (approximate) fairness?".

We consider subadditive functions and give a nearly optimal bound on fairness and social welfare bifactor approximation regardless of computational constraints. We also give polynomial time algorithms to compute allocations with constant bifactor approximation.