Research map / Learning theory and algorithms / Submodular and game algorithms
Fair Division with Market Values
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.
Studies fair division of indivisible goods where each agent has subjective additive utilities and a common additive market value, showing which combinations of SD-EF1, EF1, PO, MMS, EFX are achievable, extending to non-additive valuations and cake-cutting.
Problem
Allocating indivisible goods (and cake) so that the allocation is fair simultaneously w.r.t. agents' subjective valuations and a separate market valuation that every agent shares, which may encode feasibility constraints.
Approach
Treat the market valuation as an identical additive valuation profile alongside subjective utilities; show SD-EF1 on both sides can fail, but EF1 on subjective utilities plus SD-EF1 on market values is always achievable via cardinality-constrained EF1 (reduction to known results), and PO plus EF1 on market values via a Fisher-market / EQ1 argument.
Key results
- SD-EF1 on both subjective utilities and market values can fail: a counterexample with 2 agents and 7 goods exists.
- EF1 w.r.t. subjective utilities together with SD-EF1 w.r.t. market values always exists and is computable in polynomial time.
- PO w.r.t. subjective utilities together with EF1 w.r.t. market values (via fPO and EQ1) always exists for strictly positive utilities.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require SD-EF1 on both subjective utilities and market values | Fair division of indivisible goods · Indivisible goods; 2 agents and 7 goods | existence of a simultaneous fairness guarantee | Hurt |
| Relax subjective-utility SD-EF1 to EF1 while retaining market-value SD-EF1 | Fair division of indivisible goods · Indivisible goods | existence of a simultaneous fairness guarantee | Helped |
| Restrict to two agents and at most six goods | SD-EF1 on subjective utilities and market values · Indivisible goods; 2 agents, at most 6 goods | existence of a simultaneous fairness guarantee | Helped |
| Require identical subjective rankings across agents | SD-EF1 on subjective utilities and market values · Indivisible goods; identical subjective rankings | existence of a simultaneous fairness guarantee | Helped |
| Combine subjective-utility PO with market-value SD-EF1 | Fair division of indivisible goods · Indivisible goods; 2 agents and 6 goods | existence of a simultaneous guarantee | Hurt |
| Require α-MMS on one profile alongside EF1 or α-MMS on the other, for α > 1/n | Fair division with identical valuation profiles · Indivisible goods; 2n-1 goods | existence of a simultaneous fairness guarantee: For any α > \nicefrac{1}{n} | Hurt |
| Require EF1 on one profile and α-EFX on the other | Fair division with identical valuation profiles · Indivisible goods; 2 agents, 4 goods | existence of a simultaneous fairness guarantee: For any α \in (0,1] | Hurt |
| Use the MES allocation construction for subadditive subjective utilities and additive market values | Fair division of indivisible goods · Indivisible goods; subadditive subjective utilities | simultaneous fairness guarantee: \nicefrac{1}{2}-EF1 | Helped |
| Require simultaneous EF and PO on subjective utilities plus EF on market values | Cake division · Cake division; 3 agents | existence of a simultaneous fairness guarantee | Hurt |
| Require finite query complexity for simultaneous cake EF under subjective utilities and market values | Cake division · Cake division; two agents | finite-query protocol existence | Hurt |
Surprising findings
- SD-EF1 on both sides is impossible already with 2 agents and 7 goods, even though EF1 on both sides is achievable in the single-market-valuation case.
Limitations
- Several natural combinations (SD-EF1 on subjective with EF1 on market, EF1+PO on both) remain open.
- Monotone-valuation EF1 on both sides is open beyond two agents.
- Cake division EF+PO on subjective side with EF on market is not settled for n>=3 agents beyond impossibility for balanced variant.
Experimental setup
Builds on: EF1 existence under cardinality constraints fPO and EQ1 via Fisher markets minimal envied subsets
Closest papers by meaning
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.90)
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.90)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.90)
- Fair Division via the Cake-Cutting Share (AAAI 2025 · similarity 0.90)
- Nearly Equitable Allocations beyond Additivity and Monotonicity (AAAI 2024 · similarity 0.89)
- Towards Optimal Subsidy Bounds for Envy-Freeable Allocations (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.