Research map / Multi-agent systems and games / Games and equilibria
Fair Division with Social Impact
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 also has a social-impact valuation, giving price-of-fairness bounds for utilitarian social welfare under EF1, EFX, EF2, PROP1 and epistemic EF1, and proposes socially aware envy-freeness (sEF1) that can be combined with optimal welfare.
Problem
Fair division of indivisible goods when allocating goods has an externality on society, measured by a second per-agent social impact valuation; the goal is to be fair to agents while maximizing utilitarian social impact.
Approach
Introduce a second additive social-impact function per agent and measure the price of fairness with respect to utilitarian social impact; show linear-in-n approximations are impossible for standard fairness notions when agents ignore their impact, and define socially aware envy-freeness (sEF1) under which an optimal and sEF1 allocation always exists.
Key results
- Under EF1 no approximation better than n-k+1 to the optimal utilitarian social impact is possible for EFk; for EFX and PROP1/epistemic EF1 no approximation better than n is possible.
- An n-approximation subject to EF2 and to epistemic EF1 plus PROP1 is achievable in polynomial time for additive valuations; an O(n^2) approximation subject to EF1 is given (with 2n for a case of the analysis).
- An allocation that is both utilitarian optimal and sEF1 always exists and can be computed in polynomial time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require EF1 fairness instead of unconstrained social-welfare maximization | Additive valuations · Social-impact maximization | approximation factor: O(n^2) | Hurt |
| Require EF1 fairness for ordered valuations | Ordered valuations · Social-impact maximization | approximation factor: n | Hurt |
| Require EFX fairness | Identical valuations · Social-impact maximization | approximation factor: n | Hurt |
| Relax EF1 to EF2 | Additive valuations · Social-impact maximization | approximation factor: O(n^2) -> n | Helped |
| Use epistemic EF1 and PROP1 fairness | Additive valuations · Social-impact maximization | approximation factor: O(n^2) -> n | Helped |
| Require socially aware EF1 instead of ordinary EF1 | Socially aware agents · Social-impact maximization | approximation factor: O(n^2) -> optimal | Helped |
| Require EFk fairness, even with identical agents | Additive valuations · Social-impact maximization | approximation lower bound: n-k+1 | Hurt |
| Require EFX fairness | Additive valuations · Social-impact maximization | approximation lower bound: n | Hurt |
| Require PROP1 fairness | Additive valuations · Social-impact maximization | approximation lower bound: n | Hurt |
Surprising findings
- Maximizing social impact while requiring EF1 cannot beat a linear-in-n approximation, yet socially aware agents allow an optimal and sEF1 allocation to always exist.
Limitations
- Results are theoretical; no experiments are reported.
- Approximation for general EF1 is O(n^2) rather than linear, and the gap to the lower bound remains.
- Analysis is limited to additive valuations and utilitarian welfare; chores are left to future work.
Experimental setup
Metrics: price of fairness approximation ratio of utilitarian social welfare
Baselines: SimpleEF1Approx
Builds on: envy-cycle elimination round-robin EF1 EFX epistemic EF1
Closest papers by meaning
- Mixed Fair Division: A Survey (AAAI 2024 · similarity 0.88)
- Fair Division with Market Values (AAAI 2025 · similarity 0.86)
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.86)
- The (Exact) Price of Cardinality for Indivisible Goods: A Parametric Perspective (AAAI 2025 · similarity 0.86)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.85)
- Reducing Leximin Fairness to Utilitarian Optimization (AAAI 2025 · similarity 0.85)
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.