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/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

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

Zendy Tools

Zendy Open

Combinatorial preference aggregation has many applications in AI. Given theexponential nature of these preferences, compact representations are needed and($m$)CP-nets are among the most studied ones. Sequential and global voting aretwo ways to aggregate preferences over CP-nets. In the former, preferences areaggregated feature-by-feature. Hence, when preferences have specific featuredependencies, sequential voting may exhibit voting paradoxes, i.e., it mightselect sub-optimal outcomes. To avoid paradoxes in sequential voting, one hasoften assumed the $\mathcal{O}$-legality restriction, which imposes a sharedtopological order among all the CP-nets. On the contrary, in global voting,CP-nets are considered as a whole during preference aggregation. For thisreason, global voting is immune from paradoxes, and there is no need to imposerestrictions over the CP-nets' topological structure. Sequential voting over$\mathcal{O}$-legal CP-nets has extensively been investigated. On the otherhand, global voting over non-$\mathcal{O}$-legal CP-nets has not carefully beenanalyzed, despite it was stated in the literature that a theoretical comparisonbetween global and sequential voting was promising and a precise complexityanalysis for global voting has been asked for multiple times. In quite fewworks, very partial results on the complexity of global voting over CP-netshave been given. We start to fill this gap by carrying out a thoroughcomplexity analysis of Pareto and majority global voting over not necessarily$\mathcal{O}$-legal acyclic binary polynomially connected (m)CP-nets. We settlethese problems in the polynomial hierarchy, and some of them in PTIME orLOGSPACE, whereas EXPTIME was the previously known upper bound for most ofthem. We show various tight lower bounds and matching upper bounds for problemsthat up to date did not have any explicit non-obvious lower bound.

Complexity Results for Preference Aggregation over (m)CP-nets: Pareto and Majority Voting