Research map / Learning theory and algorithms / Submodular and game algorithms
Groupwise Maximin Fair Allocation of Indivisible Goods
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the polynomial-time EFL allocation algorithm | Additive-valuation fair allocation · Additive valuations | GMMS approximation guarantee: 1/2 | Helped |
| Apply the EFL algorithm to randomly generated instances | EFL algorithm · 1000 random instances | Average GMMS approximation factor: 0.98 | Helped |
| Use the EFL algorithm instead of exact GMMS computation | GMMS computation · Random instances | Runtime: 10^7 times faster | Helped |
| Strengthen MMS to groupwise maximin share fairness | Indivisible-goods allocation · Additive valuations | Fairness guarantee | Helped |
| Use EF1 allocations under binary valuations | Additive, binary valuations · Additive, binary valuations | GMMS allocation existence | Helped |
| Choose a lexicographically maximal allocation | Agents with identical valuations · Identical valuations | GMMS allocation existence | Helped |
| Use the EFL algorithm on same-order preference instances | EFL algorithm · Same-order preferences versus non-SOP instances | Average GMMS approximation factor | Hurt |
| Use the EFL algorithm when the number of items is a multiple of the number of agents | EFL algorithm · Randomly generated instances | GMMS approximation factor | Helped |
| Use the EFL algorithm rather than arbitrary-order good assignment | Fair allocation algorithm · Additive valuations | EFL guarantee | Helped |
Closest papers by meaning
- 1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations (AAAI 2024 · similarity 0.91)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.91)
- Improved Maximin Share Approximations for Chores by Bin Packing (AAAI 2025 · similarity 0.90)
- Settling the Maximin Share Fairness for Scheduling among Groups of Machines (ICML 2025 · similarity 0.89)
- Epistemic Pairwise Maximin Share (NeurIPS 2026 · similarity 0.89)
- Fair Division via the Cake-Cutting Share (AAAI 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.