Almost envy-freeness for groups: improved bounds via discrepancy theory
From MaRDI portal
Publication:2166776
DOI10.1016/j.tcs.2022.07.022OpenAlexW3157188407MaRDI QIDQ2166776
Warut Suksompong, Pasin Manurangsi
Publication date: 25 August 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2105.01609
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A theory of a heterogeneous divisible commodity exchange economy
- Discrepancy of set-systems and matrices
- Splitting necklaces
- Welfare bounds in the fair division problem
- On the fair division of a heterogeneous commodity
- Asymptotic existence of fair divisions for groups
- Approximate maximin shares for groups of agents
- Consensus-halving via theorems of Borsuk-Ulam and Tucker
- Inapproximability results for set splitting and satisfiability problems with no mixed clauses
- Picking sequences and monotonicity in weighted fair division
- Almost envy-freeness in group resource allocation
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- Fair division of mixed divisible and indivisible goods
- Democratic fair allocation of indivisible goods
- Fair cake-cutting among families
- Rent division among groups
- Deterministic discrepancy minimization via the multiplicative weight update method
- Clustering with qualitative information
- A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
- On maximum weighted Nash welfare for binary valuations
- Constructive Discrepancy Minimization by Walking on the Edges
- Six Standard Deviations Suffice
- Multicolour Discrepancies
- Fair Allocation of Indivisible Goods to Asymmetric Agents
- Closing Gaps in Asymptotic Fair Division
- A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching
- Introduction to the Theory of Fair Allocation
- Fair Allocation of Indivisible Goods
- How to Cut a Cake Fairly: A Generalization to Groups
- Consensus halving is PPA-complete
- A Moment Problem in L 1 Approximation
- The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
- Consensus Halving for Sets of Items
- On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources
This page was built for publication: Almost envy-freeness for groups: improved bounds via discrepancy theory
