Optimal Decision Making with CP-nets and PCP-nets
"Explore optimal decision-making strategies using CP-nets and PCP-nets to address multi-issue voting challenges and compact preference languages. Learn about acyclic and cyclic CP-nets, winners in undominated scenarios, and the usefulness of PCP-nets in handling uncertain and dynamic preferences. Discover a quantitative approach to decision-making for loss minimization and the main messages related to preferences and voting rules."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Optimal Decision Making Optimal Decision Making with CP with CP- -nets and PCP nets and PCP- -nets nets Sibel Adali, Sujoy Sikdar, Lirong Xia
Multi-Issue Voting ? issues Combinatorial preferences over decisions on all issues. { , } X { , } Main dishes (?) Wine (?) Challenges: Preference representation Computational Goal: Cater to people s preferences What is the best decision for all issues? How to compare two decisions?
Compact Preference Languages and CP-nets [Boutilier et al. 04] I prefer red wine to white wine with my meal, ceteris paribus, given that meat is served.
Winners are Undominated No other decision is preferred Acyclic CP-nets: Always exists Unique Cyclic CP-nets: ??? Doesn t always exist May not be unique
PCP-nets [Bigot et al. 13, Cornelio et al. 13] Induces CP-net w/ probability 0.7 0.6 0.7
PCP-nets are useful Uncertain preferences [Bigot et al. 13, Cornelio et al. 13] Dynamic preferences [Cornelio et al. 14] Aggregate CP-net profile as a single PCP-net [Cornelio et al. 14]
Previous Work Winner determination Common assumptions: Dependencies are acyclic All preferences have the same structure
Quantitative approach to decision making Loss Minimization Framework # (weakly) dominating decisions Optimal decision = Loss minimizing decision
Main messages Full generality w.r.t. preferences: Cyclic dependencies CP-net and PCP-net profiles Natural notions of loss Generalizes previous work New class of voting rules And axiomatic properties
Loss of a decision Inputs: (P)CP-net ? Decision ? Output: Loss ?(?, ?)
Natural loss functions 0-1 loss (?0 1) Is it dominated? Most probable optimal decision [Cornelio et al. 13] Neighborhood loss (??) # (weakly) dominating neighbors Local Condorcet winner [Conitzer et al. 11] Global loss (??) Total # dominating decisions ?0 1( , ) = 1 ??( , ) = 2 ??( , ) = 3
Computing the Loss ???? ??. ?0 1 ?? ?? Acyclic P (trivial) Cyclic P P coNP-hard coNP-hard
Computing the Optimal Decision for CP-nets Input: CP-net Output: Optimal decision = Loss minimizing decision ???? ??. ?0 1 ?? ?? Acyclic Cyclic P [Boutilier et al., 04] NP-complete P
Optimal Decision for PCP-nets ???? ??. ?0 1 Acyclic NP-complete, P for trees [Cornelio et al., 13] Cyclic NP-complete [Cornelio et al., 13] ?? NP-hard, P for trees* NP-hard ?? coNP-hard * Exponential in tree-width Using a variable-elimination algorithm
A new class of voting rules Input: CP-net profile ? Output: Decision for every issue ???? ??. ?0 1 Acyclic P Cyclic NP-complete ?? NP-complete P for shared tree dependency structure coNP-hard ??
Axiomatic Properties Anonymity Consistency Issue-wise neutrality Weak monotonicity Satisfied by every rule
Summary and Conclusions Quantitative approach to multi-issue voting Fully general: Cyclic dependencies CP-net and PCP-net profiles New loss minimization framework Natural loss functions New class of voting rules Identifying tractable sub-cases for optimal outcome of PCP-nets Large space of possible loss functions Good social choice normative properties Computationally tractable
