Two's company, three's a crowd: consensus-halving for a constant number of agents
type: Item
instance of: scholarly article
title: Two's company, three's a crowd: consensus-halving for a constant number of agents
author: Argyrios Deligkas
author: Aris Filos-Ratsikas
author: Alexandros Hollender
published in: Artificial Intelligence
publication date: 2022-11-08T00:00:00Z
full work available at URL: https://arxiv.org/abs/2007.15125
Mathematics Subject Classification ID: 68Txx
zbMATH DE Number: 7613162
zbMATH Keywords: consensus-halving
zbMATH Keywords: fair division
zbMATH Keywords: computational complexity
zbMATH Keywords: query complexity
zbMATH Keywords: Robertson-Webb
MaRDI profile type: Publication
OpenAlex ID: W3045663689
cites work: 2-D Tucker is PPA complete
cites work: Splitting necklaces
cites work: The Borsuk-Ulam Theorem and Bisection of Necklaces
cites work: An improved envy-free cake cutting protocol for four agents
cites work: A discrete and bounded envy-free cake cutting protocol for four agents
cites work: Fair Cake Division Under Monotone Likelihood Ratios
cites work: The relative complexity of NP search problems
cites work: Drei Sätze über die n-dimensionale euklidische Sphäre
cites work: Fair Allocation of Indivisible Goods
cites work: Q4338900
cites work: Matching algorithmic bounds for finding a Brouwer fixed point
cites work: Settling the complexity of computing two-player Nash equilibria
cites work: Q5365081
cites work: The Complexity of Computing a Nash Equilibrium
cites work: Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
cites work: Discrete fixed points: models, complexities, and applications
cites work: Algorithmic Solutions for Envy-Free Cake Cutting
cites work: On the Complexity of Nash Equilibria and Other Fixed Points
cites work: The complexity of gradient descent: CLS = PPAD ∩ PLS
cites work: Consensus halving is PPA-complete
cites work: The complexity of splitting necklaces and bisecting ham sandwiches
cites work: Q5005124
cites work: Q3256187
cites work: Bisection of Circle Colorings
cites work: Contiguous Cake Cutting: Hardness Results and Approximation Algorithms
cites work: Consensus halving for sets of items
cites work: A Sperner lemma complete for PPA
cites work: A Moment Problem in L 1 Approximation
cites work: Measure partitions using hyperplanes with fixed directions
cites work: White-Box vs. Black-Box Complexity of Search Problems
cites work: Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
cites work: On total functions, existence theorems and computational complexity
cites work: Simplotopal maps and necklace splitting
cites work: Q5836126
cites work: On the complexity of the parity argument and other inefficient proofs of existence
cites work: Cake Cutting Algorithms
cites work: Approximating fair division with a limited number of cuts
cites work: Q4221107
cites work: Consensus-halving via theorems of Borsuk-Ulam and Tucker
cites work: Sur la division pragmatique
cites work: Rental Harmony: Sperner's Lemma in Fair Division
cites work: Q5837940
cites work: On the complexity of cake cutting
DOI: 10.1016/J.ARTINT.2022.103784
description: scientific article; zbMATH DE number 7613162