Consensus Halving for Sets of Items
From MaRDI portal
Publication:5870379
DOI10.1287/MOOR.2021.1249zbMath1505.91198arXiv2007.06754OpenAlexW4210952501MaRDI QIDQ5870379
Alexandros Hollender, Warut Suksompong, Pasin Manurangsi, Paul W. Goldberg, Ayumi Igarashi
Publication date: 9 January 2023
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2007.06754
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)
Related Items (2)
On the Complexity of Equilibrium Computation in First-Price Auctions ⋮ Almost envy-freeness for groups: improved bounds via discrepancy theory
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sets on which several measures agree
- Splitting necklaces
- On the complexity of the parity argument and other inefficient proofs of existence
- Asymptotic existence of fair divisions for groups
- Approximate maximin shares for groups of agents
- Consensus-halving via theorems of Borsuk-Ulam and Tucker
- Almost envy-freeness in group resource allocation
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- Democratic fair allocation of indivisible goods
- Fair cake-cutting among families
- Computing a small agreeable set of indivisible items
- Agreeable sets with matroidal constraints
- On the Complexity of Nash Equilibria and Other Fixed Points
- Bisection of Circle Colorings
- Envy-Free Division of Land
- Minimizing the Worst Slowdown: Offline, Online
- Settling the complexity of computing two-player Nash equilibria
- Inapproximability of Nash Equilibrium
- Competitive Division of a Mixed Manna
- The Borsuk-Ulam Theorem and Bisection of Necklaces
- Algorithmic Solutions for Envy-Free Cake Cutting
- Fairly Allocating Many Goods with Few Queries
- Almost Envy-Freeness with General Valuations
- How to Cut a Cake Fairly: A Generalization to Groups
- The Complexity of Computing a Nash Equilibrium
- The complexity of splitting necklaces and bisecting ham sandwiches
- Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm
- Consensus halving is PPA-complete
- A Moment Problem in L 1 Approximation
- Twenty Lectures on Algorithmic Game Theory
- The classes PPA-\(k\): existence from arguments modulo \(k\)
This page was built for publication: Consensus Halving for Sets of Items
