Hypercubewise Preference Aggregation in Multi-Issue Domains

1 Introduction

In many multi-agent scenarios, the space of alternatives has a combinatorial structure: there are p issues to decide on, each issue i takes a value from a set Di, and n agents (voters) generally have preferential dependencies among these issues. In classical voting theory, voters submit their preferences as linear orders over the set of alternatives, and then a voting rule is applied to select a set of winning alternatives. However, when the set of alternatives has a multi-issue structure, the number of alternatives is exponential in the number of issues, and therefore, as soon as the number of issues is not very small, it is not realistic to ask voters to specify their preferences as explicit linear orders.

Several other ways of proceeding have been considered: (1) voting separately on each issue simultaneously, which is known to lead to severe "multiple election paradoxes" [2]; (2) limiting the set of alternatives that voters may vote for, which is quite arbitrary (who decides which alternatives are allowed?), and leads the voters to express their preferences on only a tiny fraction of the alternatives; (3) asking voters to report only a (small) part of their preference relation and applying a voting rule that needs this information only, such as Lirong Xia Department of Computer Science Duke University Durham, NC 27708, USA lxia@cs.duke.edu plurality, which is not always a bad idea, but the smaller the part of their preference relation voters express, the more likely it is that results will not be significant as soon as the number of issues is large (2p ≫ n); (4) imposing a domain restriction such as separability (which allows for using method (1) above), or a weaker restriction such as O-legality, which allows for deciding on the issues one after the other [7]; (5) using a compact preference representation language in which the voters' preferences are represented in a concise way; this method does not require any domain restriction, but leads to nontrivial computational issues.

In this paper, we take an approach that is intermediate between (3) and (5): we elicit only a part of the voters' preferences - however, not a small part of it, but still, a part significantly smaller than the explicit specification of the full preferences; and we use it to draw a (partial) preference relation, using the semantics of a preference representation language, namely CP-nets [1].

Group decision making in multi-issue domains via CP-net aggregation has been considered in a number of papers, which we briefly review in a structured (nonchronological) order. Rossi et al. [11] were the first to address the aggregation of CP-nets; given a collection of acyclic CP-nets, they define several aggregation functions mapping the preference relations induced by the individual CP-nets to a collective preference relation. This approach was pushed further by Li et al. [8], who give algorithms for computing Pareto-optimal alternatives with respect to the preference relations induced by the CP-nets, and fair alternatives with respect to a cardinalization of these preference relations. Another path is followed by Lang and Xia [7]; they also assume that the individual CPnets are acyclic, and furthermore share the same acyclic dependence graph, and study a family of sequential voting rules that consider the issues one after another, following the dependence graph. Xia et al. [12] take still another direction: they do not make any domain restriction on the individual CP-nets, rather they consider separately every set of "neighboring" alternatives differing only in the value of one issue, use a local voting rule for deciding the common preferences over this set, and finally, optimal outcomes are defined based on the aggregated CP-net. They also introduce the notion of local Condorcet winners, which are alternatives that beat each of their neighbors in a pairwise majority duel. The latter notion was studied further by Li et al. [9], who study some of its properties and propose (and implement) a SAT-based algorithm for computing them.

In this paper, we follow the direction of [12; 9]. The input consists of arbitrary consistent CP-nets on a multi-issue domain whose issues are all binary. Because every preference relation on a multi-issue domain extends the preference relation induced by some consistent CP-net, this method does not require any domain restriction. Then we go further in studying the properties of local Condorcet winners, which we rename hypercube Condorcet winners (HCWs) for reasons that will be made clear. After giving some background on CP-nets in Section 2 and introducing the majoritarian aggregation of CP-nets in Section 3, we recall the notion of HCWs in Section 4 and give a simple complexity result about the existence of HCWs. Then we focus on an important problem, namely the worst-case and expected numbers of HCWs under various assumptions. We give a theoretical analysis in Section 5 and an experimental analysis in Section 6. Lastly, we show how a few standard tournament solutions can be generalized in a natural way to inputs consisting of CP-nets, and focus on three of them (Copeland, maximin and Kemeny).

2 Multi-issue Domains and CP-nets

Let X be a finite set of alternatives (or candidates). A vote V is a linear order on X, i.e., a transitive, antisymmetric, and total relation on X . The set of all linear orders on X is denoted by L(X). An n-voter profile P is a collection of n votes, that is, P = (V1, . . . , Vn), where Vj ∈ L(X) for every j ≤ n. The set of all profiles on X is denoted by P(X). A (voting) rule r : P(X) → 2X maps any profile to a subset of alternatives.

In this paper, the set of all alternatives X is a multi-issue domain. We have a set of issues I = {x1, . . . , xp} (p ≥ 2), where each issue xi takes values in a finite domain Di. In this paper, we assume that all issues are binary: for every i we have Di = {0i, 1i}. The set of alternatives is X = D1 × · · · ×Dp: an alternative is uniquely identified by its values on all issues. For any alternative ⃗ d = (d1, . . . , dp) and any issue xi, we let ⃗ d|xi = di and ⃗ d-i = (d1, . . . , di-1, di+1, . . . , dp). For any I ⊆ I, we let DI = ∏xi∈I Di, and D-i = DI\{xi}.

A CP-net N over X consists of two components: (a) a directed graph G = (I,E) and (b) a set of conditional linear preferences ≻i⃗u over Di, for any i ≤ p and any setting ⃗u of the parents of xi in G (denoted by ParG(xi)). These conditional linear preferences ≻i⃗u over Di form the conditional preference table for issue xi, denoted by CPT (xi). When G is acyclic, N is said to be an acyclic CP-net. The size of a CP-net is the cumulative size of all its conditional preference tables.

The preference relation ≻N induced by N is the transitive closure of {(ai, ⃗u, ⃗z) ≻ (bi, ⃗u, ⃗z) | i ≤ p; ⃗u ∈ DParG(xi); ai, bi ∈ Di, ai ≻i⃗u bi; ⃗z ∈ D-(ParG(xi)∪{xi})}. If ≻N is asymmetric then N is consistent. If G is acyclic, then we know that N is consistent [1].

Because all issues are binary, a CP-net N can be visualized as a hypercube with directed edges in a p-dimensional space, where each vertex is an alternative, and any two neighboring vertices differ in only one component (issue): for any i ≤ p and ⃗ d-i ∈ D-i, there is a directed edge connecting (0i, ⃗ d-i) and (1i, ⃗ d-i), and the direction of the edge is from (0i, ⃗ d-i)

to (1i, ⃗ d-i) if and only if (0i, ⃗ d-i) ≻N (1i, ⃗ d-i). For any alternative ⃗ d ∈ X and any i ≤ p, we let ⃗ d[↔ i] denote the neighbor of ⃗ d that only differs from ⃗ d in the ith issue.

Example 1 Let p = 3 and let N be a CP-net defined as follows: the directed graph has an edge from x1 to x2 and an edge from x2 to x3; the CPTs are CPT(x1) = {01 ≻ 11}, CPT(x2) = {01 : 02 ≻ 12, 11 : 12 ≻ 02}, CPT(x3) = {02 : 03 ≻ 13, 12 : 13 ≻ 03}. N is illustrated in Figure 1.

A linear order V extends a CP-net N, denoted by V ∼ N, if it extends ≻N.

3 Majoritarian Hypercube Aggregation

We assume that what is known about the voters' preferences is their underlying (consistent) CP-nets, i.e., for every voter, we know the direction of every edge in the hypercube. Such a collection of consistent CP-nets will be called a hypercube profile, or for short, an H-profile. For the sake of simplicity, we also assume that there is an odd number of agents.

Definition 1 Let I = {x1, . . . , xp} be a set of binary issues. An H-profile over I is a collection P = (N1, . . . ,Nn) of consistent CP-nets over I. A profile PL = (V1, . . . , Vn) of linear orders over X extends an H-profile P = (N1, . . . , Nn) (denoted by PL ∼ P ) if for every j ≤ n, Vj extends Nj .

Definition 2 Given an H-profile P = (N1, . . . , Nn), the majoritarian aggregation M(P) of P is the CP-net N ∗ where for any pair of neighboring alternatives ⃗x = (⃗x-i, xi) and ⃗y = (⃗x-i, x′i ), we have ⃗x ≻N ∗ ⃗y if and only there is a majority of agents j such that ⃗x ≻Nj ⃗y.

Similarly, we can define the majoritarian aggregation for a profile composed of (possibly inconsistent) CP-nets. The majoritarian aggregation has been defined and studied previously under different names [12; 8]. In the weighted majoritarian aggregationW(P), each edge in the hypercube is associated with a weight, defined as follows. Suppose ⃗x ≻N ∗ ⃗y, then, the weight on the edge ⃗x → ⃗y is w(⃗x → ⃗y) = |{j ≤ n : ⃗x ≻Nj ⃗y}| - |{j ≤ n : ⃗y ≻Nj ⃗x}|.

Note that the profile PL consisting of the three linear preference relations (ST ≻ ST ≻ ST ≻ ST , ST ≻ ST ≻ ST ≻ ST, ST ≻ ST ≻ ST ≻ ST) extends P. The (weighted) majority aggregation of N1, N2 and N3 is the following CP-net, depicted with its induced preference relation.

Note that although N1, N2, and N3 are consistent, their majoritarian aggregation is not, as it contains a cycle.

We note that usually the majoritarian aggregation is represented compactly as a CP-net (called the majoritarian CPnet), rather than directly as a hypercube. CP-nets are a good representation for majoritarian aggregations because the majoritarian aggregation preserves preferential independencies of the individual CP-nets. Therefore, the more structure the individual CP-nets share, the more compact the majoritarian CP-net is. Given a preference relation ≻, x ∈ I, Y ⊆ I \ {x} and Z = I \ ({x} ∪ Y ), we say that x is preferentially independent of Y given Z with respect to ≻, which we denote by Ind(x, Y, Z,≻), if for any xi, x′i ∈ Dx, ⃗y, ⃗y′ ∈ DY , and ⃗z ∈ DZ, we have (xi, ⃗y, ⃗z) ≻ (x′i , ⃗y, ⃗z) if and only if (xi, ⃗y′ , ⃗z) ≻ (x′i , ⃗y′ , ⃗z). Similarly, x is preferentially independent of Y given Z with respect to a CP-net N, which we denote by Ind(x, Y, Z,N), if Ind(x, Y, Z,≻) holds for any ≻ extending ≻N . We immediate obtain the following proposition. Most proofs are omitted due to the space constraint.

Proposition 1 Let x ∈ I, Y ⊆ I \ {x} and Z = I \ ({x} ∪ Y ). If Ind(x, Y, Z,Nj) holds for every j ≤ n, then we have Ind(x, Y, Z,M(N1, . . . , Nn)).

On the other hand, Ind(x, Y, Z,M(N1, . . . ,Nn)) may hold even if Ind(x, Y, Z,Nj) fails to hold for some j (and even for every j). For instance, take N1 = {a ≻ ¯a, b ≻ ¯b, ab : ¯ c ≻ c, a¯b : c ≻ ¯ c, ¯ab : c ≻ ¯ c, ¯a¯b : c ≻ ¯ c}; N2 = {a ≻ ¯a, b ≻ ¯b, ab : c ≻ ¯ c, a¯b : ¯ c ≻ c, ¯ab : c ≻ ¯ c, ¯a¯b : c ≻ ¯ c}; N3 = {a ≻ ¯a, b ≻ ¯b, ab : c ≻ ¯ c, a¯b : c ≻ ¯ c, ¯ab : c ≻ ¯ c, ¯a¯b : ¯ c ≻ c}. Then M(N1,N2,N3) is the CP-net with no edges, where the local preferences are {a ≻ ¯a, b ≻ ¯b, c ≻ ¯ c}. The next proposition shows that the size of the majoritarian aggregation (as a CPnet) can be exponentially larger than the sum of the sizes of the individual CP-nets.

Proposition 2 The largest ratio between the size of the majoritarian CP-net and the sum of the sizes of the individual CP-nets is 2p-2/(p - 1).

Proposition 2 only states that in the worst case, representing the majoritarian aggregation as a CP-net is costly. However, because of Proposition 1, we can expect the dependency graph for the majoritarian CP-net, in practice, to have a limited number of edges, which can be computed easily by computing the union of the edges in individual CP-nets.

4 Hypercube Condorcet Winners

Let PL = (V1, . . . , Vn) be a profile of linear orders. We recall that an alternative c is a Condorcet winner (CW) for PL if for every alternative b ̸= c, c is preferred to b in a majority of Vj's. Let CW(PL) denote the set of Condorcet winner(s). Definition 3 ⃗x is a hypercube Condorcet winner (HCW) 1 for P = (N1, . . . ,Nn) if for every neighbor ⃗y of ⃗x, we have ⃗x ≻M(P) ⃗y.

1 This was called "local Condorcet winner" [12]. We use a different name to emphasize that it is for binary multi-issue domains.

Let HCW(P) denote the set of all HCWs in the H-profile P. We know from [9] (Theorem 1 and Corollary 1) that for any H-profile P, ⋃PL∼P CW(PL) ⊆ HCW(P), and the inclusion is strict for some H-profile P . 2

The following useful lemma states that any (possibly cyclic) CP-net can be represented as the (weighted) majoritarian CP-net of an H-profile consisting of 2p - 1 consistent CP-nets, whose size is no more than 2p - 1 times larger.

Lemma 1 Let N be a CP-net (consistent or not) over p binary variables. There exists an H-profile of 2p - 1 consistent CP-nets P = (N1, . . . , N2p-1), such that (a) for every j ≤ n, the size of Nj is no larger than the size of N, (b) N = M(P), and (c) the weight of each edge in W(P) is 1.

Proposition 3 Deciding whether there exists at least one hypercube Condorcet winner for an H-profile is NP-complete. Proof sketch: Membership is easy; the hardness proof uses the following reduction from EXISTENCE OF NONDOMINATED OUTCOME IN A CP-NET, which is NPcomplete (Theorem 1 in [4]): to any CP-net N we associate an H-profile P composed of the 2p - 1 CP-nets as in Lemma 1. ⃗x is an HCW for P iff ⃗x is undominated in M(P). ■

Note that Li et al. address the practical computation of HCWs, via a reduction to SAT with cardinality formulas.

5 HowMany HCWs?

HCW is an important solution concept for majoritarian CPnets. Two questions naturally arise: (1) what is the probability that there exists at least one HCW in the majoritarian CP-net, and (2) what is the average number of HCWs?

The importance of these questions lies in the fact that if the set of HCWs is empty most of the time, then this casts doubt on the usefulness of the notion. On the other hand, if it is likely to contain many alternatives, then it has little decisive power, and listing all HCWs may even result in exponentially large output. Fortunately, we argue that, at least under the following natural assumption on the distribution over profiles, neither is the case. We assume that any CP-net (consistent or not) is drawn with the same probability, which is 1/2p·2p-1 . This distribution naturally induces a distribution for the majoritarian CP-net, where the direction of each edge is drawn i.i.d. uniformly at random (we recall that n is odd).

Proposition 4 The maximum number of HCWs is 2p-1 .

Theorem 1 Suppose each CP-net is drawn i.i.d. uniformly from the set of all CP-nets. The probability that there exists at least one HCW in the majoritarian CP-net is at least 1 - 1e . Proof: Under this distribution the direction of each edge in the majoritarian CP-net is generated i.i.d. uniformly at random. Now, for every ⃗ d ∈ X, ⃗ d is an HCW if for each i ≤ p, the edge between ⃗ d and ⃗ d[↔ i] goes in the direction ⃗ d → ⃗ d[↔ i]. Because the directions of these edges are drawn independently, the probability that ⃗ d is an HCW is 1 2p . Let EVEN (respectively, ODD) denote the set of alternatives ⃗ d such that ∑i di is even (respectively, odd). Since no two alternatives in EVEN are neighbours, for any pair of alternatives ⃗ d, ⃗y in EVEN, the events "⃗ d is an HCW" and "⃗y is an HCW" are independent. Therefore, the probability that EVEN does not contain any HCW is (11 2p )2p-1 . Now, ln (1 - 1 2p )2p-1 = 2p-1 · ln(11 2p ), and ln(11 2p ) < - 1 2p . Therefore, ln (11 2p )2p-1 < - 1 2 and the probability that EVEN (and, symmetrically, ODD) does not contain any HCW is at most 1 √e .

2 Their results were established for a slightly different notion, due to the handling of ties, but their proofs also hold for HCWs.

Given that there is no HCW in ODD, intuitively the probability that there is no HCW in EVEN should be (slightly) less than the (unconditioned) probability that there is no HCW in EVEN. The existence of an HCW in ODD implies that all its neighbors, which are all in EVEN, cannot be HCWs; therefore, there seems to be a negative correlation between the events "at least one HCW in ODD" and "at least one HCW in EVEN," hence a positive correlation between "no HCW in ODD" and "at least one HCW in EVEN," and a negative correlation between the events "no HCW in ODD" and "no HCW in EVEN." Let Pr denote the uniform distribution over all (consistent or not) CP-nets. We have the following claim, which is proved by induction. We omit the proof due to the space constraint.

Therefore, the probability that there is no HCW overall is no more than ( 1 √e )2 = 1e , which means that the probability that there exists at least one HCW is at least 1 - 1e . ■

Theorem 1 is quite positive, because 11e is around 0.632, which means that the probability of having at least one HCW is significant. We conjecture that as p → ∞, the probability actually tends towards 1 - 1e .

Proposition 5 Suppose each CP-net is drawn i.i.d. uniformly from the set of all CP-nets. The expected number of HCWs in the majoritarian CP-net is 1.

Proof: For each alternative, the probability that it is an HCW is 1/2p. Therefore, the expected number of HCWs is ∑⃗ d E[ ⃗ d is an HCW] = 2p · 1 2p = 1. ■

By Markov's inequality, we obtain that the probability that there are at least k HCWs is at most 1/k. This shows that the probability that we have many HCWs is low.

An arguably more natural distribution is the one where each voter's vote is a linear order and is drawn i.i.d. uniformly from the set of all linear orders over X . For any profile PL of linear orders over X, we can still compute the majoritarian CP-net of the H-profile P , where PL is an extension of P , and count the number of HCWs. This setting is known as Impartial Culture, which is by far the most common probability distribution in (computational or not) social choice theory for both theoretical analysis and simulations. The probability of the existence of one Condorcet winner (in non-multi-issue domains) under Impartial Culture has been investigated (see e.g. [10; 5]), but the exact probability is still unknown. Surprisingly, such probabilities are higher than one might expect. 3 For HCWs, we have a similar observation in the next section, where votes are drawn i.i.d. uniformly at random from all linear orders over all 2p alternatives.

3 For example, for 20 alternatives and 37 voters, the probability of the existence of a Condorcet winner is 0.33 by simulation [10].

6 Simulation Results

We run simulations to show the probability of the existence of at least one HCW, as well as the average number of HCWs, for the following two settings.

Setting 1 (Figure 2): The CP-nets are drawn i.i.d. uniformly; the number of issues ranges from 2 to 15; we generated 20000 samples for each setting. In Figure 2(a) we observe that the probability that there exists at least one HCW is almost always above 0.632 ≈ 1 - 1/e, and 0.632 seems to be the limit as p increases. This observation is consistent with Theorem 1, which only proves that 1 - 1/e is a lower bound. In Figure 2(b) we observe that the average number of HCWs is approximately 1 for any number of issues we have investigated. This observation is consistent with Proposition 5.

Li et al. [9] ran similar simulations to find the probability that there exists at least one weak HCW (an alternative that does not lose to any of its neighbors in pairwise elections). However, they randomly generated CP-nets where each issue has no more than 6 parents, while we do not have such a constraint on the number of parents of any issue.

Setting 2 (Figure 3): Each linear order over X is drawn i.i.d. uniformly (i.e., Impartial Culture); the number of issues ranges from 2 to 15; we tested the cases where the number of voters is 501, 601, 701, 801, 901, and 1001; for each setting we generated 10000 samples. In Figure 3(a) we observe that the probability that there exists at least one HCW is almost 1 when there are 6 issues or more, and these probabilities are insensitive to the number of voters (as long as it is larger than 501). In Figure 3(b) we show the log average number of HCWs when the number of voters is 1001 (results are similar for other numbers of voters we have tested). We observe that this number increases as the number of issues increases, and there seems to be a linear correlation. These results justify (experimentally) our conjecture that the probability of the existence of at least one HCW under Impartial Culture is larger than the probability of the existence of at least one HCW when the direction of each edge in the weighted majority graph is drawn i.i.d. uniformly. They also suggest that under Impartial Culture, we face the problem of having too many HCWs.

7 Hypercube-tournament Solution Concepts

All common tournament solution concepts can be naturally extended to hypercubes. Note that hypercubes correspond to partial tournaments on a multi-issue domain, and that extending tournament solution concepts to partial tournaments has been investigated in [3]. Therefore, the definitions below correspond to those in [3] if we ignore the hypercube structure of our partial tournaments. For each tournament solution T , we can define a voting rule over H-profiles by computing the (weighted) majoritarian CP-net and applying the tournament solution T to it. In previous work [12], we explored this idea only for Schwartz. Here, we focus on Copeland, maximin, and Kemeny. Let P be an H-profile, ≻maj P =M(P), and ⃗x ∈ X.

7.1 H-Copeland

We recall that the Copeland score of an alternative, with respect to a profile P, is the number of alternatives it beats in pairwise elections, 4 and a Copeland winner is an alternative with the maximum Copeland score. Let Copeland(P) denote the set of all Copeland winners for P .

Given an H-profile P, we define the hypercube Copeland score of an alternative to be the number of its neighbors it beats in pairwise elections. This seems the most intuitive way of defining a variant of the Copeland score when we know only the hypercube. In both cases (Copeland and HCopeland), we maximize the number of outgoing edges in the dominance graph, the difference is that in H-Copeland we use the majority hypercube instead of the full majority graph.

Definition 4 (H-Copeland) Let HC(⃗x, P) = #{i ≤ p : ⃗x ≻maj P ⃗x[↔ i]}. ⃗x is a hypercube Copeland winner for P if it maximizes HC(⃗x, P). Let HCopeland(P) denote the set of hypercube Copeland winners for P .

Proposition 6 If HCW(P) ̸= ∅, then HCopeland(P) = HCW (P ).

The next proposition studies the relationship between HCopeland winners and Copeland winners of the same profile.

Proposition 7 There exists an H-profile P and an extension PL of P such that Copeland(PL) ̸⊆ HCopeland(P). There exists an H-profile P ′ such that HCopeland(P ′ ) ̸⊆ ⋃P ′L∼P ′ Copeland(P ′L).

Proof: Let P be composed of the following three CP-nets.

Let V1 = ST ≻ ST ≻ ST ≻ ST be the extension of N1; the only extension of N2 is V2 = ST ≻ ST ≻ ST ≻ ST; and the only extension of N3 is V3 = ST ≻ ST ≻ ST ≻ ST. Therefore, ST is a Copeland winner for PL but not an HCopeland winner for P. Let P ′ = (N ′1 ,N ′2 ,N ′3 ), where N ′1 is S : T ≻ ¯ T ; ¯ S : ¯ T ≻ T ; T : S ≻ ¯ S; ¯ T : ¯ S ≻ S, N ′2 is S ≻ ¯ S; S : T ≻ ¯ T ; ¯ S : ¯ T ≻ T and N ′3 is ¯ S ≻ S; T ≻ ¯ T ; ¯ S : ¯ T ≻ T . ST is an HCopeland winner but not a Copeland winner in any extension of P ′ (P ′ only has one extension). ■

Proposition 8 Checking whether ⃗x is an H-Copeland winner is coNP-complete.

Proof: Membership in coNP is straightforward. Hardness is proved by a reduction from EXISTENCE OF NONDOMINATED OUTCOME IN A CP-NET, which is NPcomplete (Theorem 1 in [4]). Let N be the (possibly cyclic) CP-net in an instance of EXISTENCE OF NON-DOMINATED OUTCOME IN A CP-NET. We define a CP-net N ′ over p + 1 issues as follows. Let I = {x1, . . . , xp}.

• The restriction of N ′ on DI when xp+1 = 0 is N. That is, for any i ≤ p and any ⃗u ∈ DI\{xi}, (0i, 0p+1, ⃗u) ≻N ′ (1i, 0p+1, ⃗u) if and only if (0i, ⃗u) ≻N (1i, ⃗u).
• The restriction of N ′ on DI when xp+1 = 1 is a CP-net with no edges, such that for any i ≤ p, 1i ≻ 0i.
• xp+1 has no incoming edges, and 0p+1 ≻ 1p+1.

We note that the size of N ′ is two times the size of N plus 1.

Now, by Lemma 1, there exists an H-profile P composed of 2p + 1 consistent CP-nets such that M(P) = N ′ and the size of P is polynomial in N ′ . Let ⃗x = (1, . . . , 1). Because ⃗x only loses to (1, . . . , 1, 0) in their pairwise election, we have HC(⃗x, P) = p - 1. Note that for any HCW ⃗ d ∈ DI in N, (⃗ d, 0) is an HCW for P, so that HC((⃗ d, 0), P) = p. Hence, ⃗x is an H-Copeland winner if and only if N has no HCW. ■

7.2 H-maximin

Let NP (ci, cj) denote the number of votes that rank ci ahead of cj in the profile P. We recall that the maximin rule selects the alternatives c maximizing min{NP(c, c′ ) : c′ ∈ X, c′ ̸= c}. Let MM(P) denote the set of all maximin winners for P . We define H-maximin as follows:

Definition 5 (H-maximin) For any H-profile P, let Hmm(⃗x, P) = mini≤p |{j ≤ n : ⃗x ≻Nj ⃗x[↔ i]}|. ⃗x is a hypercube maximin winner for P if it maximizes Hmm(⃗x, P). Let HMaximin(P) denote the set of hypercube maximin winners for P .

Note that HMaximin is a weighted H-tournament solution: it is determined from the weighted majoritarian CP-net.

Proposition 9 If HCW(P) ̸= ∅, then HMaximin(P) ⊆ HCW(P ).

The inclusion can be strict. Take the following H-profile P = (N1,N2,N3), where N1 and N2 are a : b ≻ ¯b; ¯a : ¯b ≻ b; b : a ≻ ¯a; ¯b : ¯a ≻ a, and N3 is a ≻ ¯a; b ≻ ¯b. The weighted majoritarian CP-net is a : b ≻ ¯b (weight 3); ¯a : ¯b ≻ b (weight 2); b : a ≻ ¯a (weight 3); ¯b : ¯a ≻ a (weight 2). Both ab and ¯a¯b are HCWs, while only ab is an H-maximin winner.

Proposition 10 There exists an H-profile P and an extension PL of P such that MM(PL) ̸⊆ HMaximin(P). There exists an H-profile P ′ such that HMaximin(P ′ ) ̸⊆ ⋃P ′L∼P ′ MM(P ′L ).

Proof: The proposition can be proved with the same profiles shown in the proof of Proposition 7. ■

Proposition 11 Checking whether ⃗x is an H-maximin winner is coNP-complete.

Proof: Membership in coNP is straightforward. The hardness proof uses the same reduction as for H-Copeland. ■

7.3 H-Kemeny

For any pair of linear orders V and V ′ , let d(V, V ′ ) denote the number of pairs of alternatives {c, c′} on which V and V ′ disagree. Given a profile P = (V1, . . . , Vn), a Kemeny consensus for P is a linear order V that minimizes ∑nj=1 d(V, Vj); an alternative c is a Kemeny winner for P if c is ranked in the top position in some Kemeny consensus for P. Let Kemeny(P) denote the set of all Kemeny winners for P .

Now, we adapt the Kemeny rule to multi-issue domains as follows. The main difference from Kemeny is that the distance function for H-Kemeny only counts the number of edges in the hypercube on which two CP-nets differ.

Definition 6 Given two CP-nets N and N ′ over p binary variables, the distance dH(N,N ′ ) between N and N ′ is the number of edges in the hypercube on which N and N ′ differ. Given an H-profile P = (N1, . . . ,Nn) and a CP-net N, the distance between N and P is defined by dH(N, P) = ∑1≤j≤n dH(N, Nj). A hypercube Kemeny consensus for P is a consistent CP-net N over {x1, . . . , xp} that minimizes the distance dH(N, P); an alternative ⃗x is a hypercube Kemeny winner (HKW) for P if ⃗x is undominated in some hypercube Kemeny consensus for P . We denote by HKemeny(P ) the set of all HKWs for P .

We note that H-Kemeny is a weighted H-tournament solution.

The inclusion can be strict, even when HCW(P) ̸= ∅. (See the profile P in the proof of Proposition 7.)

Proposition 13 There exists an H-profile P and an extension PL of P such that Kemeny(PL) ̸⊆ HKemeny(P). There exists an H-profile P ′ such that HKemeny(P ′ ) ̸⊆ ⋃P ′L∼P ′ Kemeny(P ′L ).

Proof: The proposition can be proved with the same profiles shown in the proof of Proposition 7. ■

Next, we study the computational complexity of deciding whether an alternative ⃗x is an H-Kemeny winner. We adopt a compact representation for CP-net entries (already used in [4]) that uses "else" to represent all the valuations of the parents that are not mentioned in the CPT.

Proposition 14 Checking whether ⃗x is an H-Kemeny winner is P NP || -hard.

Proof sketch: Hardness is proved by reduction from KEMENY WINNER, which is P NP || -complete [6]. In an instance of KEMENY WINNER, we are given a profile PL = (V1, . . . , Vn) over C and an alternative c ∈ C. We are asked whether c is a Kemeny winner. The idea behind the construction is that for j ≤ |C|, we first identify an alternative ⃗ej in X. Then, we "embed" the weighted majority graph of PL into the weighted majoritarian CP-net, such that each edge ci → cj in the weighted majority graph of PL corresponds to a path from

⃗ei to ⃗ej. The length of each of these paths is 2 and they are disjoint (except the start point and the end point). With this construction, ci is a Kemeny winner if and only if ⃗ei is an H-Kemeny winner. The details are omitted. ■

8 Future Work

We can extend our majoritarian approach to multi-issue domains with non-binary issues as follows: for any issue i and any ⃗ d-i in D-i, we compute the local (weighted) majority graph based on agents' local preferences over xi.

There are some open questions left for future research. Figure 2(a) suggests that when each CP-net is generated i.i.d. uniformly at random, the probability that there exists at least one HCW in the majoritarian CP-net goes to 1 - 1/e as p → ∞. Figure 3(b) suggests that under the impartial culture assumption, the log average number of HCWs is linear in the number of issues. It would be desirable to find theoretical proofs for these observations.

Another important direction is to investigate other tournament solutions, such as Slater, Banks, and the uncovered set.

Acknowledgements

Vincent Conitzer and Lirong Xia acknowledge NSF CAREER 0953756 and IIS-0812113, and an Alfred P. Sloan fellowship for support. J´erˆome Lang thanks the ANR project ComSoc (ANR-09-BLAN-0305). Lirong Xia is supported by a James B. Duke Fellowship. We thank all IJCAI-11 reviewers for their helpful comments and suggestions.