Abstract
In voting theory, impossibility results and computational hardness results are often circumvented by
recognising that voters’ preferences are not arbitrary, but lie within a restricted domain. Uncovering the structure of the underlying domain often
provides useful insights about the nature of the alternative space, and may be helpful in identifying
a collective choice. Preferences single-peaked on
a tree are an example of a relatively broad domain
that nonetheless exhibits several desirable properties. We consider the setting where agents’ preferences are independently sampled from rankings
that are single-peaked on a given tree, and study the
problem of reliably identifying the tree that generated the observed votes. We test our algorithm
empirically; to this end, we develop a procedure
to uniformly sample preferences that are singlepeaked on a given tree