Almost envy-freeness for groups: improved bounds via discrepancy theory

DOI10.1016/J.TCS.2022.07.022MaRDI QIDQ2166776zbMATH OpenOpenAlexFDO

Authors Pasin Manurangsi, Warut Suksompong

Publication date 25 August 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

discrepancy theoryenvy-freenessfair divisionindivisible goods

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Almost envy-freeness in group resource allocation
• Optimal bounds on the price of fairness for indivisible goods
• Asymptotic existence of fair divisions for groups
• On the number of almost envy-free allocations

Cites work

• A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching
• A Moment Problem in L 1 Approximation
• A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
• A theory of a heterogeneous divisible commodity exchange economy
• Almost envy-freeness in group resource allocation
• Approximate maximin shares for groups of agents
• Asymptotic existence of fair divisions for groups
• Closing gaps in asymptotic fair division
• Clustering with qualitative information
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• Consensus Halving for Sets of Items
• Consensus halving is PPA-complete
• Consensus-halving via theorems of Borsuk-Ulam and Tucker
• Constructive discrepancy minimization by walking on the edges
• Democratic fair allocation of indivisible goods
• Deterministic discrepancy minimization via the multiplicative weight update method
• Discrepancy of set-systems and matrices
• Fair Allocation of Indivisible Goods
• Fair Allocation of Indivisible Goods to Asymmetric Agents
• Fair cake-cutting among families
• Fair division of mixed divisible and indivisible goods
• Group Envy Freeness and Group Pareto Efficiency in Fair Division with Indivisible Items
• Hardness results for consensus-halving
• How to cut a cake fairly: a generalization to groups
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• Inapproximability results for set splitting and satisfiability problems with no mixed clauses
• Introduction to the theory of fair allocation
• Multicolour Discrepancies
• On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources
• On maximum weighted Nash welfare for binary valuations
• On the fair division of a heterogeneous commodity
• Picking sequences and monotonicity in weighted fair division
• Rent division among groups
• Six Standard Deviations Suffice
• Splitting necklaces
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Tight hardness results for minimizing discrepancy
• Welfare bounds in the fair division problem

Cited in

(6)

• Fair division of indivisible goods: recent progress and open questions
• Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory
• Fair division with allocator's preference
• A new lower bound for multicolor discrepancy with applications to fair division
• Differentially private fair division
• Ordinal maximin guarantees for group fair division

This page was built for publication: Almost envy-freeness for groups: improved bounds via discrepancy theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2166776)