Research map / Learning theory and algorithms / Submodular and game algorithms
Approximation Algorithms for Preference Aggregation Using CP-Nets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies approximation algorithms for aggregating CP-nets under the swap-disagreement objective, showing the best-input-CPT rule gives 4/3 under symmetry and a polynomial-time parent-set-based algorithm that is never worse and often much better.
Problem
Aggregating multiple acyclic CP-nets into one consensus CP-net under the swap-disagreement objective is intractable, since optimal solutions can be exponentially large.
Approach
Instead of outputting the best input CPT, for each input parent set compute the optimal CPT restricted to that parent set via majority voting per context, then output the best such candidate; analyze the trivial algorithm's ratio under a symmetry condition (4/3) and show a family where the new algorithm is optimal.
Key results
- Under symmetric CPTs with pairwise disjoint parent sets, the best input CPT is a 4/3-approximation (t>=3).
- For every epsilon>0 there are instances where the best input CPT has ratio >(2-epsilon), so the trivial bound 2 is tight.
- On the family T^{k,n} with 2<=k<=n-1, the parent-set algorithm outputs an optimal solution while the best input CPT has ratio at least 3/2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Select the best input CPT rather than an optimal aggregate | CPT aggregation · General problem instances | approximation ratio: 2; for every ε>0, some instances have ratio > (2-ε) | Mixed |
| Require symmetric input CPTs with pairwise disjoint parent sets | Best-input-CPT algorithm · CPT aggregation | approximation ratio: 2 -> 4/3 | Helped |
| Optimize the CPT while restricting its parent set to an input parent set | CPT aggregation algorithm · General problem instances | objective value | Helped |
| Optimize the aggregate over an input parent set instead of using an input CPT unchanged | CPT aggregation on T^{k,n} · T^{k,n} | approximation ratio: at least 3/2 -> 1 | Helped |
| Use an input CPT unchanged instead of an optimal aggregate | CPT aggregation on T^{k,n} · T^{k,n} | approximation ratio: at least 3/2 | Hurt |
| Use an input CPT unchanged instead of an optimal aggregate | CPT aggregation · Some general problem instances | approximation ratio: 2-ε | Hurt |
Surprising findings
- Optimal CP-net aggregation for swaps is intractable due to the number of input CPTs rather than the number of attributes.
Limitations
- Only CPTs for a fixed attribute are aggregated; complete CP-nets assumed.
- Approximation ratio of the parent-set algorithm in general remains open (conjectured 4/3 upper bound, no counterexample known).
- Analysis restricted to binary attributes and symmetric or special instance families.
Experimental setup
Metrics: approximation ratio swap disagreement objective
Baselines: best input CPT (trivial 2-approximation)
Builds on: CP-nets binary aggregation Ali et al. swap-disagreement objective
Closest papers by meaning
- Generating CP-Nets Uniformly at Random (AAAI 2016 · similarity 0.89)
- Fair Division via the Cake-Cutting Share (AAAI 2025 · similarity 0.84)
- Maximizing Nash Social Welfare under Two-Sided Preferences (AAAI 2024 · similarity 0.84)
- 1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations (AAAI 2024 · similarity 0.84)
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.84)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.