Mostapha Diss
email: mostapha.diss@univ-fcomte.fr.

Clinton Gubong Gassi

Issofa Moyouwou
email: imoyouwou2@yahoo.fr.

Clinton Gubong Gassi
email: clinton.gubong_gassi_takoulo@univ-fcomte.fr.

S ocial acceptability and the majoritarian compromise rule

Keywords: Voting, single-winner elections, social acceptability, majoritarian compromise rule. JEL classification: D71, D72

. The two concepts have been introduced separately in the literature in the spirit of selecting an alternative that satisfies most individuals in single-winner elections. Our results in this paper show that the two concepts are so closely related that the interaction between them cannot be ignored. We show that the majoritarian compromise rule always selects a socially acceptable alternative when the number of alternatives is even and we provide a necessary and sufficient condition so that the majoritarian compromise rule always selects a socially acceptable alternative when the number of alternatives is odd. Moreover, we show that when we restrict ourselves to the three well-studied classes of single-peaked, single-caved, and single-crossing preferences, the majoritarian compromise rule always picks a socially acceptable alternative whatever the number of alternatives and the number of voters.

Introduction

There are many reasons why societies run elections. For instance, a given society may need to select its leader (e.g., a president); members of a team may need to find an appropriate meeting time; referees of an academic journal or a conference may need to decide which candidate should receive a given prize. Each of these settings may call for a single-winner voting system.

The plurality rule is the simplest means of determining the outcome of a single-winner election and it has attracted much attention in social choice theory. Under this voting rule each voter is allowed to vote for only one alternative and, in order to win, an alternative need only poll more votes than any other single opponent. The plurality vote has many advantages that should be stressed: it is easily understood by voters; it provides for a quick decision; and most importantly it is less costly to operate than many other voting rules. However, so long as there are more than two alternatives, the winner under the plurality rule may lack the support of any majority. The winner may be opposed by a strict majority of agents, each of whom may even regard the chosen alternative as the worst alternative available. As a consequence, the winner will not be seen as fully legitimate, and to the best of our knowledge this is the main argument against the use of the plurality rule.

The issue of the legitimacy of the winner does not only concern the plurality system but also concerns a broad range of well-studied voting systems in the social choice literature.

The fact remains that whatever voting system is considered, one generally agrees that in many important real-world social choice problems it is important to choose an alternative which is regarded as strong by the agents forming the society. Many lines of research in social choice theory have been concerned with that approach. In this respect, two well-known social choice concepts have been introduced in the literature in the spirit of selecting an alternative that has support from voters to the best degree possible within the classic framework that assumes that voters' preferences over alternatives are represented by linear orders: the majoritarian compromise rule and the social acceptability principle.

The majoritarian compromise rule was introduced by Sertel (1986) and studied in detail by [START_REF] Sertel | The majoritarian compromise is majoritarian-optimal and subgame-perfect implementable[END_REF]. It is based on the majority principle and aims to select an alternative which satisfies the largest majority of voters as well as possible. According to this voting system, a majority is a subset of the set of voters that contains at least half of the individuals. Any majority enjoys some satisfaction from each alternative and the majoritarian compromise rule picks the alternative(s) which give(s) the best possible satisfaction to the largest majority.1 Note that this voting system has been the subject of many investigations in the literature such as [START_REF] Brams | Fallback bargaining[END_REF], [START_REF] Dindar | Compromise in combinatorial vote[END_REF], [START_REF] Giritligil | Does majoritarian approval matter in selecting a social choice rule? An exploratory panel study[END_REF], [START_REF] Kondratev | Measuring majority tyranny: Axiomatic approach[END_REF], [START_REF] Laffond | Searching for a Compromise in Multiple Referendum[END_REF], [START_REF] Llamazares | Positional voting systems generated by cumulative standings functions[END_REF], [START_REF] Merlin | Properties of majoritarian compromise, efficient compromise, and related compromise rules[END_REF][START_REF] Merlin | Compromise rules revisited[END_REF], [START_REF] Nurmi | Voting paradoxes and how to deal with them[END_REF], among others.

The concept of social acceptability was introduced in the literature by [START_REF] Mahajne | The socially acceptable scoring rule[END_REF]. In the framework of linear orders, we say that a voter places a given alternative above the line if she prefers it to at least half of the alternatives, and she places it below the line if at least half of the alternatives are preferred to it. An alternative is said to be socially acceptable with respect to a given preference profile if it is placed above the line by at least as many voters as those who place it below the line. In other words, a socially acceptable alternative is an alternative ranked among the top half of the linear orders by at least as many individuals as those who rank it among the bottom half. [START_REF] Mahajne | The socially acceptable scoring rule[END_REF] characterised the only scoring rule that satisfies the social acceptability principle, that is, the only scoring rule that always selects a socially acceptable alternative for any preference profile.2

It is worth noting that [START_REF] Mahajne | Condorcet winners and social acceptability[END_REF] studied the social acceptability of the q-Condorcet winner, that is, an alternative which is head-to-head preferred by at least a proportion q ∈] 1 2 , 1] of voters over any other alternative. Moreover, they showed that if preferences are single-peaked or satisfy the single-crossing property, any Condorcet winner (i.e., q = 1 2 ) is socially acceptable.3 In the paper at hand, we show that the interaction between the majoritarian compromise and the social acceptability principles cannot be ignored. Our results show that the majoritarian compromise rule always selects a socially acceptable alternative when the number of alternatives is even. We also provide a necessary and sufficient condition that allows this connection between the two concepts when the number of alternatives is odd. Moreover, we show that when we restrict our attention to the classes of singlepeaked, single-caved, and single-crossing preference profiles, the majoritarian compromise rule always picks a socially acceptable alternative whatever the number of alternatives and whatever the number of voters.

The paper is organised as follows. Section 2 lays out the basic notation and definitions, Section 3 states and proves our results, and Section 4 concludes.

Definitions and notation

Consider a non-empty set A of m alternatives (or candidates) and a non-empty set N of n voters with m ≥ 3 and n ≥ 2. Alternatives are sometimes denoted by small letters a, b, c, etc., or a 1 , a 2 , a 3 , etc. and voters are denoted by non-negative integers 1, 2, 3, etc.

We assume that each voter ranks, without the possibility of ties, all the alternatives from the most preferred alternative to the least preferred one. Each individual's preference is then a linear order on the set A; that is, a complete, anti-symmetric and transitive binary relation on the set A. Given a voter i ∈ N , the (linear) ranking or the preference relation of i is denoted by p i or i4 and the n-tuple p = (p 1 , p 2 , . . . , p n ) is called a preference profile (or simply a profile) which specifies the ranking of each voter. For any two alternatives a and b, we write a i b if voter i strictly prefers a to b. The rank of any alternative a ∈ A in the preference relation p i of voter i is denoted by r(p i , a) and it is defined by

r(p i , a) = b ∈ A : b i a + 1 = m -b ∈ A : a i b . (1)
The set of all individual preferences in which alternative a is strictly preferred to A social choice rule (SCR) is any mapping F that associates each profile p with a non-empty subset F (p) of A called the social outcome of p. We restrict our attention to anonymous SCRs which are defined in such a way that they do not depend on the names of voters: permuting the preference relations of any two voters does not affect the social outcome for any profile. We then simply write P n instead of P N since specifying N is no longer necessary. When the set N of voters under consideration possibly varies, the set of all possible profiles is denoted by ∪ ∞ n=2 P n . A scoring vector of size m is an m-tuple α = (α 1 , α 2 , . . . , α m ) of real numbers such that α 1 ≥ α 2 ≥ • • • ≥ α m and α 1 > α m . An SCR can be associated with the scoring vector α as follows: given a profile p ∈ ∪ n=∞ n=2 P n and an alternative a, across individual preferences in p, alternative a receives α 1 points for each first position, α 2 points for each second position, and so on. The total number of points received by a is called the score of a in profile p and it is denoted by S α (p, a). It is formally defined by

S α (p, a) = n i=1 α r(p i ,a) , (2)
where α r(p i ,a) denotes the score in the vector α which is given to alternative a in the preference p i of individual i. With m alternatives, the scoring SCR associated with the m-tuple α is denoted by F α and it selects the set of all alternatives having the maximum score S α (p, a) taking into account all alternatives in the profile p ∈ ∪ n=∞ n=2 P n . Wellknown scoring SCRs F α include the Plurality rule, the Antiplurality rule, the Borda rule, and the t-approval rule which respectively correspond to the scoring vectors (1, 0, . . . , 0), (1, . . . , 1, 0), (m -1, m -2, . . . , 1, 0), and (1, . . . , 1 t times , 0, . . . , 0 m-t times ). Note that [START_REF] Mahajne | The socially acceptable scoring rule[END_REF] introduced a new scoring rule called the Half Accepted Half Rejected (HAHR) rule which is defined by the scoring vector (α 1 , α 2 , . . . , α m ) such that

α j =      +1 if j < m+1 2 0 if j = m+1 2 -1 if j > m+1 2 (3)
Following [START_REF] Mahajne | The socially acceptable scoring rule[END_REF], we say that an alternative a is ranked above the line by voter i if a is strictly preferred to at least half of the alternatives by voter i, that is: r(p i , a) < (m + 1)/2. Similarly, the alternative a is said to be ranked below the line by voter i if at least half of the alternatives are strictly preferred to a by voter i, that is: r(p i , a) > (m + 1)/2. When the number of alternatives is odd, any alternative ranked neither above the line nor below the line by voter i is said to be ranked on the line by i, that is: r(p i , a) = (m + 1)/2. Definition 1 Let p be a preference profile, A be a set of m alternatives, and N be a set of voters. An alternative a ∈ A is said to be socially acceptable in p if the total number of voters who rank a above the line is greater than or equal to the number of voters who rank a below the line, that is:

i ∈ N : r(p i , a) < m + 1 2 ≥ i ∈ N : r(p i , a) > m + 1 2 .
The set of all socially acceptable alternatives in profile p is denoted by SA(p).

Definition 2 Given a set of alternatives A, we say that an SCR F satisfies social acceptability if for all profiles p ∈ ∪ n=∞ n=2 P n , F (p) ⊆ SA(p), that is:

∀a ∈ A, a ∈ F (p) =⇒ a ∈ SA(p) ,
meaning that an SCR satisfies the social acceptability principle if it always selects a socially acceptable alternative for any preference profile.5

Let us now formally define the majoritarian compromise rule introduced by Sertel (1986), which aims to select an alternative yielding the best majority satisfaction for the largest proportion of voters. Given a preference profile, each majority earns some satisfaction/welfare from any alternative depending on its lowest ranking for that majority.

We then find the maximal satisfaction that a majority can enjoy in the considered profile.

Then, the majoritarian compromise rule identifies all alternatives which yield this maximal satisfaction to some majority, and picks among them the alternative which yields it to the largest majority.

Formally, for any alternative a ∈ A and any voter i ∈ N , we denote by π i (a) the integer mr(p i , a) + 1 which defines the satisfaction/welfare given by alternative a to voter i according to her preference p i . For any coalition of voters K ⊆ N , we define the satisfaction of K with regard to the alternative a by

π K (a) = min π i (a) : i ∈ K . (4)
In other words, π K (a) defines the minimum satisfaction that can be obtained from the alternative a by a voter belonging to coalition K. A coalition K will be called a majority if it contains at least half of the voters, that is: K ≥ |N \ K|. We denote by M the set of all possible majorities of N . For any preference profile p, the maximal satisfaction that any majority can obtain from any alternative is denoted by

π(p) = max π K (a) : K ∈ M, a ∈ A , (5)
and we denote by

M (p) = a ∈ A : ∃i ∈ N, π i (a) = π(p) , (6)
the set of all alternatives that give the maximal satisfaction π(p) to at least one voter. For any alternative a ∈ M (p), we define

K(a, p) = i ∈ N : π i (a) ≥ π(p) , (7)
as the set of all voters who enjoy at least π(p) of satisfaction from a. We are now ready to define the majoritarian compromise rule. It intuitively selects among the alternatives which give the maximal (majority) satisfaction π(p) to at least one voter (i.e., among the alternatives in the set M (p)) those which give it to the largest majority.

Definition 3 The majoritarian compromise rule is the social choice rule M :

∪ n=∞ n=2 P n -→ 2 A defined by M (p) = a ∈ M (p) : b ∈ M (p) =⇒ K(b, p) ≤ K(a, p) ,
where 2 A stands for the set of all possible subsets of A.

Example 1 illustrates the previous definitions.

Results

The only alternative picked out by the majoritarian compromise rule in Example 1 is socially acceptable. It is interesting to check whether this is always true; that is, whether the majoritarian compromise rule always satisfies the social acceptability principle. We start our analysis by considering the general model where no restrictions are imposed on individual preferences.

General setting

The next proposition states that when the number of alternatives is even, the majoritarian compromise rule always selects a socially acceptable alternative for any preference profile.

Proposition 1 Let A be a set of m alternatives and p be a preference profile. If m is even, then M (p) ⊆ SA(p).

Proof. Assume that m = 2q (q ∈ N * ). Let p be a preference profile and c ∈ M (p).

Since SA(p) = ∅,6 consider a ∈ SA(p). It holds that there is a majority K of voters who rank a above the line since no alternative is ranked on the line whenever m is even. It

follows that π K (a) ≥ q + 1. Therefore, π(p) ≥ q + 1 and since c ∈ M (p) there exists a majority T ∈ M such that π T (c) = π(p) ≥ q + 1. This implies that min i∈T {π i (c)} = m -max i∈T r(p i , c) + 1 ≥ q + 1, that is, max i∈T r(p i , c) ≤ q < m+1
2 . Thus all voters in T rank the alternative c above the line. Since T is a majority, then c ∈ SA(p).

We now focus on the case where the number of alternatives is odd.

Proposition 2 Let A be a set of m alternatives and p be a preference profile with n voters.

If m is odd, M (p) ⊆ SA(p) if and only if:

n ≤ 2m + 2 if n is even n ≤ m + 2 if n is odd
Proof. Assume that m = 2q + 1(q ∈ N * ) and pose A = {a 1 , . . . , a m }.

First, suppose that the majoritarian compromise rule does not satisfy the social acceptability principle. Then, there exists a preference profile p and an alternative c such that c ∈ M (p) and c / ∈ SA(p). We show that n > 2m + 2 for n even and n > m + 2 for n odd.

For this purpose, we pose for any x ∈ A:

E x = (i, k) : i ∈ N, k ∈ {1, . . . , q + 1}, r(p i , x) = k E - x = (i, k) : i ∈ N, k ∈ {1, . . . , q}, r(p i , x) = k E + x = (i, k) : i ∈ N, k ∈ {q + 2, . . . , m}, r(p i , x) = k Note that each (i, k) ∈ E x ∪ E - x ∪ E +
x tells us about the position of alternative x in voter i's ranking. Precisely, E x stands for the set of all positions of x above or on the line, E - x stands for the set of all positions of x above the line, and E +

x stands for the set of all positions of x below the line. Since SA(p) = ∅, let us consider b ∈ SA(p). There is a majority of voters K who rank b among the top (q + 1) alternatives, and for that majority we have π K (b) ≥ q +1, which implies that π(p) = π T (c) ≥ q +1 for some majority T . Since c / ∈ SA(p), the satisfaction of any majority from c is at most q+1, i.e., π(p) = π T (c) ≤ q+1 since there is no majority of voters who rank c above the line, that is, among the top q alternatives. Therefore, we have π(p) = q + 1 = π T (c).

Case 1: Suppose that n is even and let n = 2t (t ∈ N * ).

Since π(p) = q + 1 = (m + 1)/2, there is no majority of voters who rank any alternative above the line. Then, |E - x | ≤ t -1 = (n -2)/2 for all x ∈ A. This implies that

E - c = x =c E - x = x =c E - x ≤ (m -1) n -2 2 . ( 8
)
Thus, we have

E - c = nq -x =c E - x ≥ nq -(m-1)(n-2)/2 = m-1 since q = (m-1
)/2 and the number of places available above the line is nq. Moreover, since c is not socially acceptable, we have

E + c > E - c which implies that E + c ≥ m since E - c ≥ m -1 by (8). It follows that E c = n -E + c ≤ n -m.
We deduce that

x =c

E x = x =c |E x | = n(q + 1) -|E c | ≥ n m + 1 2 -(n -m). (9)
Recalling that c ∈ M (p), it follows that E x ≤ E c = K(c, p) for any other alternative

x = c since the size of the majority which enjoys the maximal satisfaction q + 1 from c is exactly the cardinality of the set E c of all positions of x above or on the line, that is, among the top q + 1 positions. It follows that

x =c

E x = x =c E x ≤ (m -1) E c ≤ (m -1)(n -m). (10)
From inequalities ( 9) and ( 10), we deduce that n(m

+ 1)/2 -(n -m) ≤ (m -1)(n -m), which is equivalent to n ≥ 2m 2 /(m -1). Hence n > 2m + 2 since 2m 2 /(m -1) > 2m + 2
for all integers m such that m ≥ 3.

Case 2: Suppose n is odd and let n = 2t + 1 (t ∈ N * ).

Since π(p) = q + 1 = (m + 1)/2, there is no majority of voters who rank any alternative above the line. This implies that E - x ≤ t = (n -1)/2 for all x ∈ A. We deduce that

x =c

E - x = x =c E - x ≤ (m -1) n -1 2 . ( 11
)
Thus, we have

E - c = nq - x =c E - x ≥ nq -(m -1)(n -1)/2 = (m -1)/2 since q = (m -1)/2. Moreover, since c is not socially acceptable, we have E + c > E - c which implies by (11) that E + c ≥ (m -1)/2 + 1 = (m + 1)/2. It follows that E c = n -E + c ≤ n -(m + 1)/2. Therefore, x =c E x = x =c E x = n(q + 1) -E c ≥ n m + 1 2 -n - m + 1 2 . ( 12
)
Furthermore, c ∈ M (p). Therefore, E x ≤ E c = K(c, p) for all x ∈ A\{c}. This implies that

x =c

E x = x =c E x ≤ (m -1) E c ≤ (m -1) n - m + 1 2 . ( 13
)
From ( 12) and ( 13), we deduce that

n m + 1 2 -n - m + 1 2 ≤ (m -1) n - m + 1 2 .
Equivalently, n ≥ m(m+1)/(m-1). Therefore, n > m+2 since m(m+1)/(m-1) > m+2.

Second, suppose that n > 2m + 2 for an even number of voters or n > m + 2 for an odd number of voters. We prove in both cases that the majoritarian compromise rule does not satisfy the social acceptability principle by providing a profile p and an alternative c ∈ M (p) such that c is not socially acceptable.

Case 1: Suppose that n is even and n > 2m + 2. This means that n ≥ 2m + 4. Consider six subsets N 1 , N 2 , N 3 , N 4 , N 5 , and N 6 of the set of voters N such that N 1 = 1, 2, . . . , q , N 2 = q + 2, q + 3, . . . , 2q + 1 = m , N 3 = m + 1, m + 2, . . . , m + q , N 4 = m + q + 2, . . . , 2m , and N 5 = N 6 = (n -2m)/2, and consider the partition of N defined by

N = N 1 ∪ N 2 ∪ N 3 ∪ N 4 ∪ N 5 ∪ N 6 ∪ {q + 1} ∪ {m + q + 1}.
In the following profile p, each individual's preference is constructed around one of the two rankings r 1 = a 1 a 2 . . . a m and r 2 = a m a m-1 . . . a 1 by moving alternative a q+1 from the line to the top (i.e., first position)

or just below the line (i.e., (q +2) th position) while some other alternative, say a j , is moved to the line as follows:

p i = a q+1 a 1 a 2 . . . a i-1 a i+1 . . . a q a i a q+2 . . . a m for i ∈ N 1 (with j = i in r 1 ) p i = a q+1 a m a m-1 . . . a i+1 a i-1 . . . a q+2 a i a q . . . a 1 for i ∈ N 2 (with j = i in r 2 ) p m+i = a m a m-1 . . . a q+2 a i a q+1 a q . . . a i+1 a i-1 . . . a 1 for m + i ∈ N 3 (with j = i in r 2 ) p m+i = a 1 a 2 . . . a q a i a q+1 a q+2 . . . a i-1 a i+1 . . . a m for m + i ∈ N 4 (with j = i in r 1 )
p q+1 = a m a m-1 . . . a q+2 a 1 a q+1 a q . . . a 2 (with j = 1 in r 2 )

p i = r 1 for i ∈ N 5 ∪ {m + q + 1} and p i = r 2 for i ∈ N 6
For this profile, each alternative a k for 1 ≤ k ≤ q is ranked above the line by exactly n/2-1 for all a k = a q+1 and K(a

voters from (N 1 \{k}) ∪ N 4 ∪ N 5 ∪ {m + q + 1}
q+1 , p) = m -1 + n -(2m -1) = n -m. Since n ≥ 2m + 4, it follows that K(a q+1 , p) ≥ (n + 4)/2 ≥ K(a k , p) for all a k = a q+1 . Thus, a q+1 ∈ M (p)
and a q+1 is not socially acceptable. This proves that the majoritarian compromise rule fails to satisfy social acceptability in this case.

Case 2: Suppose that n is odd and n > m + 2. This means that n ≥ m + 4. Consider a partition of the set N of voters into five disjoint subsets N 1 , N 2 , N 3 , N 4 and N 5 such that

N 1 = 1, 2, . . . , q , N 2 = q + 1, q + 2, . . . , 2q , N 3 = m and N 4 = N 5 = (n -m)/2.
Using the same operations as in the previous case, the following profile p is built from r 1 = a 1 a 2 . . . a m or r 2 = a m a m-1 . . . a 1 as follows:

p i = a q+1 a 1 a 2 . . . a i-1 a i+1 . . . a q a i a q+2 . . . a m for i ∈ N 1 (with j = i in r 1 ) p q+i = a m a m-1 . . . a q+2 a i a q+1 a q . . . a i+1 a i-1 . . . a 1 for q + i ∈ N 2 (with j = i in r 2 )
p m = a 1 a 2 . . . a q a m a q+1 a q+2 . . . a m-1 (with j = m in r 1 )

p i = r 1 for i ∈ N 4 and p i = r 2 for i ∈ N 5
For this profile, each alternative a k with 1 ≤ k ≤ q is ranked above the line by exactly (n -1)/2 voters from (N 1 \{k}) ∪ N 4 ∪ {m} and on the line by two voters from {k, q + k};

each alternative a k with q + 2 ≤ k ≤ m is ranked above the line by exactly (n -1)/2 voters from N 2 ∪ N 5 and on the line by at most one voter from {m}. Clearly, any alternative a k = a q+1 is ranked above the line by no majority. Now, alternative a q+1 is ranked above the line by exactly (m-1)/2 voters from N 1 , below the line by exactly (m+1)/2 voters from N 2 ∪{m}, and on the line by exactly n-m voters from N 4 ∪N 5 . Therefore, π(p) = (m+1)/2, K(a k , p) ≤ (n -1)/2 + 2 = (n + 3)/2 for all a k = a q+1 and K(a q+1 , p) = (m -1)/2 + n -

m = n -(m + 1)/2. Since n ≥ m + 4, it follows that K(a q+1 , p) ≥ (n + 3)/2 ≥ K(a k , p)
for all a k = a q+1 . Thus, a q+1 ∈ M (p) and a q+1 is not socially acceptable. This proves that the majoritarian compromise rule fails to satisfy social acceptability in this case.

Example 2 provides an illustration of the profiles presented in the previous proposition.

Example 2 Suppose that m = 5 and n = 14 (i.e., n > 2m + 2). Consider the following preference profile p:

p =        
a 3 a 3 a 3 a 3 a 5 a 5 a 5 a 1 a 1 a 1 a 1 a 1 a 5 a 5 a 2 a 1 a 4 a 5 a 4 a 4 a 4 a 2 a 2 a 2 a 2 a 2 a 4 a 4 a 1 a 2 a 5 a 4 a 1 a 1 a 2 a 4 a 5 a 3 a 3 a 3 a 3 a 3 a 4 a 4 a 2 a 2 a 3 a 3 a 3 a 3 a 3 a 4 a 4 a 4 a 2 a 2 a 5 a 5 a 1 a 1 a 2 a 2 a 1 a 5 a 4 a 5 a 5 a 5 a 1 a 1

       
It can be checked that M (p) = {a 1 , a 3 }. Alternative a 3 is a majoritarian compromise winner (and the Condorcet winner), but it is not socially acceptable. As in the above example, it can be checked that when the total number of alternatives is odd and greater than or equal to five,7 in each of the profiles presented in the proof of Proposition 2, alternative a q+1 is both a majoritarian compromise winner and a Condorcet winner, but fails to be socially acceptable. This shows that the bounds provided in Proposition 2 are tight because even if we are looking for an alternative who is both a majoritarian compromise winner and a Condorcet winner, the bounds cannot be improved.

It is worth noting that even if the majoritarian compromise rule always picks a socially acceptable alternative when the number of alternatives is even or whenever the number of alternatives is odd and the conditions of Proposition 2 are satisfied, the outcome of this rule can differ from the outcome of the only scoring rule that satisfies social acceptability, namely the HAHR rule. This is due to the fact that not all socially acceptable alternatives are necessarily selected by the HAHR rule. Moreover, the HAHR rule rates all the alternatives on the same side of the line with the same worth, while the majoritarian compromise rule takes into account the degree of majority support. This is illustrated in Example 3.

Example 3 Consider the following profiles p and p :

p =       a a c

Some restricted domains

In this section, we restrict our attention to the classes of single-peaked, single-caved, and single-crossing preferences and we show that the majoritarian compromise rule always selects a socially acceptable alternative for each of these domains.

Single-peaked preferences

The class of single-peaked preferences introduced by Black ( 1948) is perhaps the most extensively studied type of domain restriction. Roughly speaking, a set of preference relations is single-peaked with respect to a given linear order of the alternatives if each preference has a "peak" (most preferred alternative) such that for any two alternatives on the same side of the peak, one is preferred over the other if it is closer to the peak.

Single-peaked preferences can arise for instance in the presence of a desirable suggested project such as the construction of a hospital. In this case, for a voter, the best location would be closest to her home. Single-peaked preferences can also arise in political area with a left-right preference spectrum in which policies are on a classical axis which can be modelled by a segment [a, b], such that any voter cannot prefer both a and b over any middle policy. Formally, Definition 4 Let A be a set of m alternatives, and let ≤ be a linear order on A. We say that a preference relation is single-peaked with respect to ≤ if there is an alternative

p( ), called the peak, such that b < a ≤ p( ) or p( ) ≤ a < b ⇒ (a b).
We say that a preference profile p = (p 1 , . . . , p n ) is single-peaked with respect to ≤ if all preference relations p i are single-peaked with respect to ≤.

The next two claims from [START_REF] Mahajne | Condorcet winners and social acceptability[END_REF] are very useful properties of single-peaked preferences that we will use in order to facilitate our proof. . We can remark that when the number of alternatives is odd, for any k ∈ {1, m}, the relation between an alternative a k and its counter is converse; that is, if b is the counter of a k , then a k is also the counter of b.

Example 4 gives an illustration.

Example 4 Let us consider the set of alternatives A = {a 1 , a 2 , a 3 , a 4 , a 5 }. Obviously, the preference relation a 1 a 2 a 3 a 4 a 5 is single-peaked with respect to the linear order a 1 < a 2 < a 3 < a 4 < a 5 . For this preference relation, the alternative a 3 is the counter of the alternatives a 1 and a 5 . The alternative a 4 is the counter of a 2 and a 2 is conversely the counter of a 4 . By single-peakedness, it is not possible to rank the alternatives a 2 and a 4 on the same side of the line.

Definition 5 Let a be an alternative, p be a preference profile, and K be a majority. We say that a "gains k th degree approval" from K if r(p i , a) ≤ k for all i ∈ K, which means that π K (a) ≥ mk + 1.

Definition 6

The critical degree of majority approval of an alternative a, denoted k * (a),

is the lowest degree of approval that a gains from a majority.

From the definitions above, we can remark that for any preference profile p, and for any alternative a ∈ M (p), we have that

π(p) = m -k * (a) + 1 which is equivalent to saying that k * (a) ≤ k * (b) for all b ∈ A.
Example 5 Let us consider the set of 5 alternatives A = {a 1 , a 2 , a 3 , a 4 , a 5 } and the following preference profile p:

p =         a 1 a 1 a 5 a 5 a 2 a 2 a 4 a 4 a 3 a 3 a 3 a 3 a 4 a 4 a 2 a 2 a 5 a 5 a 1 a 1        
It can be checked that p is single-peaked with respect to the linear order a 1 < a 2 < a 3 < a 4 < a 5 . The critical degree of majority approval of the alternatives a 1 and a 5 is k * (a 1 ) = k * (a 5 ) = 1 < k * (a j ) for all j ∈ {2, 3, 4}. Then, M (p) ⊆ {a 1 , a 5 }. Moreover, the majorities who rank either a 1 or a 5 first have the same size. Therefore, M (p) = {a 1 , a 5 } Before proceeding to the main result of this section, let us state the following lemma from [START_REF] Sertel | The majoritarian compromise is majoritarian-optimal and subgame-perfect implementable[END_REF] which is useful.

Lemma 1 [START_REF] Sertel | The majoritarian compromise is majoritarian-optimal and subgame-perfect implementable[END_REF] The critical degree of majority approval of a majoritarian compromise winner does not exceed m+1

2

.

We are now ready to state our main result regarding single-peaked preferences.

Proposition 3 Let ≤ be a linear order on A and assume without loss of generality that

a 1 < • • • < a m .
Let p be a profile of single-peaked preferences with respect to ≤. Then

M (p) ⊆ SA(p).
Proof. Let p be a profile of single-peaked preferences with respect to ≤. Assume without loss of generality that a 1 < • • • < a m . Let a be a majoritarian compromise winner of p.

The following cases arise:

Case 1: If m is even, then a is socially acceptable by Proposition 1.

Case 2: If m is odd, we distinguish two cases:

Case 2.1: If a = a m+1 2
, then a cannot be below the line for any preference relation in p. To see this, note that by Claim 1, it holds that for all i ∈ N a i a k , either for all k < m+1 2 or for all k > m+1 2 . This means that r(p i , a) ≤ m+1 2 for all i ∈ N . Hence, a is socially acceptable.

Case 2.2: If a = a m+1 2 , assume by contradiction that a is not socially acceptable and let b be the counter of a. Since a ∈ M (p), the critical degree of majority approval of a does not exceed m+1 2 by Lemma 1. Therefore, k * (a) ≤ m+1 2 . Moreover, recalling that a is not socially acceptable, k * (a) ≥ m+1 2 (since there is no majority of voters who rank a above the line). Hence, k * (a) = m+1 2 .

• If b = a m+1 2 (which can be the case either for a = a 1 or a = a m ), then r(p i , b) ≤ m+1 2 , for all i ∈ N (as shown in Case 2.1). It then follows that k

* (b) ≤ m+1 2 . Since a ∈ M (p), then k * (b) ≥ k * (a) = m+1 2 . We deduce that k * (b) = k * (a) = m+1 2 and thus a, b ∈ M (p). Moreover, |K(a, p)| < n since k * (a) = m+1
2 and a is not socially acceptable. It follows that

K(b, p) = i ∈ N : r(p i , b) ≤ m + 1 2 = n > K(a, p) .
This inequality contradicts the fact that a ∈ M (p).

• If b = a m+1 2 (that is, a = a 1 and a = a m ), the counter of b is then a. By Claim 2, the number of voters who place a above the line is exactly the number of voters who prefer a to b. Since a is not socially acceptable, we have that

i ∈ N : r(p i , a) < m + 1 2 < i ∈ N : r(p i , a) > m + 1 2 .
We deduce that n(p, a b) < n(p, b a) and that n(p, b a) > n 2 . Thus, the number of voters who prefer b to a is greater than n 2 , which means that more than half of the voters rank b above the line. Therefore, we have that k * (b) < m+1 2 which implies that k * (a) < m+1 2 . This is a contradiction since k * (a) = m+1 2 . A contradiction holds in both cases. Hence, a is necessarily socially acceptable.

We conclude that any majoritarian compromise winner with respect to a single-peaked preference profile is socially acceptable.

Single-caved preferences

The class of single-caved preferences was introduced by Inada (1964).8 A set of preference relations is single-caved with respect to a linear order of the alternatives if each preference has a "cave" (least preferred alternative) such that for any two alternatives on the same side of the cave, one is preferred over the other if it is more distant from the cave. Singlecaved preference profiles are generated from single-peaked preference profiles by inverting the preference relation of each voter. Single-caved preferences can arise, for instance, in the presence of an undesirable suggested project such as the construction of a prison. In this case, for a voter, the worst location may be the closest to her home, and the more distant a location, the more desirable it is. Formally, Definition 7 Let ≤ be a linear order on A. We say that a preference relation is singlecaved with respect to ≤ if there is an alternative d( ) such that

a < b ≤ d( ) or d( ) ≤ b < a ⇒ (a b).
We say that a profile p = (p 1 , . . . , p n ) is single-caved with respect to ≤ if all the preference relations p i are single-caved with respect to ≤.

The following results from [START_REF] Diss | Social acceptability of Condorcet committees[END_REF] are useful properties of singlecaved preference relations that we will use later. Proof. Let p be a profile of single-caved preferences with respect to ≤ and assume without loss of generality that a 1 < • • • < a m . Let a be a majoritarian compromise winner of p.

The following cases arise:

Case 1: If m is even, then a is socially acceptable by Proposition 1. To prove that a is necessarily socially acceptable, suppose by contradiction that a is not socially acceptable. Since a = a m+1 2 , by Claim 4, let b be the counter of a. Then we have

i ∈ N : r(p i , a) < m + 1 2 < i ∈ N : r(p i , a) > m + 1 2 . Therefore, n(p, a b) < n(p, b a). This implies that n(p, b a) > n 2 . It then follows that {i ∈ N : r(p i , b) < m+1 2 } > n 2 and that k * (b) < m+1 2 . Since a ∈ M (p), it follows that k * (a) < m+1
2 , which means that there is a majority of voters who place a above the line. This is a contradiction since by assumption a is not socially acceptable. This proves that a is necessarily socially acceptable.

Single-crossing preferences

We now restrict our attention to the class of preferences that satisfies the single-crossing property introduced by [START_REF] Mirrlees | An exploration in the theory of optimum income taxation[END_REF]. Roughly speaking, a set of preferences satisfies the single-crossing property if both preferences (individuals or voters) and alternatives can be ordered from "left" to "right" so that if, with respect to a rightist preference, an alternative a is preferred to another alternative b, then the same comparison holds for all other preferences that are to the left of this preference whenever a is at the left of b. In the political area, the single-crossing property makes sense if, for instance, individuals are interpreted as having different ideological characters, arranged on a left-right scale, and alternatives are policies to be chosen by the society. Put in this way, given two policies, one of them more to the right than the other, the more rightist an individual the more she will tend to prefer the right-wing policy over the left-wing one.

Definition 8 Let ≤ be a linear order on A. Let C ⊆ P be a non-empty set of preference relations on A and let be a linear order on C. We say that preference relations in C satisfy the single-crossing property with respect to (≤, ) if for all pairs of alternatives a, b in A and for all pairs of preferences , in C, we have

a < b ⇒ (b a ⇒ b a).
We say that a preference profile p satisfies the single-crossing property if there is a linear order ≤ on A and a linear order on the set of preferences in p, such that the preferences in p satisfy the single-crossing property with respect to (≤, ). with the linear order given by p 1 p 2 p 3 p 4 . We can easily check that the set of preferences C satisfies the single-crossing property with respect to (≤, ).

The next claim from [START_REF] Mahajne | Condorcet winners and social acceptability[END_REF] gives a very useful property of singlecrossing preferences.

Claim 5 [START_REF] Mahajne | Condorcet winners and social acceptability[END_REF] Let p be a profile of single-crossing preferences with respect to (≤, ) for some linear order ≤ on A and for some linear order on the set {p 1 , . . . , p n }. Let i, j, k ∈ N with p i p j p k . Then for any two alternatives a, b ∈ A, if both a i b and a k b, then a j b.

When a set of preferences is ordered with a linear order , we can define its median.

Definition 9 Let p be a profile of preferences and be a linear order on the set of preferences in p. We say that p M is a median preference relation of

p if i ∈ N : p i p M ≥ n 2 and i ∈ N : p M p i ≥ n 2 .
In other words, p M is a median preference of p if at least half of the individual preferences are at least as to the "right" as p M and at least half of the individual preferences are at least as to the "left" as p M . Let us recall the following result from [START_REF] Mahajne | Condorcet winners and social acceptability[END_REF].

Proposition 5 [START_REF] Mahajne | Condorcet winners and social acceptability[END_REF] Let p be a single-crossing preference profile.

The top alternative of any median preference of p is socially acceptable (and Condorcet winner).

The next proposition gives our main result regarding the single-crossing preference profiles.

Proposition 6 Let p = (p 1 , . . . , p n ) be a preference profile that satisfies the single-crossing property. Then M (p) ⊆ SA(p).

Proof. Let ≤ be a linear order on A and be a linear order on the set {p 1 , . . . , p n } such that p satisfies the single-crossing property with respect to (≤, ). Let a be a majoritarian compromise winner of p.

Case 1: If m is even, then a is socially acceptable by Proposition 1. 2 . To prove that a is socially acceptable, suppose on the contrary that a is not socially acceptable. This implies that k * (a) ≥ m+1 This inequality holds in contradiction to the fact that a ∈ M (p). Hence, a is necessarily socially acceptable.

Concluding remarks

Let us first emphasise an important remark. Although the majoritarian compromise rule always selects a socially acceptable alternative for any single-peaked, single-caved, or single-crossing preference profiles, it is worth mentioning that there are some domains for which the result does not hold. Single-peaked and single-caved preferences are two subsets of the broader set of value-restricted preferences (see, for instance, [START_REF] Sen | Quasi-transitivity, rational choice and collective decisions[END_REF].

Another subset of this domain of preferences is the class of group-separable preferences introduced by [START_REF] Inada | A note on the simple majority decision rule[END_REF]. A preference profile is group-separable if each subset (of size three at least) of the set of all the alternatives can be partitioned into two disjoint nonempty subsets such that for each voter, either she prefers every alternative from the first subset to every alternative from the second subset, or she prefers every alternative from the second subset to every alternative from the first subset. The next example shows that the majoritarian compromise winner of a group-separable preference profile can be socially We can check that the profile p is group-separable with the group-separable partition A = {a} ∪ {b, c}: each voter prefers a to every alternative from {b, c} or she prefers every alternative in {b, c} to a. We can also check that M (p) = {b, c} and SA(p) = {c}; that is, b is a majoritarian compromise winner which is socially unacceptable. In other words, being group-separable does not guarantee in a profile that each majoritarian compromise winner is socially acceptable.

To summarise, the paper at hand mainly shows that the majoritarian compromise rule always selects a socially acceptable alternative, except for some profiles when the number of voters is odd. Our study raises many interesting additional questions. Our main objective is to define an extension of the majoritarian compromise rule for multi-winner elections and make some investigations about its social acceptability. As noted earlier, Diss and Mahajne (2020) have already extended the concept of social acceptability to multi-winner elections.

  alternative b in the preference profile p is denoted by N (p, a b) and n(p, a b) = N (p, a b) is the number of such preferences. The set of all possible linear orders on the set A is denoted by P, and the set of all profiles is denoted by P N .

Example 1

 1 Consider a set A = {a, b, c, d} of four alternatives and a preference profile p The first column in p represents the preference relation of voter 1, the second one is the preference relation of voter 2, and so on. The horizontal bar in p indicates the border between the candidates that are ranked above the line and those ranked below the line. The alternatives a and b are socially acceptable in p since they are ranked above the line by three voters and they are ranked below the line by only one voter. However, the alternatives c and d are socially unacceptable since they are ranked above the line by only one voter and below the line by three voters. It can be checked that the maximal satisfaction enjoyed by any majority from any alternative is π(p) = 4. This number corresponds to the satisfaction obtained from the alternative b by the majority composed of voters 3 and 4. It can also be checked that M (p) = {a, b, c} since the alternative a yields the satisfaction of 4 to voter 1, alternative c yields the satisfaction of 4 to voter 2, and alternative b gives it to voters 3 and 4. However, the only alternative that gives this maximal satisfaction to some majority is b. As a result M (p) = {b}. In other words, the alternative b is the only majoritarian compromise winner with respect to p.

  and on the line by at most three voters from {k, q+1, m+k}. Similarly, each alternative a k for q+2 ≤ k ≤ m is ranked above the line by exactly n/2 -1 voters from (N 2 \{k}) ∪ N 3 ∪ N 6 and on the line by exactly two voters from {k, m+k}. Clearly, any alternative a k = a q+1 is ranked above the line by no majority. Now, alternative a q+1 is ranked above the line by exactly m -1 voters from N 1 ∪ N 2 , below the line by exactly m voters from N 3 ∪N 4 ∪{q+1} and on the line by exactly n-(2m-1) voters from N 5 ∪N 6 ∪{m+q+1}. Therefore, π(p) = (m+1)/2, K(a k , p) ≤ n/2-1+3 = (n+4)/2

  It can be checked that M (p) = {a, c}, SA(p) = {a, b, c}, and HAHR(p) = {b}. For the second profile, M (p ) = {a}, SA(p ) = {a, b}, and HAHR(p ) = {a, b}. In both cases, the two rules yield distinct outcomes.

Claim 1 ( 2 }

 12 [START_REF] Mahajne | Condorcet winners and social acceptability[END_REF] Let ≤ be a linear order on A and assume without loss of generality that a1 < • • • < a m .Let be a preference relation that is single-peaked with respect to ≤ and let a, b, and c be any three alternatives such that a < b < c. It holds that (a c) ⇒ (b c), and (c a) ⇒ (b a). Claim 2 (Mahajne and Volij, 2019) Let ≤ be a linear order on A and assume without loss of generality that a 1 < • • • < a m . For any alternative a such that a = a m+1 2 , there is an alternative b (called the counter of a) such that for any preference relation that is single-peaked with respect to ≤, a is ranked above the line by if and only if a is strictly preferred to b by . Precisely, if a = a k for some k ∈ {1, . . . , m-1 then b = a k+ m-1 2 , and if a = a k for some k ∈ { m+1 2 + 1, . . . , m}, then b = a k-m-1 2

Claim 3 (..

 3 [START_REF] Diss | Social acceptability of Condorcet committees[END_REF] Let ≤ be a linear order on A and assume without loss of generality that a1 < • • • < a m .Let a, b, and c be any three alternatives such that a < b < c and let be a single-caved preference with respect to ≤. Then it holds that b a ⇒ c b and b c ⇒ a b. Claim 4 (Diss and Mahajne, 2020) Let p be a profile of single-caved preferences with respect to ≤ and assume without loss of generality that a 1 < • • • < a m . For any alternative a such that a = a m+1 2 , there is an alternative b (called the counter of a), such that for any preference relation that is single-caved with respect to ≤, a is ranked above the line by if and only if a is strictly preferred to b by . Precisely, if a = a k for some k ∈ {1, . . . , m-1 2 }, then b = a k+ m+1 2 and if a = a k for some k ∈ { m+1 2 + 1, . . . , m}, then b = a k-m+1 2 Note that in this case, a is conversely the counter of b because for any k ∈ {1, . . . , Let us now state our result regarding single-caved preferences. Proposition 4 Let ≤ be a linear order on A and assume without loss of generality that a 1 < • • • < a m . Let p be a profile of single-caved preferences with respect to ≤. Then M (p) ⊆ SA(p).

Case 2 :

 2 If m is odd, a cannot be a m+1 2 . Indeed, let us assume that a = a m+1 2 . Given a voter i ∈ N , it holds by Claim 3 that a k i a either for all k such that k < m+1 2 or for all k such that k > m+1 2 . It follows in both cases that r(p i , a) ≥ m+1 2 . This implies that E - a = ∅ and k * (a) ≥ m+1 2 . Since a ∈ M (p), it holds by Lemma 1 that k * (a) ≤ m+1 2 . Hence k * (a) = m+1 2 and k * (c) ≥ m+1 2 for all c ∈ A. Thus, for all c ∈ A, there is no majority of voters who rank c above the line; that is, |E - c | < n 2 . Noting that |E - a | = 0, we deduce that n(mholds. In other words, this means that a = a m+1 2 .

Example 6

 6 Let A = {a, b, c} be a set of three alternatives and a < b < c be a linear order on A. Consider the set C of preferences that contains the following four preference relations

Case 2 :

 2 Consider that m is odd. If we first suppose that a is the top alternative of a median preference, then a is socially acceptable by Proposition 5. Now suppose that a is the top alternative of a no-median preference. Let b be the top alternative of a median preference p M . Since b is socially acceptable, it follows that k * (b) ≤ m+1 2 since there is a majority of voters who rank b among the top m+1 2 alternatives. Recalling that a ∈ M (p), we deduce that k * (a) ≤ k * (b) ≤ m+1

  majority of voters who rank a above the line. Therefore, k * (a) = k * (b) = m+1 2 , π(p) = m+1 2 and |K(a, p)| < n since a is not socially acceptable. In this case, it holds that r(p j , b) ≤ m+1 2 for all j ∈ N . Indeed, let i ∈ N the the individual who ranks b as low as possible. Suppose that r = r(p i , b) > m+1 2 . Then there are r -1 alternatives b 1 , . . . b r-1 with r -1 ≥ m+1 2 such that i strictly preferred each b k to b, k = 1, 2, . . . , r -1. Assume without loss of generality that p i p M . Then by the single-crossing property (Claim 5), it holds that b p j b k for all k ∈ {1, . . . , r -1} and for all j ∈ N such that p M p j . Thus, for all j ∈ N such that p M p j , j prefers b to at least m+1 2 alternatives which means that p j ranks b above the line. Consequently, b is ranked above the line by at least half of the voters and thus k * (b) < m+1 2 . A contradiction arises since k * (b) = m+1 2 . Note that voter i ranks b as low as possible and that r(p i , b) ≤ m+1 2 , which implies that r(p j , b) ≤ m+1 2 for all j ∈ N . Therefore the following holds: K(b, p) = i ∈ N : r(p i , b) ≤ m + 1 2 = n > K(a, p) .

  unacceptable. Consider the set of alternatives A = {a, b, c} and the following preference profile p of n = 9 voters such that

Note that the majoritarian compromise rule can be seen as a refinement of the median voting rule introduced by[START_REF] Bassett | Robust voting[END_REF]. See also[START_REF] Gehrlein | On some limitations of the Median Voting Rule[END_REF].

This rule is called the HAHR (Half Accepted Half Rejected) rule. Its formal definition will be presented in the next section.

It is worth noting that[START_REF] Diss | Social acceptability of Condorcet committees[END_REF] extended the concept of social acceptability to multiwinner elections and in that setup studied the social acceptability of any q-Condorcet committee[START_REF] Gehrlein | The Condorcet criterion and committee selection[END_REF], that is a subset of alternatives where every member of that subset is head-to-head preferred by at least a proportion q ∈] 1 2 , 1] of voters than any non-member alternative. See also[START_REF] Diss | Multi-winner scoring election methods: Condorcet consistency and paradoxes[END_REF],[START_REF] Gehrlein | Condorcet's paradox[END_REF] andGehrlein and Lepelley (2011, 2017).

A preference relation will also be denoted by if the specification of the voter i is useless.

As noticed before,[START_REF] Mahajne | The socially acceptable scoring rule[END_REF] provided an axiomatic characterization of the only scoring rule that always follows the social acceptability principle, namely the HAHR rule. Consequently, they show that SA(p) is non-empty for any profile p.

See footnote 5.

Note that if m = 3, any Condorcet winner is socially acceptable according to[START_REF] Mahajne | Condorcet winners and social acceptability[END_REF].

Sometimes single-caved preferences are also called single-dipped (e.g.,[START_REF] Klaus | Strategy-proof division of a private good when preferences are single-dipped[END_REF].

* Mostapha Diss would like to acknowledge financial support from Région Bourgogne Franche-Comté within the program ANER 2021-2024 (project DSG).


Walid Fathallah

Nahla Ben Amor

Philippe Leray

An optimized Quantum circuit representation of Bayesian networks

Keywords: Bayesian networks, Quantum circuit, Qiskit

In recent years, there has been a significant upsurge in the interest surrounding Quantum machine learning, with researchers actively developing methods to leverage the power of quantum technology for solving highly complex problems across various domains. However, implementing gate-based quantum algorithms on noisy intermediate quantum devices (NISQ) presents notable challenges due to limited quantum resources and inherent noise. In this paper, we propose an innovative approach for representing Bayesian networks on quantum circuits, specifically designed to address these challenges.Our aim is to minimize the required quantum resource needed to implement a Quantum Bayesian network (QBN) on a quantum computer. By carefully designing the sequence of quantum gates within the dynamic circuit, we can optimize the utilization of limited quantum resources while mitigating the impact of noise. Furthermore, we present an experimental study that demonstrates the effectiveness and efficiency of our proposed approach. Through simulations and experiments on NISQ devices, we show that our dynamic circuit representation significantly reduces the resource requirements and enhances the robustness of QBN implementation. These findings highlight the potential of our approach to pave the way for practical applications of Quantum Bayesian networks on currently available quantum hardware.

Introduction

Quantum algorithms are typically expressed in terms of quantum circuits, which describe a computation as a sequence of elementary quantum logic gates acting on qubits. There are many ways of implementing a given algorithm with an available set of elementary operations, and it is advantageous to find an implementation that uses the fewest resources especially on near-term device (NISQ machine) [START_REF] Preskill | Quantum computing in the NISQ era and beyond[END_REF] [START_REF] Leymann | The bitter truth about gate-based quantum algorithms in the nisq era[END_REF]. The depth and width of the quantum circuit is key for evaluating the potential of its successful execution on that particular machines. Optimizing those tow metrics when implementing quantum Bayesian Networks will be the aim of our work. take into account that the depth represent the number of gates to be performed sequentially, and the width is the number of qubits it actually manipulates.

The first tentative to define Quantum Bayesian networks were introduced by Tucci [START_REF] Tucci | Quantum bayesian nets[END_REF] as an analog to classical Bayesian networks. He proposed that the conditional probabilities in a classical Bayesian networks can be represented using quantum complex amplitudes. Tucci argued that there could be infinite possible quantum Bayesian networks for a given classical Bayesian network. Following Tucci ideas, Moreira & Wichert [START_REF] Moreira | Quantum-like bayesian networks for modeling decision making[END_REF] proposed quantum-like Bayesian networks, where the marginal and conditional probabilities were represented using quantum probability amplitudes. To determine the parameters of a quantum Bayesian network, a heuristic method was used which considered similarity between two dimensional vectors corresponding to the two states of the random variables.

In 2014 [START_REF] Low | Quantum inference on bayesian networks[END_REF] discussed the principles of quantum circuit design to represent a Bayesian network with discrete nodes that have two states, and also discussed the circuit design for implementing quantum rejection sampling for inference and recently, Borujeni et al. [START_REF] Borujeni | Quantum circuit representation of bayesian networks[END_REF], proposed Compositional Quantum Bayesian Network (C-QBN) to represent a discrete Bayesian network and discuss the decomposition of complex gates using elementary gates such that they can be implemented on available quantum computing platforms. In this paper, we optimize the circuit construction of Compositional Quantum Bayesian network by reducing the width and the depth. We reuse the qubit that represent a variable from the Bayesian network once it doesn't step in the calculation of another event in the chain rule also we will eliminate the redundancy of not gate in the circuit.

This paper is organized as follows: we will first introduce Quantum computing. Then it moves to present classical and quantum Bayesian networks mainly the work of Borujeni et al. on Quantum Bayesian networks and her approach named (C-QBN) and finally details the proposed method for optimizing a quantum circuit to represent a Bayesian network.

Basic quantum computation

Quantum computers can solve some computational problems exponentially faster than classical computers, which may lead to several applications in field of machine learning. To store and manipulate the information, they use their own quantum bits also called 'Qubits' unlike other classical computers which are based on classical computing that uses binary bits 0 and 1 individually .

Instead of using high and low voltages to represent the 1's and 0's of binary data, we generaly use the two spin states of an electron, |1⟩ and |0⟩ [3][12].

Any measurement made on this states will always yield one of the two eigenvalues with no way of knowing which one. If we prepare an ensemble of identical systems then quantum mechanics assures us that we will observe result 1 with probability |α| 2 and result 0 with probability |β| 2 . Normalization of the state to unity guarantees:

|α| 2 + |β| 2 = 1
Information stored in a 2-states quantum system is called a quantum bit or qubit: besides storing classical 1 and 0 information there is also the possibility of storing information as a superposition of 1 and 0 states.

To represent the state of a qubit, we can use the Bloch sphere. For instance, if we have a qubit that is initially prepared in state |1⟩ and then apply the NOT operator (also known as the Pauli-X gate), we will find the qubit in state |0⟩. This operation corresponds to a rotation of the qubit state vector by 180 degrees around the X-axis of the Bloch sphere.

The reversible logic gates used in classical computing (such as AND, OR, and NOT) have quantum analogues that are implemented using unitary operators that act on the basis states of a qubit. These quantum gates are also reversible and can be used to perform quantum computations. The basic quantum gates include: The Hadamard gate, which creates a superposition of the |0⟩ and |1⟩ states. The Pauli gates which have four different types: R X , R Y and R Z gates corresponding to the three axes of the Bloch sphere (X, Y , and Z), and the identity gate. The R X gate, also known as the NOT gate, flips the value of a qubit from |0⟩ to |1⟩or vice versa. The R Y gate is similar to the R X gate, but also introduces a phase shift around the Y-axis. The CNOT gate, which entangles two qubits and flips the second if the first is in the |1⟩ state. The Measurement gate, which is used to extract classical information from a quantum state by collapsing a qubit to one of its possible classical states.These gates form the basis for constructing more complex quantum circuits. The impact of hardware on quantum algorithms is significant, as the performance of a quantum algorithm is ultimately limited by the quality and capabilities of the underlying quantum hardware. These hardware limitations can affect the performance of quantum algorithms in several ways that can be summarized as follows: the number of qubit and gate limitations, the coherence time, and the error rate.

Therefore, as quantum hardware continues to improve, it is expected that the performance and applicability of quantum algorithms will also improve. This is why the development of high-quality and scalable quantum hardware is one of the key challenges in the field of quantum computing. Meanwhile one of the techniques to cushion the impact of hardware on quantum algorithm is to reduce the size of quantum circuit.

Quantum Bayesian networks

In this section, we first introduce classical Bayesian networks and then their most recent quantum representation proposed by Borujeni et al [START_REF] Borujeni | Quantum circuit representation of bayesian networks[END_REF].

Classical Bayesian networks

Bayesian networks [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF], are among the most powerful probabilistic graphical models representing knowledge and reasoning under uncertainty. Bayesian networks are widely used in artificial intelligence, machine learning, and decision analysis for tasks such as diagnosis, prediction, and decision-making under uncertainty.

They can be used to model complex systems and make predictions about the behavior of those systems, even in the presence of missing or noisy data.

Formally, a Bayesian network BN =< G, P > has two components: The graphical component composed of a directed acyclic graph (DAG) G = (V, E), where G is a DAG with nodes (or vertices V ) representing variables and edges E representing the dependencies between variables. The numerical component P composed of a set of conditional probability distributions P Xi = P (X i | P a(X i )) for each node X i ∈ V in the context of its parents P a(X i ). The set of all these conditional probability tables P is used to define the joint probability distribution over all variables in the network using a chain rule expressed as:

P (X 1 .....X n ) = n i=1 P (X i |P a(X i )) (1)
Example 1 Figure 1 shows an example of a Bayesian network with four binary nodes V = A, B, C, D that we will use in the rest of the article. Inference is a crucial task in Bayesian networks that involves calculating probabilities of interest based on observations or evidence. The two most common types of inference are computing marginal probabilities of a subset of variables and conditional probabilities of a subset of variables given evidence about another subset of variables. Inference is an optimization problem that involves manipulating the joint probability distribution of the Bayesian network, which can be computationally expensive for large and complex networks. It has been proven that this problem is NP-hard [START_REF] Cooper | The computational complexity of probabilistic inference using bayesian belief networks[END_REF].The problem of inference in Bayesian networks has been an active research area for decades, leading to many proposed algorithms and techniques for efficient computation of probabilities [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF][4] .

Compositional Quantum Bayesian networks C-QBN

Recently, Borujeni et al. [START_REF] Borujeni | Quantum circuit representation of bayesian networks[END_REF] introduced a systematic method for designing a quantum circuit to represent a discrete Bayesian network. This method (outlined by Algorithm 1) is mainly based on mapping each variable in a Bayesian network to one or more qubits (depending on its cardinality). Then, it computes associated gates (via the Gates function) by first calculating the probability amplitudes of the qubit states from conditional probabilities, and then by obtaining the probability amplitudes of the associated quantum states through the application of rotational gates. In this representation four gates are used: Hadamard gates X (green), Pauli gates R Y (purple), CNOT gates and measurement gates (black).

Note the use of extra qubits (ancilla bits) that are not part of the input or output of a quantum circuit but are instead used to perform intermediate computations that help to improve the efficiency and accuracy of quantum algorithms. The use of ancilla bits is a common technique in quantum computing.

Algorithm 1: Transformation of a BN into a QC 1. This generates a five-qubit circuit represented in Figure 3. Qubits q 0 , q 1 , and q 2 and q 3 are associated to A, B, C, D, respectively, while q 4 is the ancilla qubit associated to the decomposition on the rotation gate relative to the node D which has 2 parents.

Input : BN =< G = (V,
The resulting quantum circuit can then be used to compute the joint probability of any configuration, or the marginal probability of a subset of variables, by assigning the corresponding values as input of the quantum circuit.

In the proposed method, each node X in the Bayesian network is mapped onto a qubit in a quantum circuit. As mentioned earlier, qubits are a scarce resource in quantum computing, and reducing the number of qubits required to represent the network can provide a significant advantage in representing more complex networks and performing more sophisticated analyses. This is the main idea that we propose in the following section.

Optimized representation of quantum Bayesian networks

In this section, we present an optimized Algorithm that reduces the size of a given quantum Bayesian network circuit compared to Algorithm 1.

The idea is to take advantage of the structure of the DAG in the given Bayesian network to measure and reuse the qubit that represents a node midway through, by using the standard measurement gate before applying further quantum gates. This allows us to reuse a qubit after computing the probability amplitude of all its child nodes.

The optimized version, outlined by Algorithm 2, starts by initializing an empty quantum circuit QC and creating a list P a list that contains all the parents of each node. This list will serve as an indicator to know if there are still nodes that have not been mapped to the circuit and that require the presence of their parents to calculate their probability amplitude. Otherwise, the qubit relative to this node will be measured and added to Available list to be reused for another variable. Then, it iterates over the nodes in V in a topological order. For each node X, it computes the number of extra qubits n needed by the quantum gates to represent its probability distribution. It also computes the number of qubits k required to represent the probability distribution even with the reuse of the reinitialized qubits in Available list .If the node has no parents, it creates a new qubit for it and computes the quantum gates that implement the node's probability distribution G X (X, P X , q X , A X ). Then If P a(X) is already in P a list, the algorithm checks if Available list is empty. Then it creates a new qubit and build its gates. Or it uses a qubit from Available list.

After that, we update the P a list and the Available list, and perform midcircuit measurement if needed, based on the requirements of the not-yet-built nodes, with regard to the presence of their parent nodes, to compute their probability amplitude. Finally, we measure all the qubits that have not yet been measured in V and add these measurements to QC. The resulting quantum circuit can be used to compute the joint probability distribution of the Bayesian network BN.

Example 3 Given the BN in Figure 1, let us consider the following topologically order [A, B, C, D]. We have P a list = [P a(A), P a(B), P a(C), P a(D)] = [A, B, C].We start by considering node A, which is binary and root node. Since A has no parents, we allocate only one qubit, denoted q 0 , to build its gates and add them to the quantum circuit. We do not make any modifications to the available Parent list P a list. Next, we move to the variable B. Similar to A, we allocate one qubit q 1 and build its gates.

Then, we handle variable C which is a parented node with P a(C) = A. To compute its gates, we need the values from A gates because the values expressed by its conditional probability table (P (C | A) are based on A. After computing the probability amplitudes of the qubits q 2 and adding the gates to the circuit, we delete A from P a list and add its relative qubit to Available list because no further nodes in the topological list are dependent on it. This allows us to apply a measurement gate to q 0 then a reset gate, enabling its reuse to map another variable and reducing the global width of the circuit. Finally, we move to the last node D, which has two parents. This requires the use of an extra ancilla qubit (q 3 ), which is added to the node itself, and only one qubit from Available list is added to the circuit 3. This will act on global width of the final circuit by reducing it from 5 qubits using Algorithm 1 to 4 qubits using our algorithm. To evaluate the effectiveness of our algorithm, we analyze the Bayesian network shown in Figure 4, which consists of 10 binary nodes. It is worth noting that this network was previously used in [START_REF] Borujeni | Quantum circuit representation of bayesian networks[END_REF], where Algorithm 1 required 12 qubits Fig. 3. Optimized Quantum circuit of Bayesian network of Figure 2 to transform it into a quantum circuit, while our optimized version only needs 6 qubits. Our main objective is to assess the accuracy of our model in terms of marginal probabilities. To achieve this, we compare the results obtained through an exact inference algorithm applied to the original Bayesian network with those obtained by measuring the quantum circuits generated by Borujeni's algorithm and our optimized approach. We use the mps method from Qiskit Aer, an opensource quantum circuit simulator [START_REF]Qiskit contributors: Qiskit: An open-source framework for quantum computing[END_REF], to simulate the quantum circuits and also execute them on a real quantum machine with 7 qubits (IBM Perth). We ran the

X6 X7 X8 X9 X5 X4 X3 X1 X10 X2
Fig. 4. A 10-node Bayesian network [START_REF] Tavana | An artificial neural network and bayesian network model for liquidity risk assessment in banking[END_REF] Bayesian network circuit five times on a simulator without any hardware noise and on a real quantum computer, each with 20,000 shots. To investigate the effect of width reduction of QBN circuits using the two approaches described in Algorithm 1 and 2, we computed the root mean square error (RMSE) expressed by:

RM SE = N i=1 P (X i = 0) -P (X i = 0) 2 N
where N is the number of nodes in the Bayesian network, P (X i = 0) is the exact probability computed from the full joint distribution, and P (X i = 0) is the probability from the quantum circuit. This measure will indicate the extent to which a set of marginal probabilities computed with a simulator and a real quantum computer deviates from the exact values. The results showed that the RMSE of the optimized circuit is lower than the one generated by Algorithm 1 (3% versus 7%). This improvement is particularly noteworthy given the size of the initial network, and is attributed to the efficient reuse of qubits enabled by our approach.

Note that the circuit generated by Algorithm 1 exceeded the 7 qubits available on the real quantum machine we used, and thus could not be executed. Therefore, we only tested the optimized circuit generated by Algorithm 2.

Clearly, the reduction in the width of the quantum circuit has the potential to improve the error rate as it reduces the number of physical qubits required to implement the circuit. This, in turn, minimizes the complexity of the hardware and mitigates some sources of errors.

Conclusion and perspectives

We have proposed an optimized version to design a quantum circuit to represent Bayesian networks based on C-QBN approach. Our approach takes advantage of the structure of the DAG in Bayesian networks to measure and reuse the qubit that represents a node midway through, by using the standard measurement gate before applying further quantum gates. This allows us to reuse a qubit after computing the probability amplitude of all its child nodes.

This technique has been shown to reduce the width of the quantum circuit even on small networks, as demonstrated by the example with 10 nodes, where it resulted in a reduction of half the number of qubits required to implement the QBN circuit. As a result, the reduction in the number of required qubits leads to a simplification of the hardware and helps to alleviate certain sources of errors.

While our first experiments with two examples showed promising results, further investigation on more complex Bayesian networks is needed to fully evaluate the effectiveness of our technique in reducing the width of quantum circuits. As access to quantum hardware with larger numbers of qubits becomes available under certain conditions, we plan to test our approach on more challenging problems. In addition, we will investigate the potential benefits of reducing the number of qubits required for implementing a quantum circuit, which could provide additional resources for improving the overall reliability of the computation. One approach we will explore is integrating error correction techniques directly into the circuit design, which could further reduce error rates.

Fig. 1 .

 1 Fig. 1. A 4-nodes Bayesian network

Fig. 2 .

 2 Fig. 2. Quantum circuit of Bayesian network of Figure 1

  To illustrate Algorithm 1, we reconsider the Bayesian network of Figure

	E), P >
	Output: A quantum circuit QC
	QC ← an empty quantum circuit
	for each X in topological order of V do
	Create a qubit qX
	AX ← empty
	for each Y in P a(X) do
	Create ancilla qubit ax
	Add ax to AX
	end
	for i in |Dom(P a(X))| -2 do
	Create ancilla qubit ax
	Add ax to AX
	end
	GX ← Gates(X, PX , qX , Ax)
	Add GX to QC
	end
	for each X in V do
	Measure(qX , QC)
	end
	Example 2

Algorithm 2: Optimized transformation of a BN into a QC Measure(q P a(X) , QC) Reset(q P a(X) ,AX ) Add(Available list, q P a(X) , AX ) else if Count(P a list, P a(X)) >