Search Results

In resource allocation problems, a central planner often strives to have a fair assignment. A challenge they might face, however, is that there are several objectives that could be argued to be fair, such as the max-min and maximum social welfare. In this work, we study bipartite assignment problems involving the optimization of a class of functions that is sensitive to the relative utilities derived by individuals in allocation and captures these traditional objectives. We introduce and study a subclass of evaluation functions that targets the average welfare attained within some interval of the economic ladder (e.g., the bottom 10%, middle 50%, or top 80%). We provide an efficient algorithm that can be used to optimize the welfare for an arbitrary interval and also show how the approach can be used to approximate more general evaluation functions. We also study a subclass of evaluation functions consisting of the "fair" ordered weighted averages (OWA) introduced by Lesca et al. (Algorithmica 2019), which are most sensitive to the utilities received by the worst-off individuals. We provide a simple proof that optimizing this objective belongs to the class XP.