Fair Division with Bounded Sharing: Binary and Non-degenerate Valuations

A set of objects is to be divided fairly among agents with different tastes, modeled by additive utility-functions. An agent is allowed to share a bounded number of objects between two or more agents in order to attain fairness. The paper studies various notions of fairness, such as proportionality, envy-freeness, equitability, and consensus. We analyze the run-time complexity of finding a fair allocation with a given number of sharings under several restrictions on the agents’ valuations, such as: binary generalized-binary and non-degenerate. — NOTE: due to space constraints, we had to move several parts that appeared on the submitted version to appendices. All material can be found in the full version at https://arxiv.org/abs/1912.00459 [2].