Approximation Ratio for Preference Aggregation Using Tree CP-Nets

Aggregating preferences of multiple entities is a problem that has been studied in various models of preference representation, including Conditional Preference Networks (CP-nets). Since optimal aggregation of CP-nets (for a specific natural choice of objective function) is known to require exponential time, efficient approximation algorithms have been proposed in the literature, yet with very limited results on the corresponding approximation ratio. In this paper, we show that a very simple and efficient method yields a 4 3 -approximation for aggregating CP-nets from a proper superset of the set of all tree CP-nets—a well-studied class of CP-nets of relevance to many applications.

Authors

• Abu Mohammad Hammad Ali University of Regina
• Daniel Ogundare University of Regina
• Boting Yang University of Regina
• Sandra Zilles University of Regina, Canada

Keywords

• Conditional Preference Networks
• Preference Aggregation