Back to Search
Start Over
Consensus-Halving: Does It Ever Get Easier?
- Source :
- Filos-Ratsikas, A, Hollender, A, Sotiraki, K & Zampetakis, M 2023, ' Consensus-Halving: Does It Ever Get Easier? ', SIAM Journal on Computing, vol. 52, no. 2, pp. 563-602 . https://doi.org/10.1137/20M1387493, EC
- Publication Year :
- 2023
-
Abstract
- In the $\varepsilon$-Consensus-Halving problem, a fundamental problem in fair division, there are $n$ agents with valuations over the interval $[0,1]$, and the goal is to divide the interval into pieces and assign a label "$+$" or "$-$" to each piece, such that every agent values the total amount of "$+$" and the total amount of "$-$" almost equally. The problem was recently proven by Filos-Ratsikas and Goldberg [2019] to be the first "natural" complete problem for the computational class PPA, answering a decade-old open question. In this paper, we examine the extent to which the problem becomes easy to solve, if one restricts the class of valuation functions. To this end, we provide the following contributions. First, we obtain a strengthening of the PPA-hardness result of [Filos-Ratsikas and Goldberg, 2019], to the case when agents have piecewise uniform valuations with only two blocks. We obtain this result via a new reduction, which is in fact conceptually much simpler than the corresponding one in [Filos-Ratsikas and Goldberg, 2019]. Then, we consider the case of single-block (uniform) valuations and provide a parameterized polynomial time algorithm for solving $\varepsilon$-Consensus-Halving for any $\varepsilon$, as well as a polynomial-time algorithm for $\varepsilon=1/2$. Finally, an important application of our new techniques is the first hardness result for a generalization of Consensus-Halving, the Consensus-$1/k$-Division problem [Simmons and Su, 2003]. In particular, we prove that $\varepsilon$-Consensus-$1/3$-Division is PPAD-hard.<br />Journal version. Preliminary version appeared at EC '20
- Subjects :
- FOS: Computer and information sciences
General Computer Science
Computer science
TFNP
General Mathematics
0211 other engineering and technologies
Parameterized complexity
Class (philosophy)
0102 computer and information sciences
02 engineering and technology
Computational Complexity (cs.CC)
01 natural sciences
fair division
Reduction (complexity)
Computer Science - Computer Science and Game Theory
PPAD
Time complexity
Discrete mathematics
021103 operations research
consensus-halving
Computer Science - Computational Complexity
010201 computation theory & mathematics
Piecewise
Interval (graph theory)
PPA
Fair division
Computer Science and Game Theory (cs.GT)
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- Filos-Ratsikas, A, Hollender, A, Sotiraki, K & Zampetakis, M 2023, ' Consensus-Halving: Does It Ever Get Easier? ', SIAM Journal on Computing, vol. 52, no. 2, pp. 563-602 . https://doi.org/10.1137/20M1387493, EC
- Accession number :
- edsair.doi.dedup.....788596e2d3657f60e7651c0a1e1f286c