  In multiagent systems, we often have a set of agents each of which have a
preference ordering over a set of items and one would like to know these
preference orderings for various tasks, for example, data analysis, preference
aggregation, voting etc. However, we often have a large number of items which
makes it impractical to ask the agents for their complete preference ordering.
In such scenarios, we usually elicit these agents' preferences by asking (a
hopefully small number of) comparison queries --- asking an agent to compare
two items. Prior works on preference elicitation focus on unrestricted domain
and the domain of single peaked preferences and show that the preferences in
single peaked domain can be elicited by much less number of queries compared to
unrestricted domain. We extend this line of research and study preference
elicitation for single peaked preferences on trees which is a strict superset
of the domain of single peaked preferences. We show that the query complexity
crucially depends on the number of leaves, the path cover number, and the
distance from path of the underlying single peaked tree, whereas the other
natural parameters like maximum degree, diameter, pathwidth do not play any
direct role in determining query complexity. We then investigate the query
complexity for finding a weak Condorcet winner for preferences single peaked on
a tree and show that this task has much less query complexity than preference
elicitation. Here again we observe that the number of leaves in the underlying
single peaked tree and the path cover number of the tree influence the query
complexity of the problem.
