Computing welfare-maximizing fair allocations of indivisible goods
From MaRDI portal
Abstract: We analyze the run-time complexity of computing allocations that are both fair and maximize the utilitarian social welfare, defined as the sum of agents' utilities. We focus on two tractable fairness concepts: envy-freeness up to one item (EF1) and proportionality up to one item (PROP1). We consider two computational problems: (1) Among the utilitarian-maximal allocations, decide whether there exists one that is also fair; (2) among the fair allocations, compute one that maximizes the utilitarian welfare. We show that both problems are strongly NP-hard when the number of agents is variable, and remain NP-hard for a fixed number of agents greater than two. For the special case of two agents, we find that problem (1) is polynomial-time solvable, while problem (2) remains NP-hard. Finally, with a fixed number of agents, we design pseudopolynomial-time algorithms for both problems. We extend our results to the stronger fairness notions envy-freeness up to any item (EFx) and proportionality up to any item (PROPx).
Recommendations
Cites work
- `` Strong NP-Completeness Results
- A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
- A robust disaster preparedness model for effective and fair disaster response
- Approximating the Nash social welfare with indivisible items
- Complexity of finding Pareto-efficient allocations of highest welfare
- Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity
- Fair Allocation of Indivisible Goods
- Fair division with binary valuations: one rule to rule them all
- Fair resource allocation: using welfare-based dominance constraints
- Fairness and efficiency in multiportfolio optimization
- Finding fair and efficient allocations when valuations don't add up
- Group Envy Freeness and Group Pareto Efficiency in Fair Division with Indivisible Items
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 7415106 (Why is no real title available?)
- Improving fairness in ambulance planning by time sharing
- Inequity averse optimization in operational research
- Maximizing Nash product social welfare in allocating indivisible goods
- Multi-objective vehicle routing problems
- Non-monetary coordination mechanisms for time slot allocation in warehouse delivery
- NON-NULL RANKING MODELS. I
- On fairness via picking sequences in allocation of indivisible goods
- On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences
- Optimal bounds on the price of fairness for indivisible goods
- Price of fairness for allocating a bounded resource
- Price of fairness in two-agent single-machine scheduling problems
- Rank-maximal matchings
- The efficiency of fair division
- The price of fairness for a small number of indivisible items
- Two-player fair division of indivisible items: comparison of algorithms
Cited in
(18)- Fair welfare maximization
- Welfarism and rationalizability in allocation problems with indivisibilities
- On the complexity of fair house allocation
- Fair and efficient allocation with few agent types, few item types, or small value levels
- Maximizing Nash product social welfare in allocating indivisible goods
- scientific article; zbMATH DE number 4160481 (Why is no real title available?)
- scientific article; zbMATH DE number 6902543 (Why is no real title available?)
- scientific article; zbMATH DE number 6466174 (Why is no real title available?)
- Computing fair and efficient allocations with few utility values
- EFX allocations exist for binary valuations
- Fair division with allocator's preference
- The price of fairness for budget-feasible EF1 allocations
- Fair distribution of delivery orders
- Analyzing the price of fairness in scheduling problems with two agents
- Nearly tight bounds on the price of fairness for indivisible items under budget constraints
- A fair allocation is approximately optimal for indivisible chores, or is it?
- Pareto-optimal linear programming
- Maximizing social welfare among EF1 allocations at the presence of two types of agents
This page was built for publication: Computing welfare-maximizing fair allocations of indivisible goods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6109821)
