Liseth Pasaguayo
email: lisethpasaguayoec@ieee.orgzeina.al.masry@ens2m.frnoureddine.zerhouni@femto-st.fr

Zeina Al Masry

Sergio Lescano
email: sergio.lescano@amarob.com

Noureddine Zerhouni

Critical Components' Selection Methodology of a Microgripper for Intracorporeal Surgegy

Prognostics and Health Management (PHM) is widely used to study the health state of the system. However, the application of PHM for micro medical devices is a big challenge since they are made up of multiple components which are complex. Prognostics approaches for complex microsystems should be oriented towards identifying critical components and monitoring them individually. This implies the importance of identifying as much as possible the components that can lead to system failures. This work proposes a methodology to select critical components of a micro medical device for PHM implementation. The micro device is a microgripper composed of four components and four steel wires of 0.08 mm in diameter. A risk analysis is performed according to the requirements of ISO standard 14971 for medical devices. This standard provides some techniques that allow to identify some failures modes which affect the behavior and performance of the final product. This work can be seen as a necessary preliminary step before data collection and PHM implementation for such tiny devices. For that purpose, the Failure mode and effect analysis (FMEA) technique is used in order to select critical components. The selection of the critical components is based on a criticality analysis (CA) mainly to prioritize and minimize the effects of critical failure modes that can lead to fault propagation.In addition, some practical guides are presented for PHM development in future works.

The development of microscale medical devices has had great growth in recent years in a variety of medical applications. However, the development of microscale medical devices brings with it some challenges due to their small sizes, the number of components, the used materials, and the manufacturing processes. Some of these medical devices are intended to be used inside the human body in contact with mucous membranes, blood, tissues, and bones. Therefore, they must be safe and reliable in order to guarantee a good performance during their operating time. The probability of failure in med-1 Surgery ical devices could represent different risks for the patient. The medical device manufacturers must offer the highest level of reliability in the phases of design, manufacturing, assembly, and production in order to reduce as much as possible the failure during a surgical procedure.

Well-made designs provide safer products. In [START_REF] Dyadem | Guidelines for failure modes and effects analysis for medical devices[END_REF], the author mentioned that approximately 76% of all engineering changes are due to the correction of bad designs.

In this way, in order to prevent failures on the product and reduce any kind of hazard, the identification of design defects or potential failure sources is an important consideration before proceeding to the next stages of a product.

The Prognostics and Health Management (PHM) is an approach that integrates different technologies and techniques. These allow detecting anomalies or failures, evaluating the current status, monitoring the system, and estimating the remaining useful life (RUL) of an equipment [START_REF] Brahimi | Critical components selection for a prognostics and health management system design: an application to an overhead contact system[END_REF] through knowledge of its physics, information, or data (Zio, 2022). One way to analyze the systems is by supervising the behavior of their critical components according to [START_REF] Mosallam | Component based data-driven prognostics for complex systems: Methodology and applications[END_REF] and [START_REF] Brahimi | Critical components selection for a prognostics and health management system design: an application to an overhead contact system[END_REF]. For this reason, critical components' identification and selection is the main and first step to PHM implementation, since these can affect the performance of the system in terms of safety and reliability.

There are some regulations and standards for medical devices that provide a combination of techniques to assess the reliability of the devices. The main regulations are the Food and Drug Administration (FDA) in the United States and the Medical Devices Regulation (MDR) in Europe, which provide information to guarantee high reliability in all phases of the design and development of the product. These regulations are supported by the International Organization for Standardization [ISO], being the ISO 14971 destined to risk management of medical devices. These standard provides some qualitative and quantitative risk analysis techniques such as Failure Mode and Effects Analysis (FMEA), Hazard and Operability Study (HAZOP) and Fault Tree Analysis (FTA). According to (ISO, 2019) these three techniques are the most used for medical devices. FMEA technique is currently one of the most used for failure analysis in risk management in medical devices design, according to [START_REF] Onofrio | Failure mode, effects and criticality analysis (fmeca) for medical devices: Does standardization foster improvements in the practice[END_REF] and [START_REF] Fechter | Failure mode effect analysis applied to the use of infusion pumps[END_REF].

Therefore, this work aims to provide a methodology for critical components' selection for a microgripper destined to work inside the human body. This methodology will allow the PHM development in the design phase for similar micro medical devices, in order to guarantee a safe and marketable device. In addition, considering the challenges of PHM implementation at the microscale, a detailed FMEA is developed which helps to identify the critical components from design stage.

The remainder of this paper is organized in the following sections. Section 2 explains the main PHM challenges to implement in micro medical devices. Section 3 describes the components of the microgripper to be studied. Section 4 explains the proposed methodology to select the critical components.

In Section 5 all the results are presented according to the proposed methodology, and finally, Section 6 is to conclude our work.

MEDICAL MICRODEVICES AND ITS CHALLENGES FOR PHM IMPLEMENTATION

The PHM context involves different disciplines such as mathematics, statistics, computer science, physics and engineering (Zio, 2022). It allows to evaluate the health state of a system starting from data acquisition, data manipulation, health assessment, diagnostics, prognostics and decision support [START_REF] Brahimi | Critical components selection for a prognostics and health management system design: an application to an overhead contact system[END_REF].

Although PHM systems have been implemented for years in industry, today their use continues to expand in areas such as microelectronics, micromechanics, and micromechatronics. However, up to our knowledge, PHM implementation for micro medical devices has not been much studied in the literature. This may be due to the challenges that those bring with them in terms of design, size, the number of constitutive components, materials used, manufacturing, assembly processes, and intended use. Developing a PHM for micro medical device depends mainly on physics, data availability, and data collection. (1) The physics is related to the complexity and the number of components. When devices have many components, it is sometimes difficult to identify the component that is degrading as well as the cause of the degradation.

(2) The data availability is a challenging part here since there is no existing databases that provide information on the behavior and performance of similar micro medical devices.

The only available information is the number of possible failure modes of micro medical devices that are reported by the FDA and Manufactures and Users Facility Device Experience (MAUDE). However, these failure modes can be considered as a guide to identify failures in similar devices [START_REF] Onofrio | Failure mode, effects and criticality analysis (fmeca) for medical devices: Does standardization foster improvements in the practice[END_REF].

(3) The data collection is related to the complexity and size of the microsystem and the number of components. This may lead to the implementation of internal or external sensors. Nevertheless, the complexity of the functions of the sensors should be deeply studied in order to guarantee a representative data of the degradation phenomenon. The data collection step is crucial for a successful PHM implementation.

MICROGRIPPER DESCRIPTION

The microgripper presented in this work is designed to be used in intracorporeal surgeries. An example of its use is shown in the Figure 1. Its total dimension should be as small as possible in order to be used through small incisions that are performed during intracorporeal surgeries, mainly in minimally invasive surgery (MIS).

For instance, the commercial microgrippers developed by Intuitive surgical Inc. da Vinci known as EndoWrist have diameters between 5 and 8.5 mm. Another example is the microgripper of 8 mm in diameter developed by the Olympus Medical System Group [START_REF] Group | Olympus 3d/flexdex® for minimal access surgery simplifies suturing, redefines robotics[END_REF], (Valley, 2018) and FlexDex (Surgical, 2022) to be used in a robotic system. Medical Microinstruments (MMI, 2020) developed a microgripper that has a diameter of 3 mm.

We are focused on diameter size since these microgrippers must be inserted in small tubes or cannulas called trocars to perform incisions of 3 mm, 5 mm, 10 mm, or 12 mm according to the surgical procedure mentioned by [START_REF] Holcomb | chapter 50 -laparoscopy[END_REF] and [START_REF] Fernandes | Toward a miniaturized mechanical surgeon[END_REF]. The smallest microgrippers can be used for different types of MIS such as gastroenterological surgery, nerosurgery, cardiac surgery, gynecologic surgery, laparoscopic surgery, and biomedical applications [START_REF] Fu | 11 -smart microgrippers for biomems applications[END_REF]. Amarob company presents the design of a 2 mm diameter microgripper to be used in intracorporeal surgeries. This microgripper is composed of two jaws, a shaft, a support, and four steel wires shown in Figure 2. These components enable to perform the opening and closing movements of the jaws 1 and 2 in order to hold, spread and pull out some tissues or anomalies during the surgical procedure. This microgripper will be driven by four steel wires of 0.08 mm in diameter, two wires will be used for opening motion and two wires for closing motion through four motors.

Before certifying the Amarob's microgripper for surgical procedures, more studies related to its performance should be done. Recall that the ultimate goal is to implement the PHM in the design of a micro medical device. Before proceeding to the whole implementation, the focus is on identifying the critical components. This allows data characterizing and PHM process development.

METHODOLOGY

The methodology proposed for critical components' selection for micro medical devices is shown in Figure 3. It is based on risk assessment according to ISO 14971. The risk assessment must cover two aspects: risk analysis and risk evaluation. Within risk analysis, some factors are established, for example, the phase of the product's life cycle that is to be analyzed, what can go wrong in the systems or components of the system, and mainly to understand the intended use or purpose of the system. For that, the hazards and characteristics related to its safety and reliability must be identified.

There are some techniques with qualitative or quantitative approaches that evaluate the safety and reliability of the system. Above all, these techniques enable us to identify failures that occur in micro medical devices that can mean potential harm or injury to patients, [START_REF] Kiran | Chapter 26 -failure modes and effects analysis[END_REF]. Their use depends on the complexity of the system, and the amount of data or information available from the system [START_REF] Dyadem | Guidelines for failure modes and effects analysis for medical devices[END_REF]. Then, in order to select the critical components of the system, a safety and reliability technique will be chosen.

Risk analysis techniques for critical components identifications for PHM

There exist many procedures to implement a PHM system. One of them is to identify the critical components that are the first ones to fail and affect its performance. The qualitative FMEA technique recommended by ISO 14971, is referred to as bottom-up or inductive analysis. This means that the analysis starts at the component level where the possible component failure modes are identified, and then it is examined what the consequences are on a higher level [START_REF] Elahi | Chapter 12 -risk analysis techniques[END_REF]. This technique can be used throughout the life cycle of a product by implementing different types of FMEAs, for example, design FMEA (D-FMEA), process FMEA (P-Figure 3. Methodology for critical components' selection FMEA), application FMEA (A-FMEA), and service FMEA (S -FMEA) [START_REF] Basu | Chapter iv -guided word hazard analysis[END_REF]. In the sequel, D-FMEA will be explained since this work aims to provide the methodology to select the critical components of a system, by analyzing from the early design stage.

Design FMEA

The FMEA steps consist of four steps:

Step 1 -Risk identification. This step includes the listing of the system's components, the definition of the function of each component, and the identification of the potential failure modes of each component. The failure mode is the way the failure occurs and its effect on system operation [START_REF] Dhillon | Medical Device Reliability and Associated Areas[END_REF], that is, the manner in which the product/process fails to perform the intended function [START_REF] Basu | Chapter iv -guided word hazard analysis[END_REF].

Step 2 -Risk analysis. In this step the potential causes for each failure mode are determined, the potential effects for each failure mode are identified and the current controls that are intended to eliminate failure causes are defined. Failure causes are the main reasons that lead to a failure in the system. These causes can be design defects, physical or chemical processes, and quality defects [START_REF] Dhillon | Medical Device Reliability and Associated Areas[END_REF]. Moreover, in this part, a severity value is determined to the failure effect, which is the consequence or consequences of a failure mode on the operation, function, or status of a system or equipment. The severity represents the seriousness of the failure and not the mode of the failure and generally, the severity of the effect is given a severity number (S) from 1 (no danger) to 10 (critical) [START_REF] Kiran | Chapter 26 -failure modes and effects analysis[END_REF], a failure effect can be caused by one or more failure modes (Ramakrishna, Tian, Wang, Liao, & Teo, 2015). Within the risk analysis, a probability of occurrence of the failure value is also assigned. Generally, the occurrence (O) takes values from 1 for the least frequent to 10 for the most frequent occurrence. Sometimes these values are taken considering the occurrence of failure of similar systems or products. Another value to determine within the risk analysis is the ease of detection. This allows knowing the control mechanisms that detect the potential cause or the subsequent failure mode before the production of the product. The detection (D), generally takes values between 1 and 10. A high detection number indicates that the chances are high that the failure will escape detection [START_REF] Dhillon | Medical Device Reliability and Associated Areas[END_REF]. Below are some definitions.

• Severity is an assessment of the failure effects on the end user, the local area and the next high-level effects [START_REF] Dyadem | Guidelines for failure modes and effects analysis for medical devices[END_REF]. • Occurrence is related to the probability of the failure mode and cause. This is expressed in terms of probability of occurrence [START_REF] Basu | Chapter iv -guided word hazard analysis[END_REF]). • Detection is an assessment of the ability of current design controls to identify any potential failure mode if it does occur [START_REF] Dyadem | Guidelines for failure modes and effects analysis for medical devices[END_REF]. • Criticality analysis (CA) is used to prioritize and minimize the effects of critical failure modes in the early design stage, i.e., this analysis help to classify the significance of each potential failure for each component in the system's design based on a failure rate and a severity ranking. Dhillon, ( 2020) and [START_REF] Bona | Total efficient risk priority number (terpn): a new method for risk assessment[END_REF] mentioned that the CA is a relative measure of severity and its occurrence. CA has quantitative and qualitative approaches. The quantitative approach is used when failure rates, failure modes, failure mode ratios, and failure effects probabilities are known, and the qualitative approach is used when no known failure rates and failure modes are available. • Criticality Matrix. According to the U.S. Army Corps of engineers (Army-GOE, 2006) the criticality matrix is a graphical or visual tool for identifying and comparing failure modes for all components within a system or subsystem and their probability of occurring with respect to severity. This is a finer method to prioritize criticality, that is, enables customizing the criticality depending on the needs of each company.

• Failure modes, effect and criticality analysis (FMECA) is an extension of FMEA, this is composed of two separate analysis the FMEA and the Criticality Analysis (CA) (Army-GOE, 2006).

Step 3 -Risk evaluation. In this step, the risk priority number (RPN) is computed by multiplying the values of S, O, and D, such as in Eq. 1.

RP N = S ⇥ O ⇥ D (1)
RPN is the product of the numerical severity, probability, and detection ratings, it is described in FMEA/FMECA on the scale of 0-1000 according to [START_REF] Basu | Chapter iv -guided word hazard analysis[END_REF]. Depending on the value that the RPN takes, this shows the areas of the greatest concentration, therefore the corrective actions must be focused on reducing its value.

Step 4 -Risk control.

In this stage, some corrective/preventive actions are determined in order to reduce the criticality of the failure modes according to [START_REF] Kiran | Chapter 26 -failure modes and effects analysis[END_REF]. The control actions are focused on reducing the severity of the hazard and the probability of occurrence, taking corrective or preventive actions that allow the risk to be monitored throughout the life of the product.

Critical components' selection and monitoring in PHM

Critical components of a micro medical device represent risks that can affect severely the health of the patient during a determined function. The main cause of risks depends on the criticality of each failure mode of its components. The failure modes must be reduced as far as possible from the design stage to guarantee a reliable device.

To ensure that the product meets the design specifications, these are subjected to finite element analysis (FEA). However, the FEA for complex systems does not provide reliable results, or in many cases, it is impossible to analyze the entire function of the systems.

Then, when in the risk control stage it is not possible to determine corrective or preventive actions to reduce the criticality of the failure mode of each component, the system must be monitored through the implementation of sensors (see Figure 4). The use of sensors allows getting representative data of the degradation of each component.

RESULTS

The methodology described in the previous section is applied to a microgripper that will be used in intracorporeal surgeries. All this study is based on the requirements of ISO 14971. The first step is to identify the phase of the product's life cycle to be analyzed. This work is focused on identifying hazards and failure modes starting from an early stage, for which the design phase is selected.

Mainly, risk assessment must fulfill three specific questions that can affect the safety [START_REF] Dyadem | Guidelines for failure modes and effects analysis for medical devices[END_REF]:

• What can go wrong?

• How likely is it?

• What are the impacts?

To answer these questions, damages and safety-related characteristics must be identified by answering some questions provided by the ISO standard (Tr, 2020). The Table 1 details the questions that were adapted to the proposed microgripper for intracorporeal surgeries and that help to identify hazards or failure modes.

First prototype and results of finite element analysis

In this work, the identification of the failure modes is based on some defects that were appreciated in the first prototype.

As well as the results of the finite element analysis (FEA) of the microgripper and some information from the literature that reports some failure modes for similar migrogripper.

After the manufacture and assembly of the first prototype of the microgripper, some defects were observed in some of its components. For example, some teeth on jaws 1 and 2 broke off. The shaft was fragile during its assembly, which showed that when applying the forces to open and close the jaws, the probability of breaking is very high. Therefore, a redesign was carried out focused on improving the areas where there is a greater stress concentration since they represent one of the causes that lead to failure. Then, the FEA was performed to see if the stress concentration in critical areas was reduced. FEA results were:

• Stress concentration in the last tooth of jaws 1 and 2 as Questions adopted from ISO 14971 Answers What is the intended use/purpose, and how is the medical device to be used?

The microgripper will be used for intracorporeal surgeries to operate inside the human body. Either to grasp the tissue or to remove it, thus the microgripper will be driven with steel wires to open and close its jaws. Is the medical device intended to be in contact with patients or other persons, The microgripper will be in contact with the patient, mainly with tissues and blood. What materials and/or components are incorporated in, or are in contact with, the medical device?

The microgripper will be manufactured in stainless steel 316 low carbon vacuum melt (LVM), and this will be the material that will be in contact with tissues and blood. Is the medical device supplied sterile or intended to be sterilized by the user, or are other microbiological controls applicable?

The device must be sterilized before and after being used.

Is the medical device intended for use in conjunction with other medical devices, medicines or other medical technologies?

The microgripper will be used in conjunction with a microrobot that leads a laser beam. Does the medical device have a restricted shelf life?

The life of the microgripper will be computed by estimating its RUL by implementing a PHM study. To what mechanical forces will the medical device be subjected?

The microgripper will be subject to stress, strain, tension and shear forces. What determines the lifetime of the medical device?

The lifetime of the microgripper depends on the degradation and failure of its components due to cyclic movements during its life cycle and due to the tension in the wires. Is the medical device intended for single use or multiple uses?

The microgripper has both clamping and expanding functionalities and can be used in different types of minimally invasive surgery, and the number of its uses will be defined by the RUL estimation. Does installation of the medical device require special training? The manufacture and assembly process requires special abilities since it is a device at microscale. Does the medical device have connecting parts or accessories?

The microgripper hasa mechanical stage, motorization stage, power supply stage and control stage. Does the medical device have a control interface?

Yes, it does. In what ways might the medical device be misused (deliberately or not)? Incorrect use of the microgripper and exceeding the number of uses established by the manufacturer, as well as operating outside the limit of its useful life.

Table 1. Identification of hazards and characteristics related to safety. This gives an idea that the wire will break in a joint o welding point.

Critical components' selection of the microgripper

The FEA results helped to identify some failure modes for each component of the microgripper as well as their failure causes and failure effects.

The D-FEMEA for each component of the microgripper is detailed in Table 2. The stress concentration in the last tooth of jaws 1 and 2 leads to the failure mode of the jaws, which is the breakage of the tooth in the final product. The potential cause is the small size of the tooth and its effects could reflect directly in the surgical procedure since the precision to hold and pull the tissues would be bad. Then, considering the effect of the failure, a low severity (equal to 5) was assigned since the product is operable but with a loss of comfort. The probability of occurrence is moderate (equal to 4) since this could happen if a high force different from the computed force is applied, and the detection is high (equal to 3) since the current controls for prevention are to perform some modification in the design. When performing these changes, the stress concentration in the last tooth was reduced. Then jaw 1 and jaw 2 have a RPN value of 60.

The support was evaluated by FEA but it did not show possible failures nor could any failures be observed in the manufactured component. On the other hand, according to FEA results of the shaft, two failure modes were identified: the breakage of the shaft and the permanent deformation of the shaft. The breakage of the shaft is due to two failure causes, the first one is due to an improper force applied, and the second one is due to the shear force. Both failures lead to the same failure effect which is the unavailability of the microgripper and the severity factor takes a value of 9 (equivalent to hazardous) with a warning. The probability of occurrence of the improper force applied is 6, equivalent to moderate, since this can happen only if there is no external control of the applied force. The detection factor of the improper force takes a value of 10 (equivalent to absolutely impossible) since there are no current controls that can be applied at the design stage to reduce or prevent these failure modes, however, they must be analyzed at later stages. Then the RPN takes a value of 540. As for the shear force, the probability of occurrence is 9 since all the time, when opening and closing motions are performing, the shear will occur in the microgripper. The detection factor is 10 since there are no current controls in this stage to reduce or prevent these failure modes. Then the RPN value takes a value of 810.

The permanent deformation of the shaft is the other failure mode of the shaft. The main failure cause is an improper force applied that lead to improper motion of the jaws. Then the severity factor is very high (equal to 8) which means even if the component does not fracture, it becomes unavailable. The probability of occurrence and the detection factor take values of 6 and 10 respectively. Then the RPN value is 480. According to FEA results, the wire presents two failure modes, breakage of the wire, and the stretching of the wire. Both are due to the same failure cause, which is repetitive movements of tension. The failure effect leads to the unavailability of the microgripper and the difficulty to hold and pull tissues during the surgical procedure. Then the severity factor takes values of 10 and 8 respectively, the probability of occurrence takes a value of 9 for both failure causes, and the detection factor takes a value of 10 for both cases. The closing movement of the microgripper was simulated in order to analyze the behavior of one wire. For the analysis, a force was placed at the end of the wire and a constraint on the bonded surfaces between the wire and the jaw. This analysis generated a meshing problem preventing the desired resolution. A solution to this problem was to simulate only one jaw, the shaft, and the wire shown in Figure 5 (d), which demonstrates that the deformation along the wire is quite significant. However, this analysis was incomplete, since the friction between the cable and the support could not be simulated. For that reason, the detection factor takes a value of 10 since there are no current controls in this stage to reduce or prevent a failure mode. Then RPN is 900 and 720 respectively.

Although the RPN values show the areas of the greatest concentration to take corrective or preventive actions, in this work the critical elements were selected by performing a criticality analysis to prioritize the critical failure modes of each component considering its probability of occurrence and its seriousness of the failure effect that is the severity. In the criticality matrix shown in Figure 6 the support and the two jaws are in the safe zone that was considered by Amarob company.

On the other hand, the shaft and the wire are in the zone of maximum risk. The shaft presents two failure modes that are detailed in Table 2. One of the failure modes presents two causes that lead to the failure mode, in order to better understand these were named F1-C1and F1-C2, where F1 represents the failure mode 1, and C1 and C2 are the causes 1 and 2 respectively.

Then, according to the criticality matrix, two components are identified as critical, that is the shaft and the wire. The support and the two jaws of the microgripper are joined by the shaft. Serious patient injuries can be caused by the shaft breaking during a surgical procedure. In the same way, something similar happens with wires, whether one of these breaks, the microgripper can no longer perform its functions. Therefore, in both cases, the microgripper will no longer be able to operate.

The importance of selecting them as critical allows to prevent the occurrence of failures during a surgical procedure and to estimate their RUL. In this way, one can define how many hours or how many times the microgripper can operate without failures during a surgical procedure.

Monitoring of the critical components of the microgripper

Once the critical components of the microgripper are selected, the next step is monitoring through the implementation of sensors that allow data collection on their behavior and performance. The sensor's implementation must be performed strategically in order to get useful information for PHM implementation. Figure 7 includes a block diagram with the steps to follow to PHM implementation in future works, as well as its real-time monitoring.

CONCLUSION

The contribution of this work was to develop a methodology in order to select critical components of a microgripper dedicated to intracorporeal surgeries. This selection was realized through a risk analysis based on the requirements of ISO 14971 for medical devices. Likewise, this work shows the importance of selecting the critical components, when analyzing the causes that lead to failure modes from the early design stage in order to develop the PHM at design stage.

The proposed methodology can be adapted to analyze the critical components of similar micro medical devices. The root causes which affect the safety and reliability can be exposed thanks to this procedure. This work is the base to develop the PHM system for micro medical devices in future works. Since by knowing the critical components, these can be deeply analyzed through the implementation of sensors.

Figure 1 .

 1 Figure 1. Microgripper operation in larynx surgery.

Figure 2 .

 2 Figure 2. Microgripper constitutive components' description.

Figure 4 .

 4 Figure 4. Monitoring of the critical components

  Figure 5. Finite elements' analysis results of microgripper

Figure 6 .

 6 Figure 6. Criticality matrix of the failure modes of the microgripper components.

Figure 7 .

 7 Figure 7. Monitoring of the critical components of the microgripper

ACKNOWLEDGMENT

This work has been supported by the EIPHI Graduate school (contract "ANR-17-EURE-0002") and the ANRT-AMAROB CIFRE Thesis.


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

The Condorcet Loser Criterion in Committee Selection

Keywords: Committee, Condorcet, Scoring, Borda, Stable rule JEL Classification: D70, D71

In committee selection setting, we introduce the Condorcet Loser Committee (CLC) which when it exists, is a committee such that each of its members is defeated in pairwise comparisons by any outside candidate. It turns out that most popular committee selection rules can elect the CLC when it exists. From the perspective of the Condorcet majority criterion, the election of the CLC is simply not acceptable. We identify the few rules that will never elect the CLC when it exists. We show among others that the k-Borda rule is the only k-scoring committee rule that never select the CLC. This also holds with k-iterative Borda rule, Nanson rule, Kemeny rule, Copeland rule. As a corollary, it appeared that the Chamberlin-Courant rule can elect the CLC when it exists.

Statements and Declarations

The author has no relevant financial or non-financial interests to disclose. The author has no competing interests to declare that are relevant to the content of this article. The author certifies that he has no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript. The author has no financial or proprietary interests in any material discussed in this article.

Introduction

Committee selection and the study of the properties of the voting rules for electing committees are increasingly popular topics in social choice theory. In committee selection, the goal of preference aggregation is to elect a fixed number of winners. In the well-supplied family of works on committee selection, one of the approaches is to assume that an elected committee must meet the Condorcet winner criterion. In single winner election, the Condorcet winner criterion [START_REF] De | Essai sur l'Application de l'Analyse à la Probabilité des Décisions Rendues à la Pluralité des Voix[END_REF] recommends to elect, when he exists, the candidate who defeats each of his competitors in pairwise comparisons; such a candidate is called the Condorcet winner. The extension of the Condorcet winner criterion to committee selection led to two main concepts: the Condorcet Committee à la Gehrlein [START_REF] Good | A note on Condorcet sets[END_REF][START_REF] Gerhlein | The Condorcet criterion and committee selection[END_REF] and the Condorcet Committee à la Fishburn [START_REF] Fishburn | An analysis of simple voting systems for electing committees[END_REF]. 1 The Condorcet Committee à la Gehrlein (CCG) is a committee such that each of its members defeats any outside candidate in majority duels. The CCG as we have just defined it is still known in the literature as the "Strong Condorcet Committee"; the "Weak Condorcet Committee (à la Gehrlein)" is a committee such that none of its members is defeated in majority duels. When the CCG exists, it is unique, whereas there may be several weak Condorcet Committees. In Condorcet Committee à la Fishburn (CCF) is the committee that is preferred by a majority of individuals to any other committee. In recent work, [START_REF] Kamwa | Coincidence of Condorcet committees[END_REF]; [START_REF] Kaymak | Sets of alternatives as Condorcet winners[END_REF] have looked at the relationships between these two Condorcet committees. The CCG, like the CCF, does not always exist. Voting rules that always elect the CCG when it exists (or a committee that is close to it when it does not exist) have been proposed in the literature: these are called stable rules. We will describe these rules later.

As noted above, Condorcet committees are simply extensions of the Condorcet winner criterion to committee selection. In this paper, we attempt for the first time, an extension of the Condorcet loser criterion to the framework of committee selection. In single-winner elections, the Condorcet loser criterion would require that when the Condorcet loser exists, he should not be selected. The Condorcet loser is a candidate who is defeated in pairwise comparisons by each of the other candidates. While there is no consensus in the single winner literature that the Condorcet winner should be elected when he exists, there is nonetheless a near consensus that the Condorcet loser should not be elected. According to [START_REF] Lepelley | On the probability of electing the Condorcet[END_REF], "[...] the election of the Condorcet loser is disturbing enough to consider the Condorcet loser criterion as a minimal requirement that a voting system should meet: it seems reasonable to rule out the systems which can lead to the election of the Condorcet loser, unless one can demonstrate that the occurrences of this paradoxical result are extremely rare."

According to the results by [START_REF] Diss | On some k-scoring rules for committee elections: agreement and Condorcet Principle[END_REF], when electing committees, most of the popular committee selection rule may quite often elect the Condorcet loser as member of an elected committee. By extending the Condorcet loser criterion to the framework of committee selection, we introduce the concept of Condorcet Loser Committee (CLC) to describe a committee such that each of its members is defeated in pairwise comparisons by each of the external candidates. It is obvious that when it exists, the CLC is unique. As we will see later, there are situations in which the CLC exists and is elected under a number of popular voting rules; this could even occur in the presence of a CCG. With this in mind, the position we take here, by extension of the point made by [START_REF] Lepelley | On the probability of electing the Condorcet[END_REF], is that when the CLC exists, it would be objectionable for it to be elected. From this point on, we strive to identify the committee selection rules that never elect the CLC when it exists. To do so, we focus on four main families of committee selection rules found in the literature: k-scoring rules, k-iterative scoring rules, k-Condorcet consistent rules and stable rules. A k-scoring rule (resp. k-iterative scoring rule) select the k best candidates of the associated scoring rule (resp. iterative scoring rule); we define scoring rules later. A k-Condorcet consistent rule selects the k best candidates of the corresponding Condorcet consistent rule. A Condorcet consistent rule is a voting rule that always picks the Condorcet winner when he exists.

We show that the k-Borda rule is the k-scoring rule that never elects the CLC when it exists; the same is true of k-iterative Borda rule. We also show that the Kemeny rule, the Nanson rule, and the Copeland rule are Condorcet consistent rule never pick the CLC when it exists. Among the seven stable rule encountered in the literature, only two of them never select the CLC.

The rest of the paper is organized as follows: Section 2 is devoted to notation and definitions; it is in this section that we present each of the families of voting rules we are interested in. Section 3 presents our main results. Section 4 concludes.

Basic notation 2.1 Preferences

Let N be the set of n voters (n ≥ 2) and A the set of m candidates (m ≥ 3).We denote by R the set of binary relations on A, and by P the subset of complete, transitive, and antisymmetric binary relations on A. The preference profile π = (P 1 , P 2 , ..., P i , ..., P n ) gives all the linear orders of all the n voters on A, where P i is the strict ranking of a given voter i. For x, y, z ∈ A and given voter, we write ayz to say that this voter ranks x before y who is ranked before z. We denote by P (A) n the set of preference profiles. A voting situation ñ = (n 1 , n 2 , ..., n t , ..., n m! ) indicates the number of voters for each linear order such that m! t=1 n t = n. We denote by n xy the number of voters who rank x before y. If n xy > n yx , we say that x is majority preferred to y; this is denoted by xM y. In case we get n xy = n yx , this means that x and y are tied; we denote this by xT y. In a The Condorcet Loser Criterion in Committee Selection majority graph, the relation xM y will be materialized by an arrow going from x to y; no arrow between x and y will translate the relation xT y.

Given π and a candidate x, x is said to be the Condorcet winner if xM y ∀y ∈ A \ {x}; he is the Condorcet loser if yM x ∀y ∈ A \ {x}. We have a majority cycle when the majority relation M is not transitive. Thus, we say that x, y, z ∈ A are in a majority cycle if we have xM y, yM z and zM x.

Assume that we want to elect a committee of size k (2 ≤ k ≤ m -1). We denote by A k the set of all possible committees of size k. When the CCG exists, it unique while there may exist more than one wCCG. In the remainder of the paper, when we refer simply to the Cordorcet Committee (CC), this would mean in the context under consideration that there is no need to distinguish between the CCG and a wCCG. We denote by C k (π) the set of Condorcet Committees. Given π and k the size of the committee to be elected, when the CLC exists, it is unique.

Voting rules

We will pay attention to four groups of ranking-based committee selection rules: k-scoring rules, k-Iterative scoring rules, k-Condorcet consistent rules and stable rules.

k-scoring rules

Given π and the m! possible complete strict rankings, we denote by r(t, a) (r(t, a) = 1, 2, . . . , m) the rank of candidate a in the ranking of voter of type t (t = 1, 2, . . . , m!), and by n t the number of voters of type t (n t ≥ 0). A scoring rule gives w r(t,a) points to candidate a each time he is ranked at position r(t, a); a scoring rule is thus defined by a scoring vector w = (w 1 , w 2 , . . . , w m ) with w 1 ≥ w 2 ≥ . . . ≥ w m and w 1 > w m . Let us introduce some of the most popular scoring rules. The Plurality rule also called Single non-transferable vote is characterized by w = (1, 0, . . . , 0); the Borda rule is defined by w = (m -1, m -2, . . . , 1, 0); the Antiplurality rule is defined by w = (1, 1, . . . , 1, 0); the q-approval rule uses the vector w = (1, . . . , 1 q , 0, . . . , 0), the Nairu rule also called the Harmonic rule is defined by w = (1, 1 2 , . . . , 1 m-1 , 1 m ). Given π and w, the score of candidate a is defines as follows: t=1 m! n t w r(t,a) . In committee selection, a k-scoring rule picks the k best candidates of the associate scoring rule. Thus we define Plurality those k-Plurality rule, k-Borda rule, k-Antiplurality rule and so on. q-approval rule is also called Bloc rule when q = k.

In some situations, the use of a tie-break mechanism may be necessary; we do not need to address this issue here because we will not need to deal with tie scores. This will also be the case for the rules that we will present in the sequel.

k-Iterative scoring rules

Iterative scoring rules can also be used for committee selection and they involve multiple rounds of voting. Here, we consider those k-iterative rules based on One-by-one eliminations. There are two main ways of conceiving iterative kscoring rules:

downward eliminations: at each round, only the candidate with the lowest score of the considered scoring rule is eliminated until there are only k candidates left. The iterative Borda rule, also known as the Baldwin rule [START_REF] Baldwin | The technique of the Nanson preferential majority system of election[END_REF], belongs to this group. upward eliminations: at each round, one candidate, the one with the highest score, is declared elected. The process continues until k candidates are elected.

In the family of k-iterative scoring rules, we can also add the particular group formed by Single Transferable vote (STV) with its variants.2 STV is a multi-round rule where in each round, any candidate whose Plurality score is at least equal to a certain threshold/quota is elected; if there are still seats to be filled, the candidate with the lowest score is eliminated and the process continues until all contested seats are filled. STV tends to promote representative committees. Note that in some situations, STV is equivalent to (iterative) k-Plurality.

k-Condorcet consistent rules

The consistent Condorcet rules have been evoked in the context of committee selection [START_REF] Coelho | Understanding, evaluating and selecting voting rules through games and axioms[END_REF]. With these rules, the aim is to select the k best candidates. The Condorcet consistent rules we are interested in are the following: The Condorcet Loser Criterion in Committee Selection Kemeny rule: it operates by computing distances from a given linear order to all the linear orders of a preferences profile; the Kemeny social ranking is the linear order that minimizes this distance, the total distance to the whole profile. Dodgson rule: this rule elects the candidate who needs the fewest number of adjacency switches to become the Condorcet winner. Based on the ascending number of switches, the Dodgson social ranking is determined. Young rule: it elects the candidate who needs the fewest number of deletions of voters to become the Condorcet winner. Based on the ascending number of switches, the Young ranking is determined. Maximin/Minimax rule: This rule determines the support received by each candidate in every pairwise comparison; the candidate with the greatest minimum support received is the winner or appears at to top of the collective ranking.

Copeland rule: The Copeland score of a candidate x ∈ A is defined by Cop(x, π) = y =x γ x,y (π); where for y ∈ A\{x}, γ x,y (π) = 1 if xM y, γ x,y (π) = 1 2 if xT y and γ x,y (π) = 0 if yM x. For a committee of size k, the Copeland rule will pick the k highest Copeland scores. Nanson rule [START_REF] Nanson | Methods of election[END_REF]: this rule uses the same scoring vector as the Borda rule and at each step, any candidate who obtains (strictly) less than the average of the scores is eliminated. Note that in the context of committee selection, Nanson's rule can pose some problems: there may be situations in which, in the first round, more than m -k candidates obtain scores below the average. To guarantee the election of a committee, it is necessary to describe a procedure to deal with such situations.

To the above list, we can add the iterative Borda rule already defined in Section 2.2.2.

The stable rules

Here we formally define the stable rule encountered in the literature. Given π and a committee C ∈ A k :

The Kemeny-Ratliff rule [START_REF] Ratliff | Some startling inconsistencies when electing committees[END_REF]. Kemeny-Ratliff rule (KR) selects the committee(s) with the smallest total margin of loss in pairwise comparisons versus the outside candidates. KR picks the committee

C ∈ A k such that KR(π, C) ≤ KR(π, C ) ∀C ∈ A g \ {C} with KR(π, C) = x∈C,y∈A\C max{0, n yx -n xy }. KR(π, C
) is the total margin of loss in pairwise comparisons by the candidate in C versus the other m -k candidates. The Dodgson-Ratliff rule [START_REF] Ratliff | Some startling inconsistencies when electing committees[END_REF]. Dodgson-Ratliff rule (DR) picks the committee(s) with the fewest number of adjacency switches needed to make it becomes a CCG. DR selects the committee C ∈ A k such that DR(π, C) ≤ DR(π, C ) ∀C ∈ A k \{C} with DR(π, C) the number of adjacency switches needed to make C subset become a Condorcet committee.

The Minimal Size of External Opposition rule [START_REF] Coelho | Understanding, evaluating and selecting voting rules through games and axioms[END_REF]. Minimal Size of External Opposition rule (SEO) selects the committee(s) with the smallest margin of loss of its members versus the outside candidates.Let SEO(π, C) = max The Young-Condorcet rule [START_REF] Kamwa | On Stable Rules for Selecting Committees[END_REF]. Young-Condorcet rule (YC) selects the committee(s) that needs the fewest number of deletions of voters to become a Condorcet committee. Let us denote by π S be the profile obtained after the deletion of a subset S of voters (S ⊆ N ). YC picks the committee

C ∈ A k such that Y C(π, C) ≤ Y C(π, C ) ∀C ∈ A k \ {C} with Y C(π, C) = min S∈∆(π,C) |S| and ∆(π, C) = {S ⊆ N : C ∈ C k (π S )}.
The Minimal number of Deletion of Candidates [START_REF] Kamwa | On Stable Rules for Selecting Committees[END_REF]. (MDC) picks the committees that need the fewest number of deletions of candidates to become a Condorcet committee. Let π B be a voting profile obtained after the deletion of a subset B of A. MDC selects the committee C ∈ A k such that min

B∈Ω(π,C) |B|≤ min B∈Ω(π,C ) |B| ∀C ∈ A k \ {C} with Ω(π, C) = {B ⊆ A : C ∈ C k (π B )}.
The Copeland 0 [START_REF] Aziz | The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality[END_REF]: This rule differs from the classical Copeland rule only by the fact that when the majority duel between two candidates results in a tie, they both receive 0 point. This rule picks the candidates with the k highest Copeland 0 scores.

Results

Some may wonder if the existence of the CLC is a frequent or rare occurrence. So, before stating our result, Let us take a look at this issue. Note that for a given profile, if there is a CLC of size k this implies that there is a CCG of size m -k. This remark is very important if one were to wonder whether the existence of the CLC is a frequent fact or not: the probability of existence of the CLC of size k is equal to the probability of existence of the CCG of size m -k. Thus, from the existence probabilities of the CCG we can easily deduce those of the CLC. That what we do from the probabilities of existence of CCG provided by [START_REF] Diss | Multi-winner scoring election methods: Condorcet consistency and paradoxes[END_REF]. So, for electorate tending to infinity and a number of candidates between 3 and 6, we record the limiting existence probabilities of the CLC in Table 1 for the impartial anonymous culture hypothesis (IAC). IAC is one of the hypothesis often used when computing the likelihood of The Condorcet Loser Criterion in Committee Selection voting events. Under IAC, it is assumed that all voting situations are equally likely to be observed. For more on this hypothesis, we refer to the book by [START_REF] Gehrlein | Voting paradoxes and group coherence[END_REF]. Recall that our point of view is to say that electing the CLC when it exists is an objectionable situation for committee selection. So, our aim is to search out the committee selection rules that never lead to the CLC when it exists. Theorem 1 to 4 present our results for each of the four groups of voting rules/methods on which we focused.

Theorem 1 Consider a voting situation with m ≥ 3 candidates and where one want to elect a committee of size 1 < k < m; k-Borda rule is the only k-scoring rule that never elects the CLC as the winning committee.

Proof First of all, let us show that k-Borda rule never elects the CLC as the unique winning committee. Given A, let us consider a voting situation where a committee C ∈ A k is the CLC and is selected by k-Borda; consider the set H = A \ C with |H|= m-k. It comes that the Borda winner, let us say a, belongs to C and the Borda bottom-ranked candidate belong to H. We know from [START_REF] Levenglick | A consistent extension of Condorcet's election principle[END_REF] that if n ab > n ba , then b cannot be ranked just above a in a Kemeny social order; since ∀x ∈ C and ∀y ∈ H, nyx > nxy, it follows that the Kemeny winner belongs to H while the Kemeny bottom-ranked candidate belongs to C. As C is assumed to be the Borda winning committee, this means that the Kemeny rule winner is not among the k highest Borda scores: this lead to a contradiction since we know from [START_REF] Saari | A geometric examination of Kemeny's rule[END_REF] that for m ≥ 3 candidates, the Borda rule always ranks the Kemeny rule top-ranked candidate strictly above the Kemeny bottom-ranked candidate and that, the Kemeny rule ranks the Borda rule top-ranked candidate strictly above the Borda rule bottom-ranked candidate. So, k-Borda rule never elects the CLC as the unique winning committee.

A simple way to show that all other scoring rules could elect the CLC would be to assume an election with m = 3 and k = 2; in this election if there is a CLC, it implies that there is a Condorcet winner. For the CLC to be elected for a given scoring rule in this case, the Condorcet winner would have to be ranked last by this rule. According to Fishburn and Gerhlein (1976), if a scoring rule is not the Borda rule, there is a voting profile where the Condorcet winner scores the worst. Such a situation is known in the literature as the strict Borda paradox. It is established that apart from the Borda rule, all other scoring rules are vulnerable to the strict Borda paradox; see for instance [START_REF] Gehrlein | Voting paradoxes and group coherence[END_REF]. Thus, such a voting situation with three candidates is therefore sufficient to say that all other scoring rules can elect the CLC when it exists.

Another selection rule much studied in the literature and which we do not dwell on is the Chamberlin-Courant rule3 . This rule is equivalent to the Borda rule for k = 1; it is also equivalent to k-Plurality rule for k = m -1 [START_REF] Kamwa | Essais sur les modes de scrutins et la sélection des comités[END_REF]. As we know from Theorem 1 that k-Plurality may pick the CLC when it exists, this may also be the case for the Chamberlin-Courant rule when k = m -1. Thus, we derive Corollary 1.

Corollary 1 Chamberlin-Courant rule can elect the CLC when it exists.

Theorem 2 tells us what we get with k-iterative scoring rules.

Theorem 2 Consider a voting situation with m ≥ 3 candidates where we want to elect a committee of size k using a k-iterative scoring rule with one-by-one (downward or upward) eliminations. Assume that a CLC of size k (1 < k ≤ m-1) exists. Except the k-iterative Borda rule, all the iterative scoring rules may select the CLC as the unique winning committee.

Proof Given a voting situation with m ≥ 3 candidates, assume that the CLC of size k denoted C ∈ A k exists and it is elected by a k-iterative scoring rule.

Let us first consider the k-iterative scoring rules with downward eliminations. As C is elected, this means that at the last round, the set of candidates is C ∪ {x} with x ∈ A \ C. As C is the CLC, candidate x is by definition, the Condorcet winner on C ∪ {x}. In such a situation, for C to be elected, this needs x to scores the worst on C ∪ {x}. It is well known that on C ∪ {x}, x the Condorcet winner can never obtains the lowest score only under the Borda rule (see [START_REF] Fishburn | Paradoxes of voting[END_REF]Smith, 1973;[START_REF] Daunou | A paper on elections by ballot[END_REF] while this can occur under the other scoring rules (Fishburn and Gerhlein, 1976). So, k-iterative Borda is the only k-iterative scoring rule with downward eliminations that never picks the CLC when it exists.

Let us now consider the k-iterative scoring rules with upward eliminations. Consider y ∈ C the candidate elected at round kth; it follows that at this round, y is the Condorcet loser on {x} ∪ A \ C and gets the highest score. It is well known that it is only under the Borda rule that the Condorcet loser never scores the best while this may occur under the other scoring rules. Thus, k-iterative Borda is the only k-iterative scoring rule with upward eliminations that never picks the CLC when it exists. The Condorcet Loser Criterion in Committee Selection Since STV can be similar to (iterative) Plurality in some situations, Corollary 2 follows from Theorems 1 et 2 Corollary 2 STV can elect the CLC when it exists.

Theorem 3 tells us what we get with the Condorcet consistent rule on which we focus.

Theorem 3 Consider a voting situation with m > 4 candidates such that there is no Condorcet winner but there is a CLC of size 1 < k < m -1. Dodgson rule, Maximin rule and Young rule may lead to the CLC. This never occurs with the Kemeny rule, Nanson rule and the Copeland rule.

Proof The cases m = 3 or m = 4 with k = m -1 are automatically excluded because the existence of the CLC implies that of a Condorcet winner who would be elected in all cases. Similarly, in the case m = 4 with k = 2 the existence of the CLC implies that of a Condorcet Committee of which at least one of the members would in all cases be elected by our Condorcet consistent rules. To show that Dodgson rule, Young rule and Maximin rule may lead to the CLC when it exists, let us consider the following voting profile with 21 voters and 5 candidates. In this profile candidate a is the Condorcet loser. Assume that we want a committee of size k = 2; in our profile there is no (Weak) Condorcet Committee while (a, e) is the CLC. After computations, it comes for the Dodgson ranking that e is ranked at the top while all the other candidates tie for the second place; thus for k = 2, committee (a, e) the CLC belongs to the set of elected committee for the Dodgson rule. Candidates a and e share the first place in the collective ranking of the Young and Maximin rules while the others share the second place; thus, (a, e) the CLC is elected by the Young rule and the Maximin rule. So, it comes from the above profile that Dodgson rule, Young rule and Maximin rule may pick the Condorcet loser as a member of an elected committee.

Regarding the Kemeny rule, we can use an argument that we have used earlier. Consider a voting situation where a committee C ∈ A k is the CLC and let us consider the set H = A\C such that |H|= m-k. We know from [START_REF] Levenglick | A consistent extension of Condorcet's election principle[END_REF] that if n ab > n ba , then b cannot be ranked just above a in a Kemeny social order. So, since for every x ∈ C and y ∈ H, nyx > nxy, it follows that every candidate in H are ranked ahead of those in C in the Kemeny social order; then, the Kemeny winner thus belongs to H while C contains the Kemeny k bottom-ranked candidate: thus, Kemeny rule cannot select the CLC. It follows that if there is no CLC while a Condorcet loser exists, this candidate cannot be a member of an elected committee.

Let us consider the Nanson rule. If there is a Condorcet winner, the proof is direct since we know that this candidate will never have a Borda score below the average. Let us assume that there is no Condorcet winner. Given C and H = A \ C, it follows from Theorems 1 and 2 that at each round, there is always at least one candidate x ∈ H who score better than at least one candidate y ∈ C; so, C cannot be elected. Thus Nanson rule never elects the CLC.

Let us show that the Copeland rule never elects the CLC when it exists. Consider the best candidate in the CLC; this candidate will get, in the best case, a Copeland score equal to k -1. Let us take a candidate outside the CLC and suppose that he loses all his pairwise comparisons against his fellows; he will then have a Copeland score equal to k. Thus the best candidate in the CLC has a lower score than the worst external candidate. Thus, the CLC cannot be elected with the Copeland rule. It is also obvious that whenever the CLC does not exist, a Condorcet loser cannot be a member of an elected committee under the Copeland rule.

We know from [START_REF] Kamwa | On Stable Rules for Selecting Committees[END_REF] that for voting profiles where there is a Condorcet winner (resp. a Condorcet loser) but no (Weak) Condorcet Committee of size k, KR, DR, YR, and SEO may pick a committee that does not contain (resp. that contains) the Condorcet winner (resp. the Condorcet loser) while this is never the case with MDC and NED. Theorem 4 tells us that among the Condorcet Consistent rules under consideration, only NED and Copeland 0 never lead to the CLC.

Theorem 4 Consider a voting situation m ≥ 4 where for a given k, there is no (Weak) Condorcet Committee while there is a CLC. Among the identified stable rules, NED and Copeland 0 never elect the CLC while this can be the case for KR, DR, YR, SEO and MDC. More, the CLC cannot be the unique element in the outcome set of MDC.

Proof The case m = 3 is de facto eliminated because if there is no (Weak) Condorcet Committee for a given k = 1, 2, it means that we are in the presence of a majority cycle and therefore of no CLC. [START_REF] Kamwa | On Stable Rules for Selecting Committees[END_REF] showed that when there is no (Weak) Condorcet Committee, KR, DR, YC and SEO may pick the Condorcet loser when he exists and that these rule may fail to picks the Condorcet winner while this is not the case with MDC and NED.

Let us prove that NED and Copeland 0 never select the CLC when it exists. Consider a profile π with m ≥ 4 such that for a given k (2 ≤ k ≤ m -1), X ∈ A k is the CLC and C k = ∅.

Notice that ∀a ∈ X, Cop 0 (a) the Copeland 0 score is as follows: 0 ≤ Cop 0 (a) ≤ k -1. Let us consider b the worst candidate in A \ X; we get Cop 0 (b) = k then Cop 0 (b) > Cop 0 (a). So, the worst candidate outside the CLC always scores more than every candidates in this set. Thus, Copeland 0 never selects the CLC when it exists.

Under NED, we get N

ED(π, X) = k(m -k). Assume that k < m -k and let us take a committee Y such that |Y |= k and X ∩ Y = ∅. Since C k = ∅, the NED score of Y is as follows 1 ≤ N ED(π, Y ) ≤ k(m -2k); as k(m -2k) < k(m -k),it follows that N ED(π, Y ) < N ED(π, X). So, NED cannot pick the CLC. Let now assume that k > m -k and consider a committee Z such that |Z|= k and X ∩ Z = ∅ with |X ∩ Z|= 2k -m. Since C k = ∅, the NED score of Z here is as follows 1 ≤ N ED(π, Z) ≤ (m -k)(2k -m). Since k(m -k) > (m -k)(2k -
m), it then follows that N ED(π, X) > N ED(π, Z). Thus, NED cannot pick the CLC.

To show that KR, DR, YR and SEO can select the CLC, let us consider the following profile drawn from Ratliff (2003, p.436) Assume that we want to select a committee of size k = 3. It is easy to check that for k = 3, there is no (Weak) Condorcet Committee while {b, c, d} is the CLC. After all computations, we report the scores for k = 3 as it follows: It comes that KR, DR, SEO and YC selects {b, c, d}; MDC selects {a, b, c}, {a, b, d}, {a, c, d}, and {b, c, d}. Thus the CLC in our profile belongs to the outcome set of each of the rules KR, DR, YC and MDC. So they may pick the CLC when it exists. We know from [START_REF] Kamwa | On Stable Rules for Selecting Committees[END_REF] that MDC never selects a committee containing the Condorcet loser picks; so, if the CLC contains a CL, this committee cannot be selected by MDC. Thus, this is the only case where MDC never picks the CLC.

Concluding comments

In the context of committee selection, we have introduced the notion of Condorcet loser Committee (CLC), a committee such that each of its members is beaten in pairwise comparisons by each of the external candidates. We have highlighted the fact that the most popular committee selection rules can select the selection CLC. Such a situation is proved to be questionable. Focusing on four groups of popular committee selection rules, we showed that:

The k-Borda rule (resp. the k-iterative Borda rule) is the only k-scoring rule (resp. k-iterative scoring rule) that never picks the CLC when it exists. Among the k-iterative scoring rules (with upward or downward eliminations), only k-iterative Borda rule never picks the CLC when it exists. Dodgson rule, Maximin rule and Young rule are k-Condorcet consistent rule that may select the CLC while this is never the case for the Kemeny rule, the Nanson rule and the Copeland rule. Among the seven stable rules encountered in the literature, only NED and Copeland 0 never elect the CLC.

Our results allow us to discriminate between the committee selection rules: those which can pick the CLC from those from those that do not. This study could be pushed forward by considering whether the fact that some rules elect the CLC when it exists is a rare fact or not. Table 2 goes a bit in this direction; it gives us for elections with 4 candidates, the limiting probabilities under IAC that the CLC of size k exists and is elected for some committee selection rules: k-Plurality (k-PR), k-Antiplurality (k-APR), Bloc, k-Nairu and Chamberlin-Courant rule (CCR). The message that can be drawn from Table 2 varies from one rule to another. We see that with CCR, the probabilities tend to increase with k the size of the committee. With k-Plurality, we note that when we go from k = 1 to k = 2, probability increases then decreases when we go from k = 2 to k = 3. We have an inverse pattern with k-Antiplurality, Block and k-Nairu. Results with more candidates and more voting rules would help us to draw more accurate conclusions. Nonetheless, such a work is not an easy task. One solution would be to rely on Monte-Carlo simulations or to investigate what happens with real-world data. Our Theorems 1 and 2 have allowed us to derive conclusions about committee selection rules that are not k-scoring rules such as Bloc and Chamberlin-Courant rule. It would also be interesting to look at the committee scoring rules introduced by [START_REF] Elkind | Properties of multiwinner voting rules[END_REF] as a broad class of rules encompassing almost all of the most common committee selection rules. By doing so, this would give a generalization of our Theorem 1.

Definition 3 (

 3 Condorcet Loser Committee (CLC)) A committee C ∈ A k is a CLC if and only if ∀x ∈ C and ∀y ∈ A \ C we have yM x.

n

  yx defines largest margin of loss of the members of C ∈ A k versus the non members. Committee C is selected under SEO if SEO(π, C) ≤ SEO(π, C ) ∀C ∈ A k \ {C}. The Minimal Number of External Defeats Rule (Coelho, 2004). Minimal Number of External Defeats Rule (NED) chooses the committee(s) for which the number of pairwise comparisons lost by its members is minimal. NED selects the committee C ∈ A k such that NED(π, C) ≤ NED(π, C ) ∀C ∈ A g \ {C} with NED(π, C) = x∈C |{y ∈ A \ C : n xy < n yx }| the number of pairwise comparisons lost by the members of C.

  4

  Definition 1 (Condorcet Committee à la Gerhlein (CCG)) A committee C ∈ A k is a CCG if and only if ∀x ∈ C, xM y ∀y ∈ A \ C.Definition 2 (weak Condorcet Committee à la Gerhlein (wCCG)) A committee C ∈ A k is a wCCG if and only if ∀x ∈ C and ∀y ∈ A \ C we do not have yM x.

Table 1

 1 Limiting probabilities of existence of the CLC under IAC

			m
	k	3	4	5	6
	1	0.937 0.838 0.747 0.677
	2	0.937 0.759 0.612 0.483
	3	-	0.838 0.602 0.426
	4	-	-	0.753 0.494
	5	-	-	-	0.683

  with four candidates and 33 voters. 5

	preferences 6 : abcd 10 : cdba 5 : bcda 1 : bacd	1	a	1	1	9	b	11	Pairwise comparisons vs a b c a -17 17 17 d b 16 -22 12
	10 : adbc	1 : dcab		d	11		c		c d	16 16	11 21	-11	22 -

Table 2

 2 Limiting probabilities under IAC that some committee selection rules pick the CLC when it exists

			Voting rules
	k	k-Plurality	k-APR	Bloc	k-Nairu	CCR
	1	0.0227	0.0238	0.0227	0.0033	0
	2	0.0394	0.0094	0.0015	0.0011	0.0032
	3	0.0056	0.0227	0.0227	0.0029	0.0056

The Condorcet Loser Criterion in Committee Selection

Determining the CCF requires voter preferences on all committees. This is not easy in practice. It is for this reason that this concept is less discussed in the literature than the CCG, which only requires the preferences on the candidates.

According to[START_REF] Tideman | Better voting methods through technology: the refinement-manageability trade-off in the single transferable vote. Public Choice 103(1-2): 13-34 The Condorcet Loser Criterion in Committee Selection Young H.P. (1975) Social Choice scoring functions[END_REF] "STV is not a specific voting method but rather a family of voting methods. [...] The different STV methods vary primarily in how much of which surplus votes are transferred and in the meanings that are attached to enough votes to be elected and the next available candidate."

Recall that Chamberlin-Courant rule[START_REF] Chamberlin | Representative deliberations and representative decisions: proportional representation and the Borda rule[END_REF]) is a voting rule that combines the Borda rule and proportional representation. Given a profile π, CCR selects the committee C which maximizes the representativeness value α(C, π) = x∈C i∈Nx(C,π) w(rix) where rix is the rank of candidate x in voter i's ranking, w(rix) = m -rix and Nx(C, π) the set of voters for which the representative in committee C is candidate x for profile π. This is the utilitarian version of the CCR; to more on the other versions/approximations of the CCR, the reader may refer to[START_REF] Elkind | Properties of multiwinner voting rules[END_REF].

This profile is drawn from[START_REF] Kamwa | On Stable Rules for Selecting Committees[END_REF].

This profile was used by[START_REF] Kamwa | On Stable Rules for Selecting Committees[END_REF] to show that KR, DR, YR and SEO can pick the Condorcet loser among the member of the winning committee.

Acknowledgments. The author would like to thank the participants of the CREM seminar in Caen, of the Workshop GDR Jeux in Besançon. Thanks to Vincent and Jérôme Lang for pointing out that some ways for extending our results.


Shaun D ' Souza

Intelligent supply chain management using Quantum

Algorithms provide a solutions approach to problems in computer science. A problem can be tractable (solved in better than polynomial time -NP-complete) or intractable (E.g. exponential time). Recent advances in the area of Quantum research are taking fruition as the field of quantum computing. With broad applications in Artificial intelligence and Optimization -Retail is the future application for quantum.

A subset of the algorithms are now orders of magnitude faster owing to the quantum speedup that would otherwise take years to solve on a classical computer. Some of these benefits come for free owing to the nature of quantum superposition and entanglement in a Quantum realm.

1 With exponential growth in the internet, cloud resources have become pervasive. While these are effective at solving a large number of problems, they do not scale adequately on a set of problems such as NP hard or computationally intractable problems -Figure 2. It is predicted that quantum systems will scale to >1000 qubits in the next decade opening up an array of algorithms in the areas of AI and optimization. Advanced use cases requiring higher number of qubits can be modeled on a simulator today. However, they run an order of magnitude slower as software is used simulate quantum properties. Algorithms translate into tangibles in source code. It is plausible that future quantum simulators could run on a quantum accelerator using vectors or tensors similar to the graphics and AI journey today. These could provide orders of magnitude speedup. Quantum computers exploit the properties of subatomic particles such as super positioning and entanglement allowing us to create new algorithms for existing problems. Measuring a quantum particle through observation destroys its state for future use.

It would take a classical computer years to solve a maximum cut or traveling salesman problem for example using brute force techniques. Dynamic approaches to algorithms can alleviate complexity and tractability problems in solving an optimality similar to divide and conquer [START_REF]Algorithms design[END_REF]. However, in the worst-case it could take exponential run time. These can be easily solved on today's quantum computers in no time. There are still fundamental constraints around the number of qubits available in the quantum cloud instances. Algorithms use a set of constraints to create a problem solution. Applications like spreadsheets, web browser, and email would continue to run in the classical paradigm. While specialized applications would run on a quantum computer. As the industry matures with ecosystem players, we will anticipate applications in optimization as well as AI and ML. Explicit and parallel programming can be cumbersome E.g. TensorFlow, Tensors. Abstractions are programmer friendly in the software paradigm E.g. Keras, OOP (Java, python), functional programming (SML). Libraries like Qiskit provide a viable API for a range of quantum applications [START_REF]Qiskit: An open-source framework for quantum computing[END_REF]. Some applications include - Artificial Intelligence is designed to mimic human tasks. While classical computers are compute & control bound. What that means is that a classical computer is good for general purpose programmability. The quantum computer lends itself to compute bound applications and is effective on tasks such as factorization or optimization. Some of the areas of interest include:

Quantum machine learning

Quantum information science

Quantum algorithms and software [START_REF]An invitation to the intersection of quantum computing and programming languages[END_REF] Selection tradeoffs in algorithms design include access to open-source code, pricing, licensing models, packaging, cloud deployment, security / reliability / uptime, proprietary ecosystems, legacy software, and phased lifecycles.

Quantum supply chain optimization

Today's clouds instances for quantum provide the user with both options of a quantum simulator and actual quantum bits. These could be used to devise algorithms for use cases in supply chain optimization allowing retailers to pass on cost savings to the consumer [START_REF]Quantum technology: Cutting the supply chain knot (forbes.com). accessed[END_REF].

The traveling salesman problem (TSP) is an example of an NP-complete problem. We can express the problem using a directed graph: G = (V, E) where V ∈ set of vertices E ∈ set of edges The goal is to discover the shortest distance over which the salesman can visit all the cities in the graph and return to his home location. With n vertices in a graph, the number of paths grow quadratically as n 2 and complexity n! making it NP-hard. Even a small graph with 10 cities would take 100 qubits to solve on a quantum computer. This could be solved today on a classical computer for less than 50 cities, however, becomes intractable for larger number of nodes. As quantum computers improve in the next decade -Table 1, larger number of qubit machines would be able to take on these complex problem challenges with ease. In this section we look at the distribution network of a leading medical retailer with stores in the regional USA. The figure shows the proposed network solution solved using a quantum algorithm for the TSP and Maximum cut (NP-hard). A classical algorithm would we able to address up to 20 stores using today's platforms. Figure 5 a / b shows the path using a quantum solution. A combination of quantum and unsupervised learning (clustering) could be used for more sophisticated use cases to approximate store locations or distribution centers in the vicinity.

Optimal route planning enables us to bring about operational efficiencies in the endto-end Supply chain. Future work include quantum neural networks, quantum machine learning, and quantum programming languages.

Part II

Quantum Retail applications

In Part 2 of our edition on Quantum and Retail we continue to look at how Quantum will drive retail applications. Read Part 1 on the Intelligent supply chain. While Quantum computing will not replace classical applications, it will enable key functions around Quantum machine learning and Optimization for retail customers. The pandemic has disrupted consumer behavior and retailers have had to adapt to newer dynamics and customer trends.

Quantum instances are today available in the cloud by some of the leading vendors like IBM, Microsoft (Azure Quantum) and Google [START_REF]Hello quantum world! google publishes landmark quantum supremacy claim[END_REF]. It is forecast that quantum systems will scale to > 1000 qubits in the next decade opening up an array of algorithms in the areas of AI and optimization. Advanced use cases requiring higher number of qubits can be modeled on a quantum simulator today.

Quantum computers outperform their classical counterparts on tasks that are algorithmically intractable (solved in exponential time or NP-hard). Retailers are grappling with rising number of stores, revenues, routes, volumes, transport capacity, and utilization constraints [START_REF]What business 4.0 means for global enterprises[END_REF]. Quantum will enhance business deliverables in an ever-expanding and complex SCM ecosystem. We explore a realm where quantum meets retail.

Industry perspectives on Quantum

Following Artificial Intelligence, Quantum is the next iteration in intelligent computing. It sits along other technologies such as the distributed ledger (cryptocurrency and blockchain) and extended reality (metaverse). These are collectively referred to as DARQ.

Human-machine. AI and software are today ubiquitous. In the conventional paradigm parallel programming, concurrency, and synchronization are used to achieve speedup goals. Algorithms translate into tangibles in source code. Quantum will leap us into the Fifth industrial revolution with AI, blockchain, and data analytics being the Fourth industrial revolution [3].

NP-completeness.

A subset of the algorithms are now orders of magnitude faster owing to the nature of quantum superposition and entanglement. Some of these benefits come for free owing to the nature of quantum particles.

Platforms / algorithms as an abstraction

Some vendors for Quantum computing programming languages are IBM (Qiskit), Rigetti (PyQuil), Google (Cirq), and Microsoft (Q#). Quantum computing today lies at the intersection of computer science and quantum physics. It uses quantum laws at the algorithmic level. Classical algorithms function as Boolean logic. Developers will continue to use the same tools, languages, and code in a quantum paradigm -Figure 6.

Windows was the hot application for the classical computer. Retail is the next hot application for the quantum computer! Quantum applications will deliver Retail value creation through numerous venues. Some of these are: Fleet management. The routing of delivery vehicles, their loading and fill.

We can conceptualize the supply chain as a complex network of graphs. Nodes in the graph corresponding to stores or DCs and the edges as the links connecting these entities. The goal is to minimize the travel distance and overlapping routes and/or additional constraints around capacity. Retailers are looking to provide forecast guidance in applications such as demand forecasting, product end-of-life, and promotional forecasting. With ability to learn from time series and regression data Quantum models will enable future supply chain forecasting tasks.

Stochastic modeling. AI/ML models learn outcomes from real data/parameters and business rules. These can be applied to supply chains, i.e., predicting store sales for a given calendar day based on historical sales data. Typically, such promotions are governed by retailer goals and constraints / business rules. The data points provided are typically evaluated in conjunction with business rules such as seasonality, promotional events, day of the week, and state or school holidays. Quantum ML has large applications in kernel feature estimation [START_REF]Supervised learning with quantum-enhanced feature spaces[END_REF]. These are traditionally done using classical approaches to reduce the feature size of a training dataset. Some techniques for dimensionality reduction are Principal Component analysis (PCA) and Linear Discriminant analysis (LDA). These are used to map higher dimensional datasets into a representable space to be used by a Machine learning algorithm -Figure 10. A novel feature space representation can be the difference in training a robust ML model vs. one with ambiguity. Use cases for text include the creation of Topic models to classify unstructured text [START_REF]Probabilistic topic models[END_REF]. 11 GPT-3 Quantum dataset Datasets like the GPT-3 [START_REF]Openai gpt-3[END_REF] could be trained using Quantum models. It is predicted that the answer to life and everything in the universe could be described in 5 trillion parameters from state of the art models such as the OpenAI GPT-3 1 . Modern day applications use fewer parameters and can be trained with precision in the present generation of AI models. Data sets like the GPT-3 are used in a wide variety of tasks for natural language. Their deep learning models can produce human-like texts. With applications in text classification, translation and chatbots. However, these take long amounts of time to train with costs in the millions of dollars. GPT-3 with 175 billion parameters has been trained on 500 billion words at a cost of 5 million dollars. Future models can be trained using Quantum AI. Customers today are moving from brick-and-mortar stores to online in a globalized economy. Retailers are ramping inventory to cope with rising demand with increasing number of products (SKUs) and fulfillment channels. Current approaches in supply chain optimization look at a combination of greedy heuristics. These provide an adequate balance of business value and customer satisfaction. With rising number of stores, routes, transport capacity and utilization constraints, our goal is to further enhance business deliverables in an ever-expanding and complex SCM ecosystem. Note: Protocols like one-time passwords (OTP) and OAuth are the norm today in e-commerce transactions. Some research challenges include software, more algorithms (cryptography, randomness) and interdisciplinary collaboration (social), GDPR. Organizations would grow these functions organically as quantum applications become mainstream in business / entrepreneurial and government initiatives. IBM does have a foothold in this area with Qiskit. However, I am sure Microsoft (Azure Quantum), and Google would catch up here soon. It is the right time to invest into the quantum market [START_REF]Quantum algorithm zoo[END_REF].

D Classical solution objective

Appendix D shows a solution for a network with up to 20 cities but becomes NP-hard to solve classically for larger number of nodes. It is forecast that quantum computers with greater than 10's of thousands of qubits will be available in the coming decade. These would outperform today's computers and simulators providing linear speedup to some of our most complex network problems.

Figure 1 :

 1 Figure 1: Qubit representation

Figure 1

 1 Figure 1 shows the Bloch sphere corresponding to the state space of a qubit. It depicts a visual representation to denote quantum information.

Figure 2 :

 2 Figure 2: Algorithmic complexity

Figure 3 :

 3 Figure 3: Dynamic programming decomposes a problem into subproblems

Figure 4

 4 Figure4shows a case study where an automobile manufacturer and distributor was looking to optimize their supply chains. The use case is especially relevant to Retail customers and can bring billions of dollars in savings in operational costs.

Figure 4 :

 4 Figure 4: Optimization

3

  Fields of studyWe can map some of the classical algorithms such as Linear programming or Quadratic programming to a quantum application as shown in Listing 1 -4. Listing 1: Quadratic programs from qiskit_optimization import QuadraticProgram quadratic_program = QuadraticProgram() Listing 2: QUBO -Quadratic Unconstrained Binary Optimization from qiskit_optimization.converters import QuadraticProgramToQubo qp2qubo = QuadraticProgramToQubo() Listing 3: QAOA -Quantum Approximate Optimization Algorithm [9] from qiskit.algorithms import QAOA qaoa = QAOA(optimizer = ADAM()) Listing 4: VQE -Variational Quantum Eigensolver from qiskit.algorithms import VQE, NumPyMinimumEigensolver vqe_optimizer = MinimumEigenOptimizer(vqe)

  (a) Traveling salesman problem (n = 4) (b) Maximum cut (n = 10)

Figure 5 :

 5 Figure 5: Quantum solution objective (a graph with 5-10 vertices and up to 40 edges)

Figure 6 :

 6 Figure 6: Quantum programming languages taxonomy

Figure 7 :

 7 Figure 7: Vehicle routing problem

Figure 8 :

 8 Figure 8: Knapsack problem

Figure 9 :

 9 Figure 9: Retail forecasting -daily sales

Figure 10 :

 10 Figure 10: Fashion MNIST [2]

Figure 11 :

 11 Figure 11: Topic modeling

B 4 1 Bounds

 41 points traveling salesman problem expressed as a quadratic optimization Minimize obj: [ 96 x_0_0*x_1_1 + 96 x_0_0*x_1_3 + 182 x_0_0*x_2_1 + 182 x_0_0*x_2_3 + 66 x_0_0*x_3_1 + 66 x_0_0*x_3_3 + 96 x_0_1*x_1_0 + 96 x_0_1*x_1_2 + 182 x_0_1*x_2_0 + 182 x_0_1*x_2_2 + 66 x_0_1*x_3_0 + 66 x_0_1*x_3_2 + 96 x_0_2*x_1_1 + 96 x_0_2*x_1_3 + 182 x_0_2*x_2_1 + 182 x_0_2*x_2_3 + 66 x_0_2*x_3_1 + 66 x_0_2*x_3_3 + 96 x_0_3*x_1_0 + 96 x_0_3*x_1_2 + 182 x_0_3*x_2_0 + 182 x_0_3*x_2_2 + 66 x_0_3*x_3_0 + 66 x_0_3*x_3_2 + 126 x_1_0*x_2_1 + 126 x_1_0*x_2_3 + 142 x_1_0*x_3_1 + 142 x_1_0*x_3_3 + 126 x_1_1*x_2_0 + 126 x_1_1*x_2_2 + 142 x_1_1*x_3_0 + 142 x_1_1*x_3_2 + 126 x_1_2*x_2_1 + 126 x_1_2*x_2_3 + 142 x_1_2*x_3_1 + 142 x_1_2*x_3_3 + 126 x_1_3*x_2_0 + 126 x_1_3*x_2_2 + 142 x_1_3*x_3_0 + 142 x_1_3*x_3_2 + 184 x_2_0*x_3_1 + 184 x_2_0*x_3_3 + 184 x_2_1*x_3_0 + 184 x_2_1*x_3_2 + 184 x_2_2*x_3_1 + 184 x_2_2*x_3_3 + 184 x_2_3*x_3_0 + 184 x_2_3*x_3_2 ]/2 Subject To c0: x_0_0 + x_0_1 + x_0_2 + x_0_3 = 1 c1: x_1_0 + x_1_1 + x_1_2 + x_1_3 = 1 c2: x_2_0 + x_2_1 + x_2_2 + x_2_3 = 1 c3: x_3_0 + x_3_1 + x_3_2 + x_3_3 = 1 c4: x_0_0 + x_1_0 + x_2_0 + x_3_0 = 1 c5: x_0_1 + x_1_1 + x_2_1 + x_3_1 = 1 c6: x_0_2 + x_1_2 + x_2_2 + x_3_2 = 1 c7: x_0_3 + x_1_3 + x_2_3 + x_3_3 =

Figure 12 :Figure 13 :

 1213 Figure 12: Classical solution objective (a graph with 20 vertices and up to 200 edges)

Table 1 :

 1 See Appendix C. Quantum roadmap

		2019 2020 2021	2022 2023 2024+
	Qubits	20	50	100	500 1000 1k -1M
	Simulator 500 1000 5000+

A Bra-ket notation

The state of a qubit can be described as -|q = α |0 + β |1 , where α, β ∈ C and |α| 2 + |β| 2 = 1 So that when a quantum particle is measured it would observe a |0 with probability |α| 2 and |1 with probability |β| 2 . Their corresponding vector notations are denoted by

These provide an orthogonal basis to represent the state of a quantum system. We can view the state of a quantum system as a complex linear superposition of its basis states

This demonstrates a property of quantum particles. E.g. An n-qubit system can exist in any superposition of the 2 n basis states.

As per Heisenberg uncertainty principle, quantum physics limits how we can measure certain properties of a sub-atomic particle and its state such as position or momentum accurately.