Approximate Solutions To Max-Min Fair and Proportionally Fair Allocations of Indivisible Goods

摘要

Max-min fair allocations and proportionally fair allocations are desirable outcomes in a fair division of indivisible goods. Unfortunately, such allocations do not always exist, not even in very simple settings with few agents. A natural question is to ask about the largest value c for which there is an allocation such that every agent has utility of at least c times her fair share. Our goal is to approximate this value c. For additive utilities, we show that when the number of agents is fixed, one can approximate c by a polynomial-time approximation scheme. We show that the case when utility functions are defined based on scoring vectors (binary, Borda, and lexicographic vectors) is tractable. For 2-additive functions, we show that a bounded constant for max-min fair allocations does not exist, not even when there are only two agents. We explore a class of symmetric submodular functions for which a tight 1/2-max-min fair allocation exists and show how it can be approximated within a factor of 1/4.