Fair allocation of conflicting items

摘要

We study fair allocation of indivisible items, where the items are furnished with a set of conflicts, and agents are not permitted to receive conflicting items. This kind of constraint captures, for example, participating in events that overlap in time, or taking on roles in the presence of conflicting interests. We demonstrate, both theoretically and experimentally, that fairness characterizations such as EF1, MMS and MNW still are applicable and useful under item conflicts. Among other existence, non-existence and computability results, we show that a \(1/\Delta \)-approximate MMS allocation for n agents may be found in polynomial time when \(n>\Delta >2\), for any conflict graph with maximum degree \(\Delta\), and that, if \(n > \Delta \), a 1/3-approximate MMS allocation always exists.