Majority-rule-based preference aggregation on multi-attribute domains with CP-nets

Minyi Li, Quoc Bao Vo, Ryszard Kowalczyk

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

12 Citations (Scopus)

Abstract

This paper studies the problem of majority-rule-based collective decision-making where the agents’ preferences are represented by CP-nets (Conditional Preference Networks). As there are exponentially many alternatives, it is impractical to reason about the individual full rankings over the alternative space and apply majority rule directly. Most existing works either do not consider computational requirements, or depend on a strong assumption that the agents have acyclic CP-nets that are compatible with a common order on the variables. To this end, this paper proposes an efficient SAT-based approach, called MajCP (Majority-rule-based collective decision-making with CP-nets), to compute the majority winning alternatives. Our proposed approach only requires that each agent submit a CP-net; the CP-net can be cyclic, and it does not need to be any common structures among the agents’ CP-nets. The experimental results presented in this paper demonstrate that the proposed approach is computationally efficient. It offers several orders of magnitude improvement in performance over a Brute-force algorithm for large numbers of variables.
Original languageEnglish
Title of host publicationAAMAS 2011
Subtitle of host publicationProceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems
EditorsKagan Tumer, Pinar Yolum, Liz Sonenberg, Peter Stone
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems
Pages659-666
Number of pages8
VolumeIII
ISBN (Print)9780982657171
Publication statusPublished - 2011
Externally publishedYes
EventInternational Conference on Autonomous Agents and Multiagent Systems - Taipei, Taiwan
Duration: 2 May 20116 May 2011

Conference

ConferenceInternational Conference on Autonomous Agents and Multiagent Systems
CountryTaiwan
CityTaipei
Period2/05/116/05/11

Keywords

  • CP-nets
  • Voting
  • Preference aggregation
  • Majority rule

Cite this

Li, M., Vo, Q. B., & Kowalczyk, R. (2011). Majority-rule-based preference aggregation on multi-attribute domains with CP-nets. In K. Tumer, P. Yolum, L. Sonenberg, & P. Stone (Eds.), AAMAS 2011: Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (Vol. III, pp. 659-666). International Foundation for Autonomous Agents and Multiagent Systems.