Filos-Ratsikas, Aris
[VerfasserIn];
Frederiksen, Søren Kristoffer Stiil
[VerfasserIn];
Goldberg, Paul W.
[VerfasserIn];
Zhang, Jie
[VerfasserIn]
;
Aris Filos-Ratsikas and Søren Kristoffer Stiil Frederiksen and Paul W. Goldberg and Jie Zhang
[MitwirkendeR]
Beteiligte:
Filos-Ratsikas, Aris
[VerfasserIn];
Frederiksen, Søren Kristoffer Stiil
[VerfasserIn];
Goldberg, Paul W.
[VerfasserIn];
Zhang, Jie
[VerfasserIn]
Erschienen:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
The Consensus-halving problem is the problem of dividing an object into two portions, such that each of n agents has equal valuation for the two portions. We study the epsilon-approximate version, which allows each agent to have an epsilon discrepancy on the values of the portions. It was recently proven in [Filos-Ratsikas and Goldberg, 2018] that the problem of computing an epsilon-approximate Consensus-halving solution (for n agents and n cuts) is PPA-complete when epsilon is inverse-exponential. In this paper, we prove that when epsilon is constant, the problem is PPAD-hard and the problem remains PPAD-hard when we allow a constant number of additional cuts. Additionally, we prove that deciding whether a solution with n-1 cuts exists for the problem is NP-hard.