# Consensus theories: an oriented survey

Olivier Hudry, Bernard Monjardet

► To cite this version:

Olivier Hudry, Bernard Monjardet. Consensus theories: an oriented survey. 2010. halshs-00504974

HAL Id: halshs-00504974

https://shs.hal.science/halshs-00504974

Submitted on 22 Jul 2010

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

Consensus theories : An oriented survey

Olivier HUDRY, Bernard MONJARDET

2010.57

<figure><img src="image_4.png" /></figure>
CONSENSUS THEORIES. AN ORIENTED SURVEY

Olivier HUDRY<fnref n="1" />, Bernard MONJARDET<fnref n="2" />

Théories du consensus. Une synthèse orientée

RÉSUMÉ – Cet article présente une vue d'ensemble de sept directions de recherche en théorie du consensus : résultats arrowiens, règles d'agrégation définies au moyen de fédérations, règles définies au moyen de distances, solutions de tournoi, domaines restreints, théories abstraites du consensus, questions de complexité et d'algorithmique. Ce panorama est orienté dans la mesure où il présente principalement – mais non exclusivement – les travaux les plus significatifs obtenus – quelquefois avec d'autres chercheurs – par une équipe de chercheurs français qui sont – ou ont été – membres pléniers ou associés du Centre d'analyse et de mathématique sociale (CAMS).

MOTS-CLÉS – théories du consensus, résultats arrowiens, règles d'agrégation, distances, médiane, solutions de tournoi, domaines restreints, valuations inférieures, demi-treillis à médianes, complexité.

SUMMARY – This article surveys seven directions of consensus theories: Arrowian results, federation consensus rules, metric consensus rules, tournament solutions, restricted domains, abstract consensus theories, algorithmic and complexity issues. This survey is oriented in the sense that it is mainly – but not exclusively – concentrated on the most significant results obtained, sometimes with other searchers, by a team of French searchers who are or were full or associate members of the *Centre d'analyse et de mathématique sociale* (CAMS).

KEYWORDS – consensus theories, Arrowian results, aggregation rules, metric consensus rules, median, tournament solutions, restricted domains, lower valuations, median semilattice, complexity.

I. INTRODUCTION

Let us specify the contents of this paper. By *consensus theory*, we mean any theory dealing with a problem where several “objects” must be merged into one (or several) “consensus object(s)” of the same or of similar nature that in some sense represent(s) them at best. This

<footnote n="1">¹ Télécom ParisTech, 46, rue Barrault, 75634 Paris Cedex 13, hudry@enst.fr. O. Hudry's research was supported by the ANR project "Computational Social Choice" n° ANR-09-BLAN-0305-03.</footnote>

<footnote n="2">² Centre d'Économie de la Sorbonne, Université Paris I Panthéon Sorbonne, Maison des Sciences Économiques, 106-112, boulevard de l'Hôpital, 75647 Paris Cedex 13, and CAMS, EHESS, Bernard.Monjardet@univ-paris1.fr</footnote>
type of problem appears first with the problem of means in statistics. Here the objects are
numbers (the elements of a statistical series) and the aim is to find a number summarizing this
series as well as possible (classical answers are the arithmetical mean, the median or the
mode). In social choice theory and multiple criteria decision aid, the objects can be
preferences expressed by voters or through criteria. These preferences can be modelled by
– crisp or fuzzy – binary relations like – crisp or fuzzy – orders (of various kinds); they can
also be represented by utility functions. One can also consider the case where voters’
preferences are expressed via choice functions. In cluster analysis, the objects to aggregate
can be classifications, like partitions (or, equivalently, equivalence relations) or hierarchies
(also called *n*-trees). They can also be functions like ultrametrics. In biomathematics, the
objects can be unrooted trees or molecular sequences. In computer science, they can be
rankings given by Web search engines. Merging symbolic objects is a topic of artificial
intelligence. There is a large amount of practices and literature in sport to aggregate the scores
given by judges (or obtained on several criteria) on the performances of the athletes. Finally,
the recently largely developed topic of “judgment aggregation” appears at least as soon as
1785 with Condorcet’s *Essai sur l’application de l’analyse à la probabilité des décisions
rendues à la pluralité des voix* [1785].

This survey deals with seven main directions in consensus theories that will be
examined in the following sections.

1. *Arrowian results.* Arrow’s theorem [1951] shows that imposing some a priori desirable
properties to an aggregation function may lead to a very unsatisfactory rule, namely a
“dictatorship”, in which the consensus object is the object provided by the “dictator”<fnref n="3" />. In fact,
if we add, as a condition for the rule, that it must not be dictatorial or – more generally –
“oligarchic”, one often gets impossibility results. Since then, many other impossibility results
have been obtained from this “axiomatic” approach.

2. *Federation consensus rules.* These rules are the generalization of the classical majority rule
promoted by Condorcet. In the majority rule applied to the preferences of voters, an
alternative *x* is collectively preferred to another alternative *y* if a majority of voters prefers *x*
to *y*. Now, this rule is extended by replacing the family of usual majorities by a family (called
federation) of generalized majorities. For instance, we can take the family of all the subsets of
voters with a size greater than or equal to a given integer *q*, obtaining thus the so-called quota
rules. But like the majority rule, these federation rules can lead to unsatisfactory consensus
objects. Recall that the majority rule applied to preferences can lead to an “effet Condorcet”
(see Example 1 in Section V), i.e. to cycles *a* > *b* > *c* > *a* in the collective preference, where
*x* > *y* means that *x* is preferred to *y* by a majority (here, the relation > is not assumed to be
transitive).

3. *Metric consensus rules.* If one reckons that a consensus rule does not need to satisfy all Arrow’s axioms and especially the independence axiom, many rules are available and in particular the metric rules. To define such a rule, the set of objects is made a metric space by introducing a notion of distance between (any) two objects. Then, based on this distance, we define a remoteness function between an *n*-tuple of these objects and any object. The consensus objects of an *n*-tuple are those minimizing this remoteness. Section IV develops particularly the most known metric rule, namely the so-called median procedure.

4. *Tournament solutions.* A tournament is a binary relation *T* such that, for any distinct elements *x* and *y*, we have one and only one of the following two possibilities: *x* is preferred to *y* according to *T* (*xTy*) or *y* is preferred to *x* according to *T* (*yTx*). A transitive tournament is

<footnote n="3">³ In fact, such a dictator is called an absolute dictator and it is obtained when the preferences are linear orders. In Arrow’s theorem on complete preorders, the dictator imposes only his strict preference (and not his indifference) between two alternatives.</footnote>
a (strict) linear order and conversely. Such a structure can be used to summarize the result of a pairwise comparison method when there is no tie. Such a tournament may be transitive; it is then a linear order and it is natural to consider that the first element of the linear order is the winner of the pairwise comparison method. It is more difficult and thus more disputable to determine a winner when the tournament is not transitive. The aim of tournament solutions is to determine a winner from a tournament, sometimes to rank all the elements to which the pairwise comparison method is applied.

5. *Restricted domains.* Another classical way to escape impossibility Arrowian theorems is to restrict the domain of objects to aggregate. In particular, there is a big amount of literature on this topic in social choice theory and we will present results related to the case where preferences are modelled by linear orders.

6. *Abstract consensus theories.* It was observed that very similar consensus results appear in different fields. For instance, there are “oligarchic” results in the aggregation of orders, choice functions or partitions. This fostered the researchers to find aggregation results on more “abstract” objects in order to generalize and unify those obtained in particular domains.

7. *Complexity issues.* From a practical point of view, the algorithmic complexity of a method plays an essential role; for instance for an election, it is quite important to be able to declare who is the winner in a “reasonable” time. In this respect, polynomial methods are usually preferable to exponential methods. Indeed for an exponential method the CPU time may quickly become prohibitive if we want to compute an exact solution. Now when a problem is NP-hard (or NP-complete if we deal with a decision problem, i.e. a problem in which a question is set with “yes” or “no” as its answer), the only methods known nowadays to solve the problem exactly are exponential. It is thus quite important to know whether the considered problem is polynomial or NP-hard.

On the other hand, this survey is oriented since we will mainly – but not exclusively – survey the most significant contributions of a team of researchers<fnref n="4" /> who are or were full or associate members of the “Centre d’analyse et de mathématique sociale” (CAMS) at the “École des hautes études en sciences sociales” (EHESS)<fnref n="5" />. These contributions are contained in some of the about one hundred papers written by them (often in cooperation with other – French or not – searchers) on consensus problems<fnref n="6" />. These papers were published from 1952 and the first ones were generally written in French, which can explain that they remained rather unknown<fnref n="7" />. Moreover, since this paper will be published in a special issue of *Mathématiques et Sciences humaines* in Bruno Leclerc’s honour, we will particularly develop his contributions. A much more exhaustive survey on a large part of the literature on consensus theories up to 2003 can be found in Day and McMorris’s excellent book *Axiomatic Consensus Theory in Group Choice and Biomathematics* [2003]. An older survey for the consensus of classifications is [Leclerc, 1998]. A recent survey on the main aspects of the

<footnote n="4">⁴ Barbut, Barbut-Le Conte de Poly, Barthélemy, Bermond, Chameni-Nembua, Domenach, Guilbaud, Feldman-Högaasen, Hudry, Leclerc, Monjardet, Raderanirina, Rosenstiehl.</footnote>

<footnote n="5">⁵ Obviously, this survey is still less a survey on the contributions of French searchers on consensus theories. Since Borda and Condorcet, there are many of them: without attempting to be exhaustive, let us mention Caen’s team in social choice theory around Maurice Salles (Lepelley, Mbih, Merlin, Vidu...) and people like Bloch, Bordes, Bouyssou, Demange, Dubois, Grabisch, Kolm, Laslier, Laffond, Lainé, Lang, Lebreton, Mongin, Moulin, Perny, Prade, Roy, Tallon, Trannoy... For details on the CAMS, see [Monjardet, 2005].</footnote>

<footnote n="6">⁶ The list of these papers up to 2003 can be found in [Monjardet 2005].</footnote>

<footnote n="7">⁷ It is stranger for some other papers written in English, published in reputed international journals and containing significant results.</footnote>
median procedure is [Hudry, Leclerc, Monjardet and Barthélemy, 2009], whereas related
surveys on the linear ordering problem are [Charon and Hudry, 2007a and 2010]. Finally, a
survey on the complexity of voting procedures is [Hudry, 2009a].

Remark. Unless stated otherwise, all the mathematical objects considered in this paper are
finite.

## II. ARROWIAN RESULTS

The “axiomatic” approach initiated by Arrow for *complete preorders*<fnref n="8" /> was used for
many other objects. As soon as 1952, Guilbaud [1952] uses it for judgment aggregation (see
Section VII). Brown [1975] uses it for orders and Mirkin [1975] for partitions. Barthélemy
[1982] uses it when the domain and the codomain of the aggregation function are sets of
orders. He assumes that the domain is sufficiently large, in the sense that, for any triple of
alternatives, it contains all the possible orders (except maybe the trivial one). Then he shows
that when this domain is included in the codomain, the only aggregation functions satisfying
the independence condition<fnref n="9" /> and the weak Pareto principle<fnref n="10" /> are the *absolute dictatorships* or
the *absolute oligarchies*<fnref n="11" />.

We said above that the preferences of an individual can also be expressed by a choice
function. The aggregation of choice functions was first studied by the Russian school
(Aizerman, Aleskerov, Malishevsky...; see for instance [Aleskerov, 1999]). Monjardet and
Raderanirina [2004] study the latticial structure of some significant classes of choice
functions. Then, using the latticial approach presented below in Section VII, they obtain
axiomatic results on the aggregation of choice functions in these classes.

In cluster analysis, Mirkin [1975] was the first to use the axiomatic method for the
case of partitions and to obtain an oligarchic result. His result was improved by Leclerc
[1984] as a by-product of his significant theorem on the consensus of valued preorders. A
*valued preorder* (or *valued quasi-order*) on a set X is a map p: X² → R⁺ satisfying, for all
(x, y, z) ∈ X³, p(x, z) ≤ max(p(x, y), p(y, z)) and, for every x ∈ X, p(x, x) = 0. So, the valued
preorders are – under duality – identical to the *fuzzy preorders* satisfying maxmin transitivity
[Zadeh, 1971]. On the other hand, a symmetric valued preorder, i.e. satisfying p(x, y) = p(y,
x), is an *ultrametric distance*<fnref n="12" />. The set V of all valued preorders is ordered by the pointwise
order on functions and closed with respect to the usual join operation:

<footnote n="8">⁸ A complete preorder R (called ordering by Arrow and also called weak order, weak ordering, complete pre-ordering, complete quasi-ordering, linear preorder, ranking, etc.) is a complete (we must have xRy or yRx) and transitive (xRy and yRz imply xRz) binary relation. An antisymmetric (xRy and yRx imply x = y) complete preorder is a linear order. An order is a reflexive (xRx), antisymmetric and transitive binary relation; so, an order is a linear order if and only if it is complete.</footnote>

<footnote n="9">⁹ The *independence condition* says that if the preferences restricted to two alternatives of two profiles are the same, then the collective preference for these profiles on these alternatives must be the same. This condition (with some variants) can be stated for any consensus function.</footnote>

<footnote n="10">¹⁰ The weak Pareto principle says that the aggregation function must preserve the unanimous preferences of the voters.</footnote>

<footnote n="11">¹¹ In an *absolute oligarchic rule*, the consensus object is completely determined only by some voters. For instance, when the objects are orders, the consensus object is the intersection of the orders given by these voters (i.e. their unanimous preferences).</footnote>

<footnote n="12">¹² Ultrametrics are significant in cluster analysis since they induce a chain of nested (and indexed) partitions.</footnote>
$p \nvDash p'(x, y) = \max(p(x, y), p'(x, y))$. Leclerc defines two "Arrow-like" axioms for the aggregation of valued preorders. Let $F$ be a map $\mathcal{V}^n \to \mathcal{V}$ and let $p$ (respectively, $p'$) denote the image $F(\Pi)$ (respectively, $F(\Pi')$) of a profile $\Pi = (p_1, \dots, p_n)$ (respectively, $\Pi'$) of valued preorders; these axioms are:

*Efficiency*: for every profile $\Pi \in \mathcal{V}^n$ and all $(x, y) \in X^2$,
$$ \max p(x, y) \le \max_{i \in \{1, 2, \dots, n\}} p_i(x, y). $$

*Binariness*: for all the profiles $(\Pi, \Pi') \in (\mathcal{V}^n)^2$ and $(x, y) \in X^2$,
$$ p_i(x, y) = p_i'(x, y) \text{ for } i \in \{1, 2, \dots, n\} \text{ implies } p(x, y) = p'(x, y). $$

We may observe that these axioms are generalizations of classical Paretian and independence axioms. Then, Leclerc obtains the following result (where $\circ$ is the composition operation of two maps):

**THEOREM 1.**

A consensus function $F: \mathcal{V}^n \to \mathcal{V}$ satisfies the efficiency and binariness properties if and only if there exist $n$ reductive and isotone$^{13}$ maps $f_1, \dots, f_n$ from $\mathbf{R}^+$ into itself such that $F(\Pi) = (f_1 \circ p_1) \lor (f_2 \circ p_2) \lor \dots \lor (f_n \circ p_n)$.

Replacing $\mathbf{R}^+$ by the set $\{0, 1\}$ ordered by $<$, Leclerc shows that the following results are particular cases of Theorem 1: Mas-Collel and Sonnenschein's result [1972] on complete preorders$^{14}$, Brown's result [1975] on orders, Mirkin's result [1981] on preorders. Moreover he obtains a form of Arrow's 1951 theorem. Other particular cases deal with cluster analysis where Leclerc obtains – as already noticed – an improvement of Mirkin's 1975 theorem on partitions$^{15}$ and a result on the consensus of ultrametrics. On the other hand, the above result is considerably extended in [Leclerc, 1991]. Here, valued preorders are replaced by much more general *valued objects*$^{16}$ defined by maps from a lattice of *objects* into a lattice of *values*. The set of these valued objects is itself a lattice (isomorphic to a lattice of Galois maps$^{17}$) and so, one can apply, and above all particularize to this case, the results of the latticeial consensus theory described in Section VII. Then, consensus functions called *extensively oligarchic* (dual generalizations of the above map $F$) are characterized.

For the case of *hierarchies*$^{18}$ in cluster analysis, variants of Arrow's independence axiom lead to characterizations of dictatorship and absolute dictatorships consensus rules [Barthélemy and McMorris, 1989], [Barthélemy, McMorris and Powers, 1991, 1992].

The above Arrowian results are often “negative” since, by adding as a condition for the rule that it must not have a dictatorial or oligarchic form, we often obtain impossibility results. The Arrowian approach leads to more positive results when it comes to axiomatic characterizations of interesting consensus rules, a line of research initiated by May as soon as

<footnote>$^{13}$ A map $f$ from $\mathbf{R}^+$ into $\mathbf{R}^+$ is *reductive* if $f(x) \le x$ and *isotone* if $x \le y$ implies $f(x) \le f(y)$.</footnote>

<footnote>$^{14}$ Mas-Collel and Sonnenschein's result deals with the aggregation of complete preorders into the so-called *quasi-transitive relations*, i.e. the complete relations for which the asymmetric part is an order.</footnote>

<footnote>$^{15}$ This improved form was found again by [Fishburn and Rubinstein, 1986]; see [Barthélemy 1988a].</footnote>

<footnote>$^{16}$ They could as well be called *fuzzy objects*, but in the paper they are rather strangely called *valued preferences*.</footnote>

<footnote>$^{17}$ A Galois map between two lattices is a map $f$ such that $f(x \lor y) = f(x) \land y$ and $f(0) = 1$.</footnote>

<footnote>$^{18}$ A hierarchy – also called *n-tree* – on a set $E$ is a family $\mathcal{H}$ of subsets (called *classes* or *clusters*) of $E$ such that if two classes have a nonempty intersection, then one of these classes is contained in the other. One also assumes that $E$ and all the singletons are classes and that the empty set is not a class.</footnote>
1952 for the majority rule [May, 1952]. Several such results will be presented in the following sections.

### III. FEDERATION CONSENSUS RULES

A federation (also called simple game<fnref n="19" />) $\mathcal{F}$ on a set $N$ is a family $\mathcal{F}$ of subsets of $N$ (called coalitions) closed under supersets:

$$ \forall S \subseteq N \text{ and } \forall U \subseteq N, [S \in \mathcal{F} \text{ and } S \subseteq U] \Rightarrow [U \in \mathcal{F}]. $$

Federations allow defining consensus rules for many objects. For instance, let $N = \{1, 2, ..., n\}$ be a set of $n$ voters choosing their preference relations in a set of relations defined on a set $A$ and let $\Pi = (R_1, R_2, ..., R_n)$ be a profile of relations. For $(x, y) \in A^2$, we set:

$$ N_{\Pi}(x, y) = \{i \in N: xR_iy\} \text{ and } n_{\Pi}(x, y) = |N_{\Pi}(x, y)|. $$

Then, the collective preference relation $R_{\mathcal{F}}(\Pi)$ associated with the federation $\mathcal{F}$ and the profile $\Pi$ is given by:

$$ \forall (x, y) \in A^2, [xR_{\mathcal{F}}(\Pi)y] \Leftrightarrow [N_{\Pi}(x, y) \in \mathcal{F}]. $$

So, we take as the consensus relation the ordered pairs unanimously present in at least a coalition, what can also be written:

$$ R_{\mathcal{F}}(\Pi) = \bigcup_{S \in \mathcal{F}} \{\cap\{R_i, i \in S\}\} $$

(a formulation that will be generalized in Section VII).

The usual majority rule is obtained by considering the federation formed by all the majority coalitions, i.e. the coalitions of size greater than $n/2$. More generally, the so-called quota rules are defined by an integer $q$ and the federation

$$ \mathcal{F}_q = \{S \subseteq N: |S| \ge q\}. $$

By increasing the quota $q$, we put in the consensus relation ordered pairs more and more frequent in the relations of the profile. In the extreme case where $q = n$, we obtain the *Pareto* (or *unanimity*) rule where the consensus relation keeps only the unanimous ordered pairs.

We find again the oligarchic rules of the previous section (see footnote 11) by taking a filter, i.e. the set of supersets of a fixed set $M \subseteq N$, as the federation. If the set $M$ is reduced to a singleton $\{i\}$, i.e. if the filter is an *ultrafilter*, we obtain an (absolute) dictatorship, since the consensus relation is $R_i$.

Guilbaud [1952] was the first to use federations (called *families of generalized majorities* by him). He stated an Arrowian theorem for judgment aggregation (see Section VII) by essentially proving that Arrowian conditions required for a federation consensus rule imply that the federation is an *ultrafilter*<fnref n="20" />.

In [Monjardet, 1978], federation<fnref n="21" /> rules are used for tournaments. The problem of aggregating tournaments occurs for instance with the paired comparison method in socio-psychology. When a subject is asked to give all his binary preferences between some objects, the result can contain *intransitivities*, as $a > b > c > a$. So, when the subject must express strict preferences (indifference and abstention are excluded), the result is a tournament. In [Monjardet, 1978], several axiomatically-defined aggregation rules on tournaments are

<footnote n="19">¹⁹ This last appellation is due to von Neumann and Morgenstern who use this structure in their theory of games. It is unfortunate that it went on again in the different context of social choice theory. The better term of federation is due to Mirkin [1981].</footnote>

<footnote n="20">²⁰ For the use of ultrafilters in social choice theory, see [Monjardet, 1983].</footnote>

<footnote n="21">²¹ Here a federation is called a *family of majorities* and it satisfies an additional condition: a coalition belongs to the family $\mathcal{F}$ if and only if the complementary coalition does not belong to $\mathcal{F}$.</footnote>
characterized as rules defined by federations. As a by-product, one obtains a Galois connexion<sup>22</sup> showing the duality between Arrow's theorem and Ward's theorem<sup>23</sup> for linear orders.

The general problem with the federation consensus rules is that the consensus object
may be unsatisfactory. First, it may not belong to the class of considered objects (for instance,
the majority rule on linear orders may produce a non-transitive tournament). But, even if it is
not the case, the consensus object may remain unsatisfying. For instance, in cluster analysis,
the unanimity rule applied to hierarchies is often called the *strict rule*. This rule, like more
generally other quota rules, gives a hierarchy but which may miss some structural features of
the aggregated hierarchies and, in particular, the fact that two elements of the set *E* of
elements to classify may be put together in all the hierarchies before to be joined by a third
element. Then, one would wish that these two elements appear in some cluster of the
consensus hierarchy not containing the third element. The celebrated *Adams's rule* [Adams,
1986] achieves this wish. First, Adams associates a *nesting relation* on the subsets of *E* with
any hierarchy and conversely. Then, given a profile of hierarchies, the consensus hierarchy is
this one corresponding with the intersection of all the nesting relations associated with the
hierarchies of the profile. The one-to-one correspondence between hierarchies and nesting
relations has been generalized to a one-to-one correspondence between *Moore families*<sup>24</sup> and
*overhanging relations* by Domenach and Leclerc [2004a, 2004b, 2007]. The problem to
aggregate Moore families occurs in several fields and raises the same type of difficulties as
the above problem for hierarchies. Then, Adams's method can be generalized by using quota
rules on the overhanging relations associated with a profile of Moore families. But the
obtained relation is not necessarily an overhanging relation. Nevertheless, one can show that
there exists at most a unique overhanging relation containing this relation and satisfying
another desirable condition [Leclerc, 2004], [Domenach and Leclerc 2004b]. Now, when this
overhanging relation exists, one can come back to a Moore family. If one applies this method
to aggregate Moore families of a special class, one still needs to obtain a Moore family of the
same type. It is shown in [Domenach, 2010] that it is indeed the case for some classes of
Moore families.

IV. METRIC CONSENSUS RULES

The most known metric rule is the so-called *Kemeny rule* defined for complete preorders in [Kemeny, 1959]. Kemeny defines a measure of distance between two complete preorders as the number of their *disagreements*<fnref n="25" />. This measure is actually a distance since it is nothing else than the well-known *symmetric difference distance*. Then, Kemeny defines the

<footnote n="22">²² For all terms of order or lattice theories not defined here, see for instance [Davey and Priestley, 2001] and [Caspard, Leclerc and Monjardet, 2007].</footnote>

<footnote n="23">²³ A *cyclic triple* of preferences on three objects *a*, *b*, *c* is a triple such as: *a* > *b* > *c*, *b* > *c* > *a* and *c* > *a* > *b*. Ward's theorem says that majority rule applied on linear orders belonging to a set of linear orders always provides an order if and only if this set does not contain cyclic triples.</footnote>

<footnote n="24">²⁴ A *Moore family* (also called a *closure system*) on a set *N* is a family *F* of subsets of *N* (the *closed sets*) closed by intersection and containing the set *N*. By adding the empty set to a hierarchy, this one becomes a closure system.</footnote>

<footnote n="25">²⁵ Two complete preorders have two (respectively one) disagreement(s) for the pair {x, y} if one prefers x to y and the other y to x (respectively, is indifferent between x and y). In the case of linear orders where the number of disagreements can only be equal to 0 or 2 for each pair, half this distance normalized between -1 and +1 is Kendall's tau, well-known to the statisticians [Kendall, 1938].</footnote>
remoteness between a profile of complete preorders and a complete preorder as the sum of the distances between this complete preorder and those in the profile. Finally, he defines the consensus complete preorders of a profile as the complete preorders minimizing the remoteness to this profile. His paper contains also an axiomatic characterization of the symmetric difference distance between complete preorders. Barthélemy [1979, see also 1981] improves it in a paper containing characterizations of this same distance for the most used sets of relations and where he also shows the independence of the considered axioms.

Any set of binary relations (and, more generally of sets) endowed with the symmetric difference distance becomes a metric space. In a metric space, a "point" minimizing the sum of its distances to an *n*-tuple of other points is classically called a (metric) median of these points. Then, Kemeny's rule is a particular case of what has been called the median procedure<sup>26</sup> to define consensus objects. In the case of arbitrary binary relations, this procedure has been independently proposed by Barbut [1967] and Mirkin [1974]. Both authors observe that the majority (or Condorcet) relation of a profile of (arbitrary) relations is a median of this profile. But, this procedure is a "multiprocedure" in the sense that a profile has generally several medians. And generally the computation of median objects amounts to solve difficult combinatorial optimisation problems (see Section VIII).

Consider first the case where the objects are linear orders. In this case, one can observe that the median procedure can be defined in many other ways (sixteen are presented in [Monjardet, 1990b]). For instance, in statistics, a classic concordance coefficient between the linear orders of a profile is the so-called Kendall-Ehrenberg's coefficient *U*. This coefficient is formed by the mean of Kendall's tau on the pairs of linear orders of the profile. But since Kendall's tau is a normalization of the symmetric difference distance between linear orders, computing a median order of a profile Π of linear orders is equivalent to computing a linear order *L* maximizing the coefficient *U*(Π + *L*)<sup>27</sup>. Several of the many ways to define median linear orders have been independently proposed in the literature. In particular, arguments advanced by Guilbaud [1952] and Young [1988] lead to think that it was the rule proposed by Condorcet to palliate the "Condorcet effect" (the possible existence of cycles in the majority relation)<sup>28</sup>, see [Monjardet, 2005 or 2008] for details. A remarkable result is the axiomatic characterization of the median rule for linear orders by Young and Levenglick [1978] who use in particular a *consistency axiom*<sup>29</sup> that we will find again several times. The median procedure also appeared in cluster analysis. It has been first used for partitions by Régnier [1965], then independently by Mirkin [1974]. The problems related to the computation of median relations will be examined in Section VIII.

The median procedure has been also used for hierarchies by Margush and McMorris
[1981]. The case of hierarchies is particular since the set of all hierarchies (on a set) is
endowed with a median semilattice structure (see Section VII). Then, median hierarchies can
be easily obtained from the majority hierarchy [Barthélemy and McMorris, 1986]. In this
same paper, the characterization of the median procedure for hierarchies, by the consistency
axiom (see footnote 29) and four other axioms, is a particular case of the characterization of

<footnote n="26">26 For a survey on the median procedure up to 1988, see [Barthélemy and Monjardet, 1981 and 1988]. For historical details on the median in several (discrete or not) metric spaces, see [Monjardet, 1991 and 2008].</footnote>

<footnote n="27">²⁷ For an alike use of the Boarda-Kendall coefficient, see [Monjardet, 1985 and 1997].</footnote>

<footnote n="28">²⁸ When there is no Condorcet effect, all the median linear orders are the linear orders containing the order given by the majority rule (if the number of voters is odd, there is a unique median).</footnote>

<footnote n="29">²⁹ This *consistency axiom* says that if two profiles of linear orders have some identical median linear orders, then the profile formed by the concatenation of these two profiles must have these identical linear orders as its median linear orders.</footnote>
medians in a median semilattice presented in Section VII. A class belongs (respectively, does not belong, or may or not belong) to a median hierarchy of an *n*-tuple of hierarchies if it occurs in at least *n*/2 (respectively less than *n*/2, or equal to *n*/2) classes of the *n*-tuple. More generally, Barthélemy [1988b] defines a *thresholded consensus* rule by considering an interval [*m*, *m*'] of numbers and by setting that a class belonging to *k* hierarchies of a profile of hierarchies belongs (respectively, does not belong, or may or not belong) to a consensus hierarchy of this profile if *k* ≥ *m*' (respectively *k* < *m*, or *m* ≤ *k* < *m*'). Then, he characterizes these thresholded rules.

V. TOURNAMENT SOLUTIONS

This section is devoted to the so-called *tournament solutions* (see [Laslier, 1993, 1996, 1997] and [Moulin, 1986]) of which the aim is to determine a winner from a tournament. Remember that a *tournament* is a binary relation *T* such that, for any distinct elements *x* and *y*, we have one and only one of the following two possibilities: *xTy* or *yTx* (see Figure 1). Note that a transitive tournament is a (strict) linear order and conversely. The procedures described here (for other tournament solutions, see for instance [Laslier, 1996, 1997]) rather apply to unweighted tournaments, but the first two can be extended to weighted tournaments (see Section V.3).

A tournament can be used to summarize the result of a pairwise comparison method when there is no tie, as assumed in the sequel. For instance, if such a method is applied in an election, then we obtain the *majority tournament* T = (X, A) of the election: the set X of vertices is the set of the candidates of the election; in the following, *n* will denote the size of X; there is a directed edge from *x* to *y* in A if *x* is preferred to *y* by a majority of voters. Example 1 below illustrates these considerations.

Example 1. Assume that nine voters must rank *n* = 4 candidates *a*, *b*, *c*, and *d*. The preferences of the voters are supposed to be given by the following linear orders (where *x* > *y* still means that *x* is preferred to *y* by a majority of voters, as above, but here the relation > is assumed to be transitive: *x* > *y* and *y* > *z* involve *x* > *z*):

• the preferences of three voters are: *a* > *b* > *c* > *d*;

• the preferences of two voters are: *b* > *d* > *c* > *a*;

• the preference of one voter is: *d* > *c* > *a* > *b*;

• the preference of one voter is: *a* > *c* > *b* > *d*;

• the preference of one voter is: *d* > *b* > *a* > *c*;

• the preference of one voter is: *c* > *d* > *b* > *a*.

Here, the majority relation is not a linear order, but the tournament of Figure 1.

<figure><img src="image_5.png" /><figcaption>Figure 1. The majority tournament associated with the data of Example 1.</figcaption></figure>
We shall note that, if the election summarized by *T* admits a *Condorcet winner C*, i.e. a candidate preferred to any other candidate by a majority of voters, the tournament solutions described below will select *C* as the unique winner.

## V.1. NUMBER OF WINS: COPELAND'S SOLUTION

The procedure designed by A.H. Copeland<fnref n="30" /> [1951] is based on the *Copeland scores*. The Copeland score $s(x)$ of a candidate $x$ is the number of candidates defeated by $x$. From the graph theoretic point of view, $s(x)$ is the outdegree of $x$. A *Copeland winner* is any candidate with a maximum Copeland score (we may also rank the candidates according to the non-increasing Copeland scores).

Its application to Example 1 gives: $s(a) = 2$, $s(b) = 2$, $s(c) = 1$, $s(d) = 1$. Here, *a* and *b* are the Copeland winners.

## V.2. LINEAR ORDERS AT MINIMUM DISTANCE: SLATER'S SOLUTION

Slater solution [1961] allows also ranking the candidates. It consists in reversing a minimum number of arcs of $T$ in order to obtain a transitive tournament $O$, i.e. a linear order, and then to consider the winner of $O$ as a *Slater winner*. More precisely, let $O$ be a linear order defined on $X$. We define the distance $\theta(T, O)$ between $T$ and $O$ as the number of arcs of $T$ which have a different orientation in $O$ (note that this distance is half the symmetric difference distance of Section IV applied to the relations $T$ and $O$). A *Slater order of T* is a linear order $O^*$ minimizing $\theta(T, O)$ over the set of the linear orders $O$ defined on $X$. A *Slater winner of T* is the winner of any Slater order of $T$. We note $i(T)$ the minimum number of arcs that must be reversed in $T$ to get a Slater order $O^*$ of $T$: $\theta(T, O^*) = i(T)$; $i(T)$ is called the *Slater index of T*.

It is easy to see that the Slater index of the tournament of Figure 1 is equal to 1: reversing $(d, a)$ is sufficient to obtain a linear order, namely $a > b > c > d$. In fact, we may prove that this reversing is also necessary to obtain a linear order: thus $a > b > c > d$ is the only Slater order of this tournament and *a* is its only Slater winner.

Attention had been paid to combinatorial aspects of Slater's solution. For instance, the maximum values that the Slater index can take, the number of Slater orders that a given tournament can admit, some links between Slater orders and Hamiltonian paths, or the construction of tournaments with a given Slater index are investigated in papers like [Barthélemy *et al.*, 1995], [Bermond, 1972, 1973], [Charon and Hudry, 2000, 2003], [Hudry, 1997]. The links between Slater's solution and other tournament solutions have also been studied. For example, Bermond [1972] showed that the Copeland score of a Slater winner in a tournament with $n$ vertices is at least $n/2$; this result was generalized to weighted tournaments in [Charon *et al.*, 1997a] while [Guénoche, 1995] provides bounds for the rank of any vertex in a Slater order, still based on the Copeland scores (or on the weights of the arcs of the considered tournament, if this one is weighted). Bermond [1972] also exhibited a tournament with 7 vertices such that the set of Copeland winners and the one of Slater winners are disjoint. In fact, as pointed out in [Charon and Hudry, 2007a], the minimum number of vertices for such a situation to occur is 6. The Copeland scores may also be involved to provide bounds of the Slater index, as in [Charon *et al.*, 1992a] and [Charon and Hudry,

<footnote n="30">³⁰ According to I. McLean, H. Lorrey and J. Colomer [2008], “Ramon Llull (ca 1232-1316) (...) made contributions which have been believed to be centuries more recent. Llull promotes the method of pairwise comparison, and proposes the Copeland rule to select a winner.”</footnote>
2003]. More recently, Charon and Hudry [to appear] study the distance between Slater orders and Copeland orders (i.e., orders obtained by ranking the vertices of a tournament T according to the non-increasing Copeland scores of T). They show that there exist tournaments T admitting Slater orders $O_S$ and Copeland orders $O_C$ such that the distance $\theta(O_S, O_C)$ between these orders reaches its maximum, equal to $n(n - 1)/2$, in spite of Bermond's 1972 result about the Copeland score of a Slater winner.

For more detailed surveys on Slater's solution, see [Charon et al., 1996b], [Charon and Hudry, 2007, 2010] or [Laslier, 1996, 1997].

### V.3. EXTENSION OF SLATER'S SOLUTION TO WEIGHTED TOURNAMENTS

If T represents the majority tournament of a pairwise comparison method applied for instance to an election, we may weight the arcs of T. A usual way to do this consists in defining the weight $w(x, y)$ of an arc $(x, y)$ as the difference between twice the number $m(x, y)$ of voters who prefer $x$ to $y$ minus the number $m$ of voters when a majority of voters prefers $x$ to $y$: $w(x, y) = 2m(x, y) - m$. Then, instead of considering the number of arcs that must be reversed in T to make it transitive, we may want to compute a minimum weighted set of arcs such that the simultaneous reversal of these arcs transforms T into a linear order. This allows representing the problem of aggregating preferences into median relations. This includes the so-called Kemeny's problem<fnref n="31" /> consisting in computing a median linear order, then also called a Kemeny order, i.e. a linear order minimizing the total number of disagreements with respect to the preferences of the voters when these preferences are assumed to be linear orders.

More formally, consider an election in which $m$ voters want to rank $n$ candidates belonging to the set $X$. Let $\Pi = (O_1, O_2, ..., O_m)$ denote the profile of the preferences of the $m$ voters. Each preference $O_j$ ($1 \le j \le m$) is assumed to be a linear order here, but more generally, it is a binary relation defined on $X$: $O_j \subseteq X \times X$. For a binary relation $O$ defined on $X$, let $\delta(O_j, O)$ be the symmetric difference distance between $O_j$ and $O$: $\delta(O_j, O) = |O_j \Delta O|$, where $\Delta$ denotes the symmetric difference between sets. We may interpret $\delta(O_j, O)$ as the number of disagreements between $O_j$ and $O$. Then we define a remoteness $R(\Pi, O)$ between $\Pi$ and a binary relation $O$ by $R(\Pi, O) = \sum_{j=1}^{m} \delta(O_j, O)$. We may interpret $R(\Pi, O)$ as the total number of disagreements between $\Pi$ and $O$. A median relation is a relation $O^*$ minimizing $R$ over a prescribed set $\Omega$ of relations fulfilling some structural properties:

$$R(\Pi, O^*) = \min_{O \in \Omega} R(\Pi, O).$$

Here, all the preferences $O_j$ ($1 \le j \le m$) are linear orders and $\Omega$ is the set of linear orders defined on $X$. Slater's problem can also be stated in this way: in this case, $\Pi$ contains only one preference ($m = 1$) which is a tournament $T$ and $\Omega$ is still the set of linear orders defined on $X$; then, we may show that, for any linear order $O$, $\delta(T, O)$ is even and that we have the relations $\theta(T, O) = \delta(T, O)/2$ and, for any candidate $x$ preferred to another candidate $y$ according to $T$, we have $w(x, y) = 1$. In both cases, any instance of Kemeny's problem or of Slater's problem can be represented by a tournament $T$ weighted by $w(x, y) = 2m(x, y) - m$, and the aim is then to reverse in $T$ the orientation of arcs such that the total weight with

<footnote n="31">³¹ Also called Kemeny's rule. As this problem can be stated in different ways (see for instance [Monjardet, 1990b] and [Charon and Hudry, 2007, 2010]), several authors rediscovered this problem under different names. In fact, in Kemeny's problem, individual preferences are complete preorders and the median relation should also be a complete preorder. Anyway, “Kemeny's problem” is often the expression used to call the problem consisting in aggregating linear orders into a median linear order, as we do here.</footnote>
respect to *w* of the reversed arcs is minimum while this reversing transforms *T* into a linear order (which will be a median order).

For the data of Example 1, the weighted tournament is the one of Figure 2. This tournament admits only one Kemeny order: *a* > *b* > *c* > *d*, which is also a Slater order (but this is not true in general).

<figure><img src="image_6.png" /><figcaption>Figure 2. The weighted tournament associated with the data of Example 1.</figcaption></figure>

### V.4. MAXIMAL TRANSITIVE SUBTOURNAMENTS: BANKS’S SOLUTION

Among the other tournament solutions, one was designed by J. Banks [1985]. When the considered tournament *T* is transitive (i.e. *T* is a linear order), there exists a unique winner (the Condorcet winner of the election), who is selected as the winner of *T* by the usual tournament solutions. Otherwise, we may anyway consider the transitive subtournaments of *T* which are maximal with respect to inclusion, and then select the winner of each of them as the winners of *T*. This defines the *Banks's solution*: a *Banks winner* of *T* is the winner of any maximal (with respect to inclusion) transitive subtournament of *T*.

If we consider the majority tournament of Example 1, there exist three Banks winners: *a* (because of the maximal transitive subtournament induced by *a*, *b* and *c*), *b* (because of the subtournament induced by *b*, *c* and *d*) and *d* (because of the subtournament induced by *d* and *a*).

As for Slater's solution, some papers consider the links between Banks's solution and other tournament solution. For instance, Laffond and Laslier [1991] provide a tournament with 75 vertices such that the set of Copeland winners, the set of Slater winners and the set of Banks winners are pairwise disjoint. A tournament with 16 vertices such that the set of Slater winners and the set of Banks winners are disjoint can be found in [Charon et al., 1997b], while another tournament with 14 vertices satisfying the same property has been exhibited by Östergård and Vaskelainen [2010]. Nonetheless, the minimum number of vertices required to reach this property remains unknown. It is not the case for the disjunction between the set of Copeland winners and the one of Banks winners: it is shown in [Hudry, 1999] that the minimum number of vertices for this property is equal to 13.

## VI. RESTRICTED DOMAINS

A set of linear orders is a *Condorcet domain* (called also *acyclic* or *consistent domain*) if the strict majority rule applied to any profile of linear orders of this set always leads to an order. The best known example of Condorcet domain is the *single-peaked domain* defined by Black [1948]. Its definition requires defining a reference linear order *L* considered as the “objective” order over the alternatives. It is then also called the domain of *L-unimodal* linear orders.
Guilbaud [1952] provides an analysis of the single-peaked domain showing that the set of single-peaked linear orders has a distributive lattice structure<fnref n="32" /> and that the majority relation of a profile in this domain is the median of the elements of the profile in this lattice.

Using another paper by Guilbaud and Rosenstiehl [1963], Chameni-Nembua [1989] generalizes this result. Indeed, Guilbaud and Rosenstiehl show that the set $\mathcal{L}$ of linear orders can be endowed with a lattice structure called the “permutoèdre” lattice<fnref n="33" />. This lattice has an arbitrary linear order $\mathcal{L}$ as its greatest element and the dual of $\mathcal{L}$ as its least element. The unoriented covering relation of this lattice is the adjacency relation where two linear orders are adjacent if they differ on a unique pair of elements. The permutoèdre lattice is not distributive but it contains distributive sublattices. A sublattice of $\mathcal{L}$ is said to be *covering* if the covering relation in this sublattice is the same as the covering relation in $\mathcal{L}$. Then, Chameni-Nembua proved that any distributive covering sublattice of the permutoèdre lattice $\mathcal{L}$ is a Condorcet domain. Indeed, in this distributive lattice, the majority relation of a profile of $n$ (odd integer) linear orders is the metric (and algebraic, see Section VII) median of these $n$ elements. Related results were obtained by Abello [1985, for instance] and Fishburn [1997, for instance]. Finally, Galambos and Reiner [2008] provide a general theorem – unifying all the previous results – on the Condorcet domains that are distributive covering sublattices of the permutoèdre lattice. A survey on all these results can be found in [Monjardet, 2009].

## VII. ABSTRACT CONSENSUS THEORIES

To begin this section, we cannot do better that quoting the following excerpt of the introduction of Barthélemy and Janowitz’s paper [1991]: “since Arrow’s 1951 theorem, there has been a flurry of activity designed to prove analogues of this theorem in other contexts, and to establish contexts in which the rather dismaying consequences of this theorem are not necessarily valid. The resulting theories have developed somewhat independently in a number of disciplines, and one often sees the same theorem proved differently in different contexts. What is needed is a general mathematical model in which these matters may be disposed of in a common setting. That is to say, we forget about the exact nature of the objects and, using some abstract structure on various sets of objects under consideration, concern ourselves instead with ways in which the structure can be used to summarize a given family of objects”. Proceeding in this manner, there are two main approaches. Rubinstein and Fishburn’s approach [1986], following a line initiated by Wilson [1975], uses linear algebra. The other approach uses ordered structures and it has been followed by several researchers of the *Centre d’analyse et de mathématique sociale*.

Recall that a *meet semilattice* $L$ is a partially ordered set such that the *meet* (i.e. the greatest lower bound) $x \triangleleftharpoons y$ of any two elements $x$ and $y$ of $L$ exists (then, the meet of any finite subset of $L$ exists). Dually, a *join semilattice* is a partially ordered set $L$ such that the *join* (i.e. the lowest upper bound) $x \triangleleftharpoons y$ of any two elements $x$ and $y$ of $L$ exists. A *lattice* is a meet and join semilattice. Observe that many sets of binary relations are (semi)lattices for the operations of set intersection $\cap$ and set union $\cup$. Two lines of research were followed. The

<footnote n="32">³² For the definitions concerning lattices, see the following section.</footnote>

<footnote n="33">³³ They considered also sublattices of this lattice as negotiation intervals between the preferences of two voters, an idea generalized in [Feldman-Högaasen, 1969].</footnote>
first one develops an axiomatic theory of consensus in (semi)lattices. The second develops the study of the median operation in (semi)lattices.<fnref n="34" />

In any partially ordered set, an element is formed from simpler elements: it is the join (respectively, the meet) of the so-called *join-irreducible* (respectively, of the so-called *meet-irreducible*) elements, i.e. of the elements not join of elements strictly lesser (respectively, not meet of elements strictly greater) than themselves<fnref n="35" />. In [Monjardet, 1990a] and [Leclerc and Monjardet, 1995], it is shown that the form of the consensus functions defined by the same axioms on a lattice strongly depends on the properties of this lattice, and in particular on a dependence relation $\delta$ defined on its join-irreducible elements by:

$$j \delta j' \text{ if } j \neq j' \text{ and there exists } x \in L \text{ such that } j, j' \nsubseteq x \text{ and } j < j' \lor x$$

They obtain the following result:

## THEOREM 2.

Let $L$ be a finite lattice and $F: L^n \to L$ a consensus function.

(1) If $L$ is distributive<fnref n="36" />, then $F$ is a federation consensus function if and only if $F$ is neutral monotonic.

(2) If $L$ is not distributive, then $F$ is a meet projection (oligarchic) consensus function if and only if it is neutral.

(3) If $L$ is strong, then $F$ is a meet projection (oligarchic) consensus function if and only if it is decisive and Paretian.

The axioms involved in this theorem are straightforward generalizations of independence, monotonicity, neutrality and Pareto axioms used in social choice theory. A federation consensus function is a function defined as in Section III by a federation $\mathcal{F}$ on the set $N$ of “voters”. Let $\Pi = (x_1, x_2, ..., x_n)$ be an $n$-tuple of elements of $L$. Then

$$F(\Pi) = \bigvee_{A \in \mathcal{F}} (\wedge_{i \in A} x_i).$$

We may see that this formulation is the same as in Section III, the operations of set union and intersection being replaced by the join and meet operations of a lattice. And, by replacing the ordered pairs by the join-irreducible elements, we may also write, like in Section III:

$$\forall j \in J, [j \in F(\Pi)] \Leftrightarrow [N_{\Pi}(j) \in \mathcal{F}],$$

where $N_{\Pi}(j) = \{i \in N: j \in x_i\}$.

In case (1) of Theorem 2, the lattice is distributive, which is equivalent to say that its dependence relation reduces to the order relation existing between its join-irreducible elements<fnref n="37" />. Then, there are as many neutral, monotonic consensus functions as there are federations (simple games) on $N$. But as soon as the lattice $L$ is no longer distributive, the same axioms reduce the class of admissible functions strongly: there exists a (nonempty)

<footnote n="34">³⁴ [Barthélemy, Leclerc and Monjardet, 1986] provides a survey up to 1986 on these two research lines and their applications to the comparison and to the consensus of classifications.</footnote>

<footnote n="35">³⁵ For instance, in the lattice of all binary relations, the join-irreducible elements are the relations containing a unique ordered pair $(x, y)$ and, in the meet semilattice of orders, the meet-irreducible elements are the linear orders.</footnote>

<footnote n="36">³⁶ A lattice $L$ is distributive if each one of the meet and join operations is distributive over the other, for instance if, for all $(x, y, z) \in L^3$, $x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z)$ (this distributivity of the meet operation over the join operation implies the distributivity of the join operation over the meet operation, and conversely).</footnote>

<footnote n="37">³⁷ For any partially ordered set $P$, there exists a distributive lattice such that the poset of its join-irreducible elements is isomorphic to $P$.</footnote>
subset A of N such that $F(\Pi) = \bigwedge_{i \in A} x_i$ (which means that the only admissible federations are those formed by the supersets of a nonempty subset of N). Finally, when L is strong, i.e. when the dependence relation is strongly connected, the decisivity and Paretian axioms imply the stronger axiom of neutral monotonicity. The above result is in fact a particular case of a more general result obtained for semilattices.

Since first Barbut's works [1961, 1969], the abstract latticial approach has also been
developed much for metric consensus. In this case, we have a meet (or a join) semilattice L
endowed with a distance d. Several distances are possible and the most usual, used below,
generalizes the symmetric difference distance. Axiomatic characterizations of these distances
can be found in [Barthélemy, 1979], [Monjardet, 1981] and [Barthélemy, Leclerc and
Monjardet, 1986].

Let $\Pi = (x_1, x_2, \dots, x_n)$ be an $n$-tuple of elements of $L$. The *remoteness* of an element $x$ of $L$ from $\Pi$ (with respect to the distance $d$) is

$$
R(\Pi, x) = \sum_{i \in N} d(x, x_i).
$$

A median of Π (with respect to the distance *d*) is any element of *L* minimizing this remoteness; it is called a Π-median. The set of Π-medians is denoted by *Med*<sub>*L*</sub>Π. Observe that, since there generally exist several medians, the median rule is a map from *L*<sup>*n*</sup> to 2<sup>*L*</sup>, so defining a multi-consensus rule.

On the other hand, several “majority” elements can be associated with Π, obtained by
using different forms of the majority rule. Let *J* (respectively, *J*') be the set of join-irreducible
(respectively, meet-irreducible) elements of *L*. We set:

$$
C(\Pi) = \{j \in J : |\{i \in N : j \le x_i\}| > n/2\}, C'(\Pi) = \{j' \in J' : |\{i \in N : j' \ge x_i\}| > n/2\},
$$

$$
B(\Pi) = \{j \in J : |\{i \in N : j \le x_i\}| \ge n/2\}, B'(\Pi) = \{j' \in J' : |\{i \in N : j' \ge x_i\}| \ge n/2\}
$$

and

$$
c(\Pi) = \bigvee C(\Pi); c'(\Pi) = \bigwedge C'(\Pi); b(\Pi) = \bigvee B(\Pi); b'(\Pi) = \bigwedge B'(\Pi).
$$

In a semilattice, some of these elements may not exist. For the existing elements, we
have $c(\Pi) \le b(\Pi) \le c'(\Pi)$ and $c(\Pi) \le b'(\Pi) \le c'(\Pi)$. If $n$ is odd, we have $c(\Pi) = b(\Pi)$ and
$b'(\Pi) = c'(\Pi)$. If $L$ is a distributive lattice, we have $c(\Pi) = b'(\Pi)$ and $c'(\Pi) = b(\Pi)$.

The reason to consider these majority elements will become clear below. We consider
as the distance a straightforward generalization of the symmetric difference distance
previously used in Section IV. This generalization uses the join-irreducible representation of
the elements mentioned above. Let $x$ be an element of a semilattice $L$; set $J_x = \{j \in J : j \le x\}$
(thus, $x = \bigvee J_x$). Now write, for any $(x, x')$ belonging to $L^2$:

$$
\delta(x, x') = |J_x \Delta J_{x'}| = |J_x \cup J_{x'}| - |J_x \cap J_{x'}| = |\{j \in J : [j \in J_x \text{ and } j \notin J_{x'}]\} - \{j \in J : j \in J_{x'}\}|.
$$

A meet semilattice *L* is said to be *lower distributive* if, for any *x* ∈ *L*, the lattice
{*x*′ ∈ *L*: *x*′ ≤ *x*} is distributive (see footnote 36). A *median semilattice* [Avann, 1961] is a
lower distributive meet semilattice *L* in which, for all (*x*₁, *x*₂, *x*₃) ∈ *L*³, *x*₁∨*x*₂∨*x*₃ exists as soon
as the three elements *x*₁∨*x*₂, *x*₁∨*x*₃ and *x*₂∨*x*₃ all exist. In such a median semilattice, the element
(*x*∧*x*')∨(*x*′∧*x*′′)∨(*x*′′∧*x*) exists for any (*x*, *x*′, *x*′′) ∈ *L*³ and is called the (*algebraic*) *median* of
these three elements. Then, it can be shown that, for Π = (*x*₁, *x*₂, ..., *x*ₙ), the (*algebraic*)
*median* of Π, i.e. the element *c*(Π), also exists (but not necessarily the element *b*(Π)). If a
median semilattice is a lattice, it is a distributive lattice. When *L* is a median semilattice, the
medians of a profile with respect to the metric δ can be easily obtained from the majority
elements, as shown in the result below. This characterization of medians with respect to δ in a
median semilattice [Bandelt and Barthélemy, 1984] generalizes a series of results on medians
in distributive lattices [Birkhoff and Kiss, 1947], [Barbut, 1961], [Monjardet, 1980]:
### THEOREM 3.

Let $L$ be a median semilattice and $\Pi \in L^n$ be a profile of $L$. If $n$ is odd, then $c(\Pi)$ is the unique $\Pi$-median; if $n$ is even, then the set of all $\Pi$-medians with respect to the symmetric difference distance metric $\delta$ is $Med_L(\Pi) = \{vK: C(\Pi) \subseteq K \subseteq B(\Pi) \text{ and } vK \text{ exists}\}$.

In particular, in a distributive lattice, the set of all $\Pi$-medians is the median interval $[c(\Pi), b(\Pi)] = \{x \in L: c(\Pi) \le x \le b(\Pi)\}$ [Monjardet, 1980]. If $n$ is odd, $c(\Pi) = b(\Pi)$ is the unique median. The fact that these properties characterize distributive lattices can be obtained from the following more general result due to Leclerc [1990], where the distance used is the distance $d_{sp}$ of the shortest path<fnref n="38" />:

### THEOREM 4.

A lattice is upper semimodular<fnref n="39" /> if and only if, for any profile $\Pi$ and for any $\Pi$-median $m$ (with respect to the distance $d_{sp}$), the inequality $c(\Pi) \le m$ holds.

Observe that this result gives a lower bound for medians (with respect to $d_{sp}$) in the case of an upper semimodular lattice. This is significant since, except for the median semilattice case, medians may be difficult to compute. Continuing this line of research, Leclerc gave many results on medians with respect to other metrics and other semilattices. A usual way to define metrics on semilattices (and more generally on partially ordered sets) is to use valuations. Let $v$ be a strictly isotone (i.e. $x < y$ implies $v(x) < v(y)$) real map on a meet semilattice $L$. The map $v$ is a lower valuation if it satisfies the following property whenever $xvy$ exists:

$$v(x) + v(y) \le v(x \wedge y) + v(x \vee y).$$

For all $(x, y) \in L^2$, set $d_v(x, y) = v(x) + v(y) - 2v(x \wedge y)$.

A classic result<fnref n="40" /> says that a strictly isotone real function $v$ on a meet semilattice $L$ is a lower valuation if and only if $d_v$ is a distance on $L$. The following characterization of lower valuations [Leclerc, 1993] provides an upper bound to medians:

### THEOREM 5.

A strictly isotone real function $v$ on a meet semilattice $L$ is a lower valuation if and only if, for any profile $\Pi$ such that $C'(\Pi)$ is not empty and for any $\Pi$-median $m$ with respect to the metric $d_v$, the inequality $m \le c'(\Pi)$ holds.

Obviously, there exist dual results for join semilattices and upper valuations ($v(x) + v(y) \ge v(x \wedge y) + v(x \vee y)$) and the application of these results to lattices gives, for instance, the following result:

### THEOREM 6.

A strictly isotone real function $v$ on a finite lattice $L$ is a valuation⁴¹ if and only if, for any profile $\Pi$ and for any $\Pi$-median $m$ with respect to the metric $d_v$, the inequalities $c(\Pi) \le m \le c'(\Pi)$ hold.

<footnote n="38">³⁸ Let $\prec$ be the covering relation of $L$: $x \prec y$ whenever $x \le z < y$ implies $x = z$. Setting $xEy$ if $x \prec y$ or $y \prec x$ defines an undirected graph $(L, E)$. The distance $d_{sp}$ between $x$ and $y$ is the minimum length of a path between $x$ and $y$ in this graph.</footnote>

<footnote n="39">³⁹ A lattice $L$ is upper (respectively, lower) semimodular if, for all $(x, y, z) \in L^3$, $x \wedge y \prec x$ and $x \wedge y \prec y$ imply (respectively, are implied by) $x \prec xvy$ and $y \prec xvy$ where $\prec$ denotes the covering relation of $L$. A lattice is modular if it is upper and lower semimodular. A distributive lattice is modular (but the converse is false).</footnote>

<footnote n="40">⁴⁰ See [Monjardet, 1981] for a survey on such results.</footnote>
We consider now the case of particular lower valuations called weight valuations. A real function $v$ on a meet semilattice $L$ is said to be a weight valuation if there exists a strictly positive real map $w$ defined on the set $J$ of its join-irreducible elements such that, for any $x \in L$,

$$v(x) = \sum_{j \in J(x)} w(j).$$

It is easy to see that a weight valuation $v$ on a meet semilattice is a lower valuation. The associated weight metric $d_v$ is given, for all $(x, y) \in L^2$, by

$$d_v(x, y) = \sum_{j \in J(x) \Delta J(y)} w(j).$$

In particular, setting $w(j)$ uniformly equal to 1, we get the lower valuation $v(x) = |J(x)|$, and the corresponding metric $d_v$ is nothing else than the metric $\delta$ of the symmetric difference defined above. The following result [Leclerc, 1994] provides upper bounds and intervals for medians.

### THEOREM 7.

Let $L$ be a finite meet semilattice endowed with a weight metric $d_v$.

For any profile $\Pi$ such that $b(\Pi)$ exists and for any median $m$ of $\Pi$, the inequality $m \le b(\Pi)$ holds.

For any profile $\Pi$ such that $c(\Pi)$ exists and for any median $m$ of $\Pi$, there exists a median $m_0$ of $\Pi$ such that:

(i) $m_0 \le c(\Pi)$;

(ii) $m_0 \le m$;

(iii) all the elements of the lattice interval $[m_0, m]$ are medians.

We consider now the case where the meet semilattice $L$ is lower distributive (recall that it means that, for any $x \in L$, the set $\{x\} = \{y \text{ with } y \le x\}$ is a distributive lattice). In this case, Leclerc [1994] first shows that a weight valuation $v$ on $L$ is characterized by the fact that it is strictly isotone and that, for all $(x, y) \in L^2$ such that $xvy$ exists, we have $v(x\wedge y) + v(xvy) = v(x) + v(y)$. Then, he extends the previous result on medians (with respect to the distance $\delta$) in median semilattices to this case:

### THEOREM 8.

Let $L$ be a finite lower distributive semilattice and $\Pi \in L^n$ be a profile such that $c(\Pi)$ exists, and let $v$ be a weight valuation on $L$. Then, if $n$ is an odd number, $c(\Pi)$ is the unique median. If $n$ is even, the set of all the $\Pi$-medians with respect to the metric $d_v$ is $\text{Med}_{d_v}(\Pi) = \{vK: C(\Pi) \subseteq K \subseteq B(\Pi) \text{ and } vK \text{ exists}\}$.

Observe that, in a lower distributive semilattice and contrary to a median semilattice, the element $c(\Pi)$ may not exist. Nevertheless, it is possible to give a way to search medians in this case.

Obviously, all the previous results can be applied to “concrete” objects. It suffices that the set of all the considered objects can be endowed with a (semi)latticial structure. It is the case for many sets of relations (like orders or equivalences), for many sets of classifications (like partitions or hierarchies), for many sets of maps (like fuzzy preorders, choice functions or ultrametrics). Then, to apply the previous results, it suffices to determine the latticial properties of these ordered sets. In some cases, one can also obtain specific results. The example below illustrates such a situation.

<footnote n="41">41 A strictly isotone real function $v$ on a lattice $L$ is a valuation if it satisfies $v(x \wedge y) + v(xvy) = v(x) + v(y)$. The existence of such a valuation characterizes the modular lattices.</footnote>
Let $\mathcal{O}$ be the set of all the orders defined on a set $X$ endowed with the inclusion relation. The partially ordered set $\mathcal{O}$ is a lower locally distributive meet semilattice$^{42}$ [Leclerc, 2003]. Using the above results on medians with respect to a weight metric, we can for instance obtain that the covering relation of any median order of a profile of orders is formed of majority ordered pairs (a generalization of a result on median linear orders can be found in [Monjardet, 1973]). On the other hand, a classic and desirable property for a consensus rule is the Pareto property, requiring that the consensus order keeps the unanimous preferences. In the latticial context, this property translates into the following form. A consensus rule on a semilattice $L$ has the *Pareto property* if for any profile $\Pi = (x_1, x_2, ..., x_n) \in L^n$ and for any consensus element $m$, $\wedge_{i \in N} x_i \leq m$ holds. In [Leclerc, 2003], it is shown that the median rule for orders with respect to the symmetric difference distance $\delta$ satisfies the Pareto property but that this property is not satisfied with respect to other weight metrics. The same is true for partitions [Barthélemy and Leclerc, 1995]. Still in [Leclerc, 2003], many similar results may be found concerning the Pareto property for various metrics and various semilattices. Observe for instance that Leclerc’s characterization of upper semimodular lattice given above (by the inequality $c(\Pi) \leq m$ for any $\Pi$-median $m$, with respect to the distance $\delta$) shows that in this case the median rule has the Pareto property (a result first obtained by Barthélemy [1981]). Barthélemy [1976] proves Paretian properties for metric procedures defined on large classes of binary relations by remoteness functions satisfying monotonicity properties.

Coming back to the axiomatic approach, we can search to provide an axiomatic characterization of median rules. As already said, the first such result was obtained by Young and Levenglick [1978] for the case of the median rule (with respect to the symmetric difference distance $\delta$) for linear orders. Barthélemy and Janowitz [1991] characterized the median rule (with respect to $\delta$) on median semilattices by the consistency property (see footnote 29) and four other properties. Their result was improved by McMorris, Mulder and Powers [2000] who use only the consistency property and two other properties.

Another abstract approach to the aggregation problem was initiated by Guilbaud [1952] as early as 1952. Indeed, in his paper “*Les théories de l'intérêt général et le problème logique de l'agrégation*”, Guilbaud considers the aggregation of individual opinions (or judgments) consisting of the answers “yes” or “no” to a series of questions. In other terms, the opinion of an individual (for instance, a judge) is the set of valuations 0 or 1 given to a set of binary propositions. When these propositions are logically connected, it is assumed that these valuations respect the connexions. For instance, if proposition $p$ implies proposition $q$, then an answer “yes” to $p$ implies an answer “yes” to $q$. So, Guilbaud searches independent and neutral aggregation rules such that the collective judgment always respects the same connexions as the individual judgments. And the answer is that they are only the dictatorships for which the collective judgment is the judgment of one individual. A reconstruction of Guilbaud’s proof and historical considerations on his paper can be found in Eckert and Monjardet (2010). One can observe that in this paper Guilbaud appears as a precursor of the so-called *judgment aggregation* considerably developed in the last years. In the present formulation of judgment aggregation, an individual judgment is the set of accepted propositions in an agenda of logically interconnected propositions$^{43}$.

<footnote>$^{42}$ A lower locally distributive meet semilattice is a meet semilattice such that all its principal ideals (x] are lower locally distributive lattices. A lower locally distributive lattice can be defined for instance by the fact that for any $x \in L$, the interval $[\wedge\{y \in L: y \prec x\}, x]$ is a Boolean lattice.</footnote>

<footnote>$^{43}$ For instance, in standard propositional logic, propositions have two truth values and it is assumed that an individual judgment satisfies coherence conditions like *consistency* or/and *completeness*.</footnote>
VIII. ALGORITHMIC AND COMPLEXITY ISSUES

As said in the introduction, the algorithmic complexity of a method plays an important role. It is usual to distinguish between polynomial problems and NP-hard ones. Let us remind that a problem is polynomial when there exists a polynomial method to solve it. On the opposite, the practical consequence of the NP-hardness of a problem is that none polynomial method is known to solve it exactly; so, solving such a problem exactly may require a CPU time which may increase exponentially with the size of the instances to solve (for more details upon the theory of algorithmic complexity and the theory of NP-completeness, see for instance [Barthélemy, Cohen and Lobstein, 1996] or [Garey and Johnson, 1979]).

The computation of median linear orders is a problem which can be modelled as a particular case of the *linear ordering problem*<sup>44</sup> and so as a 0-1 linear program (see, for instance [Reinelt, 1985] or [Charon and Hudry, 2010]). It has been shown to be NP-hard (see below). This fact induces that exact methods giving the median orders do not allow solving large (with respect to the number of alternatives) problems<sup>45</sup>. These methods are mainly based on branch and bound methods. For instance, Bermond and Kodratoff [1976], then Barthélemy, Guénoche and Hudry [1989] provide branch and bound algorithms later improved with the help of some theoretical results in [Charon et al., 1992b, 1996a, 1997a, 2006a]. When these methods cannot be applied, another possibility is to look for approximate solutions, with the hope to compute “good” solutions in a “reasonable” time. Some of these heuristics are specific to the considered problem (see [Charon and Hudry, 2010] for a survey). Other methods come from *metaheuristics* (general approximate methods) such as simulated annealing, tabu search, noising methods, genetic algorithms or even some hybridization between these different methods (once again, see [Charon and Hudry, 2010] for a survey). They have been used for instance in [Hudry, 1989], [Charon and Hudry, 1998, 2009]. If the quality of some specific heuristics may decrease quite fast with the size of the considered instance, metaheuristics seem to provide good results in a limited amount of computation time.

The computation of a median partition is also a NP-hard problem [Barthélemy and Leclerc, 1995]<sup>46</sup>. This problem can be modelled as an instance of another NP-hard problem known as the *clique partitioning problem*. Here also, metaheuristics can be applied to compute medians partitions. For instance, de Amorim, Barthélemy and Ribeiro [1992] apply simulated annealing and Tabu search to this problem. Charon and Hudry [1993, 2006b, 2007b, 2009] provide a metaheuristic based on their *noising method* (a metaheuristic which generalizes simulated annealing and threshold accepting methods, see [Charon and Hudry, 2001, 2002]). For other approaches, see the survey [Barthélemy and Leclerc, 1995].

The complexities of the tournament solutions depicted in Section V are summarized in
the following theorems (see [Hudry, 2009b] for more details and for complexity results about

<footnote n="44">44 This problem includes also a representation of Slater's problem. This one consists in searching a linear order fitting a tournament at best. And indeed the search of a median order can be stated as the search of a linear order fitting a *weighted* tournament at best (see Section V).</footnote>

<footnote n="45">⁴⁵ It is difficult to give a specific value, since the performances of the algorithms much depend on the considered instances and on the used computer. For example, the software available at the Web address http://www.enst.fr/~charon/tournament/median.html can deal with instances simulating some real data with 100 candidates in about 1 second. Random instances seem more difficult to solve (see [Charon and Hudry, 2006a]).</footnote>

<footnote n="46">⁴⁶ More precisely, the problem is NP-hard when the number of partitions to aggregate is not fixed, and its status is not known for a fixed value of this number.</footnote>
other tournament solutions; a more general survey on the complexity of voting procedures can be found in [Hudry 2009a]).

### THEOREM 9.

Let $T$ be a tournament with $n$ vertices.

* Computing the Copeland winners of $T$ can be done in $O(n^2)$.

* Computing a Banks winner can be done in $O(n^2)$ [Hudry, 2004].

### THEOREM 10.

The following problems are NP-complete:

* Given a tournament $T$ and a vertex $x$ of $T$, is $x$ a Banks winner of $T$? [Woeginger, 2003].

* Given a tournament $T$ and an integer $k$, is the Slater index $i(T)$ of $T$ less than or equal to $k$? (see [Hudry, 2010], based on the results obtained independently by [Alon, 2006], [Charbit, Thomasse and Yeo, 2007] and [Conitzer, 2006]).

### THEOREM 11.

The following problems are NP-hard:

* Given a tournament $T$, compute all the Banks winners of $T$.

* Given a tournament $T$, compute the Slater index $i(T)$ of $T$.

* Given a tournament $T$, compute a Slater winner of $T$.

* Given a tournament $T$, compute all the Slater winners of $T$.

* Given a tournament $T$ and a vertex $x$ of $T$, is $x$ a Slater winner of $T$?

* Given a tournament $T$, compute a Slater order of $T$.

* Given a tournament $T$, compute all the Slater orders of $T$.

### THEOREM 12.

The following problem belongs to co-NP:

* Given a tournament $T = (X, A)$ and a linear order $O$ defined on $X$, is $O$ a Slater order of $T$?

We may note that it is possible to compute a Banks winner in polynomial time while checking that a given vertex is a Banks winner is NP-hard; there is no contradiction, because we do not choose the Banks winner that we may compute in polynomial time (see [Guénoche, 1996] for an exponential algorithm computing all the Banks winners of a tournament). Note also that the decision problem of Theorem 11 is not known to belong to NP, and that the problem of Theorem 12 is conjectured to be co-NP-complete in [Hudry, 2010].

To finish this section, we consider the aggregation of linear orders into median relations. The case of a median relation which must be a linear order is the most studied (see [Bartholdi, Tovey and Trick, 1989], [Dwork et al., 2001], [Hemaspaandra et al., 2005], [Hudry, 1989 and 2008]; see [Charon and Hudry, 2010] for more general references on the properties of median linear orders).

### THEOREM 13.

The following problems are NP-hard:

* Let $m$ be an even integer greater than or equal to 4; given a profile $\Pi$ of $m$ linear orders, compute a median linear order of $\Pi$.

* Given a profile $\Pi$ of $m$ linear orders defined on a set $X$ with $n$ elements with $m$ odd and $m$ large enough (at least about $n^2$), compute a median linear order of $\Pi$.

The aggregation of two linear orders into a median linear order is a polynomial problem.
In other words, the aggregation of *m* linear orders into a median linear order is NP-hard when the number *m* of voters is large enough. More precisely, it is NP-hard for any fixed even value of *m* with *m* ≥ 4, but the minimum odd value of *m* such that this problem is NP-hard is not known.

Theorem 13 can be generalized into two directions. On the one hand, the same results apply if we consider a profile of any kind of preferences containing linear orders as special cases (for instance, profiles of orders, or of preorders, or of binary relations, and so on). On the other hand, the variants for which we look for a median relation which would not be necessarily a linear order but another kind of median partially ordered relation often remain also NP-hard when *m* is large enough (see also [Wakabayashi, 1986 and 1998] where the aggregation of binary relations into different types of median relations is studied):

THEOREM 14.

*The aggregation of *m* linear orders into a median relation is an NP-hard problem [Hudry, 1989, 2008, submitted] when:*

* the median relation must be an acyclic relation<sup>47</sup>, a complete preorder (see footnote 8) or a weak order<sup>48</sup> and *m* is any fixed even value with *m* ≥ 4 or *m* takes an odd value large enough (at least about *n*<sup>2</sup>);

* the median relation must be an interval order<sup>49</sup>, a semiorder<sup>50</sup> or a quasi-order<sup>51</sup> and *m* takes a value large enough (at least about *n*<sup>2</sup> for even values of *m*, or at least about *n*<sup>4</sup> for odd values of *m*).

Note that, when not trivial, the complexity of the above problems is not known for values of *m* less than the ones stated in Theorem 14. Note also that the complexity of the aggregation of linear orders into a median order or a median preorder remains unknown.

On the other hand, the next theorem can be obtained as a corollary of Section VI:

THEOREM 15.

<footnote n="47"><sup>47</sup> An acyclic relation is a relation without directed cycle.</footnote>

<footnote n="48"><sup>48</sup> Here, a weak order is defined as the asymmetric part of any complete preorder.</footnote>

<footnote n="49"><sup>49</sup> An interval order is an order R satisfying the property: $\forall (x, y, z, t) \in X^4$ with x, y, z and t pairwise distinct, (xRy and zRt) $\Rightarrow$ (xRt or zRy). The name “interval order” comes from the fact that such an order may be described by intervals defined on the set of real numbers and spread over the real axis. The relation xRy then means that the interval associated with x is utterly on the left of the interval associated with y; if the two intervals overlap, then x and y are incomparable. The implication (xRy and zRt) $\Rightarrow$ (xRt or zRy) means that, if the interval associated with x (respectively z) is completely on the left of the interval associated with y (respectively t), the interval associated with x must be on the left of the interval associated with t or the interval associated with z must be on the left of the interval associated with y. Note that the lengths of the intervals are not necessarily the same for all the intervals.</footnote>

<footnote n="50"><sup>50</sup> A semiorder is an interval order R satisfying the property: $\forall (x, y, z, t) \in X^4$ with x, y, z and t pairwise distinct, (xRy and yRz) $\Rightarrow$ (xRt or tRz). As an interval order, a semiorder may be represented by intervals. In this case, all the intervals have the same length. Then the implication (xRy and yRz) $\Rightarrow$ (xRt or (inclusively) tRz) means that, if the interval associated with x (respectively y) is completely on the left of the interval associated with y (respectively z), then the interval associated with any extra t cannot overlap the interval associated with x and the one associated with z simultaneously: the length of the interval associated with t is too small for that. For more details, see [Aleskerov, Bouyssou and Monjardet, 2007].</footnote>

<footnote n="51"><sup>51</sup> A quasi-order is here defined as the asymmetric part of any semiorder (we must observe that in the literature this asymmetric part can be also called semiorder).</footnote>
*The aggregation of single-peaked linear orders into a median relation is a polynomial problem when the median relation must be a linear order.*

Indeed in this case majority rule provides median linear orders.

BIBLIOGRAPHIE

ABELLO J.M. (1985) Intrinsic limitation of the majority rule, an algorithmic approach, *SIAM Journal on Algebraic and Discrete Methods* 6 (1), 133-144.

ADAMS E.N. III (1986) *N-trees as nestings: Complexity, similarity, and consensus*, Journal of Classification 3 (2), 299-317.

ALESKEROV F.T. (1999) *Arrovian Aggregation Models*, Kluwer (Theory and decision library Volume 39 in Mathematical and statistical methods).

ALESKEROV F.T., BOUYSSOU D., MONJARDET B. (2007) *Utility maximisation, choice and preference*, Studies in Economic Theory 16, Springer-Verlag.

ALON N. (2006) Ranking tournaments, *SIAM Journal on Discrete Mathematics* 20 (1), 137-142.

ARROW K.J. (1951) *Social Choice and Individual Values*, New-York, Wiley.

AVANN S.P. (1961) Metric ternary distributive semi-lattices, *Proceedings of the American Mathematical Society* 12, 407-414.

BANDELT H.J., BARTHÉLEMY J.-P. (1984) Medians in Median Graphs, *Discrete Applied Mathematics* 8, 131-142.

BANKS J. (1985) Sophisticated voting outcomes and agenda control, *Social Choice and Welfare* 2, 295-306.

BARBUT M. (1961) Médianes, distributivité, éloignements, *Publications du Centre de mathématiques sociales*, Paris; reprint (1980): *Mathématiques et Sciences humaines* 70, 5-31.

BARBUT M. (1967) Médianes, Condorcet et Kendall, note SEMA, Paris; reprint (1980): *Mathématiques et Sciences humaines* 69, 5-13.

BARBUT M. (1969) Une classe de demi-treillis ordonnés pouvant servir à des agrégations de critères, in *La décision : agrégation et dynamique des préférences*, CNRS, 27-35.

BARTHÉLEMY J.-P. (1976) Sur les éloignements symétriques et le principe de Pareto, *Mathématiques et Sciences humaines* 56, 97-125.

BARTHÉLEMY J.-P. (1979) Caractérisations axiomatiques de la distance de la différence symétrique entre des relations binaires, *Mathématiques et Sciences humaines* 67, 85-113.

BARTHÉLEMY J.-P. (1981) Trois propriétés des médianes dans un treillis modulaire, *Mathématiques et Sciences humaines* 75, 83-91.

BARTHÉLEMY J.-P. (1982) Arrow's theorem: unusual domain and extended codomain, *Mathematical Social Sciences* 3, 79-89.

BARTHÉLEMY J.-P. (1988a) Comments on "Aggregations of Equivalence Relations", by P.C. Fishburn and A. Rubinstein, *Journal of Classification* 5 (1), 85-87.

BARTHÉLEMY J.-P. (1988b) Thresholded consensus for *n*-trees, *Journal of Classification* 5 (2), 229-236.

BARTHÉLEMY J.-P., COHEN G., LOBSTEIN A. (1996) *Algorithmic Complexity and Communication Problems*, University College London Press, London.

BARTHÉLEMY J.-P., GUÉNOCHE A., HUDRY O. (1989) Median linear orders: heuristics and a branch and bound algorithm, *European Journal of Operational Research* 42, 313-325.

BARTHÉLEMY J.-P., HUDRY O., ISAAK G., ROBERTS F.S., TESMAN B. (1995) The reversing number of a digraph, *Discrete Applied Mathematics* 60, 39-76.

BARTHÉLEMY J.-P., JANOWITZ M.F. (1991) A formal theory of consensus, *SIAM Journal on Discrete Mathematics* 4, 305-322.
BARTHÉLEMY J.-P., LECLERC B. (1995) The median procedure for partitions, in *Partitioning data sets*, I.J. Cox, P. Hansen and B. Julesz (eds), American Mathematical Society, Providence, 3-34.

BARTHÉLEMY J.-P., LECLERC B., MONJARDET B. (1986) On the use of ordered sets in problems of comparison and consensus of classifications, *Journal of Classification* 3, 187-224.

BARTHÉLEMY J.-P., MCMORRIS F.R. (1986) The median procedure for *n*-trees, *Journal of Classification* 3, 329-334.

BARTHÉLEMY J.-P., MCMORRIS F.R. (1989) On an independence condition for consensus *n*-trees, *Applied Mathematics Letters* 2 (1), 75-78.

BARTHÉLEMY J.-P., MCMORRIS F.R., POWERS R.C. (1991) Independence conditions for consensus *n*-trees revisited, *Applied Mathematics Letters* 4 (5), 43-46.

BARTHÉLEMY J.-P., MCMORRIS F.R., POWERS R.C (1992) Dictatorial consensus functions on *n*-trees, *Mathematical Social Sciences* 25, 59-64.

BARTHÉLEMY J.-P., MONJARDET B. (1981) The median procedure in cluster analysis and social choice theory, *Mathematical Social Sciences* 1 (3), 235-267.

BARTHÉLEMY J.-P., MONJARDET B. (1988) The median procedure in data analysis: new results and open problems, in *Classification and related methods in data analysis*, H.H. Bock (ed.), North-Holland, 309-316.

BARTHOLDI III J.J., TOVEY C.A., TRICK M.A. (1989) Voting schemes for which it can be difficult to tell who won the election, *Social Choice and Welfare* 6, 157-165.

BERMOND J.-C. (1972) Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux, *Mathématiques et Sciences humaines* 37, 5-25.

BERMOND J.-C. (1973) The circuit-hypergraph of a tournament, in *Infinite and finite sets, Proceedings of the Colloquia Mathematica Societatis János Bolyai* 10, North Holland, 165-180.

BERMOND J.-C., KODRATOFF Y. (1976) Une heuristique pour le calcul de l'indice de transitivité d'un tournoi, *RAIRO* 10 (3), 83-92.

BIRKHOFF G., KISS S.A. (1947) A ternary operation in distributive lattices, *Bulletin of the American Mathematical Society* 53, 749-752.

BLACK D. (1948) On the rationale of group decision-making, *Journal of Political Economy* 56, 23-34.

BROWN J.D. (1975) Aggregation of preferences, *Quarterly Journal of Economics* 89 (3), 456-469.

CASPARD N., LECLERC B., MONJARDET B. (2007) Ensembles ordonnés finis : concepts, résultats, usages, Springer-Verlag.

CHAMENI-NEMBUA C. (1989) Règle majoritaire et distributivité dans le permutoèdre, *Mathématiques et Sciences humaines* 108, 5-22.

CHARBIT P., THOMASSE S., YEO, A. (2007) The minimum feedback arc set problem is NP-hard for tournaments, *Combinatorics, Probability and Computing* 16 (1), 1-4.

CHARON I., GERMA A., HUDRY O. (1992a) Encadrement de l'indice de Slater d'un tournoi à l'aide de ses scores, *Mathématiques, Informatique et Sciences humaines* 118, 53-68.

CHARON I., GERMA A., HUDRY O. (1992b) Utilisation des scores dans des méthodes exactes déterminant les ordres médians des tournois, *Mathématiques, Informatique et Sciences humaines* 119, 53-74.

CHARON I., GUÉNOCHE A., HUDRY O., WOIRGARD F. (1996a) A bonsaï branch and bound method applied to voting theory, in *Ordinal and Symbolic Data Analysis, Springer Verlag*, 309-318.

CHARON I., GUÉNOCHE A., HUDRY O., WOIRGARD F. (1997a) New results on the computation of median orders, *Discrete Mathematics* 165-166, 139-154.
CHARON I., HUDRY O. (1993) The noising method: a new method for combinatorial optimization, *Operations Research Letters* 14, 133-137.

CHARON I., HUDRY O. (1998) Lamarckian genetic algorithms applied to the aggregation of preferences, *Annals of Operations Research* 80, 281-297.

CHARON I., HUDRY O. (2000) Slater orders and Hamiltonian paths of tournaments, *Electronic Notes in Discrete Mathematics* 5, 60-63.

CHARON I., HUDRY O. (2001) The noising methods: a generalization of some metaheuristics, *European Journal of Operational Research* 135 (1), 86-101.

CHARON I., HUDRY O. (2002) The noising methods: a survey, in *Essays and Surveys in Metaheuristics*, P. Hansen and C.C. Ribeiro (eds), Kluwer Academic Publishers, Boston, 245-261.

CHARON I., HUDRY O. (2003) Links between the Slater index and the Ryser index of tournaments, *Graphs and Combinatorics* 19 (3), 309-322.

CHARON I., HUDRY O. (2006a) A branch and bound algorithm to solve the linear ordering problem for weighted tournaments, *Discrete Applied Mathematics* 154, 2097-2116.

CHARON I., HUDRY O. (2006b) Noising methods for a clique partitioning problem, *Discrete Applied Mathematics* 154 (5), 754-769.

CHARON I., HUDRY O. (2007a) A survey on the linear ordering problem for weighted or unweighted tournaments, *4OR: A Quarterly Journal of Operations Research* 5 (1), 5-60.

CHARON I., HUDRY O. (2007b) Application of the “descent with mutations” metaheuristic to a clique partitioning problem, *Proceedings of 2007 IEEE International Conference on Research, Innovation and Vision for the Future*, Vietnam, 29-35.

CHARON I., HUDRY O. (2009) Self-tuning of the noising methods, *Optimization* 58 (7), 1-21.

CHARON I., HUDRY O. (2010) An updated survey on the linear ordering problem for weighted or unweighted tournaments, *Annals of Operations Research* 175, 107-158.

CHARON I., HUDRY O. (to appear) Maximum distance between Slater orders and Copeland orders of tournaments, *Order*.

CHARON I., HUDRY O., WOIRGARD F. (1996b) Ordres médians et ordres de Slater des tournois, *Mathématiques, Informatique et Sciences humaines* 133, 23-56.

CHARON I., HUDRY O., WOIRGARD F. (1997b) A 16-vertex tournament for which Banks set and Slater set are disjoint, *Discrete Applied Mathematics* 80 (2-3), 211-215.

CONDORCET, M.J.A.N. Caritat, marquis de (1785), *Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix*, Imprimerie royale, Paris; facsimile version: Chelsea Publishing Company, New York, 1972.

CONITZER V. (2006) Computing Slater Rankings Using Similarities Among Candidates, in *Proceedings of the 21st National Conference on Artificial Intelligence (AAAI-06)*, Boston, MA, USA, 613-619.

COPELAND A.H. (1951) A “reasonable” social welfare function, Seminar on applications of mathematics to social sciences, University of Michigan.

DAVEY B.A., PRIESTLEY H.A. (2001) *Introduction to lattices and order*, Cambridge University Press.

DAY W.H.E., McMORRIS F.R. (2003) *Axiomatic Consensus Theory in Group Choice and Biomathematics*, SIAM, Philadelphia.

DE AMORIM S.G., BARTHÉLEMY J.-P., RIBEIRO C.C. (1992) Clustering and clique partitioning: simulated annealing and tabu search approaches, *Journal of Classification* 9, 17-42.

DOMENACH F. (2010) Consensus de familles de Moore typées, *Mathématiques et Sciences humaines* 190.
DOMENACH F., LECLERC B. (2004a) Closure systems, implicational systems, overhanging relations and the case of hierarchical classification, *Mathematical Social Sciences* 47 (3), 349-366.

DOMENACH F., LECLERC B. (2004b) Consensus of classification systems, with Adams's results revisited, in *Classification, Clustering and Data Mining Applications*, D. Banks, L. House, F.R. McMorris, P. Arabie and W. Gaul (eds), Berlin, Springer, 417-428.

DOMENACH F., LECLERC B. (2007) The structure of the overhanging relations associated with some types of closure systems, *Annals of Mathematics and Artificial Intelligence* 49, 137-149.

DWORK C., KUMAR R., NAOR M., SIVAKUMAR D. (2001) Rank aggregation methods for the Web, *Proceedings of the 10th International Conference on World Wide Web (WWW10)*, 613-622.

ECKERT D., MONJARDET B. (2010) Guilbaud's 1952 theorem on the logical problem of aggregation, *Mathématiques et Sciences humaines* 189.

FELDMAN-HÖGAASEN J. (1969) Ordres partiels et permutoèdre, *Mathématiques et Sciences humaines* 28, 27-38.

FISHBURN P.C. (1997) Acyclic sets of linear orders, *Social Choice and Welfare* 14, 113-124.

FISHBURN P.C., RUBINSTEIN A. (1986) Aggregation of equivalence relations, *Journal of Classification* 3 (1), 61-65.

GALAMBOS A., REINER V. (2008) Acyclic Sets of Linear Orders via the Bruhat Order, *Social Choice and Welfare* 30 (2), 245-264.

GAREY M.R., JOHNSON D.S. (1979), *Computers and intractability: a guide to the theory of NP-completeness*, Freeman and Company, San Francisco.

GUÉNOCHE A. (1995) How to choose according to partial evaluations, in *Advances in Intelligent Computing, IPMU'94*, B. Bouchon-Meunier et al. (eds), Lecture Notes in Computer Sciences 945, Springer-Verlag, Berlin-Heidelberg, 611-618.

GUÉNOCHE A. (1996) Vainqueurs de Kemeny et tournois difficiles, *Mathématiques, Informatique et Sciences humaines* 133, 57-66.

GUILBAUD G. Th. (1952) Les théories de l'intérêt général et le problème logique de l'agrégation, *Économie appliquée* 5, 501-584. English translation: Theories of the general interest and the logical problem of aggregation, *Electronic Journal for History of Probability and Statistics* 4, 2008.

GUILBAUD G. Th., ROSENSTIEHL P. (1963) Analyse algébrique d'un scrutin, *Mathématiques et Sciences humaines* 4, 9-33.

HEMASPAANDRA E., SPAKOWSKI H., VOGEL J. (2005) The complexity of Kemeny elections, *Theoretical Computer Science* 349, 382-391.

HUDRY O. (1989) *Recherche d'ordres médians : complexité, algorithmique et problèmes combinatoires*, PhD thesis, ENST, Paris.

HUDRY O. (1997) Nombre maximum d'ordres de Slater des tournois T vérifiant $σ(T) = 1$, *Mathématiques, Informatique et Sciences humaines* 140, 51-58.

HUDRY O. (1999) A smallest tournament for which the Banks set and the Copeland set are disjoint, *Social Choice and Welfare* 16, 137-143.

HUDRY O. (2004) A note on “Banks winners in tournaments are difficult to recognize” by G.J. Woeginger, *Social Choice and Welfare* 23, 113-114.

HUDRY O. (2008) NP-hardness results on the aggregation of linear orders into median orders, *Annals of Operations Research* 163 (1), 63-88.

HUDRY O. (2009a) Complexity of voting procedures, in *Encyclopedia of Complexity and Systems Science*, R. Meyers (ed.), Springer, New York, 2009.
HUDRY O. (2009b) A survey on the complexity of tournament solutions, *Mathematical Social Sciences* 57, 292-303.

HUDRY O. (2010) On the complexity of Slater’s problems, *European Journal of Operational Research* 203, 216–221.

HUDRY O. (submitted) On the computation of median complete preorders.

HUDRY O., LECLERC B., MONJARDET B., BARTHÉLEMY J.-P. (2009) Metric and latticial medians, in *Concepts and methods of decision-making*, D. Bouyssou, D. Dubois, M. Pirlot, H. Prade (eds), Wiley, 811-856.

KEMENY J.G. (1959) Mathematics without numbers, *Daedalus* 88, 577-591.

KENDALL M.G. (1938) *Rank correlation methods*, Hafner, New York.

LAFFOND G., LASLIER J.-F. (1991) Slater’s winners of a tournament may not be in the Banks set, *Social Choice and Welfare* 8, 355-363.

LASLIER J.-F. (1993) *Solutions de tournois*, habilitation à diriger les recherches en science économique, université de Cergy-Pontoise.

LASLIER J.-F. (1996) Solutions de tournois : un spicilège, *Mathématiques, Informatique et Sciences humaines* 133, 7-22.

LASLIER J.-F. (1997) *Tournament Solutions and Majority Voting*, Springer, Berlin, Heidelberg, New York.

LECLERC B. (1984) Efficient and binary consensus functions on transitively valued relations, *Mathematical Social Sciences* 8, 45-61.

LECLERC B. (1990) Medians and majorities in semimodular lattices, *SIAM Journal on Discrete Mathematics* 3 (2), 266-276.

LECLERC B. (1991) Aggregation of fuzzy preferences: a theoretic Arrow-like approach, *Fuzzy Sets and Systems* 43 (3), 291-309.

LECLERC B. (1993) Lattice valuations, medians and majorities, *Discrete Mathematics* 111, 345-356.

LECLERC B. (1994) Medians for weight metrics in the covering graphs of semilattices, *Discrete Applied Mathematics* 49, 281-297.

LECLERC B. (1998) Consensus of classifications: the case of trees, in *Advances in Data Science and Classification*, A. Rizzi, M. Vichi, H.-H. Bock (eds), *Studies in Classification, Data Analysis and Knowledge Organization*, Berlin, Springer-Verlag, 81-90.

LECLERC B. (2003) The median procedure in the semilattice of orders, *Discrete Applied Mathematics* 127 (2), 241-269.

LECLERC B. (2004) On the consensus of closure systems, *Annales du LAMSADE* 3, 237-247.

LECLERC B. (2007) Consensus of classifications based on frequent groupings, in *Selected Contributions in Data Analysis and Classification*, P. Brito, P. Bertrand, G. Cucumel F. De Carvalho (eds), Berlin, Springer, 317-324.

LECLERC B., MONJARDET B. (1995) Latticial theory of consensus, in *Social choice, Welfare and Ethics*, V. Barnett, H. Moulin, M. Salles, N. Schofield (eds), Cambridge University Press, 145-160.

MARGUSH T., McMORRIS F.R. (1981) Consensus *n*-trees, *Bulletin of Mathematical Biology* 43, 239-244.

MAS-COLLEL A., SONNENSCHEIN H. (1972) General possibility theorems for group decisions, *The Review of Economic Studies* 39, 185-192.

MAY K.O. (1952) A Set of Independent Necessary and Sufficient Conditions for Simple Majority Decision, *Econometrica* 20 (4), 680-684.

MCLEAN I., LORREY H., COLOMER J.M. (2008) Social Choice in Medieval Europe, *Electronic Journal for History of Probability and Statistics* 4 (1).
MCMORRIS F.R., MULDER H.M., POWERS R.C. (2000) The median function on median graphs and semilattices, *Discrete Applied Mathematics* 101, 221-230.

MIRKIN B.G. (1974) *Group Choice* (in Russian), English translation (1979), P. Fishburn (ed.), Winston, Washington.

MIRKIN B.G. (1975) On the problem of reconciling partitions, in *Quantitative Sociology, International Perspectives on Mathematical and Statistical Modelling*, New-York, Academic Press, 441-449.

MIRKIN B.G. (1981) Federations and transitive group choice, *Mathematical Social Sciences* 2, 35-38.

MONJARDET B. (1973) Tournois et ordres médians pour une opinion, *Mathématiques et Sciences humaines* 43, 55-70.

MONJARDET B. (1978) An axiomatic theory of tournament aggregation, *Mathematics of Operations Research* 3 (4), 334-351.

MONJARDET B. (1980) Théorie et applications de la médiane dans les treillis distributifs finis, *Annals of Discrete Mathematics* 9, 87-91.

MONJARDET B. (1981) Metrics on partially ordered sets - A survey, *Discrete Mathematics* 35, 173-184.

MONJARDET B. (1983) On the use of ultrafilters in social choice theory, in *Social Choice and Welfare*, P. K. Pattanaik and M. Salles (eds), Amsterdam, North-Holland, 73-78.

MONJARDET B. (1985) Concordance et consensus d'ordre totaux : les coefficients *K* et *W*, *Revue de statistique appliquée* 33 (2), 55-87.

MONJARDET B. (1990a) Arrowian characterizations of latticial federation consensus functions, *Mathematical Social Sciences* 20 (1), 51-71.

MONJARDET B. (1990b) Sur diverses formes de la “règle de Condorcet” d’agrégation des préférences, *Mathématique, Informatique et Sciences humaines* 111, 61-71.

MONJARDET B. (1991) Éléments pour une histoire de la médiane métrique, in *Moyenne, milieu, centre. Histoire et usages*, Coll. Histoire des Sciences et Techniques, n°5, éditions de l'HEESS, Paris.

MONJARDET B. (1997) Concordance between two linear orders: the Spearman and Kendall coefficients revisited, *Journal of Classification* 14 (2), 269-295.

MONJARDET B. (2005) Social choice theory and the “Centre de mathématique sociale”. Some historical notes, *Social Choice and Welfare* 25, 433-456.

MONJARDET B. (2008) “Mathématique Sociale” and Mathematics. A case study: Condorcet’s effect and medians, *Electronic Journ@l for History of Probability and Statistics* 4 (1).

MONJARDET, B. (2009) Acyclic domains of linear orders: a survey, *The Mathematics of Preference, Choice and Order, Essays in honor of Peter C. Fishburn*, S. Brams, W. V. Gehrlein, F. S. Roberts (eds), Springer, 139-160.

MONJARDET B., RADERANIRINA V. (2004) Lattices of choice functions and consensus problems, *Social Choice and Welfare* 23, 349-382.

MOULIN H. (1986) Choosing from a tournament, *Social Choice and Welfare* 3, 272-291.

ÖSTERGÅRD P. R. J., VASKELAINEN V. P. (2010) A tournament of order 14 with disjoint Banks and Slater sets, *Discrete Applied Mathematics* 158 (5), 588-591.

RÉGNIER S. (1965) Sur quelques aspects mathématiques des problèmes de classification automatique, *ICC Bull.* 4, 175-191; reprint (1983): *Mathématiques et Sciences humaines* 82, 13-29.

REINELT G. (1985) *The linear ordering problem: algorithms and applications*, Helderman Verlag, Berlin.

RUBINSTEIN A., FISHBURN P.C. (1986) Algebraic aggregation theory, *Journal of Economic Theory* 38 (1), 63-77.
SLATER P. (1961) Inconsistencies in a schedule of paired comparisons, *Biometrika* 48, 303-312.

WAKABAYASHI Y. (1986) *Aggregation of binary relations: algorithmic and polyhedral investigations*, PhD Thesis, Augsbourg.

WAKABAYASHI Y. (1998) The Complexity of Computing Medians of Relations, *Resenhas* 3 (3), 323-349.

WILSON R.B. (1975) On the theory of aggregation, *Journal of Economic Theory* 10, 89-99.

WOEGINGER G.J. (2003) Banks winner in tournaments are difficult to recognize, *Social Choice and Welfare* 20, 523-528.

YOUNG H.P. (1988) Condorcet’s theory of voting, *American Political Science Review* 82 (4), 1231-1244; reprint (1990): *Mathématique, Informatique et Sciences humaines* 111, 43-58.

YOUNG H.P., LEVENGLICK A. (1978) A Consistent Extension of Condorcet’s Election Principle, *SIAM Journal on Applied Mathematics* 35, 285-300.

ZADEH L.A. (1971) Similarity and fuzzy ordering, *Information Sciences* 3, 177-200.