=Paper=
{{Paper
|id=Vol-3419/paper3
|storemode=property
|title=Pareto and Majority Voting in mCP-nets
|pdfUrl=https://ceur-ws.org/Vol-3419/paper3.pdf
|volume=Vol-3419
|authors=Thomas Lukasiewicz,Enrico Malizia
|dblpUrl=https://dblp.org/rec/conf/aiia/LukasiewiczM22
}}
==Pareto and Majority Voting in mCP-nets==
<pdf width="1500px">https://ceur-ws.org/Vol-3419/paper3.pdf</pdf>
<pre>
Pareto and Majority Voting in 𝑚CP-nets⋆
Thomas Lukasiewicz1,2 , Enrico Malizia3
1
  Department of Computer Science, University of Oxford, UK
2
  Institute of Logic and Computation, TU Wien, Austria
3
  DISI, University of Bologna, Italy


                                      Abstract
                                      Aggregating preferences over combinatorial domains has several applications in AI. Due to the exponen-
                                      tial 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.

                                      Keywords
                                      Combinatorial preferences, Preference aggregation, CP-nets, Majority voting, Computational complexity




1. Introduction
Managing and aggregating agent preferences have attracted extensive interest for their im-
portance in AI applications, such as recommender systems [2], product configuration [3],
planning [4], preference-based constraint satisfaction [5], preference-based query answer-
ing/information retrieval [6, 7, 8], and preference-based argumentations [9]. In computer
science, preference aggregation has often been based on social choice theory [10]. In this theory,
agents’ preferences are usually extensively represented. Although this is reasonable with a
small set of candidates, this is not feasible with combinatorial domains, i.e., when the set of
candidates, or outcomes, is the Cartesian product of finite-value domains for each of a set of
features [11, 12]. Combinatorial domains contain an exponential number of outcomes in the
number of features, and hence compact representations are needed [11, 12]. CP-nets [13] are
among the most studied of these representations, and have also been used in applications even
in learning scenarios [14, 15]. In CP-nets, vertices of a graph represent features, and an edge
from vertex 𝐴 to vertex 𝐵 models the influence of 𝐴’s value on the choice of 𝐵’s value. This
model captures conditional ceteris paribus preferences like “if the rest of the dinner is the same,
with a fish dish (𝐴’s value), I prefer a white wine (𝐵’s value)”.


Discussion Papers - 21st International Conference of the Italian Association for Artificial Intelligence (AIxIA 2022)
⋆
 This is an abridged version of the AIJ paper [1].
$ thomas.lukasiewicz@cs.ox.ac.uk (T. Lukasiewicz); enrico.malizia@unibo.it (E. Malizia)
 0000-0002-7644-1668 (T. Lukasiewicz); 0000-0002-6780-4711 (E. Malizia)
                                    © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
                      ceur-ws.org
    Workshop
    Proceedings
                  ISSN 1613-0073
                                    CEUR Workshop Proceedings (CEUR-WS.org)
                                                              (b) The CP-net’s induced prefer-
            (a) A CP-net modeling dinner preferences.             ence graph.
Figure 1: A CP-net and its preference graph.


Example 1. Assume that we want to model one’s preferences for a dinner with a main dish
and a wine [13]. In the CP-net in Figure 1a, an edge from vertex Main to vertex Wine models
that the value of feature Main influences the choice of the value of feature Wine: 𝑚 and 𝑓 are
the possible values of feature Main, denoting “𝑚eat” and “𝑓 ish”, respectively, while 𝑟 and 𝑤
are the possible values of feature Wine, denoting “𝑟ed (wine)” and “𝑤hite (wine)”, respectively.
The table associated with feature Wine specifies that when a meat dish is chosen, then a red
wine is preferred to a white one, and when a fish main is chosen, then a white wine is preferred
to a red wine. The table associated with feature Main indicates that a meat dish is preferred to
a fish one. These tables are called CP tables. A CP-net like this one can represent the conditional
ceteris paribus preference “given that the rest of the dinner does not change, with a meat dish
(Main’s value), I prefer a red wine (Wine’s value)”.
   Every CP-net has an associated induced preference graph [13], whose vertices are all the
possible outcomes of the domain, and whose edges connect outcomes differing on only one
value: there is a directed edge from an outcome to another if the latter is preferred to the former
according to the preferences encoded in the CP tables of the CP-net. Figure 1b shows the induced
preference graph of the CP-net in Figure 1a, having as vertices all the possible combinations
for the dinner, and there is, e.g., an edge from mw to mr , because the combination meat and
red wine is preferred to the combination meat and white wine. The preferences encoded in a
CP-net are the transitive closure of its induced preference graph. Intuitively, an outcome 𝛼 is
preferred to an outcome 𝛽 according to the preferences of a CP-net, if there is a directed path
from 𝛽 to 𝛼 in the induced preference graph, in which case 𝛼 is said to dominate 𝛽.              ◁

   CP-nets were also used to model preferences of groups, obtaining the multi-agent model
𝑚CP-nets [16], which is a profile of CP-nets, one for each agent. The preference semantics
of 𝑚CP-nets is defined via voting schemes: through its own individual CP-net, every agent
votes whether an outcome is preferred to another. Various voting schemes were proposed for
𝑚CP-nets [16, 17], and different voting schemes give rise to different dominance semantics for
𝑚CP-nets. In this paper, we consider Pareto and majority voting as they were defined in [16].

Example 2. Consider again the dinner scenario of Example 1, and assume that there are three
agents (Alice, Bob, and Chuck), expressing their preferences via CP-nets (see Figure 2). In Pareto
voting, an outcome 𝛼 dominates an outcome 𝛽, if all agents prefers 𝛼 to 𝛽. In majority voting,
an outcome 𝛼 dominates an outcome 𝛽, if the majority of agents prefers 𝛼 to 𝛽.
  The outcome fr is not Pareto optimal, because fr is Pareto dominated by 𝑚𝑟, i.e., the outcome
𝑚𝑟 is preferred to fr by all agents. The outcome 𝑚𝑤 is instead Pareto optimal, as there is no
Figure 2: Dinner preferences of Alice, Bob, and Chuck (in this order) modeled via CP-nets (above) and
their induced preference graphs (below).


outcome Pareto dominating 𝑚𝑤. Hence, from a Pareto perspective, 𝑚𝑤 is better than fr . The
outcome 𝑚𝑤, however, is not majority optimal, because 𝑚𝑟 majority dominates 𝑚𝑤 (Alice and
Chuck prefer 𝑚𝑟 to 𝑚𝑤). Conversely, 𝑚𝑟 is majority optimal, as there is no outcome majority
dominating 𝑚𝑟. Hence, from a majority perspective, 𝑚𝑟 is better than 𝑚𝑤. Moreover, again
according to the majority perspective, 𝑚𝑟 is a very good outcome, because 𝑚𝑟 is also majority
optimum, i.e., 𝑚𝑟 majority dominates all other outcomes. On the contrary, in this example,
there is no Pareto optimum outcome, i.e., there is no outcome Pareto dominating all the others.◁
   Unlike CP-nets, which were extensively analyzed, a precise complexity analysis of the group
dominance semantics in 𝑚CP-nets was missing for long time, as explicitly mentioned several
times in the literature [18, 19, 20, 17]. Our aim in this paper is to settle these problems in their
exact complexity classes, showing, if possible, completeness results.
   In particular, we focus on acyclic binary polynomially-connected 𝑚CP-nets (see Section 2
for these notions) built with standard CP-nets. Unlike what is often assumed in the literature,
in this work, we do not restrict the profiles of CP-nets to be 𝒪-legal, meaning that we do
not require that there is a topological ordering common to all the CP-nets of the profile. We
carry out a thorough complexity analysis for the (a) Pareto and (b) majority voting schemes, as
defined in [16], of deciding (1) dominance, (2) optimal and (3) optimum outcomes, and (4) the
existence of optimal and (5) optimum outcomes. Deciding the dominance for a voting scheme 𝑠
means deciding, given two outcomes, whether one dominates the other according to 𝑠. Deciding
whether an outcome is optimal or optimum for a voting scheme 𝑠 means deciding whether the
outcome is not dominated or dominates all others, respectively, according to 𝑠. Deciding the
existence of optimal and optimum outcomes is the natural extension of the previous problems.
A summary of the complexity results obtained is provided in Table 1.
   We obtain many intractability results, where the problems are put at various levels of the
Polynomial Hierarchy. Although intractability is usually “bad” news, these results are quite
interesting, as for most of these tasks only exp upper bounds were known in the literature to
date [16]. Even more interestingly, some of these problems are actually tractable, as they are in
p or even logspace, which is a huge leap from exp. The complexity results here shown can be
extended to wider notions of “compact representations” of preference profiles [1, 21].
Table 1
Summary of the complexity results. *A different proof is provided in [16].
                                     Problem                    Complexity
                                     Pareto-Dominance            np-complete




                          Pareto
                                     Is-Pareto-Optimal         co-np-complete
                                     Exists-Pareto-Optimal           Θ(1)*
                                     Is-Pareto-Optimum           in logspace
                                     Exists-Pareto-Optimum            in p
                          Majority   Majority-Dominance          np-complete
                                     Is-Majority-Optimal       co-np-complete
                                     Exists-Majority-Optimal    Σp2 -complete
                                     Is-Majority-Optimum        Πp2 -complete
                                     Exists-Majority-Optimum    Πp2 -hard, in dp2


  In Section 2, we provide definitions of the framework. In Section 3 and in Section 4 we discuss
our results for Pareto and majority voting, respectively. Full proof details are available in [1].


2. Preliminaries
CP-nets. A CP-net N is a triple ⟨𝒢N , Dom N , (CPT 𝐹N )𝐹 ∈ℱN ⟩, where 𝒢N = ⟨ℱN , ℰN ⟩ is a
directed graph whose vertices ℱN represent the features of the combinatorial domain, Dom N
is a function, and (CPT 𝐹N )𝐹 ∈ℱN is a family of functions. For a feature 𝐹 , Dom N associates a
(value) domain Dom N (𝐹 ) with 𝐹 , while CPT 𝐹N is the so called “CP table” of 𝐹 .
    Feature 𝐹 ’s domain is the set of values that 𝐹 may have in the outcomes. Here, we assume
features to be binary, i.e., each feature’s domain contains two values. We denote by 𝑓 and 𝑓 the
two values of 𝐹 . For a feature set 𝒮 ⊆ ℱN , Dom N (𝒮) = ×𝐹 ∈𝒮 Dom N (𝐹 ). An outcome is an
element of the set 𝒪N = Dom N (ℱN ). For a feature 𝐹 ∈ ℱN and an outcome 𝛼, 𝛼[𝐹 ] is 𝐹 ’s
value in 𝛼. For a feature set 𝒮 ⊆ ℱN and an outcome 𝛼, 𝛼[𝒮] is the projection of 𝛼 over 𝒮.
    CP tables encode preferences over feature values. The CP table of feature 𝐹 has a row for
any possible combination of values of all the parent features of 𝐹 in 𝒢N ; in each row there
is a total order over Dom N (𝐹 ). This order encodes agent’s preferences for 𝐹 ’s values when
specific values of 𝐹 ’s parents are considered: 𝑓 ≻ 𝑓 denotes 𝑓 being preferred to 𝑓 . If 𝐹 has
no parents, its CP table has only one row with a total order over Dom N (𝐹 ). We denote by
‖N ‖ the size of CP-net N , i.e., the space in terms of bits required to represent the whole net N
(including, features, links, feature domains, and CP tables).
    CP-nets’ preference semantics is based on “improving flips”. Let 𝐹 be a feature, and let 𝛼, 𝛽
be two outcomes differing only on 𝐹 ’s value. Flipping 𝐹 from 𝛼[𝐹 ] to 𝛽[𝐹 ] is an improving flip
iff, in the row of 𝐹 ’s CP table associated with the values in 𝛼 of the parents of 𝐹 , 𝛽[𝐹 ] ≻ 𝛼[𝐹 ].
Outcome 𝛽 is preferred to 𝛼, or 𝛽 dominates 𝛼 (in N ), denoted 𝛽 ≻N 𝛼, iff there is a sequence
of improving flips from 𝛼 to 𝛽, otherwise 𝛽 does not dominate 𝛼, denoted 𝛽 ̸≻N 𝛼; 𝛽 and 𝛼
are incomparable, denoted 𝛽 ◁▷N 𝛼, iff 𝛽 ̸≻N 𝛼 and 𝛼 ̸≻N 𝛽.
    A CP-net N is binary iff all its features are binary; N is singly connected iff, for any two
features 𝐺 and 𝐹 of N , there is at most one path from 𝐺 to 𝐹 in 𝒢N . A class F of CP-nets is
polynomially-connected iff there exists a polynomial 𝑝 such that, for any CP-net N ∈ F and for
any two features 𝐺 and 𝐹 of N , there are at most 𝑝(‖N ‖) distinct paths from 𝐺 to 𝐹 in 𝒢N . A
CP-net N is acyclic iff 𝒢N is acyclic. Acyclic CP-nets N have a unique optimum outcome oN ,
dominating all others, that can be computed in polynomial time [13]. Unless stated otherwise,
we consider acyclic binary CP-nets.
𝑚CP-nets. An 𝑚CP-net is a tuple of 𝑚 CP-nets defined over the same set of features having,
in turn, the same domain. The “𝑚” of an 𝑚CP-net is the agents’ number, so a 3CP-net is an
𝑚CP-net with 𝑚 = 3. Originally, partial CP-nets were allowed to constitute 𝑚CP-nets [16].
Here, we assume only standard CP-nets in 𝑚CP-nets, and CP-nets do not need to be 𝒪-legal
(i.e., we de not assume that the CP-nets of an 𝑚CP-net have a common topological ordering).
𝑚CP-nets’ semantics is based on voting. Let ℳ = ⟨N1 , . . . , N𝑚 ⟩ be an 𝑚CP-net, and let 𝛼, 𝛽
                               ≻                              ≺
be two outcomes. The sets 𝑆ℳ      (𝛼, 𝛽) = {𝑖 | 𝛼 ≻N𝑖 𝛽}, 𝑆ℳ    (𝛼, 𝛽) = {𝑖 | 𝛼 ≺N𝑖 𝛽}, and
   ◁▷
𝑆ℳ (𝛼, 𝛽) = {𝑖 | 𝛼 ◁▷N𝑖 𝛽}, are the sets of agents preferring 𝛼 to 𝛽, preferring 𝛽 to 𝛼, and for
which 𝛼 and 𝛽 are incomparable, respectively. The dominance semantics considered are [16]:

Pareto: 𝛽 Pareto dominates 𝛼, denoted by 𝛽 ≻pℳ 𝛼, iff all the agents of ℳ prefer 𝛽 to 𝛼, i.e.,
       ≻
     |𝑆ℳ (𝛽, 𝛼)| = 𝑚.

Majority: 𝛽 majority dominates 𝛼, denoted by 𝛽 ≻maj ℳ 𝛼, iff the majority of the agents of ℳ
                            ≻             ≺             ◁▷ (𝛽, 𝛼)|.
    prefers 𝛽 to 𝛼, i.e., |𝑆ℳ (𝛽, 𝛼)| > |𝑆ℳ (𝛽, 𝛼)| + |𝑆ℳ

For a voting scheme 𝑠, an outcome 𝛼 is 𝑠 optimal in ℳ iff 𝛽 ̸≻sℳ 𝛼 for all 𝛽 ̸= 𝛼, whereas 𝛼 is
𝑠 optimum in ℳ iff 𝛼 ≻sℳ 𝛽 for all 𝛽 ̸= 𝛼. Optimum outcomes, if they exist, are unique.
   An 𝑚CP-net is acyclic, binary, and singly connected, iff all its CP-nets are acyclic, binary, and
singly connected, respectively. A class F of 𝑚CP-nets is polynomially-connected iff the set of
CP-nets constituting the 𝑚CP-nets in F is polynomially-connected. Unless stated otherwise,
𝑚CP-nets here considered are acyclic, binary, and belong to polynomially-connected classes.


3. Complexity of Pareto voting on 𝑚CP-nets
We now focus on Pareto voting. Being based on the concept of unanimity, an np witness for an
outcome Pareto dominating another outcome is the set of the witnesses of all agents preferring
one to the other (for the class of (𝑚)CP-nets here considered, dominance check is known to be
np-complete [13]). For the hardness, on 1CP-nets, ≻p and ≻ are equivalent.

Theorem 3. Let ℳ be an 𝑚CP-net, and let 𝛼, 𝛽 be two outcomes. Deciding whether 𝛽 ≻pℳ 𝛼 is
np-complete. Hardness holds even on 1CP-nets.

   Consider the problem of deciding whether a given outcome 𝛼 is Pareto optimal for a given
𝑚CP-net ℳ. We can disprove 𝛼 being Pareto optimal by guessing an outcome 𝛽 along with
the witness that 𝛽 ≻pℳ 𝛼, and checking the witness (in np, see Theorem 3). For the hardness, it
is possible to provide a reduction from unsatisfiability of 3CNF Boolean formulas.

Theorem 4. Let ℳ be an 𝑚CP-net, and let 𝛼 be an outcome. Deciding whether 𝛼 is Pareto
optimal in ℳ is co-np-complete. Hardness holds even on 2CP-nets.
   Deciding whether an 𝑚CP-net has a Pareto optimal outcome is trivial, because there is always
one. Indeed, if this were not the case, then the optimal outcomes of the single CP-nets would be
dominated by some other outcome, which would be a contradiction. An 𝑚CP-net has a Pareto
optimum outcome iff all its CP-nets have the very same individual optimal outcome (that is
also Pareto optimum). Indeed, to be Pareto optimum, an outcome has to dominate all other
outcomes in all the CP-nets of the 𝑚CP-net: this property is satisfied only by an outcome that is
the optimum in all the CP-nets of the 𝑚CP-net. By combining this with the fact that checking
the optimality of an outcome in a CP-net is in logspace [1], we can state the following.
Theorem 5. Let ℳ be an 𝑚CP-net. Deciding whether an outcome 𝛼 is Pareto optimum in ℳ is
in logspace; deciding whether ℳ has a Pareto optimum outcome is in p.


4. Complexity of majority voting on 𝑚CP-nets
In this section, we deal with majority voting. It is possible to design four different acyclic binary
singly-connected CP-nets with the following dominance relationships: 𝑎𝑏 ≻N1 𝑎𝑏 ≻N1 𝑎𝑏 ≻N1
𝑎𝑏; 𝑎𝑏 ≻N2 𝑎𝑏 ≻N2 𝑎𝑏 ≻N2 𝑎𝑏; 𝑎𝑏 ≻N3 𝑎𝑏 ≻N3 𝑎𝑏 ≻N3 𝑎𝑏; and 𝑎𝑏 ≻N4 𝑎𝑏 ≻N4 𝑎𝑏 ≻N4 𝑎𝑏.
Interestingly, the 4CP-net constituted by the four above nets do not have majority optimal and
optimum outcomes. Therefore, we can state the following.
Theorem 6. There are acyclic binary singly-connected 𝑚CP-nets not having majority optimal
and optimum outcomes.
   Let us now focus on majority dominance. Observe that 𝛽 ≻maj              ≻            𝑚
                                                                ℳ 𝛼 iff |𝑆ℳ (𝛽, 𝛼)| > 2 . Hence,
a certificate consists in the witnesses of at least 𝑚
                                                    2 agents preferring 𝛽 to 𝛼 (which is in np; see
above). On the hardness side, on 1CP-nets, ≻maj equals ≻ (which is np-hard; see above).
Theorem 7. Let ℳ be an 𝑚CP-net, and let 𝛼, 𝛽 be two outcomes. Deciding whether 𝛽 ≻maj
                                                                                  ℳ 𝛼 is
np-complete. Hardness holds even on 1CP-nets.
  For the majority optimal problem, to test that an outcome 𝛼 is not majority optimal, we
guess an outcome 𝛽 and the witness of 𝛽 ≻maj
                                         ℳ 𝛼 (in np, see Theorem 7). For the hardness, on
2CP-nets, ≻ maj      p
                and ≻ are equivalent.
Theorem 8. Let ℳ be an 𝑚CP-net. Deciding whether an outcome 𝛼 is a majority optimal in ℳ
is co-np-complete. Hardness holds even on 2CP-nets.
   We now focus on deciding the existence of majority optimal outcomes. We can test in Σp2
that ℳ has a majority optimal outcome by guessing an outcome 𝛼 (in np), and checking that 𝛼
is majority optimal (in co-np, see Theorem 8). To prove the respective hardness, an involved
construction showing a reduction from QBF is required.
Theorem 9. Let ℳ be an 𝑚CP-net. Deciding whether ℳ has a majority optimal outcome is
Σp2 -complete. Hardness holds even on 6CP-nets.
   Consider the problem of deciding whether an outcome is majority optimum. We can test in Σp2
that 𝛼 is not majority optimum by guessing an outcome 𝛽 (in np) and checking that 𝛼 ̸≻maj
                                                                                        ℳ 𝛽
(in co-np, see Theorem 7). The hardness proof uses similar ideas to those in Theorem 9.
Theorem 10. Let ℳ be an 𝑚CP-net. Deciding whether an outcome 𝛼 is majority optimum in ℳ
is Πp2 -complete. Hardness holds even on 3CP-nets.
   We now deal with the problem of deciding the existence for an 𝑚CP-net of a majority
optimum outcome. First, observe that an outcome, to be majority optimum, must also be
majority optimal. Notice that, when the majority optimum exists, then it is the only majority
optimal outcome. For this reason, an 𝑚CP-net ℳ has a majority optimum outcome if and only
if ℳ has majority optimal outcomes and it is not true that ℳ has majority optimal outcomes
that are not also majority optimum. Hence, two tasks need to be solved to decide whether an
𝑚CP-net ℳ has a majority optimum outcome: (1) decide whether ℳ has majority optimal
outcomes; and (2) decided whether ℳ does not have majority optimal outcomes that are not
also optimum. We already know that the complexity of task (1) is in Σp2 (see Theorem 9). The
complexity of task (2) can be shown in Πp2 . Indeed, solving the complement of task (2), i.e.,
deciding whether ℳ has majority optimal outcomes that are not also optimum, can be shown
in Σp2 . First, we guess two different outcomes 𝛼 and 𝛽 (feasible in np). Then, through a co-np
oracle call, we check that 𝛼 is actually majority optimal (see Theorem 4), then through another
oracle call in co-np, we check that 𝛼 ̸≻maj
                                          𝑀 𝛽 (see Theorem 7).
   By combining the complexity of these two tasks follows that deciding whether an 𝑚CP-net
has a majority optimum outcome is in dp2 . The Πp2 -hardness of the problem can be shown by
inspection of the reduction for the hardness in Theorem 10.
Theorem 11. Let ℳ be an 𝑚CP-net. Deciding whether ℳ has a majority optimum outcome is
in dp2 and is Πp2 -hard. Hardness holds even on 3CP-nets.


5. Summary and outlook
We have carried out a thorough complexity analysis of the Pareto and majority semantics in
𝑚CP-nets. The various problems analyzed here have been put at various levels of the Polynomial
Hierarchy, and some of them are even tractable (in p or logspace). This work was extended
to consider also rank voting and relative majority voting [22, 23, 24], where to analyse the
complexity of the latter a novel characterization of the complexity class Θp2 was needed [25].
The semantics intractability of (𝑚)CP-nets has encouraged research to individuate tractable
approximate algorithms for CP-nets dominance [26].
   There are various possible directions for further research. Having constraints on the feasibility
of outcomes is an interesting direction of investigation. Without any constraint, CP-nets model
agents’ preferences when it is assumed that all outcomes are attainable. However, this is not
always the case. For example, to decide whether an outcome is majority dominated by another,
we should check that the latter is feasible. A similar idea characterized the solution concepts in
NTU cooperative games defined via constraints [27, 28]. This approach could be merged with
the definition of constrained CP-nets [5, 29]. CP-nets offer a rather flexible formalism to express
preferences, and in fact it would be interesting to extend the preference model adopted in the
AI explanation framework [8] to something capable of leveraging the representational power of
CP-nets, and extend this to other explanation frameworks [30, 31, 32]. The model of CP-nets
could also be extended to hypergraphs [33, 34] by following the intuitions provided in [35],
where ceteribus paribus preferences are put in relationship with hypergraphs transversals.
Acknowledgments
This work was supported by UK EPSRC grants EP/J008346/1, EP/L012138/1, and EP/M025268/1,
the Alan Turing Institute under the EPSRC grant EP/N510129/1, and the AXA Research Fund.


References
 [1] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (𝑚)CP-nets:
     Pareto and majority voting, Artif. Intell. 272 (2019) 101–142.
 [2] F. Ricci, L. Rokach, B. Shapira (Eds.), Recommender Systems Handbook, 2nd ed., Springer,
     New York, NY, USA, 2015.
 [3] R. I. Brafman, C. Domshlak, TCP-nets for preference-based product configuration, in:
     Proc. of the ECAI 2002 Workshop on Configuration, 2002, pp. 101–106.
 [4] R. I. Brafman, Y. Chernyavsky, Planning with goal preferences and constraints, in: Proc.
     of ICAPS, 2005, pp. 182–191.
 [5] C. Boutilier, R. I. Brafman, C. Domshlak, H. H. Hoos, D. Poole, Preference-based constrained
     optimization with CP-nets, Comput. Intell. 20 (2004) 137–157.
 [6] T. Di Noia, T. Lukasiewicz, M. V. Martinez, G. I. Simari, O. Tifrea-Marciuska, Combining
     existential rules with the power of CP-theories, in: Proc. of IJCAI, 2015, pp. 2918–2925.
 [7] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Preference-based inconsistency-tolerant
     query answering under existential rules, Artif. Intell. 312 (2022) art. no. 103772.
 [8] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavičius, Preferred explanations
     for ontology-mediated queries under existential rules, in: Proc. of AAAI, 2021, pp. 6262–
     6270.
 [9] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On preferences and priority rules in abstract
     argumentation, in: Proc. of IJCAI, 2022, pp. 2517–2524.
[10] F. Brandt, V. Conitzer, U. Endriss, J. Lang, A. D. Procaccia (Eds.), Handbook of Computa-
     tional Social Choice, Cambridge University Press, New York, NY, USA, 2016.
[11] J. Lang, Logical preference representation and combinatorial vote, Ann. Math Artif. Intel.
     42 (2004) 37–71.
[12] J. Lang, L. Xia, Voting in combinatorial domains, in: F. Brandt, V. Conitzer, U. Endriss,
     J. Lang, A. D. Procaccia (Eds.), Handbook of Computational Social Choice, Cambridge
     University Press, New York, NY, USA, 2016, pp. 197–222.
[13] C. Boutilier, R. I. Brafman, C. Domshlak, H. H. Hoos, D. Poole, CP-nets: A tool for
     representing and reasoning with conditional ceteris paribus preference statements, J. Artif.
     Intell. Res. 21 (2004) 135–191.
[14] J. T. Guerin, T. E. Allen, J. Goldsmith, Learning CP-net preferences online from user
     queries, in: Proc. of ADT, 2013, pp. 208–220.
[15] T. E. Allen, C. Siler, J. Goldsmith, Learning tree-structured CP-nets with local search, in:
     Proc. of FLAIRS, 2017, pp. 8–13.
[16] F. Rossi, K. B. Venable, T. Walsh, 𝑚CP Nets: Representing and reasoning with preferences
     of multiple agents, in: Proc. of AAAI, 2004, pp. 729–734.
[17] M. Li, Q. B. Vo, R. Kowalczyk, Aggregating multi-valued CP-nets: A CSP-based approach,
     J. Heuristics 21 (2015) 107–140.
[18] J. Lang, Vote and aggregation in combinatorial domains with structured preferences, in:
     Proc. of IJCAI, 2007, pp. 1366–1371.
[19] M. Li, Q. B. Vo, R. Kowalczyk, An effcient majority-rule-based approach for collective
     decision making with CP-nets, in: Proc. of KR, 2010, pp. 578–580.
[20] M. Li, Q. B. Vo, R. Kowalczyk, An efficient procedure for collective decision-making with
     CP-nets, in: Proc. of ECAI, 2010, pp. 375–380.
[21] G. Greco, E. Malizia, L. Palopoli, F. Scarcello, The complexity of the nucleolus in compact
     games, ACM Trans. Comput. Theory 7 (2014) 3:1–3:52.
[22] T. Lukasiewicz, E. Malizia, On the complexity of 𝑚CP-nets, in: Proc. of AAAI, 2016, pp.
     558–564.
[23] E. Malizia, More complexity results about reasoning over (𝑚)CP-nets, in: Proc. of AAMAS,
     2018, pp. 1540–1548.
[24] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (𝑚)CP-nets:
     Max and rank voting, Artif. Intell. 303 (2022) art. no. 103636.
[25] T. Lukasiewicz, E. Malizia, A novel characterization of the complexity class Θ𝑃𝑘 based on
     counting and comparison, Theor. Comput. Sci. 694 (2017) 21–33.
[26] T. E. Allen, J. Goldsmith, H. E. Justice, N. Mattei, K. Raines, Uniform random generation
     and dominance testing for CP-nets, J. Artif. Intell. Res. 59 (2017) 771–813.
[27] E. Malizia, L. Palopoli, F. Scarcello, Infeasibility certificates and the complexity of the core
     in coalitional games, in: Proc. of IJCAI, 2007, pp. 1402–1407.
[28] G. Greco, E. Malizia, L. Palopoli, F. Scarcello, Non-transferable utility coalitional games
     via mixed-integer linear constraints, J. Artif. Intell. Res. 38 (2010) 633–685.
[29] S. D. Prestwich, F. Rossi, K. B. Venable, T. Walsh, Constraint-based preferential optimization,
     in: Proc. of AAAI, 2005, pp. 461–466.
[30] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Explanations for ontology-
     mediated query answering in description logics, in: Proc. of ECAI, 2020, pp. 672–679.
[31] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for inconsistency-tolerant query
     answering under existential rules, in: Proc. of AAAI, 2020, pp. 2909–2916.
[32] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for negative query answers under
     inconsistency-tolerant semantics, in: Proc. of IJCAI, 2022, pp. 2705–2711.
[33] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem
     through logic, in: Proc. of LICS, 2014, pp. 43:1–43:10.
[34] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem
     through logic, SIAM J. Comput. 47 (2018) 456–492.
[35] S. Obiedkov, Parameterized ceteris paribus preferences over atomic conjunctions under
     conservative semantics, Theor. Comput. Sci. 658 (2017) 375–390.

</pre>