Research map / Multi-agent systems and games / Games and equilibria
Maxileximin Envy Allocations and Connected Goods
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.
Introduces maxileximin allocations (leximin over agents' maximum envy, tie-broken by maximum social welfare) for connected fair division of indivisible goods, and studies their computational complexity.
Problem
Fair allocation of indivisible goods when envy-free allocations may not exist and goods must form connected bundles on a graph; the goal is an always-existing fair and efficient allocation.
Approach
Define fairness as lexicographic minimization of the sorted envy vector (agents' dissatisfaction = maximum envy), with social welfare maximization as a tie-breaker, giving maxileximin allocations that always exist; analyze their complexity under connectivity constraints.
Key results
- MLM-CFD is F-Delta-P-2 complete, even on path and star graphs.
- MLM-CFD is F-Delta-P-2 hard even on smooth utility functions with polynomially bounded values.
- With a bounded number of agents, smooth utilities and bounded treewidth, MLM-CFD belongs to LogCFL-functional class and is polynomial time parallelizable.
Surprising findings
- Hardness holds even on instances where envy-free allocations are guaranteed to exist, since the problem reduces to maximizing social welfare among envy-free allocations.
Limitations
- Intractable (F-Delta-P-2 complete) with arbitrary number of agents and even with smooth utilities on path/star graphs.
- Tractability requires bounded number of agents, bounded treewidth and small utility values; NP-hard with two agents and arbitrary values even on bounded treewidth.
Experimental setup
Builds on: Nucleolus connected fair division (Bouveret et al. 2017) OWA envy minimization (Shams et al. 2021) treewidth
Closest papers by meaning
- Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints (AAAI 2019 · similarity 0.90)
- The Price of Connectivity in Fair Division (AAAI 2021 · similarity 0.90)
- Fair Division of Mixed Divisible and Indivisible Goods (AAAI 2020 · similarity 0.90)
- Optimizing the Envy Cycle Elimination Algorithm (NeurIPS 2026 · similarity 0.89)
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.88)
- Constrained Fair and Efficient Allocations (AAAI 2025 · similarity 0.88)
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.