Exact and approximate maximin share allocations in multi-graphs

2025/06/25 by George Christodoulou, Christodoulou, George, Symeon Mastrakoulis +1 · 2 citations
Computer Science · Economics, Econometrics and Finance · Mathematics · #Advanced Graph Theory Research #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Voting Systems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2506.20317

openalex publication_date 2025/06/25 · openalex created_date 2025/10/09 · openalex updated_date 2026/08/01

Abstract

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.

Citations

• An FPTAS for 7/9-Approximation to Maximin Share Allocations
• Improved Maximin Share Guarantee for Additive Valuations
• From multi-allocations to allocations, with subadditive valuations
• Tractable Graph Structures in EFX Orientation
• Fair allocations with subadditive and XOS valuations
• Independent transversal blow-up of graphs
• Concentration and maximin fair allocations for subadditive valuations
• On the existence of EFX allocations in multigraphs
• Maximin Share Guarantees for Few Agents with Subadditive Valuations
• EFX Allocations on Some Multi-graph Classes
• Envy-Free and Efficient Allocations for Graphical Valuations
• EFX Orientations of Multigraphs
• EF1 and EFX Orientations
• A Complete Landscape of EFX Allocations on Graphs: Goods, Chores and Mixed Manna
• Fair and Truthful Allocations Under Leveled Valuations
• Maximin Shares in Hereditary Set Systems
• 1/2 Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations
• Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations
• Improving Approximation Guarantees for Maximin Share
• Breaking the 3/4 Barrier for Approximate Maximin Share
• Simplification and Improvement of MMS Approximation
• On Fair Allocation of Indivisible Goods to Submodular Agents
• Truthful allocation in graphs and hypergraphs
• Guaranteeing Maximin Shares: Some Agents Left Behind
• A tight negative example for MMS fair allocations
• Existence and Computation of Maximin Fair Allocations Under Matroid-Rank Valuations
• An Improved Approximation Algorithm for Maximin Shares
• Comparing Approximate Relaxations of Envy-Freeness
• Approximation Algorithms for Maximin Fair Division
• On the Configuration-LP for Scheduling on Unrelated Machines
• On the structure of EFX orientations on graphs

Cited by

• Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division
• From multi-allocations to allocations, with subadditive valuations

Related

• Improved maximin fair allocation of indivisible items to three agents
• Maximin share allocations on cycles
• Breaking the 3/4 Barrier for Approximate Maximin Share
• Maximin Share Guarantees for Few Agents with Subadditive Valuations
• An Improved Approximation Algorithm for Maximin Shares