Research map / Learning theory and algorithms / Submodular and game algorithms
Fair Allocation of Indivisible Chores: Beyond Additive Costs
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 submodular rather than additive costs | Chore allocation under MMS · Submodular costs | MMS approximation lower bound: min\{n,\frac{\log m}{\log \log m}\} | Hurt |
| Use a subadditive-cost allocation guarantee | General chore allocation · Subadditive costs | MMS approximation: \min\{n, \lceil\log m\rceil\} | Helped |
| Require 1-out-of-d MMS with d ≥ 2 | Submodular chore allocation · Submodular costs | Allocation existence: 2\le d\le n | Hurt |
| Use bag filling and imaginary bin assignments | Bin packing allocation · Bin packing | 1-out-of-d MMS: 1-out-of-\lfloor \frac{n}{2} \rfloor | Helped |
| Use n bundles and select one recipient per round | Bin packing allocation · Bin packing | MMS approximation: 2-MMS | Helped |
| Use round-robin bundles and imaginary machine assignments | Job scheduling allocation · Job scheduling | 1-out-of-d MMS: 1-out-of-\lfloor \frac{n}{2} \rfloor | Helped |
| Use n bundles and allocate each bundle to one agent | Job scheduling allocation · Job scheduling | MMS approximation: 2-MMS | Helped |
| Allow subadditive costs rather than restrict to additive costs | PROP1 and PROPX fairness · Subadditive costs | PROP1 and PROPX approximation lower bound: n | Hurt |
Closest papers by meaning
- Improved Maximin Share Approximations for Chores by Bin Packing (AAAI 2025 · similarity 0.94)
- 1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations (AAAI 2024 · similarity 0.90)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.89)
- Settling the Maximin Share Fairness for Scheduling among Groups of Machines (ICML 2025 · similarity 0.89)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.89)
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.89)
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.