Approximation Algorithms for Preference Aggregation Using CP-Nets
This addresses the computational challenge of preference aggregation in AI and decision-making, offering incremental improvements for specific CP-net scenarios.
The paper tackles the problem of aggregating preferences over combinatorial domains using CP-nets, focusing on swaps where optimal solutions are exponentially large, and proposes a polynomial-time approximation algorithm that improves upon a trivial 2-approximation, achieving optimal solutions in some cases and potentially a ratio better than 2.
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 \emph{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 can\emph{not}\/ 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$.