Aggregating multi-valued CP-nets: a CSP-based approach

Minyi Li, Quoc Bao Vo, Ryszard Kowalczyk

Research output: Contribution to journalArticleResearchpeer-review

11 Citations (Scopus)

Abstract

We develop a framework for preference aggregation in multi-attribute, multi-valued domains, where agents’ preferences are represented by Conditional Preference Networks (CP-nets). Most existing work either does not consider computational requirements, or depends on the strong assumption that the agents can express their preferences by acyclic CP-nets that are compatible with a common order on the variables. In this paper, we focus on majoritarian aggregation of CP-nets. We propose a general approach that allows for aggregating preferences when the expressed CP-nets are not required to be acyclic. Moreover, there is no requirement for any common structure among the agents’ CP-nets. The proposed approach computes a set of locally winning alternatives through the reduction to a constraint satisfaction problem. We present results of experiments that demonstrate the efficiency and scalability of our approach. Through comprehensive experiments we also investigate the distributions of the numbers of locally winning alternatives with different CP-net structures, with varying domain sizes and varying numbers of variables and agents.
Original languageEnglish
Pages (from-to)107-140
Number of pages34
JournalJournal of Heuristics
Volume21
Issue number1
DOIs
Publication statusPublished - 2015
Externally publishedYes

Keywords

  • Preference aggregation
  • CP-nets
  • Majority rule
  • Local condorcet winner
  • Necessary/possible condorcet winner

Cite this