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

Minyi Li, Quoc Bao Vo, Ryszard Kowalczyk

Research output: Contribution to journalArticleResearchpeer-review

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

Li, Minyi ; Vo, Quoc Bao ; Kowalczyk, Ryszard. / Aggregating multi-valued CP-nets : a CSP-based approach. In: Journal of Heuristics. 2015 ; Vol. 21, No. 1. pp. 107-140.
@article{fdef6acf920a430b86abbc12e3889c4a,
title = "Aggregating multi-valued CP-nets: a CSP-based approach",
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.",
keywords = "Preference aggregation, CP-nets, Majority rule, Local condorcet winner, Necessary/possible condorcet winner",
author = "Minyi Li and Vo, {Quoc Bao} and Ryszard Kowalczyk",
year = "2015",
doi = "10.1007/s10732-014-9276-8",
language = "English",
volume = "21",
pages = "107--140",
journal = "Journal of Heuristics",
issn = "1381-1231",
publisher = "Springer-Verlag London Ltd.",
number = "1",

}

Aggregating multi-valued CP-nets : a CSP-based approach. / Li, Minyi; Vo, Quoc Bao; Kowalczyk, Ryszard.

In: Journal of Heuristics, Vol. 21, No. 1, 2015, p. 107-140.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Aggregating multi-valued CP-nets

T2 - a CSP-based approach

AU - Li, Minyi

AU - Vo, Quoc Bao

AU - Kowalczyk, Ryszard

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Preference aggregation

KW - CP-nets

KW - Majority rule

KW - Local condorcet winner

KW - Necessary/possible condorcet winner

U2 - 10.1007/s10732-014-9276-8

DO - 10.1007/s10732-014-9276-8

M3 - Article

VL - 21

SP - 107

EP - 140

JO - Journal of Heuristics

JF - Journal of Heuristics

SN - 1381-1231

IS - 1

ER -