Fair Assignment for Agents with Multiple Weights

We study the problem of fairly allocating a set of indivisible items among heterogeneous agents with a set of weights quantifying their distinct entitlements for different types of items. In this setting, each agent is associated with a preference (utility) function over the items according to its different task processing abilities. To measure the fairness, we explore the multi-weight version of MMS called multi-weight maximin share (MWMMS). In spite of the relatively negative result shown by the counterexample for MWMMS, we present an algorithm guaranteeing that each agent obtains a bundle worth at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1/n$</tex> of its MWMMS for the restricted setting. Finally, based on the fact that the relatively bad approximation occurs only in the polar case, we provide a stochastic variant, where the weights are randomly sampled from the given distribution. Theoretical analysis shows that the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1/n$</tex> -approximation can be guaranteed with a desirable probability.