E Kamwa
email: eric.kamwa@univ-antilles.fr

On Two Voting Systems that Combine Approval and Preferences: Fallback Voting and Preference Approval Voting

Keywords: Approval Voting, Rankings, Condorcet, Properties, Impartial and Anonymous Culture JEL Classification: D71, D72

 by exploring some other normative properties of FV and PAV. We show among other things that FV and PAV satisfy and fail the same criteria; they possess two properties that AV does not: Pareto optimality and the fact of always electing the Absolute Condorcet winner when he exists. To provide a practical comparison, we evaluate the probabilities of satisfying the Condorcet majority criteria for three-candidate elections and a considerably large electorate, examining FV and PAV alongside other voting rules. Our findings indicate that PAV outperforms the Borda rule in this regard. Furthermore, we observe that in terms of agreement, FV and PAV align more closely with scoring rules than with Approval Voting. Our analysis is performed under the impartial anonymous culture assumption.

Introduction

When it comes to single-winner elections, the literature and practical applications primarily revolve around two major categories of voting rules. These can be broadly classified as scoring rules based on rankings and rules based on evaluation or approval. Scoring rules (SCR) typically require voters to rank the candidates, either all of them or a subset. Based on these rankings, candidates receive points according to their positions. The candidate with the highest total score, as determined by the rule in question, is declared the winner.

Among the most well-known SCR are the Plurality Rule (PR), the Negative Plurality Rule (NPR) and the Borda Rule (BR). 1 Approval Voting (AV), popularized by [START_REF] Brams | Approval Voting[END_REF], has gained significant popularity: this rule simplifies the voting process by allowing voters to express their approval for the candidates they find acceptable. Under AV, each voter has the freedom to approve as many candidates as they desire. The candidate(s) who receive the highest number of approvals are declared the winner(s). AV has garnered attention as a viable alternative to SCR in various contexts; its simplicity and intuitive nature have contributed to its appeal among both scholars and practitioners. As a result, numerous organizations have adopted AV for their decision-making processes (see [START_REF] Regenwetter | Approval voting and positional voting methods: Inference, relationship, examples[END_REF].

Numerous studies have extensively analyzed the merits and limitations of both SCR and AV. Prominent works, such as those by [START_REF] Felsenthal | Review of paradoxes afflicting procedures for electing a single candidate[END_REF] and the comprehensive Handbook of Approval Voting edited by [START_REF] Laslier | Handbook on Approval Voting, Studies in Choice and Welfare[END_REF], delve into these voting rules and offer insights into their strengths 1 Scoring rules play a significant role in various sports disciplines, such as figure skating, diving, and gymnastics competitions. These rules are often variants of the weighted and/or truncated Borda rule and are designed to establish rankings and determine winners based on a fair and balanced evaluation of participants' performances. In the realm of sports, scoring rules serve as a vast and largely untapped resource, offering numerous remarkable and significant examples of their application. and weaknesses. The objective of such analyses is to provide valuable information and insights to the public and decision-makers, facilitating informed discussions and considerations regarding the selection or implementation of an appropriate voting rule in the context of electoral reform. Through rigorous analysis and empirical evidence, they aim to inform public opinion and provide decision-makers with valuable guidance in choosing the "best" voting rule suited to their specific needs and goals. [START_REF] Norris | Choosing electoral systems: Proportional, majoritarian and mixed systems[END_REF] points out, following a long tradition of analysis of the influence (real or supposed) of voting systems on political systems, that an electoral reform is never trivial; because, depending on the society in which it is implemented, it can lead to unstable political systems, result in strong political polarization, give the role of kingmaker to certain groups or favor certain types of candidates. Indeed, any electoral reform should be driven by well-defined objectives and necessitate thoughtful deliberations regarding both its goals and the normative criteria that the chosen voting rule should meet. In addition, it is crucial that the voting rule implemented is simple and easily understandable for voters. A voting system that is complex or difficult to understand may discourage voter participation and undermine the legitimacy of the electoral process. Simplicity and transparency in the voting rule help ensure that voters can easily grasp the mechanics of the system, have confidence in the process, and make informed choices. Unfortunately, no clear consensus seems to emerge in the literature on the possible superiority of one rule over the others. Arguments in favor of different voting rules are diverse and numerous, reflecting the complexity and multifaceted nature of the topic. Given this lack of consensus, one potential solution is to seek a compromise between the families of voting rules. This is the choice that [START_REF] Brams | Voting systems that combine approval and preferences[END_REF] and [START_REF] Sanver | Approval as an intrinsic part of preference[END_REF] seem to have made. Fallback Voting and Preference Approval Voting [START_REF] Brams | Voting systems that combine approval and preferences[END_REF] and [START_REF] Sanver | Approval as an intrinsic part of preference[END_REF] introduced two voting rules reconciling ranking-based decisions with approval-based decisions:2 Preference Approval Voting (PAV) and Fallback Voting (FV). Under PAV, voters rank all the running candidates and distinguish the ones they approve of from those they disapprove of. If there is no more than one alternative with the majority of approvals (greater than half of the number of voters), PAV picks the AV winner; when more than one candidate is approved by more than half of the electorate, PAV picks the one who is preferred by the majority among them; in case of a majority cycle among these candidates, it picks the one with the highest number of approvals among them. Under FV, voters first indicate all the candidates they approve of (this can range from no candidates to all) and then they rank only these candidates; each level of rankings (of the approved candidates) is considered and if at a given level a majority of voters agree on one highest-ranked candidate, this candidate is the FV winner. 3 The procedures implemented under PAV or FV to determine the winner are defined in such a way as to satisfy both the principle of the "most approved" and that of the "most preferred". However, the above informal definitions of PAV and FV do not appear to take into account situations where ties may arise; in fact, there is no reference made to any tie-breaking rules. Further discussion on this point will be provided in Section 2. Formal definitions of PAV and FV are provided later. [START_REF] Brams | Voting systems that combine approval and preferences[END_REF] have highlighted several desirable properties and drawbacks of FV and PAV. They showed among other things that: FV, PAV, and AV may all give different winners for the same profile; a unanimously approved candidate may not be a FV or a PAV winner; a least-approved candidate may be a FV or PAV winner; a PAV winner may be different from the winners under BR; FV and PAV may fail to pick the Condorcet winner when he exists. Given the limited number of properties considered, the analysis of [START_REF] Brams | Voting systems that combine approval and preferences[END_REF] does not allow a clear judgement on the superiority or not of PAV and FV compared to AV or SCR. It is striking to note that since PAV and FV were introduced, almost no work has been addressed to these rules, contrary to what was the case for AV or SCR. 4 In this paper, our objective is to conduct a comprehensive analysis of the properties of PAV and FV in order to gain deeper insights into these voting rules. Our aim is to draw meaningful conclusions about the strengths and limitations of PAV and FV based on our analysis. Can we say that these rules are a "good" compromise between AV and SCR? Are they better? If the answer is yes, then the choice of PAV or FV as a replacement for SCR or AV would then be justified and these rules would therefore be recommendable for real-world use.

To achieve our goal, this paper is structured into two phases. The first phase focuses on extending the analysis of FV and PAV based on the groundwork laid by [START_REF] Brams | Voting systems that combine approval and preferences[END_REF]. We delve into additional properties of FV and PAV, exploring their performance in relation to other desirable properties commonly used in evaluating voting rules. Many of these properties have been extensively studied in the normative evaluation of SCR and AV. On this basis, we believe that it will henceforth be easier to decide on a comparison between PAV, FV and these rules. It is fair to say that we cannot here review, in an exhaustive way, all the normative properties encountered in the literature. The properties on which we base our study are the following: the Condorcet principle, social acceptability, efficient compromise, Pareto optimality, cancellation, reinforcement, homogeneity, clone independence, and the independence criterion. When these criteria are satisfied, they guarantee a certain consistency between individual preferences and the collective choice.

Each of these criteria will be presented in detail later. Before delving into our analysis, it is important to provide a brief overview of some of the properties we will be discussing. The Condorcet principle allows us, on the one hand, to ensure that when a Condorcet winner (a candidate preferred to any other candidate by more than half of the voters) exists, then that candidate is elected; on the other hand, it allows us to avoid the election of the Condorcet loser (a candidate to whom more than half of the voters prefer any other candidate) when he exists. Social acceptability suggests that a candidate should be elected when the number of voters who rank him among the half of the candidates they prefer is at least as large as the number of voters who rank him in the least preferred half. The efficient compromise principle advocates the election of candidate(s) receiving the highest quantity of support at some efficient level of quality, the quality of support being defined in terms of a candidate's rank in the order of voters' preferences. As we will see later, the non-satisfaction of some of these properties is presented in the literature as unacceptable for a democratic voting rule. It follows that the choice of a voting rule is consequential. We show among other things that FV and PAV are Pareto optimal, and that they always elect the Absolute Condorcet winner when such a candidate exists; 5 and we determine the conditions under which these rules satisfy the reinforcement criterion, and under which they are not vulnerable to the No-Show paradox. From our analysis, it appears that FV and PAV satisfy and respect some of the properties that AV fails.

A great deal of work has been done in recent years on the probability of AV electing the Condorcet Winner (or the Condorcet Loser) when he exists.

In this sense, these studies have made notable comparisons between AV and the three most popular SCR (PR, NPR and BR). We can quote in this respect the works of [START_REF] Diss | On the condorcet efficiency of approval voting and extended scoring rules for three alternatives[END_REF][START_REF] El Ouafdi | On the Condorcet efficiency of evaluative voting (and other voting rules) with trichotomous preferences[END_REF][START_REF] Gehrlein | The Condorcet efficiency of approval voting and the probability of electing the Condorcet loser[END_REF], 2015), and [START_REF] Gehrlein | A note on Approval Voting and electing the Condorcet loser[END_REF]. The second part of this paper will lead in a similar direction. This will provide us with the opportunity to conduct a comparative evaluation of AV, FV, PAV and SCR. First, for voting situations with three candidates and an electorate tending to infinity, we evaluate the probabilities of agreement between AV, FV, and PAV; this analysis is extended to the three scoring rules PR, NPR, and BR. We are also interested in the probabilities of satisfaction or violation of the Condorcet criteria. One advantage that FV and PAV have over AV is their reliance on the principle of "most preferred" candidates. This advantage becomes particularly evident when it comes to electing the Condorcet winner, should one exist. It will therefore be necessary to be aware of the amplitude of this advantage. To do so, our calculations adopt the impartial and anonymous culture assumption. This assumption will be defined later. Our computation analysis teaches us that, for three-candidate elections, the combination of approvals and rankings in FV and PAV brings them closer to SCR in terms of agreement, as opposed to AV; furthermore, they perform better in terms of compliance with the Condorcet criteria than some SCR.

The rest of the paper is organized as follows: Section 2 is devoted to basic definitions. Section 3 presents our results on the properties of FV and PAV.

We provide our probabilistic results in Section 4. Section 5 concludes.

Notation and definitions

Consider a set of n (n ≥ 2) non-abstaining individuals N = {1, 2, . . . , i, . . . , n} who vote sincerely on C = {a, b, c, . . . , m} a set of m (m ≥ 3) candidates. Fallback Voting and Preference Approval Voting It is assumed that the rankings provided by the voters on C are asymmetric, meaning that there are no ties in the rankings. Furthermore, we assume that the approvals of the voters are monotonic with respect to their rankings. This means that if a voter approves a and ranks b ahead of a, this implies that he also approves b. For example, the ranking a ≻ b ≻ c (or simply abc) means that a is ranked ahead of b which is ahead of c and a and b are both approved while c is disapproved.

As voters' inputs are both rankings and approvals, a voting situation is therefore a κ-tuple π = (n 1 , n 2 , . . . , n t , . . . , n κ ) that indicates the total number n t of voters for each of the κ rankings on C such that κ t=1 n t = n; given the assumptions made above, κ = (m + 1)!. Given π, we denote by n ab (π) (or simply n ab ) the number of voters who rank a before b. Candidate a is majority preferred to b if n ab > n ba . We say that candidate a is the Condorcet winner if

n ab > n ba ∀b ∈ C \ {a}; candidate a is the Condorcet loser if n ab < n ba ∀b ∈ C \ {a}.
A candidate a is an Absolute Condorcet winner (resp. an Absolute Condorcet loser) if he is ranked first (resp. last) by more than half of the voters.

Given the rankings and approvals of the voters, we denote by S l (a, π) or simply S l (a) the total number of approvals of candidate a when rankings of level l are considered (l = 1, 2, . . . , m); we say that candidate a is majority approved at level l if S l (a) > n 2 .

Let us now define each of the voting rules under consideration here.

Approval Voting (AV): Under this rule, voters can vote for (approve of) as many candidates as they wish. We denote by AV(a, π) the total number of approvals for candidate a given π. Candidate a is the AV winner if AV(a, π) > AV(b, π) ∀b ∈ C \ {a}. Notice that AV(a, π) = S m (a).

Preference Approval Voting (PAV): According to [START_REF] Brams | Voting systems that combine approval and preferences[END_REF], PAV is determined by two rules and proceeds as follows:

Rule 1 : The PAV winner is the AV winner if i. no candidate receives a majority of approval votes (i.e. is approved by more than half of the electorate)

ii. exactly one candidate receives a majority of approval votes.

Rule 2 : In the case that two or more candidates receive a majority of approval votes, i. The PAV winner is the one among these candidates who is preferred by a majority to every other majority-approved candidate.

ii. In the case of a cycle among the majority-approved candidates, then the AV winner among them is the PAV winner.

Fallback Voting (FV): Following [START_REF] Brams | Voting systems that combine approval and preferences[END_REF], FV proceeds as follows:

1 It is worth noting that the definitions of PAV and FV that we have just presented do not explicitly address situations where ties occur. This is especially true in cases where the number of voters is even. In such situations, it becomes necessary to describe a method for resolving ties. Various tie-breaking methods can be considered, including the random tie-breaking method suggested by [START_REF] Sanver | Approval as an intrinsic part of preference[END_REF]. However, there may be several issues associated with the use of a tie-breaking rule. For the same situation, different tie-breaking rules can lead to different results. The use of a tie-breaking rule can result in the violation of certain normative properties; or it may lack transparency, making it difficult for voters and stakeholders to comprehend and evaluate the decisionmaking process which can undermine the legitimacy and acceptance of the outcome. Then, the use of a tie-breaking rule should be carefully evaluated, taking into account its impact on normative properties, necessity, subjectivity, potential manipulation, and transparency. In the context of this paper, it is not necessary to explore in a particular way the cases where ties can occur.

Since the second part of the paper will have to include the three most popular scoring rules, let us define them at the outset here.

Plurality rule (PR): This rule picks the candidate who is the most ranked at the top. We denote by PR(a, π) the Plurality score of candidate a. Notice that

PR(a, π) = S 1 (a). Candidate a is the PR winner if PR(a, π) > PR(b, π) ∀b ∈ C \ {a}.
Negative Plurality rule (NPR): Under this rule, the winner is determined based on the candidate who receives the fewest last-place rankings from the voters. We denote by NPR(a, π) the number of last places (the Negative Plurality score) of candidate a, this candidate is the NPR winner if

NPR(a, π) < NPR(b, π) ∀b ∈ C \ {a}.
Borda rule (BR): BR gives K -t points to a candidate each time she is ranked t-th; BR(a, π), the Borda score of a candidate, is the sum of the points received. Candidate a is the BR winner if BR(a, π) > BR(b, π) ∀b ∈ C \ {a}.

In the context of a single-winner election, it is possible for multiple candidates to obtain the same score under AV, PR, NPR, or BR. In such situations, a tie-break rule becomes necessary to determine the winner among the candidates with equal scores. In this paper, the setting is such that we will not need to use a tie-break rule.

We can now review the properties of FV and PAV.

Normative properties of FV and PAV

As previously mentioned, [START_REF] Sanver | Approval as an intrinsic part of preference[END_REF] and [START_REF] Brams | Voting systems that combine approval and preferences[END_REF] have identified and analyzed several properties of FV and PAV. They showed that these rules are monotonic, more precisely, they are approval-monotonic and rank-monotonic. A voting rule is approval-monotonic (resp. rank-monotonic) if Fallback Voting and Preference Approval Voting a class of voters, by approving of a new candidate (resp. by raising a candidate in their ranking) -without changing their approval of other candidates -never hurts that candidate and may help the candidate get elected. In this section, we will review additional properties that FV and PAV may either satisfy or fail to satisfy. By examining these properties, we aim to gain a comprehensive understanding of the behavior and performance of FV and PAV as voting rules. This analysis will provide insights into their advantages and limitations in comparison to other voting systems.

Condorcet principle

We know that AV may fail to pick the (Absolute) Condorcet winner when he exists (see [START_REF] Felsenthal | Review of paradoxes afflicting procedures for electing a single candidate[END_REF]. According to [START_REF] Brams | Voting systems that combine approval and preferences[END_REF], FV and PAV may fail to elect the Condorcet winner when he exists; through Propositions 1 and 2, we refine this result.

Proposition 1 When AV selects the Condorcet winner, this candidate is also the PAV winner, but the reverse is not always true.

Proof By definition, PAV always elects the AV winner under Rule 1; this may not be the case under Rule 2. So, for the proof, we only need to focus on Rule 2. Assume that candidate a is both the Condorcet winner and the AV winner. Let us also assume that candidate b (b ̸ = a) is the PAV winner under Rule 2; this means that (i)

AV(b, π) > n 2 > AV(a, π) or (ii) AV(a, π) > n 2 and AV(b, π) > n 2 . It is obvious that (i)
clearly contradicts that a is the AV winner. By definition, b cannot win under (ii)

since n ab > n ba , so a wins. Thus, if AV selects the Condorcet winner, this is also the case for PAV. Let us exhibit a profile to show that the reverse is not always true.

Consider the following profile with 3 candidates and 11 voters:

5 : a ≻ b ≻ c 5 : b ≻ a ≻ c 1 : c ≻ a ≻ b
With this profile, it easy to see that b is the AV winner while a is both the Condorcet winner and the PAV winner. The fact is that when there is an Absolute Condorcet winner, this candidate is the winner under FV, PAV, and PR. As noted further in the paper, FV and PAV exhibit insensitivity to certain paradoxes in domains where an Absolute Condorcet winner exists. The story is quite different on the domain where there is an (Absolute) Condorcet loser. We know that AV can elect the (Absolute)

Condorcet loser (see [START_REF] Felsenthal | Review of paradoxes afflicting procedures for electing a single candidate[END_REF]. We also know from [START_REF] Kamwa | Condorcet Efficiency of the Preference Approval Voting and the Probability of Selecting the Condorcet Loser[END_REF] that PAV may pick the Condorcet loser when he exists. To our knowledge, nothing is known concerning FV. Propositions 3 tells us more on this.

Proposition 3 FV and PAV may elect the (Absolute) Condorcet loser when he exists. When PAV elects the (Absolute) Condorcet loser, this candidate is also the AV winner but the reverse is not true. When FV elects the Absolute Condorcet loser, this candidate is also the AV winner but the reverse is not always true. Fallback Voting and Preference Approval Voting

Proof Consider the following profile with 3 candidates and 11 voters.

5 : a ≻ b ≻ c 3 : b ≻ c ≻ a 3 : c ≻ b ≻ a
With this profile it is easy to see that a is the Absolute Condorcet loser and that he is both the AV winner, the FV winner and the PAV winner. So, FV and PAV may elect the (Absolute) Condorcet loser when he exists.

By definition, PAV can elect a (Absolute) Condorcet loser only under Rule 1; as Rule 1 of PAV is equivalent to AV, it follows that for a given profile, if PAV elects the (Absolute) Condorcet loser, he is also the AV winner. In the following profile, a is both the Absolute Condorcet loser and the AV winner but b is the PAV winner.

5 : a ≻ b ≻ c 3 : a ≻ c ≻ b 5 : b ≻ c ≻ a 4 : c ≻ b ≻ a
Assume that candidate a is the Absolute Condorcet loser; it follows that S l (a) < n 2 for 1 ≤ l ≤ m -1. Candidate a cannot be the FV winner on this range. He can only be elected at l = m; if so, this means that if he gets the highest score of AV, then he is also the AV winner. The above profile is sufficient to show that the reverse is not true since a is both the Absolute Condorcet loser and the AV winner while c is the FV winner. □

Efficient compromise

The efficient compromise axiom was introduced by Özkal- [START_REF] Özkal-Sanver | Efficiency in the degree of compromise: a new axiom for social choice theory[END_REF] as a trade-off between the quantity and quality of support that a candidate may receive; the quantity refers to the number of voters supporting a candidate, and the quality of support is defined in terms of a candidate's rank in the order of voters' preferences. According to [START_REF] Merlin | Compromise rules revisited[END_REF], for any profile, the efficient compromises are candidates receiving the highest quantity of support at some efficient level of quality. A voting rule is said to satisfy the efficient compromise axiom if and only if it always picks efficient compromises.

Following Özkal- [START_REF] Özkal-Sanver | Efficiency in the degree of compromise: a new axiom for social choice theory[END_REF], the Plurality rule meets the efficient compromise; this is also the case for the q-Approval Fallback Bargaining7

for any q ∈ {1, 2, . . . , n} while the Borda rule and all the Condorcet consistent rules do not. What is more, [START_REF] Merlin | Compromise rules revisited[END_REF] showed that if the set of efficient compromises contains only one candidate, all the scoring rules will pick this candidate. Proposition 4 tells us that AV and PAV may fail the efficient compromise axiom except on the domain where there is an absolute majority winner.

Proposition 4 FV, PAV, and AV do not satisfy the efficient compromise axiom.

FV and PAV always satisfy the efficient compromise axiom over the domain where there is an Absolute Condorcet winner.

Proof To show that FV, PAV, and AV do not meet the efficient compromise axiom, let us consider the following profile8 with four candidates {a, b, c, d} and seven voters;

1 : a ≻ b ≻ d ≻ c 2 : a ≻ c ≻ d ≻ b 2 : b ≻ c ≻ d ≻ a 1 : c ≻ b ≻ d ≻ a 1 : d ≻ c ≻ b ≻ a
With this profile, the reader can check that {a, c, d} is the set of efficient compromises while b is the winner under AV, FV, and PAV.

Notice that if an Absolute Condorcet winner exists he is also an efficient compromise. As previously mentioned, when an Absolute Condorcet winner exists, both FV and PAV are equivalent to PR. Given that PR satisfies the efficient compromise axiom, it will select the Absolute Condorcet winner, just like FV and PAV.

□ Fallback Voting and Preference Approval Voting

Social (un)acceptability

In the search for a certain consensus around a candidate, [START_REF] Mahajne | The socially acceptable scoring rule[END_REF] have introduced the concept of social acceptability. They say that a candidate is socially acceptable if the number of voters who rank him among their most preferred half of the candidates is at least as large as the number of voters who rank him among the least preferred half. [START_REF] Mahajne | The socially acceptable scoring rule[END_REF] showed that there always exist at least one socially acceptable candidate in any profile; and they show that there exists a unique scoring rule that always elects such a candidate, the Half Accepted-Half Rejected rule (HAHR).9 In contrast to a socially acceptable candidate, a candidate is said to be socially unacceptable if the number of individuals who rank him among their least preferred half of the candidates is at least as large as the number of voters who rank him among the most preferred half.

Proposition 5 AV, FV, and PAV may not select a socially acceptable candidate and they may select a socially unacceptable candidate. Following Proposition 2, within the domain where an Absolute Condorcet winner exists, FV and PAV always select a socially acceptable candidate and never select a socially unacceptable candidate.

Proof Consider the following profile with 3 candidates and 6 voters.

2 : a ≻ c ≻ b 1 : a ≻ b ≻ c 1 : b ≻ a ≻ c 2 : c ≻ b ≻ a
In this profile, a is a socially acceptable candidate while b is socially unacceptable and b is the winner under AV, FV, and PAV.

It is obvious that, when he exists, an Absolute Condorcet winner is also a socially acceptable candidate. By Proposition 2, FV and PAV always select this candidate.

Such a candidate cannot be socially unacceptable; he is still elected in the presence of a socially unacceptable candidate. But this may not be the case for AV: to see this, just add a voter with a ≻ b ≻ c ; it follows that a is the absolute majority winner and therefore socially acceptable while the AV winner is b. □

Cancellation property

Before going further, let us raise a point about PAV. By definition, Rule 2 of PAV relies on pairwise comparisons to decide the winner; but what if all the majority duels between the majority-approved candidates end up in tie?

In such a case, should all candidates be declared elected, or only the one(s)

with the highest AV score? This situation does not seem to have been taken into account by [START_REF] Brams | Voting systems that combine approval and preferences[END_REF]. In such a scenario, not choosing all the candidates involved implies a violation of the cancellation criterion. The cancellation condition requires that when all the majority comparisons end up in a tie, all the candidates should be selected [START_REF] Young | An axiomatization of Borda's rule[END_REF]. Admittedly it is a bit difficult to apply the cancellation property to AV, because this rule does not fundamentally depend on rankings. Proposition 6 tells us that FV and PAV fail the cancellation criterion and that this also the case for AV when it is based on rankings.

Proposition 6 AV, FV, and PAV do not meet the cancellation property.

Proof Consider the following profile with 3 candidates and 4 voters.

2 : a ≻ b ≻ c 2 : c ≻ b ≻ a
We can see in this profile that all the pairwise comparisons end up in ties while candidate b is the winner of AV, FV, and PAV. So, AV, FV, and PAV fail the cancellation property. □

Pareto optimality

In a given voting situation, candidate a Pareto dominates candidate b if all the voters strictly prefer a to b. A candidate is said to be Pareto-optimal if there is no other candidate that dominates him. According to [START_REF] Felsenthal | Review of paradoxes afflicting procedures for electing a single candidate[END_REF], the election of a candidate a is not tolerable when there is another candidate b that all voters rank before him. [START_REF] Felsenthal | Review of paradoxes afflicting procedures for electing a single candidate[END_REF] drives the point home by arguing that a voting rule that can elect a Pareto-dominated candidate should be disqualified no matter how low the frequency. A voting rule meets the Pareto criterion if for all voting profiles it never elects a Pareto-dominated candidate.

According to [START_REF] Felsenthal | Review of paradoxes afflicting procedures for electing a single candidate[END_REF], AV may elect a Pareto-dominated candidate.

Proposition 7 tells us that this is not the case for FV and PAV.

The reinforcement condition

According to the reinforcement condition10 (Myerson, 1995) when an electorate is divided in two disjoint groups of voters

N 1 (|N 1 | = n 1 ) and N 2 (|N 2 | = n 2 ) such that N 1 ∩ N 2 = ∅ and N 1 ∪ N 2 = N (|N | = n 1 + n 2 = n),
and
the winner is the same for each group, this outcome will remain unchanged when both groups of voters are merged. It is known that AV, PR, NPR, and BR meet the reinforcement condition (see [START_REF] Felsenthal | Review of paradoxes afflicting procedures for electing a single candidate[END_REF]. Proposition 8 tells us that FV and PAV do not meet the reinforcement condition and it characterizes when this is (not) the case.

Proposition 8 Assume that an electorate is divided in two disjoint groups of voters N 1 and N 2 such that the winner is the same for each group.

Considering that PAV is defined by four rules (Rule 1i, Rule 1ii, Rule 2i, and Rule 2ii), it always meets the reinforcement criterion if the winner in each of the two groups of voters is determined by Rule 1i or Rule 1ii; this is also the case when the winner is determined in one group by Rule 1i and in the other group by Rule 1ii. In the other cases, PAV may fail the reinforcement condition.

FV meets the reinforcement condition if the winner in each group is deter- mined at the same level of rankings. In the other cases, it may fail the reinforcement condition.

Proof See Appendix. □

Homogeneity

Given the voting outcome on a voting profile, if duplicating this profile λ times (λ > 1, λ ∈ N) changes the result, we say that the homogeneity property is not satisfied. The violation of the homogeneity property is a major challenge for collective decision rules [START_REF] Nurmi | A comparison of some distance-based choice rules in ranking environments[END_REF]. It is obvious that AV is homogeneous since duplicating a population also duplicates the approvals in the same magnitude. Proposition 9 tells us the same thing concerning FV and PAV.

Proposition 9 FV and PAV are homogeneous.

Proof Suppose we duplicate a profile π, λ times. On the resulting profile, given a candidate x, we have S l (x, λπ) = λS l (x, π), AV(x, λπ) = λAV(x, π), and nxy(λπ) = λnxy(π). It then follows that if a candidate wins under FV at level l in π, he also wins at the same level in λπ; we reach the same conclusion with PAV. Thus, duplicating a profile does not change the outcome under FV and PAV. □

The No-Show paradox and the Truncation paradox

The No-Show paradox describes a situation under which some voters may do better to abstain than to vote since abstaining may result in the victory of a more preferable or desirable candidate [START_REF] Doron | Single Transferable Vote: An example of a Oerverse Social Choice Function[END_REF][START_REF] Fishburn | Paradoxes of preferential voting[END_REF]. The Plurality rule, the Borda rule, and Approval voting are among the few voting rules not vulnerable to the No-Show paradox [START_REF] Felsenthal | Review of paradoxes afflicting procedures for electing a single candidate[END_REF]. It is known that the vulnerability of a voting rule to the No-Show paradox leads to its vulnerability to the Truncation paradox but the reverse is not always true [START_REF] Nurmi | Comparing Voting Systems[END_REF]. The Truncation paradox occurs when some voters may reach a more preferred outcome by submitting a sincere but incomplete ranking (Fishburn andBrams, 1983, 1984). According to [START_REF] Brams | The AMS nominating system is vulnerable to truncation of preferences[END_REF],

AV is sensitive to the Truncation paradox; this is also the case for NPR and BR but not for PR.11 Proposition 10 characterizes the vulnerability of FV and PAV to the No-Show paradox.

Proposition 10 PAV is vulnerable to the No-Show paradox only when the winner is determined by Rule 2i. FV is not vulnerable to the No-Show paradox only when the winner is determined at level l = 1 or l = m. Thus, FV and PAV are vulnerable to the Truncation paradox.

Proof See Appendix. □

Independence of clones

Following [START_REF] Tideman | Independence of clones as a criterion for voting rules[END_REF] We are now going to summarize all the above results in Table 1. In this table, we recap our findings about PAV, AV, and FV as well as those of [START_REF] Brams | Voting systems that combine approval and preferences[END_REF] and [START_REF] Sanver | Approval as an intrinsic part of preference[END_REF]; besides FV and PAV, we include PR, NPR, and BR. The fact that these rules satisfy or do not satisfy one of the criteria retained here comes from results of the 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] Felsenthal | Review of paradoxes afflicting procedures for electing a single candidate[END_REF]. In Table 1, a "Yes" means that the voting rule meets the supposed criterion 12 and a "No" means it does not.

Table 1 Normative properties of the rules

On the basis of the normative criteria used in our analysis, it appears that FV and PAV satisfy and fail the same criteria; they possess two properties that AV does not: Pareto optimality and the fact of always electing the Absolute Condorcet winner when he exists. AV, for its part, meets two criteria that FV and PAV do not: reinforcement and non-vulnerability to the No-Show paradox.

Approval-based rules, compared to score-based rules, satisfy fewer criteria.

Another way to compare these sets of rules would be to check the frequencies for the criteria they violate. This is what we try to do in the next section, with particular attention to the Condorcet criteria.

Computational analysis

Our aim in this section is to evaluate, for voting situations with three candidates and electorates tending to infinity, the probabilities of some voting events. We have chosen to only present here the main messages that stand out from our calculations, while relegating the details of our calculation approach to Appendix C.13 So, we formally define, for three-candidate elections, the preferences and voting rules in Appendix C.1. The impartial and anonymous culture assumption that we assume for our computations is presented in Appendix C.2.

In our calculations, we focus on the following voting events, already described above:

the agreement between the rules;

FV and PAV may pick the least-approved candidate;

FV or PAV may not pick a unanimously approved candidate;

the satisfaction(resp. the violation) of the Condorcet winner criterion (resp.

the Condorcet loser criterion);

We extend our analysis to the three popular scoring rules (PR, NPR, and BR) and consider comparisons with FV and PAV. This extension is justified by the fact that we have pointed out above that, in some configurations, FV is very close to PR.

Concerning the agreement between the rules under consideration, Table 2 summarizes the probabilities we obtained. According to [START_REF] Ju | Collective choices for simple preferences[END_REF] and [START_REF] Xu | Axiomatizations of approval voting[END_REF], when voters have dichotomous preferences, AV always elects the Condorcet winner when he exists. This is not always the case when voters have rather strict preferences or when indifference is allowed, as shown by [START_REF] Diss | On the condorcet efficiency of approval voting and extended scoring rules for three alternatives[END_REF], Gehrlein andLepelley (1998, 2015),

and [START_REF] Kamwa | Condorcet Efficiency of the Preference Approval Voting and the Probability of Selecting the Condorcet Loser[END_REF]. Considering three-candidate elections with a certain degree of indifference under the extended impartial culture condition, 14 Diss et al. 3. In this table, we denote by CE(R) (resp. CL(R)) the Condorcet efficiency (resp. the 14 Under the impartial culture condition [START_REF] Guilbaud | Les théories de l'intérêt général et le problème logique de l'aggrégation[END_REF] it is assumed that each voter chooses his preference (randomly and independently) on the basis of a uniform probability distribution across all strict orders. The extended impartial culture condition allows dichotomous preferences with complete indifference between two or more candidates. 15 The extended anonymous impartial culture condition allows dichotomous preferences with complete indifference between two or more candidates. 16 Recall that PR always elects the Absolute Condorcet winner when he exists. Fallback Voting and Preference Approval Voting probability of electing the Condorcet loser) given the voting rule R; and we define ACE(R) and ACL(R) similarly. (2020) obtain in their setting. 2016) achieve in their respective frameworks. With a limiting probability of nearly 0.01%, PAV performs significantly better than FV whose probability is raised to nearly 3%. Regarding the election of an Absolute Condorcet loser, our results show that among our rules AV is the most likely to elect such a candidate; PAV performs better than FV which performs better than PR.

To refine the comparisons, we may assess more closely how each of the probabilities in Table 3 reacts to the proportion α = n1+n2+n3+n4+n5+n6 n of voters who approve only one candidate. When α = 1, AV and PR are equivalent. For some values of α, we report in Table 4 the probabilities CE(R, α), ACE(R, α), CL(R, α), and ACL(R, α) as functions of α.

FV 1 1 1 1 1 1 1 PAV 1 1 1 1 1 1 1 PR 1 1 1 1 1 1 1 NPR 0.
NPR 0 0 0 0 0 0 0 BR 0 0 0 0 0 0 0
Table 4 demonstrates that the probabilities vary depending on the value of α. We note that for α = 1, CE(AV, 1) = CE(F V, 1) = CE(P AV, 1) = CE(P R, 1)

and ACE(AV, 1) = 1. In the scenario where the electorate consists solely of voters who approve exactly one candidate, PR, AV, PAV, and FV exhibit identical performance according to the (Absolute) Condorcet winner criterion.

PAV appears to surpass all other rules in terms of Condorcet efficiency for 0 ≤ α < 3/4; for 3/4 ≤ α ≤ 1, BR dominates over other rules. PR tends to dominate FV for 0 ≤ α < 1/2 while we get the reverse for 1/2 ≤ α ≤ 1. PR dominates AV for all α; AV is also dominated by NPR for 0 ≤ α < 1/2. As for electing the Absolute Condorcet winner, AV tends to dominate NPR for α ≥ 1/3 and it dominates BR for α ≥ 2/3.

For any value of α, NPR appears to be the rule most likely to elect the Condorcet loser. It appears that CL(AV, α) decreases with α while CL(P AV, α)

increases with α. CL(F V, α) tends to increase for α going from 0 to reach its maximum at α = 1/2 then decreases. CL(P R, α) and CL(N P R, α) tend to grow for 0 ≤ α < 1/2 then to decrease for 1/2 ≤ α < 1. For α = 1, we find that AV, PR, FV, and PAV have the same probability to elect the Condorcet loser.

For 0 ≤ α ≤ 1/2, AV appears to be the rule most likely to elect an Absolute Condorcet loser; over this interval, ACL(AV, α) tends to decrease with α. We also note that for 0 ≤ α ≤ 1/2, FV and PAV never elect an Absolute Condorcet loser. For 1/2 < α < 1, PR is the most likely to elect an Absolute Condorcet loser; it is followed by AV while PAV performs better than FV. For α = 1, AV, FV, PAV, and PR have the same probability (about 2.47%) of electing the Absolute Condorcet loser.

Concluding remarks

The first objective of this paper was to further develop the analysis of [START_REF] Brams | Voting systems that combine approval and preferences[END_REF] regarding the normative properties of FV and PAV. This is how we managed to show that FV and PAV are Pareto optimal as they never elect a Pareto-dominated candidate; FV and PAV are also homogeneous; FV and PAV always elect the Absolute Condorcet winner when he exists; and that on the domain where there is an Absolute Condorcet winner, these rules always elect a socially acceptable candidate, they never elect a socially unacceptable candidate, and they are resistant to manipulation by clones. Nonetheless, these rules do not meet the Cancellation property or the reinforcement criterion and they are vulnerable to the No-Show paradox and to the Truncation paradox.

We managed to find some conditions under which these rules always meet Our analysis shows that FV and PAV tend to deliver on the promise of being rules that could reconcile the advocates of score rules with those of approval voting. FV and PAV share the simplicity that characterizes AV, yet with scoring rules they share the constraint of ranking candidates, which can be a daunting task when there is a large number of candidates.

voters and with Rule 2ii in an other group, or when a candidate wins through Rule 2i (resp. 2ii) in both groups of voters.

We can give a summary that reflects whether or not the criterion is met as follows:

N 2

Rule 1i Rule 1ii Rule 2i Rule 2ii N 1 candidate in each group at a given level l, he remains elected when both groups are merged.

(ii) At l, a has the greatest score among the majority approved candidates in each group. This means that S l 1 (a

) > S l 1 (b) > n1 2 ≥ S l 1 (c) and S l 2 (a) > S l 2 (b) > n2 2 ≥ S l 2 (c
). What we have in (i) implies that c can never win when the two groups merge.

To complete the proof, let us use some profiles to show that when the same FV winner is determined in two groups at two different levels, he may not remain elected when both groups merge.

Profile 1

2 : a ≻ b ≻ c 1 : a ≻ b ≻ c 2 : b ≻ c ≻ a Profile 2 1 : a ≻ b ≻ c; 1 : b ≻ c ≻ a; 2 : a ≻ b ≻ c; 1 : c ≻ b ≻ a; 2 : b ≻ a ≻ c;
In Consider the configuration where candidate a was the winner under Rule 2i. First, let us assume that b was not among the majority approved candidates (AV(b, π) < n 2 ) and that he wins after abstention. After abstention, AV(b, π)- are such that n-β 2 < AV(a, π) -β < AV(b, π) -β or AV(a, π) -β < n-β 2 < AV(b, π) -β; in each case, these conditions lead to AV(a, π) < AV(b, π), which is a contradiction. Thus, PAV is vulnerable to the No-Show paradox only when the winner is determined by Rule 2i.

β < n-β 2 ; b cannot win if AV(a, π) -β > n-β 2 ; if AV(b, π) -β < n-β 2 , b wins if AV(b, π) -β > AV(a, π) -β which is equivalent to AV(b, π) > AV(a,
B.2. FV is not vulnerable to the No-Show paradox only when the winner is determined at level l = 1 or l = m.

When the FV winner is determined at l = 1, any abstention of voters who do not rank this winner first does not affect the approval of the level l = 1. So, for l = 1, the No-Show paradox never occurs.

Let us assume that a is the FV winner at level l = m and that a group C. Details of the computational analysis

C.1. Preferences and the rules in three-candidate elections

We need to present the rankings and approvals in the particular case of three candidates. For the sake of simplicity, we rule out the possibilities of approving nothing; so, given his ranking, a voter may approve at least one candidate and at most all the running candidates. So, given C = {a, b, c}, the 18 possible types of preferences on C are reported in Table 1. Then, a voting situation is the 18-tuple π = (n 1 , n 2 , . . . , n t , . . . , n 18 ) such that

C = {a, b, c} a ≻ b ≻ c (n 1 ) a ≻ b ≻ c (n 7 ) a ≻ b ≻ c (n 13 ) a ≻ c ≻ b (n 2 ) a ≻ c ≻ b (n 8 ) a ≻ c ≻ b (n 14 ) b ≻ a ≻ c (n 3 ) b ≻ a ≻ c (n 9 ) b ≻ a ≻ c (n 15 ) b ≻ c ≻ a (n 4 ) b ≻ c ≻ a (n 10 ) b ≻ c ≻ a (n 16 ) c ≻ a ≻ b (n 5 ) c ≻ a ≻ b (n 11 ) c ≻ a ≻ b (n 17 ) c ≻ b ≻ a (n 6 ) c ≻ b ≻ a (n 12 ) c ≻ b ≻ a (n 18 )
Given the labels of Table 1, the approval scores S l (.) at level l are provided in Table 2; with three candidates, l varies from 1 to 3.

Table 2 The approval scores S l (.)

Candidates

a b c S 1 (.) n1 + n2 + n7 + n8 + n13 + n14 n3 + n4 + n9 + n10 + n15 + n16 n5 + n6 + n11 + n12 + n17 + n18 S 2 (.) n1 + n2 + n7 + n8 + n9 n3 + n4 + n7 + n9 + n10 n5 + n6 + n8 + n10 + n11 +n11 + n13 + n14 + n15 + n17 +n12 + n13 + n15 + n16 + n18 +n12 + n14 + n16 + n17 + n18 S 3 (.) n1 + n2 + n7 + n8 + n9 + n11 n3 + n4 + n7 + n9 + n10 + n12 n5 + n6 + n8 + n10 + n11 + n12 +n13 + n14 + n15 + n16 + n17 + n18 +n13 + n14 + n15 + n16 + n17 + n18 +n13 + n14 + n15 + n16 + n17 + n18
Notice that S 3 (a) = AV(a, π). Candidate a is the AV winner if the conditions described by Eq. 1 are met.

     S 3 (a) > S 3 (b) S 3 (a) > S 3 (c) (1)
Recall that S 1 (.) = PR(., π). We provide in Table 3 the scores of the candidates under NPR and BR.17

+ n6 + n10 + n12 + n16 + n18 n2 + n5 + n8 + n11 + n14 + n17 n1 + n3 + n7 + n9 + n13 + n15 BR(., π) 2(n1 + n2 + n7 + n8 + n13 + n14) 2(n3 + n4 + n9 + n10 + n15 + n16) 2(n5 + n6 + n11 + n12 + n17 + n18) +n3 + n5 + n9 + n11 + n15 + n17 +n1 + n6 + n7 + n12 + n13 + n18 +n2 + n4 + n8 + n10 + n14 + n16

C.2. The impartial and anonymous culture assumption

When computing the likelihood of voting events, the impartial and anonymous culture (IAC) assumption introduced by [START_REF] Kuga | Voter Antagonism and the Paradox of Voting[END_REF] and [START_REF] Gehrlein | The probability of the paradox of voting: A computable solution[END_REF] is one of the most widely used assumptions in social choice theory literature. Under this assumption, all voting situations are equally likely to be observed; it follows that the probability of a given event is calculated according to the ratio between the number of voting situations in which the event occurs and the total number of possible voting situations.

For a given voting event, the number of voting situations can be reduced to the solutions of a finite system of linear constraints with rational coefficients.

The appropriate mathematical tools to find these solutions are the Ehrhart polynomials.

For a non-exhaustive overview of these techniques and algorithms, we refer to the recent books by [START_REF] Diss | Evaluating Voting Systems with Probability Models, Essays by and in honor of William V. Gehrlein and Dominique Lepelley[END_REF] and Gehrlein andLepelley (2011, 2017). As in this paper we deal with situations where the number of voters tends to infinity, finding the limiting probabilities under IAC is reduced to the computation of volumes of convex polytopes [START_REF] Bruns | The computation of generalized Ehrhart series in normaliz[END_REF][START_REF] Schürmann | Exploiting polyhedral symmetries in social choice[END_REF]. For our computations, we use the software Normaliz [START_REF] Bruns | Polytope volume by descent in the face lattice and applications in social choice[END_REF][START_REF] Bruns | Computations of volumes and Ehrhart series in four candidates elections[END_REF]. 18 It should be noted that the calculations are relatively simple to implement under Normaliz because it is enough to enter the conditions describing an event and the algorithm returns the volume of the corresponding polytope which is the probability of this event.

C.3. Agreement between the rules

First of all, let us look at situations where two rules coincide. Let us take the case where FV and AV agree on candidate a as the winner. We denote Fallback Voting and Preference Approval Voting by P (AV = F V = a) the limiting probability of this event. This probability is in fact equal to a sum of volumes of polytopes to take into account the different scenarios that can occur under FV as described above. For example, the case where the winner of AV is the same as the winner of FV at level l = 1 is described by the inequalities of Eq. 1 and 2; we denote this volume obtained by V 1∩2 (π). In a similar way, we determine the volumes V 1∩j (π) for j = 3, 4, . . . , 11. Thus, we obtain

P (AV = F V = a) = 11 j=2 V 1∩j (π) = 3864518350115 15850845241344
We can therefore deduce P(F V = AV ), the probability of agreement between AV and FV, as follows As pointed out by [START_REF] Brams | Voting systems that combine approval and preferences[END_REF], a least-approved candidate may be a PAV winner under rule 2i; in our framework, this event is fully characterized by the inequalities of Eq. 15 and 19. We then need to compute the volume V 15∩19 (π) that we multiply by 3 to find P(P AV = LAV ), the limiting probability that PAV elects the least-approved candidate as follows:

P(P AV = LAV ) = 3V 15∩19 (π) = 6095207 75497472 ≈ 0.0807339
So, it is thus in nearly 8.07% of cases that PAV can lead to the election of the least-approved candidate. What about FV? Since at level l = m, S l (.) is equal to the AV score, it is obvious that FV cannot elect the least-approved candidate at this level. It follows then that with three candidates, FV can elect the least-approved candidate only at l = 1 or l = 2; this corresponds to Eq. 2 to 6. Thus, P(F V = LAV ) the limiting probability that FV elects the least-approved candidate, is computed as follows: V 21∩j (π) 19 We notice that there is an incompatibility between Eq. 20 (or Eq. 21) and the conditions of Eq. 3. So, with these conditions FV does not fail to pick a unanimously approved candidate. Fallback Voting and Preference Approval Voting one candidate. For some values of α, we report in Table 4 the probabilities CE(R, α), ACE(R, α), CL(R, α), and ACL(R, α) as functions of α.

P(F V = LAV ) = 3

C.7. The election of the Condorcet loser

Let us assume on C = {a, b, c} that a is the Condorcet loser (resp. the Absolute Condorcet loser); using the labels of For our voting situations with three candidates, P(CL), the existence probability of the Condorcet loser and P(ACL) that of the Absolute Condorcet loser, are as follows: P(CL) = P(CW ) and P(ACL) = P(ACW ).

We know from Prop. 3 that FV and PAV may elect the (Absolute) Condorcet loser when he exists. When a voting rule may elect a Condorcet loser (resp. an Absolute Condorcet loser), it is said to be vulnerable to the Borda paradox (resp. to the Absolute Majority Loser Paradox). By definition, a (Absolute) Condorcet loser, when he exists, can never be elected under rule 2 of PAV; this can only be the case under Rule 1. With FV, the Condorcet loser cannot be elected at level l = 1 and the Absolute Condorcet loser can only be elected at level l = 3. We follow the same methodology as for the Condorcet winner efficiency to determine CL(.) (resp. ACL(.)), the limiting probability of electing the Condorcet loser (resp. the Absolute Condorcet loser) when he exists. From our computations, we get: 20

Proposition 7

 7 FV and PAV meet the Pareto criterion. Proof Given π, assume that a is the PAV winner and that he is Pareto-dominated by b. As b Pareto-dominates a, if a voter approves a this is also the case for b; it follows that AV(b, π) ≥ AV(a, π) and b is majority preferred to a since n ba = n. If a wins under Rule 1i of PAV, this means that AV(b, π) < AV(a, π) < n 2 which contradicts AV(b, π) ≥ AV(a, π). If a wins under Rule 1ii of PAV, this leads to AV(a, π) > n 2 and AV(b, π) < n 2 which contradicts AV(b, π) ≥ AV(a, π). If a wins under Rule 2 of PAV, the following three cases can be considered: (i) AV(a, π) > n 2 , AV(b, π) > n 2 , and n ab > n ba , or (ii) AV(a, π) > n 2 > AV(b, π), AV(c, π) > n 2 , and nac > nca for c ∈ C \ {a, b}, or (iii)AV(a, π) > AV(b, π) > n 2 . It turns out that (i) contradicts n ba = n while (ii) and (iii) contradict AV(b, π) ≥ AV(a, π). Thus, b cannot win: PAV meets the Pareto criterion. Given π, assume that a is the FV winner and that he is Pareto-dominated by b. By definition, as b Pareto-dominates a we get S 1 (b) > S 1 (a), and S l (b) ≥ S l (a) for all l > 1. That candidate a wins at a level l implies that n 2 > S l (a) > S l (b) or S l (a) > n 2 > S l (b) or S l (a) > S l (b) > n 2 ; these conditions all contradict that S l (b) ≥ S l (a). So, b cannot be the winner: FV never elects a Pareto-dominated candidate. □

(

  2010) and[START_REF] Gehrlein | The Condorcet Efficiency Advantage that Voter Indifference Gives to Approval Voting Over Some Other Voting Rules[END_REF] conclude that: AV is more likely to elect the Condorcet winner than both PR and NPR; BR performs better than AV.[START_REF] Gehrlein | The Condorcet Efficiency Advantage that Voter Indifference Gives to Approval Voting Over Some Other Voting Rules[END_REF] and El Ouafdi et al. (2020) reach a quite similar conclusion when considering the extended impartial anonymous culture condition.15 When it comes to electing the Absolute Condorcet winner when he exists, El[START_REF] El Ouafdi | On the Condorcet efficiency of evaluative voting (and other voting rules) with trichotomous preferences[END_REF] show in their framework that AV does less well than BR but better than NPR.16 Almost nothing is known about the propensity of FV and PAV to elect the Condorcet winner (resp. the Condorcet loser) when he exists.[START_REF] Kamwa | Condorcet Efficiency of the Preference Approval Voting and the Probability of Selecting the Condorcet Loser[END_REF] investigates the limiting Condorcet efficiency of PAV in three-candidate elections while assuming the extended impartial culture condition; he finds that PAV tends to perform better than AV. Considering the framework developed in this paper, we compute the Condorcet efficiency of AV, FV, PAV, PR, NPR, and BR and their propensity to elect the Absolute Condorcet winner when he exists. We do the same job for the election of the Condorcet loser and of the Absolute Condorcet loser. Our results are summarized in Table

  the reinforcement criterion or are not sensitive to the No-Show paradox. It turns out that FV and PAV satisfy and fail the same criteria; they possess two properties that AV does not: Pareto optimality and the fact of always electing the Absolute Condorcet winner when he exists. AV, for its part, meets two criteria that FV and PAV do not: the reinforcement criterion and nonvulnerability to the No-Show paradox.Even if, by definition, there is a certain advantage of FV and PAV over AV regarding the respect of the Condorcet majority criteria, we wanted to measure the extent of this advantage. Thus, for voting situations with three candidates, we calculated the probabilities that these rules would elect the (Absolute) Condorcet winner or the (Absolute) Condorcet loser. Our analysis shows that in terms of the election of the Condorcet winner, PAV performs better than BR which dominates FV. When it comes to electing the Absolute Condorcet winner, PAV and FV dominate BR, AV, and PR. To prevent the election of an (Absolute) Condorcet loser, FV and PAV perform better than AV and PR.

  Profile 1, a wins at the first level since S 1 (a) = 3, S 1 (b) = 2, and S 1 (c) = 0; he also wins with Profile 2 at level 2 since S 1 (a) = S 1 (b) = 3, S 1 (c) = 1, S 2 (a) = 5, S 2 (b) = 4, and S 2 (c) = 1. When both profiles are merged, b wins since S 1 (a) = 6, S 1 (b) = 5, S 1 (c) = 1, S 2 (a) = 8, S 2 (b) = 18, and S 2 (c) = 1. So, FV may fail the reinforcement criterion when the winner in both groups is elected at two different levels of preferences. B. Proof of Proposition 10 B.1. PAV is vulnerable to the No-Show paradox only when the winner is determined by Rule 2i.

  π): this contradicts AV(a, π) > n 2 . So, it not possible to favor b. Let us now assume that b was among the majority approved candidates (AV(b, π) > n2 ) and that he wins after abstention. It is obvious after abstention that b cannot win ifAV(a, π) -β > n-β 2 . After abstention, if AV(a, π) -β < n-β 2 ,two cases are possible: If AV(a, π) > AV(b, π), it is not possible to favor b; let us show how. Given AV(a, π) > AV(b, π), if AV(b, π) -β > n-β 2 and b wins, this means that AV(b, π) > AV(a, π); we get a contradiction. For AV(b, π)-β < n-β 2 , b wins if AV(b, π)-β > AV(a, π)-β which is tantamount to AV(b, π) > AV(a, π): we get a contradiction. If AV(a, π) < AV(b, π), -it is possible to favor b since it is possible to get AV(b, π) -β > n-β 2 such that b wins as illustrated by the following profile with 3 candidates and 19 voters.

  of β voters try to favor a more preferred candidate b by abstaining. Assume at l = m that a is the only majority approved candidate, this means that S m (a) > n 2 > S m (b); after abstention, we may get (i) S m (a) -β > n 2 and S m (b) -β < n 2 or (ii)S m (a) -β < n 2 and S m (b) -β < n 2 . Candidate a remains the winner under (i); candidate b wins under (ii) if S m (a)-β < S m (b)-β which is equivalent to S m (a) < S m (b): this contradicts that a was the only majority approved candidate. Let us now assume that a and b are among the majority approved candidates; since a wins, this means that S m (a) > S m (b) > n 2 . After truncation, we can get S m (a) -β > S m (b) -β > n 2 or n 2 > S m (a) -β > S m (b) -β; in each case, b cannot be the winner. It follows that FV is not sensitive to the No-Show paradox when the winner is determined at level l = 1 or l = m. Now, let us assume that a is the FV winner at level l (l ̸ = 1, m) and consider the following profile with 12 voters and 3 candidates. 2 : a ≻ b ≻ c; 1 : a ≻ c ≻ b; 4 : b ≻ a ≻ c; 2 : b ≻ c ≻ a; 1 : c ≻ a ≻ b; 1 : c ≻ b ≻ a; 1 : c ≻ b ≻ a; With this profile, no candidate wins at l = 1 since S 1 (a) = S 1 (c) = 3 and S 1 (b) = 6; at l = 2, S 2 (a) = 8, S 2 (b) = 7, and S 2 (c) = 4: candidate a wins. Assume that the 4 voters with b ≻ a ≻ c abstain. In the new profile, we get: S 1 (a) = S 1 (c) = 3, S 1 (b) = 2 at l = 1 and no one wins; S 2 (a) = S 2 (c) = 4 and S 2 (b) = 3 and no one wins. At l = 3, S 3 (a) = S 3 (c) = 4 and S 3 (b) = 5 and b wins; by abstaining, the 4 voters have favored b who is preferred to a. Thus, FV is vulnerable to the No-Show paradox when the winner is determined at level of approval l ̸ = 1 and l ̸ = m.Since the vulnerability of a voting rule to the No-Show paradox leads to its vulnerability to the Truncation paradox, FV and PAV would therefore be vulnerable to the Truncation paradox. Preference truncation is efficient under FV and PAV only if it consists, as shown by[START_REF] Brams | Voting systems that combine approval and preferences[END_REF], in a contraction of the set of approved candidates.

P

  (F V = AV ) = 3P (F V = AV = a) = 3864518350115 5283615080448Note that the calculation of (F V = P AV = a) requires us to review 7 × 10 = 70 possible configurations; among these configurations only 29 are possible because of the incompatibilities between the conditions. Proceeding in a similar way and including the scoring rules in our analysis, we obtain:

  unanimously approved candidate may not win underFV or PAVAs[START_REF] Brams | Voting systems that combine approval and preferences[END_REF] note, there may be times when FV and PAV do not elect a unanimously approved candidate. This marks another point of dissonance between these rules and AV. By definition, this can only occur with PAV under Rule 2i. Let us assume on C = {a, b, c} that b is unanimously approved. In our framework, this is tantamount to:n 1 + n 2 + n 5 + n 6 + n 8 + n 11 = 0 (20)If b and c are both unanimously approved, we getn 10 + n 12 + n 13 + n 14 + n 15 + n 16 + n 17 + n 18 = n(21)Given Eq. 20, situations where a is the PAV winner while b (resp. c) is unanimously approved occur when Eq. 14 or 16 (resp. Eq. 15 or 16) hold. The case where both b and c are unanimously approved while a is the PAV winner can only occur if Eq. 16 holds. Then, P(P AV ̸ = U ap) the limiting probability that PAV fails to elect a unanimously approved candidate is computed as follows:P(P AV ̸ = U ap) = 3 2 V 20∩14 (π) + V 20∩16 (π) -V 21∩16 (π)to pick a unanimously approved candidate when Eq. 2 or 4 or 5 or 6 holds. Then, P(F V ̸ = U ap), the limiting probability that FV fails to elect a unanimously approved candidate, is computed as follows: 19 P(F V ̸ = U ap)

□

  Proposition 2 FV and PAV always elect the Absolute Condorcet winner when he exists.Proof Assume that candidate a is the Absolute Condorcet winner. As he is ranked first by more than half of the voters, AV(a, π) > n 2 and n ab > n ba for all b ∈ C \ {a}.

Under PAV, if a is the only one to be majority approved, he is obviously elected; if there are more candidates majority approved, a is elected since he is the Condorcet winner. So, PAV always elects the Absolute Condorcet winner. Since a is the Absolute Condorcet winner we get S 1 (a) > n 2 : by definition, he is the FV winner. So, FV always elects the Absolute Condorcet winner. □

Table 2

 2 Limiting probabilities of agreement

		FV	PAV	AV	PR	NPR	BR
	FV	1	0.7474874 0.7314156 0.6603448 0.7077614 0.7714232
	PAV	0.7474874	1	0.6714614 0.7993055 0.6556436 0.8661731
	AV	0.7314156 0.6714614	1	0.6032491 0.5779744 0.6428802
	PR	0.6603448 0.7993055 0.6032491	1	0.5301230 0.7946785
	NPR	0.7077614 0.6556436 0.5779744 0.5301230	1	0.7197796
	BR	0.7714232 0.8661731 0.6428802 0.7946785 0.7197796	1

Table 3

 3 Voting rules and the limiting probabilities of the Condorcet principleIt emerges that PAV is the best-performing rule in terms of Condorcet efficiency; it is followed by BR. FV performs better than AV but worse than PR. Interestingly, within our framework, AV emerges as the rule with the

		CE(R)	CL(R)	ACE(R)	ACL(R)
	AV	0.6461261 0.0898578 0.8099504 0.0293452
	FV	0.7600535 0.0300712	1	0.0001114
	PAV	0.9973310 0.0001028	1	0.0000249
	PR	0.8326151 0.0340336	1	0.0139566
	NPR	0.6803188 0.0359394 0.7303018	0
	BR	0.9044277	0	0.9944123	0

lowest Condorcet efficiency, indicating that it performs worse than scoring rules in this context. The fact that AV performs worse than PR and NPR here contrasts with what Diss et al. (2010), Gehrlein and Lepelley (2015), and El Ouafdi et al. (2020) achieve in their different settings. As for electing the Absolute Condorcet winner when he exists, AV performs worse than BR but better than NPR. This conclusion is in agreement with what El Ouafdi et al.

Table 3

 3 also tells us that in our analytical framework, AV is the rule most likely to elect the Condorcet loser when he exists; it does less well than PR and NPR. This result contrasts with what El Ouafdi et al. (2020) or Gehrlein et al. (

Table 4

 4 Some computed values of CE(R, α), ACE(R, α), CL(R, α), and ACL(R, α)

						α
		Rules	0	1/4	1/3	1/2	2/3	3/4	1
		AV	0.5384051	0.5916563	0.6396992	0.7544142	0.8361545	0.8590698	0.8814815
	CE(R, α)	FV	0.7818569	0.7379713	0.7497197	0.8356119	0.8517430	0.8648282	0.8814815
		PAV	1	0.9999867	0.9998151	0.9911858	0.9297356	0.8965582	0.8814815
		PR	0.8484781	0.8330283	0.8276168	0.8376708	0.8620404	0.8713166	0.8814815
		NPR	0.6639015	0.6798728	0.6855510	0.6750562	0.6493909	0.6397497	0.6296296
		BR	0.9061312	0.9045864	0.9037684	0.9050865	0.9089313	0.9101536	0.9111111
		AV	0.5482718	0.7196296	0.8260673	0.9647654	0.9961465	0.9989699	1
	ACE(R, α)

  Consider a voting situation where candidate a is PAV winner. Assume a group of β voters (β ≥ 1) who decide to not show up in order to favor a more preferred candidate b. Obviously, if these voters do not approve of candidate a in the original profile, the maneuver is futile. Suppose now that these voters approve candidate a in the original profile. When they abstain, the AV score of each candidate they approved decreases by β. Let us discuss each of the possible configurations.

	It is known that AV is not vulnerable to the No-Show paradox (see Felsenthal,
	2012); as Rule 1 of PAV is equivalent to AV, it follows that under Rule 1, PAV
	is not vulnerable to the No-Show paradox.

Table 1

 1 The 18 types of rankings and approvals on

Table 3

 3 Scores of the candidates under NPR and BR

			Candidates
		a	b	c
	NPR(., π)	n4

  Table 1, this is equivalent to Eq. 23 (resp.

	Eq. 24).
	
	   	n ab < n ba n ac < n ca	(23)	NPR(a, π) >	n 2	(24)

Notice that the first formal introduction of this framework in terms of ordinal versus cardinal preferences is made in[START_REF] Sanver | Approval as an intrinsic part of preference[END_REF].

Notice that FV is called "Majoritarian Approval Compromise" in[START_REF] Sanver | Approval as an intrinsic part of preference[END_REF] and it is an adaptation of the Majoritarian Compromise rule of[START_REF] Sertel | Lectures notes in microeconomics[END_REF] or[START_REF] Sertel | The majoritarian compromise is majoritarian optimal and subgame perfect implementable[END_REF].

[START_REF] Kamwa | Condorcet Efficiency of the Preference Approval Voting and the Probability of Selecting the Condorcet Loser[END_REF] is the only paper to our knowledge that has paid particular attention at least to PAV;[START_REF] Kamwa | Condorcet Efficiency of the Preference Approval Voting and the Probability of Selecting the Condorcet Loser[END_REF] investigated the propensity of PAV to elect the Condorcet winner or the Condorcet loser.

Notice that we stop going down once we reach the approval line for a voter that may be placed differently given different voters.

q-Approval Fallback Bargaining winners are the candidates receiving the support of q voters at the highest possible quality.

This profile is adapted from Özkal-[START_REF] Özkal-Sanver | Efficiency in the degree of compromise: a new axiom for social choice theory[END_REF].

For m even, HAHR is equivalent to the m 2 -approval rule.

This condition is also known as the Separability axiom in[START_REF] Smith | Aggregation of preferences with variable electorate[END_REF] or the Consistency axiom in[START_REF] Young | Social Choice scoring functions[END_REF].

For more details on the Truncation paradox and its occurrence under the scoring rules, we refer to[START_REF] Kamwa | Scoring Rules, Ballot Truncation, and the Truncation Paradox[END_REF] and[START_REF] Kamwa | Susceptibility to manipulation by sincere truncation: the case of scoring rules and scoring runoff systems[END_REF].

For reasons of space, we cannot present the detailed calculations here. These calculation details are available upon request.

t=1 n t = n.

With three candidates, the Borda rule gives 2 to a candidate each times he is ranked first, 1 point when he is second, and 0 when he is ranked last.

To more on Normaliz, we refer the reader to the paper of[START_REF] Bruns | The computation of generalized Ehrhart series in normaliz[END_REF] or the website dedicated to this algorithm, https://www.normaliz.uni-osnabrueck.de.

It turns out that among the rules under consideration, BR is the one with the highest probability of agreement with each of the other rules. In at least 66% of the cases, FV agrees with each of the other rules and it tends to agree more with PAV (74.75%) than with AV (73.14%), and more with NPR (70.77%) than with PR (66.03%). PAV tends to more agree with PR (79.93%) than with AV (67.15%) or with NPR (65.56%). Not surprisingly, AV tends to agree more with FV and PAV than with scoring rules. Regarding scoring rules, PR and BR tend to agree the most with PAV. The general observation derived from Table 2 suggests that the combination of approvals and rankings in FV and PAV tends to align them more closely with scoring rules rather than AV, particularly in terms of agreement. [START_REF] Brams | Voting systems that combine approval and preferences[END_REF] showed that for the same preference profile, AV, FV, and PAV can elect completely different candidates. From our computations, we found that for the same voting profile, PAV, AV, and FV elect the same winner in about 58.86% of cases; they therefore diverge in about 41.13% of cases.

When it comes to the election of a least-approved candidate, this occurs in 8.07% of cases under PAV while it occurs in 4.95% of cases under FV. FV would therefore be almost half as likely to elect a least-approved candidate than PAV. This result would tend to confirm the fact that in terms of agreement, AV coincides more with FV than PAV. Another point of dissonance between FV, PAV, and AV appears when FV and PAV do not elect a unanimously approved candidate. We found that in almost 18.89% of the cases PAV may not elect a unanimously approved candidate, while this is the case in only 8.58% of the cases for FV.

Appendices A.Proof of Proposition 8

Assume that an electorate is divided into two disjoint groups of voters N 1

A.1. PAV and the reinforcement criterion

We know that AV is equivalent to Rule 1 of PAV; since AV meets the reinforcement condition, it follows that PAV meets the reinforcement condition if the winner in each group is elected by Rule 1i or 1ii. To complete the proof, let us show that this is no longer the case in the other configurations. So, consider the following profiles

It is easy to check that a is elected in each of the seven profiles: through Rule

A.2. FV and the reinforcement criterion

Assume that candidate a is the FV winner at level l in both groups N 1 and N 2 . Let us denote by S l j (a) the l-level score of a in group j (j = 1, 2). We distinguish two cases:

(i) at l, a is the only majority approved candidate in each group. This means for all other candidate b, we get

Consider the profile obtained when both populations are merged and assume that b wins at a given level r. It is obvious that we get a contradiction for

Since it is assumed that a is the only majority approved candidate in each group at l, it follows that for all r < l, we get S r j (a)

Therefore, when both groups are merged, it is impossible at level r for b to be majority approved or to score more than a. So, if a is the only majority approved

In this profile, AV(a, π) = 10, AV(b, π) = 13, and AV(c, π) = 5. Candidates a and b are majority approved and a wins since n ab = 10 > n ba = 9.

Assume that the 3 voters with b ≻ a ≻ c abstain. In the new profile π ′ with 16 voters, the scores are AV(a, π ′ ) = 7, AV(b, π ′ ) = 10, and AV(c, π ′ ) = 5: b wins since he is now the only majority approved candidate.

-it is possible to favor b since it is possible to get AV(b, π) -β < n-β 2 such that b wins as illustrated by the following profile with 3 candidates and 18 voters. Given π, if candidate a is the FV winner, the following scenarios are possible:

Candidate a is the only majority approved candidate at l = 1; this is fully described by Eq 2.

No one wins at l = 1 and a is the only candidate majority approved at l = 2.

In this case, we get Eq 3.

No one wins at l = 1 and a with b (or c) are majority approved at l = 2; a gets more approvals than b (or c) at this stage. This situation is characterized by Eq 4 or Eq 5.

No one wins at l = 1 and a, b, and c are majority approved at l = 2. At this stage, a gets more approvals than b and c. In this case, we get Eq 6.

There is no winner at both l = 1 and l = 2 and a is the only candidate who is majority approved at l = 3. This situation is characterized by Eq 7.

There is no winner at l = 1 and l = 2: a with b (or c) are majority approved at l = 3. In this case, we get Eq. 8 or Eq 9.

No candidate is majority approved at l = 1, 2 but they are all majority approved at l = 3; a gets more approvals than b and c. This situation is characterized by Eq 10.

No candidate is majority approved at l = 1, 2, 3 and a gets more approvals than b and c. This situation is characterized by Eq. 11.

If we assume that candidate a is the PAV winner, the following five scenarios are possible:

no candidate gets a majority of approvals and a gets the highest number of approvals; this is fully described by Eq. 12.

only a gets a majority of approvals; in this case, we get Eq. 13.

a and b (or c) get a majority of approvals and a is majority preferred to b (or to c); this leads to Eq. 14 (or Eq. 15). Fallback Voting and Preference Approval Voting all the three candidates get a majority of approvals and a majority dominates b and c; this is described by Eq. 16.

all the three candidates get a majority of approvals, there is a majority cycle and a gets the highest number of approvals; we thus get Eq. 17 or 18. We summarize our results in Table 2.

Using the same approach as above, we were able to determine P(F V = AV = P AV ), the limiting probability that AV, FV, and PAV agree on the same profile.

Using the conditions of Eq. 22, Normaliz gives us the probability P (a = CW ) that a is the winner of Condorcet over π.

P (a = CW ) = 20129 65536

In the same way, we determined the probability that a is the Absolute Condorcet winner (i.e. S 1 (a) > n 2 ):

We therefore deduce P(CW ), the existence probability of the Condorcet winner, and P(ACW ), that of the Absolute Condorcet winner: CL(N P R) = 787367474789 21908225820672 ; We were willing, as we did in the previous section, to refine our findings based on α the proportion of voters who approve of exactly one candidate.

The probabilities CL(R, α) and ACL(R, α) that we obtained in this regard are provided in Table 4.


M Sahnoun
email: sahnoun@univ-metz.fr

G Bourhis
email: bourhis@univ-metz.fr

Haptic feedback to assist powered wheelchair piloting

Keywords: assistive technology, haptic feedback, human-machine interaction, electric wheelchair aides techniques, retour d'effort, interaction humain-machine, fauteuil roulant électrique

The objective of this study is to implement a force feedback joystick on a smart electric wheelchair provided with a set of range sensors. The force feedback is calculated according to the proximity of the obstacles and help the user, without forcing him, to move towards the free direction. The first stage of the project consists in validating the interest of this method of control.

In this paper we present our methodology and some first experimental results.

Introduction

A recent American study relating to the interview of 200 rehabilitation clinicians showed that for approximately 10% of patients an electric wheelchair is difficult even impossible to use in the everyday life [START_REF] Fehr | Adequacy of power wheelchair control interfaces for persons with severe disabilities : a clinical survey[END_REF]. Moreover, questioned more specifically on the manoeuvres tasks, 40% of patients report difficulties. However, at the end of the eighties, to alleviate the difficulties of these people, some research teams have tried to give to the electric wheelchair a certain "intelligence" [START_REF] Bourhis | The VAHM robotized wheelchair : system architecture and humanmachine interaction[END_REF], [START_REF] Bourhis | Autonomous vehicle for people with motor disabilities[END_REF].

The "intelligence" of the wheelchair may be defined as the capacity to perceive its external environment and to deduce relevant information in the objective of carrying out autonomous or semi-autonomous movements: obstacle avoidance, doors passing, docking, path following, … If several prototypes of smart wheelchairs with high level functionalities are available in the research laboratories, to our knowledge none has reached the commercial stage [START_REF] Nisbet | Who's intelligent ? Wheelchair, driver or both ?[END_REF]. In particular, the control of a wheelchair in automatic mode poses two major problems, a technical problem and a psychological one. From the technical point of view, a perfect reliability of an autonomous motion supposes to use a sophisticated set of environment sensors and a heavy data-processing treatment not very compatible with the requirements of such an application as regards cost. From the psychological point of view many potential users on the one hand apprehend to leave the whole control of the movement to the machine, on the other hand wish to use their residual motor capacities as well as possible.

When the physical capacities of the user allow it we can mitigate the problem of reliability by controlling the wheelchair in a "shared" mode: the order and the direction of movement are given by the user, the machine, thanks to its environment sensors (ultrasonic rangefinders usually), helps him to avoid the obstacles. The person is thus always free to stop or continue the movement. This type of assisted control presents nevertheless some limitations. In particular certain movements like pushing a slightly opened door become impossible. The psychological drawbacks of the automatic mode do not disappear either: the person loses the control of the movement partly since he divides it with the machine. This can disturb strongly some users, the direction of displacement being not always that proposed via the human-machine interface.

A method to assist the control of the wheelchair while leaving the pilot his whole free will consists in implementing a force feedback on the control joystick depending on the obstacles proximity. We can then speak about an "assisted" control mode: the control of the wheelchair is entirely of the responsibility of the person, the machine, as a movement supervisor, only transmits haptic information to him to enrich the natural visual feedback. In this context the technical and psychological limitations of the automatic and semi-automatic modes do not appear any more.

However it remains to be demonstrated that the control performances will be improved to a significant degree compared to a usual piloting of the wheelchair: it's the objective of this study.

Justification

The control of an "intelligent" wheelchair by a person with disability opens research problematics close to those met in teleoperation [START_REF] Bourhis | The VAHM robotized wheelchair : system architecture and humanmachine interaction[END_REF]. In particular the human-machine interaction is an essential factor to optimize. Thus, many studies have related to the transmission of information from the disabled person who, by hypothesis, has very limited motor capacities, towards an assistive technology device (mobility aid, manipulation aid or communication aid). On the other hand the information feedback from the machine towards the human remains, at the present time, insufficiently explored. It concerns essentially visual feedback associated in certain cases with sound information (voice synthesis). The sense of touch (considered in the broad sense of an "haptic" return i.e. including tactile, proprioceptive and kinaesthetic information), if it is naturally requested for people with visual impairment, is only very rarely used for assisted devices intended for people with motor disabilities. Some work in this way was however reported in the literature. In [START_REF] Brienza | A force feedback joystick and control algorithm for wheelchair obstacle avoidance[END_REF] a joystick was specifically conceived to test in an entirely modelled environment an algorithm of "passive" force feedback (the joystick resists to a movement towards an obstacle) and an algorithm of "active" force feedback (the joystick moves the wheelchair away from the obstacles). The "active" algorithm being proven more effective, it was tested on 5 people with disability [START_REF] Protho | An evaluation of an obstacle avoidance force feedback joystick[END_REF]: for 4 of them the number of collisions in a course test has decreased compared to a piloting without force feedback. In [START_REF] Hong | Shared-control and force reflection joystick algorithm for the door passing of mobile robot or powered wheelchair[END_REF] the authors describe an algorithm of the "active" type based on the potentials method modified: to circumvent the difficulty in passing the doors with this method the authors, to calculate the repulsive force, only take into account the obstacles located at +/-30° in the forward direction of the wheelchair.

In another context, the human-computer interaction, some tests with people with disabilities also showed that a force feedback interface could improve the performances obtained in a pointing task [START_REF] Keates | Investigating the use of force feedback for motion impaired users[END_REF]. These results are corroborated by a study described in [START_REF] Repperger | A study on spatially induced "virtual force" with an information theoretic investigation of human performance[END_REF] bearing on a group of 10 people with motor disabilities.

Other works described in the literature relate to the teleoperation of a mobile assisted by a force feedback. These applications only concern users without disability but their conclusions are indicative all the same on the potential of the method. Thus in [15] experiments are carried out in simulation concerning the teleoperation of a mobile base in hostile environments. The authors note a significant reduction in the number of collisions by using a force feedback joystick compared to a usual one. The duration and the length of the ways on the other hand are only little modified from one situation to another. A similar experimentation in [16], carried out using a 3D force feedback device PHANToM TM restricted to 2D, leads to the same conclusions: the force feedback decreases the collisions without increasing the duration of navigation significantly. However performance measurements are not always sufficient to validate the interest of the force feedback: in [17], mental workload evaluation during the teleoperation of an helicopter lead to the conclusion that certain force feedback calculation algorithms improve the performance but significantly increase the mental workload.

Methodology

Experimental environment

The force feedback calculation is carried out, by hypothesis, according to the proximity of the obstacles measured by range sensors. An experimentation in real conditions thus requires to get a wheelchair equipped with a set of environment sensors. We'll use the robot resulting from the VAHM project (French acronym for "Autonomous Vehicle for People with Motor disabilities") initiated in 1989 in the University of Metz. The objective of this project is to facilitate the control of electric wheelchairs by using methods and technologies coming from mobile robotics [START_REF] Bourhis | Autonomous vehicle for people with motor disabilities[END_REF]. Two prototypes of this smart wheelchair are currently available, both equipped with a belt of 16 ultrasonic sensors, with a dead-reckoning system and with a computer implemented to the back of the wheelchair.

In a first stage, to be free from the technical problems inherent to the tests in real situation, the experiments are carried out in simulation: the environment is represented in 2 dimensions, the force feedback joystick (Microsoft Sidewinder TM Force Feedback Joystick 2) moving a cursor in this environment. Simulation is programmed under Matlab/Simulink TM . It is made up of three main building blocks:

The "joystick interface" block makes it possible to read the position of the joystick and to apply to him a force adjustable in amplitude and direction.

The "graphic animation" block translates the joystick position into a robot motion which it displays on a 2D animation (Figure 1). The possible collisions are underlines by a change of colour of the mobile. The dimensions of the mobile and of the environment are selected in order to correspond to realistic situations. It is the same for the speed of the wheelchair which maximum is fixed to 0.5m/s.

The "force feedback" block reads at regular rate the distances data obtained by the 16 ultrasonic sensors and deduces a force feedback on the joystick.

Force feedback calculation

The principle of the force feedback calculation consists in applying a force to the joystick in the most adapted free direction, i.e. the direction which corresponds the "best" to that indicated by the pilot. The main difficulty is to define this direction. It is important to note that this method does not prohibit any movement decided by the person. We only make the motions leading to a collision more difficult.

A first series of experiments reported in [18] have allowed to validate the experimental system. The force feedback calculation was based on the "potentials method": each obstacle detected by an ultrasonic sensor emits a repulsive force inversely proportional to its distance to the wheelchair; the force feedback applied to the joystick is the vectorial sum of all these forces. The results obtained by this method are not very convincing, in particular in very constrained environments (doors passages). This had already been noted in the literature in the context of the shared control of an electric wheelchair [START_REF] Borenstein | The Vector Field Histogram -Fast Obstacle Avoidance For Mobile Robots[END_REF].

We propose in this paper to calculate the force feedback by two algorithms described in [START_REF] Levine | The Navchair assistive wheelchair navigation system[END_REF] and [START_REF] Borenstein | The Vector Field Histogram -Fast Obstacle Avoidance For Mobile Robots[END_REF], the VFH algorithm (Vector Field Histogram) and the MVFH algorithm (Modified Vector Field Histogram). They indeed were initially conceived to mitigate the deficiencies of the potentials method and were tested successfully on several prototypes of smart wheelchairs [START_REF] Levine | The Navchair assistive wheelchair navigation system[END_REF], [20]. The principle of the VFH algorithm is as follows:

We build an occupation grid around the wheelchair, a cell being incremented with each measurement of the presence of an obstacle and being regularly decremented along the time (factor of lapse of memory).

We deduce a polar histogram (Figure 2) representing the density of obstacles around the wheelchair (the significant values represent close or large-sized obstacles).

We choose as force feedback direction the free direction nearest to the one indicated by the pilot via the joystick. This algorithm was defined initially to carry out a shared control of the wheelchair: the forward direction is then that indicated above as being the force feedback direction. The authors have noted certain difficulties for passing doors of standard size (0,76m for a wheelchair of width 0,63m) and also that, with this method, significant changes in the direction selected by the pilot may not The application context of our study not being the same one (a force feedback is applied but we don't impose any motion to the wheelchair) we are going to test in what follows two algorithms, the VFH and the MVFH, to confirm or invalidate the results obtained above.

Results and discussion

The results which follow concern a panel of 6 experimenters without disability. Each of them, after a training phase, guide 3 times the virtual wheelchair in the test environment of Figure 1 using the joystick according to various experimental conditions: without force feedback ("without FF"), with force feedback calculated by the VFH algorithm and with force feedback calculated by the MVFH algorithm. Moreover each one of these three options is realized with two kinematics configurations for the virtual wheelchair: the driving wheels may be backward or forward, which constitutes an usual option of the electric wheelchairs. In each case we record three parameters significant of the operator performance in the guidance task: the duration of the task, the distance covered and the number of collisions. Of course these parameters are not independent.

First of all, from the observation of the experiments and from the results below we can deduce some qualitative considerations concerning the parameters "Distance" and "Time". The differences in distances covered, the environment being identical for all the tests, are primarily due to the operations carried out to go out of blocking situations. Thus this parameter is strongly correlated with the number of collisions and does not seem a significant comparison element between the navigation methods. The variations of courses durations seem also difficult to exploit. Indeed they are related to the pilot's behaviour: if he accelerates the wheelchair, he decreases the duration of the course but he increases the collision risks, collisions which, if they occur, increase the course duration. Additional experiments will be necessary to evaluate the relevance of this time criterion to compare the methods of wheelchair control. However we can henceforth note that generally this parameter of time is smaller with the force feedback than without this one.

On the other hand the number of collisions appears directly related to the control mode. For 5 experimenters among 6 the use of the force feedback clearly decreases this factor. This corroborates the results reported in the literature. Quantitatively, the MVFH algorithm does not seem to bring of significant improvement compared to the VFH. We observe however an appreciably better behaviour of the MVFH in the passages of doors compared to the VFH and conversely in the corridors (the trajectory is less stable).

The results of the 4 th experimenter are more atypical: the force feedback decreases considerably its performances considering the number of collisions. This is probably due to the fact that he's an usual player of video games and, consequently, he's particularly skilful to use the traditional joystick to guide a mobile. This observation does not call into question the utility of this study since it is intended to people which have difficulties in the electric wheelchair control using a traditional joystick.

Table 1 presents the results for the two basic kinematics configurations for an electric wheelchair: rear and front driving wheels. The strategy of navigation is very different according to the configuration but this fact doesn't influence the remarks made above. This will have undoubtedly to be confirmed on more specific tests in very constrained environments.

Lastly, to try to evaluate the comfort of navigation, it is planned for the continuation of our experiments to associate the usual performance criteria an estimation of the person mental workload. A method containing questionnaires, the NASA-TLX method ("Task Load Index") [START_REF] Pino | Performance measurement of a man-machine system: application to the control of a powered wheelchair[END_REF], might be used for this purpose.

Conclusion

The project above described aims at conceiving a new control mode of electric wheelchair. It is intended for people for whom control by a traditional joystick (or any other adapted sensor) is difficult or impossible because of too severe motor disabilities. It is initially a question of validating the interest of a force feedback to assist the wheelchair control. The first tests reported in this paper have been related to a panel of people without disability in order to elaborate the experimental apparatus and the algorithms. This system being a simulator, it will make it possible to carry out experiments with people with severe motor disabilities without the constraints of safety and reliability which the tests in real conditions imply. If the interest of the "assisted" control mode is validated by the experiments in simulation, the final stage of the project will consist in transposing this system on the smart wheelchair VAHM.

Figure 1 .

 1 Figure 1. 2D test environment; The task consists in guiding the virtual mobile from the initial

Figure 2 .

 2 Figure 2. Polar histogram (VFH algorithm): we represent in ordinates the obstacles density in

  generate any variation of direction of the mobile[19]. Thus they proposed a modified algorithm, the MVFH algorithm, which, during the calculation of the movement direction, minimizes the sum of the histogram and of a parabolic function centred on the direction desired by the person (Fig.3). This one can thus carry out little local deviations of the trajectory. In particular, the door passing manoeuvres are improved by this way.

Figure 3 .

 3 Figure 3. Polar histogram (MVFH algorithm); the polar histogram resulting from the VFH method

Table 1 .

 1 Experimental results for a rear-wheel drive wheelchair (RWD) and a front-wheel drive wheelchair (FWD) (the values indicated are averages on 3 tests)

	Operators	Joystick	Collisions	Distance(m)	Time (s)	Collisions	Distance(m)	Time (s)
			(RWD)	(RWD)	(RWD)	(FWD)	(FWD)	(FWD)
	1	Without FF	15	620	122	12	647	133
		VFH	10	584	111	7	607	115
		MVFH	3	588	107	8	628	124
	2	Without FF	11	638	161	16	609	157
		VFH	9	604	168	8	658	131
		MVFH	11	637	181	9	643	125
	3	Without FF	29	695	160	39	727	205
		VFH	15	593	121	25	662	158
		MVFH	10	597	111	18	679	157
	4	Without FF	1	583	119	1	628	144
		VFH	7	581	112	1	606	113
		MVFH	4	588	108	7	613	115
	5	Without FF	15	586	123	13	678	180
		VFH	11	585	128	9	629	144
		MVFH	3	588	121	22	669	152
	6	Without FF	20	587	108	15	639	123
		VFH	9	578	101	3	612	111
		MVFH	7	600	109	6	618	109