Two's company, three's a crowd: consensus-halving for a constant number of agents

DOI10.1016/J.ARTINT.2022.103784MaRDI QIDQ2093385zbMATH OpenOpenAlexFDO

Authors Argyrios Deligkas, Aris Filos-Ratsikas, Alexandros Hollender

Publication date 8 November 2022

Published in Artificial Intelligence (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

computational complexityquery complexityfair divisionconsensus-halvingRobertson-Webb

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Cites work

• scientific article; zbMATH DE number 3136641 (Why is no real title available?)
• scientific article; zbMATH DE number 1234106 (Why is no real title available?)
• scientific article; zbMATH DE number 1015852 (Why is no real title available?)
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• scientific article; zbMATH DE number 3097423 (Why is no real title available?)
• scientific article; zbMATH DE number 3102257 (Why is no real title available?)
• 2-D Tucker is PPA complete
• A Moment Problem in L 1 Approximation
• A Sperner lemma complete for PPA
• A discrete and bounded envy-free cake cutting protocol for four agents
• Algorithmic solutions for envy-free cake cutting
• An improved envy-free cake cutting protocol for four agents
• Approximating fair division with a limited number of cuts
• Bisection of Circle Colorings
• Cake cutting algorithms
• 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
• Contiguous cake cutting: hardness results and approximation algorithms
• Discrete fixed points: models, complexities, and applications
• Drei Sätze über die n-dimensionale euklidische Sphäre
• Fair Allocation of Indivisible Goods
• Fair Cake Division Under Monotone Likelihood Ratios
• Hardness results for consensus-halving
• Matching algorithmic bounds for finding a Brouwer fixed point
• Measure partitions using hyperplanes with fixed directions
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of cake cutting
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• Rental Harmony: Sperner's Lemma in Fair Division
• Settling the complexity of computing two-player Nash equilibria
• Simplotopal maps and necklace splitting
• Splitting necklaces
• Sur la division pragmatique
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• The complexity of computing a Nash equilibrium
• The complexity of gradient descent: CLS = PPAD ∩ PLS
• The complexity of splitting necklaces and bisecting ham sandwiches
• The relative complexity of NP search problems
• 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
• White-box vs. black-box complexity of search problems: Ramsey and graph property testing

Cited in

(1)

• Consensus-Halving: Does It Ever Get Easier?

This page was built for publication: Two's company, three's a crowd: consensus-halving for a constant number of agents

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