Efficient Fair Division with Minimal Sharing

DOI10.1287/opre.2022.2279zbMath1496.90088arXiv1908.01669OpenAlexW3086898784MaRDI QIDQ5095173

Erel Segal-Halevi, Fedor Sandomirskiy

Publication date: 5 August 2022

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1908.01669

zbMATH Keywords

polynomial-time algorithmfair divisionenvy-freenessproportional fairnessdiscrete objectsfractional Pareto-optimality

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Multi-objective and goal programming (90C29) Combinatorial optimization (90C27)

Related Items (3)

Fairness and efficiency in cake-cutting with single-peaked preferences ⋮ Multi resource allocation with partial preferences ⋮ Fair division of goods in the shadow of market values

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two-person cake cutting: the optimal number of cuts
• Fair division is hard even for amicable agents
• A note on the undercut procedure
• On finding an envy-free Pareto-optimal division
• Negative-cycle detection algorithms
• How to cut a cake fairly using a minimal number of cuts
• Asymptotic existence of fair divisions for groups
• Cake division with minimal cuts: envy-free procedures for three persons, four persons, and beyond
• Computing envy-freeable allocations with limited subsidies
• Envy-free cake division without assuming the players prefer nonempty pieces
• Fair division with subsidy
• Cake-cutting with different entitlements: how many cuts are needed?
• The undercut procedure: an algorithm for the envy-free division of indivisible items
• A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
• Simultaneously achieving ex-ante and ex-post fairness
• Rental Harmony: Sperner's Lemma in Fair Division
• Two-Person Fair Division of Indivisible Items: An Efficient, Envy-Free Algorithm
• Improved algorithms for computing fisher's market clearing prices
• Consensus of Subjective Probabilities: The Pari-Mutuel Method
• WELFARE ECONOMICS AND EXISTENCE OF AN EQUILIBRIUM FOR A COMPETITIVE ECONOMY
• On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• Approximation Algorithms for Computing Maximin Share Allocations
• Fair Enough
• A theory of school-choice lotteries
• Competitive Division of a Mixed Manna
• Which Is the Fairest (Rent Division) of Them All?
• Pareto Optimal Solutions for Smoothed Analysts
• Competitive Equilibrium with Indivisible Goods and Generic Budgets
• A strongly polynomial algorithm for linear exchange markets
• Handbook of Computational Social Choice
• Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation
• Algorithmic Game Theory
• Existence of an Equilibrium for a Competitive Economy
• A new solution to the random assignment problem.
• ENVY‐FREE DIVISION USING MAPPING DEGREE

This page was built for publication: Efficient Fair Division with Minimal Sharing