Creating an acceptable consensus ranking for group decision making

Abstract

This paper examines the problem of combining a set of ordinal rankings to form an acceptable consensus ranking. The objective of traditional group decision making problem is to determine the Minimum Violation Ranking. Motived by the applications of adjusted consensus in recent years, we study this problem from a new perspective, for obtaining an acceptable consensus ranking for group decision making. In this paper, every voter ranks a set of alternatives respectively, and we know the acceptability index, which represents the minimum adjustments that are allowed for each voter. The problem is to find the Minimum Acceptable Violation Ranking (MAVR) which minimizes the sum of voter’s unacceptable violations. Besides, we develop a branch and bound ranking algorithm to solve this problem. The suggested improvement include: (1) analysing the ranking preference by two ways: pairwise preference and ranking-based preference; (2) constructing the lower bound and upper bound, which exclude at most half of the feasible solutions in each iteration process. Furthermore, the effectiveness and efficiency of this algorithm are verified with an example and numerical experiments. Finally, we discuss two extensions of the basic MAVR problem: the Minimum Weighted Acceptable Violation problem, whose voters are accompanied with a set of weights or multiples, and the Minimum Hierarchy Acceptable Violation problem, which uses hierarchical acceptability indexes. In addition, our results can be applied to other ranking and subset selection problems in which provide consensus rankings over the alternatives.

1 Introduction

Group decisions are widely used in many areas: the president election, the Oscar film review, allocation of priorites to projects, and so on. In the group decision making setting, every voter ranks a subset of alternatives based on his or her own preference, and the chairman has to combine all the individual rankings together into a group choice or consensus ranking as the ultimate result. Such a voting format is common in group decision making, where a set of available alternatives (candidates in an election, projects, ..., etc.) are required to fill a complete ranking positions. Additional requirement of transitivity must be present as well.

The traditional group decision making based on ordinal ranking has been studied for over 200 years. De Borda (1781) firstly proposed this concept by using the average ranks assigned by voters. The most common and simplest way of group decision making is majority rule. For mathematical properties and applications of majority decision rule, one may be referred to Inada (1969), Bowman and Colantoni (1973) and the references there in. Further the majority rule problem under transitivity property is solved in Blin and Whinston (1974) as an integer progamming problem.

An excellent work in Kendall (1948) proposed a preference vector to describe group decision making. If voters represent their preferences in terms of priority, a form of group consensus can be derived by adding the individual preference vector together. Wei (1952) tried to obtain the consensus preference by using strength vector method. Then Kendall (1955) extended this problem by aggregating the individual preference vector together and taking their average. This work does not lead to a consensus which under transitivity property. However, it is fundamental to the latter problem which we concentrate on herein.

Using Kendall preference distance function, a novel group consensus was introduced independently by Kemeny and Snell (1962). Their model aggregated the individual preference difference by pairwise comparisons of the form “alternative a is preferred to alternative b , alternative a is preferred to alternative c , etc ”. The pairwise difference can be viewed as an distance measure. Such a measure would be an indicator of the degree of consensus between voter’ ranking and consensus ranking. The objective function is to minimize the total violation distance (or differences) between every voters preference and “consensus”ranking preference. They named this problem as Minimum Violation Ranking (MVR) problem. Cook (1976) used a branch and bound ranking algorithm to solve this MVR problem by determining the median. Then Blin (1976) and other scholars (Cook and Seiford 1978, 1982; Ali et al. 1986) extended the distance among rankings through various approaches. Further, Barzilai et al. (1986) used an equivalent positive KS (PKS) form and expressed this problem as a network for solving it more efficiently. Cook et al. (1988) used heuristics to find the order ranking with a minimum violation. Furthermore, Cook and Kress (1990) gave us some transformed models based on the Date Envlopement Model (DEA) framework. Also, there are many transformed MVR problem, such as Cook et al. (2007) came up with a partial MVR problem and solved it with a branch and bound ranking algorithm. Recently Rademaker and De Baets (2014) formulated a new ranking procedure for the initial MVR problem and gave some great properties of this ranking procedure.

We know that people probably have violation (or difference) acceptability when they are involved in a group decision making environment. It means that people will ignore (or accept) the violation (or difference) if the violation is not significant. We pay more attention to minimize the total unacceptable violations. This concept has been used in group adjusted consensus decisions for more than twenty years since Herrera and Herrera-Viedma (1996). A common framework of the adjusted consensus model is as the notable consensus model presented by Herrera-Viedma et al. (2002). For instance, Dong et al. (2014, 2015) applied the adjusted consensus in linguistic preference enviornment. In this type of consensus models, at first we obtain a collective opinion from individual opinions. The consensus level among voters is then obtained by using the consensus measure to calculate the difference between the individual opinions and the collective opinion. Finally, when the consensus level is unacceptable (greater than the established level $\alpha$), a feedback process is used to help experts adjust their individual opinions. The adjusted consensus in continous model is well studied in the literature, see for example Herrera-Viedma et al. (2007), Ben-Arieh and Easton (2007), Ben-Arieh et al. (2009) and elsewhere. In recent years, based on Ben-Arieh and Chen (2006)’ work, Zhang et al. (2011, 2013, 2014) did some further reasearch for multiple consensus rules.

However, few researchers apply the adjusted consensus to the traditional discrete group decision making. In this paper, we attempt to model a new MVR problem with an acceptability index. We permit every voter to adjust their preferences less than or equal to a constant step (saying, acceptability index) before we calculate the violation. Then we associated the problem of consensus derivation in terms of a violation distance measure. The unique objective is to find a ranking C for which the total violation distance between C and the set of all voters adjusted rankings (it is also called unacceptable violations) is minimized. This problem can be titled as Minimum Acceptable Violation Ranking (MAVR) problem.

While the MVR problem is NP-hard for it is equivalent either to a minimum feedback edge set problem (Isaak and Narayan 2004), or a problem of which the group preference matrix has the property of being an upper and lower triangular (it is also called transitivity property) (Even 2011). Both of them are NP-complete or NP-hard. The MAVR problem, we shall study in this paper, is more difficult because we have to identify whether voters violate the acceptability index or not. Thus, the branch and bound algorithm is a reasonable method to solve this problem.

The rest of the paper is organized as follows. In Sect. 2, we present a set of definitions and describe the connection between them. The problem of determining the MAVR is then shown with two equivalent formulations based on different distance forms. Having formulated the MAVR problem, we examine, in Sect. 3, the properties of optimal consensus ranking. The most important thing is, that we present a branch and bound ranking procedure with a tight upper bound and a tight lower bound. In Sect. 4, we give an example to illustrate the algorithm and report a set of numerical experiments to evaluate its effeciency and effectiveness. Finally in Sect. 5 we discuss the Minimum Weighted Acceptable Violation (MWAVR) problem and the Minimum Hierarchy Acceptable Violation (MHAVR) problem, and show how to transform MWAVR and MHAVR to be a MAVR problem for obtaing the optimal consensus ranking, respectively. Concluding remarks and possible future studies are given in Sect. 6.

2 Formulation

Based on a set of definitions and two transformations, we derive a formulation of MAVR problem.

2.1 Preliminaries

We introduce some basic concepts and network formations of MAVR problem. Let $X=\{x_{1},x_{2},\ldots ,x_{m}\}$ be a discrete set of alterntives, $E=\{e_{1},e_{2},\ldots ,e_{n}\}$ be the set of voters that participate in the group decision making and $R=\{R^{1},R^{2},\ldots ,R^{n}\}$ be the set of ordinal ranking matrix. We denote $\alpha$ as the acceptability index, which denotes the established adjustment threshold. The acceptability index $\alpha$ must be even because for each pair of violation, the violation distance is $\left| 0-1\right| +\left| 1-0\right| =2$.

Definition 1

(Kemeny and Snell 1962) Let $A^{l}=(a^{l}_{ij})_{m*m}(l=1,2,\ldots ,n)$, where  $a_{ij}\ge 0$ and $a_{ij}+a_{ji}=1$, be the preference decision matrix which we assume that the pairwise preference are given by the voter $e_{l}$, where $a^{l}_{ij}$ represents the preference between $x_{i}\in X$ and $x_{j}\in X$, and

$$\begin{aligned} a^{l}_{ij}= {\left\{ \begin{array}{ll} 1 \quad \text{ if } \text{ voter } e_{l} \text{ deems } \text{ that } \text{ alternative } x_{i} \text{ is } \text{ preferred } \text{ to } \text{ alternative } x_{j} , \\ 0 \quad \text{ otherwise }. \end{array}\right. } \end{aligned}$$

Definition 2

Let $R^{l}=(r^{l}_{ij})_{m*m} (l=1,2,\ldots ,n)$ be the ranking decision matrix given by voter $e_{l}\in E$, where $r^{l}_{ij}$ presents that the ranking order of alternative $x_{i}\in X$ is jth $\left( j\in \left\{ 1,2,\ldots ,m \right\} \right)$, and

$$\begin{aligned} r_{ij}^{l}={\left\{ \begin{array}{ll} 1 \quad \text{ if } \text{ voter } e_{l} \text{ deems } \text{ that } \text{ alternative } x_{i} \text{ is } \text{ j } \text{ th }, \\ 0 \quad \text{ otherwise }, \end{array}\right. } \end{aligned}$$

s.t.

$$\begin{aligned} \sum _{i=1}^{m}{r}_{ij}^{l}= & {} 1 \ \ \ \ l=1,\ldots ,n, j=1,\ldots ,m, \\ \sum _{j=1}^{m}{r}_{ij}^{l}= & {} 1 \ \ \ \ l=1,\ldots ,n, i=1,\ldots ,m. \end{aligned}$$

It is obvious that $A^{l}$ can be derived from $R^{l}$, and $R^{l}$ can be derived from $A^{l}$, too. For example, (1) the ranking $R^{l}$ of three alternatives $x_{1},x_{2}$ and $x_{3}$ in which $x_{1}$ is first, $x_{2}$ is second, and $x_{3}$ is third would be represented by

(2) the preference $A^{l}$ of three alternatives $x_{1}$, $x_{2}$ and $x_{3}$ in which the alternative $x_{1}$ is preferred to the alternative $x_{3}$, the alternative $x_{1}$ is preferred to the alternative $x_{2}$, the alternative $x_{3}$ is preferred to the alternative $x_{2}$ would be represented by

Definition 3

(PKS distance) Generally, Positive Kemeny and Snell distance (Barzilai et al. 1986) is used for representing the difference (or violation) of two preference decision matrixes $A^{l}=(a^{l}_{ij})_{m*m}$ and $C=(c_{ij})_{m*m}$:

$$\begin{aligned} d_{PKS}(A^{l},C)=\sum _{i=1}^{m}\sum _{j=1}^{m} \left| a^{l}_{ij}-c_{ij} \right| . \end{aligned}$$

Definition 4

(Ranking distance) Given two ranking decision matrix $R^{l}=(r^{l}_{ij})_{m*m}$ and $\tilde{C}=(\tilde{c}_{ij})_{m*m}$, the ranking distance (or violation) between them is given by:

$$\begin{aligned} d_{RD}(R^{l},\tilde{C})=\sum _{i=1}^{m}\sum _{j=1}^{m} v_{ij}, \end{aligned}$$

where

$$\begin{aligned} v_{ij}={\left\{ \begin{array}{ll} 1 \quad \left( \sum _{i_{1}} i_{1}*r^{l}_{i,i_{1}}-\sum _{j_{1}} j_{1}*r^{l}_{j,j_{1}}\right) *\left( \sum _{i_{1}} i_{1}*\tilde{c}_{i,i_{1}}-\sum _{j_{1}} j_{1}*\tilde{c}_{j,j_{1}}\right) <0, \\ 0 \quad \text {otherwise}. \end{array}\right. } \end{aligned}$$

If $A^{l}=(a^{l}_{ij})_{m*m}$ is derived from $R^{l}=(r^{l}_{ij})_{m*m}$ (or $R^{l}=(r^{l}_{ij})_{m*m}$ is derived from $A^{l}=(a^{l}_{ij})_{m*m}$), and $C=(c_{ij})_{m*m}$ is derived from $\tilde{C}=(\tilde{c}_{ij})_{m*m}$ (or $\tilde{C}=(\tilde{c}_{ij})_{m*m}$ is derived from $C=(c_{ij})_{m*m}$), we have $d_{RD}(R^{l}, \tilde{C})= d_{PKS}(A^{l},C)$. It is obvious. Because the two distances are both defined based on the same meaning, the differences between voter’s preference and the consensus preference. They are just formed by two different methods.

Definition 5

(Violating voters and no-violating voters) Given a set of preference decision rankings $\{ A^{1}, A^{2},\ldots , A^{n}\}$, and a consensus preference decision matrix C . If voter $e_{l}$’s violation(PKS distance between $A^{l}$ and C ) is not less than $\alpha$, $e_{l}$ is a violating voter; otherwise, $e_{l}$ is a no-violating voter.

For example, there are 50 voters involved in an election, and the acceptability index is 4. The voters will be divided into two parts, as shown in Fig. 1, called violating voter, whose PKS distance is greater than (or equal to) the acceptability index (above /on the red line), and no-violating voter, whose PKS distance is less than the acceptability index (below the red line).

Fig. 1

A 50-voter election (with an acceptability index)

2.2 Minimum acceptable violation ranking model

Definition 6

(Acceptable PKS distance (APD)) Given a set of preference decision matrixes $\{ A^{1}, A^{2},\ldots , A^{n}\}$, the unacceptable violation of a ranking C (in matrix representation) is given by

$$\begin{aligned} V(C)=\sum _{l=1}^{n} d_{APD}(B^{l},C) =\sum _{l=1}^{n}\sum _{i=1}^{m}\sum _{j=1}^{m} \left| b_{ij}^{l}-c_{ij} \right| \end{aligned}$$

s.t.

$$\begin{aligned} \sum _{i}^{m}\sum _{j}^{m} \left| a_{ij}^{l} - b_{ij}^{l} \right| \le \alpha \ \ \ \ l= & {} 1,\ldots ,n, \\ c_{ij} \ \text {satisfies transitivity property} \ \ \ i= & {} 1,\ldots ,m, j=1,\ldots ,m . \end{aligned}$$

where $A^{l}$ is the initial preference matrix of voter $e_{l}$, $B^{l}=(b_{ij}^{l})_{m*m}$ is the adjusted preference matrix of voter $e_{l}$ after $k^{l}$ adjustments $( k^{l}\leqslant \alpha )$, $C=(c_{ij})_{m*m}$ is a feasible consensus preference decision matrix.

There are some axioms which such distance $d_{ARD}$ in this paper should satisfy, similar to those of Arrow (1951). They are the usual conditions for a violation measurement with the additional requirement that the distance is linear. We required:

Axiom 1.:

$d(A,B)\ge 0$ with equality iff $A=B$.

Axiom 2.:

$d(A,B)\ge d(B,A)$.

Axiom 3.:

$d(A,C)\le d(A,B)+d(A,C)$ with equality iff the ranking B is between A and C . (We say that ranking B is between A and C is for each voter the adjusted ranking of B is preferred because it provides much better consensus availability for group decision making).

Definition 7

(Acceptable consensus preference) The consensus preference $C^{*}$ is that preference which minimizes the total absolute distance

$$\begin{aligned} V(C)=\sum _{l=1}^{n} d_{APD}(B^{l},C) =\sum _{l=1}^{n}\sum _{i=1}^{m}\sum _{j=1}^{m} \left| b_{ij}^{l}-c_{ij} \right| \end{aligned}$$

(2.1)

s.t.

$$\begin{aligned} \sum _{i}^{m}\sum _{j}^{m} \left| a_{ij}^{l} - b_{ij}^{l} \right| \le \alpha \ \ \ \ l= & {} 1,\ldots ,n, \\ c_{ij} \ \text {satisfies transitivity property} \ \ \ i= & {} 1,\ldots ,m, j=1,\ldots ,m . \end{aligned}$$

The above preference can also be presented as below (for details see Appendix 1).

$$\begin{aligned} \min V_{0}(C) =\sum _{l=1}^{n} d_{APD}(A^{l},B^{l}) =\sum _{l=1}^{n}\sum _{i=1}^{m}\sum _{j=1}^{m} \left| b_{ij}^{l}-a_{ij}^{l} \right| \end{aligned}$$

s.t.

$$\begin{aligned} \sum _{i}^{m}\sum _{j}^{m} \left| c_{ij} - b_{ij}^{l} \right| \le \alpha \ \ \ \ l= & {} 1,\ldots ,n, \\ c_{ij} \ \text {satisfies transitivity property} \ \ \ i= & {} 1,\ldots ,m, j=1,\ldots ,m . \end{aligned}$$

It’s similar to the linear adjusted consensus group decision making linear model (Ben-Arieh and Easton 2007).

In Theorem 1, we will simplify the objective notation of Problem 2.1 by removing the adjusted preference decision matrix $B^{l}=(a^{l}_{ij})_{m*m}$.

Theorem 1

Problem 2.1 is equivalent to Problem 2.2

$$\begin{aligned} \min _{c_{ij}} \sum _{l=1}^{n} \ \ max \left\{ \sum _{i=1}^{m}\sum _{j=1}^{m} \left| a_{ij}^{l} - c_{ij} \right| ,\alpha \right\} . \end{aligned}$$

(2.2)

s.t.

$$\begin{aligned} c_{ij} \ \text {satisfies transitivity property} \ \ \ i=1,\ldots ,m, j=1,\ldots ,m . \end{aligned}$$

Proof

We firstly prove that Problem 2.1 is equivalent to Problem 2.3

$$\begin{aligned} \min _{c_{ij}} \sum _{l=1}^{n} \ \ \left[ max \left\{ \sum _{i=1}^{m}\sum _{j=1}^{m} \left| a_{ij}^{l} - c_{ij} \right| ,\alpha \right\} -\alpha \right] . \end{aligned}$$

(2.3)

s.t.

$$\begin{aligned} c_{ij} \ \text {satisfies transitivity property} \ \ \ i=1,\ldots ,m, j=1,\ldots ,m . \end{aligned}$$

The MAVR model allows all voters to adjust their preferences as more as possible (not greater than acceptability index) before calculating the violation distance. If voter $e_{l}$ is a violating voter, minimizing objective requires that the adjusted violation does equal to $\alpha$; otherwise, the adjusted violation equals to $d_{PKS}(A^{l},C)$.

(i) For a violating voter, we have $\sum _{i=1}^{m}\sum _{j=1}^{m} \left| a_{ij}^{l} - c_{ij} \right| \ge \alpha$. Because $d(A^{l},C)= d(A^{l},B^{l})+d(A^{l},C)$, to minimize the unacceptable violations between $B^{l}$ and C , we have

$$\begin{aligned} \sum _{i=1}^{m}\sum _{j=1}^{m} \left| a_{ij}^{l} - b_{ij}^{l} \right| = \alpha . \end{aligned}$$

So we have

$$\begin{aligned} \sum _{i=1}^{m}\sum _{j=1}^{m} \left| b_{ij}^{l} - c_{ij} \right| = \sum _{i=1}^{m}\sum _{j=1}^{m} \left| a_{ij}^{l} - c_{ij} \right| - \alpha = max \left\{ \sum _{i=1}^{m}\sum _{j=1}^{m} \left| a_{ij}^{l} - c_{ij} \right| ,\alpha \right\} -\alpha . \end{aligned}$$

(ii) For a no-violating voter, we have $\sum _{i=1}^{m}\sum _{j=1}^{m} \left| a_{ij}^{l} - c_{ij} \right| < \alpha$. Because $d(A^{l},C)= d(A^{l},B^{l})+d(A^{l},C)$, to minimize the unacceptable violations between $B^{l}$ and C , we have

$$\begin{aligned} \sum _{i=1}^{m}\sum _{j=1}^{m} \left| a_{ij}^{l} - b_{ij}^{l} \right| = \sum _{i=1}^{m}\sum _{j=1}^{m} \left| a_{ij}^{l} - c_{ij} \right| . \end{aligned}$$

So we have

$$\begin{aligned} \sum _{i=1}^{m}\sum _{j=1}^{m} \left| b_{ij}^{l} - c_{ij} \right| =0 = max \left\{ \sum _{i=1}^{m}\sum _{j=1}^{m} \left| a_{ij}^{l} - c_{ij} \right| ,\alpha \right\} -\alpha . \end{aligned}$$

Obviously, adding a constant to or removing a constant from the objective function will not affect the result. Hence, we add $n*\alpha$ to transfer Problem 2.3 to Problem 2.2.

This proves the theorem. $\square$

The greatest difficulty in solving this problem is to deal with the requirement that the elements $c_{ij}$ in the optimal preference decision matrix C must satisfy transitivity property (Isaak and Narayan 2004; Even 2011). An order relation is said to be transitive if it satisfies for all three alternatives $x_{i}, x_{j}, x_{k}$: $x_{i}\succ x_{j}$ and $x_{j}\succ x_{k} \Rightarrow x_{i}\succ x_{k}$.

Definition 8

(Acceptable ranking distance (ARD)) Given a set of rankings $\left\{ R^{1},R^{2},\ldots ,R^{n}\right\}$, the unacceptable violation of a ranking $\tilde{C}$(in matrix representation) is given by

$$\begin{aligned} V_{1}(\tilde{C})=\sum _{l=1}^{n} d_{ARD}(R^{l},\tilde{C} )= \sum _{l=1}^{n} \sum _{i=1}^{m}\sum _{j=1}^{m} w_{ij}^{l} \end{aligned}$$

where $w_{ij}^{l}= \left\{ \begin{array}{ll} 1 &{}\quad v_{ij}^{l}=1 , \ d_{RD}(R^{l},\tilde{C})\ge \alpha , \\ \frac{\alpha }{d_{RD}(R^{l},\tilde{C})} &{}\quad v_{ij}^{l}=1 , \ 0< d_{RD}(R^{l}, \tilde{C})< \alpha , \\ 0 &{}\quad \text{ otherwise }, \end{array}\right.$

$d_{RD}(R^{l},\tilde{C})=\sum _{i}\sum _{j} v^{l}_{ij}$, and

$$\begin{aligned} v^{l}_{ij}={\left\{ \begin{array}{ll} 1 &{}\quad \!\!\!\left( \sum _{i_{1}} i_{1}*r^{l}_{i,i_{1}}- \sum _{j_{1}} j_{1}*r^{l}_{j,j_{1}} \right) *\left( \sum _{i_{1}} i_{1}*\tilde{c}_{i,i_{1}}- \sum _{j_{1}} j_{1}*\tilde{c}_{j,j_{1}} \right) <0, \\ 0 &{}\quad \!\!\text{ otherwise }. \end{array}\right. } \end{aligned}$$

If $A^{l}$ is derived from $R^{l}$ ( or $R^{l}$ is derived from $A^{l}$) and C is derived from $\tilde{C}$ (or $\tilde{C}$ is derived from C), we have $d_{ARD}(R^{l},\tilde{C})=d_{APD}(A^{l},C)$. It is obvious. Because the two acceptable distances are defined based on a same meaning, the unacceptable violations (differences) between voter’s preference and the consensus preference. They are just formed from two different methods.

Definition 9

(Acceptable consensus ranking) Given a set of rankings $\{R^{1},R^{2},\ldots ,R^{n}\}$, the consensus $\tilde{C}^{*}$ ranking is that ranking which minimizes the total absolute distance

$$\begin{aligned} V_{1}(\tilde{C})=\sum _{l=1}^{n} d_{ARD}(R^{l},\tilde{C} )= \sum _{l=1}^{n} \sum _{i=1}^{m}\sum _{j=1}^{m} w_{ij}^{l}. \end{aligned}$$

Theorem 2

Problem 2.2 is equivalent to Problem 2.4.

$$\begin{aligned} \min _{\tilde{c}_{ij}} V_{1}(\tilde{C}) \end{aligned}$$

(2.4)

s.t.

$$\begin{aligned} \sum _{i=1}^{m}\tilde{c}_{ij}^{l}=1, \ \ \ \ l=1,\ldots ,n, j=1,\ldots ,m,\\ \sum _{j=1}^{m}\tilde{c}_{ij}^{l}=1, \ \ \ \ l=1,\ldots ,n, i=1,\ldots ,m. \end{aligned}$$

The elements $\tilde{c}_{ij}$ in the ranking matrix $\tilde{C}$ do not need to satisfy transitivity property.

Proof

According to Definition 8, for any arbitrary ranking decision matrix $\tilde{C}$, we have the following.

(i) For an arbitrary voter $e_{l}$, if $d_{ARD}(R^{l},\tilde{C}) \ge \alpha$ holds,

for any pair of alternatives $(x_{i},x_{j})$, if $x_{i}$ is preferred to $x_{j}$ both in $R^{l} \ and \ \tilde{C}$, we have $w_{ij}^{l}= \left| a_{ij}^{l} - c_{ij} \right| =0;$

for any pair of alternatives $(x_{i},x_{j})$, if $x_{i}$ is preferred to $x_{j}$ in $R^{l}$ but not in $\tilde{C}$; or $x_{i}$ is preferred to $x_{j}$ in $\tilde{C}$ but not in $R^{l}$, we have $w_{ij}^{l}= \left| a_{ij}^{l} - c_{ij} \right| =1.$

Therefore, $d_{ARD}(R^{l},\tilde{C})=\sum _{i}\sum _{j} w_{ij}^{l}= max \left\{ \sum _{i}\sum _{j} \left| a_{ij}^{l} - c_{ij} \right| ,\alpha \right\}$ holds.

(ii) For an arbitrary voter $e_{l}$, if $d_{ARD}(R^{l},\tilde{C}) < \alpha$ holds,

for any pair of alternatives $(x_{i},x_{j})$, if $x_{i}$ is preferred to $x_{j}$ both in $R^{l} \ and \ \tilde{C}$, we have $w_{ij}=\left| a_{ij}^{l} - c_{ij} \right| =0;$

for any pair of alternatives $(x_{i},x_{j})$, if $x_{i}$ is preferred to $x_{j}$ in $R^{l}$ but not in $\tilde{C}$; otherwise $x_{i}$ is preferred to $x_{j}$ in $\tilde{C}$ but not in $R^{l}$, we have $w_{ij}^{l}=\frac{\alpha }{d_{RD}(R^{l},\tilde{C})}.$

Therefore, $d_{ARD}(R^{l},\tilde{C})=\alpha = max \left\{ \sum _{i}\sum _{j} \left| a_{ij}^{l} - c_{ij} \right| ,\alpha \right\}$ holds.

For all voters $e_{l}\in E$, $\sum _{l} d_{ARD}(R^{l},\tilde{C}) =\sum _{l} \ max \left\{ \sum _{i=1}^{m}\sum _{j=1}^{m} \left| a_{ij}^{l} - c_{ij} \right| ,\alpha \right\}$ holds.

Thus, Problem 2.2 and Problem 2.4 are equivalent. $\square$

3 Ranking procedure

In this section, we will examine some properties of MAVR and apply a branch and bound ranking algorithm to derive the best solution of the MAVR problem. Note that the optimal consensus ranking may be found out before the algorithm “walks through”all possible rankings. Additionally, we’ll show a simple example and numerical experiments in the next section.

We start by representing some definitions and propositions that are derived from Sect. 2. In all lemmas and the procedures of our algorithm described below the following variables are used:

• $s_{ij}$(aggregated preference): given a set of ranking $\left\{ A^{1},A^{2},\ldots ,A^{n}\right\}$ which comes from ranking decision matrix set $\left\{ R^{1},R^{2},..,R^{n}\right\}$, denote $s_{ij}=\sum _{l}a_{ij}^{l}$ as the aggregated preference between $x_{i}$ and $x_{j}$

• I(prefix ranking): for a ranking $\tilde{C}=\left\{ x_{1}\succ x_{2}\ldots \succ x_{m}\right\}$, if $I=\left\{ x_{1}\succ x_{2}\ldots \succ x_{i}\right\} (i<m)$, I is a prefix ranking of $\tilde{C}$

• $X_{1}$: the set of alternatives in I

• $X_{2}$: the set of left alternatives, represented as I / X

• $E_{1}$: the set of violating voters

• $E_{2}$: the set of no-violating voters

• Absolute(first/last) alternative: given a set of rankings $\{R^{1},R^{2},\ldots ,R^{n}\}$, if $x_{i}\in X=\{x_{1},x_{2},\ldots ,$ $x_{m}\}$ and $\forall e_{l}\in E=\{e_{1},e_{2},\ldots ,e_{n}\}$, $\tilde{a}_{i1}^{l}=1$ or $\tilde{a}_{im}^{l}=1$, $x_{i}$ is the absolutely first or last alternative

Lemma 1

(Separate property) For any given set of rankings, removing the absolutely first or last alternatives initially and add them back finally will not change the optimal ranking.

Because absolutely first or last alternative is easy to identify, we do not need to consider such alternatives exactly.

Given a set of ranking $\{R^{1},R^{2},\ldots ,R^{n}\}$, acceptability index $\alpha$, and I, we divide alternative set X into two parts: $X_{1}$ is the set of alternatives ranked by I, and $X_{2}$ is the set of left alternatives. According to Definition 5, the voter set E can be separated into two sets: set $E_{1}$ includes violating voters, while set $E_{2}$ includes no-violating voters.

Lemma 2

(Lower/Upper bound) A tight lower bound with the prefix ranking I is given by

$$\begin{aligned} \underline{M}(I)=M_{0}+M_{1} \end{aligned}$$

(3.1)

and an upper bound can be represented by

$$\begin{aligned} \overline{M}(I)=M_{0}+M_{2}, \end{aligned}$$

(3.2)

where

$$\begin{aligned} M_{0}(I)= & {} \sum _{e_{l}\in E_{1}}\sum _{i}\sum _{j}w_{ij}^{l} +\left\| E_{2} \right\| *\alpha \ \ \ \ \ \ x_{i},x_{j}\in X; \text { one of } x_{i}, x_{j}\in X_{1}, \\ M_{1}(I)= & {} \sum _{i}\sum _{j} min\left\{ s_{ij},s_{ji}\right\} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_{i},x_{j}\in X_{2},e_{l}\in E_{1},\\ M_{2}(I)= & {} \sum _{i}\sum _{j} max\left\{ s_{ij},s_{ji}\right\} -2*\left( max^{1}\left\{ s_{ij}\right\} +max^{2}\left\{ s_{ij}\right\} \right) \\&+2*\left( min^{1}\left\{ s_{ij}\right\} +min^{2}\left\{ s_{ij}\right\} \right) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_{i},x_{j}\in X_{2},e_{l}\in E, \end{aligned}$$

where $min^{1}\{s_{ij}\}$ and $min^{2}\{s_{ij}\}$ represent the first and second lowest aggregated preference $s_{ij} (x_{i},x_{j}\in X_{2})$, $max^{1}\{s_{ij}\}$ and $max^{2}\{s_{ij}\}$ represent the first and second greatest aggregated preference $s_{ij} (x_{i},x_{j}\in X_{2})$, and $\left\| E_{2} \right\|$ represents the number of voters in $E_{2}$.

Proof

We give a brief illustration about $\underline{M}$ as follows.

If $e_{l} \in E_{1}$, when at least one of $x_{i},x_{j}\in X_{1}$, we have $\sum _{l}\sum _{i}\sum _{j}w_{ij}^{l}$; when $x_{i},x_{j}\in X_{2}$, without loss of generality, we have $\sum _{i}\sum _{j} min\{s_{ij},s_{ji}\} \le \sum _{l}\sum _{i}\sum _{j}w_{ij}^{l}$.

If $e_{l} \in E_{2}$, we assume that all voters in $E_{2}$ are no-violating voters. So we have $\left\| E_{2} \right\| *\alpha \le \sum _{l} max \left\{ \sum _{i=1}^{m}\sum _{j=1}^{m} w_{ij}^{l} ,\alpha \right\} \left( x_{i},x_{j}\in X\right)$.

Hence, $M_{0}+M_{1}$ is a lower bound of the prefix ranking I.

Similarly, We give a brief illustration about $\overline{M}$ as follows.

If at least one of $x_{i},x_{j}\in X_{1}$, for all $e_{l} \in E_{2}$, we have $\left\| E_{2} \right\| *\alpha \ge \sum _{e_{l}\in E_{2}}\sum _{i}\sum _{j}w_{ij}^{l}$; for all $e_{l} \in E_{1}$, we have $\sum _{e_{l}\in E_{1}}\sum _{i}\sum _{j}w_{ij}^{l}$. So we have $\sum _{e_{l}\in E_{1}}\sum _{i}\sum _{j}w_{ij}^{l} + \left\| E_{2} \right\| *\alpha \ge \sum _{e_{l}\in E}\sum _{i}\sum _{j}w_{ij}^{l}$.

If $x_{i},x_{j}\in X_{2}$, without loss of generality, we have $\sum _{i}\sum _{j} max\left\{ s_{ij},s_{ji}\right\} \ge \sum _{l}\sum _{i}\sum _{j}w_{ij}^{l}$. At the same time, relieving the two different pairs of preferences with the highest aggregated violation does not violate the rule of transitivity, they still can be part of some feasible solutions. After further analysis in Appendix 2, we have $\sum _{i}\sum _{j} max\left\{ s_{ij},s_{ji}\right\} -2*\left( max^{1}\left\{ s_{ij}\right\} +max^{2}\left\{ s_{ij}\right\} \right) +2*\left( min^{1}\left\{ s_{ij}\right\} +min^{2}\left\{ s_{ij}\right\} \right) \ge \sum _{l}\sum _{i}\sum _{j}w_{ij}^{l}$.

Hence, $M_{0}+M_{2}$ is an upper bound of the prefix ranking I. $\square$

Lemma 3

(Noninterchangeability property) For an adjacent pair of the prefix order I (say, $x_{i}\succ x_{j}$) and the prefix order $I'$ (say, $x_{j}\succ x_{i}$), if both $s_{ij} < s_{ji}$ and $M_{0}(I) > M_{0}(I')$ hold, I must not be a prefix order of $\tilde{C}^{*}$.

Proof

We will derive a contradiction. We suppose I may be a prefix order of $\tilde{C}^{*}$, it means that $V(\tilde{C}^{I})\leqslant V(\tilde{C}^{I'})$ must exists.

Suppose that I is a prefix order of an acceptance ranking $\tilde{C}^{I}$ and $I'$ is a prefix order of an acceptance ranking $\tilde{C}^{I'}$. $I \subseteq \tilde{C}^{I}$, $I' \subseteq \tilde{C}^{I'}$ and the other part of ranking in $\tilde{C}^{I'}$ are the same with the other part of $\tilde{C}^{I}$. Denote $W^{l}(I)=d_{RD}(R^{l},I)$ and $W(I)=\sum _{l}W^{l}(I)$, where $d_{RD}(R^{l},I)$ has been denoted by Definition 4.

We know that $M_{0}(I) > M_{0}(I')$ and $W^{l}(I')= W^{l}(I)-2$ (or $W^{l}(I')= W^{l}(I)+2$) because the only difference is the prefix order itself. At the same time, the number of voters whose $W^{l}(I')= W^{l}(I)-2$, is not less than the number of voters whose $W^{l}(I')= W^{l}(I)+2$ because of $s_{ji} > s_{ij}$.

For a given $\alpha$, there are three cases below because violation $W^{l}(I)$ is even.

Case 1 $W^{l}(I) \geqslant \alpha +2$.

We know that $V(\tilde{C}^{I}/I) =V(\tilde{C}^{I'}/I')$ because these voters have been listed in $E_{1}$. Due to $M_{0}(I)> M_{0}(I')$, we have $V(\tilde{C}^{I}) > V(\tilde{C}^{I'})$.

Case 2 $W^{l}(I)=\alpha$.

If there is no additional violation, we know that the violations of I and $I'$ will not change, $V(\tilde{C}^{I})= W^{l}(I) > W^{l}(I') = V(\tilde{C}^{I'})$.

If there are some additional violations, when $W^{l}(I')= W^{l}(I)-2$, we have $V(\tilde{C}^{I}/I) =V(\tilde{C}^{I'}/I')+2$; when $W^{l}(I')= W^{l}(I)+2$, we have $V(\tilde{C}^{I}/I) =V(\tilde{C}^{I'}/I')$. As we know, the number of voters whose $W^{l}(I')= W^{l}(I)-2$ is not less than the number of voters, whose $W^{l}(I')= W^{l}(I)+2$, so $V(\tilde{C}^{I}/I) > V(\tilde{C}^{I'}/I')$. Due to $M_{0}(I)> M_{0}(I')$, we have $V(\tilde{C}^{I}) > V(\tilde{C}^{I'})$.

Case 3 $W^{l}(I)\le \alpha -2$.

If there is no additional violation, we know that the violations of I and $I'$ will not change, $V(\tilde{C}^{I})= W^{l}(I) > W^{l}(I') = V(\tilde{C}^{I'})$.

If there are some additional violation, when $W^{l}(I')= W^{l}(I)-2$, we have $V(\tilde{C}^{I}/I) =V(\tilde{C}^{I'}/I')+2$; when $W^{l}(I')= W^{l}(I)+2$, we have $V(\tilde{C}^{I}/I) =V(\tilde{C}^{I'}/I')+2$. As we know, the number of voters whose $W^{l}(I')= W^{l}(I)-2$ is not less than the number of voters, whose $W^{l}(I')= W^{l}(I)+2$, so $V(\tilde{C}^{I}/I) > V(\tilde{C}^{I'}/I')$. Due to $M_{0}(I)> M_{0}(I')$, we have $V(\tilde{C}^{I}) > V(\tilde{C}^{I'})$.

Summing up all voters’ violation, we have $V(\tilde{C}^{I}) > V(\tilde{C}^{I'})$. It contradicts with the assumption.

Thus, order I will not be a prefix order of $\tilde{C}^{*}$, this proves the lemma. $\square$

In the algorithm below, we start with an empty ranking. Then adding each alternative to the first node one by one, and calculate the lower bound and upper bound for later, and then cut off some branches based on branching principle or Noninterchangeability Property. Note that we start from the branches with the lowest bound and check all other branches’ upper bound when we add a new alternative.

We represent an algorithm to generate MAVR as follows.

Algorithm—Branch and bound ranking algorithm

Input: Set of alternatives $X=\{x_{1},x_{2},\ldots ,x_{m}\}$ and the voters’ ranking decision matrix $\{R^{1},R^{2},\ldots ,R^{n}\}$. $\underline{M}(I):= 0$ and $\overline{M}(I) := 0$.

• 1. Initialization: Initialize the search tree by creating the root node with the prefix ranking set $I=\phi$ $(j=0)$. Calculate its lower bound $\underline{M}(I)$ and upper bound $\overline{M}(I)$, and store them as the branch and bound tree root node. If $\underline{M}(I) = \overline{M}(I)$, then stop with the optimal solution; Otherwise, define this node as an active node and go to Step 2.

• 2. Branching Selecting a node: Selecting the node with the lowest $\underline{M}(I)$ from the set of active nodes of the search tree. Branching new nodes: Construct node $\tilde{c}_{ij}=1 (i\in X_{2},j=j+1)$ to selected node I . I includes the alternatives which have been ranked already. Add these $c_{ij}$ to I as active nodes to the search tree and store $\underline{M}(I)$ and $\overline{M}(I)$. If $\underline{M}(I) = \overline{M}(I)$, then stop with the optimal solution; Otherwise, increment j by one and go to 3.

• 3. Bounding Bounding (lower bound and upper bound): Calculate these new nodes’ $\underline{M}(I)$ and $\overline{M}(I)$. Check whether one of $\underline{M}(I)$ is greater than currently best known minimum $\overline{M}(I)$. If so, cut off this branch. If not, then proceed to the bounding of noninterchangeability property. Bounding (noninterchangeability property): Use this property to check whether some branches have both smaller $s_{ij}$ and larger $M_{0}$ than its pair branch. If so, cut off this branch. If not, then proceed to 2.

• 4. Termination: If there are still some active nodes or the number of the left alternatives is greater than 2, return to Step 2; otherwise, select the smaller $s_{ij}$ of the left two alternatives, and add this order ranking behind the termination ranking.

4 An example and computational tests

4.1 A numerical example

We consider an example with the acceptability index $\alpha =4, n=10$ voters, and $m=4$ alternatives. The Table 1 presentes the voter’s rankings:

Table 1 A group decision making example

The $s_{ij}$ below presentes the summarized pairwise preference:

Initialization: $I=\phi$. Calculate $M_{0}=4*10=40$, $M_{1}=0$, and $M_{2}=2*(0+2+7+7+7+7)=60$. We obtain a lower bound $\underline{M}=M_{0}+M_{1}=40$, and an upper bound $\overline{M}=M_{0}+M_{2}=40+60=100$.

Branching: We process the root node with the empty ranking one by one as shown in Fig. 2, we check them all:

Fig. 2

First iteration

• Adding alternative 1 Let $\tilde{c}_{11}=1$, we have $I=\{ 1 \}$. Calculate $M_{0}=4*6+3*6+2*\alpha =52$, $M_{1}=2*(1+1+3)=10$, and $M_{2}=2*(3+3+7)=26$. We obtain a lower bound $\underline{M}=62$, and an upper bound $\overline{M}=78$.

• Adding alternative 2 Let $\tilde{c}_{21}=1$, we have $I=\{ 2 \}$. Calculate $M_{0}=40$, $M_{1}=6$, and $M_{2}=24$. We obtain a lower bound $\underline{M}=46$, and an upper bound $\overline{M}=64$.

• Adding alternative 3 Let $\tilde{c}_{31}=1$, we have $I=\{ 3 \}$. Calculate $M_{0}=40$, $M_{1}=0$, and $M_{2}=20$. We obtain a lower bound $\underline{M}=40$, and an upper bound $\overline{M}=60$.

• Adding alternative 4 Let $\tilde{c}_{41}=1$, we have $I=\{ 4 \}$. Calculate $M_{0}=46$, $M_{1}=2$, and $M_{2}=16$. We obtain a lower bound $\underline{M}=48$, and an upper bound $\overline{M}=62$. We could not bound any point because $max \{ \underline{M} \} < min \{ \overline{M} \}$.

Fig. 3

Second iteration

Branching: Ranking all the nodes by their $\underline{M}$, we process the root node one by one again as shown in Fig. 3. We check them all:

• Adding alternative 2 to $I=\{ 3 \}$, for now we have $I=\{3,2\}$: Calculate $M_{0}=4*\alpha +3*\alpha +2*4+1*\alpha =40$, $M_{1}=0$, and $M_{2}=2*3=6$. We obtain a lower bound $\underline{M}=40$, and an upper bound $\overline{M}=46$.

• Adding alternative 4 to $I=\{ 3 \}$, for now we have $I=\{3,4\}$: We obtain a lower bound $\underline{M}=50$. We do not need to calculate its upper bound and add it to the branch and bound tree because the lower bound is greater than present $min \{ \overline{M}\}=46$.

• Adding alternative 1 to $I=\{ 3 \}$, for now we have $I=\{3,1\}$: We obtain a lower bound $\underline{M}=52$. We do not need to calculate upper bound and add it to the branch and bound tree because the lower bound is greater than present $min \{ \overline{M}\}=46$.

Bounding (lower bound and upper bound): For $\underline{M}\left( I=\left\{ 1\right\} \right) =62$, $\underline{M}(I=\{2\})=46$, and $\underline{M}\left( I=\left\{ 4\right\} \right) =48$ is not less than $\overline{M}\left( I=\left\{ 3,2\right\} \right) =46$, we cut off these branches from the branch and bound tree.

Bounding (Noninterchangeability property): For $s_{41}=7 > s_{14}=3$ and $M_{0}\left( I=\left\{ 3,2,4,1\right\} \right) = 44<M_{0}\left( I=\left\{ 3,2,1,4\right\} \right) =46$, we cut off $I=\{3,2,1,4\}$.

Hence, we know that the MAVR is $3\succ 2 \succ 4 \succ 1$.

4.2 Numerical experiments

We implement some computational tests to evaluate the branch and bound ranking algorithm. Our testing platform is a AMD Athlon(tm) II X4 640 Processor 3.00 GHz with 4.00 GB that run under Windows 7. We coded the algorithm in Matlab and compiled it with Matlab 7.11.0. We construct six classes, each with 25 test instances, and different number of alternatives or voters as shown in Table 2. For each of the 150 instances in Table 2, we created 3 different sets of voters decision matrixes which have different normally distributed noise $N(0,\sigma ^{2})$, with $\sigma ^{2}=1,4$ or 9. In Table 3 we represent the average and worst case running time (in seconds) for each of the six classes and three levels of noises.

Table 2 Six classes of the test problems

It’s apparent in Table 3 that we are able to obtain the optimal ranking of each instance within 5 seconds. Although the number of alternatives is not high $(m \le 5)$, it matches with most of practical scenarios.

Additionally, we have three conclusions. Firstly, the fact that every class with different level of noise take a similar amount of time to process implies that our algorithm is insensitive to the level of noise. Secondly, as the size of alternatives increases (Class C, D and E), the processing time increases quickly because the pairwise preference comparisions increase with factorial growth. Thirdly, Classes A, B, and C take a similar amount of processing time, which implies that our algorithm is insensitive to the amount number of voters. Our method does have a good performance.

Table 3 Running time (s) and percentage of the problems solved

5 Minimum weighted/hierarchy acceptable violation

There are two useful extended problems of the MAVR problem, the Minimum Weighted Acceptable Violation (MWAVR) problem and the Minimum Hierarchy Acceptable Violation (MHAVR) problem.

5.1 Minimum weighted acceptable violation problem

Considering the voting system, numerical researchers studied from a more generalized aspect, weighted voting method (Lucas 1983; Isaak and Narayan 2004; Bustince et al. 2013). In some group decision making processes, the voters are treated differently according to their education, wealth, ect. For example, the members of the board in a company have weighted voting rights, which is based on their right of control, and these weights may differ across voters. Thus, we should not aggregates every voter’s ranking together equally. We will discuss the MWAVR problem and solve it then.

Without loss of generality, we denote $W=(w^{1},\ldots ,w^{n})^{T}$ as the voter’s weight vector, where $w^{l}\ge 0$ and $\Sigma _{l=1}^{n} w^{l}=1$, from the judgement matrix $A^{l}$.

The MWAVR problem can be represented as:

$$\begin{aligned} V(C)= \sum _{l=1}^{n} w^{l} \times d_{APD}(A^{l},C) =\sum _{l=1}^{n}\sum _{i=1}^{m}\sum _{j=1}^{m} w^{l} \times \left| b_{ij}^{l}-c_{ij} \right| \end{aligned}$$

s.t.

$$\begin{aligned} \sum _{i}^{m}\sum _{j}^{m} \left| a_{ij}^{l} - b_{ij}^{l} \right| \le \alpha \ \ \ \ l= & {} 1,\ldots ,n, \\ c_{ij} \ \ \text {satisfies transitivity property} \ \ \ i= & {} 1,\ldots ,m, j=1,\ldots ,m . \end{aligned}$$

For solving this problem, we could multiple the weight vector to be an integer vector without altering the problem, and then consider the MWAVR problem as a new MAVR problem with more voters, simply.

For example, there are 5 voters involved in an election, and the voter’s weight vector is (0.25, 0.2, 0.2, 0.15, 0.2) . The initial MWAVR problem can be represented as a MAVR problem as shown in Table 4. Thus, the new MAVR problem owns 20 voters, and we can solve it by using the branch and bound ranking algorithm.

Table 4 The initial MWAVR problem $\Rightarrow$ the MAVR problem

According to the computational tests in the previous section, as the voters increased exponentially, the running time increased slowly. What’s more, when voters increased, the ranking types do not increase in MWAVR problem. We can predict that the running time do not increase dramatically. Thus, the branch and bound ranking algorithm in the Sect. 3, will be able to solve the MWAVR problem, too.

5.2 Minimum hierarchy acceptable violation

It is easy for us to know that people have various violation acceptability. Some voters do not care about the violations in group decision making, and some voters could not tolerate any violations. According to each voter’s tolerance, the voters will be classified into different acceptability index hierarchies. For example, there are 50 voters involved in an election, and the acceptability index hierarchy is $\left\{ 8, 8 \ldots ; 4, 4 \ldots ; 2,2 \ldots \right\}$. The voters will be divided into two parts by Definition 5, as shown in Fig. 4, called violating voter, whose PKS distance is not less than its own acceptability index (above /on the red line), and no-violating voter, whose PKS distance is less than its own acceptability index (below the red line).

Fig. 4

A 50-voter election (with a hierarchy acceptability index)

When we try to minimize the unacceptable violations (or total PKS distance above/ on the red line) for obtaing the optimal ranking, we should introduce the difference of voter’s acceptability into this problem. Thus, $\alpha$ should no longer be assumed to be a fixed integer simply. We will discuss the MHAVR problem and solve it then.

Without loss of generality, we denote $\alpha =\left( \alpha ^{1},\ldots ,\alpha ^{n}\right) ^{T}$ as the voter’s acceptability index vector. Actually, suppose there are m alternatives, the $\alpha$ owns at most $m*(m-1)/2$ different forms in this problem. At the same time, $\alpha ^{l}$ is even, and $\alpha ^{l} \in \left[ 2,m*\left( m-1\right) \right]$.

The MHAVR problem can be represented as:

$$\begin{aligned} V(C)=\sum _{l=1}^{n} d_{APD}(A^{l},C) =\sum _{l=1}^{n}\sum _{i=1}^{m}\sum _{j=1}^{m} \left| b_{ij}^{l}-c_{ij} \right| \end{aligned}$$

s.t.

$$\begin{aligned} \sum _{i}^{m}\sum _{j}^{m} \left| a_{ij}^{l} - b_{ij}^{l} \right| \le \alpha ^{l} \ \ \ \ l= & {} 1,\ldots ,n, \\ c_{ij} \ \ \text {satisfies transitivity property} \ \ \ i= & {} 1,\ldots ,m, j=1,\ldots ,m . \end{aligned}$$

We still use the branch and bound ranking algorithm to solve this problem, however, the voters are divided into two parts (violating voter and no-violating voter) according to their own acceptability index $\alpha ^{l}$ in each iteration. The lower bound and the upper bound are still strict. Thus, the branch and bound ranking algorithm is useful to solve the MHAVR problem, too. The only difference between the MHAVR problem and the MAVR problem is that the voters in the MAVR problem have the same acceptability index $\alpha$.

6 Summary and future research directions

This paper has examined the issue of aggregating ordinal voter rankings across a set of alternatives into an acceptable consensus ranking. We considered that voters are more willing to accept the final ranking MAVR than the initial MVR because, on one hand, most of the voters’ violations will not exceed the acceptability index, and on the other hand, the total unacceptable violation is minimized. To simplify the MAVR problem, we came up with two transformations. Firstly, we removed the adjusted preference matrixes $\left\{ B^{1}, B^{1},\ldots , B^{m}\right\}$ from the model. Secondly, we using ranking distance instead of PKS distance to represent the model so that the elements of the final ranking decision matrix do not need to be transitive. Based on Problem 2.4 and the noninterchangeability property, we represented a branch and bound ranking algorithm. The approach undertaken in this research serves as an exact algorithm for this problem. The results of the numerical experiments, the processing time and precentage of the problems solved, clearly show the superiority of algorithm. Additionally, we proposed two extension problems, the MWAVR problem and the MHAVR problem, and give some brief illustrations of their solutions. We believe that this paper could help users to attain an “acceptable consensus ranking”in practical group decision making with a clear procedure.

The study of ordinal rankings and adjusted consensus touch on a variety of field. In terms of this paper, we assumed that the preferences of each voter is complete, in reality, however, the situation in which each voter choose a subset of alternatives from a ballot, and to rank order that subset from most to least preference, is relatively common in municipal elections. The MAVR problem with partial preferences is left to be explored in the future. Besides, research into the handling of multiple types of preferences, like ranking, scores, and etc., in this MAVR performance measurement setting, can be an important contribution to group decision making.

Appendices

Appendix 1: The proof of equivalency of the two linear models

To prove the equivalency, we just need to prove that the two models have the same feasible solution set and the feasible solutions of these two models are the same.

The first linear model is given by

$$\begin{aligned} \min V(C)=\sum _{l=1}^{n} d_{APD}(B^{l},C) =\sum _{l=1}^{n}\sum _{i=1}^{m}\sum _{j=1}^{m} \left| b_{ij}^{l}-c_{ij} \right| \end{aligned}$$

s.t.

$$\begin{aligned} \sum _{i}^{m}\sum _{j}^{m} \left| a_{ij}^{l} - b_{ij}^{l} \right| \le \alpha \ \ \ \ l= & {} 1,\ldots ,n, \\ c_{ij} \ \text {satisfies transitivity property} \ \ \ i= & {} 1,\ldots ,m, j=1,\ldots ,m . \end{aligned}$$

The second linear model can be represented as below.

$$\begin{aligned} \min V_{0}(C) =\sum _{l=1}^{n} d_{APD}(A^{l},B^{l}) =\sum _{l=1}^{n}\sum _{i=1}^{m}\sum _{j=1}^{m} \left| b_{ij}^{l}-a_{ij}^{l} \right| \end{aligned}$$

s.t.

$$\begin{aligned} \sum _{i}^{m}\sum _{j}^{m} \left| c_{ij} - b_{ij}^{l} \right| \le \alpha \ \ \ \ l= & {} 1,\ldots ,n, \\ c_{ij} \ \text {satisfies transitivity property} \ \ \ i= & {} 1,\ldots ,m, j=1,\ldots ,m . \end{aligned}$$

where $A^{l}=(a_{ij}^{l})$ is the initial preference matrix of voter $e_{l}, B^{l}=(b_{ij}^{l})$ is the adjusted preference matrix of voter $e_{l}$ after $k^{l}$ adjustments $( k^{l}\leqslant \alpha ), C=(c_{ij} )$ is a consensus preference decision matrix.

It is obvious to know that the feasible solutions are the set of all possible rankings, so the feasible solutions of these two models are the same. For example, there are 3 alternatives(or candidates) a, b and c in an election, the feasible solution set can be represented as: $\{a, b, c\}, \{a, c, b\}, \{b, a, c\}, \{b, c, a\}, \{c, a, b\}, \{c, b, a\}$.

For a given preference decision matrix C (a feasible solution), we will know the distance between each voter $A^{l}$ and C .

In the first model, because $d(A^{l},C)= d(A^{l},B^{l})+d(A^{l},C)$, to minimizing the distance between adjusted preference matrix $B^{l}$ and C , each voter should adjuste their preference as more as possible (at most $\alpha$), nearing to C . If the distance between adjusted preference matrix $A^{l}$ and C is greater than $\alpha$, $d_{APD}(A^{l},B^{l}) = \alpha$, then $d_{APD}(B^{l},C) = d_{APD}(A^{l},C) - \alpha$. If the distance between adjusted preference matrix $A^{l}$ and C is not greater than $\alpha$, $d_{APD}(A^{l},B^{l}) = d_{APD}(A^{l},C)$, then $d_{APD}(B^{l},C) = 0$.

In the second model, because $d(A^{l},C)= d(A^{l},B^{l})+d(A^{l},C)$, to minimizing the adjusted distance between adjusted preference matrix $B^{l}$ and $A^{l}$, the distance between $B^{l}$ and C is as great as it could be (at most $\alpha$). If the distance between adjusted preference matrix $A^{l}$ and C is greater than $\alpha$, $d_{APD}(B^{l},C) = \alpha$, then $d_{APD}(A^{l},B^{l}) = d_{APD}(A^{l},C) - \alpha$. If the distance between adjusted preference matrix $A^{l}$ and C is not greater than $\alpha$, $d_{APD}(B^{l},C) = d_{APD}(A^{l},C)$, then $d_{APD}(A^{l},B^{l}) = 0$.

Eventually, we choose the minimum distance among all feasible solutions C as the final decision. Because the objectives of these two linear models are same for every feasible solution, so the final decisions of these two models are the same.

From the above we can draw a conclusion that these two two linear models are equivalent.

Appendix 2: The supplemental proof of the upper bound

Because the objective is to minimize the violations, any one of the feasible solutions is no less than the final solution. To prove the upper bound, we just need to prove that the upper bound we represents, is a feasible solution.

If $x_{i},x_{j}\in X_{2}$: The worst case is that we choose all the pairs with a higher aggregated violation $max\left\{ s_{ij},s_{ji}\right\}$ between $\left( x_{i}\prec x_{j}\right)$ and $\left( x_{j}\succ x_{i}\right)$. We have $\sum _{i}\sum _{j} max\left\{ s_{ij},s_{ji}\right\} \ge \sum _{l}\sum _{i}\sum _{j}w_{ij}^{l}$.

Fixing (or choosing) two different pairs of preferences with the highest aggregated violation does not violate the rule of transitivity, they still can be part of some feasible solutions, because the rule of transitivity only exists in more than or equal to three different pairs. For example, $\left\{ a\succ b, b\succ c\right\}$ is not contradict with the transitivity property, however, $\left\{ a\succ b, b\succ c, c\succ a \right\}$ is contradict with the rule of transitivity.

Among these alternatives which we have not yet assigned to the prefix order ($x_{i},x_{j}\in X_{2}$), we choose two different pairs of preferences with the highest aggregated violation as part of solution. For these two pairs , the violation is $2*\left( min^{1}\left\{ s_{ij}\right\} +min^{2}\left\{ s_{ij}\right\} \right)$. For the other pairs, the violation is $\sum _{i}\sum _{j} max\left\{ s_{ij},s_{ji}\right\} -2*\left( max^{1}\left\{ s_{ij}\right\} +max^{2}\left\{ s_{ij}\right\} \right)$. Because the objective is to minimize the violations, any one of the feasible solutions is no less than the final solution. We have $\sum _{i}\sum _{j} max\left\{ s_{ij},s_{ji}\right\} -2*\left( max^{1}\left\{ s_{ij}\right\} +max^{2}\left\{ s_{ij}\right\} \right) +2*\left( min^{1}\left\{ s_{ij}\right\} +min^{2}\left\{ s_{ij}\right\} \right) \ge \sum _{l}\sum _{i}\sum _{j}w_{ij}^{l}$.

From the above and the previous proof in Lemma 2 we can draw a conclusion that $M_{0}+M_{2}$ is an upper bound.