| Summary: | <div>In the <span tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#x03B5;</mi></math>">ε</span>-<em>Consensus-Halving</em> problem, a fundamental problem in fair division, there are <span tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math>">n</span> agents with valuations over the interval [0,1], and the goal is to divide the interval into pieces and assign a label “<span tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mo>+</mo></math>">+</span>” or “<span tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#x2212;</mo></math>">−</span>” to each piece, such that every agent values the total amount of “<span tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mo>+</mo></math>">+</span>” and the total amount of “<span tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#x2212;</mo></math>">−</span>” almost equally. The problem was recently proven by Filos-Ratsikas and Goldberg [<em>Proceedings of the</em> 50<em>th Annual ACM Symposium on Theory of Computing,</em> 2018, pp. 51–64; <em>Proceedings of the</em> 51<em>st Annual ACM Symposium on Theory of Computing,</em> 2019, pp. 638–649] 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 [<em>Proceedings of the</em> 51<em>st Annual ACM Symposium on Theory of Computing</em>, 2019, pp. 638–649] to the case when agents have <em>piecewise uniform</em> valuations with only <em>two blocks</em>. We obtain this result via a new reduction, which is in fact conceptually much simpler than the corresponding one in Filos-Ratsikas and Goldberg [<em>Proceedings of the</em> 51<em>st Annual ACM Symposium on Theory of Computing,</em> 2019, pp. 638–649]. Then, we consider the case of <em>single-block (uniform) valuations</em> and provide a parameterized polynomial-time algorithm for solving <span tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#x03B5;</mi></math>">ε</span>-<em>Consensus-Halving</em> for any <span tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#x03B5;</mi></math>">ε</span>, as well as a polynomial-time algorithm for <span tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#x03B5;</mi><mo>=</mo><mn>1</mn><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mn>2</mn></math>">ε=1/2</span>. Finally, an important application of our new techniques is the first hardness result for a generalization of Consensus-Halving, the Consensus-<span tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mi>k</mi></math>">1/k1</span>-Division problem [F. W. Simmons and F. E. Su, <em>Math. Social Sci.,</em> 45 (2003), pp. 15–25]. In particular, we prove that <span tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#x03B5;</mi></math>">ε</span>-Consensus-<span tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mn>3</mn></math>">1/3</span>-Division is PPAD-hard.</div>
|
|---|