Sébastien Courtin
email: sebastien.courtin@u-cergy.fr

Mathieu Martin
email: mathieu.martin@u-cergy.fr

Bertrand Tchantcho
email: btchantcho@yahoo.fr

Positional rules and q Condorcet consistency

Keywords: Positional rules (Simple and Sequential), Condorcet Consistency, q-majority JEL Classification D71,D72

A well-known result in Social Choice theory is the following: every scoring rule (positional rules) violates Condorcet consistency. A rule is Condorcet consistent when it selects the alternative that is preferred to every other alternative by a majority of individuals. In this paper, we investigate some limits of this negative result. We expose the relationship between a weaker version of the Condorcet consistency principle and the scoring rules. Our main objective is then to study the condition on the quota that ensure that positional rules (simple and sequential) satisfy this principle.

Introduction

A wide literature on voting theory is concerned with the theoretical debate between Condorcet social choice methods on one hand, and positional (or scoring) systems -voting à la Borda -on the other hand. The first ones consider, following [START_REF] Condorcet | Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix[END_REF], that the collective choice has to be based on majority duals between alternatives; while the second ones introduced by Borda (1781), suggest to deduce the collective preference from a numerical evaluation taking into account the positions of the alternatives in the orders of individual preferences.

There are several arguments in favor of either type of procedures, discussed in an abundant literature (see [START_REF] Nurmi | Comparing voting systems[END_REF][START_REF] Nurmi | Voting paradoxes and how to deal with them[END_REF][START_REF] Saari | Which is better: the Condorcet or Borda winner?[END_REF] among others). The most significant contributions concerning positional rules are due to [START_REF] Smith | Aggregation of preferences with variable electorate[END_REF], [START_REF] Young | An axiomatization of Borda's rule[END_REF][START_REF] Young | Social choice scoring functions[END_REF] and [START_REF] Saari | Geometry of voting[END_REF]. The results presented by these three authors reveal some very natural properties that are satisfied only by positional mechanisms. They are certainlty powerful arguments for adopting a positional approach. Unfortunately we know from [START_REF] Condorcet | Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix[END_REF] that the Borda rule and more generally the positional rules do not necessarily choose the Condorcet winner when it exists which is not the case of Condorcet consistent rule. A Condorcet winner is an alternative that is preferred to every other alternative by a majority of individuals: such an alternative would beat every other in majority comparisons. A Condorcet consistent rule selects the Condorcet winner when it exists. Similarly, it is well known that positional rules fail also to satisfy some weaker version of this property.

There is no doubt about the importance of these results, since it provides a clear axiomatic boundary between Borda's and Condorcet's approaches of social choice mechanisms. It is worth noting, however, that the above-mentioned negative results have been obtained by assuming that the simple majority is used. An alternative is majority preferred to an other alternative if at least more than one half of the individuals prefer this alternative to the other one 1 .

The question we propose to tackle in this paper is then the following: to what extent does a larger majority (supra-majority) modify these negative results? To assume a larger majority is not so common in social choice theory. An important result concerning a supra-majority have been established by [START_REF] Ferejohn | On a class of rational social decision procedures[END_REF]. According to a given supra-majority m, an alternative is socially preferred to an other alternative if at least m individuals prefer this alternative to the other one. They give a necessary and sufficient condition on the majority needed in order to ensure that the rule associated with that majority always selects an alternative 2 . In a voting game context, they give simple and elegant condition for which the Core is non empty 3 .

The purpose of this paper is then to give conditions such that the alternatives chosen by a rule belongs to the Core. For that, we follow [START_REF] Baharad | The Borda rule, Condorcet consistency and Condorcet stability[END_REF] who study the relationship between the positional rule and what they call the "q Condorcet consistency" principle. Given a supra-majority q, a rule satisfies this principle if the winner of this rule is not preferred by any other alternative by a q majority of individuals. Unfortunately, they have results for only one special positional rule, the Borda rule. We want to extent these results by investigating more positional rules.

Note that the well known positional approach takes place in a single stage process, where the winner(s) is (are) the alternative(s) with the highest score. But it can also be used in a multi-stage process of sequential eliminations, in each stage of which the alternative(s) with the least votes is (are) eliminated. We will then focus also on this kind of rules in this paper.

Our main objective is then to study the conditions on the majority that ensure that positional rules (simple and sequential) satisfy the q Condorcet consistency principle.

The remainder of this work is organized as follows: Section 2 is a presentation of the general framework with notations and definitions. Section 3 provides a characterization of the most famous simple positional rules vis-à-vis the q Condorcet Consitency principle. Then, Section 4 provides results for sequential positional rules. Finally, Section 5 concludes the paper.

Notations and definitions

Consider a finite set N of n individuals or voters. For any subset S of N , S c denotes the complementary of S, that is N \ S. Consider a finite set A = {a 1 , ..., a k } of k distinct alternatives (or candidates), k 3. Let 2 A be the set of nonempty subsets of A. Individual preference relations are defined over A and are assumed to be strict (indifference is not allowed). Assume that the preference relation R i of individual i, i 2 N , is a complete, antisymmetric and transitive binary relation (or simply a linear order) on A and let L be the set of all linear orders on A. A profile is an n-tuple R = (R i ) i2N of individual preference relations, one for each individual. The set of all profiles on N will be denoted by L N .

A social choice correspondence (SCC ) is a mapping F from L N to the set of nonempty subsets of A. This rule specifies the collective choice for any preference profile, F : L N ! 2 A . For all profile R, F (R) is the set of winners according to R.

Note that we do not introduce in this paper a mechanism in order to break ties among alternatives. That is why we focus on social choice correspondences and not on social choice functions which assign a single alternative to each profile. It should however be emphasized that the results presented here remain valid when we take into account a mechanism in order to break ties. Now, we need additional notations to present the simple positional rules (PR) and the sequential positional rules (SPR) under focus in the present paper.

Given

↵ 1 = 1, ↵ |B| = 0. ↵ r (B, a h , R i
) is the number of points given to the alternative a h 2 B by the individual i.

Definition 1. Given B 2 2 A , R 2 L N , a h 2 B and a scoring vector ↵ 2 R |B| , the score of a h denoted Sc (B, a h , R, ↵) is defined as follows: Sc (B, a h , R, ↵) = n ⌃ i=1 ↵ r(B,a h ,R i ) .
In social choice processes using PR, the winning alternatives are those with the highest score, as stated in the following definition. Definition 2. Let B 2 2 A and a scoring vector ↵ 2 R |B| . A simple positional rule (PR) with scoring vector

↵ denoted F ↵ is a social choice correspondence F such that 8R 2 L N , 8a h 2 B, a h 2 F ↵ (R) if [Sc (B, a h , R, ↵) Sc (B, a j , R, ↵) 8a j 2 B].
From the definitions of PR, it appears that given some issue B, a PR is defined by a vector ↵ 2 R |B| . We can then express the three usual procedures: plurality rule denoted F ↵ 0 where ↵ = (1, 0, ..., 0); negative plurality rule denoted F ↵ 1 with ↵ = (1, ..., 1, 0) and Borda rule denoted

F ↵ 2 corresponding to ↵ = (1, k 2 k 1 , ..., k r k 1 , ..., 1 k 1 , 0).
We now introduce sequential positional rules (SPR). Let ↵ A = ↵ k , ..., ↵ |B| , ..., ↵ 2 a collection of scoring vectors, each vector ↵ |B| being associated with each possible cardinality |B| of the subset B ✓ A, |B| 2. At the first step of the sequential process, scores are computed using the vector ↵ k and the losing alternatives defined below are eliminated. In the next step, the corresponding vector is used to compute the scores and again the losing alternatives are eliminated. The sequential process is repeated until a set of winners (possibly one) is obtained (see [START_REF] Lepelley | Constant scoring rules, Condorcet criteria and single-peaked preferences[END_REF].

More formally, Definition 3. Given B 2 2 A , R 2 L N and a scoring vector ↵ |B| 2 R |B| , the set of losing alternatives denoted L B, R, ↵ |B| is such that:

L B, R, ↵ |B| = ⇢ a h 2 B : ⇢ Sc B, a h , R, ↵ |B|  Sc B, a j , R, ↵ |B| for all a j 2 B and 9a j 2 B : Sc B, a h , R, ↵ |B| < Sc B, a j , R, ↵ |B| .
Note that when there is only one element in B, L (B, R, ↵ 1 ) = ;. Then we have the following definition for the SPR. Definition 4. A sequential positional rule (SPR) associated with a collection of vectors

↵ A = ↵ k , ..., ↵ |B| , ..., ↵ 2 , denoted F ↵ A is a social choice correspondence F such that given B ✓ A, R 2 L N and a h 2 A, a h 2 F ↵ A (R) () a h 2 A p ,
with A p sequentially defined in the following way:

A 1 = A A 2 = A L A 1 , R, ↵ |A 1 | . . . A |B|+1 = A |B| L A |B| , R, ↵ |B| . . . A p = A p 1 L A p 1 , R, ↵ |A p 1 | and L A p , R, ↵ |Ap| = ;
. In order to illustrate this definition, let us consider the three-alternative case, that is A = {a 1 , a 2 , a 3 }. We then have

↵ A = (↵ 3 , ↵ 2 ), with ↵ 3 = (1, , 0), 0   1,
where 1, and 0 are the scores of the alternatives ranked first, second and third respectively, in individual preference relations in the first step, and ↵ 2 = (1, 0). More generally, given a profile of individual preferences, the total score of an alternative is the sum of individual scores, over the whole set of individuals. A PR selects the set of alternatives with the highest score. As a difference, an SPR first eliminates the alternatives with the smallest score at the first step, and then selects the alternatives with the highest score at the last step.

Note that with this formulation of sequential positional rules, there is no fixed relation between two scoring vectors of different steps: for example, we may use plurality at step 1 and negative plurality at step 2, etc. However, the most well known sequential positional rules are the iterative positional rules, where at each step the scoring vector changes only with respect to the number of alternatives. More formally, if at each step, ↵ |B| is the |B|-tuple (1, 0, ..., 0) then it is Hare's Procedure denoted F

↵ A 0 . Likewise if at each step, ↵ |B| is the |B|-tuple ↵ = (1, ..., 1, 0) or ↵ = (1, |B| 2 |B| 1 , ..., 1 |B| 1 , 0), then we obtain Coombs' Procedure denoted F ↵ A 1 and Nanson's Procedure denoted F ↵ A 2 , respectively.
It should be also noted that alternatives are not removed one after the other if several of them have the worst score. They should be removed all together. Furthermore, if all alternatives have the same score at a given step, then there is no elimination: all the alternatives are selected.

We can now define the q Condorcet consistency principle. Definition 5. Given a profile R, a rational number q, an alternative a h 2 A is q-majority preferred to an alternative a

j 2 A iff |{i 2 N : a h R i a j }| q.n, with q 2 ⇤ 1 2 , 1
⇤ . a j is said to be q-majority beaten by a h . In this paper we assume that n is large enough such that for all rational number k, k.n is an integer. 4Let C q (R) , the q Condorcet majority set, defined as the set of alternatives in A which are not q majority beaten by any other alternative in A.

It is well known from Ferejohn and Grether (1974) that a necessary and sufficient condition under which C q (R) 6 = ; for all R is that q > k 1 k .

Definition 6. Given a rational number q 2

⇤ 1 2 , 1 ⇤ , a SCC F satisfies the q Condorcet consistency (q CC ) principle if F (R) ✓ C q (R)
for any profile R. Our main objective is then to determine conditions on q that ensure that usual PR and SPR satisfy q CC.

Simple Positional rules

Usual procedures

We will first present results for the three usual simple positional rules, i.e. plurality, negative plurality and Borda.

The following result completely solves the plurality case.

Theorem 1. Let A = {a 1 , ..., a k }, the scoring vector ↵ = (1, 0, ..., 0). Let q 2

⇤ 1 2 , 1 ⇤ . F ↵ 0 satisfies q-CC if and only if q > k 1 k .
Proof. 1) We know by [START_REF] Ferejohn | On a class of rational social decision procedures[END_REF] that if q  k 1 k there exists a profile R such that C q (R) is empty. For any such profile R, F ↵ 0 (R) is q-majority beaten (is not included in C q (R)) and thus F ↵ 0 does not satisfies q-CC. 2) Conversely, assume that q > k 1 k . In order to show that F ↵ 0 satisfies q-CC, it is enough to show that if R is a profile for which a 1 is q-majority beaten by (say) a 2 then a 1 / 2 F ↵ 0 (R). Since a 1 is q-majority beaten by a 2 , we have |S| qn where S = {i 2 N : a 2 R i a 1 }. Since the scoring vector is ↵ = (1, 0, ..., 0) : |S| qn implies Sc(A, a 1 , R, ↵)  n qn = (1 q)n.

Let a max be a candidate such that Sc(A, a max , R, ↵) = max 2jk Sc(A, a j , R, ↵).

Since k P j=2 Sc(A, a j , R, ↵) qn we have Sc(A, a max , R, ↵) qn k 1 . Thus, Sc(A, a max , R, ↵) Sc(A, a 1 , R, ↵) n( q k 1 (1 q)) = n( k k 1 q 1) > 0 because q > k 1 k , and hence a 1 / 2 F ↵ 0 (R).
This ends the proof. The answer of our main question is given below for the negative plurality rule. Theorem 2. Let A = {a 1 , ..., a k }, the scoring vector ↵ = (1, 1, ..., 1, 0). For all q 2

⇤ 1 2 , 1 ⇤ , F ↵ 1
does not satisfies q-CC.

Proof. Let q 2 ⇤ 1 2 , 1 ⇤ : To prove that F ↵ 1 does not satisfies q-CC, we shall determine a profile R for which a winner, according to F ↵ 1 is q-majority beaten. For that, consider the profile R in which each individual i has the preference R i defined as follows :

a 2 R i a 1 R i a 3 R i a 4 ...R i a k 1 R i a k It is obvious that F ↵ 1 (R) = {a 1 , ..., a k 1 } because ⇢ 8j = 1, ..., k 1, Sc(A, a j , R, ↵) = n Sc(A, a k , R, ↵) = 0 .
The candidate a 1 is q-majority beaten (everybody prefers a 2 to a 1 ) meanwhile a 1 2 F ↵ 1 (R). As [START_REF] Baharad | The Borda rule, Condorcet consistency and Condorcet stability[END_REF], we now solve the Borda case (with a slightly different proof).

Theorem 3. Let A = {a 1 , ..., a k }, the scoring vector ↵ = (1, k 2 k 1 , ..., 1 k 1 , 0). Let q 2 ⇤ 1 2 , 1 ⇤ . F ↵ 2 satisfies q-CC if and only if q > k 1 k .
Proof. 1) Again, it is obvious that if q  k 1 k then F ↵ 2 does not satisfies q-CC property. 2) Conversely, assume that q > k 1 k . In order to show that F ↵ 2 satisfies q-CC, it is enough to show that if R is a profile for which a 1 is q-majority beaten by a 2 then a 1 / 2 F ↵ 2 (R). Since a 1 is q-majority beaten by a 2 , we have |S| qn where S = {i 2 N :

a 2 R i a 1 }. Furthermore, ⇢ ↵ r(A,a 2 ,R i ) ↵ r(A,a 1 ,R i ) 1 k 1 for all i 2 S and ↵ r(A,a 2 ,R i ) ↵ r(A,a 1 ,R i ) 1 for all i 2 S c . Sc(A, a 2 , R, ↵) Sc(A, a 1 , R, ↵) = P i2S (↵ r(A,a 2 ,R i ) ↵ r(A,a 1 ,R i ) ) + P i2S c (↵ r(A,a 2 ,R i ) ↵ r(A,a 1 ,R i ) ) 1 k 1 |S| |S c | qn 1 k 1 (1 q)n = n(( 1 k 1 + 1)q 1) = n( k k 1 q 1) > 0 (because q > k 1 k ). Hence a 1 / 2 F ↵ 2 (R).
This ends the proof.

General Case

The aim of this section is to identify the conditions on the quota q under which a given PR satisfies q CC.

A sufficient condition.

We will first introduce the following proposition giving a sufficient condition under which winners for a given simple positional rule are never q-majority beaten.

For any scoring vector ↵ = (↵

= (↵ 1 , ↵ 2 , ..., ↵ k ) with ↵ 1 = 1, ↵ k = 0 and q 2 ⇤ 1 2 , 1 ⇤ . If q > 1 1 + ↵ , then F ↵ satisfies q-CC. Proof. Let ↵ = (↵ 1 , ↵ 2 , ..., ↵ k ) and q 2 ⇤ 1 2 , 1 ⇤ such that q > 1 1+↵
. In order to prove that F ↵ satisfies q-CC it is enough to show that for any profile R for which a 1 is q-majority beaten by a 2 , a 1 / 2 F ↵ (R). Let R be such a profile : then |S| qn where S = {i 2 N :

a 2 R i a 1 }. Sc(A, a 2 , R, ↵) = P i2N ↵ r(A,a 2 ,R i ) = P i2S ↵ r(A,a 2 ,R i ) + P i2S c ↵ r(A,a 2 ,R i ) and Sc(A, a 1 , R, ↵) = P i2N ↵ r(A,a 1 ,R i ) = P i2S ↵ r(A,a 1 ,R i ) + P i2S c ↵ r(A,a 1 ,R i ) ; thus Sc(A, a 2 , R, ↵) Sc(A, a 1 , R, ↵) = P i2S (↵ r(A,a 2 ,R i ) ↵ r(A,a 1 ,R i ) ) + P i2S c (↵ r(A,a 2 ,R i ) ↵ r(A,a 1 ,R i ) ). Since a 2 R i a 1 for all i 2 S, we have ↵ r(A,a 2 ,R i ) ↵ r(A,a 1 ,R i )
↵ for all i 2 S. On the other hand, for i / 2 S, ↵

r(A,a 2 ,R i ) ↵ r(A,a 1 ,R i ) 1. Finally, Sc(A, a 2 , R, ↵) Sc(A, a 1 , R, ↵) = P i2S (↵ r(A,a 2 ,R i ) ↵ r(A,a 1 ,R i ) ) + P i2S c (↵ r(A,a 2 ,R i ) ↵ r(A,a 1 ,R i ) ) ↵|S| |S c | qn↵ (1 q)n = n((1 + ↵)q 1) > n((1 + ↵) ⇥ 1 1+↵ 1) (because q > 1 1+↵ ) = 0. Since Sc(A, a 2 , R, ↵) Sc(A, a 1 , R, ↵) > 0, it follows that a 1 / 2 F ↵ (R)
and this ends the proof.

3.2.2

A necessary and sufficient condition: the particular three alternative case.

Let A = {a 1 , a 2 , a 3 } and a scoring vector

↵ = (↵ 1 , ↵ 2 , ↵ 3 ) = (1, , 0) with 2 [0, 1]
. The cases = 0, = 1 2 and = 1 are already solved : next we consider the two following cases: > 1 2 and < 1 2 .

The case > 1 2 is handled in the following result.

Proposition 2. Let A = {a 1 , a 2 , a 3 } and let ↵ = (1, , 0) with > 1 2 , F ↵ the simple positional rule associated with ↵ and q 2

⇤ 1 2 , 1 ⇤ . F ↵ satisfies q-CC if and only if q > 1 2 . Proof. Let ↵ = (1, , 0) with > 1 2 . Then ↵ = 1
and therefore 1 1+↵ = 1 2

. Thanks to proposition 1, if q > 1 2

, then F ↵ satisfies q-CC.

Conversely, assume that q  1 2 . To show that F ↵ does not satisfies q-CC, consider the following profile R in which: ⇢ qn individuals have preference a 2 R i a 1 R i a 3

(1 q)n have preference a 1 R i a 3 R i a 2 For the profile R so defined, a 1 is q-majority beaten by a 2 . However let us compute the scores:

we have : 21)q + 1 ) > 0 because 2 1 > 0 and 1 > 0 It then follows that a 1 2 F ↵ (R) and hence, F ↵ does not satisfy q-CC. The following result deals with the case < 1 2 .

8 < : Sc(A, a 1 , R, ↵) = qn + (1 q)n Sc(A, a 2 , R, ↵) = qn and Sc(A, a 3 , R, ↵) = (1 q)n Sc(A, a 1 , R, ↵) Sc(A, a 2 , R, ↵) = qn + (1 q)n qn = n(( 2)q + 1) = n((2 )q 1) 0 because q  1 2 Sc(A, a 1 , R, ↵) Sc(A, a 3 , R, ↵) = qn + (1 q)n (1 q)n = n( q + 1 q + q) = n((
Proposition 3. Let A = {a 1 , a 2 , a 3 } and let ↵ = (1, , 0) with < 1 2 , F ↵ the simple positional rule associated with ↵ and q 2 ⇤ 1 2 , 1 ⇤ .

F

↵ satisfies q-CC if and only if q > 2 3

.

Proof. 1) By [START_REF] Ferejohn | On a class of rational social decision procedures[END_REF], it is obvious that if q  2 3 then F ↵ does not satisfies q-CC.

2) Conversely, let q > 2 3 . In order to prove that F ↵ satisfies q-CC, we will show that for any profile R for which a 1 is q majority beaten by a 2 , a 1 / 2 F ↵ (R). Let R be such a profile. Assume on the contrary that a 1 2 F ↵ (R). There exists a subset S such that |S| = qn and a 2 R i a 1 for all i 2 S. Let ✓ be the proportion of individuals in S holding preference a 2 R i a 1 R i a 3 . With no loss of generality, we can then assume that in S: ⇢ ✓n individuals have preference a 2 R i a 1 R i a 3 and

(q ✓)n individuals have preference a 3 R i a 2 R i a 1 with 0  ✓  q.
The score of a 1 is bounded above by ✓n + (1 q)n and furthermore, the value ✓n + (1 q)n is obtained if and only if every individual in S c ranks a 1 at the first position. Now let be the proportion of individuals in S c with preference

a 1 R i a 3 R i a 2 .
With no loss of generality, we can then assume that in S c :

⇢ n individuals have preference a 1 R i a 3 R i a 2 and
(1 q

)n individuals have a 1 R i a 2 R i a 3 with 0   1 q.
At this level we will distinguish two cases : = 1 q and < 1 q :

First case : = 1 q

In this case,

<

:

Sc(A, a 1 , R, ↵) = ✓n + (1 q)n = n( ✓ q + 1) Sc(A, a 2 , R, ↵) = ✓n + (q ✓)n = n((1 )✓ + q) Sc(A, a 3 , R, ↵) = (q ✓)n + (1 q)n = n( ✓ + (1 )q + ) . If a 1 2 F ↵ (R) then : ⇢ Sc(A, a 1 , R, ↵) Sc(A, a 2 , R, ↵) 0 and Sc(A, a 1 , R, ↵) Sc(A, a 3 , R, ↵) 0 ) ⇢ ( 2 1
)✓ (1 + )q + 1 0 (1) and 1) with ( 1)

(1 + )✓ + ( 2 + )q + (1 ) 0 (2) (1) ) (2 1)✓ (1 + )q 1 ) ✓  1 1 2 [ (1 + )q + 1] (2) ) (2 )q  (1 + )✓ + (1 ) ) (2 )q  (1 + ) 1 1 2 [ (1 + )q + 1] + (
) (2 )q (1 )  1+ 1 2 [ (1 + )q + 1] ) (1 2 )(2 )q (1 )(1 2 )  (1 + ) 2 q + (1 + ) ) (3 2 3 + 3)q  2 2 2 + 2 ) 3q  2 because 3 2 3 + 3 > 0. a contradiction since q > 2 3 . Second case : < 1 q Assume that a 1 2 F ↵ (R) : then Sc(A, a 1 , R, ↵) Sc(A, a 2 , R, ↵) 0 and Sc(A, a 1 , R, ↵) Sc(A, a 3 , R, ↵) 0. 8 < : Sc(A, a 1 , R, ↵) = ✓n + (1 q)n = n[ ✓ + (1 q)] Sc(A, a 2 , R, ↵) = n[✓ + (q ✓) + (1 q )] = n[(1 )✓ + ] Sc(A, a 3 , R, ↵) = (q ✓)n + n = n[ ✓ + q + ] .
As Sc(A, a 1 , R, ↵) Sc(A, a 2 , R, ↵) 0 and Sc(A, a 1 , R, ↵) Sc(A, a 3 , R, ↵) 0, we have:

⇢ ( 2
1)✓ q + 1 + 0 ( + 1)✓ 2q + 1 0 ) ⇢ (1 2 )✓ + q + 1 ( + 1)✓ 2q + 1 (⇤) ) (1 2 )✓ + q + 1   ( + 1)✓ 2q + 1 ) (1 2 )✓ + q + 1  ( + 1)✓ 2q + 1 ) (1 2 1)✓  3q + 2 ) 3 ✓  (3q + 2) that is, ✓ 1 3 (3q + 2)(⇤⇤).
On the other hand we have 0  < 1 q which implies q > (1 2 )✓ + q + 1 (thanks to (⇤)).

q > (1 2 )✓ + q + 1 ) ( 1)q + 1 > (1 2 ) 1 3 (3q + 2) (thanks to (⇤⇤)) ) 3 ( 1)q + 3 > 3q(1 2 ) + ( 12 )( 2)

) ( 3 2 3 3 + 6 )q > 2 2 2 + 4 3 ) 3q( 2 + 1) > 2( 2 + 1) ) 3q < 2 because 2 + 1 < 0 which is a contradiction since q > 2 3 .
To summarize, for

A = {a 1 , a 2 , a 3 }, ↵ = (1, , 0), let q ↵ = ⇢ 1 1+↵ if ↵ = 1 2 3 if ↵ = that is, q ↵ = ⇢ 1 2 if > 1 2 2 3 if < 1 2 .
Thanks to propositions 2 and 3 above, we can state the following result.

F

↵ satisfies q-CC if and only if q > q ↵ . We can remark that this result is consistent with the previous results for Borda, Plurality and Negative Plurality. Indeed when = 0 and = 1 2 , q ↵ = 2 3 , and when = 1, q ↵ = 1.

Sequential Positional Rules

We will present results in this section for the three usual SPR, i.e. Hare's Procedure (F

↵ A 0 ), Coombs' Procedure (F ↵ A 1 ) and Nanson's Procedure (F ↵ A 2 )
. Before presenting the results of this section, we recall that we assumed that n, the number of voters is large enough so that kn is an integer whenever k is a rational number.

The following result completely solves Hare's case.

Theorem 5. Let A = {a 1 , ..., a k }, and let ↵ = (1, 0, ..., 0) the scoring vector at each step. Let

q 2 ⇤ 1 2 , 1 ⇤ . Then F ↵ A 0 satisfies q-CC if and only if q > (1 1 2 k 1 ) 1 n .
Proof. First we will show that if q  (1

1 2 k 1 ) 1 n then F ↵ A
0 does not satisfy q-CC. We then need to construct a profile R such that (say) a 1 2 F ↵ A 0 (R) meanwhile a 1 is q-majority beaten by a 2 . Let ✓ = n 2 k 1 and consider the following profile :

✓ + 1 individuals : a 1 R i a k R i a k 1 R i ...R i a 2 ✓ : a 2 R i a 1 R i a k R i a k 1 R i ...R i a 3 2✓ : a 3 R i a 2 R i a 1 R i a k R i a k 1 R i ...R i a 4 2 2 ✓ : a 4 R i a 3 R i a 2 R i a 1 R i a k R i a k 1 R i ...R i a 5 ... : 2 k 4 ✓ : a k 2 R i a k 3 R i ...R i a 2 R i a 1 R i a k R i a k 1 2 k 3 ✓ 1 : a k 1 R i a k 2 R i ...R i a 2 R i a 1 R i a k 2 k 2 ✓ : a k R i a k 1 R i a k 2 R i ...R i a 2 R i a 1
With respect to R a 1 is q-majority beaten by a 2 . Indeed, the number of voters who prefer a 2 to a 1 is

✓ + 2✓ + 2 2 ✓ + ... + 2 k 3 ✓ 1 + 2 k 2 ✓ = ✓(2 k 1 1) 1 = n[(1 1 2 k 1 ) 1 n ] qn since q  (1 1 2 k 1 ) 1 n .
Then a 1 is q majority beaten by a 2 . Now let us show that a 1 2 F

↵ A 0 (R). Let L(A t , R, ↵ |At|
) be the set of losing candidates at step t, we have F

↵ A 0 (R) = A\ p S t=1 L(A t , R, ↵ |At|
) where p is the number of steps. The scoring vector at any step t is the

|A t |-tuple (1, 0, 0, ..., 0). From the definition of R it is obvious that Sc(A 1 , a 2 , R, ↵ |A 1 | ) = ✓ < Sc(A 1 , a i , R, ↵ |A 1 | ) for all i 6 = 2; thus L(A 1 , R, ↵ |A 1 | ) = {a 2 }. Note that Sc(A 2 , a 1 , R, ↵ |A 2 | ) = ✓ + ✓ + 1 = 2✓ + 1 whereas Sc(A 2 , a 3 , R, ↵ |A 2 | ) = 2✓. It can be easily seen that : L(A 2 , R, ↵ |A 2 | ) = {a 3 }, L(A 3 , R, ↵ |A 3 |
) = {a 4 }, and so on and

L(A k 2 , R, ↵ |A k 2 | ) = {a k 1 }. Finally, at the last step, a 1 is pitted against a k . Sc(A k 1 , a 1 , R, ↵ |A k 1 | ) = ✓ + ✓ + 2✓ + ... + 2 k 3 ✓ = (2 + 2 1 + ... + 2 k 3 )✓ = 2 k 2 ✓ and Sc(A k 1 , a k , R, ↵ |A k 1 | ) = 2 k 2 ✓ = Sc(A k 1 , a 1 , R, ↵ |A k 1 | ) thus, F ↵ A 0 (R) = {a 1 , a k }.
Conversely, assume that q > 1

1 2 k 1 1 n , that is, qn > n(1 1 2 k 1 ) 1 or qn n(1 1 2 k 1 )(⇤)
Let us show that F ↵ A 0 (R) satisfies q-CC. For that, let R be a profile for which a 1 is q-majority beaten by a 2 and a 1 2

F ↵ A 0 (R).
Assume that for the profile R, there are p steps and that the set of losing candidates are respectively

L(A 1 , R, ↵ |A 1 | ), L(A 2 , R, ↵ |A 2 | ), ... and L(A p , R, ↵ |Ap|
) and the set of winners is

F ↵ A 0 (R) = A r p S j=1 L(A j , R, ↵ |A j | ). Let n j be the cardinality of L(A j , R, ↵ |A j |
) and r + 1 the cardinality of

F ↵ A 0 (R). (If r = 0 then a 1 is the only winner).
Since a 1 is q-majority beaten by a 2 ,

Sc(A 1 , a 1 , R, ↵ |A 1 | )  (1 q)n.
As n 1 candidates are eliminated at the first step, we have

Sc(A 1 , a h , R, ↵ |A 1 | ) < Sc(A 1 , a 1 , R, ↵ |A 1 | )  (1 q)n 8a h 2 L(A 1 , R, ↵ |A 1 |
) and thus, P

a h 2L(A 1 ,R,↵ |A 1 | ) Sc(A 1 , a h , R, ↵ |A 1 |
) < n 1 (1 q)n, therefore at the second step,

Sc(A 2 , a 1 , R, ↵ |A 2 | ) < (1 q)n + n 1 (1 q)n = (1 + n 1 )(1 q)n. Likewise, since candidates in L(A 2 , R, ↵ |A 2 |
) are eliminated at step 2, we have

Sc(A 2 , a r , R, ↵ |A 2 | ) < (1 + n 1 )(1 q)n 8a r 2 L(A 2 , R, ↵ |A 2 |
) and therefore

P ar2L(A 2 ,R,↵ |A 2 | ) Sc(A 2 , a, R, ↵ |A 2 | ) < n 2 (1 + n 1 )(1 q)n. We deduce that Sc(A 3 , a 1 , R, ↵ |A 3 | ) < (1 + n 1 )(1 q)n + n 2 (1 + n 1 )(1 q)n = [(1 + n 2 )(1 + n 1 )] (1 q)n. At the last step, after the elimination of L(A 1 , R, ↵ |A 1 | ), L(A 2 , R, ↵ |A 2 |
), ... and L(A p , R, ↵ |Ap| ), we have:

Sc(A p , a 1 , R, ↵ |Ap| ) < [(1 + n p )(1 + n p 1 )...(1 + n 2 )(1 + n 1 )
] (1 q)n. At the end, all the candidates in F ↵ A 0 (R) have the same score say s ⇤ , implying that (r+1)s ⇤ = n. However, since a 1 2 F

↵ A 0 (R), s ⇤ should be equal to Sc(A p , a 1 , R, ↵ |Ap| ). Finally, n = (r + 1)s ⇤ = (r + 1)Sc(A p , a 1 , R, ↵ |Ap| ) < (1 + r)(1 + n p )(1 + n p 1 )...(1 + n 2 )(1 + n 1 )(1 q)n note that for all nonnegative integer m, 1 + m  2 m  2 r+np+n p 1 +...+n 1 (1 q)n = 2 k 1 (1 q)n because (1 + r) + (n p ) + .... + (n 1 ) = k  2 k 1
( 1 2 k 1 )n = n (thanks to (⇤)) This is a contradiction. Conclusion : we cannot have a 1 q majority beaten and a 1 2

F ↵ A 0 (R).
The following result deals with Coombs' procedure. Theorem 6. Let A = {a 1 , ..., a k }, and let ↵ = (1, 1, ...1, 0) the scoring vector at each step. Let

q 2 ⇤ 1 2 , 1 ⇤ . F ↵ A 1 satisfies q-CC if and only if q > k 1 k .
Proof. 1) By [START_REF] Ferejohn | On a class of rational social decision procedures[END_REF] it is obvious that if

q  k 1 k , F ↵ A
2) It then suffices to prove that if q > k 1 k then for any R for which a 1 is q-majority beaten by

a 2 , a 1 / 2 F ↵ A 1 (R).
Let R be such a profile. Assume the contrary : a 1 2 F ↵ A 1 (R). Since a 1 is q-majority beaten by a 2 , we have |S| qn where S = {i 2 N : a 2 R i a 1 }. Recall that at any step t in which the set of alternatives is A t , the scoring vector is the |A t |-tuple (1, 1, ...1, 0). Assuming that there are p steps and that L(A t , R, ↵ |At| ) is the set of eliminated candidates at step t, we have F

↵ A 1 (R) = A \ p S t=1 L(A t , R, ↵ |At|
) . We will prove that if a 1 2 F

↵ A 1 (R) then a 2 2 F ↵ A 1 (R).
We will then show that at any step t, if

a 1 / 2 L(A t , R, ↵ |At| ) then a 2 / 2 L(A t , R, ↵ |At|
). Consider a step t and assume, with no loss of generality that v (v > 0) candidates have so far been eliminated with a 1 / 2 L(A t , R, ↵ |At| ). v is the cardinality of

t 1 S h=1 L(A h , R, ↵ |A h |
) Let a 0 be a candidate such that :

Sc(A t , a 0 , R, ↵ |At| ) = min ⇢ Sc(A t , a j , R, ↵ |At| ) : a j 2 A t = A \ t 1 S h=1 L(A h , R, ↵ |A h |
) . As A t has exactly k v candidates and the scoring vector is ↵ |At| = (1, 1, ..., 1, 0), we have : = n(k µ 1). Note that there is at least two alternatives in

P a h 2At Sc(A t , a h , R, ↵ |At| ) = n(k v 1). By the definition of a 0 , it holds Sc(A t , a 0 , R, ↵ |At| )  Sc(A t , a h , R, ↵ |At| ) for all a h 2 A t . This implies that (k v)Sc(A t , a 0 , R, ↵ |At| )  P a h 2At Sc(A t , a h , R, ↵ |At| ), that is, Sc(A t , a 0 , R, ↵ |At| )  k v 1 k v n Since a 2 R i a 1 for all i 2 S, we have Sc(A t , a 2 , R, ↵ |At| ) qn > k 1 k n Sc(A t , a 2 , R, ↵ |At| ) Sc(A t , a 0 , R, ↵ |At| ) > k 1 k n k v 1 k v n = v k(k v) 0 which means that a 2 / 2 L(A t , R, ↵ |At| ). We have just proved that at each step t, if a 1 / 2 L(A t , R, ↵ |At| ) then a 2 / 2 L(A t , R, ↵ |At| ). This means that if a 1 2 F ↵ A 1 (R) then a 2 2 F ↵ A 1 (R). Let k µ = |F ↵ A 1 (R)|
F ↵ A 1 (R), since a 1 2 F ↵ A 1 (R) and therefore a 2 2 F ↵ A 1 (R). We should have Sc(A p , a 2 , R, ↵ |Ap| ) = s ⇤ and again Sc(A p , a 2 , R, ↵ |Ap| ) |S| since 8i 2 S, a 2 R i a 1 . Therefore, (k µ)s ⇤ (k µ)|S| > (k µ) k 1 k n (k µ)s ⇤ > (k µ) k 1 k n ) n(k µ 1) > (k µ) k 1 k n ) k(k µ) k > k(k µ) (k µ) ) k > (k µ) which is a contradiction. We conclude that a 1 / 2 F ↵ A 1 (R
t . Let q 2] 1 2 , 1]. Then F ↵ A 2 satisfies q-CC if and only if q > k 1 k . Proof. 1) Once again, it is obvious that if q  k 1 k , F ↵ A
2 does not satisfies q-CC.

2) It suffices to prove that if q > k 1 k then for any R for which a 1 is q-majority beaten by a 2 ,

a 1 / 2 F ↵ A 2 (R). Since a 1 is q-majority beaten
⇢ ↵ r(At,a 2 ,R i ) ↵ r(At,a 1 ,R i ) 1 k 1 for all i 2 S and ↵ r(At,a 2 ,R i ) ↵ r(At,a 1 ,R i )
1 for all i 2 S c . Thus,

Sc(A t , a 2 , R, ↵ |At| ) Sc(A t , a 1 , R, ↵ |At| ) = P i2S (↵ r(At,a 2 ,R i ) ↵ r(At,a 1 ,R i ) ) + P i2S c (↵ r(At,a 2 ,R i ) ↵ r(At,a 1 ,R i ) ) |S| 1 k 1 |S c | = |S|( 1 k 1 + 1) n n( k k 1 q 1) since |S| qn > n( k k 1 k 1 k 1) = 0 since q > k

Conclusion

The question motivating this study is whether a larger majority (supra-majority) can ensure that positional rules (simple and sequential) satisfy a weaker version of the Condorcet consistency principle. The affirmative answer to this question is the main message of our analysis. Indeed, all usual positional rules, that is Plurality, Borda, Hare, Nanson and Coombs satisfy this principle. The only one which does not verifies it, is Negative Plurality. This is an interesting result, since none of these rules except Nanson satisfy Condorcet Consitency when the simple majority is required. This means that Condorcet's approach and Borda's approach are not so mutually incompatible. In this respect, our results can be seen as positive results. Moreover we give the precise condition on the majority (on the quota) needed to ensure that this rules satisfies the q Condorcet consistency principle. Our results show that in general, the principle is verify as soon as the quota is greater than k 1 k . This is true for Plurality, Borda, Nanson and Coombs. This result is interesting since this is also the quota which guarantees that a rule associated with this quota always select an alternative, as established by [START_REF] Ferejohn | On a class of rational social decision procedures[END_REF]. Regarding Hare, the quota of (1

1 2 k 1 ) 1
n is greater than the previous one, which suppose that this is more difficult with Hare to respect q Condorcet Consistency.

We also consider the case of all simple positional rules. However our study is limited to the three alternative case. It appears indeed that the issue of characterizing quota under which a given rule satisfies our consistency property is a difficult task. We do not try to solve the problem for general sequential positional rules since it would require to define what is the scoring vectors at each step of the process.

Finally, it is worth noting that it may seems appropriate to extend our results by evaluating the propensitivity of positional rules to violate this majority condition when the quota is not achieved. This is a very common approach in the context of simple majority. That is why it can be interesting to apply it in the context of supra-majority.

Theorem 4 .

 4 Let A = {a 1 , a 2 , a 3 }, and let ↵ = (1, , 0), F ↵ the simple positional rule associated with ↵ and q 2

  which means that at the end µ candidates have been eliminated. As all candidates in F ↵ A 1 (R) have the same score say s ⇤ , it holds (k µ)s ⇤

  ). The last result solves Nanson's rule.

	Theorem 7. Let A = {a 1 , ..., a t where the set of alternatives is A k }, and let ↵ = (1, |At| 2 |At| 1 , ... 1 |At| 1 , 0) the scoring vector at each step

  by a 2 , we have |S| qn where S = {i 2 N : a 2 R i a 1 }. Recall that at any step t in which the set of alternatives is A t , the scoring vector is the |A Now consider a given step t such that a 1 , a 2 2 A

	(1, |At| 2 |At| 1 , ... 1 |At| 1 , 0). Assuming that there are p steps and that L(A t , R, ↵ |At| t, we have F ↵ A t=1 2 (R) = A \ p S L(A t , R, ↵ |At| ).	t |-tuple ) is the set of losing candidates at step
	In order to prove a 1 / 2 F to A t , we have Sc(A t , a 2 , R, ↵ |At| ↵ A 2 (R), it suffices to show that at any step t whenever a 1 and a 2 belong ) > Sc(A t , a 1 , R, ↵ |At| ).

t :

We have

  At a given step t 2 {1, 2, ..., p 1}, if a 1 , a 2 2 A At the last step p, we cannot have both a 1 and a 2 in F

	exactly the same score, hence a 1 / 2 F	↵ A 2 (R).	↵ A 2 (R) since all candidates in F	↵ A 2 (R) have

1 k which means that Sc(A t , a 2 , R, ↵ |At| ) > Sc(A t , a 1 , R, ↵ |At| ). t then Sc(A t , a 2 , R, ↵ |At| ) > Sc(A t , a 1 , R t , ↵ |At|

).

We assume in this paper that individual preferences are strict.

See section 2 for the recall of this result.

This well known concept is largely study in the literature with a remarkable result due to[START_REF] Nakamura | The vetoers in a simple game with ordinal preferences[END_REF].

This assumption aims at simplifying our proofs. One could also assume that there is a continuum of voters.

does not satisfies q-CC.


Sébastien Courtin

Mathieu Martin

Issofa Moyouwou

The q-Condorcet efficiency of positional rules

Keywords: Positional rules (Simple and Sequential), Condorcet efficiency, q-majority JEL Classification D71,D72

According to a given quota q, a candidate a is beaten by another candidate b if at least a proportion of q individuals prefer b to a. The q-Condorcet efficiency of a voting rule is the probability that the rule selects a q-Condorcet winner (q-CW ), that is any candidate who is never beaten under the q-majority. Closed form representations are obtained for the q-Condorcet efficiency of positional rules (simple and sequential) in three-candidate elections. This efficiency is significantly greater for sequential rules than for simple positional rules.

Introduction

In voting theory, the Condorcet winner is any candidate that would be able to defeat each of the other candidates in a series of pairwise majority comparisons. A Condorcet voting rule selects a Condorcet winner (CW ), whenever one exists. While it is very appealing for a voting rule to select a CW when one exists, another famous class of voting rules, the positional rules, lacks to satisfy this requirement (Condorcet, 1785). This is certaintly a failure of the positional approach.

However, this negative point of view can be contrasted. By computing the probability that a voting rule selects the Condorcet winner, one can check whether such a phenomenon is sufficiently rare to be ignored or not. In the context of the majority rule, this approach has been particularly studied by Gehrlein and Lepelley (2006) [START_REF] Courtin | Positional rules and q-Condorcet consistency[END_REF] . Under the majority rule a candidate a is preferred to a candidate b if the total number of voters who prefer a to b is greater than the total number of voters who prefer b to a. In this paper, we aim to extend Gehrlein and Lepelley analysis to qualified majorities. Although a simple majority is the rule most often used, qualified majorities are also common in actual parliaments on important constitutional issues.

According to a given quota q, a candidate a is beaten by a candidate b if at least a proportion of q individuals prefer b to a. Following the terminology of Baharad and Nitzan (2003) et al. (2012), the q-Condorcet winner (q-CW ) is the candidate who is never beaten under the q-majority. For a set of positional rules, Courtin et al. (2012) provide a necessary and sufficient condition on the quota for the winner of the election not to be beaten under the q-majority. For each voting rule considered2 , they provide the lower bound of the quota (q ⇤ ) which guarantees that a q-CW is always selected, whenever one exists. Indeed, the threshold q ⇤ is such that: a) for any quota q less than or equal to q ⇤ , there always exists a profile of individual preferences for which the winner of the positional rule is beaten under the q-majority; and b) for any quota q greater than q ⇤ , the winner of the positional rule is never beaten under the q-majority.

In this paper, along the line of Gehrlein and Lepelley (2006), we evaluate the propensity of positional rules to select the q-CW when the quota is not achieved. This entails computing the probability (hereafter called q-Condorcet efficiency) that a voting rule selects the q-CW . We know from Courtin et al. (2012) that given a positional rule, the q-Condorcet efficiency is equal to one for any quota q greater than q ⇤ , whereas the pioneering work of Gehrlein and Lepelley (2006) summarizes the result for simple majority. Our purpose is then to fill the gap for [START_REF] Courtin | Positional rules and q-Condorcet consistency[END_REF] 2 < q < q ⇤ . For three-candidate elections, the q-Condorcet efficiency is evaluated for a wide class of positional rules (simple and sequential). We observe that the q-Condorcet efficiency is sometimes very low for some simple positional rules. This efficiency is significantly greater for sequential rules than for simple positional rules.

The remainder of the paper is organized as follows: Section 2 is a presentation of the general framework with notation and definitions. Section 3 and 4 provide computations for the simple positional rules (PR) and the sequential positional rules (SPR) respectively. Section 5 concludes the paper.

Notation and definitions

We consider an election with three candidates (a, b, c) and n voters who have preferences represented by linear orders (indifference is not allowed). The six possible preference rankings are given by In the present paper, we focus our attention on the simple positional rules (PR) and the sequential positional rules (SPR). We assume that each individual gives 1 point to the candidate ranked first in his preferences, a weight of ↵ points (0  ↵  1) to the candidate ranked second and 0 points to the last candidate.

In a PR, a winner is any candidate who receives the largest number of points3 . For instance, the candidate a is a winner if

n 1 + n 2 + ↵(n 3 + n 5 ) n 3 + n 4 + ↵(n 1 + n 6 ) and n 1 + n 2 + ↵(n 3 + n 5 ) n 5 + n 6 + ↵(n 2 + n 4 )
. Three particular PRs are well-known in the literature: plurality rule (↵ = 0), negative plurality rule (↵ = 1) and Borda rule (↵ = [START_REF] Courtin | Positional rules and q-Condorcet consistency[END_REF] 2 ). The PR that corresponds to the weight ↵ is denoted F ↵ .

In a SPR, there are two steps. The candidate who obtains the smallest number of points is first eliminated [START_REF] Gehrlein | Voting paradoxes and group coherence: the Condorcet efficiency of voting rules[END_REF] . The preferences concerning the two other candidates are not changed. A majority comparison gives the winner at the second step. For instance, if 2 ). The SPR that corresponds to the weight ↵ is denoted F ↵ .

n 1 + n 2 + ↵(n 3 + n 5 ) < n 3 + n 4 + ↵(n 1 + n 6 ) and n 1 + n 2 + ↵(n 3 + n 5 ) < n 5 + n 6 + ↵(n 2 + n 4 ), then a is eliminated at the first step. If n 1 + n 3 + n 4 > n 2 + n 5 + n 6 ,
A candidate x is beaten under a q-majority by a candidate y if the number of individuals who prefer y to x is greater than or equal to qn, with 1 2 < q  15 . Given a PR or a SPR, Courtin et al. (2012) determine the smallest values q ⇤ for which no candidate in the winning set is beaten under the q-majority. They show that there always exists a profile of individual preferences at which a candidate in the winning set is q-majority beaten whenever 1/2 < q < q ⇤ . In order to compute the q-Condorcet efficiency, some probabilistic assumptions must be made regarding the likelihood that various profiles are observed. The impartial anonymous culture (IAC ) is one of the most used probabilistic models in the literature [START_REF] Regenwetter | Behavioral social choice[END_REF] . Under the IAC assumption, all anonymous profiles are equally likely to be observed. The q-Condorcet efficiency under IAC is then the ratio number of all anonymous profiles at which no candidate in the winning set is beaten under the q majority total number of all possible anonymous profiles It is worth noting that the q-Condorcet efficiency considered in this paper is slightly different from the one used by Gehrlein and Lepelley (2006). In fact, the (conditional) Condorcet efficiency by Gehrlein and Lepelley is the conditional probability that a positional rule will elect the CW , when one exists. We compute the probability that a positional rule selects a q-CW . By so doing we aim to highlight the concordance of the two main social choice approaches, namely the positional approach and the Condorcet approach. Note that to obtain the conditional version of our q-Condorcet efficiency, one only needs to divide our results by the probability that a q-CW exists.

To evaluate the q-Condorcet efficiency of each positional rule under study, we first have a typology of various voting situations for which no candidate in the winning set is beaten under the q-majority. These voting situations are completely described by a set of linear inequalities (technicalities are available from the authors upon simple request). From this typology, by the use of computerized evaluation processes, we obtain various results measuring the q-Condorcet efficiency of each voting rule under consideration. The computer evaluation process is based on the same technique whose origins are in Gehrlein and Fishburn (1976) but are more recently based on Ehrhart polynomials (see Lepelley et al. 2008).

Also note that in order to derive exact representations for a fixed size n of the electorate, computations will be performed only on integer variables. Thus we have to rewrite all the initial constraints that involve the term qn which may not be integer. Then given the size n of the electorate and the parameter q of the majority, a new parameter p has been introduced to allow integer computerized evaluation; that is p = dqne 1 where dye is the smallest integer greater than or equal to y.

The q-Condorcet efficiency for a given simple positional rule ↵, a given n and a given q, will be denoted CE(F ↵ , n, q), while the q-Condorcet efficiency for a given sequential positional rule ↵, n and q, will be denoted CE(F ↵ , n, q).

Simple Positional rules

Three usual PRs are under consideration here: plurality (↵ = 0), negative plurality (↵ = 1) and Borda (↵ = [START_REF] Courtin | Positional rules and q-Condorcet consistency[END_REF] 2 ). For each of the three rules, two series of results are provided: (i) the q-Condorcet efficiency in terms of n and q; and (ii) the q-Condorcet efficiency in terms of q as the size of the electorate tends to infinity 7 . More precisely, results for a finite number of voters will be given in terms of p instead of q; recall that p = dqne 1 and that

n 1 2  p  n 1 for 1 2 < q  1.

Plurality

Proposition 1 below provides exact representation of the q-Condorcet efficiency for the plurality rule.

Proposition 1. Let F 0 be the PR. If n is a multiple of 6, 8 and p 1 2 n with p = dqne 1, then

CE (F 0 , n, p) = 8 > > > > < > > > > : 9n 5 +( 320p 505)n 4 +(1680p 2 +2960p 915)n 3 +( 3240p 3 5040p 2 +7560p+3105)n 2 9(n+1)(n+2)(n+3)(n+4)(n+5) + (2700p 4 +3780p 3 11 340p 2 2340p+4266)n 810p 5 1080p 4 +5670p 3 +1080p 2 2700p+1080 9(n+1)(n+2)(n+3)(n+4)(n+5) if 1 2 n  p  2 3 n 1 if 2 3 n < p  n 1
For large electorates, that is when the total number of voters tends to infinity, p n tends to q. We then deduce the following result. Proposition 2. Let F 0 be the PR. Then for large electorates,

CE (F 0 , 1, q) = 8 > < > : 90q 5 + 300q 4 360q 3 + 560 3 q 2 320 9 q + 1 if 1 2 < q  2 3 1 if 2 3  q  1
We present in Table 1 some numerical values of the q-Condorcet efficiency of the plurality rule 9 with illustrations in Figure 1. 7 The same technique can be applied to derive more results in terms of the quota q given some other value of the weight ↵; or conversely other results in terms of the weight ↵ given some value of the quota q.

8 Data for other values of n are available from the authors upon simple request. 9 Note that for each table provided in this paper, 1 means that frequencies are almost 1, but not 1; and ✏ = 0.001. Fig. 1 q-Condorcet efficiency of the plurality rule

These results illustrate the following facts: (i) For large electorates, with only a probability of 83% the q-Condorcet efficiency of the plurality rule is small as q tends to 1 2 . In other words, for 17% of voting situations, a majority of voters prefer another candidate to the plurality winner.

(ii) The q-Condorcet efficiency increases as q increases and tends quickly to 1. The computed values in Table 1 indicate that the plurality rule always leads to the selection of a q-CW as soon as q > 2/3. This result is consistent with the general bound proposed by Courtin et al. (2012) which is k 1 k , when the total number of candidates is k. (iii) The variations of frequencies are relatively small as n increases.

Negative Plurality

The answer of our main question is given below for the negative plurality rule. Proposition 3. Let F 1 be the PR. If n is a multiple of 6, and p 1 2 n with p = dqne 1, then

CE (F 1 , n, p) = 8 > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > : 5[ 20n 5 +(200p+60)n 4 +( 816p 2 448p 500)n 3 +(1728p 3 +1440p 2 +2808p+612)n 2 ] 36(n+1)(n+2)(n+3)(n+4)(n+5) + 5[( 1080p 3 1728p 4 2592p 2 +144p+72)n+(648p 5 +81p 4 +1080p 3 +1620p 2 +2592p+864)] 36(n+1)(n+2)(n+3)(n+4)(n+5) if 1 2 n  p  2 3
n and p even

100n 5 +(1000p+300)n 4 ( 4080p 2 2240p 2500)n 3 +(8640p 3 +7200p 2 +14 040p+3060)n 2 36(n+1)(n+2)(n+3)(n+4)(n+5) + ( 8640p 4 5400p 3 12 960p 2 +3960p+6840)n+3240p 5 +405p 4 +5400p 3 +2430p 2 +1485 36(n+1)(n+2)(n+3)(n+4)(n+5) if 1 2 n  p  2 3
n and p odd

17n 5 +(90p 105)n 4 +( 180p 2 +480p 185)n 3 +(180p 3 720p 2 +810p 15)n 2 (n+1)(n+2)(n+3)(n+4)(n+5) + (480p 3 90p 4 810p 2 +480p+202)n+18p 5 120p 4 +270p 3 240p 2 +72p+120 (n+1)(n+2)(n+3)(n+4)(n+5) if 2 3 n < p  n 1
For a large electorates, we have the following results Proposition 4. Let F 1 be the PR. Then for large electorates, Fig. 2 q-Condorcet efficiency of the negative plurality rule

CE (F 1 , 1, q) = 8 > < > : 90q 5 240q 4 + 240q 3 340 3 q 2 + 250 9 q 25 9 if 1 2 < q  2 3 18q 5 90q 4 + 180q 3 180q 2 + 90q 17 if 2 3  q  1
Once again, frequencies are relatively constant when n increases and increase as q rises. Table 2 and Figure 2 show that no quota garantees the selection of a q-CW under the negative plurality rule. Indeed, for large electorate and when q tends to 1 2 , the q-CW is chosen for only 60% of the voting situations. A quota of at least 3 4 is needed for a q-Condorcet efficiency greater than 95%.

Borda rule

The following results deal with the Borda rule.

Proposition 5. Let F 2 be the PR. If n is a multiple of 1008 and p multiple of 336, with p = dqne 1, then CE (F 2 , n, p) = 8 > > > < > > > :

105n 5 +( 1440p 825)n 4 +(6480p 2 +5040p 1115)n 3 +( 12 960p 3 9720p 2 +9360p+3465)n 2 9(n+1)(n+2)(n+3)(n+4)(n+5) + (12 150p 4 +8100p 3 15 390p 2 3780p+3690)n 4374p 5 2430p 4 +8370p 3 +2430p 2 1836p+1080 9(n+1)(n+2)(n+3)(n+4)(n+5) if 1 2 n  p  2 3 n 1 if 2 3
n < p  n 1 When the total number of voters tends to infinity, the following results hold. Proposition 6. Let F 2 be the PR. Then for large electorates, With the Borda rule, computations reveal hight periodicity both on n and p. This phenomenon is frequent with the Borda rule (see Lepelley et al. 2008). In Table 3, we then provide only results when n tends to infinity. It appears that the Borda rule particularly performs well. The q-Condorcet efficiency of the Borda rule converges quickly to one as q tends to the threshold [START_REF] Baharad | The Borda rule, Condorcet consistency and Condorcet stability[END_REF] 3 . With contrast to the poor performance of the negative plurality rule, its sequential version, the Coombs rule, performs very well in selecting the q-CW . With the Coombs rule, the q-Condorcet efficiency is above 91% as soon as q is greater than [START_REF] Courtin | Positional rules and q-Condorcet consistency[END_REF] 2 . Moreover, the Coombs rule admits a threshold quota of [START_REF] Baharad | The Borda rule, Condorcet consistency and Condorcet stability[END_REF] 3 above which it always selects the q-CW , whereas the negative plurality does not admit any threshold.

CE (F 2 , 1, q) = 8 > < > : 486q 5 + 1350q 4 1440q 3 + 720q 2 160q + 35 3 if 1 2 < q  2 3 1 if 2 3  q  1

Nanson's rule

The following result deals with the Nanson's rule.

Proposition 11. Let F 2 be the SPR. If n is a multiple of 72 and p multiple of 36 with p = dqne 1, then CE F 2 , n, p =

n 1 n

 1 2 n 3 n 4 n 5 n 6 a a b b c c b c a c a b c b c a b a where for instance, n 1 individuals prefer the candidate a to the candidate b and the candidate b to the candidate c. Obviously n = P 6 i=1 n i . A specific combination of n i 's that sum to n is referred to as an anonymous profile or a voting situation.

  then b is the winner. Once again, three usual SPRs are well-known in the literature: Hare's rule (↵ = 0), Coombs rule (↵ = 1) and Nanson's rule (↵ = 1

Fig. 4 q

 4 Fig. 4 q-Condorcet efficiency of the Coombs rule

  and Courtin

	⇤ Corresponding author. sebastien.courtin@u-cergy.fr	University of Cergy-Pontoise, THEMA, UMR CNRS 8184, France.	Email:

† University of Cergy-Pontoise, THEMA, UMR CNRS 8184, France. Email: mathieu.martin@u-cergy.fr ‡ University of Yaounde I, Department of Mathematics, Advanced Teachers' Training College, Cameroon. Email: imoyouwou2@yahoo.fr

[START_REF] Courtin | Positional rules and q-Condorcet consistency[END_REF]

Their book "voting paradoxes and group coherence: The Condorcet efficiency of voting rules" summarizes many of the existing papers on that topics.

Table 1 q

 1 -Condorcet efficiency of the plurality rule

	n 12	q	1 2 + ✏ 0, 54 0, 57 0.8932 0.8932 0.8932 0.9842 0.9842 0.9842 0, 6 0, 63 2 3	> 2 3 1
	24		0.8623 0.8623 0.9376 0.9794 0.9967 0.9967	1
	30		0.8555 0.9221 0.9648 0.9648 0.9884 0.9981	1
	42		0.8476 0.9009 0.9405 0.9856 0.9952 0.9992	1
	60		0.8414 0.9154 0.9625 0.9776 0.9946 0.9997	1
	66		0.8401 0.9092 0.9555 0.9828 0.9959 0.9998	1
	78		0.8381 0.9230 0.9593 0.9820 0.9974 0.9999	1
	96		0.8359 0.9090 0.9571 0.9846 0.9968 0.9999	1
	102	0.8354 0.9233 0.9639 0.9870 0.9973 0.9999	1
	114	0.8344 0.9156 0.9556 0.9862 0.9964	1	1
	126	0.8337 0.9235 0.9580 0.9855 0.9973	1	1
	144	0.8328 0.9143 0.9645 0.9866 0.9969	1	1
	156	0.8323 0.9209 0.9585 0.9860 0.9976	1	1
	1		0.8294 0.9216 0.9646 0.9883 0.9980	1	1

Table 2 q

 2 -Condorcet efficiency of the negative-plurality rule

	n 12	q	1 2 + ✏ 0, 54 0.6130 0.6734 0.6734 0.7776 0.7776 0.7776 0.9050 0.9050 0.9922 0.9990 0.9990 0, 57 0, 6 0, 63 2 3 0, 69 0, 75 0, 84 0, 96 1
	24		0.6026 0.6370 0.6965 0.8091 0.8558 0.8558 0.9133 0.9512 0.9950 0.9999 0.9999
	30		0.6004 0.7038 0.7498 0.7498 0.8352 0.8709 0.9154 0.9683 0.9956 0.9999 0.9999
	42		0.5976 0.6743 0.7090 0.8083 0.8639 0.8876 0.9181 0.9726 0.9962	1	1
	60		0.5954 0.6899 0.7639 0.7862 0.8488 0.8997 0.9373 0.9718 0.9967	1	1
	66		0.5950 0.6685 0.7382 0.8017 0.8570 0.9022 0.9363 0.9763 0.9968	1	1
	78		0.5943 0.6985 0.7560 0.8087 0.8691 0.9060 0.9348 0.9773 0.9969	1	1
	96		0.5936 0.6703 0.7510 0.8084 0.8704 0.9099 0.9430 0.9761 0.9972	1	1
	102	0.5934 0.6892 0.7639 0.8168 0.8741 0.9108 0.9421 0.9786 0.9971	1	1
	114	0.5930 0.6793 0.7475 0.8200 0.8616 0.9125 0.9406 0.9790 0.9972	1	1
	126	0.5928 0.6971 0.7452 0.8119 0.8687 0.9138 0.9393 0.9793 0.9972	1	1
	144	0.5925 0.6783 0.7639 0.8207 0.8697 0.9154 0.9441 0.9783 0.9973	1	1
	156	0.5923 0.6873 0.7467 0.8140 0.8712 0.9162 0.9428 0.9787 0.9978	1	1
	1		0.5928 0.6907 0.7607 0.8233 0.8763 0.9259 0.9485 0.9824 0.9981	1	1

Table 3 q

 3 -Condorcet efficiency of the Borda rule

	n 1 0.8573 0.9463 0.9805 0.9953 0.9995 1 q 1 2 + ✏ 0, 54 0, 57 0, 6 0, 63 2 3	> 2 3 1

Table 5 q

 5 -Condorcet efficiency of the Coombs rule

	n 12	q	1 2 + ✏ 0, 54 0, 57 0.9349 0.9349 0.9349 0.9842 0.9842 0.9842 0, 6 0, 63 2 3	> 2 3 1
	24		0.9243 0.9243 0.9644 0.9869 0.9967 0.9967	1
	30		0.9217 0.9569 0.9798 0.9798 0.9925 0.9981	1
	42		0.9185 0.9465 0.9676 0.9917 0.9969 0.9992	1
	60		0.9159 0.9548 0.9798 0.9878 0.9969 0.9997	1
	66		0.9154 0.9516 0.9761 0.9907 0.9976 0.9998	1
	78		0.9145 0.9591 0.9783 0.9903 0.9985 0.9999	1
	96		0.9136 0.9518 0.9772 0.9918 0.9983 0.9999	1
	102	0.9134 0.9594 0.9808 0.9931 0.9985 0.9999	1
	114	0.9130 0.9554 0.9765 0.9927 0.9980	1	1
	126	0.9127 0.9596 0.9778 0.9923 0.9985	1	1
	144	0.9124 0.9548 0.9813 0.9929 0.9984	1	1
	156	0.9122 0.9583 0.9781 0.9926 0.9987	1	1
	1 0.9112 0.9590 0.9815 0.9939 0.9990	1	1

A complete solution is given for the classical positional rules (plurality rule, negative plurality rule, Borda rule, Hare's rule, Coombs rule and Nanson's rule).

If more than one candidate have the same score, then they all belong to the "winning set".

Note that if two candidates have the same score, they are eliminated at the first step and then there is no second step. If all the three candidates have the same score, then they all belong to the winning set.

Note that for q  1 2 , one may find some configurations of individual preferences where for some candidates a and b, a is beaten by b and b is beaten by a. Therefore those quotas are omitted to avoid ambiguous situations.

For a detailed discussion of this hypothese and some others, see[START_REF] Regenwetter | Behavioral social choice[END_REF].

Sequential Positional Rules

We now consider the following three SPRs: Hare's rule (↵ = 0), Coombs rule (↵ = 1) and Nanson's rule (↵ = [START_REF] Courtin | Positional rules and q-Condorcet consistency[END_REF] 2 ).

Hare's rule

The following results solve the Hare's rule.

Proposition 7. Let F 0 be the SPR. If n is a multiple of 24 and p 1 2 n with p = dqne 1, then CE F 0 , n, p =

(12 850p+10 785)n 4 1933n 5 +( 25 920p 2 53 160p 93 640)n 3 +(25

n and p even

n and p odd

For large electorates, we have the following proposition.

Proposition 8. Let F 0 be the SPR. Then for large electorates,

Table 4 and Figure 3 below present some exact frequencies. Once again, it can be observed that the q-Condorcet efficiency of the Hare's rule increases as q increases. Moreover, frequencies converge quickly to 1 as q tends to one. For q 3 4 , the Hare's rule always selects the q-CW in accordance with Courtin et al. (2012). Besides it appears in terms of q-Condorcet efficiency that the Hare's rule always performs better than the plurality rule.

Coombs rule

The following results concern Coombs' procedure.

Proposition 9. Let F 1 be the SPR. If n is a multiple of 6 and and p 1 2 n with p = dqne 1, then

In a large society, we have:

Proposition 10. Let F 1 be the SPR. Then for large electorates,

The corresponding table and figure are:

In a large society, we have:

Proposition 12. Let F 2 be the SPR. Then for large electorates, CE F 2 , 1, q = 8 < :

Table 6 illustrates these results for a large set of voters. Yet again, the Nanson's rule performs better than the Borda rule in the selection of a q-CW . Indeed, the q-Condorcet efficiency of the Nanson's rule is above 93% as soon as q is greater than

Concluding discussion

It seems desirable that the winner of an election should not be beaten under a qualified majority rule. Unfortunately for three-candidate elections, positional rules (simple or sequential) fail to satisfy this requirement for any quota of the qualified majority between [START_REF] Courtin | Positional rules and q-Condorcet consistency[END_REF] 2 and q ⇤ . Our contribution in the present paper underlines the respective behaviors of six positional rules with respect to their ability to select the q-CW . Our overall comments of the results obtained are as follows:

(i) for each rule studied, the q-Condorcet efficiency increases as the quota increases up to a threshold above which the rule always selects a q-CW ;

(ii) among the usual simple positional rules, the Borda rule consistently has significantly greater q-Condorcet efficiency than both the plurality and the negative plurality rules. The negative plurality appears to be the worst simple positional rule;

(iii) the Nanson's rule is the top-performing rule as well among the sequential positional rules as among the simple positional rules under consideration here;

(iv) the improvement in q-Condorcet efficiency seems greater in moving from a simple positional rule to its corresponding sequential form.

In a different but similar investigation, our results are in accordance with earlier observations by Gehrlein and Lepelley (2006). With three candidates, the use of a sequential positionnal rule in combination with a larger quota will significantly improve the stability of the winner.


C Bouchard
email: carole.bouchard@paris.ensam.fr

J E Kim

J F Omhover

A Aoussat

Cognitive Designers Activity Study, Formalization, Modelling, and Computation in the Inspirational Phase

Keywords: Inspirational process, Case study, Conjoint Trends Analysis, CTA method

This paper refers to a research project that we are conducting about the formalization of the designer's cognitive activity in order to develop new computational tools to support the early design process. These tools are especially focused on the inspirational phase of design. We first formalized the cognitive processes of the designers dedicated to our specific phase, and identified some routine parts where computational tools could be useful in order to enrich the traditional design process. The computation of design rules in the early phases of design needs to establish specific formalizations that can be implemented by algorithms. After modelling designers' cognitive processes, we explored the main information systems they use and completed them by an investigation about Content-Based Image Retrieval systems (CBIR). Our research consisted then in establishing specific formalizations in order to cope with recent technologies that could improve the precision and efficiency with which designers can access inspirational images.

INTRODUCTION

This paper describes a research project to model the cognitive processes of designers in order to develop computational tools for the earliest phases of design. The formalization and explicitation of designers' cognitive processes are becoming a strategic topic for many scientific communities including design science, cognitive psychology, computer science, and artificial intelligence. This growing interest is partly due to pressure from industry where the shortening of development delays and the increasing variability of the offerings expected by the consumer require a formalization and a digitalization of the earliest phases of the design process. In this context, three research areas are now well established and tend to develop new models and tools that will help to progressively digitize the early design process:  the formalization of the cognitive design process with the extraction of design knowledge, rules and skills;  the translation of design rules into design algorithms;

 the development of software tools that will be used by the designers themselves and the other trades involved in the early collaborative design process. Following this, we first investigated the cognitive activity of designers and focused on the inspirational phase. These cognitive processes were formalized as a design method named the Conjoint Trends Analysis (CTA) method. The CTA method [1] is a recent method which has been molded to the information gathering process in industrial design, taking into account the task-based requirements and the cognitive and affective processing of designers. Our original work focused on the identification and use of various domains of influence (nature, arts, industrial sectors, sociological end values) in order to enrich the design solution space.

Finally, the CTA method enables the identification of formal trends in attributes (shape, color, textures) linked to particular environments in order to use them in the early design of new products. This makes it possible to enrich and to inspire the designers and the design team when designing products. It is positioned in the earliest phases of the design process.

COGNITIVE DESIGNERS ACTIVITY, FORMALI-ZATION AND MODELLING 2.1 The information phase in the early stages of design: the inspirational process

The design process reduces abstraction through the use of various successive levels of representation which integrate more and more constraints. It can be seen as an information processing activity that includes informative, generative, evaluative and deductive stages. The informative phase is a crucial. First, it enables the completion of design problems which are by nature illdefined and ill-structured [START_REF] Restrepo | Information processing in design[END_REF][START_REF] Simon | The science of the artificial[END_REF] and so refers to semantically impoverished tasks. Designers use a large variety of sources coming from different areas such as comparable designs, other types of design, images of art, beings, objects and phenomena from nature and everyday life. Sources of inspiration are an essential base in design thinking, as definitions of context, triggers for idea generation [START_REF] Eckert | Sources of Inspiration: A language of design[END_REF], and anchors for structuring designers' mental representations of designs.

In favorable contexts, designers built trend boards in order to structure their inspiration sources. Trend boards offer a visual and sensorial channel of inspiration and communication for design research and development, which could be considered to be more logical and empathic within a design context than only verb-centric approaches [START_REF] Mcdonagh | Exploring the degree to which individual students share a common perception of specific trend boards: observations relating to teaching, learning and teambased design[END_REF]. They are usually a collection of images compiled with the intention of communicating or provoking a trend or ambience during the product design process.

As a routine part of the creative process, product (DB) in various ways: one by one browsing, keywords or designers search for and collect materials that they find image feature specification, automatic image feature inspirational. They get their inspiration in their personal extraction, or finally providing an example from which lives and through a more focused way in their features will be compared by similarity to those of other professional lives, in various sources like specialized images. The technologies used come from a range of magazines, bibliographies, material from exhibitions and the web. scientific knowledge bases from artificial intelligence and computer vision applications, including statistics, pattern 2.2 The Conjoint Trends Analysis (CTA) method recognition, and signal processing. Searches must rely on

The information phase of the cognitive design activity was metadata such as captions or keywords. These keywords can be generated by a human or automatically extracted studied and formalised in order to define the Conjoint from the web. Trends Analysis (CTA) method [1]. As shown in Figure 1, the CTA method is composed of three steps: gathering/ CBIR systems tend to turn towards specific categories of categorizing images and keywords; ambience definition; end-users working in areas where creative thinking is and pallets composition. The CTA method enables the identification of attributes linked to particular datasets needed, like industrial design or architecture. On the other hand, specific databases are increasingly developed in (e.g., common properties of images in a database) so that those domains, which do not yet integrate the they can be used to inspire designers in the early stages of design for new product. sophisticated technologies from CBIR. Multi-Dimensional Scaling seems to be a good way to interactively display sets of products arranged according to semantic axis. Besides, the use of a folksonomy for gathering progressively relevant expert material for building the ontology seems to be a promising way to bridge high and low level information.

Supporting design by Content Based Image

CBIR

Retrieval (CBIR)

systems are applied in the context of huge databases where the question arising is how to find the right image. This is particularly difficult when dealing with design information. Indeed, the design activity is specific The CTA results are trend boards that represent in the way that design information covers various levels of sociological, chromatic, textural, formal, ergonomic, and technological trends. The trend boards communicate identified homogeneity in terms of style and consumers' abstraction of the information. However the main majority of commercial and academic systems still focus on lowlevel features. This difficulty is increased when dealing sociological values. They are mainly based on visual with images that have a multi-dimensional and subjective information, and come from the frequent occurrence of nature as is the case in the context of industrial design. certain properties within a dataset. From this analysis, One major current problem in CBIR is to link visual images and relevant words are selected and formalized content with semantic content to bridge the semantic gap under a form of ambiences. Ambiences are typical between low-level content and higher-level concepts. The representations where the emotional impact is intended to semantic gap is the lack of coincidence between the be higher. Global and discrete design elements are then extracted from these ambiences under a form of pallets. These design elements are used for the generation of information that one can extract from the visual data and the interpretation that the same data has for a user in the same situation [START_REF] Datta | Image retrieval: ideas, influences and trends of the new age[END_REF]. To close the problem of the semantic new design solutions.

gap, some CBIR systems automatically generate Therefore, trend boards offer a relatively exhaustive additional search terms by conceptual similarity with the representation of the references usually used by the original terms, as identified through term co-occurrence in designers for their composition and play an important role in stimulating idea generation while anchoring contextual matter [START_REF] Eckert | Sources of Inspiration: A language of design[END_REF]. They reinforce the link and semiotic coherence between the consumers end values, functionalities in any domains of influence, and product attributes such as form, color, texture, and usability principles. Another purpose of the trends analysis is to define user-convenient principles and solutions that can be integrated in future products.

a corpus or through the use of an ontology. In the field of CBIR, many papers mention the reduction of the semantic gap, but they often do not refer to semantic adjectives and are more based on concepts like car. However their architecture is often interesting insofar as these systems could also integrate semantic adjectives.

A study [START_REF] Cox | Hidden annotation in content based image retrieval[END_REF] showed that indexing concepts by keywords in image indexing systems is much more appropriate with Indeed designers often have to provide new designs human similarity perception than low level features and using insufficient information about consumers. Trend provides good retrieval performance. Naphade et al [START_REF] Naphade | Extracting semantics from audio-visual content: the final frontier in multimedia retrieval[END_REF] boards show ambiences including people in context.

suggest that matching semantics might be achieved by Contexts are decisive in the attribution of a signification to the object. employing top-down as well as bottom-up techniques. In order to support the top-down method, it will be important to develop semantic nets that link higher-level concepts that are evoked by visual images. Existing systems

CONTENT-BASED IMAGE RETRIEVAL (CBIR) APPROACH

Content-Based Image Retrieval (CBIR) is a technology that in principle helps organize digital picture archives by frequently use about ten adjectives and at the best about several thousand of images in the DB. About the system architecture, we encounter often the combination of a filter and of a direct re-classification to images. When their visual content (colors, shapes, or textures) [START_REF] Datta | Image retrieval: ideas, influences and trends of the new age[END_REF]. User several users enter the same information, the system queries are mainly based on image example, region of performs a re-classification of the images. The feedback interest, or concept keyword. The search process mainly systems using a weighting system adjusting the consists of query formulation, specification of which images to retrieve from the system from the database importance between the features that seem interesting. A remaining problem is the changing nature of the user's perception of a semantic adjective in the time. So the feedback system has to be well developed, with a simple and efficient interaction with the user. The system should also enable the user to add information by entering new terms and new evaluations of the results.

Towards Kansei-Based Image Retrieval (KBIR)

Future CBIR systems should correlate high-level dimensions like concepts, semantics and emotions with low-level dimensions. The connection of low-level and high-level dimensions is very subjective and variable from person to person. Consequently, the previous systems are often based on a strong interaction between the endusers and the system itself, using images and semantic adjectives. It is frequently done with the intervention of the end-users thanks to learning systems using neural networks [START_REF] Bianchi-Berthouze | Subjective interpretation of complex data: requirements for supporting kansei mining process, International workshop on multimedia data mining[END_REF][START_REF] Bianchi-Berthouze | Subjective interpretation of complex data: requirements for supporting kansei mining process[END_REF][START_REF] Tsutsumi | A Development of the Building Kansei Information Retrieval System[END_REF], or genetic algorithms [START_REF] Kato | An image retrieval method based on a genetic algorithm controlled by user's mind[END_REF]. Some studies were already led in this way, but not dedicated to the field of design [START_REF] Naphade | Extracting semantics from audio-visual content: the final frontier in multimedia retrieval[END_REF][START_REF] Bianchi-Berthouze | Subjective interpretation of complex data: requirements for supporting kansei mining process, International workshop on multimedia data mining[END_REF][START_REF] Kato | An image retrieval method based on a genetic algorithm controlled by user's mind[END_REF][START_REF] Tanaka | A Method For Extracting. and. Analyzing[END_REF][START_REF] Colombo | Semantics in visual information retrieval[END_REF][START_REF] Black | Characterizing the highlevel content of natural images using lexical basis functions[END_REF][START_REF] Black | Indexing natural images fir retrieval based on kansei factors, Stereoscopic Displays and Virtual Reality Systems XI[END_REF]. The advantage of Kansei Engineering methods is that they focus more on the viewer rather than on the image [START_REF] Tanaka | A Method for Extracting. And. Analising[END_REF], and similarity measures derived from kansei indexing come from inner experience, rather than visual similarity. These methods enable the designer to assess evoked feelings on the basis of impression words including frequently semantic adjectives (urban, romantic, aggressive, and so on) or emotional adjectives (amused, astonished) describing the viewer in front of a specific image. It is, however, difficult to develop competitive systems able to search and classify images from semantic adjectives because their appreciation may be altered by an inter-individual subjectivity. Tanaka et al. investigated which regions and features of images are most attractive, contributing so to human Kansei [START_REF] Hayashi | An image retrieval system to estimate impression words from images using a neural network[END_REF] in [START_REF] Tanaka | A Method for Extracting. And. Analising[END_REF]. An increasing attractiveness seems to be correlated with size effects (attractiveness increases with size) or color effects (warmer, highly chromatic and high values colours). Hayashi et al. [START_REF] Hayashi | An image retrieval system to estimate impression words from images using a neural network[END_REF] in [START_REF] Tsutsumi | A Development of the Building Kansei Information Retrieval System[END_REF] attempted to train a neural network to predict Kansei with impression words evoked by outdoor scenery images. The best results were obtained for visual words such as spring or clear. It was emphasized that the mapping of human impressions with physical features is not one to one and that any retrieval system must retrieve multiple images, allowing the user to choose the best one. The results of this study showed a statistically significant superiority of the Kansei Based Retrieval systems over the random retrieval.

A CASE STUDY: THE TRENDS SYSTEM

On the base of research and industrial projects, we started to formalize and structure design information into specific formats. Especially in the TRENDS European project, we aimed to raise a new formalization of design information which can improve designers' access to webbased resources, and help designers to find appropriate materials and identify design trends in those materials.

Towards a new formalization of design information

We expected that the TRENDS system would enable us to elaborate the field of image search, including contentbased image retrieval and Kansei Based Image Retrieval (KBIR). Finally, the Trends Analysis (CTA) method would be partially digitalized and implemented by the computational tool which integrates semantic processing and image contents. This computational tool should reduce retrieval time and provide a certain completeness of the retrieval results in expanding the corpus of images from different sectors of influence; enhancing creativity with more or less open image retrieval; and facilitating idea generations using key harmony rule of design.

In the TRENDS project, the data collection was carried out on the basis of fictional scenarios and extraction of design information from previous projects which have used the CTA method.

Figure 2: Design knowledge extraction by manual annotation [19] First, we validated a list of sectors of influence in car design (see Table 1). This table shows sectors of influence identified in 1997 and in 2006. Interestingly, 70% of the sectors of influence have not been changed. This implies that we could integrate some routine parts of sectors of influence in the data database of the TRENDS system. , and low-level information (color, form, and texture). These levels of information can be seen as the position of an axis going from abstract (high-level information) to concrete (low-level information). The structure of design information enabled the construction of a design domain ontology. This combination yielded a more flexible structure of information and it was more suited to design information. Therefore, the developers of the TRENDS project used these data filtering models and rules to develop the design domain ontology and the Bag of Words [36].

Rank

Those two method could be used in independently or complementary.

applications Figure 3: Examples of semantic queries 'Chic' under two conditions : without the BoW (left) and without the BoW (right) Fourth, we formalized the cognitive processes of designers wherein designers mentally or explicitly categorize images sources. Those categorizations were initially based on the distribution of colors on the chromatic circle according components. Further, we Table 2: Examples of design domain ontology [START_REF] Bouchard | Kansei Information Processing In Design[END_REF] integrated the aesthetic harmony rule of image which is a core expertise of designers. In order to support this Third, an important part of the result concerned a phase, the TRENDS system is supposed to provide a definition of a semantic model which can be easily new way to retrieve images according to similarities of implemented in data mining and integrated design images corresponding to harmony rule of design and expertise. The methods used were a combination of categorize them in a smart way (pallet generation design domain ontology (See Table 2) and Bags of Words process). (BoW) (See Table 3). In particular, the BoW helps 4.2 Functionalities of the TRENDS system significantly increase the relevance of semantic queries. For example, if we enter the word 'chic', we get some Finally, the TRENDS system proposes two groups of images answering to this term. Using both the design functionalities: image retrieval and desig advanced domain ontology and the BoW, the system shows three times more images than using design domain ontology alone (See Figure 4). functionalities. Figure 4 shows a global interface of the TRENDS system. Regarding the image retrieval functionalities, the system searches the information, but not from the overall web. The information from the web is filtered according to the listed sectors of influence of the designers (See Table 1): for instance car design, advertising, architecture, arts, etc. First, the image retrieval functionalities consisted of: -random search: an open search, providing serendipity and so favouring creativity; -semantic search: the user semantic adjectives or concepts; inputs some keywords, -search with an image example: the user selects an image as a query, similar images can be found in the database based on similarity rules between the global descriptors of the image content related to shape, colour or texture dimensions; -relevance feedback: when the results are sometimes not so c nvincing after the initial query, we could give the relevance feedback (positive or negative) refine the search; manually to Table 3: Examples of Bag of Words [START_REF] Bouchard | Building A Design Ontology Based On The Conjoint Trends Analysis, I*Prom Virtual Conference[END_REF][START_REF] Bouchard | Building A Domain Ontology For Designers: Towards A Kansei Based Ontology[END_REF] In addition, some options enable the designer to select the size of the displayed images depending on the task that the designers have to manage. We can also apply interesting display functions, like a slideshow for instance. Second, design advanced functionalities consist of:

This function enables the designer to link and arrange the words with the images. Some images do not possess semantic descriptors by default. Others are overlapped when they have the same description. The designers can -grouping: to automatically display subsets of images also achieve the complete mapping manually. grouped by specific harmony rules. This function is required because it would be difficult for the end-user to -statistics: to apply statistics related to a word or an have a complete view of the content of the sphere, image. The system promises quantitative information wherein search results are displayed; about the representativeness level of a word or an image

CONCLUSION

This paper presented a study we led about modelling the cognitive processes of the designers in order to develop computational tools for the earliest phases of design.

We focused this study on the inspirational phase of the that enable the designer to link low-level descriptors with high-level descriptors.

Cognitive models enabled the designer to identify some routines that could partly be implemented by algorithms and bring an added value to the traditional process. design process, where designers have to deal with a large amount of information. Cognitive models here gave birth to the Conjoint Trends Analysis (ATC). After practicing this method in several projects in the field

ACKNOWLEDGMENTS

The authors are grateful to the European Commission for of automotive design, some computer support tools were funding TRENDS project (FP6 IST 2005-27916) and foreseen in order to enrich the information gathering.

express their gratitude to all partners of TRENDS We intended to partly digitize the ATC method which consortium for their contribution. http://www.trendsproject.org corresponds to the informational part of design activity. Two ways were combined at the same time, which were presented in this paper previously: the elaboration of 7 REFERENCES ontological data tables and bag of words which were

[1] Bouchard, C., Christofol, H., Roussel, B., Aoussat, related to more or less abstract concepts, which both A., 1999, Identification and integration of product were used to be implemented by algorithms. The design rules so elaborated are based on particular formalizations design trends into industrial design, ICED'99, 12 th International Conference on Engineering Design, 2: 1147-1151.

Figure 1 :

 1 Figure 1: The Conjoint Trends Analysis (CTA) method

-

  pallets function: to generate a pallet of specific in the sectors; harmonies linked to low-level information between -life style: a bookmark oriented towards specific websites colours, shapes, and textures; which propose information about sociological changes, -semantic mapping: to generate automatically a first values and lifestyles evolutions. This function was a version of semantic mapping with a text search; request of the designers themselves.

Figure 4 :

 4 Figure 4: A global interface of the TRENDS system

1997 (40 designers) 2006 (30 designers)

	1	Car design	Car design
	2	Aircrafts, aeronautics	Architecture
	3	Architecture	Interior design & furniture
	4	Interior design & furniture	Fashion
	5	Hi-Fi	Boat
	6	Product design	Aircraft
	7	Fashion	Sport goods
	8	Animals	Product design
	9	Plants	Cinema & commercials
	10	Science Fiction	Nature& urban ambiances
	11	Virtual reality	Transportation
	12	Fine arts	Music
	13	Cinema	Fine arts
	14	Music	Luxury brands
	15	Travels	Animals
	16	Food	Packaging & advertising
	Table 1: Sectors of influence in car design [20-21]
	Second, we identified that designers employed different
	type of design information and they consists of different
	levels: high-level (values, semantic words, analogy, and
	style), middle-level (sector name, context, and function)

  Table 2 shows some examples in the field of Image retrieval.

	Designer' s word	Related words	Related to low-level features
	Balanced	Stable		symmetry
					use of formal
	Beautiful	Aesthetic, gorgeous	harmonies use of chromatic
					harmonies
	Bright	Brilliant		reflectance
	Clear	Clean, pure	white, light greys
	Cold	Fresh, freezing, aqua		cold colors
	Dynamic		Active	dissymmetry, tense lines
	Natural	Simple Authentic	natural colors (green, …)
	Soft		Light	Curves, Pastels color, Smooth matter
	Romantic	Glamour	Unsaturated colors (pastels)
					Elemental
	Simple	Basic, Clean	geometrical volumes,
					plain colors
	Relaxed	Comfortable	Curves with big radius of curvature
				finishing, coating with
	Quality		Clean	visual and tactile
					effects
	Exciting	Seductive, appealing	saturated colors
	Powerful	solid, strong, robust, sturdy, performance,
		vigorous, sportive, big, dynamic, maxi,
		thick,	speed,	sport,	aerodynamics,
		aggressive, secure, heavy, muscular,
		brawny, hefty, muscular, powerful, sinewy,
		herculean, athlete, potency, potent
	Aggressive violent, pleasing, imposing,	speed,
		irritated, stressed, choleric, sport, brutal,
		provoking, dangerous, sharp, angular,
		daring, belligerent, imperious, energetic,
		fast pushy, pushing

Chic

knack, classy, elegant, pretty, refined, purified, exceptional, smoothness, design, style, product, fashion, stylish, high style, fine style, noble, best , style, dressed, glossy, satiny, sleek, silken, silky, silk like, slick, satin, aesthetic