Research map / Learning theory and algorithms / Submodular and game algorithms
Fair Division of 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 |
|---|---|---|---|
| Use an envy-freeness-for-mixed-goods criterion that applies EF1 to all-indivisible bundles and EF to bundles containing divisible goods | Mixed divisible and indivisible goods allocation · Mixed divisible and indivisible goods | existence of a fair allocation | Helped |
| Use a perfect-allocation oracle and alternate cake allocation with envy-cycle elimination | EFM Algorithm · Mixed divisible and indivisible goods | Robertson-Webb queries: O(n^4) Robertson-Webb queries | Helped |
| Replace exact perfect allocation with approximate EF allocation and allow ε-envy | ε-EFM Algorithm · Mixed divisible and indivisible goods | running time: O(n^4/ε + m n log m) | Helped |
| Use cut-and-choose after partitioning indivisible goods | Two-Agent EFM Algorithm · Two agents, mixed goods | existence of an EFM allocation | Helped |
| Use piecewise linear density functions with an efficient perfect-allocation procedure | EFM Algorithm · Any number of agents with piecewise linear cake valuations | computability of an EFM allocation | Helped |
| Require both EFM and Pareto optimality | Mixed divisible and indivisible goods allocation · Mixed divisible and indivisible goods | compatibility with Pareto optimality | Hurt |
| Require weak EFM together with fractional Pareto optimality | Mixed divisible and indivisible goods allocation · Mixed divisible and indivisible goods | compatibility with fractional Pareto optimality | Hurt |
| Use maximum Nash welfare as a rule for selecting a mixed-goods allocation | Mixed divisible and indivisible goods allocation · Two agents, two indivisible goods, one homogeneous cake | weak EFM: 0.2994 | Hurt |
Closest papers by meaning
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.92)
- Fair Allocation of Items in Multiple Regions (AAAI 2024 · similarity 0.92)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.92)
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.92)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.92)
- Online Fair Division Meets Reordering Buffers (NeurIPS 2026 · similarity 0.92)
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.