An FPTAS for 7/9-Approximation to Maximin Share Allocations

2025/11/17 by Xin Huang, Huang, Xin, Shengwei Zhou +1
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems

paper · pdf · doi:10.48550/arxiv.2511.13056

openalex publication_date 2025/11/17 · openalex created_date 2025/11/19 · openalex updated_date 2026/07/28

Abstract

We present a new algorithm that achieves a (7)/(9)-approximation for the maximin share (MMS) allocation of indivisible goods under additive valuations, improving the current best ratio of (10)/(13) (Heidari et al., SODA 2026). Building on a new analytical framework, we further obtain an FPTAS that achieves a (7)/(9)-ε approximation in \tfrac1ε ⋅ poly(n,m) time. Compared with prior work (Heidari et al., SODA 2026), our algorithm is substantially simpler.

Citations

• Improved Maximin Share Guarantee for Additive Valuations
• Fair Assignment of Indivisible Chores to Asymmetric Agents
• Constant Weighted Maximin Share Approximations for Chores
• Improved MMS Approximations for Few Agent Types
• Improved Maximin Share Approximations for Chores by Bin Packing
• Share-Based Fairness for Arbitrary Entitlements
• Breaking the 3/4 Barrier for Approximate Maximin Share
• Simplification and Improvement of MMS Approximation
• A Reduction from Chores Allocation to Job Scheduling
• On picking sequences for chores
• Improved maximin fair allocation of indivisible items to three agents
• Algorithmic Fair Allocation of Indivisible Items: A Survey and New Questions
• Fair and Efficient Resource Allocation with Partial Information
• A tight negative example for MMS fair allocations
• Fair-Share Allocations for Agents with Arbitrary Entitlements
• Best-of-Both-Worlds Fair-Share Allocations
• Approximate and Strategyproof Maximin Share Allocation of Chores with Ordinal Preferences
• An Algorithmic Framework for Approximating Maximin Share Allocation of Chores
• Weighted Maxmin Fair Share Allocation of Indivisible Chores
• An Improved Approximation Algorithm for Maximin Shares
• Fair Allocation of Indivisible Goods: Improvement and Generalization
• Approximation Algorithms for Maximin Fair Division
• Fair Allocation of Indivisible Goods to Asymmetric Agents
• On Truthful Mechanisms for Maximin Share Allocations

Related

• Improved Maximin Share Guarantee for Additive Valuations
• Simplification and Improvement of MMS Approximation
• Breaking the 3/4 Barrier for Approximate Maximin Share
• An Improved Approximation Algorithm for Maximin Shares
• Improving Approximation Guarantees for Maximin Share