Consensus Halving for Sets of Items

07/14/2020
by   Paul W. Goldberg, et al.
0

Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work has shown that when the resource is represented by an interval, a consensus halving with at most n cuts always exists, but is hard to compute even for agents with simple valuation functions. In this paper, we study consensus halving in a natural setting where the resource consists of a set of items without a linear ordering. When agents have additive utilities, we present a polynomial-time algorithm that computes a consensus halving with at most n cuts, and show that n cuts are almost surely necessary when the agents' utilities are drawn from probabilistic distributions. On the other hand, we show that for a simple class of monotonic utilities, the problem already becomes PPAD-hard. Furthermore, we compare and contrast consensus halving with the more general problem of consensus k-splitting, where we wish to divide the resource into k parts in possibly unequal ratios, and provide some consequences of our results on the problem of computing small agreeable sets.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset