We introduce and study the weakly single-crossing domain on trees which is a generalization of the well-studied single-crossing domain in social choice theory. We design a polynomial-time algorithm for recognizing preference profiles which belong to this domain. We then develop an efficient elicitation algorithm for this domain which works even if the preferences can be accessed only sequentially and the underlying single-crossing tree structure is not known beforehand. We also prove matching lower bound on the query complexity of our elicitation algorithm when the number of voters is large compared to the number of candidates. We also prove a lower bound of $\Omega(m^2\log n)$ on the number of queries that any algorithm needs to ask to elicit single crossing profile when random queries are allowed. This resolves an open question in an earlier paper and proves optimality of their preference elicitation algorithm when random queries are allowed.

翻译：我们引入并研究树木上薄弱的单跨域,这是社会选择理论中研究周密的单跨域的概括性。 我们设计了一种多元时间算法,用于确认属于此域的优惠概况。 然后我们为此域开发一种有效的引算法, 即使只能按顺序获得偏好, 且其基础的单跨树结构事先并不为人知。 我们还证明, 当选民人数与候选人人数相比较大时, 我们的引算法的查询复杂性比我们更低。 我们还证明, 在允许随机查询时, 任何算法需要查询的单交叉剖度的查询数量上, 也比 $\ Omega(m%2\log n) 的比值要低。 这在早先的文件中解决了一个开放问题, 并证明在允许随机查询时, 他们的优先引算法最优化 。