Research map / Learning theory and algorithms / Submodular and game algorithms
Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination
Georgios Amanatidis, Evangelos Markakis, Apostolos Ntokos
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| Combine threshold-based preprocessing, two round-robin passes, and envy-cycle elimination | Additive goods fair division · Additive goods fair division | EFX approximation factor: 0.5 -> 0.618 | Improved |
| Combine threshold-based preprocessing, two round-robin passes, and envy-cycle elimination | Additive goods fair division · Additive goods fair division | GMMS approximation factor: 0.5 -> 0.553 | Improved |
| Combine threshold-based preprocessing, two round-robin passes, and envy-cycle elimination | Additive goods fair division · Additive goods fair division | PMMS approximation factor: 0.781 -> 0.667 | Hurt |
| Replace the preprocessing threshold φ with 3/2 (ablation) | Draft-and-Eliminate · Additive goods fair division | GMMS approximation factor: 0.553 -> 0.571 | Improved |
| Replace the preprocessing threshold φ with 3/2 (ablation) | Draft-and-Eliminate · Additive goods fair division | EFX approximation factor: 0.618 -> 0.6 | Hurt |
| Replace the preprocessing threshold φ with 3/2 (ablation) | Draft-and-Eliminate · Additive goods fair division | PMMS approximation factor: 0.667 -> 0.667 | No clear effect |
| Use the (φ−1/2)-adjusted envy graph during envy-cycle elimination (ablation) | Draft-and-Eliminate · Additive goods fair division | PMMS approximation factor: 0.667 -> 0.717 | Improved |
| Use the (φ−1/2)-adjusted envy graph during envy-cycle elimination (ablation) | Draft-and-Eliminate · Additive goods fair division | EF1 approximation factor: 1 -> 0.894 | Hurt |
| Use the (φ−1/2)-adjusted envy graph during envy-cycle elimination (ablation) | Draft-and-Eliminate · Additive goods fair division | EFX approximation factor: 0.618 -> 0.618 | No clear effect |
| Use the (φ−1/2)-adjusted envy graph during envy-cycle elimination (ablation) | Draft-and-Eliminate · Additive goods fair division | GMMS approximation factor: 0.553 -> 0.553 | No clear effect |
| Pack the final three goods into two virtual goods and use envy-cycle elimination | Draft-Pack-and-Eliminate · m ≤ n+2 goods and agents | GMMS existence | Improved |
Closest papers by meaning
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.95)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.92)
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.92)
- Epistemic Pairwise Maximin Share (NeurIPS 2026 · similarity 0.92)
- Understanding EFX Allocations: Counting and Variants (AAAI 2025 · similarity 0.91)
- Fair Allocation of Items in Multiple Regions (AAAI 2024 · similarity 0.91)
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.
