Aggregating preferences over combinatorial domains has several applications in AI. Due to the exponential nature of combinatorial preferences, compact representations are needed, and CP-nets are among the most studied formalisms. 𝑚CP-nets are an intuitive formalism based on CP-nets to reason about preferences of groups of agents. The dominance semantics of 𝑚CP-nets is based on voting, and different voting schemes give rise to different dominance semantics for the group. Unlike CP-nets, which received an extensive complexity analysis, 𝑚CP-nets, as reported multiple times in the literature, lacked such a thorough characterization. In this paper, we start to fill this gap by carrying out a precise computational complexity analysis of Pareto and majority voting on acyclic binary polynomially-connected 𝑚CP-nets.
Pareto and Majority Voting in mCP-nets / Thomas Lukasiewicz; Enrico Malizia. - ELETTRONICO. - (2022), pp. 23-31. (Intervento presentato al convegno AIxIA 2022 tenutosi a Udine, Italy nel 28/11/2022 - 2/12/2022).
Pareto and Majority Voting in mCP-nets
Enrico Malizia
2022
Abstract
Aggregating preferences over combinatorial domains has several applications in AI. Due to the exponential nature of combinatorial preferences, compact representations are needed, and CP-nets are among the most studied formalisms. 𝑚CP-nets are an intuitive formalism based on CP-nets to reason about preferences of groups of agents. The dominance semantics of 𝑚CP-nets is based on voting, and different voting schemes give rise to different dominance semantics for the group. Unlike CP-nets, which received an extensive complexity analysis, 𝑚CP-nets, as reported multiple times in the literature, lacked such a thorough characterization. In this paper, we start to fill this gap by carrying out a precise computational complexity analysis of Pareto and majority voting on acyclic binary polynomially-connected 𝑚CP-nets.File | Dimensione | Formato | |
---|---|---|---|
mCP_Nets_Pareto_Majority_AIxIA_CEUR-WS.pdf
accesso aperto
Tipo:
Versione (PDF) editoriale
Licenza:
Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione
836.39 kB
Formato
Adobe PDF
|
836.39 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.