# Approximation Algorithms for Preference Aggregation Using CP-Nets

arXiv: https://arxiv.org/abs/2312.09162 · HTML: https://mlsanity.com/paper/2312.09162/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 30 references that are in the map.
- First posted on arXiv 14 Dec 2023.

## Builds on (most cited first, 2 of 2)

- [Complexity Results for Preference Aggregation over (m)CP-nets: Pareto and Majority Voting](https://mlsanity.com/paper/1806.10018/) (2018)
- [Complexity of Judgment Aggregation](https://mlsanity.com/paper/1401.5863/) (2014)

## Abstract (arXiv)

This paper studies the design and analysis of approximation algorithms for aggregating preferences over combinatorial domains, represented using Conditional Preference Networks (CP-nets). Its focus is on aggregating preferences over so-called swaps, for which optimal solutions in general are already known to be of exponential size. We first analyze a trivial 2-approximation algorithm that simply outputs the best of the given input preferences, and establish a structural condition under which the approximation ratio of this algorithm is improved to 4/3. We then propose a polynomial-time approximation algorithm whose outputs are provably no worse than those of the trivial algorithm, but often substantially better. A family of problem instances is presented for which our improved algorithm produces optimal solutions, while, for any varepsilon, the trivial algorithm cannot/ attain a (2-varepsilon)-approximation. These results may lead to the first polynomial-time approximation algorithm that solves the CP-net aggregation problem for swaps with an approximation ratio substantially better than 2.