  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.
