# reasoning_with_pcpnets__ea8c584a.pdf

Journal of Artiﬁcial Intelligence Research 72 (2021) 1103-1161 Submitted 05/2021; published 11/2021

Reasoning with PCP-Nets

Cristina Cornelio C.CORNELIO@SAMSUNG.COM Samsung AI, Cambridge, United Kingdom

Judy Goldsmith GOLDSMIT@CS.UKY.EDU University of Kentucky, Lexington, KY, USA

Umberto Grandi UMBERTO.GRANDI@IRIT.FR Institut de Recherche en Informatique de Toulouse (IRIT) University of Toulouse, France

Nicholas Mattei NSMATTEI@TULANE.EDU Department of Computer Science Tulane University, New Orleans, LA, USA

Francesca Rossi FRANCESCA.ROSSI2@IBM.COM IBM Research, T.J. Watson Research Center Yorktown Heights, New York, USA

K. Brent Venable KVENABLE@TULANE.EDU IHMC and University of West Florida, Florida, USA

We introduce PCP-nets, a formalism to model qualitative conditional preferences with probabilistic uncertainty. PCP-nets generalise CP-nets by allowing for uncertainty over the preference orderings. We deﬁne and study both optimality and dominance queries in PCP-nets, and we propose a tractable approximation of dominance which we show to be very accurate in our experimental setting. Since PCP-nets can be seen as a way to model a collection of weighted CP-nets, we also explore the use of PCP-nets in a multi-agent context, where individual agents submit CP-nets which are then aggregated into a single PCP-net. We consider various ways to perform such aggregation and we compare them via two notions of scores, based on well known voting theory concepts. Experimental results allow us to identify the aggregation method that better represents the given set of CP-nets and the most efﬁcient dominance procedure to be used in the multi-agent context.

1. Introduction

Preferences are ubiquitous in our everyday life; whenever we make a decision we exploit our preferences over the candidate options. Moreover, if the decision is shared with others, we need to ﬁnd ways to reconcile the possibly conﬂicting preferences of all the involved decision makers (agents). No area of our lives is free from explicit or implicit preference modeling, reasoning, and aggregation. For this reason, the study of how to model and reason with preference plays such an important role in automated decision making, multi-agent systems and artiﬁcial intelligence broadly deﬁned, and many comprehensive surveys exist detailing this work, for example, Rossi, Venable, and Walsh (2011), F urnkranz and H ullermeier (2010), Brafman and Domshlak (2009), Chevaleyre, Endriss, Lang, and Maudet (2008), Pigozzi, Tsoukis, and Viappiani (2015) and Amor, Dubois, Gouider, and Prade (2016).

c 2021 AI Access Foundation. All rights reserved.

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

For many decision tasks that occur in, for example, e-commerce, web search, retailing, and personalized medicine, the number of options can outstrip an agent s ability to view and express opinions over all the available choices (Adomavicius & Kwon, 2015). Hence, it is desirable in these instances to have an efﬁcient formalism to model and reason with complex, interdependent preferences that are speciﬁed over decision features, rather than entire decisions. Consider for example expressing preferences over all cars vs. over car features such as make, model, engine, etc. The set of all cars has a combinatorial structure and grows very fast over the features, but preferences can and often are expressed over features, for example, I prefer red cars to blue cars. A number of compact preference representation languages have been developed in the literature to tackle the computational challenges arising from these scenarios; see the work of Amor et al. (2016) for a survey of compact graphical models. We mention speciﬁcally conditional preference structures (CP-nets) (Boutilier et al., 2004), soft constraints (Bistarelli et al., 1997; Rossi et al., 2011), and GAI-nets (Gonzales & Perny, 2004) as they have been used widely across computer science and other disciplines and possess complementary properties in terms of expressivity and reasoning efﬁciency.

Motivation and Semantics. In this paper we formalize and provide reasoning algorithms for Probabilistic Conditional Preference networks (PCP-nets). PCP-nets are a generalization of CP-nets (Boutilier et al., 2004) that allow for modeling qualitative conditional preference statements with probabilistic uncertainty (Cornelio et al., 2013; Bigot et al., 2013; Cornelio et al., 2014, 2015). We decided to generalize CP-nets since CP-nets are arguably quite natural and intuitive to use in many circumstances (Chevaleyre et al., 2011; Allen et al., 2015), and can be used in many applications such as recommendation engines (Pu et al., 2011), including recommendation systems over features (Adomavicius & Kwon, 2015) or requiring aggregation (Beliakov, Calvo, & James, 2015); preference reasoning under constraints and/or ethical principles (Loreggia et al., 2018b, 2018a, 2019; Rossi & Mattei, 2019), aggregating the preferences of multiple agents (Lang & Xia, 2009; Rossi et al., 2004; Xia et al., 2011), and allow for expressing complex preferences over features of a decision. In addition, there is experimental evidence that qualitative preferences may more accurately reﬂect humans preferences in uncertain information settings (Roth & Kagel, 1995; Allen et al., 2015). Often in real life the information is not complete, or not precise, or contains some level of uncertainty. In preference settings, an agent may be unsure about his preferences over certain items, or there could be noise due to lack of precision in the elicitation phase or in sensor collection, for example, a measurement error from remote sensors, or the uncertainty could come from aggregating the preferences of multiple agents. While CP-nets specify a preference ordering over the values of each feature of the considered objects, in a PCP-net we are given a probability distribution over all possible preference orderings of the features domain. For the car example in a CP-net we would state our preference ordering over the two colors (for example, that we prefer white to red), while in a PCP-nets we would say that we prefer white to red with a certain probability p, and red to white with probability 1 p. For example this probability can express the percentage of the time that we encounter a particular comparison: we may very much like Italian food (90% of the time) but occasionally (10% of the time) we prefer burger with fries. Another example is when we are reporting the preferences of someone else of which we are not certain. It is interesting to think through the semantics of what the uncertainty and probabilities mean. If I prefer red to white with probability 0.8 how does one interpret this? It could be that it represents a strength of preference, though there are other formalisms that deal with this interpretation directly

REASONING WITH PCP-NETS

(Boutilier, Bacchus, & Brafman, 2001). It could be that the context is not well speciﬁed, and that in 0.8 of the cases I observe red ą white while in 0.2 of the cases I observe the reverse; this is the model used by some psychologists to resolve intransitive observations in repeated two alternative forced choice experiments (Regenwetter, Dana, & Davis-Stober, 2010; Regenwetter & Davis-Stober, 2012; Regenwetter, Dana, & Davis-Stober, 2011; Marden, 1995). Or it could be that the PCP-net represents the aggregation of preferences over a large population (considering the agents independent from each other) that prefers red ą white 80% of the time; the idea that uncertain, qualitative information may come from multiple agents has been popular in the recommendation systems area (Price & Messinger, 2005; Faltings, Torrens, & Pu, 2004; Beliakov et al., 2015). Surprisingly, the same mathematics of PCP-net formalism works for all of these interpretations.

Summary of Results. Given a PCP-net, it is then interesting to study what it means to ﬁnd the most preferred object and to respond to dominance queries involving two objects (determining if one outcome is more preferred than another according to the outcome ordering). For optimality, we notice that a PCP-net deﬁnes a probability distribution over a collection of induced CP-nets, that is, all those CP-nets that can be obtained from the PCP-net by choosing an ordering from each probability distribution over orderings in the PCP-net, and we use this observation to deﬁne two notions of optimality: the most probable optimal outcome and the optimal outcome of the most probable induced CP-net. Finding both optimal objects is computationally difﬁcult in general, but it becomes easy if we impose some restriction on the connectivity of the dependency structure. For dominance queries, of the form Is o1 more preferred than o2? , the answer is a probability value, that is, the probability that o1 is more preferred than o2, which by deﬁnition is the sum of the probabilities of those induced CP-nets where o1 is preferred to o2. Finding such a value is computationally difﬁcult, as dominance queries are already difﬁcult in CP-nets. However, we propose and evaluate a tractable approximation method that returns an interval in which the exact value is positioned. We then turn our attention to the use of PCP-nets in a multi-agent environment. This is a natural setting for PCP-nets, since, as noted above, a PCP-net models a collection of CP-nets. Thus we may think of individual agents specifying a CP-net that models their preferences, and a PCP-net that uses probabilities to reconcile the possibly conﬂicting preferences given by the individual CP-nets. This provides a formalism to perform collective reasoning tasks such as answering dominance queries, in addition to ﬁnding the most preferred outcome. Moreover, we can store or communicate between agents a single, compact structure instead of a possibly large collection of CP-nets. In contrast, previous efforts to tackle collective decision tasks over collections of CP-nets have primarily focused on the question of optimality (Li, Vo, & Kowalczyk, 2011) or dominance (Santhanam, Basu, & Honavar, 2010) and have not dealt with uncertainty. Generally, a voting method is deﬁned in order to determine the most preferred alternative and these methods usually work at the level of the individual features in a sequential fashion (Lang & Xia, 2009; Xia et al., 2011; Li, Vo, & Kowalczyk, 2010; Li et al., 2011; Xia, Conitzer, & Lang, 2008; Maran, Maudet, Pini, Rossi, & Venable, 2013; Mattei, Pini, Rossi, & Venable, 2013, 2012). We propose various ways to obtain a PCP-net out of the given collection of CP-nets and then compare both optimality and dominance tasks theoretically and experimentally by considering the satisfaction level of the contributing CP-nets. For collective optimality, we prove that our best method gives the same result as the sequential voting procedure proposed by Lang and Xia (2009). For collective dominance we provide an approximation that is tractable in the case of CP-nets for which the dependency structure is a directed poly-tree or for-

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

est, that is, polytree-structured CP-nets (a polytree is a directed graph whose underlying undirected graph is a tree).

Extensions and Related Work. Since PCP-nets were ﬁrst introduced in the work by Bigot et al. (2013) and Cornelio et al. (2013), there have been several generalizations and additional studies. The question of using CP-nets and PCP-nets for group decision making was further investigated in the work of Sikdar, Adali, and Xia (2017), closing several open questions. For example, in the work of Bigot, Mengin, and Zanuttini (2014) they show that PCP-nets can be learnt in both online and ofﬂine settings starting from a sequence of optimal items, by leveraging structure learning techniques for Bayesian Networks. Also, Fidha and Amor (2015) introduce Probabilistic Weighted CP-nets which allow for both uncertainty and differential preference weights, at the cost of a higher computational complexity. Weights are also added to CP-nets in the work of Wang, Zhang, Sun, Song, Guo, and Zhou (2012), allowing users to express more precisely the relative strength of preferences between two attributes. In the work of Lukasiewicz, Martinez, and Simari (2014) the notion of probabilistic preference logic networks are used to capture a more general notion of preferences than those modelled by CP-nets, again at the cost of higher computational complexity. Moreover, similar to our probabilistic extension of CP-nets, a probabilistic generalization of TCP-nets, which is an extension of CP-nets that represents the notion of relative importance and conditional relative importance between features (Brafman & Domshlak, 2002), has been recently proposed by Ahmed and Mouhoub (2018a). This work exploit directly our deﬁnition of G-net (see Deﬁnition 12) to compute the most probable compatible TCP-net and a generalization of the notion of Opt-Network (see Deﬁnition 13) to compute the most probable optimal outcome.

Organization. In Section 2 we introduce the main notions used throughout the paper including a background on CP-nets, Bayesian Networks, and voting. In Section 3 we formally deﬁne PCP-nets, while in Section 4 and 5 we address optimality and dominance tasks at the level of a single agent s preferences (single network) and provide empirical experiments for our algorithms. In Section 6 we move to the multi-agent setting, showing how to compute optimality and dominance when we have a collection of preferences (networks) again using both theoretical and empirical tools. Finally, in Section 7 we summarize the contributions of the paper and we discuss possible lines for future work.

2. Background and Preliminaries

In this paper we will reduce several problems regarding PCP-nets to problems on Bayesian Networks. Thus, in the following section, in addition to providing the main notions on CP-nets, voting theory, and CP-net aggregation, we also discuss Bayesian Networks.

2.1 Bayesian Networks

Bayesian networks (BNs) are a compact framework for representing and reasoning with uncertain knowledge (Pearl, 1988). A BN is a directed graph where each node corresponds to a random variable; the set of nodes is denoted by V ; a set of directed edges connects pairs of nodes, that is, if there is an edge from node X to node Y , X is said to be a parent of Y ; the graph is a directed acyclic graph (DAG); each node Xi has a conditional probability distribution Pp Xi|Pap Xiqq that quantiﬁes the effect of the parents on the node Xi. If the nodes are discrete variables, each Xi has a conditional

REASONING WITH PCP-NETS

probability table (CPT) that contains the conditional probability distribution, Pp Xi|Pap Xiqq. Each CPT row must therefore have probabilities that sum to 1. Inference in a BN corresponds to calculating Pp X|Eq where both X and E are sets of variables of the BN, or to ﬁnding the most probable assignment for X given E. A given assignment to the variables in E is called evidence. There are three standard inference tasks in BNs:

belief updating, which is ﬁnding the probability of an assignment of a variable or set of variables, possibly given evidence;

ﬁnding the most probable explanation (MPE) means ﬁnding the most probable assignment for all variables that are not given as evidence; and

ﬁnding the maximum a-posteriori (MAP) means ﬁnding the most probable assignment for some subset of variables (possibly given evidence).

These inference tasks are computationally hard in general. However, they can be solved in polynomial time if we impose restrictions on the topology of the BNs such as bounding the induced width, see the work of D Ambrosio (1999) or Dechter (1999) for details. We recall that the width of a graph is the maximum width among all nodes in the graph, where the width of a node X in a graph (given an ordering of the nodes) is the number of nodes preceding X in the ordering that are connected to X. The induced width of a graph is the width of its corresponding induced graph (given an ordering of the variables) that is obtained by recursively connecting earlier neighbors of each node following the given ordering (D Ambrosio, 1999). Given an ordering of the variables of a BN, these tractable algorithms have a number of steps linear in the number of variables, and each step is exponential in the number of variables preceding the current one in the ordering and connected to it in the BN graph. The largest of these numbers is the induced width of the graph of the BN. Different variable orderings give steps with different complexity. Finding a good variable ordering is a difﬁcult problem. It is important to observe that if we assume the induced width is bounded (and we know the optimal ordering), the overall algorithm is polynomial. If we consider the case of trees or polytrees, then the induced width is bounded.

2.2 CP-nets

CP-nets are a graphical model for compactly representing conditional and qualitative preference relations (Boutilier et al., 2004). They exploit conditional preferential independence by decomposing an agent s preferences via the ceteris paribus (cp) assumption (all other things being equal). CP-nets bear some similarity to Bayesian networks (see 2.1). Both use directed graphs where each node stands for a single feature (also called variable) from a set of features F t X1, . . . , Xnu with ﬁnite domains D1, . . . , Dn. For each feature Xi, each user speciﬁes a set of parent features Pap Xiq that can affect her preferences over the values of Xi. This deﬁnes a dependency graph in which each node Xi has Pap Xiq as its immediate predecessors. Given this structural information, the user explicitly speciﬁes her preference over the values of Xi for each complete assignment on Pap Xiq. This preference is a total or partial order over the domain of Xi (Boutilier et al., 2004). More formally:

Deﬁnition 1. A CP-net over a set of features F t X1, . . . , Xnu with ﬁnite domains is a directed graph G over X1, . . . , Xn. The nodes of the graph G are annotated with conditional preference tables CPTp Xiq for each Xi P F. Each conditional preference table CPTp Xiq associates a total

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

order ąu i over Xi s domain to each complete assignment u of Xi s parents Pap Xiq. A single row of a CPT is also called cp-statement. The total number of cp-statement in the CP-net is also called the size of the CP-net.

Note that the number of complete assignments over a set of variables (or features) is exponential in the size of the set. However, for any particular instance, there is an implicit constant k that speciﬁes the maximum number of parent features |Pap Xq|, that any feature may have. In the following we make no assumptions about the value of k other than that it is ﬁxed for a particular problem instance. With this restriction, and an implicit bound on |DX| (the domain of the variable X), we can and do treat the size of the conditional preference representation for any X as a constant. An acyclic CP-net is one in which the dependency graph is acyclic, and in this paper we focus on acyclic CP-nets. However, a CP-net need not be acyclic.

Example 1. Consider a CP-net whose features are X1, X2, X3, and X4, with binary domains containing x and x if X is the name of the feature, and with the preference statements as follows: x1 ą x1, x2 ą x2, x1x2 : x3 ą x3, x1 x2 : x3 ą x3, x1 x2 : x3 ą x3, x1x2 : x3 ą x3, x3 : x4 ą x4, x3 : x4 ą x4. Here, statement x1 ą x1 represents the unconditional preference for X1 x1 over X1 x1, while statement x3 : x4 ą x4 states that X4 x4 is preferred to X4 x4, given that X3 x3.

The semantics of CP-nets are based on the notion of a worsening ﬂip. A worsening ﬂip is a change in the value of a variable to a value which is less preferred by the cp-statement for that variable. We say that one outcome α is more preferred than another outcome β (written α ą β) if and only if there is a chain of worsening ﬂips from α to β. This deﬁnition induces a partial order over the outcomes. A CP-net thus represents a partial order over the set of possible complete assignments, deﬁned as the transitive closure of the relation induced by direct comparisons through cp-statements under the ceteris paribus assumption. Given a set of outcomes, an outcome o is optimal if and only if there does not exists any other outcome o1 such that o1 ą o, formally given in the following deﬁnition.

Deﬁnition 2. Given a CP-net inducing a preorder ą over the set of outcomes, an optimal outcome is an outcome that is maximal for ą in the set of outcomes.

There could exist more than one optimal outcome for the same CP-net, but if the CP-net has an acyclic dependency graph the optimal outcome is unique. Goldsmith, Lang, Truszczynski, and Wilson (2008) prove that ﬁnding an optimal outcome of a general CP-net is PSPACE-complete. However, in acyclic CP-nets, the unique optimal outcome can be found in linear time by sweeping through the CP-net (Boutilier et al., 2004), assigning the most preferred values in the preference tables. We sweep through the CP-net, following the arrows in the dependency graph and assigning at each step the most preferred value in the preference table. Each step in the sweep forward procedure is linear in the number of assignments to parents of the current feature, and there are as many steps as features. This algorithm takes polynomial time in the size of the CP-net description and, if we assume that the number of parents is bounded, is polynomial in the number of nodes. Two outcomes o and o1 can be in one of three possible relations with respect to a CP-net C:

o dominates o1: C |ù o ą o1

REASONING WITH PCP-NETS

o1 dominates o: C |ù o1 ą o

o and o1 are incomparable: C |ù o č o1 C |ù o1 č o written also as C |ù o o1

where C |ù o ą o1 means that there exists a worsening path (chain of worsening ﬂips) from o1 to o. A dominance query represents preferential comparison between outcomes.

Deﬁnition 3. Given a CP-net C and a pair of outcomes o and o1, a dominance query returns True if C |ù o ą o1, False otherwise.

Determining if one outcome is more preferred than another according to the outcome ordering is NP-hard even for acyclic CP-nets (Domshlak & Brafman, 2002; Goldsmith et al., 2008). However, Boutilier et al. (2004) prove that evaluating a dominance query for binary-valued tree structured CPnets has complexity Opn2q, where n is the number of features. This complexity result is improved by Bigot et al. (2013) that prove that dominance for tree-shaped CP-nets takes Opnq time. Boutilier et al. (2004) prove that dominance is polynomial also for polytrees but NP-complete for acyclic CPnets that are directed path singly connected, and NP-complete for CP-nets with a bounded number of paths between two nodes. Goldsmith et al. (2008) prove that dominance for CP-nets with a general structure is PSPACE-complete.

2.3 Voting with CP-nets

Voting is a widely studied subject, both in economics (Arrow, Sen, & Suzumura, 2002) and, more recently, in computer science (Brandt, Conitzer, Endriss, Lang, & Procaccia, 2016). In the standard setting, a set of voters express their preferences over a set of candidate alternatives, and a voting rule or social choice rule maps the set of voters preferences to one or more elements in the set of candidates (the winning alternatives). In many AI settings, however, the set of candidates have a combinatorial structure, with features and feature domains, and preferences over the candidates needs to be modeled via compact preference formalisms. In this paper we assume that individual preferences are modelled with CP-nets deﬁned on the same set of features. Candidates are all possible outcomes, that is, the complete assignments of the set of features over their domains. To aggregate preferences modelled this way, classical voting rules are not suitable, since they may generate the so-called multiple election paradoxes (Brams, Kilgour, & Zwicker, 1998) or may have a high computational complexity to compute the winner (Lang & Xia, 2009). Voting with CP-nets have been already studied extensively. Sequential voting rules have been proposed in this context (Lang, Pini, Rossi, Venable, & Walsh, 2007; Lang & Xia, 2009): First, an ordering of the features is chosen, which should be compatible with the dependency graphs of all the CP-nets, and then voting is applied to one feature at a time in the chosen order. Let us now introduce the formal setting of voting with CP-nets, together with a number of normative properties for voting rules in this setting, that will be useful to give a ﬁrst assessment. Let P p C1, . . . , Cmq be a proﬁle of CP-nets, that is, a vector of m CP-nets each corresponding to an individual in the set t1, . . . , mu. We assume that each Ci is deﬁned over the same set of variables X1, . . . , Xn, and that each variable is binary. An anonymous proﬁle of CP-nets, denoted with P pp C1, freq1q, . . . , p Ck, freqkqq, speciﬁes for k different CP-nets C1, . . . , Ck, all deﬁned on the same set of features X1, . . . , Xn, their relative frequency of appearance in a population of n voters. Given a proﬁle of CP-nets P p C1, . . . , Cmq, its anonymous version P can be easily constructed by setting freqi |tj|Cj Ciu|

n . In what follows we will indicate with P a generic anonymous CPproﬁle, or the anonymous proﬁle associated to a proﬁle P. In most of the paper we will make use

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

of anonymous CP-proﬁles. We will often assume the following property for proﬁles (Lang & Xia, 2009). We state it here for anonymous proﬁles:

Deﬁnition 4. A proﬁle P pp C1, freq1q, . . . , p Ck, freqkqq is said to be O-legal if all the dependency graphs of the CP-nets Ci share a topological ordering of the variables.

Finally, a voting rule for CP-nets r is a function that maps each anonymous proﬁle P into a single alternative rp Pq. Recall that in our case, the candidate alternatives are all possible assignments to the variables. Voting rules are typically assessed by means of desirable properties, often named axioms, that allow us to classify classes of rules. In this paper we consider the following ones:

Permutation-neutrality: The voting rule is not biased towards any of the variables. That is, for any anonymous CP-proﬁle P and any permutation σ : t1, . . . , nu Ñ t1, . . . , nu on variable names, rpσp Pqq rp Pq.1

Weak Pareto (or unanimity): If the winner in proﬁle P is rp Pq, there is no candidate that is preferred by all agents over rp Pq. That is, for any proﬁle P pp C1, freq1q, . . . , p Ck, freqkqq, if we denote with ąi the preference order associated to Ci, then there is no outcome o such that o ąi rp Pq, for all i P t1, , ku.

Consistency: If two proﬁles P1 and P2 have the same winner, then the same winner will result by merging the two proﬁles. That is, given two proﬁles P1 and P2 over the same candidates, with no voters in common, and such that rp P1q rp P2q, we have rp P1 Y P2q rp P1q rp P2q, where P1 Y P2 is the anonymous CP-proﬁles obtained by concatenating the two proﬁles, and adapting the relative frequencies accordingly.

Participation: It is always in the interest of a voter to participate in the voting process. Formally, for any proﬁle P and any CP-net Cj, rp P Y Cjq is not worse than rp Pq in the ordering ąj associated with Cj.

Homogeneity: If we take several copies of a proﬁle P, the result remains the same as taking just P. For any proﬁle P and any s P N, we have rp Pq rp P Y Y Pq where P is concatenated s times.

The properties we enumerated are rather natural and simple requirements for voting with CPnets (a complete and detailed axiomatic analysis is outside the scope of this paper). Note that, although all of the above properties seem very natural to have, and it could be hard to think of why a voting rule should not possess them, there are indeed voting rules that do not satisfy some of these properties individually or collections of them (Arrow et al., 2002).

3. Probabilistic CP-nets (PCP-nets)

In this section we introduce a generalization of traditional CP-nets with probabilities on individual cp-statements (Cornelio et al., 2013; Bigot et al., 2013). We assume that all the cp-statements are independent of each other since this allows us to use efﬁcient algorithms and techniques from

1. With a slight abuse of notation, we denote with σp Pq the anonymous CP-proﬁle obtained from P by permuting the names of the variables in each CP-net Ci of P according to σ.

REASONING WITH PCP-NETS

Bayesian Networks. Moreover in many scenarios this assumption is very reasonable: for example, when data comes from several different individuals, such as in a multi-agent scenario (see Section 6), it is reasonable to treat the incoming preferences as independent. However, there exist also many scenarios where it makes sense to remove this independence assumption (e.g., often people who prefer ﬁsh over meat also prefer wine over beer) and we plan to study them in future work.

Deﬁnition 5. A Probabilistic CP-net (PCP-net) has a feature set F t X1, . . . , Xnu, where each feature has domain D1, . . . , Dn. For each feature Xi, there is a set of parent features Pap Xiq. This deﬁnes a dependency graph in which each node Xi has directed edges from all features in Pap Xiq. Given this structural information, for each feature Xi, there is a probability distribution over the set of all preference orderings (total orderings over Di) for each complete assignment on Pap Xiq. Given a feature X in a PCP-net, its PCP-table is the table associating each combination of the values of the parent features of X with a probability distribution over the set of total orderings over the domain of X.

Note that PCP-nets are a strict generalization of CP-nets. When a PCP-net is restricted to probabilities in t0, 1u we recover the deﬁnition of CP-nets (Boutilier et al., 2004). In all the examples and experimental settings in this paper, we assume the domain of each variable to be binary and the induced width k of the dependency graph to be bounded by a constant. However, the deﬁnition of PCP-nets does not require these restrictions. Moreover, in what follows, we use a lexicographic tie-breaking rule when needed, to ensure a unique top element (since generally PCP-nets may have several ones). The proofs for all theorems and lemmas are in the Appendix.

Deﬁnition 6. Given a PCP-net Q, a CP-net is said to be induced by Q if it has the same variables, with the same domains, same dependency graph as Q and the CP-table of each variable Xi is generated by choosing a speciﬁc ordering (with non-zero probability) for each combination of the values of the parent features Pap Xiq.

Example 2. Consider the PCP-net in Figure 1(a) with two features, X and Y , with domains DX tx, xu and DY ty, yu. We can observe: the graph with the two nodes X and Y representing (through the edge between X and Y ) a preferential dependency between the two features; the preference table under the node X showing for each ordering of the values of X the corresponding probability; and the preference table under the node Y showing for each assignment of X the probability of observing a given ordering over values of Y . Figure 1(b) describes a CP-net that has been induced from the PCP-net of Figure 1(a).

It is important to notice that by generating the induced CP-tables we obtain redundant information when we select rows that are equal for each assignment to the parent variables. For example, considering a binary PCP-net with two variables X and Y and an edge from X to Y , we can have an induced CP-net with the following CP-table for the variable Y : x : y ą y and x : y ą y. This redundant information can be interpreted as vacuous edges: edges that are not actually dependencies. This means that removing these type of edges, does not change the preorder induced over the set of outcomes. Eliminating this redundant information (all the vacuous edges) allows us to reduce an (induced) CP-net to its normal form.

Deﬁnition 7. A CP-net is in normal form if it doesn t have any vacuous edge. This means that for each node X there does not exists any node Y P Pap Xq such that the rows of the CP-table of X,

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

x ą x 0.8 x ą x 0.2

x y ą y 0.1 y ą y 0.9

x y ą y 0.7 y ą y 0.3

(a) A PCP-net

x ą x x y ą y x y ą y

(b) An induced CP-net

Figure 1: A PCP-net and one induced CP-net.

in correspondence to the parents assignments uiy1, uiy2, , uiyl, have the same ordering for the values of the variable X, for each ui in the set tu1, , umu Domp Y1q ˆ ˆ Domp Ykq where Domp Y q ty1, , ylu and Pap Xq t Y, Y1, , Yku.

It is important to notice that transforming a CP-net not in normal form to another CP-net that is in normal form is always possible. This transformation preserves the same induced preorder over the set of outcomes. Moreover the process is invariant to the order in which vacuous edges are removed to transform a given a CP-net not in normal form to its normal form.

Example 3. This example shows the difference between a CP-net not in normal form and its normal form. The right part of Figure 2 shows the normal form of the CP-net in the left part of Figure 2.

x1 ą x1 x2 ą x2

x1x2 x3 ą x3 ą x3 x1 x2 x3 ą x3 ą x3 x1x2 x3 ą x3 ą x3 x1 x2 x3 ą x3 ą x3

(a) Non-Normal Form

x1 ą x1 x2 ą x2

x1 x3 ą x3 ą x3 x1 x3 ą x3 ą x3

(b) Normal Form

Figure 2: A CP-net and its associated CP-net in normal form. Note that this example uses ternary domains (x, x, and x)

If we transform an induced CP-net in normal form, we observe that, after the transformation, the edges are a subset of the edges in the PCP-net. Thus, CP-nets induced by the same PCP-net may have different dependency graphs, if considered in their normal form.

REASONING WITH PCP-NETS

Each induced CP-net has an associated probability, obtained from the PCP-net by taking the product of the probabilities of the orderings chosen in the CP-net.

Deﬁnition 8 (Probability of an Induced CP-net). Given a PCP-net Q and an induced CP-net C, let q be the set of all rows of the CPTs that deﬁne C. We deﬁne the probability of C, fp Cp qq, to be the product of the probabilities of the qi P q.

Hence, a PCP-net induces a probability distribution over the set of all induced CP-nets.

Example 4. Consider again the PCP-net in Figure 3(a) and the induced CP-net in Figure 3(b). The probability associated with this CP-net is deﬁned by: fp Cp qq rp1 q1q p1 q21q q22s.

x1 ą x1 q1 x1 ą x1 1 q1 x1 x2 ą x2 q21 x2 ą x2 1 q21

x1 x2 ą x2 q22 x2 ą x2 1 q22

(a) A PCP-net

x1 ą x1 x1 x2 ą x2 x1 x2 ą x2

(b) An induced CP-net

Figure 3: A PCP-net where the probability of the cp-statements are given as variables and one induced CP-net.

3.1 Probability over the Edges

In this section we assume that all the CP-nets are in normal form. As shown in the previous section, a PCP-net induces a collection of CP-nets, each one with a possibly different dependency graph. Each edge of the PCP-net dependency graph may or may not appear in an induced CP-net. Thus each edge, which represents whether or not some feature is dependent on another, is associated with a probability of existing. This probability is important as the modiﬁcation of the CP-nets graph through the addition or deletion of edges can have signiﬁcant impacts on the corresponding partial order over the set of outcomes described by the CP-net. As Boutilier et al. (2004) show, parent variables are more important than their child variables in the ceteris paribus semantics, since violating the preference for a parent variable is less preferred than violating the preference for any of its children. Furthermore the probability of an edge has an additional interpretation depending on the semantics of the context in which we are using the PCP-nets. For example, if we consider a PCP-net as the representation of the preferences in a multi-agent system as we have proposed, the edge probability can be interpreted as a measure of the agreement of the agents in the proﬁle on the dependency between two features, with the assumption that the rows are indeed independent from each other in the population. Hence, in the multi-agent context, the semantics of the PCP-net edges is useful

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

as it allows for a quick, interpretable understanding of the degree of agreement between the agents about a preferential dependency. This ability can be crucial in many scenarios, for example, when performing a market survey and using PCP-nets to represent customer preferences, the probability over the edges allows the surveyor to prioritize some features over others, if the majority of the customers ﬁnd them more important.

Deﬁnition 9. Given a PCP-net Q and an edge e in the dependency graph of Q, we deﬁne the probability of the existence of the edge e as the sum of the probabilities of those induced CP-nets in normal form that have e in their dependency graph:

i PI s.t. e PCi Pp Ciq

where I is the index set of induced CP-nets Ci.

This deﬁnition implies that the probability of non-existence of an edge e, thus the probability of having an induced CP-net without the edge e, is equal to 1 Ppeq. This probability can be derived using the PCP-table of the child node. We consider an edge e, from a feature X to a feature Y . The set of Y s parent nodes are the features in the set Pap Y q with cardinality k |Pap Y q|. We deﬁne E as:

FPp Pap Y qz Xq DF

where DF is the domain for a variable F. In the following theorem we show how to compute the probability of an edge as the complement of the probability of its nonexistence. This last probability is computed by summing the probability of having the same preference order for the second variable conditioned to the different values of the parent node (deﬁned by the edge), considering each instantiation of the other possible parent nodes.The proofs for all theorems and lemmas can be found in the Appendix.

Theorem 1. Given a PCP-net Q with features with binary domains, and given Υ tσ : E Ñ ty ą y, y ą yuu, the set of all possible functions σ that associate to each element v P E an element of the set ty ą y, y ą yu (the set of all the possible total orders of the domain of Y ), then the probability of an edge e p X, Y q can be computed by the following conditional probabilities:

v PE Prσpvq|vxs Prσpvq|v xs

The previous theorem can be easily generalized to PCP-net with features with non-binary domains as follows:

Theorem 2. The probability of the edge e p X, Y q can be computed as follows:

v PE Prσpvq|vx1s Prσpvq|vx2s Prσpvq|vxds

where DX tx1, x2, , xdu, Θp Y q is the set of all the possible total orders of the domain of Y and Υ tσ : E Ñ Θp Y qu is the set of all possible functions σ that associate to each elementv P E a total order over the domain of Y (an element of the set Θp Y q).

REASONING WITH PCP-NETS

4. Optimality

Given a PCP-net we study mainly two optimality tasks: ﬁnding the most probable induced CP-net and ﬁnding the most probable optimal outcome.

Deﬁnition 10. Given a PCP-net Q, the most-probable induced CP-net C is the induced CP-net with highest probability, considering the probability distribution deﬁned by Q over the set of induced CP-nets (see Deﬁnition 8): C arg max Ci Pp Ciq

Another relevant optimality task is to ﬁnd the optimal outcome of the most probable induced CP-net, that can be computed using known techniques for optimality over CP-nets (e.g., the sweep forward procedure mentioned in Section 2.2).

Deﬁnition 11. Given a PCP-net Q, the most probable optimal outcome o is the outcome that occurs with the greatest probability as the optimal one in the set of induced CP-nets:

o arg max oj

Ci PCoj Pp Ciq

where Coj is the set of induced CP-nets that have oj as optimal outcome.

These two reasoning tasks have slightly different semantics and may be of use to different groups in the preference reasoning community. The most probable induced CP-net is analogous to the CP-net that has the highest probability to map onto a user in a proﬁle. Whereas, the most probable optimal outcome would be what a recommendation engine should suggest to maximize the probability of being optimal. One can be seen as an aggregated model, that still retains usefulness for prediction and sampling, while the other is an aggregated outcome, that maximizes the probability of being optimal. In this section we do not make any general restriction on the PCP-net structure beside acyclicity. Thus, unless otherwise speciﬁed, we just assume an acyclic structure of the dependency graph.

4.1 The Most Probable Induced CP-net

We reduce the problem of ﬁnding the most probable induced CP-net, that is, the induced CP-net with highest probability according to Deﬁnition 8, to that of ﬁnding an assignment with maximal joint probability of an appropriately deﬁned BN that we call the general network or G-net. Making this explicit connection to BNs is important for several reasons: it formalizes the connection between PCP-nets and BNs, which is of independent mathematical interest; by establishing this connection several of our proofs become easier and it is simpler to write the equations for ﬁnding the probability of a CP-net induced by a PCP-net; and ﬁnally our PCP-net formalism (and that of Cornelio et al. (2013)) assumes that within a CP-table all statements are independent and all variables are independent as well.

Deﬁnition 12. Given a PCP-net Q, we deﬁne the Bayesian network called the general network, or G-net(Q), associated with Q, as follows:

For each independent feature A of the PCP-net, the G-net has a corresponding variable A. The domain of A in G-net(Q) corresponds to the set of all possible total orderings over the

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

domain of the corresponding feature A in Q. The probability distribution over these orderings is given by the PCP-table of A.

For each dependent feature B of Q, G-net(Q) has as many variables as there are combinations of value assignments to the parents. The domain of the B variables in the G-net(Q) corresponds to the set of all possible total orderings over the domain of the feature B in Q. They are independent, since we consider all the cp-statement as independent.

Example 5. Consider the PCP-net with two features, Q, from Example 2 and Figure 1. The corresponding G-net is shown in Figure 4. The variables have the following domains: DX tx ą x, x ą xu, DYx DY x ty ą y, y ą yu.

x ą x 0.2 x ą x 0.8

y ą y 0.1 y ą y 0.9

y ą y 0.7 y ą y 0.3

Figure 4: The G-net associated with the PCP-net in Example 2 and Figure 1.

By deﬁnition of G-net, given a PCP-net Q and the corresponding G-net N, there is a one-to-one correspondence between the assignments of N and the induced CP-nets of Q. This is because an assignment to a G-net N corresponds to a choice of a speciﬁc total order (over the domain of the corresponding feature in Q) for each variable and for each parent assignment. This deﬁnes a speciﬁc total order in the PCP-tables of each variable and for each parent assignment, characterizing an induced CP-net.

Theorem 3. Given a PCP-net Q and its set of induced CP-nets, then:

The probability of realizing one of its induced CP-nets is the joint probability of the corresponding assignment in the G-net for Q;

The probability distribution deﬁned in Deﬁnition 8 over the set of induced CP-nets is a well deﬁned discrete probability distribution (i.e., the probabilities over the domain elements sum to one and the probability of each element belongs to the interval r0, 1s).

The most probable induced CP-net corresponds to the CP-net associated (using the one-toone correspondence between induced CP-nets and assignments of the corresponding G-net described above) to the assignment of the G-net for Q, with maximal joint probability.

Because the G-net has a separable dependency graph (there are no edges and all the node are independent), to compute the assignment with maximal joint probability takes Op nq time, where n is the number of the nodes of the G-net. If k is the maximal number of parents nodes for each node (assuming a ﬁxed constant as maximum value for k) and d the maximal cardinality of the domain of the nodes of the PCP-net, then n n dk (n is the number of nodes in the PCP-net). We therefore

REASONING WITH PCP-NETS

have the computational complexity Opndkq (since the G-net is separable) that is polynomial in the size of the description (nodes and PCP-tables) of the PCP-net. The most probable induced CP-net could also be found by selecting the most probable ordering in the PCP-net CP-tables (with the same computational complexity as in G-nets). However, G-nets are useful for the more general case where there are dependencies between cp-statements. Extending PCP-nets to remove the independence assumption is an interesting direction for future work and establishing the relationship with BNs will help with this process. The G-net concept (and the Opt-net we introduce in Deﬁnition 13) that we introduce here has been used to reason about optimally in probabilistic TCP-nets (Ahmed, 2020; Ahmed & Mouhoub, 2018b).

4.2 PCP-nets vs Induced CP-nets

Given a discrete probability distribution P over a collection of CP-nets C, all with the same features and domains, there may be no PCP-net Q such that the set C of CP-nets are all and only the CP-nets induced by Q.

Theorem 4. Given a discrete probability distribution P over a set of CP-nets C (whether or not they have the same dependency graph), there may exist no PCP-net inducing P over the set C.

Theorem 5. Given a probability distribution over a set of CP-nets, each of which contains the same feature variables, if this distribution is generated by a PCP-net Q, then there exists and we can deﬁne a set of non-linear equations that provides as its unique solution the PCP-net Q inducing them. Theorem 4 and 5 give us interesting clues about the practicality of eliciting and aggregating CPnets. They indicate that, in some instances, we can derive a PCP-net for a population by eliciting CP-nets from individuals. However, solving the system of equation generated by Theorem 5 is likely a computationally hard problem since in general systems of non-linear equations are not even decidable; there may be a direct algorithm to solve this problem (given the fact that the system of equation constrains the solutions in the interval r0, 1s), but we leave this for future work.

4.3 The Most Probable Optimal Outcome

The most probable optimal outcome is the outcome that occurs with the greatest probability as the optimal one in the set of induced CP-nets. The probability that an outcome is optimal corresponds to the sum of the probabilities of the CP-nets that have that outcome as optimal. To reason about this task, we ﬁrst observe that the most probable optimal outcome may not be the optimal outcome of the most probable CP-net.

Example 6. Let us consider a PCP-net with only one feature X with domain DX tx1, x2, x3u and the following PCP-table:

x1 ą x2 ą x3 with probability 0.3

x1 ą x3 ą x2 with probability 0.3

x3 ą x2 ą x1 with probability 0.4

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

The most probable CP-net is the one corresponding to the third ordering and it has the optimal outcome x3. The other CP-nets have x1 as optimal, so Ppx1q 0.6 and Ppx3q 0.4. The most probable optimal outcome is therefore x1 but the optimal outcome of the most probable CP-net is x3.

Therefore, to ﬁnd the most probable optimal outcome, we cannot use the most probable induced CP-net (by the G-net procedure described) and then ﬁnd its optimal outcome. Rather, we make use of another Bayesian network, that we call the Opt-net. In general, given a PCP-net Q, the optimal network (Opt-net) for Q is a BN with the same dependency graph as Q. Thus, the Opt-net has a variable for each of the PCP-net s features. The domains of the variables in the Opt-net are the values of the corresponding features that are ranked ﬁrst in at least one ordering with non-zero probability. The conditional probability tables of the Optnet are obtained from the corresponding PCP-tables as follows: for each assignment of the parent variables, we consider the corresponding probability distribution over the values of the dependent variable deﬁned in the PCP-table. The probability of a value for the dependent variable is the sum of the probabilities of the orderings that have that particular value as most preferred according to that distribution. More formally:

Deﬁnition 13. Given a PCP-net Q, its Opt-net is a Bayesian network N such that:

for each node XQ in Q, N has a node XN;

the domain Domp XNq Ď Domp XQq and consists of the values of XQ that are ranked ﬁrst in at least one ordering with non-zero probability in the CP-table of XQ;

for each edge p XQ, Y Qq in Q, N has a an edge p XN, Y Nq;

the probability distribution over Domp XNq is deﬁned as:

j PJw pi j , @w P Domp XNq

ui is an assignment of the variables in Pap XNq;

Jw tj | ojr1s wu, where oj is a total order over Domp XNq and ojr1s is the top element in the ordering oj;

pi j is the probability of the ordering oj given the assignment ui in the PCP-net Q.

Example 7. Consider the PCP-net Q with three features A, B and C with domains DA ta1, a2u, DB tb1, b2u and DC tc1, c2, c3u shown in Figure 5. The Opt-net has the same dependency graph as Q, with three variables A, B and C with domains: DA ta1, a2u, DB tb1, b2u and DC tc1, c2u, and two edges AC and BC. The domain of variable C in the Opt-net does not contain value c3 because it never appears as most preferred in any ordering. Therefore, the Opt-net has a table for entry a1b2 where c1 appears with probability 0.2 and c2 appears with probability 0.8. The Opt-net is shown in Figure 5.

Theorem 6. Given a PCP-net Q and its Opt-net:

REASONING WITH PCP-NETS

a1 ą a2 0.8 a2 ą a1 0.2

b1 ą b2 0.7 b2 ą b1 0.3

a1 b1 c1 ą c2 ą c3 0.3 c2 ą c1 ą c3 0.7

c1 ą c2 ą c3 0.2 c2 ą c1 ą c3 0.4 c2 ą c3 ą c1 0.4

a2 b1 c1 ą c3 ą c2 0.4 c2 ą c3 ą c1 0.6

a2 b2 c1 ą c2 ą c3 0.1 c2 ą c1 ą c3 0.9

A PCP-net Q

a1 0.8 a2 0.2

b1 0.7 b2 0.3

c1 c2 a1 b1 0.3 0.7 a1 b2 0.2 0.8 a2 b1 0.4 0.6 a2 b2 0.1 0.9

The Opt-net associated with Q.

Figure 5: A PCP-net (left) and its associated Opt-net (right). We have omitted the rows of the cptables with zero probabilities for simplicity.

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

There is a one-to-one correspondence between the assignments (with non-zero probability) of the Opt-net and the outcomes that are optimal in at least one induced CP-net of Q.

Given a PCP-net Q, the probability that an outcome is optimal is the joint probability of the corresponding assignment in the Opt-net (we consider only the assignments of the Opt-net with positive probability). If no such corresponding assignment exists, then the probability of being optimal is 0.

The most probable optimal outcome for a PCP-net Q is obtained by computing the assignment that maximizes the joint probability of the Opt-net.

Since the problem of maximum assignment in BNs is NP-hard, the complexity of computing the most probable optimal outcome for a generic PCP-net is not harder than NP-hard. Moreover, if the structure of the PCP-net dependency is a poly-tree with bounded induced width, computing the most probable optimal outcome becomes polynomial in the PCP-net description (see Section 2.1). In the case of binary PCP-net with tree structure, Bigot et al. (2013) show that this task can be solved in linear time by dynamic programming. Notice that the Opt-net can solve the problem with the same computational complexity under these restrictions, however the Opt-net works for any PCP-net.

4.4 Optimality Under Partial Observations

A PCP-nets models a distribution over a collection of CP-nets: the set of induced CP-nets. The results/deﬁnitions introduced above for the two optimality tasks (most probable induced cp-net and most probable optimal outcome) can be easily extended to deal with the presence of some evidence, that is, observation of partial outcomes. This is true also for the dominance task that we will introduce in the next section (Section 5). A partial observation for some subset of features of a PCP-net is an instantiation of such features to a value in their domain. Given a PCP-net Q and an instantiation of some variable X xi, we can compute the result of either optimality task on Q given the evidence, by performing the standard optimality tasks on another PCP-net Q1 (a sub-PCP-net of Q). We obtain Q1 from Q by removing X and its outgoing edges, and modifying the cp-tables of all the features depending on X (i.e., the children nodes) to include only the rows that correspond to the value observed for X (i.e., with the assignment X xi).

Example 8. Consider the PCP-net Q with three features A, B and C with domains DA ta1, a2u, DB tb1, b2u and DC tc1, c2, c3u shown in Figure 6 (left). Consider the observation A a2. We construct the PCP-net Q1 that has only the two features B and C with the same domains as in Q, and only one edge, BC, as shown in Figure 6 (right).

5. Dominance in PCP-nets

In this section we restrict to acyclic dependency graphs, moreover in Section 5.2, Section 5.3, Section 5.4 and Section 5.5 we further restrict to binary-valued PCP-nets that have a polytree structure. Dominance queries are another relevant task to perform on a given PCP-net. In the PCP-net context this means computing the probability that one outcome dominates another one. In a multiagent scenario it corresponds to understanding whether one outcome is preferred by most agents.

REASONING WITH PCP-NETS

a1 ą a2 0.8 a2 ą a1 0.2

b1 ą b2 0.7 b2 ą b1 0.3

a1 b1 c1 ą c2 ą c3 0.3 c2 ą c1 ą c3 0.7

c1 ą c2 ą c3 0.2 c2 ą c1 ą c3 0.4 c2 ą c3 ą c1 0.4

a2 b1 c1 ą c3 ą c2 0.4 c2 ą c3 ą c1 0.6

a2 b2 c1 ą c2 ą c3 0.1 c2 ą c1 ą c3 0.9

A PCP-net Q

b1 ą b2 0.7 b2 ą b1 0.3

b1 c1 ą c3 ą c2 0.4 c2 ą c3 ą c1 0.6

b2 c1 ą c2 ą c3 0.1 c2 ą c1 ą c3 0.9

The sub-PCP-net Q1:

Q under observation A a2

Figure 6: A PCP-net (left) and its associated sub-PCP-net under observation A a2 (right). We have omitted the rows of the cp-tables with zero probabilities for simplicity.

Deﬁnition 14 (Dominance for PCP-nets). Given a PCP-net Q and a pair of outcomes o and o1, a dominance query returns the probability that Q |ù o ą o1. That is:

PQpo ą o1q ÿ

C induced by Q s.t. C|ùoąo1

Since any CP-net C can be interpreted as a PCP-net with probability values in t0, 1u, a dominance query for C returns either 0 or 1, where 0 corresponds to C |ù o ą o1 and 1 corresponds to C |ù o ą o1.

5.1 Computational Cost of Dominance

A CP-net is a particular PCP-net where all the probabilities in the PCP-tables are 0 or 1. Thus a CP-net can be seen as a subcase of PCP-net. It was shown by Boutilier et al. (2004) that evaluating a dominance query for binary-valued CP-nets is quadratic in the number of variables for tree structured CP-nets. Later Bigot et al. (2013) provided an algorithm for dominance testing in tree structured CP-nets with computational complexity Opnq where n is the number of features.

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

Moreover, dominance testing is polynomial (in the size of the CP-net description) for poly-trees (Boutilier et al., 2004; Domshlak & Brafman, 2002) and NP-complete for directed-path singly connected CP-nets (Boutilier et al., 2004), even if the in-degree of the nodes is bounded (Domshlak & Brafman, 2002), and for CP-nets with a bounded number of paths between each pair of nodes (Boutilier et al., 2004; Domshlak & Brafman, 2002). Finally, Goldsmith et al. (2008) proved that dominance is PSPACE-complete for general CP-nets . The difﬁcult cases remain of course difﬁcult for PCP-nets since CP-nets are a restricted form of PCP-nets. Bigot et al. (2013) prove that dominance for PCP-nets is #P-hard, even if the graph is acyclic, the longest path has length 3 and each node has at most one outgoing edge and at most 4 parents. They also give an algorithm to obtain dominance for a binary-valued tree structured PCPnet that takes Op22h2nq time, where n is the number of features and h is the number of variables that have a different value in o and o1. Computing the probability of dominance for separable PCP-nets (with no edges in their dependency graph) is polynomial (see Section 5.2), but computing the exact value of the probability of dominance for a more structured PCP-net is hard. In the next sections we detail algorithms to compute both a lower bound (Section 5.2) and an upper bound (Section 5.3) in polynomial time for PCP-nets if the dependency graph is a polytree (a polytree is a directed graph whose underlying undirected graph is a tree).

5.2 Lower Bound

In this section we consider only binary-valued PCP-nets that have a polytree structure. This category includes directed trees. Assuming the polytree structure (thus acyclicity), we can deﬁne an order O over n features Xi such that @i P t1, , nu, Pap Xiq Ď t X1, , Xi 1u. In what follows, given an outcome o o1o2 on, oæXi will indicate oi and oæS will indicate oæs1 oæsm where S ts1, , smu Ď t X1, , Xnu and S is such that @si P S [Papsiq Ă S]. Given a CP-net C and two outcomes o and o1, when we use the notation oæS ąS o1æS, oæS ăS o1æS or oæS S o1æS we mean that the comparison is considered in the sub-CP-net C1 that has the features in S and the arcs in C that connect them, with the corresponding CP-tables (to simplify the heavy notation, in what follow we will indicate ąS, ăS, and S as ą, ă, and since the restriction is clear from the context).

Deﬁnition 15. Given a PCP-net Q with n variables Xi and given two outcomes o and o1, let Diff be the set of feature indices that have different values on o and o1:

Diff ti | oæXi o1æXiu.

The lower bound for dominance for o ą o1 in Q is deﬁned as follows:

PL Qpo ą o1q ź

i PDiff p1 ρiq (1)

where @i P Diff, ρi is deﬁned as:

u PUo,o1 i Ppo1æXi ą oæXi|uq if Pap Xiq H

Ppo1æXi ą oæXiq if Pap Xiq H

REASONING WITH PCP-NETS

where u is an assignment of the parents of Xi and Uo,o1 i is the set of all assignments to Pap Xiq such that, given Y P Pap Xiq, if oæY o1æY then uæY oæY o1æY (otherwise, if oæY o1æY then uæY P ty, yu).

We require Deﬁnition 16 and the following lemmas in the proof of Theorem 8. In the ﬁrst lemma we consider CP-nets and we show that if o ą o1 then the same dominance relation holds on all preﬁxes of equal length of the two outcomes.

Lemma 1. Given an acyclic CP-net C with n nodes and two outcomes o o1o2 on and o1 o1 1o1 2 o1 n such that o ą o1 and given i an index in t1, , nu such that oi o1 i and oj o1 j@j ă i then oæX1 Xj ą o1æX1 Xj @j ě i.

In Lemma 2 and Corollary 6.1 we prove that if o and o1 have two incomparable preﬁxes (of equal length and involving the same variables), then, o and o1 are incomparable (denoted with o o1).

Lemma 2. Given an acyclic CP-net C with n nodes and two outcomes o and o1, if there exists an index i P t1, , nu such that oæX1 Xi o1æX1 Xi then we have that oæX1 Xj o1æX1 Xj for each index j between i and n (i ď j ď n).

Corollary 6.1 (of Lemma 2). Given an acyclic CP-net C with n nodes and two outcomes o and o1

such that there exists an index i P t1, , nu such that oæX1 Xi o1æX1 Xi, then o o1.

In the following lemma we prove that, given two incomparable outcomes, there is a preﬁx length threshold (denoted as index i in Deﬁnition 16), such that all preﬁxes of shorter length are ordered and all those of equal or greater length are incomparable.

Lemma 3. Given an acyclic CP-net C with n nodes and two outcomes o and o1, then o o1

if and only if there exists index i P t1, , nu such that oæX1 Xj o1æX1 Xj @j ă i and oæX1 Xl o1æX1 Xl @l ě i.

Deﬁnition 16. Given two oucomes o and o1 such that o o1, we say that they are incomparable for the index i (o i o1) if i satisﬁes Lemma 3.

In the following lemma we connect a topological property of the dependency graph of a CP-net to the incomparability of certain pairs of outcomes.

Lemma 4. Given an acyclic CP-net C with n nodes formed by two connected components C1 and C2, and given two different outcomes o and o1 such that rpoæC1 ą o1æC1 and oæC2 ă o1æC2q or poæC1 ă o1æC1 and oæC2 ą o1æC2qs then o o1.

Theorem 7. Given a polytree-structured CP-net C with n variables and two outcomes o and o1 then, if for all Xi in Diff (see Deﬁnition 15), there exists an assignment ui P Uo,o1 i (see Deﬁnition 15) such that ui : oæXi ą o1æXi then o ą o1. We are now in the position of proving the main result.

Theorem 8. Given a PCP-net Q and two outcomes o and o1, PL Qpo ą o1q is a lower bound for PQpo ą o1q. Observe that the lower bound is a product of at most n factors. The computation of each factor is Op2kq multiplications, where k is the maximal number of parents. Thus, the formula can be computed in Opn2kq time.

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

Example 9. Consider a PCP-net G as deﬁned in Figure 7 and outcomes o x1x2 x3x4x5 and o1 x1 x2x3x4 x5. As an example, computing the dominance value is given by PGpo ą o1q 0.10867, the lower bound is: PL Gpo ą o1q r1 Pp x2 ą x2qs r1 Ppx3 ą x3|x1qs r1 Pp x5 ą x5|x4qs 0.4 0.3 0.9 0.108. The distance between the lower bound and the true value is 0.00067, which means that the lower bound approximation gives an error of 0.067% on the correct value.

x1 ą x1, 0.3 x2 ą x2, 0.4

x1x2 : x4 ą x4, 0.4 x1 x2 : x4 ą x4, 0.8 x1x2 : x4 ą x4, 0.3 x1 x2 : x4 ą x4, 0.5

x1 : x3 ą x3, 0.7 x1 : x3 ą x3, 0.1

x4 : x5 ą x5, 0.9 x4 : x5 ą x5, 0.2

Figure 7: A PCP-net. We show only Ppxi ą xiq, since Pp xi ą xiq 1.0 Ppxi ą xiq.

If we apply the formula for the lower bound to separable PCP-nets, the resulting probability is the same as the actual value of dominance and can be computed in Opnq time.

Theorem 9. Given a separable PCP-net Q over n features X1, , Xn with binary domains Di txi, xiu@i P t1, , nu and given two outcomes o and o1 then

i PDiff po,o1q pi

j PDiff po,o1q p1 pjq

where pi Ppxi ą xiq in the PCP-net (and thus p1 piq Pp xi ą xiq) and where Diff and Diff

are a partition of Diff. Diff is the set of indexes of variables such that oæXi xi and o1æXi xi and Diff is the set of indexes of variables such that oæXi xi and o1æXi xi . Now we can prove the following theorem.

Theorem 10. Given a PCP-net Q with a separable dependency graph and two outcomes o and o1, then PQpo ą o1q PL Qpo ą o1q.

5.3 Upper Bound

We now move our attention to computing an upper bound to the probability that o ą o1 in a PCP-net Q. The computation of the upper bound, which we denote with PU Qpo ą o1q, turns out to be more straightforward than the one for the lower bound and it is detailed in Theorem 11.

REASONING WITH PCP-NETS

We say that a feature X in a PCP-net has a ﬁxed ancestor over two outcomes o and o1 if X is independent (has no parents in the PCP-net graph) or all the variables Y P Ancp Xq (ancestors of X) have the same value in o and o1: oæY o1æY @Y P Ancp Xq. We denote this set of all ﬁxed-ancestor variables as FA. As before, let Diff be the set of the indexes of features that have different values on o and o1.

Deﬁnition 17. Given a PCP-net Q with n variables Xi and given two outcomes o and o1, the dominance upper bound for o ą o1 in Q is:

PU Qpo ą o1q ź

j Pp Diff XFAq PpoæXj ą o1æXj|ujq

where uj is the assignment of the parents: uj oæPap Xjq o1æPap Xjq.

The formula above is a product of at most n factors, whose computation takes Opkq, hence Opnkq in total (which becomes Opnq, since k is bounded).

Theorem 11. Given a PCP-net Q and two outcomes o and o1, PU Qpo ą o1q is an upper bound for PQpo ą o1q.

Example 10. Consider a PCP-net G and two outcomes o and o1 as in Example 9. Diff XFA t2, 3u as they have different values on o and o1 and ﬁxed ancestors. Variable X5 has different values in o and o1and its ancestor X2 has different values in o and o1. Thus the upper bound is: PU G po ą o1q Ppx2 ą x2q Pp x3 ą x3|x1q 0.4 0.3 0.12. We recall that the true probability of dominance is PGpo ą o1q 0.10867 and the lower bound is PL Gpo ą o1q 0.108. Thus, the interval size between the two approximations is 0.012.

5.4 Experimental Evaluation: Dominance

Computing the lower bound and the upper bound gives us an interval in which the true value of the probability of dominance lies. In this section we experimentally explore the quality of our bounds by looking at the size of the interval while varying the number of features and, ﬁxing the number of features, varying the maximal number k of parents that a feature can have. For all our experiments we randomly generate collections of CP-nets, and PCP-nets. Generating PCP-nets that are independent and identically distributed (i.i.d.) is non-trivial as shown by Allen, Goldsmith, Justice, Mattei, and Raines (2016) and Allen, Goldsmith, Justice, Mattei, and Raines (2017) for CP-nets, a special case of PCP-nets, and to generate the PCP-nets i.i.d. is an interesting question for future work. Therefore we use an approximation method for random generation of a CP-nets:

Generating DAG structured CP-nets: We assume a ﬁxed ordering, X1, , Xn, of nodes, to conform to O-legality, and a maximum in-degree, k. We begin by generating the CP-net dependency graph. For each node Xi, we ﬁrst randomly choose its in-degree (uniformly) between 0 and mintk, i 1u. Next, we randomly add all the parents, choosing them from the set of variables t X1, , Xi 1u (without replacement, since we cannot add the same parent twice). When the graph is constructed, we ﬁll in the CPTs at random: given a variable X and a parents assignment u, we ﬁll the corresponding CPT row with an ordering uniformly sampled from the set tx ą x, x ą xu.

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

n 1 2 3 4 5 6 7

Pa : n 1 0.0000 0.0000 0.0010 0.0020 0.0047 0.0060 0.0047 Pa : n{2 0.0000 0.0000 0.0010 0.0016 0.0020 0.0046 0.0040 Pa : n{4 0.0000 0.0000 0.0000 0.0008 0.0018 0.0007 0.0014

Table 1: Distance between lower bound and the true probability of dominance.

Generating poly-tree structured CP-nets and PCP-nets: We generate poly-tree structured CPnets as we did for DAG structured ones, but we generate parents differently. For each node Xi we add parents, one by one, using rejection sampling on X1, , Xi 1, rejecting those that add cycles in the underlying undirected graph, until we reach the in-degree or exhaust the set of possible parents. The CPTs are ﬁlled using the same methodology used for DAG structured CP-nets.

We use a similar approximation method for generation PCP-nets:

Generating DAG structured PCP-nets: We generate the PCP-net graphs as we did the CP-net graphs, and then assign probabilities to CPT rows at random: given a variable X, for each parent assignment u we generate a value p uniformly in r0, 1s for the statement u : x ą x, then we assign to u : x ą x the value 1 p.

Generating poly-tree structured PCP-nets: We generate the dependency graph of poly-tree structured PCP-nets as we did for poly-tree structured PCP-nets. The CPTs are ﬁlled using the same methodology used for DAG structured PCP-nets.

To generate a proﬁle of m CP-nets we use the method described above independently. In all our experiments ties are broken lexicographically, that is, we select the winning element according to the ﬁxed lexicographical order over the elements names. Figure 8 shows the size of the interval as a function of the number of features, n, and of the number of parents per feature, k. In this experiment we vary n P r0, 30s and ﬁx the maximum k to n 1, n{2 and n{4. We compute the mean of the dominance approximation interval over 100 PCP-nets for each set of parameters. For each PCP-net, we take the mean over 100 outcome pairs.2

Turning back to Figure 8, we observe that the mean interval size is small, since it is between 0.1 and 0.2 over a possible maximal interval of size 1. The number of features reaches a plateau around 10 features. We conjecture that this is due to the high number of incompatibilities in the PCP-net. We also note that as the number of parents in the PCP-net grows, the size of the approximation interval increases. Table 1 and Figure 9 show the distance between our lower bound and the true value of the dominance probability (computed using the formula in Deﬁnition 14) as we vary the number of features. In this experiment we vary the number of features n P r0, 7s and we ﬁx the maximum k to n 1, n{2 and n{4. We compute the mean over 50 PCP-nets for each value of n where, for each PCP-net we use the mean over 20 outcome pairs. Hence, each point is computed from 1, 000 computational trials. We note that the true value of the probability of dominance is very close to

2. We have not included aggregate statistics about run times as the distribution was highly variable. Some instances took seconds, others took days.

REASONING WITH PCP-NETS

5 10 15 20 25 30 0

Number of features

Interval size

max parents= n 1

max parents= n{2 max parents= n{4

Figure 8: Interval size vs. number of features.

1 2 3 4 5 6 7 0.0

Number of features

max parents= n 1

max parents= n{2 max parents= n{4

Figure 9: Distance between true probability of dominance and lower bound vs. number of features.

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0

Interval r0, 1s divided in 10 bins

Normalized Proportion of Samples

n 1 n 2 n 3 n 4 n 5 n 6 n 7

Figure 10: Distribution of the true probability of dominance in the interval r0, 1s.

the lower bound since the error of the approximation is never greater than 0.6% with 7 features, although it grows as a function of the number of nodes and parents. To give more context to the signiﬁcance of the results shown in Figure 9 we need to understand the distribution of the true value of the probability of dominance to ensure that it is not always very small, and hence trivial to approximate from below. Indeed, the true probability of dominance can occur anywhere in the range r0, 0.5s for n ď 7, see Figure 10. This implies that our lower bound has good accuracy across the possible range of values. More precisely, in Figure 10 we perform a frequency study of the distribution of the true probability of dominance from Deﬁnition 14. We divided the interval r0, 1s in 10 bins and computed the normalized proportion of samples of the real probability of dominance in each bin. We observe that, for a small number of nodes, the distribution is uniform and as the number of features increases, the true value of dominance becomes more frequent in the ﬁrst bins.

5.5 Dominance as a Decision Problem

In some settings it could be enough to get a yes/no answer from a dominance query, rather than the exact probability value. To do this, it is enough to set a threshold to transform the [0,1] interval into two values. For example, suppose a choice between two products must be made, based on a proﬁle of agents CP-nets. In this case, instead of perform a dominance query on each CP-net, we can simply performing a dominance query on the aggregated PCP-net representing the proﬁle (see Section 6 for details on aggregation methods).

Deﬁnition 18 (DD for PCP-nets). Given a PCP-net Q and a pair of outcomes o and o1, the Decisional Dominance (DD) over o and o1 for Q is deﬁned as follows:

if PQpo ą o1q ą PQpo1 ą oq then DDQpo, o1q True

if PQpo ą o1q ă PQpo1 ą oq then DDQpo, o1q False

if PQpo ą o1q PQpo1 ą oq then DDQpo, o1q randomt True, Falseu.

REASONING WITH PCP-NETS

Since dominance is computationally difﬁcult also in CP-nets, this notion of decisional dominance for PCP-nets is computationally difﬁcult as well. We deﬁne the following two notions of approximate decisional dominance. One is just standard dominance on the most probable induced CP-nets, while the other one is the lower bound approximation to PCP-net dominance that we described in the previous section.

Deﬁnition 19 (MP-DD for PCP-nets). Given a PCP-net Q and a pair of outcomes o and o1, and given the most probable CP-net C induced by Q, the most probable induced CP-net based decisional dominance for PCP-nets (MP-DD) is deﬁned as follows:

if o ąC o1 then MP-DDQpo, o1q True

if o ăC o1 then MP-DDQpo, o1q False

if o C o1 then MP-DDQpo, o1q randomt True, Falseu

Deﬁnition 20 (LB-DD for PCP-nets). Given a PCP-net Q and a pair of outcomes o and o1, the Lower Bound based decisional dominance for PCP-nets (LB-DD) is deﬁned as follows:

if PL Qpo ą o1q ą PL Qpo1 ą oq then LB-DDQpo, o1q True

if PL Qpo ą o1q ă PL Qpo1 ą oq then LB-DDQpo, o1q False

if PL Qpo ą o1q PL Qpo1 ą oq then LB-DDQpo, o1q randomt True, Falseu.

Figure 11 shows the frequency of correct answers of MP-DD and LB-DD (in r0, 1s), varying the number of nodes. In this experiment we vary the number of nodes n P r0, 7s and we ﬁx the parents ď 2. We compute the mean over 50 PCP-nets for each value of n and for each PCP-net we take the mean over 20 outcomes pairs, obtaining a mean over 1000 iterations for each value of n. It is easy to see that the lower bound based decisional dominance is very accurate and is much more accurate then MP-DD. Also, LB-DD is polynomially computable, while MP-dominance is not. Moreover, we analyzed if this result changes if we consider only afﬁrmative DD answers or only negative ones. As ﬁrst result of this study we noticed that the frequencies of afﬁrmative and negative answers is uniform (50% each). Furthermore, we obtained that the afﬁrmative and negative cases are identical and thus correspond to the general case depicted in Figure 11.

6. PCP-nets in a Multiagent Context

Since a PCP-net can be interpreted as a probability distribution over a collection of CP-nets, it is natural to investigate the use of PCP-nets as structures that compactly represent the aggregation of the preferences given by a collection of agents via CP-nets. We have covered the necessary background and notations for discussing multi-agent aggregation of CP-nets and PCP-nets in Section 2.3. CP-nets have been used in the multiagent systems literature to represent the joint preferences of collections of agents (Rossi et al., 2004; Lukasiewicz & Malizia, 2016; Haret, Novaro, & Grandi, 2018) and as a preference formalism for aggregation using voting techniques (Xia et al., 2011; Li et al., 2010, 2011; Xia et al., 2008; Maran et al., 2013; Mattei et al., 2013). In a real-world scenario, the preference proﬁle of a multiagent system may be composed of hundreds or thousands of individual CP-nets. If the system needed to ﬁnd out a collective decision of all the agents then

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

1 2 3 4 5 6 7 60

Number of features

% Correct answers

MP-DD LB-DD

Figure 11: Percentage of right answers of MP-DD and LB-DD vs. number of features.

it may be easier to communicate between agents a single, compact structure instead of the entire proﬁle. Moreover, imposing some reasonable assumption, such as O-legality (or O-boundedness) (Lang & Xia, 2009), the aggregation methods can be performed in polynomial time in the size of the proﬁle. In addition, by using a summary or aggregation of the entire preference proﬁle, as has been done in some recommender systems (Adomavicius & Kwon, 2015; Beliakov et al., 2015), we can perform tasks such as deciding optimality and dominance without having to query all the agents again. The probability distribution over the CP-nets can be interpreted as the frequency of each CP-net in the collection as different agents may provide the same CP-net, and the probability values in the PCP-net can be seen as a way to reconcile the possibly different preferences stated in the CP-nets. In the following sections we restrict to the case in which we have O-legal proﬁle of acyclic CP-nets with binary features or acyclic PCP-nets with binary features, unless otherwise speciﬁed.

6.1 Aggregation Methods

We consider an O-legal anonymous proﬁle (that is, a collection) of CP-nets over features X1, , Xn, each with a binary domain. Recall that the relative frequency of a CP-net Ci, written as freqi, is the fraction of times Ci appears in the voter population, and that a proﬁle is denoted as P pp C1, freq1q, , p Cm, freqmqq, with řm i 1 freqi 1. As noted earlier in Theorem 4, given a proﬁle P of CP-nets, there may be no PCP-net which induces exactly the same distribution over the CP-nets in P. Therefore, we need to deﬁne aggregation methods that make sense even when there is no PCP-net that exactly recovers the input proﬁle of CP-nets. The ﬁrst method we propose (called the Proportion (PR) aggregation method) generates a PCP-net by taking the union of the dependency graphs of the given CP-nets and by determining the probabilities in the PCP-tables from the frequencies of the CP-nets in the proﬁle.

Deﬁnition 21 (PR aggregation method). Given a proﬁle of CP-nets P p Ci, freqiq, the Proportion (PR) aggregation method deﬁnes a PCP-net whose dependency graph is the union of the graphs of

REASONING WITH PCP-NETS

the CP-nets in the proﬁle. Given a variable X and an assignment u to its parents, the probabilities in the PCP-tables are deﬁned as follows:

Ppx ą x|uq ÿ

Ci:xą x|u freqi

(where the set t Ci : x ą x|u} denotes the set of CP-nets in the proﬁle that have the CP-row x ą x|u) that is, the probability of the ordering x ą x for variable X, given assignment u of Pap Xq, is the sum of probabilities of the CP-nets that have that particular ordering over the domain of X, given u . Similarly, Pp x ą x|uq 1 Ppx ą x|uq.

The second method (called the Least Square (LS) aggregation method) minimizes the mean squared error between the probability distribution induced by the PCP-net over the CP-nets given in the input and the relative frequency observed in the input.

Deﬁnition 22 (LS aggregation method). Let P p Ci, freqiq be a proﬁle of m CP-nets. The Least Square (LS) aggregation method deﬁnes a PCP-net whose underlying graph is the union of the graphs of the CP-nets and the probabilities qi j in the PCP-tables are those that solve the following problem:

argmin q Pr0,1sr

i 1 rfp Cip qq freqis2

where q is the vector of qi j ordered lexicographically with i as the ﬁrst variable, qi j is the probability variable of the j-th row of the PCP-table of the variable Xi in the PCP-net, r is the number of PCP-table-rows in the whole PCP-net, Ci are the m CP-nets observed in the proﬁle P and fp Cip qq is the function of probability of the CP-net Ci introduced in Deﬁnition 8.

The LS method objective function is a sum of a linear number of components (one for each CP-net in the initial proﬁle), however, evaluating fp Ci may require exponential time as the PCP-net resulting from a generic proﬁle may have an exponential number of cp-statements. The quadratic programming formulation of LS is the following:

i 1 rfp Cip qq freqis2

@i : qi P r0, 1s

We can ensure that the union graph of an O-legal proﬁle has bounded induced width by assuming the following O-boundedness condition: for each feature j there are sets PPp Xjq Ď t X1, . . . , Xnu of possible parents such that p1q |PPp Xjq| ă k for all j and a given constant k, and p2q for all individuals i, Paip Xjq Ď PPp Xjq.

Example 11. Given the CP-nets proﬁle in Figure 12, the LS method generates the following:

argmin q Pr0,1s3 rp1 q11qp1 q21qq22 0.5s2 rp1 q11qp1 q21qp1 q22q 0.4s2 rq11q21p1 q22q 0.1s2 .

The result corresponds to the PCP-net in Figure 13. The aggregated PCP-net using PR method is instead shown in Figure 14.

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

x1 ą x1 x1 x2 ą x2 x1 x2 ą x2

(a) C1 : 0.5

x1 ą x1 x2 ą x2

(b) C2 : 0.4

x1 ą x1 x1 x2 ą x2 x1 x2 ą x2

(c) C3 : 0.1

Figure 12: A proﬁle of CP-net with their frequencies.

X1 X2 x1 ą x1 0.05 rq11s x1 ą x1 0.95 r1 q11s

x1 x2 ą x2 0.05 rq21s x2 ą x2 0.95 r1 q21s

x1 x2 ą x2 0.56 rq22s x2 ą x2 0.44 r1 q22s

Figure 13: An aggregated PCP-net using LS.

It is interesting to observe that adding a pair p Ci, 0q to a proﬁle of CP-nets will change the LS result. Since LS is the result of a linear program, including p Ci, 0q is actually adding constraints to this linear program, explicitly telling the aggregation procedure that a certain CP-net cannot appear in the output distribution (of induced CP-nets). This can cause problems as the most probable induced CP-net is the one that best summarizes the preferences of the agents. This CP-net should be an aggregation of the preferences of the entire proﬁle, but observe that this CP-net might not appear in the original proﬁle. To ensure that only a CP-net in the original proﬁle is selected, constraints could be added that set all other CP-nets to 0, but this is an exponential program and would not be feasible. Computing a PCP-net using either PR or LS may require exponential time as the PCP-net resulting from a generic proﬁle may have an exponential number of cp-statements. However, PR also becomes a polynomial method if we have the O-boundedness condition. As LS formalized a notion of distance to the best we thought it was a ﬁtting complement to PR s item by item majority best method. We wanted two slightly different methods to compare and contrast.

6.2 Optimality in Aggregated CP-nets

Let P be the set of all anonymous CP-net proﬁles P of m voters over a set of alternatives X. Recall that a CP-voting rule r : P Ñ X is a function that maps each proﬁle P to an alternative rp Pq P X. In what follows we assume that CP-voting rules use lexicographic tie-breaking to return a unique winner. The choice and implementation of the tie-breaking rule can have signiﬁcant impacts on the properties of voting rules and, as is standard in the social choice literature for initial work in an area, we focus on the worst case here, that is, an ordered tie-breaking rule that is known to all agents (for

REASONING WITH PCP-NETS

X1 X2 x1 ą x1 0.1 x1 ą x1 0.9

x1 x2 ą x2 0.1 x2 ą x2 0.9

x1 x2 ą x2 0.5 x2 ą x2 0.5

Figure 14: An aggregated PCP-net using PR.

more details see the work of Mattei, Narodytska, and Walsh (2014); Obraztsova and Elkind (2011); Aziz, Gaspers, Mattei, Narodytska, and Walsh (2013), and Obraztsova, Elkind, and Hazon (2011)). We deﬁne four voting rules by combining the two aggregation methods PR and LS presented in Deﬁnition 21 and 22 with the two possible ways of extracting an optimal outcome from a PCP-net: PRO: PR and most probable optimal outcome; PRI: PR and optimal outcome of most probable induced CP-net; LSO: LS and most probable optimal outcome; LSI: LS and optimal outcome of most probable induced CP-net. Computing PRI is polynomial (if the O-boundedness condition is met) and computing PRO is guaranteed to be polynomial only if the graph of the resulting PCP-net has bounded induced width. This result follows from the fact that computing the most probable outcome and the optimal outcome of the most probable induced CP-net are polynomial in the PCP-net description, if it has bounded width. This property can be obtained via the O-boundedness condition, which also ensures a polynomial complexity to the computation of the PR method. The four methods may produce different outcomes:

Lemma 5. There exists a proﬁle of CP-nets P such that

t PROp Pq, PRIp Pqu X t LSOp Pq, LSIp Pqu H;

and there exists a proﬁle of CP-nets P 1 such that:

PROp P 1q PRIp P 1q;

and there exists a proﬁle of CP-nets P 2 such that:

LSOp P 2q LSIp P 2q.

It is interesting to observe that PRI returns the same result as the sequential voting rule with majority (Lang & Xia, 2009), which consists of applying the majority rule locally on each feature of the given CP-nets in the order given by O.

Theorem 12. Given a proﬁle of CP-nets, PRI produces the same result as sequential voting with majority. Other notions of optimal outcome may be deﬁned. For example, the outcome that maximizes the average number of outcomes worse than it in the induced CP-nets. However, this kind of optimality (and other similar ones) is computationally hard since it exploits the full partial order deﬁned over the outcomes.

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

6.3 Axiomatic Properties

A ﬁrst way to compare the four voting rules is by checking if they satisfy the axiomatic properties discussed in Section 2.3. Our results are summarized in Table 2, where empty cells correspond to open problems. It is easy to see that neutrality holds for all four voting rules. Other results follow from previous work: we can infer that PRI satisﬁes consistency and homogeneity, since it coincides with the sequential voting procedure on O-legal proﬁles deﬁned and studied by Lang and Xia (2009). For the other results, we provide the following theorem:

Theorem 13. The following holds:

piq PRO, LSO, and LSI satisfy homogeneity;

piiq PRI and PRO satisfy participation.

piiiq PRI satisﬁes consensus and PRO satisﬁes consensus over a single feature.

In conclusion, the aggregation method PR, generating voting rules PRO and PRI, satisﬁes a good number of desirable axiomatic properties. For LS instead there are some open problems, thus we do not know if it is better or worse than PR from the analysis of its properties. This provides further motivation to the experimental section that follows.

Property PRO PRI LSO LSI

Homogeneity

Consistency

Participation

Consensus 3

Table 2: Axiomatic properties of PRO, PRI, LSO and LSI.

6.4 Experimental Evaluation: Optimality

In this section we describe our experiments to evaluate the quality of the outcomes returned by the four voting rules. We compare the results of these four voting rules with a baseline we call PLUR, which outputs the result of the plurality voting rule applied to the initial proﬁle of CP-nets. PLUR takes the optimal outcome of each CP-net and returns the outcome which is optimal for the largest number of CP-nets. We then compare these ﬁve voting rules using a scoring function that is computed using dominance queries on the input proﬁle of CP-nets. Let F and G be two CP-voting rules, and let T be a set of O-legal CP-proﬁles. For ease of presentation, this section considers non-anonymous proﬁles P p C1, . . . , Cnq. Given a proﬁle P, we ﬁrst deﬁne three parameters:

dą P p F, Gq |t C P P : Fp Pq ąC Gp Pqu|,

3. With some restrictions (see Theorem 13).

REASONING WITH PCP-NETS

dă P p F, Gq |t C P P : Gp Pq ąC Fp Pqu| and

d P p F, Gq |t C P P : Fp Pq C Gp Pqu|.

Note that dą P dă P d P |P|. We then deﬁne the function Dom P p F, Gq as:

Dom P p F, Gq

1 if dą P p F, Gq ą maxtdă P p F, Gq, d P p F, Gqu 1 if dă P p F, Gq ą maxtdą P p F, Gq, d P p F, Gqu 0 otherwise.

This function captures the dominance relationship between the results of applying two voting rules F and G. To declare dominance, we require that the number of CP-nets where dominance holds is larger than each of the number of CP-nets (we recall that ties are broken lexicographically) where we have incomparability, and the number of CP-nets where we have dominance in the other direction. Based on function Dom P , we deﬁne the following notion of pairwise score:

Pair Score T p F, Gq ř PPT Dom P p F, Gq

Note that this score belongs to the interval r 1, 1s. We are now ready to deﬁne the scoring function, inspired by the Copeland voting rule, which gives a score for each voting rule, compared to all others via the Pair Score score:

Copeland Score T p Fq ÿ

GPV zt Fu Pair Score T p F, Gq

where V t PRO, PRI, LSO, LSI, PLURu. Observe that this score belongs to the interval r 4, 4s. While the choice of scores can have a dramatic effect on the outcome of the experiments, we feel that these three scores are reasonable and give interesting insight into the results. Informally, the Pair Score method only focuses on the dominance relationship while Copeland Score focuses on the decision of the overall aggregation. Comparing PLUR to Pair Score gives us an idea of the power of the dominance relation versus just looking at the top element. Copeland Score is designed to compare the different methods on how they do on the overall aggregation. We choose Copeland as the basis for this score as Copeland is qualitative so it is more suitable for qualitative preference formalisms like CP-nets and PCP-nets than other voting rules like Borda that are quantitative. In addition, to evaluate the winner we compute dominance relationships between the pairs of outcomes, hence we want to focus on pairs and Copeland is a popular pairwise voting rule.

Results. To generate O-legal proﬁles of CP-nets, and PCP-nets, we follow the same procedure described in Section 5.4. An interesting direction for future work is to generate the proﬁles of CPnets using one or more statistical distributions, as discussed by Allen et al. (2017) and often done in experiments for voting rules (Mattei & Walsh, 2017, 2013). However this would ﬁrst require being able to generate O-legal CP-nets i.i.d., which is a standing open problem. We show results for some speciﬁc parameter values. Similar results were observed also for other values. In both the experiments shown in Figure 15 and Figure 16, we compute the mean Copeland Score over 100 O-legal proﬁles of CP-nets and we consider two parameters: the number of features and the number of individuals in the proﬁle. In the experiment in Figure 15 we investigate the quality

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

2 4 6 8 10 1

Number of features

Copeland Score

LSI LSO PRI PRO PLUR

Figure 15: Copeland Score vs. the number of features.

of all the voting rules, varying the number of features and ﬁxing the number of individuals in the proﬁle. In Figure 16 we analyze the quality of the voting rules, varying the number of individuals in the proﬁle and ﬁxing the number of features. In the ﬁrst set of experiments (Figure 15) the proﬁles have 20 individual CP-nets and the number of features varies from 1 to 10, and each has at most 2 parents. According to the Copeland Score, the best voting rule is PRI, and we observe that PR is consistently better than LS using either the O or I method. PRI is consistently better than PRO and LSI is also better than LSO. Hence, the most probable optimal outcome (O) is worse than the optimal outcome of the most probable induced CP-net (I) in both the PR and the LS method. The dominance of the I methods over the O methods is interesting and consistent across the experiments. Looking speciﬁcally at PRI, we think the result is due to the fact that PRI selects the most representative agent in the proﬁle, that is, the one that best represents all the preferences of all the agents, and then computes the optimal outcome of this agent. While, in contrast, PRO is selecting the outcome that most frequently appears in the proﬁle as optimal. As each of the agent can have a different optimal outcome, this may spread out the voting and lead us toward fewer compromise candidates. The variance in Figure 15 could be explained by the fact that, with more features, the number of pairs of outcomes that are incomparable increases. There is also a noticeable difference of behavior of the PR method between even and odd numbers of features (and even and odd numbers of individuals in Figure 16). Our conjecture is that an odd number of features (resp. individuals) leads to more decisiveness in the voting rules because of the presence of a smaller number of ties. In the second set of experiments (Figure 16) the proﬁles have n 3 and at most k 1 parent per feature, and the number of individual CP-nets varies in r1, 30s. We observed that the number of CP-nets in the proﬁle does not signiﬁcantly inﬂuence the Copeland Score of the voting rule. We therefore conclude that, in our experimental setting, the PR method is the best one, since it better satisﬁes the preferences expressed by the CP-nets, according to the scores we deﬁned.

REASONING WITH PCP-NETS

5 10 15 20 25 30 2

Number of individuals

Copeland Score

LSI LSO PRI PRO PLUR

5 10 15 20 25 30 2

Trendlines:

Number of individuals

Copeland Score

LSI LSO PRI PRO PLUR

Figure 16: Copeland Score vs. the number of individuals from 1 to 30 (and trendlines).

Intuitively, we explain the better performance of the PR method with its majoritarian nature, that is, it looks at the set of CP-nets and select the cp-statement present in the majority of input CP-nets. Instead, the LS method ﬁnds a mid-point between the cp-statements in all the CP-nets. If we look at our outcome metrics, I is the optimal outcome of the most probable induced CP-net and O the most probable optimal outcome of the resulting PCP-net, and both of these are majoritarian metrics since they are attempting to pick an outcome with highest probability. Hence these outcome metrics are closer to the philosophy of PR as aggregation method, rather than LS, which is attempting to minimize the distance to the CP-nets in the input set.

6.5 Dominance on PR

Given that PR is the best method for optimality in PCP-nets for multi-agent scenarios, we now analyze both exact and approximate dominance in this setting. It turns out that PR is also accurate in terms of dominance. To show this, we compare the result of dominance tests on random pairs of outcomes in CP-net proﬁles and their associated PCP-net. Given two outcomes o and o1, the dominance value in the initial proﬁle is the probability mass of the CP-nets that entail o ą o1. In Table 3, we report the difference between the two values of dominance. Note that this values are in the interval r0, 1s where 1 is the worst value (maximum difference). We can see that the two values of dominance had maximum difference 0.047 when varying the number of features and the number of CP-nets in the proﬁle. Thus, the approximation induced by a PCP-net generated with the PR method, given a proﬁle of CP-nets, is accurate both for optimality and for dominance.

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

n features 1 2 3 4 5 6

difference 0.0 0.023 0.028 0.037 0.045 0.047

Table 3: Difference between the value of dominance in the initial proﬁle of CP-nets and in the PCP-net aggregated with PR.

7. Conclusions and Future Work

We have deﬁned and shown how to reason with PCP-nets, a generalized version of CP-nets, that can model probabilistic conditional preferences. PCP-nets can be seen as a way to extend CPnets by including probability information similarly to Bayesian Nets, thus modeling preference and probabilities in one uniﬁed structure. We have studied how to reason with PCP-nets in terms of both optimality and dominance. Since dominance is computationally hard, we also provided a tractable approximation which is very accurate when the dependency graph of the PCP-net has a polytree structure. We have also studied the use of PCP-nets as a compact representation structure for expressing the aggregated preferences of a set of agents. Starting from a collection of individual CP-nets, we introduced and evaluated two aggregation methods to obtain a PCP-net, comparing them both theoretically and experimentally. By generating a compact representation of a set of CP-net preferences via a single PCP-net, we are able to perform both optimality and (exact or approximate) dominance reasoning on the given collection of CP-nets. There are several lines for future work regarding PCP-nets. The ﬁrst one concerns the possibility of relaxing the independence assumption that is fundamental to CP-nets. In both CP-nets and PCP-nets, the dependencies are among features, and they appear in the dependency graph, but the cp-statements are considered to be independent from each other (Bigot et al., 2013; Cornelio et al., 2013). This means that the preferences of a user over a feature, given an assignment to the parent nodes, are independent from her preferences over another feature (or over the same feature but with another assignment of the parent nodes). This independence assumption appears clearly in the structure of the G-net (see Section 3). The G-net structure expresses the relation between the cp-statements and, in our formulation, has a separable graph (that is, without edges), while the graph of a PCP-net has edges between the features. Thus, in PCP-nets, we are considering all the cp-statements independent. In many scenarios it makes sense to stick to this independence assumption: when we are modelling noise in choices, hidden external factors, or when data comes from several different individuals, such as in a multi-agent scenario, and we want to treat the incoming preferences as independent. However, there are also other scenarios where it makes sense to remove this independence assumption. By doing this, the G-net will model a non-trivial relation between the cp-statements, since it will admit edges between its nodes, representing the connection between cp-statements. For example, we may observe that there is a strong correlation among the probability distributions of the preferences over the same variable (for different values of its parents), or among the probability distributions associated to preferences deﬁned over different variables (e.g., often people who prefer ﬁsh over meat also prefer wine over beer). Moreover we want expand the proﬁles of CP-nets that we consider to include different generation methods and correlations. The second line of possible future work concerns learning PCP-nets starting from examples deﬁned by pairs of outcomes. We already have initial results on learning PCP-nets with only in-

REASONING WITH PCP-NETS

dependent features, but since a separable structure is not always compatible with the input data, we intend to deﬁne methods to also learn non-separable PCP-nets, which are more expressive. We believe that using pairs of outcomes (rather than optimal outcomes, as done by Bigot et al. (2014)) as training data makes the collection of training data much easier, since it is easier for people to compare two outcomes rather than to recognise if an outcome is optimal (Allen et al., 2015). This claim is also supported by an extensive literature on learning from pairs (Chevaleyre et al., 2011; Lang & Mengin, 2009). A possible approach to this learning problem is to follow a methodology similar to the one in the work of Bigot et al. (2014) (where however PCP-nets are learnt from optimal outcomes), in which ﬁrst we learn the structure of the PCP-net and then, once the structure is ﬁxed, we learn the probabilities in the PCP-tables. To ensure good computational complexity properties of the various reasoning tasks in (P)CPnets, we also plan to combine the PCP-net framework with machine learning approaches (Li, 2011), with the intent to learn the dominance relation. Finally, another interesting direction for future work would be performing more empirical experiments comparing the similarity, for example, overlap of the structure, of a learned PCP-net to a CP-net proﬁle. Another experiment could compare the results from the LS and PR (as well as others) approaches starting from a noisy, ground-truth PCP-net. However, doing this would require also understanding how to efﬁciently and statistically accurately sample from a PCP-net (Allen et al., 2017).

Acknowledgments

Judy Goldsmith s work was partially supported by NSF grant IIS-1649152. The work of Cristina Cornelio and Francesca Rossi was partially supported by the University of Padova project Incorporating patients preferences in kidney transplant decision protocols . The work of Cristina Cornelio was partially done while at IBM Research. Nicholas Mattei s work was partially supported by NICTA, funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program. The work of Nicholas Mattei was also partially done while at IBM Research. We would also like to thank the anonymous referees whose careful feedback made this a better paper than it had been. Portions of this paper were included in three conference publications: the ﬁrst introduced the notion of PCP-nets at the Australasian Joint Conference on Artiﬁcial Intelligence (Cornelio et al., 2013), the second introduced the idea of using PCP-nets in a multiagent context at the International Workshop on Computational Social Choice (Cornelio et al., 2014), and the third more clearly formalized this multiagent view while adding experiments and tighter bounds at the International Conference on Autonomous Agents and Multiagent Systems (Cornelio et al., 2015).

Adomavicius, G., & Kwon, Y. (2015). Multi-criteria recommender systems. In Ricci, F., Rokach, L., & Shapira, B. (Eds.), Recommender Systems Handbook, pp. 847 880. Springer.

Ahmed, S., & Mouhoub, M. (2018a). Representation and reasoning with probabilistic tcp-nets. Computer and Information Science, 11, 9.

Ahmed, S., & Mouhoub, M. (2018b). Representation and reasoning with probabilistic tcp-nets.. Comput. Inf. Sci., 11(4), 9 28.

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

Ahmed, S. U. (2020). Conditional Preference Networks: Constraints, Genuine Decision, and Aggregation. Ph.D. thesis, Faculty of Graduate Studies and Research, University of Regina.

Allen, T. E., Goldsmith, J., Justice, H. E., Mattei, N., & Raines, K. (2017). Uniform random generation and dominance testing for cp-nets. Journal of Artiﬁcial Intelligence Research, 59, 771 813.

Allen, T., Chen, M., Goldsmith, J., Mattei, N., Popova, A., Regenwetter, M., Rossi, F., & Zwilling, C. (2015). Beyond theory and data in preference modeling: Bringing humans into the loop. In Proceedings of the 4th International Conference on Algorithmic Decision Theory (ADT).

Allen, T., Goldsmith, J., Justice, H., Mattei, N., & Raines, K. (2016). Generating CP-nets uniformly at random. In Proceedings of the 30th AAAI Conference on Artiﬁcial Intelligence (AAAI).

Amor, N. B., Dubois, D., Gouider, H., & Prade, H. (2016). Graphical models for preference representation: An overview. In Proceedings of the 10th International Scalable Uncertainty Management (SUM 2016), pp. 96 111.

Arrow, K. J., Sen, A. K., & Suzumura, K. (2002). Handbook of Social Choice and Welfare. North Holland.

Aziz, H., Gaspers, S., Mattei, N., Narodytska, N., & Walsh, T. (2013). Ties matter: Complexity of manipulation when tie-breaking with a random vote. In Proceedings of the 27th AAAI Conference on Artiﬁcial Intelligence (AAAI), pp. 74 80.

Beliakov, G., Calvo, T., & James, S. (2015). Aggregation of preferences in recommender systems. In Ricci, F., Rokach, L., & Shapira, B. (Eds.), Recommender Systems Handbook, pp. 777 808. Springer.

Bigot, D., Fargier, H., Mengin, J., & Zanuttini, B. (2013). Probabilistic conditional preference networks. In Proc. of the 29th International Conference on Uncertainty in Artiﬁcial Intelligence (UAI).

Bigot, D., Mengin, J., & Zanuttini, B. (2014). Learning probabilistic cp-nets from observations of optimal items. In 7th Starting AI Researcher Symposium (STAIRS 2014), pp. 81 90.

Bistarelli, S., Montanari, U., & Rossi, F. (1997). Semiring-based constraint satisfaction and optimization. Journal of the ACM (JACM), 44(2), 201 236.

Boutilier, C., Bacchus, F., & Brafman, R. I. (2001). UCP-networks: A directed graphical representation of conditional utilities. In Proceedings of the 17th International Conference on Uncertanity in Artiﬁcial Intelligence (UAI), pp. 56 64.

Boutilier, C., Brafman, R., Domshlak, C., Hoos, H., & Poole, D. (2004). CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements. Journal of Artiﬁcial Intelligence Research (JAIR), 21, 135 191.

Brafman, R., & Domshlak, C. (2002). Introducing variable importance tradeoffs into cp-nets. In UAI 02, pp. pages 69 76 (cited on pages 26, 40).

Brafman, R., & Domshlak, C. (2009). Preference handling-an introductory tutorial. AI Magazine, 30(1), 58.

Brams, S., Kilgour, D., & Zwicker, W. (1998). The paradox of multiple elections. In Soc Choice Welfare.

REASONING WITH PCP-NETS

Brandt, F., Conitzer, V., Endriss, U., Lang, J., & Procaccia, A. D. (Eds.). (2016). Handbook of Computational Social Choice. Cambridge University Press.

Chevaleyre, Y., Endriss, U., Lang, J., & Maudet, N. (2008). Preference handling in combinatorial domains: From AI to social choice. AI Magazine, 29(4), 37.

Chevaleyre, Y., Koriche, F., Lang, J., Mengin, J., & Zanuttini, B. (2011). Preference Learning, chap. Learning Ordinal Preferences on Multiattribute Domains: The Case of CP-nets. Springer Berlin Heidelberg.

Cornelio, C., Goldsmith, J., Mattei, N., Rossi, F., & Venable, K. (2013). Updates and uncertainty in CP-nets. In Proceedings of the 26th Australasian Joint Conference on Artiﬁcial Intelligence (AUSAI).

Cornelio, C., Grandi, U., Goldsmith, J., Mattei, N., Rossi, F., & Venable, K. (2014). Voting with CP-nets using a probabilistic preference structure. In Proceedings of the 5th International Workshop on Computational Social Choice (COMSOC).

Cornelio, C., Grandi, U., Goldsmith, J., Mattei, N., Rossi, F., & Venable, K. (2015). Reasoning with PCP-nets in a multi-agent context. In Proceedings of the 14th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).

D Ambrosio, B. (1999). Inference in Bayesian networks. AI Magazine, 20(2), 21.

Dechter, R. (1999). Bucket elimination: A unifying framework for reasoning. Artiﬁcial Intelligence, 113(1-2), 41 85.

Domshlak, C., & Brafman, R. (2002). CP-nets: Reasoning and consistency testing. In Proc. 8th International Conference on Principles of Knowledge Representation and Reasoning (KR).

Faltings, B., Torrens, M., & Pu, P. (2004). Solution generation with qualitative models of preferences. Computational Intelligence, 20(2), 246 263.

Fidha, S. E., & Amor, N. B. (2015). Probabilistic weighted CP-nets. In Intelligent Decision Technologies: Proceedings of the 7th KES International Conference on Intelligent Decision Technologies (KES-IDT 2015), pp. 159 169.

F urnkranz, J., & H ullermeier, E. (2010). Preference Learning: An Introduction. Springer.

Goldsmith, J., Lang, J., Truszczynski, M., & Wilson, N. (2008). The computational complexity of dominance and consistency in CP-nets. Journal of Artiﬁcial Intelligence Research (JAIR), 33(1), 403 432.

Gonzales, C., & Perny, P. (2004). GAI networks for utility elicitation.. In Proc. of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR).

Haret, A., Novaro, A., & Grandi, U. (2018). Preference aggregation with incomplete cp-nets. In Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR).

Lang, J., Pini, M., Rossi, F., Venable, K., & Walsh, T. (2007). Winner determination in sequential majority voting. In Proc. of the 20th International Joint Conference on Artiﬁcial Intelligence (IJCAI).

Lang, J., & Xia, L. (2009). Sequential composition of voting rules in multi-issue domains. Mathematical Social Sciences, 57(3), 304 324.

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

Lang, J., & Mengin, J. (2009). The complexity of learning separable ceteris paribus preferences. In Proceedings of 21st International Joint Conference on Artiﬁcial Intelligence (IJCAI).

Li, H. (2011). A short introduction to learning to rank. IEICE Transactions, 94-D(10), 1854 1862.

Li, M., Vo, Q., & Kowalczyk, R. (2010). An efﬁcient procedure for collective decision-making with CP-nets. In Proc. of the 19th European Conference on Artiﬁcial Intelligence (ECAI).

Li, M., Vo, Q., & Kowalczyk, R. (2011). Majority-rule-based preference aggregation on multiattribute domains with CP-nets. In Proc. of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS).

Loreggia, A., Mattei, N., Rossi, F., & Venable, K. B. (2018a). On the distance between CP-nets. In Proceedings of the 17th International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS).

Loreggia, A., Mattei, N., Rossi, F., & Venable, K. B. (2018b). Value alignment via tractable preference distance. In Yampolskiy, R. V. (Ed.), Artiﬁcial Intelligence Safety and Security. CRC Press.

Loreggia, A., Mattei, N., Rossi, F., & Venable, K. B. (2019). Cpmetric: Deep siamese networks for metric learning on structured preferences. In Seghrouchni, A. E. F., & Sarne, D. (Eds.), IJCAI 2019 International Workshops, Revised Selected Best Papers, Vol. 12158 of Lecture Notes in Computer Science, pp. 217 234. Springer.

Lukasiewicz, T., Martinez, M., & Simari, G. (2014). Probabilistic preference logic networks.. In Proceedings of the 21st European Conference on Artiﬁcial Intelligence (ECAI 2014), pp. 561 566.

Lukasiewicz, T., & Malizia, E. (2016). On the Complexity of m CP-nets. In Proceedings of the 30th AAAI Conference on Artiﬁcial Intelligence (AAAI-2016).

Maran, A., Maudet, N., Pini, M., Rossi, F., & Venable, K. (2013). A framework for aggregating inﬂuenced CP-nets and its resistance to bribery. In Proc. of the 27th AAAI Conference on Artiﬁcial Intelligence (AAAI).

Marden, J. I. (1995). Analyzing and Modeling Rank Data. CRC Press.

Mattei, N., Narodytska, N., & Walsh, T. (2014). How hard is it to control an election by breaking ties?. In Proceedings of the 21st European Conference on Artiﬁcial Intelligence (ECAI), pp. 1067 1068.

Mattei, N., Pini, M. S., Rossi, F., & Venable, K. B. (2012). Bribery in voting over combinatorial domains is easy. In Proceedings of the 11th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).

Mattei, N., Pini, M. S., Rossi, F., & Venable, K. B. (2013). Bribery in voting with CP-nets. Annals of Mathematics and Artiﬁcial Intelligence, 68(1 3), 135 160.

Mattei, N., & Walsh, T. (2013). Pref Lib: A library for preferences, HTTP://WWW.PREFLIB.ORG. In Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT).

Mattei, N., & Walsh, T. (2017). A PREFLIB.ORG Retrospective: Lessons Learned and New Directions. In Endriss, U. (Ed.), Trends in Computational Social Choice, chap. 15, pp. 289 309. AI Access Foundation.

REASONING WITH PCP-NETS

Obraztsova, S., & Elkind, E. (2011). On the complexity of voting manipulation under randomized tie-breaking. In Proceedings of 22nd International Joint Conference on Artiﬁcial Intelligence IJCAI, pp. 319 324.

Obraztsova, S., Elkind, E., & Hazon, N. (2011). Ties matter: Complexity of voting manipulation revisited. In Proceedings of the 10th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pp. 71 78.

Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann.

Pigozzi, G., Tsoukis, A., & Viappiani, P. (2015). Preferences in artiﬁcial intelligence. Annals of Mathematics and Artiﬁcial Intelligence, 77(3), 361 401.

Price, R., & Messinger, P. R. (2005). Optimal recommendation sets: Covering uncertainty over user preferences. In Proc. 20th AAAI Conference on Artiﬁcial Intelligence, pp. 541 548.

Pu, P., Faltings, B., Chen, L., Zhang, J., & Viappiani, P. (2011). Usability guidelines for product recommenders based on example critiquing research. In Ricci, F., Rokach, L., Shapira, B., & Kantor, P. B. (Eds.), Recommender Systems Handbook, pp. 511 545. Springer.

Regenwetter, M., Dana, J., & Davis-Stober, C. (2011). Transitivity of preferences. Psychological Review, 118(1), 42.

Regenwetter, M., Dana, J., & Davis-Stober, C. P. (2010). Testing transitivity of preferences on two-alternative forced choice data. Frontiers in psychology, 1, 148.

Regenwetter, M., & Davis-Stober, C. P. (2012). Behavioral variability of choices versus structural inconsistency of preferences. Psychological Review, 119(2), 408.

Rossi, F., & Mattei, N. (2019). Building ethically bounded AI. In Proceedings of the 33rd AAAI Conference on Artiﬁcial Intelligence (AAAI).

Rossi, F., Venable, K., & Walsh, T. (2004). m CP-nets: representing and reasoning with preferences of multiple agents. In Proc. of the 19th AAAI Conference on Artiﬁcial Intelligence (AAAI).

Rossi, F., Venable, K., & Walsh, T. (2011). A Short Introduction to Preferences: Between Artiﬁcial Intelligence and Social Choice. Morgan & Claypool Publishers.

Roth, A., & Kagel, J. (1995). The Handbook of Experimental Economics, Vol. 1. Princeton University Press Princeton.

Santhanam, G. R., Basu, S., & Honavar, V. (2010). Dominance testing via model checking.. In Proc. of the 24th AAAI Conference on Artiﬁcial Intelligence (AAAI).

Sikdar, S., Adali, S., & Xia, L. (2017). Optimal decision making with CP-nets and PCP-nets. In Proceedings of the 16th International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS).

Wang, H., Zhang, J., Sun, W., Song, H., Guo, G., & Zhou, X. (2012). WCP-nets: A weighted extension to cp-nets for web service selection. In Service-Oriented Computing: 10th International Conference (ICSOC 2012), pp. 298 312.

Xia, L., Conitzer, V., & Lang, J. (2008). Voting on multiattribute domains with cyclic preferential dependencies.. In Proc. of the 23rd AAAI Conference on Artiﬁcial Intelligence (AAAI).

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

Xia, L., Conitzer, V., & Lang, J. (2011). Hypercubewise preference aggregation in multi-issue domains. In Proc. of the 22nd International Joint Conference on Artiﬁcial Intelligence (IJCAI).

REASONING WITH PCP-NETS

Appendix A. Proofs

Theorem 1. Given a PCP-net Q with features with binary domains, the probability of an edge e p X, Y q can be computed as follows:

v PE Prσpvq|vxs Prσpvq|v xs

where Υ tσ : E Ñ ty ą y, y ą yuu is the set of all possible functions σ that associate to each element v P E an element of the set ty ą y, y ą yu (the set of all the possible total orders of the domain of Y ). Proof. We equivalently prove that the probability of nonexistence of the edge e p X, Y q is:

v PE Prσpvq|vxs Prσpvq|v xs

To prove the formula, we have to reason about the particular conﬁgurations of the PCP-table of Y that induce CP-nets that do not have the edge e. A node X is not a parent of Y exactly when (by deﬁnition of a parent) for each conﬁguration v of the other parents, the preference over Y is the same for vx and for v x. Given σ, a mapping from each element v P E to a total order over the domain of Y , this happens with probability

Prσpvq|vxs Prσpvq|v xs

for each conﬁguration v. Since all the rules are independent (per deﬁnition of a PCP-net), this happens with probability: ź

v PE Prσpvq|vxs Prσpvq|v xs

for each σ. Since different σ s concern different CP-nets, this happens with probability

v PE Prσpvq|vxs Prσpvq|v xs

Theorem 2. The probability of the edge e p X, Y q can be computed as follows:

v PE Prσpvq|vx1s Prσpvq|vx2s Prσpvq|vxds

where DX tx1, x2, , xdu, Θp Y q is the set of all the possible total orders of the domain of Y and Υ tσ : E Ñ Θp Y qu is the set of all possible functions σ that associate to each elementv P E a total order over the domain of Y (an element of the set Θp Y q). Proof. The proof follows step by step the proof of the binary case. l

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

Theorem 3. Given a PCP-net Q and its set of induced CP-nets, then:

1. The probability of realizing one of its induced CP-nets is the joint probability of the corresponding assignment in the G-net for Q;

2. The probability distribution deﬁned in Deﬁnition 8 over the set of induced CP-nets is a well deﬁned discrete probability distribution (i.e., the probabilities over the domain elements sum to one and the probability of each element belongs to the interval r0, 1s).

3. The most probable induced CP-nets correspond to the CP-nets associated (using the one-toone correspondence between induced CP-nets and assignment of the corresponding G-nets described above) to the assignment of the G-net for Q, with maximal joint probability.

1. The ﬁrst statement of this theorem follows from the fact that we take exactly the product of the chosen rows in the PCP-tables.

2. The probability deﬁned in the ﬁrst statement is computed as a product of non-negative factors, thus it is non-negative. Moreover, the sum of the probabilities of all the CP-nets in the set of the induced CP-nets is equal to 1, because there s a 1-1 correspondence between the assignments of the G-net with positive (not zero) probability and the induced CP-nets, and the sum of the probabilities of all the assignments of a BN is equal to 1.

3. This statement follows directly from the ﬁrst one. l

Theorem 4. Given a probability distribution over a set of CP-nets (even if they have the same dependency graph), there may exist no PCP-net inducing it. Proof. Consider the following two CP-nets over two variables X1 and X2:

p C1, 0.5q: px1 ą x1q and px2 ą x2q

p C2, 0.5q: p x1 ą x1q and p x2 ą x2q.

The PCP-net representing such a collection of CP-nets must satisfy the following system of equations, where q pq1, q2q, q1 is the probability of x1 ą x1, q2 is the probability of x2 ą x2: # fp C1p qq q1q2 fp C2p qq p1 q1qp1 q2q ñ

# fp C1p qq 0.5 fp C2p qq 0.5. This system has no solution for q P r0, 1s2 (it has only complex solutions). l

Theorem 5. Given a probability distribution over a set of CP-nets deﬁned over the same features, if this distribution is generated by a PCP-net Q, then we can write a system of non-linear equations that provides a unique solution that uniquely recovers the PCP-net Q. Proof. It is equivalent to prove that, if the system generated by a probability distribution over a set of CP-nets has a solution, it is unique. We consider a PCP-net and then, to compute the probabilities, we consider the G-net associated. We suppose that the G-net has n variables X1, X2, ..., Xn with domains D1 ta1 j: for j 1 to

REASONING WITH PCP-NETS

k1u, ... , Dn tan j : for j 1 to knu (the values of ai j can be either an order, or 0 or 1). We deﬁne pi j as the probability Pp Xi ai jq. Our system of equations (by deﬁnition) contains the numerical values of all the joint probabilities of every assignment to the n variables. We suppose now that there are two distinct solutions pi j and pi j (@i 1, ..., n and @j 1, ..., ki). We know that pi j is equal to:

tn 1 Pp X1 a1 t1, .., Xi 1 ai 1 ti 1, Xi ai j, Xi 1 ai 1 ti 1, .., Xn an tnq.

But all the numerical values of the joint probabilities are known (for all assignments of the n variables), so all the probabilities:

Pp X1 a1 t1, .., Xi 1 ai 1 ti 1, Xi ai j, Xi 1 ai 1 ti 1, .., Xn an tnq

are known as well. Let us consider the value of pi j, which we call it bi j. Now since both pi j and pi j are equal to bi j, they coincide. This allows us to conclude that there is a unique solution. l

Theorem 6. Given a PCP-net Q and its Opt-net:

1. There is a one-to-one correspondence between the assignments (with non-zero probability) of the Opt-net and the outcomes that are optimal in at least one induced CP-net of Q.

2. Given a PCP-net Q, the probability that an outcome is optimal is the joint probability of the corresponding assignment in the Opt-net (we consider only the assignments of the Opt-net with positive probability). If no such corresponding assignment exists, then the probability of being optimal is 0.

3. To ﬁnd the most probable optimal outcome for a PCP-net Q, it is sufﬁcient to compute the assignment that maximizes the joint probability on the Opt-net.

1. True by construction.

2. By construction, the set of assignments of the Opt-net is a subset of those of Q. By the deﬁnition of the Opt-net, if an assignment of Q is not an assignment of the Opt-net then it cannot be optimal in any induced CP-net.

Let us now focus only on the subset of assignments of Q that have a corresponding assignment in the Opt-net. Let x px1, x2, ..., xnq be one of these assignments. We denote by Poptpxq Pp X1 x1, ..., Xn xnq the joint probability of x in the Opt-net. We recall that the probability that x is optimal in the PCP-net is the sum of the probabilities of the induced CP-nets that have assignment x as optimal. We call this probability Pcppxq. Thus we want to prove that Poptpxq Pcppxq .

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

Let us consider Ax, the set of induced CP-nets that have x as their optimal assignment. Thus we have: Pcppxq ÿ

CPAx Pp Cq .

To compute the optimal value for an induced CP-net C, the sweep-forward procedure does not consider all the rows of the CP-tables, but only a subset of them. For example in the CP-net with two variables Y and Z with the cp-tables: y1 ą y2, y1 : z1 ą z2 ą z3 and y2 : z2 ą z3 ą z1, the sweep-forward procedure will consider only the ﬁrst two and not y2 : z2 ą z3 ą z1. So, we can split the CP-tables of C into two parts, one affecting the choice of the optimal outcome (denoted with C ) and one not used by the sweep-forward procedure (denoted with C ). In the example above we will have C ty1 ą y2, y1 : z1 ą z2 ą z3u and C ty2 : z2 ą z3 ą z1u.

Since each row in the CP-tables of an induced CP-net is associated with a probability (the probability of that row in the PCP-net) and contributes to deﬁne the probability of the induced CP-net, we can divide the induced CP-net probability in two independent parts: one is the product of the rows that are used in the sweep-forward procedure (the product of the probabilities of the rows belonging to C , that we will denote as Pp C q) and one as the product of the rows that are not used in the sweep-forward procedure (the product of the probabilities of the rows belonging to C , that we will denote as Pp C q):

Pp Cq Pp C q Pp C q .

Thus we have that: Pcppxq ÿ

CPAx Pp Cq ÿ

CPAx Pp C q Pp C q .

We observe now that the optimal outcome x can be produced in many different ways, as there can be many different orderings that produce the same result (all these orderings belonging to C and not to C ). For example, considering an independent variable Y , the orderings y1 ą y2 ą y3 and y1 ą y3 ą y2 both produce the optimal value y1, but in different ways. For this reason we consider a partition (Ax,1, ..., Ax,t) of the set Ax (the set of induced CP-nets that produce the same optimal outcome x) such that each induced CP-net belonging to the same equivalence class produces the same optimal outcome in the same way. This means that given two CP-nets D and E that belong to the same equivalence class Ax,i, they have the same rows that actively affect the choice of the optimal value and differ only in the remaining part, namely D E and D E .

We now deﬁne as Ci the part that is equal for all the members of the equivalence class Ax,i. That means: Ci č

CPAx,i C C @C P Ax,i .

Then we can rewrite the probability Pcppxq as:

Pp C q Pp C q

Pp Ci q Pp C q

CPAx,i Pp C q .

REASONING WITH PCP-NETS

We observe now that: ÿ

CPAx,i Pp C q 1 @i 1, ..., t

since we are summing the probabilities of all possible cases (the entire distribution) in the part C (the part not inﬂuencing the sweep-forward procedure). Thus, the probability becomes

i 1 Pp Ci q .

We notice now that the joint probability in the Opt-net Pp X1 x1, ..., Xn xnq corresponds exactly to řt i 1 Pp Ci q by contruction. We recall that we built the rows of the probability tables for the variables X1, ..., Xn by summing the probabilities of the orderings that have the same head (ﬁrst ranked value) in the PCP-net Q. This is the same as summing the probabilities Pp Ci q over the subset Ax,i.

Thus we proved that Pcppxq Poptpxq.

3. This statement is an immediate consequence of the previous two. l

Lemma 1. Given an acyclic CP-net C with n nodes and two outcomes o o1o2 on and o1 o1 1o1 2 o1 n such that o ą o1 and given i an index in t1, , nu such that oi o1 i and oj o1 j@j ă i then oæX1 Xj ą o1æX1 Xj @j ě i.

Proof. Because of o ą o1, there exists a worsening path from o to o1: P o, o1, o2, , o1. We prove that PæX1, ,Xj oæX1, ,Xj, o1æX1, ,Xj, , o1æX1, ,Xj is a worsening path from oæX1, ,Xj to o1æX1, ,Xj (considering only non-repeated outcomes in the projected space t X1, , Xju, thus removing from PæX1, ,Xj the repetition steps in which oiæX1, ,Xj oi 1æX1, ,Xj). We have to prove that each step of PæX1, ,Xj is a worsening ﬂip. Considering a ﬂip of the value of variable Xl, the fact that it is a worsening step does not depend on the values of Xl s children or of the values of the nodes that are independent of Xl. All the nodes Xj 1, , Xn are either children or nodes (conditionally) independent of Xl. Thus, removing Xl does not change the preferences for the outcomes restricted to the variables X1, , Xj. Thus, each worsening ﬂip oi ą oi 1 in the path P, it is also a worsening ﬂip in the path PæX1, ,Xj (unless oiæX1, ,Xj oi 1æX1, ,Xj). We proved that each step in the path PæX1, ,Xj obtained from P and projecting on the variables X1, , Xj without repetitions is a worsening path from oæX1 Xj to o1æX1 Xj. l

Lemma 2. Given an acyclic CP-net C with n nodes and two outcomes o and o1, if there exists an index i P t1, , nu such that oæX1 Xi o1æX1 Xi then we have that oæX1 Xj o1æX1 Xj for each index j between i and n (i ď j ď n).

Proof. We prove the lemma by contradiction. Suppose that oæX1 Xj o1æX1 Xj, then either oæX1 Xj ą o1æX1 Xj or oæX1 Xj ă o1æX1 Xj. We suppose oæX1 Xj ą o1æX1 Xj (the other case is analogous). Since oæX1 Xj ą o1æX1 Xj there exists a worsening path P from oæX1 Xj to o1æX1 Xj and P oæX1 Xj, o1æX1 Xj, , o1æX1 Xj. From Lemma 1 we have that @k P

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

t1, , ju oæX1, ,Xk ě oæX1, ,Xk because the path PæX1, ,Xk oæX1, ,Xk, o1æX1, ,Xk, , o1æX1, ,Xk is a worsening path from oæX1, ,Xk to o1æX1, ,Xk in the sub-CP-net of the nodes X1, , Xk, in particular for k i. Thus, oæX1 Xi ą o1æX1 Xi. That is a contradiction. l

Lemma 3. Given an acyclic CP-net C with n nodes and two outcomes o and o1, then o o1

if and only if there exists index i P t1, , nu such that oæX1 Xj o1æX1 Xj @j ă i and oæX1 Xl o1æX1 Xl @l ě i.

Proof. ð Consequence of Lemma 2. ñ We suppose o o1 and prove that exists index i such that

oæX1 Xj o1æX1 Xj @j ă i and

oæX1 Xl o1æX1 Xl @l ě i

by induction on the number of variables. Base case: The base case for induction considers two variables A and B (in the case of 1 variable, i 1). In the case in which there is an edge between them, there are no incomparable outcomes. Thus we consider only the cases in which there is no edge between the two variables. We have four cases for the CP-tables:

a ą a and b ą b, which implies that a b ab

a ą a and b ą b, which implies that a b ab

a ą a and b ą b, which implies that a b ab

a ą a and b ą b, which implies that a b ab.

In each we obtain i 2. Induction step: Supposing the lemma holds for n variables, we prove it for n 1. We consider a CP-net with n 1 variables in which o o1. We consider oæX1, ,Xn and o1æX1, ,Xn. We can have three cases:

1. oæX1, ,Xn ą o1æX1, ,Xn

2. oæX1, ,Xn ă o1æX1, ,Xn

3. oæX1, ,Xn o1æX1, ,Xn

In Case 3 we can apply the induction hypothesis. Cases 1 and 2 are symmetric so we will just prove Case 1. We observe that oæX1, ,Xn o1æX1, ,Xn, because otherwise the two outcome o and o1 are a ﬂipping pair, which are never incomparable. We consider the case in which o o1 and oæX1, ,Xn ą o1æX1, ,Xn. We have to prove that @j ă n oæX1, ,Xj ą o1æX1, ,Xj. We prove it by contradiction.

Suppose that Dj ă n such that oæX1, ,Xj o1æX1, ,Xj. We apply Lemma 2 and we obtain that oæX1, ,Xn o1æX1, ,Xn is also a contradiction.

REASONING WITH PCP-NETS

Suppose that Dj ă n such that oæX1, ,Xj ă o1æX1, ,Xj. Thus, there is a worsening path P from oæX1, ,Xn to o1æX1, ,Xn. Considering P restricted to the variables X1, , Xj we obtain P that is a worsening path from oæX1, ,Xj to o1æX1, ,Xj. That is a contradiction. l

Lemma 4. Given an acyclic CP-net C with n nodes formed by two connected components4 C1 and C2, and given two different outcomes o and o1 such that rpoæC1 ą o1æC1 and oæC2 ă o1æC2q or poæC1 ă o1æC1 and oæC2 ą o1æC2qs then o o1.

Proof. We prove only the case in which oæC1 ą o1æC1 and oæC2 ă o1æC2, because the other one is symmetric. We suppose by contradiction that o o1. Then we can have either o ą o1 or o ă o1. We suppose o ą o1 (the other case is analogous). Since o ą o1 there exists a worsening path P from o to o1, P o, o1, o2, , o1. Each step oi of the path correspond to a worsening ﬂip of a variable Xj that belongs either to C1 or to C2. Thus, the two sub-paths P1 and P2 such that:

P1 PæC1 oæC1, o1æC1, o2æC1, , o1æC1

P2 PæC2 oæC2, o1æC2, o2æC2, , o1æC2

are paths (with repetition) such that P1 is a worsening path from oæC1 to o1æC1 in CP-net C1 and P2 is a worsening path from oæC2 to o1æC2 in CP-net C2. We obtain that oæC1 ą o1æC1 and oæC2 ą o1æC2. That is a contradiction. l

Theorem 7. Given a polytree-structured CP-net C with n variables and two outcomes o and o1, if for all Xi in Diff (see Deﬁnition 15) there exists an assignment ui P Uo,o1 i (see Deﬁnition 15) such that ui : oæXi ą o1æXi then o ą o1. Proof. Let s order the variables such that for each variable Xi then Xj P Pap Xiq implies that j ă i. Such an order always exists since the CP-net is polytree-shaped. Moreover, it is possible that there exists more than one. We will take a random order ω between those. We prove by contradiction that o ą o1. We have to consider two cases: o ă o1 and o o1:

Let s suppose o ă o1.

Considering the ﬁrst variable X i in Diff following the order ω, from Lemma 1 and o ă o1 we have that oæX1 Xj ă o1æX1 Xj @j ě i. In particular oæX1 X i ă o1æX1 X i.

We notice that Uo,o1 i has only one element: Uo,o1 i toæPap X iq o1æPap X iqu. Thus, for all the

assignments in Uo,o1 i (only one in this case: u i) we have that u i : oæX i ą o1æX i. This is in contradiction with our hypothesis, since we proved that there exists a variable Xi in Diff such that for all the assignments ui P Uo,o1 i the following does not hold: ui : oæXi ą o1æXi.

Let s now suppose o o1.

By Lemma 3 we have that there exists an index i P t1, , nu such that

oæX1 Xj o1æX1 Xj @j ă i and oæX1 Xl o1æX1 Xl @l ě i .

4. Connected components are subgraphs in which any two vertices are connected to each other by an undirected paths; there are no edges connecting nodes belonging to different connected components.

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

Let s consider the case in which is equal to ą.

We do not consider the other case (with equal to ă) because this would lead to an immediate contradiction.5

So, given that is equal to ą, we can suppose that oæX1 X i 1 ą o1æX1 X i 1.6

We will prove now that also oæX1 X i ą o1æX1 X i, which is a contradiction to our hypothesis of oæX1 X i o1æX1 X i.

Let s consider two cases assuming that X i P Diff:7 the case in which X i is an independent node and the case in which it is a dependent node.

X i is an independent node. Let s consider a worsening path P from oæX1, ,X i 1 to o1æX1, ,X i 1:

P oæX1, ,X i 1 Ñ O1 Ñ O2 Ñ Ñ o1æX1, ,X i 1 .

Then it is easy to ﬁnd a worsening path from oæX1, ,X i to o1æX1, ,X i given the assump-

tion that for all Xi in Diff there exists an assignment ui P Uo,o1 i such that ui : oæXi ą o1æXi. In this case X i P Diff. and Uo,o1 i H and thus oæX i ą o1æX i. Thus one possible worsening path would be:

P oæX1, ,X i 1oæX i Ñ O1oæX i Ñ O2oæX i Ñ

Ñ o1æX1, ,X i 1oæX i Ñ o1æX1, ,X i 1o1æX i .

leading to the contradiction that oæX1 X i ą o1æX1 X i.

Now we consider the case in which X i is not an independent node. Because C is polytree-structured, the sub-CP-net C of the nodes X1, , X i 1 is formed by |Pap X iq| connected components,8 each one containing exactly one parent of X i. Without lack of generality, we can assume that we picked the order ω that has all the siblings of X i appearing after i in the order.

In this case, for each u P Uo,o1 i we can have a worsening path P from oæX1, ,X i 1 to o1æX1, ,X i 1 that contains u. This is because the parents belong to different connected components and we can permute, in the worsening path, the order in which we make the worsening ﬂips of the variables in the single connected components (as a consequence of Lemma 4 and the fact that all the siblings of X i appearing after i in the order ω).

5. For the ﬁrst variable in Diff (X i, following the order ω) we have that there exists an assignment ui P U o,o1

i such that ui : oæXi ą o1æXi. Since X i is the ﬁrst variable to change in the order then ui oæP ap X iq o1æP ap X iq. Moreover since X i is the ﬁrst variable to change in the order, this implies that also oæX1 X i ą o1æX1 X i. This is in contradiction with oæX1 X i 1 ă o1æX1 X i 1 by the application of Lemma 1. 6. For Lemma 1 we have also that oæX1 Xj ě o1æX1 Xj @j ă i Thus, we obtain that: oæX1 Xj ą o1æX1 Xj @j ă i and oæX1 Xl o1æX1 Xl @l ě i . 7. We make this assumption because the other case would lead to an immediate contradiction: X i R Diff implies that oæX i o1æX i and thus since oæX1 X i 1 ą o1æX1 X i 1 also oæX1 X i ą o1æX1 X i. 8. We recall that connected components are subgraphs in which any two vertices are connected to each other by an undirected paths; there are no edges connecting nodes belonging to different connected components.

REASONING WITH PCP-NETS

Thus for each u P Uo,o1 i there exists a worsening path P containing u:

P oæX1, ,X i 1 Ñ o1 Ñ o2 Ñ Ñ ol Ñ Ñ o1æX1, ,X i 1 .

Now consider u i such that u i : oæX i ą o1æX i, which exists by hypothesis. Let s suppose that ol in the worsening path P contains u i: olæPap X iq u i. Therefore, we can create a worsening path from oæX1, ,X i to o1æX1, ,X i as follows:

P oæX1, ,X i 1oæX i Ñ o1oæX i Ñ o2oæX i Ñ

Ñ oloæX i Ñ olo1æX i Ñ Ñ o1æX1, ,Xij 1o1æX i

leading to the contradiction that oæX1 X i ą o1æX1 X i .

Thus we can conclude that o ą o1. l

Theorem 8. Given a PCP-net Q and two outcomes o and o1, PL Qpo ą o1q is a lower bound for PQpo ą o1q. Proof. Intuitively the lower bound value is just the probability that a randomly generated induced CPnet (from the PCP-net Q) satisﬁes the condition expressed in Theorem 7. Let s now prove it formally. We can rewrite the lower-bound formula (Equation 1) as:

PL Qpo ą o1q p1 ρ0qp1 ρ1q p1 ρmq (2)

where j 1, , m are indices that belongs to Diff (set of m indices (m ď n) of variables that change value from o to o1) and are ordered as in ω (an ordering of the PCP-net variables such that for each variable Xi, if Xj P Pap Xiq then j ă i). Equation 2 is equivalent to:

PL Qpo ą o1q p1 ρ0q rp1 ρ0qp ρ1qs rp1 ρ0qp1 ρ1qp ρ2qs

rp1 ρ0qp1 ρ1q p1 ρm 1qp ρmqs.

Let s consider the ﬁrst term 1 ρ0 (we rename this term q for simplicity). We will see now that q corresponds to the following probability:

q PpoæXdp0q ą o1æXdp0qq if Xdp0q is independent (3)

q PpoæXdp0q ą o1æXdp0q|uq if Xdp0q is not independent (4)

where dp q is a function such that d : Diff Ñ t1, , nu and dpjq is the corresponding index in t1, , nu of the index j P Diff following the order ω. This is because we notice that (from Deﬁnition 15):

if the variable Xdp0q is independent then: ρ0 Ppo1æXdp0q ą oæXdp0qq, so p1 ρ0q PpoæXdp0q ą o1æXdp0qq.

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

S1 S2 S3 . . . Sm

S0 (o ą o1 or o o1)

Induced CP-nets

CP-nets s.t. o o1

real value of dominance (CP-nets s.t.o ą o1)

lower bound: PL Qpo ą o1q

Figure 17: Sets S0 and S1 , Sm in the proof of Theorem 8

if Xdp0q is dependent on a set of parents Pap Xdp0qq, then the set Uo,o1

dp0q has only one element u oæPap Xdp0qq o1æPap Xdp0qq. Thus ρ0 Ppo1æXdp0q ą oæXdp0q|uq and p1 ρ0q PpoæXdp0q ą o1æXdp0q|uq.

Then Formula 2 is equivalent to:

PL Qpo ą o1q q q ρ1 qp1 ρ1qp ρ2q qp1 ρ1q p1 ρm 1qp ρmq (5)

where j 1, , m are indices that belong to Diff. We note that each term of the sum contains q. Considering o px1x2 xnq and o1 py1y2 ynq, the probability q is the probability in Q that xdp0q ą ydp0q (or xdp0q ą ydp0q|u) and corresponds to the probability that an induced CP-net has that row in their CP-tables. Let s call S0 the set of all the induced CP-nets that have that row in their CP-tables. We can think of q as the probability of an induced CP-net belonging to the set S0. For simplicity, in what follows, we will refer to q as the probability of the set S09 (and we will denote it as Pp S0q). We notice that when we restrict to the set S0, we restrict our attention to the induced CP-nets for which either o ą o1 or o o1.10 Moreover S0 contains all the induced CP-nets that have o ą o1

(this follows from Lemma 1), but only some of the induced CP-nets that have o o1 (since there could exist induced CP-nets with o o1 that have xdp0q ă ydp0q or xdp0q ă ydp0q|u).

Deﬁnition 23. We deﬁne now two different types of sets:

Sj: a set of induced CP-nets with probability Pp Sjq qp1 ρ1q p1 ρj 1qp1 ρjq. This set includes all the CP-nets with xdpiq ą ydpiq (or xdpiq ą ydpiq|u) for all the i ď j and, for

9. The probability Pp Sq of a set S of induced CP-nets corresponds to the sum of the probabilities of the CP-nets belonging to that set. 10. It is not possible that a CP-net in S0 has o ă o1 because all of the CP-nets in S0 contain the CPT row that says that xdp0q ą ydp0q (or xdp0q ą ydp0q|u). This follows from Lemma 1.

REASONING WITH PCP-NETS

Figure 18: Partition of set Sj into Sj 1 and Sj 1 in the proof of Theorem 8

the other indexes l not in Diff the set includes both the CP-net with xl ą yl (or xl ą yl|u) and with the opposite xl ă yl (or xl ă yl|u), in all possible combinations.

Sj: a set of induced CP-nets with probability Pp Sjq pqqp1 ρ1q p1 ρj 1qp ρjq. This set includes all the CP-nets with xdpiq ą ydpiq (or xdpiq ą ydpiq|u) for all the i ă j and ydpjq ą xdpjq (or ydpjq ą xdpjq|u). For the other indexes l not in Diff or in Diff but with dplq ą j the set includes both the CP-net with xl ą yl (or xl ą yl|u) and with the opposite xl ă yl (or xl ă yl|u), in all possible combinations.

Proof idea: The idea of this proof is to start with the set S0: the set that contains all the CP-nets with o ą o1 and some CP-nets with o o1. We then remove from S0 all the induced CP-nets with o o1 (since our goal is to have just the CP-nets that contribute to the dominance value o ą o1). To do so we consider Equation 5 and we consider a correspondence between sets of induced CP-nets and the probability of these sets. Each term of Equation 5 corresponds to the probability of the set Sj, a subset of S0. We will see that each set Sj contains all the CP-nets with o j o1 but might also contain few CP-net such that o ą o1 (so this is a lower bound). See Figure 17 for a visualization of this concept. If we think of a generic j-term of Equation 5 as the probability of the set Sj we can rewrite Equation 5 as:

PL Qpo ą o1q Pp S0q

j 1 Pp Sjq P S0z

j 1 Sj Pp Smq .

where j 1, , m are indices that belong to Diff. We have the following assumptions:

1. Sj and Sj are a partition of the set Sj 1 for each j P t1, , mu Diff (which implies that Sj X Sj H @j P t1, , mu and that Sj, Sj Ă S0 @j P t1, , mu )

2. each set Sj contains all the induced CP-nets that are incomparable for index dpjq (o dpjq o1, see Deﬁnition 16), and oæX1, ,Xdpjq 1 ą o1æX1, ,Xdpjq 1

We will now prove the two conditions described above:

1. Sj and Sj are a partition of the set Sj 1 (Figure 18):

This is true by construction (considering the correspondence between the probability of an induced CP-net and the choice of its cp-tables) and follows from Deﬁnition 23.11

11. Thus we do not remove the same CP-net more than once from the set S0, because we are removing partitions. In particular, since we are removing the probability of the j-term of the sum, we remove the probability of the set Sj. The ﬁnal probability that we obtain is the probability of the set Sm (as we can see from the ﬁrst formulation of the formula: Equation 2).

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

2. Sj contains all the induced CP-nets that have o o1 for index dpjq and oæ1, ,dpjq 1 ą o1æ1, ,dpjq 1:

First we note that, since Sj are subset of S0, they can only contain induced CP-nets such that o o1 or o ą o1. Moreover, we know that all the induced CP-nets P S0 that have o o1

satisfy the following:

there exists an index l such that o l o1 (for Lemma 1);

oæ1, ,l 1 ą o1æ1, ,l 1 (it cannot be ă because of Lemma 3).

We will now prove that Sj contains all the induced CP-nets that have o dpjq o1 but we cannot exclude that it might also contain few CP-nets such that o ą o1. We show that, given an induced CP-net C and two outcomes o and o1, such that o dpjq o1 then C P Sj. We know that C P S0, thus there are three options for C:

(a) C P Sl with l ă j;

(b) C P Sj;

(c) C P Sj.

We show now that:

C R Sj: Suppose that C P Sj, that is the set of the CP-nets with oæXdpiq ą o1æXdpiq (or oæXdpiq ą o1æXdpiq|u) for all the i ď j. In particular this is true for the index j: oæXdpjq ą o1æXdpjq (or oæXdpjq ą o1æXdpjq|u). Moreover, since o and o1 are incomparable for index dpjq, then oæX1, ,Xdpjq 1 o1æX1, ,Xdpjq 1. Then we know that in this case corresponds to ą (see comment above). We can now apply Theorem 7 and conclude that also oæX1, ,Xdpjq ą o1æX1, ,Xdpjq, which is a contradiction.

C R Sl with l ă j: Suppose that C P Sl with l ă j, this implies that o and o1 are incomparable for dplq ă dpjq and it is a contradiction given the assumption that dpjq is the minimum index for the incomparability.

Thus we can conclude that C P Sj.

Theorem 9. Given a separable PCP-net Q over n features X1, , Xn with binary domains Di txi, xiu@i P t1, , nu and given two outcomes o and o1 then

i PDiff po,o1q pi

j PDiff po,o1q p1 pjq

where pi Ppxi ą xiq in the PCP-net (and thus p1 piq Pp xi ą xiq) and where Diff and Diff

are a partition of Diff. Diff is the set of indexes of variables such that oæXi xi and o1æXi xi and Diff is the set of indexes of variables such that oæXi xi and o1æXi xi .

REASONING WITH PCP-NETS

Proof. We call Ip Qq the set of CP-nets induced by Q, and Op Cq the partial order deﬁned by a CP-net C. We know that Ppo ą o1q ÿ

CPIp Qq s.t. poąo1q POp Cq

Now we show that:

1. if i P Diff po, o1q then the induced CP-nets that have xi ą xi don t have o ą o1 in their partial order over the features (o č o1).

2. if i P Diff po, o1q then the induced CP-nets that have xi ą xi don t have o ą o1 in their partial order over the features (o č o1).

We prove only the ﬁrst assertion because the second is symmetric. We suppose that i P Diff po, o1q. We must have a chain of worsening ﬂips from o to o1, such that o ą o1. We consider o pyxizq and o1 py1 xiz1q where y and y1 are the assignments of the variables X1, , Xi 1 and z and z1 are the assignments of the variables Xi 1, , Xn respectively of o and o1. Because the features are all independent, to have a chain of worsening ﬂips from o to o1 we must have a chain of worsening ﬂips from y to y1, from z to z1 and for xi to xi. But, in some induced CP-nets that have xi ą xi, the ﬁrst two may be possible, but the third one is an improvement. Thus, the induced CP-nets with xi ą xi have no chains of worsening ﬂips from o to o1. Thus, we have to consider only the induced CP-nets that for all the features i P Diff po, o1q have xi ą xi, and for all the features i P Diff po, o1q have xi ą xi.

Ppo ą o1q ÿ

CPIp Qq s.t. pxią xiq@i PDiff po,o1q p xiąxiq@i PDiff po,o1q

We now observe that all of these induced CP-nets have po ą o1q P Op Cq. That is because the variables xj R p Diff po, o1q Y Diff po, o1qq have the same values in o and o1, and so we can build a chain of worsening ﬂip for the variables xj P p Diff po, o1q Y Diff po, o1qq by deﬁnition, while holding the other variables ﬁxed.

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

We can compute the probability Ppo ą o1q:

Ppo ą o1q ÿ

CPIp Qq s.t. pxią xiq @i PDiff po,o1q p xiąxiq @i PDiff po,o1q

CPIp Qq s.t. pxią xiq @i PDiff po,o1q p xiąxiq @i PDiff po,o1q

j s.t. xją xj pj ź

j s.t. xjąxj p1 pjq

i PDiff po,o1q pi ź

i PDiff po,o1q p1 piq

CPIp Qq s.t. pxią xiq @i PDiff po,o1q p xiąxiq @i PDiff po,o1q

j s.t. xją xj j RDiff po,o1q

j s.t. xjąxj j RDiff po,o1q

But we know that:

CPIp Qq s.t. pxią xiq @i PDiff po,o1q p xiąxiq @i PDiff po,o1q

j s.t. xją xj j RDiff po,o1q

j s.t. xjąxj j RDiff po,o1q

Thus we can conclude that:

i PDiff po,o1q pi

i PDiff po,o1q p1 piq

Theorem 10. Given a PCP-net Q with a separable dependency graph and two outcomes o and o1, then PQpo ą o1q PL Qpo ą o1q. Proof. We prove that the formula for the lower bound in the case of separable PCP-nets is equal to the formula described in Theorem 9. We observe that each formulation is a product of factors and each factor corresponds to a variable that has a different value in o and o1. Each variable that has a different value in o and o1 has a unique factor in each formulation. We prove that the factors that correspond to the same variable coincide in the two formulations. Suppose we have a PCP-net that has the following PCP-tables: Xi : xi ą xi, qi where qi is the probability Ppxi ą xiq.

REASONING WITH PCP-NETS

We consider two cases: the ﬁrst one is the case of a variable Xi such that oæXi xi and o1æXi xi. In the formulation of dominance for separable PCP-nets (Theorem 9), we have a factor that corresponds to qi because the variable Xi belongs to the set Diff po, o1q. In the lower bound formulation we have a factor that corresponds to:

p1 Ppo1æXi ą oæXiqq p1 Pp xi ą xiqq Ppxi ą xiq qi .

The second case is the case of a variable Xi such that oæXi xi and o1æXi xi. In the formulation of Theorem 9, we have a factor that corresponds to p1 qiq because the variable Xi belongs to the set Diff po, o1q. In the lower bound formulation we have a factor that corresponds to:

p1 Ppo1æXi ą oæXiqq p1 Ppxi ą xiqq 1 qi .

Thus, the two formulations coincide. l

Theorem 11. Given a PCP-net Q and two outcomes o and o1, PU Qpo ą o1q is an upper bound for PQpo ą o1q. Proof. It is enough to prove that all CP-nets induced by Q that support o ą o1 have the row u : oæXj ą o1æXj for all variables Xj P p Diff X FAq. We prove this sentence by contradiction: we consider an induced CP-net C that contains row u : o1æX ą oæX for X P p Diff X FAq and we prove that C |ù po1 ą oq _ po o1q. We have two cases: (1) X is an independent node. Then ﬂip oæX Ñ o1æX can t be a worsening ﬂip. That implies that all the worsening paths starting from o do not contain a ﬂip for variable X, so o1 can t be reached. (2) X is a dependent node. Thus, the set Ancp Xq t Xi1, , Xiku with k ě 1 and all of them have ﬁxed value on o and o1. We call u the assignment of Pap Xq in o and o1. Each worsening path from o to o1 has the value u for Pap Xq in each step of the path, because all the ancestors of X are ﬁxed. This implies that no worsening path from o to o1 contains other assignments for the parents of X. Thus, no worsening path starting from o contains a ﬂip for variable X, so o1 can t be reached. Thus C |ù po ą o1q and so C |ù po1 ą oq _ po o1q. l

Lemma 5. There exists a proﬁle of CP-nets P such that

t PROp Pq, PRIp Pqu X t LSOp Pq, LSIp Pqu H;

and there exists a proﬁle of CP-nets P 1 such that:

PROp P 1q PRIp P 1q;

and there exists a proﬁle of CP-nets P 2 such that:

LSOp P 2q LSIp P 2q.

First we prove that there exists a proﬁle of CP-nets P such that t PROp Pq, PRIp Pqu Xt LSOp Pq, LSIp Pqu H. Let us take the following proﬁle P of four CP-nets over two variables A and B:

CORNELIO, GOLDSMITH, GRANDI, MATTEI, ROSSI, & VENABLE

C1 with probability 0.095. C1 has an edge from X1 to X2 and CP-tables: x1 ą x1 and x1 : x2 ą x2, x1 : x2 ą x2.

C2 with probability 0.505. C2 has an edge from X1 to X2 and CP-tables: x1 ą x1 and , x1 : x2 ą x2, x1 : x2 ą x2.

C3 with probability 0.005. C3 does not have an edge from X1 to X2 and has CP-tables: x1 ą x1 and x2 ą x2.

C4 with probability 0.395. C4 does not have an edge from X1 to X2 and has CP-tables: x1 ą x1 and x2 ą x2.

Proportion gives us the PCP-net px1 ą x1, 0.6q and px1 : x2 ą x2, 0.51q, p x1 : x2 ą x2, 0.1q, while LS outputs px1 ą x1, 0.59q and px1 : x2 ą x2, 0.29q, p x1 : x2 ą x2, 0q. Thus we obtain that PROp Pq x1 x2, PRIp Pq x1x2, LSOp Pq x1 x2 and LSIp Pq x1 x2.

The fact that there exists proﬁles P 1 and P 2 such that PROp P 1q PRIp P 1q (or LSOp P 2q LSIp P 2q) is an immediate consequence of the fact that the most probable optimal outcome and the outcome of the most probable CP-net can be different. For example, consider a PCPnet on two variables X1 and X2 with the PCP-tables px1 ą x1, 0.6q, px1 : x2 ą x2, 0.6q and p x1 : x2 ą x2, 0q. The most probable induced CP-net has x1 ą x1, x1 : x2 ą x2 and x1 : x2 ą x2, thus x1x2 is the optimal outcome. However, the most probable optimal outcome of the PCP-net is x1 x2. Therefore, PRO (respectively, LSO) will differ from PRI (resp. LSI) on a proﬁle that produces this PCP-net. l

Theorem 12. Given a proﬁle of CP-nets, PRI produces the same result as sequential voting with majority. Proof. Consider a variable Xi with domain txi, xiu, and an assignment u for the parents of Xi. With sequential voting we choose the value of the domain that corresponds to the ﬁrst value of the ordering that maximizes the following:

max j Pt1, ,mutr ÿ

Cj:xią xi|u Pp Cjqs, r1 ÿ

Cj:xią xi|u Pp Cjqsu.

With PRI, we create a PCP-net that has, for the row in the PCP-table of Xi corresponding to assignment u for its parents, the probability ř Cj:xią xi|u Pp Cjq for xi ą xi and 1 ř Cj:xią xi|u Pp Cjq for xi ą xi. To compute the CP-tables of the most probable induced CP-net, we choose the orderings with maximal probability: for each variable Xi, given u, we choose the ordering that maximizes the following probability:

max j Pt1, ,mutr ÿ

Cj:xią xi|u Pp Cjqs, r1 ÿ

Cj:xią xi|u Pp Cjqsu.

To compute the optimal outcome of the most probable induced CP-net, we choose the greater literal in the ordering that appears in the CP-table, given u. This is for a generic variable Xi and assignment u, thus is true for all the variables and assignment of their parents. l

Theorem 13. The following holds:

REASONING WITH PCP-NETS

piq PRO, LSO, and LSI satisfy homogeneity;

piiq PRI and PRO satisfy participation.

piiiq PRI satisﬁes consensus and PRO satisﬁes consensus over a single feature.

Proof. iq For PRO, consider a proﬁle P p C1, f1q, , p Ck, fkq from which we can get the normalised frequencies p C1, f1

mq, , p Ck, fk

m q. Considering each CP-net N times, we obtain the following distribution over Nm CP-nets, P 1 p C1, Nf1q, , p Ck, Nfkq, with the following normalised frequencies p C1, Nf1

Nmq, , p Ck, Nfk

Nm q. The probability of a generic CP-net Ci in P 1 is Nfi Nm fi

m which is the same as the probability generated by P. For LSO, and LSI, consider the fact that if, in the previous proof, we added N copies of each CP-net to the original proﬁle it would result in the same probability distribution over the CP-nets. This fact is true for any collection of CP-nets, therefore, we generate the same set of equations to minimize in the deﬁnition of LS, and thus the same PCP-net solution. iiq We ﬁrst consider the case r PRI. We provide a proof for non-anonymous proﬁles, for ease of readability. The version for anonymous proﬁles can easily be deduced. Consider a proﬁle P p C1, , Cmq and an additional CP-net C. We have to prove that rp P Y t Cuq ąC rp Pq. PR gives us a PCP-net Q for P and a PCP-net Q1 for P Y t Cu. Since P and P Y t Cu are O-legal, let X be the ﬁrst variable according to O such that rp P Y t Cuq|X rp Pq|X and let u rp Pq|PAp Xq. This means that in the most probable induced CP-net of Q there is a preference statement u : rp Pq|X ą rp P Y t Cuq|X and in Q1 there is u : rp P Y t Cuq|X ą rp Pq|X. Thus the probability Pru : rp Pq|X ą rp P Y t Cuq|Xs ě 0.5 in Q, but ď 0.5 in Q1. This means that C has the row u : rp P Y t Cuq|X ą rp Pq|X in X s CP-table. Thus the outcome rp P Y t Cuq ěC rp Pq. A similar reasoning applies to the case r PRO. In the PCP-tables of Q1, the probabilities of the rows corresponding to the CP-tables of C increase with respect to Q. Thus, for each feature X and each assignment u of its parents, the probability to obtain the ﬁrst ranked value in the u rows of C CP-tables increases. This means that it improves the result for C. iiiq We ﬁrst consider the case r PRI. Consider proﬁle P and assume there is an alternative o s.t. o ąCi rp Pq@i P t1, , mu. Since P is O-legal, let X be the ﬁrst variable according to O such that o|X rp Pq|X. Let u be the assignment to X s parents in o and rp Pq (o|PAp Xq rp Pq PAp Xq since X is the ﬁrst variable according to O in which they differ). Since o ąCi rp Pq@i P t1, , mu, it must be that u : o|X ą rp Pq|X@Ci. Let us now consider the PCP-net Q obtained from P by PR. It is easy to see that in the PCP-table of X the probability of u : o|X ą rp Pq|X will be strictly higher than the probability of u : o|X ă rp Pq|X, which implies that the most probable induced CP-net must have the row ui : o|X ą rp Pq|X. The optimal outcome of the most probable induced CP-net must have the assignment o|X for the variable X because is ranked ﬁrst in the table in the u row. But rp Pq|X o|X and we have a contradiction. A similar reasoning applies to the case r PRO, but in a weaker version. We will prove that, for any proﬁle P, there is no alternative o such that o differs from rp Pq on only a single variable and o ąCi rp Pq@Ci. Assume that there were an alternative o such that o ąCi rp Pq, @Ci and o differs from rp Pq only on the variable X. The probability of u : o|X ą rp Pq|X in the PCP-table of X is equal to 1 because all the CP-nets in the proﬁle prefer o to rp Pq. Thus the probability of rp Pq is equal to 0, and we have a contradiction. l