Research map / Learning theory and algorithms / Submodular and game algorithms
Mixed Fair Division: A Survey
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
A survey of fair division with mixed resource types: indivisible goods and chores, mixed divisible and indivisible goods, and indivisible goods with monetary subsidy, summarizing known results and open problems.
Problem
Fair division when resources are mixtures of goods and chores, divisible and indivisible goods, or indivisible goods combined with subsidies, where classic single-type fairness notions do not directly apply.
Approach
Organizes the mixed fair division literature along three settings (indivisible goods and chores, mixed divisible/indivisible goods, indivisible goods with subsidy), surveying fairness notions (EF1, EFX, EFM, PROP1, PROPX, PROP-alpha, MMS) and their existence and computation results, and highlighting open problems.
Key results
- Double round-robin returns an EF1 allocation in polynomial time for mixed indivisible goods and chores with additive utilities.
- An EFM allocation of mixed goods always exists and can be found in polynomial time with polynomially many Robertson-Webb queries and a perfect-partition oracle.
- For additive utilities, subsidy of at most one per agent suffices for an envy-free allocation (EF1 and balanced), so total subsidy n-1 suffices.
Surprising findings
- EFX-style round-robin fails EF1 with mixed goods and chores, unlike pure goods.
- EFM is incompatible with Pareto optimality, while the weaker PROP-alpha is compatible with PO.
Limitations
- Survey of theoretical results only; no new experiments.
- Many existence questions remain open (e.g., EF1 for three or more agents with mixed items).
Experimental setup
Builds on: round-robin envy-cycle elimination maximum Nash welfare Adjusted Winner
Closest papers by meaning
- Fast & Fair: A Collaborative Platform for Fair Division Applications (AAAI 2024 · similarity 0.89)
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.88)
- Fair Allocation of Items in Multiple Regions (AAAI 2024 · similarity 0.88)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.88)
- Fair Division with Social Impact (AAAI 2025 · similarity 0.88)
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.87)
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.