A Strongly Polynomial-Time 7/9-Approximation Algorithm for Maximin Share Allocations
cs.GT, cs.DS
Submitted: 2025-11-17
Updated: 2026-11-05
Comments: We have improved our result to a polynomial-time algorithm and reorganized the proof to be more structured
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Terminology
Sources
- Improved maximin fair allocation of indivisible items to three agents
- Fair Assignment of Indivisible Chores to Asymmetric Agents
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments