Exact and Approximate Maximin Share Allocations in Multi-Graphs

We study the problem of (approximate) maximin share (MMS) allocation of indivisible items among a set of agents. We focus on the graphical valuation model, previously stud- ied in (Christodoulou et al. 2023), in which the input is given by a graph where edges correspond to items, and vertices correspond to agents. An edge may have non-zero marginal value only for its incident vertices. We study additive, XOS and subadditive valuations and we present positive and neg- ative results for (approximate) MMS fairness, and also for (approximate) pair-wise maximin share (PMMS) fairness.