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.
|Title of host publication||AAMAS 2011|
|Subtitle of host publication||Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems|
|Editors||Kagan Tumer, Pinar Yolum, Liz Sonenberg, Peter Stone|
|Publisher||International Foundation for Autonomous Agents and Multiagent Systems|
|Number of pages||8|
|Publication status||Published - 2011|
|Event||International Conference on Autonomous Agents and Multiagent Systems - Taipei, Taiwan|
Duration: 2 May 2011 → 6 May 2011
|Conference||International Conference on Autonomous Agents and Multiagent Systems|
|Period||2/05/11 → 6/05/11|
- Preference aggregation
- Majority rule
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.