Complexity results for preference aggregation over (m)CP-nets: max and rank voting
Aggregating preferences over combinatorial domains has a plethora of applications in AI. Due to the exponential nature of combinatorial preferences, compact representations are needed, and conditional ceteris paribus preference networks (CP-nets) are among the most studied compact representation for...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2021
|
| _version_ | 1826308931349118976 |
|---|---|
| author | Lukasiewicz, T Malizia, E |
| author_facet | Lukasiewicz, T Malizia, E |
| author_sort | Lukasiewicz, T |
| collection | OXFORD |
| description | Aggregating preferences over combinatorial domains has a plethora of applications in AI. Due to the exponential nature of combinatorial preferences, compact representations are needed, and conditional ceteris paribus preference networks (CP-nets) are among the most studied compact representation formalisms. Unlike the problem of outcome dominance over individual CP-nets, which received an extensive complexity analysis in the literature, mCP-nets (and global voting/preference aggregation over CP-nets) lacked such a thorough complexity characterization, despite this being reported multiple times in the literature as an open problem. An initial complexity analysis for mCP-nets was carried out only recently, where Pareto and majority dominance semantics were studied. In this paper, we further explore the complexity of mCP-nets, giving a precise complexity analysis of the dominance semantics in mCP-nets when the max and rank voting schemes are considered. In particular, we show that deciding dominance under max voting is ΘP2-complete, while deciding optimal outcomes and their existence under max voting is complete for ΠP2 and ΣP3, respectively. We also show that, under max voting, deciding optimum outcomes is ΠP2-complete, and deciding their existence is ΠP2-hard and in ΣP3. As for rank voting, apart from deciding whether mCP-nets have rank optimal outcomes, which is a trivial problem, as all mCP-nets have rank optimal outcomes, all the other rank voting tasks considered are tractable and in P. Interestingly, we show here that these problems are not only in P, but also P-hard (and hence P-complete). Furthermore, we show that deciding whether mCP-nets have Pareto optimum outcomes, which was known to be feasible in polynomial time, is actually P-complete, as well as that various tasks for CP-nets are P-complete. These results provide interesting insights, as P-complete problems are (currently believed to be) inherently sequential, and hence they cannot benefit from highly parallel computations. |
| first_indexed | 2024-03-07T07:28:14Z |
| format | Journal article |
| id | oxford-uuid:fbe65799-19e2-4819-a9b0-0b3ada1aebae |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:28:14Z |
| publishDate | 2021 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:fbe65799-19e2-4819-a9b0-0b3ada1aebae2022-11-24T12:03:23ZComplexity results for preference aggregation over (m)CP-nets: max and rank votingJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:fbe65799-19e2-4819-a9b0-0b3ada1aebaeEnglishSymplectic ElementsElsevier2021Lukasiewicz, TMalizia, EAggregating preferences over combinatorial domains has a plethora of applications in AI. Due to the exponential nature of combinatorial preferences, compact representations are needed, and conditional ceteris paribus preference networks (CP-nets) are among the most studied compact representation formalisms. Unlike the problem of outcome dominance over individual CP-nets, which received an extensive complexity analysis in the literature, mCP-nets (and global voting/preference aggregation over CP-nets) lacked such a thorough complexity characterization, despite this being reported multiple times in the literature as an open problem. An initial complexity analysis for mCP-nets was carried out only recently, where Pareto and majority dominance semantics were studied. In this paper, we further explore the complexity of mCP-nets, giving a precise complexity analysis of the dominance semantics in mCP-nets when the max and rank voting schemes are considered. In particular, we show that deciding dominance under max voting is ΘP2-complete, while deciding optimal outcomes and their existence under max voting is complete for ΠP2 and ΣP3, respectively. We also show that, under max voting, deciding optimum outcomes is ΠP2-complete, and deciding their existence is ΠP2-hard and in ΣP3. As for rank voting, apart from deciding whether mCP-nets have rank optimal outcomes, which is a trivial problem, as all mCP-nets have rank optimal outcomes, all the other rank voting tasks considered are tractable and in P. Interestingly, we show here that these problems are not only in P, but also P-hard (and hence P-complete). Furthermore, we show that deciding whether mCP-nets have Pareto optimum outcomes, which was known to be feasible in polynomial time, is actually P-complete, as well as that various tasks for CP-nets are P-complete. These results provide interesting insights, as P-complete problems are (currently believed to be) inherently sequential, and hence they cannot benefit from highly parallel computations. |
| spellingShingle | Lukasiewicz, T Malizia, E Complexity results for preference aggregation over (m)CP-nets: max and rank voting |
| title | Complexity results for preference aggregation over (m)CP-nets: max and rank voting |
| title_full | Complexity results for preference aggregation over (m)CP-nets: max and rank voting |
| title_fullStr | Complexity results for preference aggregation over (m)CP-nets: max and rank voting |
| title_full_unstemmed | Complexity results for preference aggregation over (m)CP-nets: max and rank voting |
| title_short | Complexity results for preference aggregation over (m)CP-nets: max and rank voting |
| title_sort | complexity results for preference aggregation over m cp nets max and rank voting |
| work_keys_str_mv | AT lukasiewiczt complexityresultsforpreferenceaggregationovermcpnetsmaxandrankvoting AT maliziae complexityresultsforpreferenceaggregationovermcpnetsmaxandrankvoting |