Exact and approximate maximin share allocations in multi-graphs
It extends MMS fairness to a structured valuation model (graphs), providing first positive and negative results for approximate MMS and PMMS in this setting.
This paper studies maximin share (MMS) allocations of indivisible items under graphical valuations, where items are edges and agents are vertices. For additive valuations, they achieve a 2/3-approximation for MMS and a 1/2-approximation for PMMS; for XOS and subadditive valuations, they provide impossibility results and constant-factor approximations.
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 studied by Christodolou, Fiat, Koutsoupias, and Sgouritsa ("Fair allocation in graphs", EC 2023), where 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 negative results for (approximate) MMS fairness, and also for (approximate) pair-wise maximin share (PMMS) fairness.