How to Fairly Allocate Indivisible Resources Among Agents Having Lexicographic Subadditive Utilities
How can one fairly assign a finite set of m indivisible items between n agents? This question has been extensively studied last few decades with a focus on structure of utility functions representing the agent’s preferences over subsets of items. This paper considers a scenario where all agents’ utility functions are lexicographic and subadditive. In this setting, each agent has a linear order over single items, and this order is then extended to a total order over all subsets of items using the lexicographic order. Every agent is equipped with a utility function consistent with her lexicographic preference, which is either additive or, more general, subadditive. Our task is to determine a fair allocation in the sense that the minimum utility over all agents or the product of individual utilities is maximized. As a result, we obtain 1/2-approximation algorithms for both problems with lexicographic subadditive functions. In addition, we show that the factor of 1/2 is tight for the former problem, but is not for the latter one.
چگونه می توان منابع Indivisible را در میان نمایندگان ایجاد کرد.