1 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 rule has two main advantages that should be stressed: it is easily understood by voters; and most importantly it provides a quick decision in the sense that the winner determination for this rule takes less time than 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 Sertel and Yılmaz (1999). 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.Footnote 1 Note that this voting system has been the subject of many investigations in the literature such as Brams and Kilgour (2001), Dindar and Lainé (2022), Giritligil and Sertel (2005), Kondratev and Nesterov (2018), Laffond and Lainé (2012), Llamazares and Peña (2015), Merlin et al. (2006); Merlin et al. (2019) and Nurmi (1999), among others.

The concept of social acceptability was introduced in the literature by Mahajne and Volij (2018). 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 in 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. Mahajne and Volij (2018) characterised the only scoring Social Choice Rule (SCR) that satisfies the social acceptability principle, that is, the only scoring SCR that always selects a socially acceptable alternative for any preference profile.Footnote 2

It is worth noting that Mahajne and Volij (2019) 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\in ]\frac{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=\frac{1}{2}\)) is socially acceptable.Footnote 3 Note also that Awde et al. (2023) evaluate the probability that some well-studied SCRs elect a socially unacceptable candidate by making well-known assumptions about how voters might behave in the election process.

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 single-peaked, 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, Sect. 3 states and proves our results, and Sect. 4 concludes.

2 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\ge 3\) and \(n\ge 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\in N\), the (linear) ranking or the preference relation of i is denoted by \(p_{i}\) or \(\succ _{i}\)Footnote 4 and the n-tuple \(p=(p_{1},p_{2},\dots ,p_{n})\) is called a preference profile (or simply a profile) which specifies the ranking of each voter. The set of all possible linear orders on the set A is denoted by \({\mathcal {P}}\), and the set of all profiles with set of voters N is denoted by \({\mathcal {P}}^{N}\). For any two alternatives a and b, we write \(a\succ _{i} b\) if voter i strictly prefers a to b. The rank of any alternative \(a\in A\) in the preference relation \(p_{i}\) of voter i is denoted by \(r(p_{i},a)\) and it is defined by

$$\begin{aligned} r(p_{i},a)=\Big \vert \Big \{b\in A:b\succ _{i}a\Big \}\Big \vert +1=m-\Big \vert \Big \{b\in A:a\succ _{i}b\Big \}\Big \vert . \end{aligned}$$
(1)

The set of voters who strictly prefer alternative a to alternative b in the preference profile p is denoted by \(N(p,a\succ b)\) and \(n(p,a\succ b)=\big |N(p,a\succ b)\big |\) is the number of such voters.

An 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: for any two sets of voters N and \(N'\) with the same cardinality such that \(N'=\sigma (N)\), where \(\sigma \) is any bijection between N and \(N'\), replacing the set N by the set \(N'\) while saving the same preference relations (i.e., \(\succ _i=\succ _{\sigma (i)}\) for all \(i\in N\)) does not affect the social outcome of any profile. We then simply write \({\mathcal {P}}^{n}\) instead of \({\mathcal {P}}^{N}\) to denote the set of all profiles with set of voters 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 \(\cup _{n=2}^{\infty }{\mathcal {P}}^{n}\).

A scoring vector of size m is an m-tuple \(\alpha =(\alpha _{1},\alpha _{2},\dots ,\alpha _{m})\) of real numbers such that \(\alpha _{1}\ge \alpha _{2}\ge \dots \ge \alpha _{m}\) and \(\alpha _{1}>\alpha _{m}\). An SCR can be associated with the scoring vector \(\alpha \) as follows: given a profile \(p\in \cup _{n=2}^{n=\infty }{\mathcal {P}}^{n}\) and an alternative a, across individual preferences in p, alternative a receives \(\alpha _{1}\) points for each first position, \(\alpha _{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_{\alpha }(p,a) \). It is formally defined by

$$\begin{aligned} S_{\alpha }(p,a)=\sum _{i=1}^{n}\alpha _{r(p_{i},a)}, \end{aligned}$$
(2)

where \(\alpha _{r(p_{i},a)}\) denotes the score in the vector \(\alpha \) 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 \(\alpha \) is denoted by \(F_{\alpha }\) and it selects the set of all alternatives having the maximum score \(S_{\alpha }(p,a)\) taking into account all voter preferences in the profile \( p\in \cup _{n=2}^{n=\infty }{\mathcal {P}}^{n}\). Well-known scoring SCRs \(F_{\alpha }\) include the Plurality rule, the Antiplurality rule, the Borda rule, and the t-approval rule which respectively correspond to the scoring vectors \((1,0,\dots ,0)\), \( (1,\dots ,1,0)\), \((m-1,m-2,\dots ,1,0)\), and \((\underbrace{1,\dots ,1}_{t \text{ times } },\underbrace{ 0,\dots ,0}_{m-t \text{ times } })\). Note that Mahajne and Volij (2018) introduced a new scoring SCR called the Half Accepted Half Rejected (HAHR) rule which is defined by the scoring vector \((\alpha _1,\alpha _2,\dots ,\alpha _m)\) such that

$$\begin{aligned} \alpha _j=\left\{ \begin{array}{rll} +1 &{} \text{ if } &{} j<\frac{m+1}{2} \\ 0 &{} \text{ if } &{} j=\frac{m+1}{2} \\ -1 &{} \text{ if } &{} j>\frac{m+1}{2} \end{array} \right. \end{aligned}$$
(3)

Following (Mahajne and Volij 2018), 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 A be a set of m alternatives, N be a set of voters, and p be a preference profile. An alternative \(a\in 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:

$$\begin{aligned} \left| \left\{ i\in N:r(p_{i},a)<\frac{m+1}{2}\right\} \right| \ge \left| \left\{ i\in N:r(p_{i},a)>\frac{m+1}{2}\right\} \right| . \end{aligned}$$

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\in \cup _{n=2}^{n=\infty }{\mathcal {P}} ^{n}\), \(F(p)\subseteq SA(p)\), that is:

$$\begin{aligned} \forall a\in A, \Big (a\in F(p) \Longrightarrow a\in SA(p)\Big ), \end{aligned}$$

meaning that an SCR satisfies the social acceptability principle if it always selects a socially acceptable alternative for any preference profile.Footnote 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\in A\) and any voter \(i\in N\), we denote by \(\pi _{i}(a)\) the integer \(m-r(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\subseteq N\), we define the satisfaction of K with regard to the alternative a by

$$\begin{aligned} \pi _{K}(a)=\min \Big \{\pi _{i}(a):i\in K\Big \}. \end{aligned}$$
(4)

In other words, \(\pi _{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: \(\big |K\big |\ge |N\setminus K|\). We denote by \({\mathcal {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

$$\begin{aligned} {\overline{\pi }}(p)=\max \Big \{\pi _K(a): K\in {\mathcal {M}}, a\in A\Big \}, \end{aligned}$$
(5)

and we denote by

$$\begin{aligned} {\overline{M}}(p)=\Big \{a\in A: \exists i\in N, \pi _i(a)={\overline{\pi }}(p)\Big \}, \end{aligned}$$
(6)

the set of all alternatives that give the maximal satisfaction \({\overline{\pi }}(p)\) to at least one voter. For any alternative \(a\in {\overline{M}}(p)\), we define

$$\begin{aligned} K(a,p)=\Big \{i\in N: \pi _i(a)\ge {\overline{\pi }}(p)\Big \}, \end{aligned}$$
(7)

as the set of all voters who enjoy at least \({\overline{\pi }}(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 \({\overline{\pi }}(p)\) to at least one voter (i.e., among the alternatives in the set \({\overline{M}}(p)\)) those which give it to the largest majority.

Definition 3

The majoritarian compromise rule is the social choice rule \( M:\cup _{n=2}^{n=\infty }{\mathcal {P}}^n\longrightarrow 2^A\) defined by

$$\begin{aligned} M(p)=\Big \{a\in {\overline{M}}(p): b\in {\overline{M}}(p)\Longrightarrow \big |K(b,p)\big |\le \big |K(a,p)\big |\Big \}, \end{aligned}$$

where \(2^A\) stands for the set of all possible subsets of A.

Example 1 illustrates the previous definitions.

Example 1

Consider a set \(A=\{a, b, c, d\}\) of four alternatives and a preference profile p of four voters such that

$$\begin{aligned} p=\left[ \begin{array}{cccc} a &{} c &{} b &{} b \\ b &{} a &{} d &{} a \\ \hline c &{} b &{} a &{} d \\ d &{} d &{} c &{} c. \end{array} \right] \end{aligned}$$

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 \({\overline{\pi }}(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 \({\overline{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.

3 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.

3.1 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)\subseteq SA(p)\).

Proof

Assume that \(m=2q\;(q\in {\mathbb {N}}^{*})\). Let p be a preference profile and \(c\in M(p)\). Since \(SA(p)\ne \emptyset \),Footnote 6 consider \(a\in 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 \(\pi _{K}(a)\ge q+1\). Therefore, \({\overline{\pi }}(p)\ge q+1\) and since \(c\in M(p)\) there exists a majority \(T\in {\mathcal {M}}\) such that \(\pi _{T}(c)= {\overline{\pi }}(p)\ge q+1\). This implies that \(\min _{i\in T}\{\pi _{i}(c)\}=m-\max _{i\in T}r(p_{i},c)+1\ge q+1\), that is, \(\max _{i\in T}r(p_{i},c)\le q<\frac{m+1}{2}\). Thus all voters in T rank the alternative c above the line. Since T is a majority, then \(c\in SA(p)\). \(\square \)

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)\subseteq SA(p)\) if and only if:

$$\begin{aligned} n\le \left\{ \begin{array}{ll} 2m+2 &{}\text{ if } \text{ n } \text{ is } \text{ even } \\ m+2 &{}\text{ if } \text{ n } \text{ is } \text{ odd } \end{array} \right. \end{aligned}$$

Proof

Assume that \(m=2q+1 (q\in {\mathbb {N}}^*)\) and pose \(A=\{a_1,\dots ,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\in M(p)\) and \(c\notin 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\in A\):

$$\begin{aligned} E_x= & {} \Big \{(i,k): i\in N, k\in \{1,\dots ,q+1\}, r(p_i,x)=k\Big \}\\ E_x^-= & {} \Big \{(i,k): i\in N, k\in \{1,\dots ,q\}, r(p_i,x)=k\Big \}\\ E_x^+= & {} \Big \{(i,k): i\in N, k\in \{q+2,\dots , m\}, r(p_i,x)=k\Big \} \end{aligned}$$

Note that each \((i,k)\in E_x\cup E_x^-\cup 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)\ne \emptyset \), let us consider \(b\in SA(p)\). There is a majority of voters K who rank b among the top \((q+1)\) alternatives, and for that majority we have \(\pi _K(b)\ge q+1\), which implies that \({\overline{\pi }}(p)=\pi _T(c)\ge q+1\) for some majority T. Since \(c\notin SA(p)\), the satisfaction of any majority from c is at most \(q+1\), i.e., \({\overline{\pi }}(p)=\pi _T(c)\le 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 \({\overline{\pi }}(p)=q+1=\pi _T(c)\).

Case 1: Suppose that n is even and let \(n=2t\; (t\in {\mathbb {N}}^*)\).

Since \({\overline{\pi }}(p)=q+1=(m+1)/2\), there is no majority of voters who rank any alternative above the line. Then, \(|E_x^-|\le t-1=(n-2)/2\) for all \(x\in A\). This implies that

$$\begin{aligned} \big |E_c^-\big |=\left| \bigcup _{x\ne c}E_x^-\right| =\displaystyle \sum _{x\ne c}\big |E_x^-\big |\le (m-1)\frac{n-2}{2}. \end{aligned}$$
(8)

Thus, we have \( \big |E_c^-\big |=nq-\big |\bigcup _{x\ne c}E_x^-\big |\ge 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 \(\big |E_c^+\big |>\big |E_c^-\big |\) which implies that \(\big |E_c^+\big |\ge m\) since \(\big |E_c^-\big |\ge m-1\) by (8). It follows that \(\big |E_c\big |=n-\big |E_c^+\big |\le n-m\). We deduce that

$$\begin{aligned} \left| \bigcup _{x\ne c}E_x\right| =\displaystyle \sum _{x\ne c}|E_x|=n(q+1)-|E_c|\ge n \frac{m+1}{2}-(n-m). \end{aligned}$$
(9)

Recalling that \(c\in M(p)\), it follows that \(\big |E_x\big |\le \big |E_c\big |=\big |K(c,p)\big |\) for any other alternative \(x\ne 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

$$\begin{aligned} \left| \bigcup _{x\ne c}E_x\right| =\displaystyle \sum _{x\ne c}\big |E_x\big |\le (m-1)\big |E_c\big |\le (m-1)(n-m). \end{aligned}$$
(10)

From inequalities (9) and (10), we deduce that \(n(m+1)/2-(n-m)\le (m-1)(n-m)\), which is equivalent to \(n\ge 2m^2/(m-1)\). Hence \(n> 2\,m+2\) since \(2\,m^2/(m-1)>2\,m+2\) for all integers m such that \(m\ge 3\).

Case 2: Suppose n is odd and let \(n=2t+1\; (t\in {\mathbb {N}}^*)\).

Since \({\overline{\pi }}(p)=q+1=(m+1)/2\), there is no majority of voters who rank any alternative above the line. This implies that \(\big |E_x^-\big |\le t=(n-1)/2\) for all \(x\in A\). We deduce that

$$\begin{aligned} \left| \bigcup _{x\ne c}E_x^-\right| =\displaystyle \sum _{x\ne c}\big |E_x^-\big |\le (m-1)\frac{n-1}{2}. \end{aligned}$$
(11)

Thus, we have \(\big |E_c^-\big |=nq-\big |\bigcup _{x\ne c}E_x^-\big |\ge nq-(m-1)(n-1)/2=(m-1)/2\) since \(q=(m-1)/2\). Moreover, since c is not socially acceptable, we have \(\big |E_c^+\big |>\big |E_c^-\big |\) which implies by (11) that \(\big |E_c^+\big |\ge (m-1)/2+1=(m+1)/2\). It follows that \(\big |E_c\big |=n-\big |E_c^+\big |\le n-(m+1)/2\). Therefore,

$$\begin{aligned} \left| \bigcup _{x\ne c}E_x\right| =\displaystyle \sum _{x\ne c}\big |E_x\big |=n(q+1)-\big |E_c\big |\ge n \frac{m+1}{2}-\left( n-\frac{m+1}{2}\right) . \end{aligned}$$
(12)

Furthermore, \(c\in M(p)\). Therefore, \(\big |E_x\big |\le \big |E_c\big |=\big |K(c,p)\big |\) for all \(x\in A\backslash \{c\}\). This implies that

$$\begin{aligned} \left| \bigcup _{x\ne c}E_x\right| =\displaystyle \sum _{x\ne c}\big |E_x\big |\le (m-1)\big |E_c\big |\le (m-1)\left( n-\frac{m+1}{2}\right) . \end{aligned}$$
(13)

From (12) and (13), we deduce that

$$\begin{aligned} n\frac{m+1}{2}-\left( n-\frac{m+1}{2}\right) \le (m-1)\left( n-\frac{m+1}{2}\right) . \end{aligned}$$

Equivalently, \(n\ge 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\in M(p)\) such that c is not socially acceptable.

Case 1: Suppose that n is even and \(n>2m+2\). This means that \( n\ge 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=\big \{1,2,\dots ,q\big \}\), \(N_2=\big \{q+2,q+3,\dots ,2q+1=m\big \}\), \(N_3=\big \{m+1,m+2,\dots ,m+q\big \}\), \(N_4=\big \{m+q+2,\dots ,2m\big \}\), and \(\big |N_5\big |=\big |N_6\big |=(n-2m)/2\), and consider the partition of N defined by \(N=N_1\cup N_2\cup N_3\cup N_4\cup N_5\cup N_6\cup \{q+1\}\cup \{m+q+1\}\). In the following profile p, each individual’s preference is constructed around one of the two rankings \(r_1=a_1a_2\dots a_m \) and \(r_2=a_m a_{m-1}\dots 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:

$$\begin{aligned} p_i= & {} \varvec{a}_{\mathbf {q+1}}a_1a_2\dots a_{i-1}a_{i+1}\dots a_q \varvec{a}_{\varvec{i}} a_{q+2}\dots a_m \text { for }i\in N_1\text { (with }j=i \text { in }r_1)\\ p_i= & {} \varvec{a}_{\varvec{q+1}}a_{m}a_{m-1}\dots a_{i+1}a_{i-1}\dots a_{q+2} \varvec{a}_{\varvec{i}} a_{q}\dots a_1 \text { for }i\in N_2 \text { (with }j=i \text { in }r_2)\\ p_{m+i}= & {} a_ma_{m-1}\dots a_{q+2} \varvec{a}_{\varvec{i}} \varvec{a}_{\varvec{q+1}}a_{q}\dots a_{i+1} a_{i-1}\dots a_1\text { for }m+i\in N_3\text { (with }j=i \text { in }r_2)\\ p_{m+i}= & {} a_1a_2\dots a_q \varvec{a}_{\varvec{i}} \varvec{a}_{\varvec{q+1}}a_{q+2}\dots a_{i-1} a_{i+1}\dots a_m\text { for }m+i\in N_4\text { (with }j=i \text { in }r_1)\\ p_{q+1}= & {} a_{m}a_{m-1}\dots a_{q+2}\varvec{a}_{\varvec{1}}\varvec{a}_{\varvec{q+1}}a_{q}\dots a_{2} \text { (with }j=1 in r_2)\\ p_{i}= & {} r_1\text { for }i\in N_5 \cup \{m+q+1\}\text { and }p_{i}=r_2\text { for }i\in N_6 \end{aligned}$$

For this profile, each alternative \(a_k\) for \(1\le k \le q\) is ranked above the line by exactly \(n/2-1\) voters from \(\left( N_1\backslash \{k\}\right) \cup N_4\cup N_5\cup \{m+q+1\}\) and on the line by at most three voters from \(\{k,q+1,m+k\}\). Similarly, each alternative \(a_k\) for \(q+2\le k \le m\) is ranked above the line by exactly \(n/2-1\) voters from \(\left( N_2\backslash \{k\}\right) \cup N_3\cup N_6\) and on the line by exactly two voters from \(\{k,m+k\}\). Clearly, any alternative \(a_k\ne 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\cup N_2\), below the line by exactly m voters from \(N_3\cup N_4\cup \{q+1\}\) and on the line by exactly \(n-(2m-1)\) voters from \( N_5\cup N_6\cup \{m+q+1\}\). Therefore, \({\overline{\pi }}(p)=(m+1)/2\), \(\big |K(a_k,p)\big |\le n/2-1+3=(n+4)/2\) for all \(a_k\ne a_{q+1}\) and \(\big |K(a_{q+1},p)\big |=m-1+n-(2m-1)=n-m\). Since \(n\ge 2m+4\), it follows that \(\big |K(a_{q+1},p)\big |\ge (n+4)/2\ge \big |K(a_k,p)\big |\) for all \(a_k\ne a_{q+1}\). Thus, \(a_{q+1}\in 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\ge 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=\big \{1,2,\dots ,q\big \}\), \(N_2=\big \{q+1,q+2,\dots ,2q\big \}\), \(N_3=\big \{m\big \}\) and \(\big |N_4\big |=\big |N_5\big |=(n-m)/2\). Using the same operations as in the previous case, the following profile p is built from \(r_1=a_1a_2\dots a_m \) or \(r_2=a_m a_{m-1}\dots a_1 \) as follows:

$$\begin{aligned} p_i= & {} \varvec{a}_{\mathbf {q+1}}a_1a_2\dots a_{i-1}a_{i+1}\dots a_q \varvec{a}_{\varvec{i}} a_{q+2}\dots a_m \text { for }i\in N_1\text { (with } j=i \text { in } r_1)\\ p_{q+i}= & {} a_{m}a_{m-1}\dots a_{q+2}\varvec{a}_{\varvec{i}}\varvec{a}_{\varvec{q+1}}a_q\dots a_{i+1} a_{i-1}\dots a_1 \text { for }q+i\in N_2 \text { (with } j=i \text { in }r_2)\\ p_{m}= & {} a_{1}a_{2}\dots a_{q}\varvec{a}_{\varvec{m}}\varvec{a}_{\varvec{q+1}}a_{q+2}\dots a_{m-1} \text { (with }j=m\text { in }r_1)\\ p_{i}= & {} r_1\text { for }i\in N_4 \text { and }p_{i}=r_2\text { for }i\in N_5\\ \end{aligned}$$

For this profile, each alternative \(a_k\) with \(1\le k \le q\) is ranked above the line by exactly \((n-1)/2\) voters from \(\left( N_1\backslash \{k\}\right) \cup N_4\cup \{m\}\) and on the line by two voters from \(\{k,q+k\}\); each alternative \(a_k\) with \(q+2\le k \le m\) is ranked above the line by exactly \((n-1)/2\) voters from \(N_2\cup N_5\) and on the line by at most one voter from \(\{m\}\). Clearly, any alternative \(a_k\ne 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\cup \{m\}\), and on the line by exactly \(n-m\) voters from \( N_4\cup N_5\). Therefore, \({\overline{\pi }}(p)=(m+1)/2\), \(\big |K(a_k,p)\big |\le (n-1)/2+2=(n+3)/2\) for all \(a_k\ne a_{q+1}\) and \(\big |K(a_{q+1},p)\big |=(m-1)/2+n-m=n-(m+1)/2\). Since \(n\ge m+4\), it follows that \(\big |K(a_{q+1},p)\big |\ge (n+3)/2\ge \big |K(a_k,p)\big |\) for all \(a_k\ne a_{q+1}\). Thus, \(a_{q+1}\in 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. \(\square \)

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:

$$\begin{aligned} p=\left[ \begin{array}{cccccccccccccc} 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 \\ \hline 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 \\ \hline 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 \end{array} \right] \end{aligned}$$

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,Footnote 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 SCR 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'\):

$$\begin{aligned} p=\left[ \begin{array}{cccc} a &{} a &{} c &{} c \\ b &{} b &{} b &{} b \\ \hline c &{} c &{} a &{} a \\ d &{} d &{} d &{} d \end{array} \right] \qquad p^{\prime }=\left[ \begin{array}{ccc} a &{} a &{} b \\ \hline b &{} b &{} c \\ \hline c &{} c &{} a \end{array} \right] \end{aligned}$$

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

3.2 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.

3.2.1 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 \(\le \) be a linear order on A. We say that a preference relation \(\succ \) is single-peaked with respect to \(\le \) if there is an alternative \(p(\succ )\), called the peak, such that

$$\begin{aligned} \big (b<a\le p(\succ ) \text{ or } p(\succ )\le a<b\big )\Rightarrow (a\succ b). \end{aligned}$$

We say that a preference profile \(p=(p_1,\dots ,p_n)\) is single-peaked with respect to \(\le \) if all preference relations \(p_i\) are single-peaked with respect to \(\le \).

The next two claims from Mahajne and Volij (2019) are very useful properties of single-peaked preferences that we will use in order to facilitate our proof.

Claim 1

(Mahajne and Volij 2019) Let \(\le \) be a linear order on A and assume without loss of generality that \(a_1<\dots <a_m\). Let \(\succ \) be a preference relation that is single-peaked with respect to \(\le \) and let a, b, and c be any three alternatives such that \(a<b<c\). It holds that \((a\succ c)\Rightarrow (b\succ c)\), and \((c\succ a)\Rightarrow (b\succ a)\).

Claim 2

(Mahajne and Volij 2019) Let \(\le \) be a linear order on A and assume without loss of generality that \(a_1<\dots <a_m\). For any alternative a such that \( a\ne a_{\frac{m+1}{2}}\), there is an alternative b (called the counter of a) such that for any preference relation \(\succ \) that is single-peaked with respect to \(\le \), a is ranked above the line by \( \succ \) if and only if a is strictly preferred to b by \(\succ \).

Precisely, if \(a=a_k\) for some \(k\in \{1,\dots ,\lceil \frac{m-1}{2}\rceil \}\) then \( b=a_{k+\lceil \frac{m-1}{2}\rceil }\), and if \(a=a_k\) for some \(k\in \{\lfloor \frac{m+1}{2}\rfloor +1,\dots ,m\}\), then \(b=a_{k-\lceil \frac{m-1}{2}\rceil }\). We can remark that when the number of alternatives is odd, for any \( k\not \in \{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\succ a_2\succ a_3\succ a_4\succ 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 kth degree approval" from K if \( r(p_i,a)\le k\) for all \(i\in K\), which means that \(\pi _K(a)\ge m-k+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\in M(p)\), we have that \(\overline{\pi }(p)=m-k^*(a)+1\) which is equivalent to saying that \(k^*(a)\le k^*(b)\) for all \(b\in 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:

$$\begin{aligned} p=\left[ \begin{array}{cccc} 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\\ \end{array} \right] \end{aligned}$$

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\in \{2, 3, 4\}\). Then, \(M(p)\subseteq \{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 Sertel and Yılmaz (1999) which is useful.

Lemma 1

(Sertel and Yılmaz 1999) The critical degree of majority approval of a majoritarian compromise winner does not exceed \( \lfloor \frac{m+1}{2}\rfloor \).

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

Proposition 3

Let \(\le \) be a linear order on A and assume without loss of generality that \(a_1<\dots <a_m\). Let p be a profile of single-peaked preferences with respect to \(\le \). Then \(M(p)\subseteq SA(p)\).

Proof

Let p be a profile of single-peaked preferences with respect to \(\le \). Assume without loss of generality that \(a_1<\dots <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_{\frac{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\in N\) \(a\succ _{i}a_k\), either for all \( k<\frac{m+1}{2}\) or for all \(k>\frac{m+1}{2}\). This means that \(r(p_i,a)\le \frac{m+1}{2}\) for all \(i\in N\). Hence, a is socially acceptable.

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

  • If \(b=a_{\frac{m+1}{2}}\) (which can be the case either for \(a=a_1\) or \(a=a_m\)), then \(r(p_i,b)\le \frac{m+1}{2}\), for all \(i\in N\)(as shown in Case 2.1). It then follows that \(k^*(b)\le \frac{m+1}{2}\). Since \(a\in M(p)\), then \(k^*(b)\ge k^*(a)=\frac{m+1}{2}\). We deduce that \(k^*(b)=k^*(a)=\frac{m+1}{2}\) and thus \(a,b\in {\overline{M}}(p)\). Moreover, \(|K(a,p)|<n\) since \(k^*(a)=\frac{m+1}{2}\) and a is not socially acceptable. It follows that

    $$\begin{aligned} \big \vert K(b,p)\big \vert =\left| \left\{ i\in N:r(p_i,b)\le \frac{m+1}{2}\right\} \right| =n>\big \vert K(a,p)\big \vert . \end{aligned}$$

    This inequality contradicts the fact that \(a\in M(p)\).

  • If \(b\ne a_{\frac{m+1}{2}}\) (that is, \(a\ne a_1\) and \(a\ne 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

    $$\begin{aligned} \left| \left\{ i\in N:r(p_i,a)<\frac{m+1}{2}\right\} \right| <\left| \left\{ i\in N:r(p_i,a)>\frac{m+1}{2}\right\} \right| . \end{aligned}$$

    We deduce that \(n(p,a\succ b)<n(p,b\succ a)\) and that \(n(p,b\succ a)>\frac{n}{2}\). Thus, the number of voters who prefer b to a is greater than \(\frac{n}{2} \), which means that more than half of the voters rank b above the line. Therefore, we have that \(k^*(b)<\frac{m+1}{2}\) which implies that \(k^*(a)< \frac{m+1}{2}\). This is a contradiction since \(k^*(a)=\frac{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. \(\square \)

3.2.2 Single-caved preferences

The class of single-caved preferences was introduced by Inada (1964).Footnote 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. Single-caved 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 \(\le \) be a linear order on A. We say that a preference relation \( \succ \) is single-caved with respect to \(\le \) if there is an alternative \( d(\succ ) \) such that

$$\begin{aligned} \big (a<b\le d(\succ ) \text{ or } d(\succ )\le b<a\big )\Rightarrow (a\succ b). \end{aligned}$$

We say that a profile \(p=(p_1,\dots ,p_n)\) is single-caved with respect to \( \le \) if all the preference relations \(p_i\) are single-caved with respect to \(\le \).

The following results from Diss and Mahajne (2020) are useful properties of single-caved preference relations that we will use later.

Claim 3

(Diss and Mahajne 2020) Let \(\le \) be a linear order on A and assume without loss of generality that \(a_1<\dots <a_m\). Let a, b, and c be any three alternatives such that \(a<b<c\) and let \(\succ \) be a single-caved preference with respect to \(\le \). Then it holds that \(b\succ a\Rightarrow c\succ b\) and \(b\succ c\Rightarrow a\succ b\).

Claim 4

(Diss and Mahajne 2020) Let p be a profile of single-caved preferences with respect to \(\le \) and assume without loss of generality that \(a_1<\dots <a_m\). For any alternative a such that \(a\ne a_{\frac{m+1}{2}}\), there is an alternative b (called the counter of a), such that for any preference relation \(\succ \) that is single-caved with respect to \(\le \), a is ranked above the line by \(\succ \) if and only if a is strictly preferred to b by \(\succ \).

Precisely, if \(a=a_k\) for some \(k\in \{1,\dots ,\lceil \frac{m-1}{2}\rceil \}\), then \(b=a_{k+\lfloor \frac{m+1}{2}\rfloor }\) and if \(a=a_k\) for some \(k\in \{\lfloor \frac{m+1}{2} \rfloor +1,\dots ,m\}\), then \(b=a_{k-\lfloor \frac{m+1}{2}\rfloor }\). Note that in this case, a is conversely the counter of b because for any \( k\in \{1,\dots ,\lceil \frac{m-1}{2}\rceil \}, a_{k+\lfloor \frac{m+1}{2} \rfloor }\ne a_{\frac{m+1}{2}}\) and for any \(k\in \{\lfloor \frac{m+1}{2} \rfloor +1,\dots ,m\}, a_{k-\lfloor \frac{m+1}{2}\rfloor }\ne a_{\frac{m+1}{2} } \). Let us now state our result regarding single-caved preferences.

Proposition 4

Let \(\le \) be a linear order on A and assume without loss of generality that \(a_1<\dots <a_m\). Let p be a profile of single-caved preferences with respect to \(\le \). Then \(M(p)\subseteq SA(p)\).

Proof

Let p be a profile of single-caved preferences with respect to \(\le \) and assume without loss of generality that \(a_1<\dots <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, a cannot be \(a_{\frac{m+1}{2}}\). Indeed, let us assume that \(a=a_{\frac{m+1}{2}}\). Given a voter \(i\in N\), it holds by Claim 3 that \(a_k\succ _{i}a\) either for all k such that \(k<\frac{m+1}{2}\) or for all k such that \(k>\frac{m+1}{2}\). It follows in both cases that \(r(p_i,a)\ge \frac{m+1}{2}\). This implies that \(E^-_a=\emptyset \) and \(k^*(a)\ge \frac{m+1}{2}\). Since \(a\in M(p)\), it holds by Lemma 1 that \(k^*(a)\le \frac{m+1}{2}\). Hence \(k^*(a)=\frac{m+1}{2}\) and \(k^*(c)\ge \frac{m+1}{2} \) for all \(c\in A\). Thus, for all \(c\in A\), there is no majority of voters who rank c above the line; that is, \(|E^-_c|<\frac{n}{2}\). Noting that \(|E^-_a|=0\), we deduce that \(\displaystyle \frac{n(m-1)}{2}=\displaystyle \sum _{c\ne a}|E_c^-|<\frac{n(m-1)}{2}\) and a contradiction holds. In other words, this means that \(a\ne a_{ \frac{m+1}{2}}\).

To prove that a is necessarily socially acceptable, suppose by contradiction that a is not socially acceptable. Since \(a\ne a_{\frac{m+1}{2}}\), by Claim 4, let b be the counter of a. Then we have

$$\begin{aligned} \left| \left\{ i\in N:r(p_i,a)<\frac{m+1}{2}\right\} \right| < \left| \left\{ i\in N: r(p_i,a)>\frac{m+1}{2}\right\} \right| . \end{aligned}$$

Therefore, \(n(p,a\succ b)<n(p,b\succ a).\) This implies that \(n(p,b\succ a)>\frac{n}{2}\). It then follows that \(\big |\{i\in N: r(p_i,b)<\frac{m+1}{2}\}\big | >\frac{n}{2}\) and that \(k^*(b)<\frac{m+1}{2}\). Since \(a\in M(p)\), it follows that \(k^*(a)<\frac{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. \(\square \)

3.2.3 Single-crossing preferences

We now restrict our attention to the class of preferences that satisfies the single-crossing property introduced by Mirrlees (1971). 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 \(\le \) be a linear order on A. Let \({\mathcal {C}}\subseteq {\mathcal {P}}\) be a non-empty set of preference relations on A and let \(\sqsubseteq \) be a linear order on \({\mathcal {C}}\). We say that preference relations in \(\mathcal { C}\) satisfy the single-crossing property with respect to \((\le ,\sqsubseteq )\) if for all pairs of alternatives a, b in A and for all pairs of preferences \( \succ , \succ ^{\prime }\) in \({\mathcal {C}}\), we have

$$\begin{aligned} \left. \begin{array}{c} a<b \\ \succ \sqsubseteq \succ ^{\prime } \end{array} \right\} \Rightarrow (b\succ a\Rightarrow b\succ ^{\prime }a). \end{aligned}$$

We say that a preference profile p satisfies the single-crossing property if there is a linear order \(\le \) on A and a linear order \(\sqsubseteq \) on the set of preferences in p, such that the preferences in p satisfy the single-crossing property with respect to \((\le , \sqsubseteq ).\)

Example 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 \({\mathcal {C}}\) of preferences that contains the following four preference relations

$$\begin{aligned} p=\left[ \begin{array}{cccc} a&{}a&{}c&{}c\\ b&{}c&{}a&{}b\\ c&{}b&{}b&{}a\\ \end{array} \right] \end{aligned}$$

with the linear order given by \(p_1\sqsubset p_2\sqsubset p_3\sqsubset p_4.\) We can easily check that the set of preferences \({\mathcal {C}}\) satisfies the single-crossing property with respect to \((\le ,\sqsubseteq )\).

The next claim from Mahajne and Volij (2019) gives a very useful property of single-crossing preferences.

Claim 5

(Mahajne and Volij 2019) Let p be a profile of single-crossing preferences with respect to \((\le , \sqsubseteq )\) for some linear order \(\le \) on A and for some linear order \(\sqsubseteq \) on the set \(\{p_1,\dots ,p_n\}\). Let \(i,j,k\in N\) with \( p_i\sqsubset p_j\sqsubset p_k\). Then for any two alternatives \(a,b\in A\), if both \(a\succ _{i}b\) and \(a\succ _{k}b\), then \(a\succ _{j}b\).

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

Definition 9

Let p be a profile of preferences and \(\sqsubseteq \) be a linear order on the set of preferences in p. We say that \(p_M\) is a median preference relation of p if

$$\begin{aligned} \Big \vert \big \{i\in N: p_i\sqsubseteq p_M\big \}\Big \vert \ge \frac{n}{2} \text{ and } \Big \vert \big \{i\in N: p_M\sqsubseteq p_i\big \}\Big \vert \ge \frac{n}{2}. \end{aligned}$$

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 Mahajne and Volij (2019).

Proposition 5

(Mahajne and Volij 2019) 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,\dots ,p_n)\) be a preference profile that satisfies the single-crossing property. Then \(M(p)\subseteq SA(p)\).

Proof

Let \(\le \) be a linear order on A and \(\sqsubseteq \) be a linear order on the set \(\{p_1,\dots ,p_n\}\) such that p satisfies the single-crossing property with respect to \((\le , \sqsubseteq )\). Let a be a majoritarian compromise winner of p.

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

Case 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)\le \frac{m+1}{2}\) since there is a majority of voters who rank b among the top \(\frac{m+1}{2}\) alternatives. Recalling that \(a\in M(p)\), we deduce that \(k^*(a)\le k^*(b)\le \frac{m+1}{2}\). To prove that a is socially acceptable, suppose on the contrary that a is not socially acceptable. This implies that \(k^*(a)\ge \frac{m+1}{2} \) since there is no majority of voters who rank a above the line. Therefore, \( k^*(a)=k^*(b)=\frac{m+1}{2}\), \({\overline{\pi }}(p)=\frac{m+1}{2}\) and \(|K(a,p)|<n\) since a is not socially acceptable. In this case, it holds that \(r(p_j,b)\le \frac{m+1}{2}\) for all \(j\in N\). Indeed, let \(i\in N\) the the individual who ranks b as low as possible. Suppose that \( r=r(p_i,b)>\frac{m+1}{2}\). Then there are \(r-1\) alternatives \(b_1,\dots b_{r-1}\) with \(r-1\ge \frac{m+1}{2}\) such that i strictly preferred each \(b_k\) to b, \(k=1,2,\dots ,r-1\). Assume without loss of generality that \(p_i\sqsubseteq p_M\). Then by the single-crossing property (Claim 5), it holds that \( b\succ _{p_j}b_k\) for all \(k\in \{1,\dots ,r-1\}\) and for all \(j\in N\) such that \(p_M\sqsubseteq p_j\). Thus, for all \(j\in N\) such that \(p_M\sqsubseteq p_j\), j prefers b to at least \(\frac{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)<\frac{m+1}{2}\). A contradiction arises since \(k^*(b)=\frac{m+1}{2}\). Note that voter i ranks b as low as possible and that \(r(p_i,b)\le \frac{m+1}{2}\), which implies that \(r(p_j,b)\le \frac{m+1}{2}\) for all \(j\in N\). Therefore the following holds:

$$\begin{aligned} \Big \vert K(b,p)\Big \vert = \left| \left\{ i\in N:r(p_i,b)\le \frac{m+1}{2}\right\} \right| =n>\Big \vert K(a,p)\Big \vert . \end{aligned}$$

This inequality holds in contradiction to the fact that \(a\in M(p)\). Hence, a is necessarily socially acceptable. \(\square \)

4 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, Sen 1969). Another subset of this domain of preferences is the class of group-separable preferences introduced by Inada (1964). 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 non-empty 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 unacceptable. Consider the set of alternatives \(A=\{a, b, c\}\) and the following preference profile p of \(n=9\) voters such that

$$\begin{aligned} p=\left[ \begin{array}{ccccccccc} a &{} a &{} a &{} a &{} c &{} c &{} c &{} c &{} b \\ \hline b &{} b &{} c &{} c &{} b &{} b &{} b &{} b &{} c \\ \hline c &{} c &{} b &{} b &{} a &{} a &{} a &{} a &{} a \end{array} \right] \end{aligned}$$

We can check that the profile p is group-separable with the group-separable partition \(A=\{a\}\cup \{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 summarize, 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 alternatives is odd. Our study raises many interesting additional questions. One of possible issues is to set up an extension of the majoritarian compromise rule for multi-winner elections and make some investigations with regards to social acceptability and other suitable properties in the multi-winner framework. Note that multi-winner elections are voting situations wherein instead of choosing a single winner a society is required to select a fixed-size subset of candidates, such as parliamentary elections or shortlisting tasks. Many well-known SCRs have been adapted to the multi-winner context and the study of their features in this context has received increasing interest in the recent literature of social choice theory (see, e.g., Bubboloni et al. 2020; Elkind et al. 2017; Faliszewski et al. 2016). As noted earlier, Diss and Mahajne (2020) have already extended the concept of social acceptability to multi-winner elections. A fixed-size subset of candidates is said to be socially acceptable if all of its members are socially acceptable, it is socially partly (un)acceptable if some of its members are socially acceptable and the others are socially unacceptable, and it is socially completely unacceptable if all of its members are socially unacceptable. It seems to us that the extension of the majoritarian compromise rule to the multi-winner framework and the study of its properties (e.g., social acceptability) in this context is an interesting research direction to follow.