English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We introduce and study the weakly single-crossing domain on trees which is ageneralization of the well-studied single-crossing domain in social choicetheory. We design a polynomial-time algorithm for recognizing preferenceprofiles which belong to this domain. We then develop an efficient elicitationalgorithm for this domain which works even if the preferences can be accessedonly sequentially and the underlying single-crossing tree structure is notknown beforehand. We also prove matching lower bound on the query complexity ofour elicitation algorithm when the number of voters is large compared to thenumber of candidates. We also prove a lower bound of $\Omega(m^2\log n)$ on thenumber of queries that any algorithm needs to ask to elicit single crossingprofile when random queries are allowed. This resolves an open question in anearlier paper and proves optimality of their preference elicitation algorithmwhen random queries are allowed.

Recognizing and Eliciting Weakly Single Crossing Profiles on Trees