Complexity Results for Preference Aggregation over (m)CP-nets: Pareto and Majority Voting
- Submitting institution
-
University of Exeter
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 1830
- Type
- D - Journal article
- DOI
-
10.1016/j.artint.2018.12.010
- Title of journal
- Artificial Intelligence
- Article number
- -
- First page
- 101
- Volume
- 272
- Issue
- -
- ISSN
- 0004-3702
- Open access status
- Compliant
- Month of publication
- January
- Year of publication
- 2019
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
-
- Citation count
- 2
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This work resolves a long standing open problem on the computational complexity of preference aggregation over combinatorial domains. CP-nets were proposed 2 decades ago to represent preferences over combinatorial domains, and preference aggregation over them was defined shortly after. A definitive answer on the complexity of preference aggregation over CP-nets according to global voting, was requested multiple times in the literature in the past years, and our paper presents the definitive solution to this problem. Preliminary results of this work were presented at the long-established and influential conference, AAAI in 2016.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -