Research map / Learning theory and algorithms / Submodular and game algorithms
Maximin Fairness with Mixed Divisible and 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 |
|---|---|---|---|
| Allow divisible cake alongside indivisible goods | Worst-case MMS approximation guarantee across all instances · Mixed goods versus indivisible goods instances | MMS approximation guarantee: γ_M = γ_I | No clear effect |
| Add a small amount of divisible cake | The constructed indivisible-goods instance for n ≥ 6 · Counterexample instance | MMS approximation guarantee: (1 - 2ε)/(1 - ε) -> at most 1 - 3ε/2 | Hurt |
| Use the constructive mixed-goods allocation algorithm | Mixed goods instances · Arbitrary mixed goods instance | MMS approximation guarantee: α = min{1, 1/2 + min_{i ∈ N}{u_i(C)/(2(n-1) · MMS_i)}} | Helped |
| Provide cake worth at least (n-1) times each agent's MMS | Mixed-MMS algorithm · Mixed goods instances | MMS allocation: u_i(C) ≥ (n-1)MMS_i -> full-MMS | Helped |
| Replace heterogeneous cake with homogeneous cake of equal value per agent, then allocate the real cake by weighted proportionality | Mixed-MMS algorithm · Mixed goods with heterogeneous cake | MMS approximation guarantee | No clear effect |
| Approximate MMS values and discretize cake for polynomial-time computation | Mixed-MMS algorithm · Mixed goods instances | MMS approximation guarantee: (1-ε)α'-MMS, α' ≥ α | Hurt |
| Use an EFM allocation | Mixed goods allocation · Mixed goods instances | MMS approximation guarantee: v_i(A_i) ≥ (MMS_i(n, M) + v_i(C))/n ≥ MMS_i(n, M ∪ C)/n | Helped |
Closest papers by meaning
- Groupwise Maximin Fair Allocation of Indivisible Goods (AAAI 2018 · similarity 0.92)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.92)
- Fair Allocation of Items in Multiple Regions (AAAI 2024 · similarity 0.91)
- 1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations (AAAI 2024 · similarity 0.90)
- Improved Maximin Share Approximations for Chores by Bin Packing (AAAI 2025 · similarity 0.90)
- Constrained Fair and Efficient Allocations (AAAI 2025 · similarity 0.90)
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.