m = 12 for different values of k and n. . . . . . . . .

ACKNOWLEDGMENTS

While I am incredibly grateful to so many people who have supported me throughout my PhD journey, I have never been very good at expressing my gratitude in words. For this reason, as I write this section, I realize that one of the things I am grateful for is this very thesis for prompting me to take the time to express feelings that too often go unspoken. This process has allowed me to reflect on the incredible support and encouragement that I have received from so many people, and has reminded me of how fortunate I am to have such wonderful friends, family, colleagues, and mentors in my life.

The first people I would like to thank are the members of my jury for their valuable comments and insightful feedback during the revision and the defense of my thesis. Their constructive criticism and suggestions have been immensely helpful in improving the quality and clarity of my work. Without their guidance during the pre-defense of my thesis this dissertation would not be what it is today.

My deep gratitude goes to my supervisors, Remzi Sanver and Olivier Cailloux, for their unwavering support, advice, and encouragement throughout my research journey. Remzi's expertise, mentorship, and willingness to share knowledge have been instrumental in shaping the direction of my research. Olivier's dedication to work, guidance and attention to details have contributed in shaping who I am today as a researcher but also as a person. Olivier, even though I may have rolled my eyes at times, I will never forget your meticulous comments, jokes and our insightful discussions. Your words of encouragement, constructive feedback and your confidence in my abilities have been a source of motivation and inspiration, even during the most challenging times. Thank you both for being there even when I did not know I needed you.

I would also like to extend my appreciation to all the PhD students in our lab for creating such a positive and collaborative atmosphere. Most of these past few years have been marked by a pandemic that disrupted all of our lives and we have not been able to take advantage of the classical social events. However, this has not prevented the growth of important relationships and deep friendships that I hope will continue in the future. I also thank all the members of LAMSADE, including professors and administrative staff, for the warm welcome I received when I joined the lab. I feel grateful to have had the opportunity to work alongside such an amazing group of people.

I am especially grateful to Jérôme Lang, for helping me during a tough time when he himself was going through a very hard moment in his life. His generosity and kindness have been invaluable and I will never be able to fully express my gratitude.

Although I never told him, I would also like to thank Umberto Grandi, for responding to a stranger's email in the middle of the summer of some years ago asking for an internship for the following week. I consider this event as the sliding doors moment of my life. Umberto has been extremely kind and welcoming, taught me the fundamentals of a field that was completely new to me until then, and believed in me and supported me from the beginning. This opportunity not only allowed me to gain valuable experience and skills but also opened the door for my PhD. i Moreover, it allowed me to get to know the person who, years later, became my life partner.

Perhaps the greatest thanks goes to this very person, my partner in crime, my soulmate. Arthur, your presence in my life has been a constant source of comfort and strength, I am grateful for your love and patience during the most challenging times. You are my number one fan, my best supporter. You have stood by my side through the ups and downs, always offering a shoulder to lean on and you pushed me to keep going, even when I felt like giving up. I feel incredibly lucky to have you in my life. Thank you for being such an amazing partner and for always having my back. Thank you for being you.

Finally, I would like to express my deepest gratitude to my family and friends for their love, encouragement, and understanding during this challenging yet rewarding period of my life. Their support and belief in me have been a constant source of motivation and inspiration. Thanks to the old friends who have always stood by my side despite kilometers of distance, friendships made up of texts and video calls. Friendships where you don't hear from each other for weeks but a phone call is enough to shorten time and distance. Friendships made up of venting and support but also laughter and memes. Thanks to the new friends, who became my Parisian family since we met the first week I set foot in this new city. The friends who bring you a hot meal when you are sick and who come to help you move even when you don't ask them to. Thanks to my acquired family, Arthur's parents and siblings, who welcomed me into their family with open arms. Their kindness, warmth, and generosity have made me feel like a part of the family from the very beginning and they have shown me nothing but love and support.

And, last but not least, thanks to my family. Their sacrifices and support, have allowed me to pursue my dreams and achieve milestone after milestone in my academic career. Every departure has been heartbreaking, but my family has always been the first to encourage me to follow my ambitions. The packages that they periodically send from Cosenza to Paris are full of coffee, chocolate and sausages only to the outside eye, but in reality they are primarily full of love. I feel grateful and blessed to have such a wonderful family who have always been there for me, no matter the distance. Thank you for being my rock and my foundation, and for making me the person I am today.

INTRODUCTION

Democracy is difficult, flawed and unstable. It involves barely distinguishable political parties taking part in lengthy, over-complicated and expensive decision-making processes. Trying to engage so many people with political issues seems to lead only to complexity and disagreement. So why bother?

-Michela Murgia, Istruzioni per diventare fascisti (Trans. How to be a Fascist: A Manual by Alex Valente)

Collective decision-making is a process in which individual preferences are aggregated to form a single group choice. This broad definition allows many instances, that seem very different from each other, to fit into this category. Some examples include fair allocation problems-which address the problem of fairly dividing some resources among individuals who have different interests in such resources, e.g. houses allocation, creation of a working schedule etc.-matching problems-which deal with the problem of matching individuals from two separate groups considering their preferences, e.g. students to schools, tenants to houses etc.-and judgment aggregation problems-which try to group the beliefs of different individuals into a judgment that reflects the society as a single entity. In this thesis we will focus on another example of collective decision-making: voting. Given a set of individuals who express their preferences over a given set of candidates, how do we select the best candidate for the group? This is a very ancient dilemma that has been faced multiple times during centuries and that we are going to tackle throughout this manuscript. As we shall see, the answer depends on many factors, such as the information we have at our disposal -do we know the preferences of all voters with respect to all candidates? -and the properties we want the outcome to satisfy -what do we mean by the best candidate? Who decides what is best?

An important methodology in our work is to define desirable properties we want a rule to satisfy. This allows us, on one hand, to divide aggregation rules into classes of methods satisfying the same properties, and, on the other hand, to do the inverse process: starting from an already defined method to help the decision-maker understand its properties. The lack of information and the assistance to decision-makers are two of the themes explored in the course of this work.

This introductory chapter aims to introduce the contributions and organization of this dissertation, but also, and maybe more importantly, to introduce its motives. We have mentioned the analysis of aggregation processes through the definition of desiderata, but this axiomatic approach is very recent and started only after the publication of the Ph.D. thesis of Kenneth Arrow [1951]. The theory behind collective decision-making processes is, however, much older and, as [START_REF] Mclean | The borda and condorcet principles: Three medieval applications[END_REF] wrote, "the theory of voting is known to have been discovered three times and lost twice".

To understand what we are studying today, we think it is essential to take a look at the past. Starting from the first traces of decision-making processes in history, we consider early voting mechanisms that focused mainly on particular cases. From the analysis of specific instances, we move on to the start of Social Choice Theory as a formal scientific discipline. We then focus on how it has managed to evolve by incorporating computational aspects typical of the computer science field. Finally, we discuss how this led us to investigate the problems that will be described in the following chapters and we outline our contributions.

Voting rules from practice to theory

The first records of collective choice problems can be traced back to ancient Greece (ca. 500 BC), and the word democracy itself originated from the greek dēmokratiā: dēmos people and kratos rule. Many scholars, including Aristotle, have described in details the functioning of Athenian democratic institutions, however they never formally analyzed voting processes. This appears to be partly due to the fact that Athenian voters where asked to express their preferences over only two alternatives: the choices were often in the form of yes/no, banish/not banish [McLean and Urken, 1995]. Today we know that most of the problems in social choice arise when at least three alternatives are considered.

From ancient Rome to the Middle Ages: the precursors of social choice. A problem concerning the use of three alternative is exactly the reason that brought Pliny the Younger, a magistrate of Ancient Rome, to write a letter to his jurist friend Titius Aristo (105 AD). In the letter, that can be found translated in McLean and Urken [1995, Chapter 2], Pliny asks Titius advice about a problem that emerged during a vote in the Senate. A consul had been found dead and his servants were suspected of his death, the Senate had to decide whether to free them, to banish them or to put them to death. For the first time they were facing a problem with more than two choices and, with it, its related issues. Pliny explains that the first option was acclaimed by the largest number of senators but not by the majority of them. Thus, he asked the Senate to consider the alternatives as three separate ones on the principle of huge disparity in punishments, and tried to arrange a series of binary votes among the three verdicts. Pliny was aware of his own attempt to manipulate the elections in favor of his top choice, freeing the slaves, but so was one of his adversary, supporter of the death penalty. The latter knew that the most lenient sentence would have won in binary votes against banishment and death taken separately, so he withdraw his proposal that could not have defeated any of the others. The supporters of death penalty then moved their support to banishment that easily won, having now a strong majority. Note how by changing the way we aggregate the same set of preferences we can have completely different outcomes.

Pliny's concern shows how some desiderata of electoral protocols are not only restricted to modern society. The desire for a transparent system that was difficult to manipulate was present also in medieval elections. However, after Pliny, the democratic process did not find much room in the public discussion. The only two exceptions of abstract works on voting rules in the Middle German theologian and philosopher who studied Llull's De arte eleccionis. He rejected Llull's work and proposed his own voting procedure in a chapter of his work De concordantia catholica [ca. 1431-34] (Catholic concordance), which can be found in McLean and Urken [1995, Chapter 4]. Cusanus' main concern was to reduce manipulation and strategic voting and he recommended a Borda count method with secrete voting. We must say that there are no evidence that Cusanus was aware of the other two methods proposed by Llull, but only of the Condorcet-like one. With this in mind, we can see that although both Llull and Cusanus wanted to reduce manipulation, the methods they proposed turned out to be quite different. This is probably due to the different contexts they were considering. Llull had in mind an election where members of an abbey had to select their own leader: voters were people who knew and trusted each other and would have lived together even after the vote. Cusanus, on the other hand, wrote De concordantia catholica while attending the Council of Basel: voters were people that would have met only once to elect the new head of the Catholic Church and had their own interests and strategies. This underlines a very important point about voting methods: context matters. If we were to define a voting procedure, the first thing to consider is "to elect what?".

Enlightenment and the revival of choice. To find new discussions on voting procedures we must skip the rest of the Middle Ages and move on to the Enlightenment. In particular, we must travel to the France of the late eighteenth century. This should come as no surprise since by that time, in France, sciences had been extremely well organized for at least a century already through the establishment of the "Académie royale des sciences" by Louis XIV in 1666 [START_REF] Demeulenaere-Douyère | L'académie des sciences des origines au milieu du XXe siècle[END_REF]. Starting from 1753, membership to the Academy was decided through elections using plurality rule and in 1770 Jean-Charles de Borda argued that this method could lead to undesirable results. In particular, he showed how the candidate elected under plurality could lose in case of pairwise comparisons and he proposed, instead, a rank order count -what we now call Borda count which is also equivalent to the Cusanus method. Although Borda presented these observations to the Academy in 1770, elections continued to be conducted using plurality rule and his work was published many years later [START_REF] De Borda | Mémoire sur les élections au scrutin[END_REF]. One of the reasons for this delay has been attributed to one of his political opponents: Nicolas de Condorcet [START_REF] Urken | The Origins of Social Choice Theory[END_REF] -also known as Marquis of Condorcet. In fact, the latter had meanwhile become secretary of the Academy, presumably also thanks to the voting method in place, and was responsible for scheduling publications. The year after the publication of Borda's method, the Marquis of Condorcet also proposed a voting procedure, the one we now recognize as equivalent to LLull's method [START_REF] De Condorcet | Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix[END_REF]. After the revolution, the Academy was reformed into the so-called "Institut de France" and Napoleon appointed a commission to study the voting mechanisms to be used within it. The commission chose Borda's method but after a while Napoleon took the unilateral decision to switch back to the use of plurality.

Once again, all these works were ignored until the second half of the 20th century. One of the few noteworthy works is that of Charles Dogson, better known as Lewis Carroll. Although not aware of the studies of the Marquis of Condorcet, in 1876 he proposed a voting procedure that solves the paradox arising in the Condorcet method when cycles occur. In his proposition the winner is the only candidate that wins every pairwise comparison (Condorcet winner). If such a candidate does not exist then for each candidate we count the number of changes in the voter preferences required for they to be the Condorcet winner. The elected candidate is the one associated to the lowest number of changes.

The axiomatization of social choice theory. This concludes a brief introduction to the start of voting theory which has so far been concerned with analyzing procedures, and their related problems, on the basis of examples. From this point on, and especially since the publication of the Ph.D. thesis of Kenneth [START_REF] Arrow | Social Choice and Individual Values[END_REF], social choice theory emerges as a scientific discipline. Arrow, in fact, was the first to introduce axiomatic analysis of aggregation methods and to characterize classes of rules on the basis of the set of properties they satisfy. In his thesis, he also defines a small set of axioms that seem naturally desirable and then he proves that the only voting rule able to satisfy them all is the dictatorship. This opened the door to the research that followed over the next sixty years.

In the meantime, however, the aforementioned works were still unknown to the general public, until a few years later, when Duncan [START_REF] Black | The Theory of Committees and Elections[END_REF] published the book that soon became the basis of Social Choice Theory: The Theory of Committees and Elections. From this point onward, new axioms are recurrently proposed and new electoral rules analyzed. In Chapter 2, we will describe the most relevant ones to this work.

For reasons of space, and complexity of the topic, many authors who have worked on electoral procedures -e.g. Pufendorf, Daunou, LaPlace, Lhulier, Nanson, Galton, Scitovsky, Bergson, Samuelson etc.-have not been mentioned in this chapter. More details on the history of Social Choice Theory can be found in [START_REF] Black | The Theory of Committees and Elections[END_REF], McLean and Urken [1995], [START_REF] Mclean | The borda and condorcet principles: Three medieval applications[END_REF], [START_REF] Urken | The Origins of Social Choice Theory[END_REF]. Some other excellent sources for approaching the study of this discipline are: [START_REF] Arrow | Handbook of Social Choice and Welfare[END_REF][START_REF] Arrow | Handbook of Social Choice and Welfare[END_REF], [START_REF] Gaertner | Primer in Social Choice Theory[END_REF], [START_REF] Fishburn | The Theory of Social Choice[END_REF], [START_REF] Taylor | Social Choice and the Mathematics of Manipulation[END_REF], [START_REF] Nitzan | Collective Preference and Choice[END_REF].

The origin of computational social choice. Starting from the first traces of decision-making processes we have almost reached the present days. But we are still missing something to complete the picture. All rules mentioned so far never considered the computational cost of executing these procedures. Since Arrow, an aggregation method has been viewed as more or less reasonable on the basis of the axioms, the properties, it satisfies. However, the same rule may be proven impractical in its use [START_REF] Bartholdi | Voting schemes for which it can be difficult to tell who won the election[END_REF][START_REF] Rothe | Exact complexity of the winner problem for young elections[END_REF][START_REF] Hemaspaandra | The complexity of kemeny elections[END_REF][START_REF] Davenport | A computational study of the kemeny rule for preference aggregation[END_REF]. Furthermore, most of the traditional rules require voters to express an order of preference over all alternatives. When the set of candidates is very large this comes at a huge cost, both from a cognitive and communicative point of view. If we were to decide where to have dinner, how would we expect all voters to order dozens, or even hundreds, of restaurants? What if some choices are not comparable [START_REF] Pini | Incompleteness and incomparability in preference aggregation[END_REF]? Even assuming that voters are prepared to make such an effort, what is the cost of communicating all this information [Lang, 2004, Conitzer and[START_REF] Conitzer | Communication complexity of common voting rules[END_REF]? It is from all these questions (and many others such as the cost of manipulability for example) that many computer scientists have become interested in problems previously restricted to social theory. The first time the term Computational Social Choice was used to refer to this specific area of research was in 2006, during the first edition of the COMSOC workshop (Amsterdam). "The Handbook of Computational Social Choice" brings together the main notions of all major research sub-areas related to this new field [START_REF] Brandt | Handbook of Computational Social Choice[END_REF].

Research questions and contributions

Studying the history of aggregation methods, we realized that starting from a wide spectrum of procedures we can identify classes whose elements satisfy common properties. Given a method we can analyze the axioms it satisfies. The power of this is that we could also go the other way round: given some preferences about the properties that the rule must respect, we can help the decision-maker to define their desired aggregation method. One of the points we will focus on is precisely this:

• how can we help the decision-maker formally define an electoral rule on the basis of generic preferences about its properties?

In Chapter 4 we will study a situation in which a committee of non-experts has to decide how to aggregate the preferences of voters. Assume that the committee assigns a score to each position in the preference order of the voters. So, for example, the first ranked gets 10 points, the second 5 etc. Imagine now that the committee wishes the score of the best choice to be "much higher" than the one of the third best choice. How do we translate this "much higher" into a voting rule? What exactly does it mean? In this thesis we will focus on a particular class of rules, Positional Scoring Rules -which we will describe in detail in Chapter 2 -and develop a method for asking questions to the committee in terms of picking winners in an example profile. So, we transform a complex question involving differences of weights between consecutive positions into questions more easily answerable by a human committee such as "who should win in this profile"? From the answer to this question we deduce the answer to the original question.

Note how an important concept that we encountered when discussing Llull and Cusanus returns here. Both wanted to solve the same problem by proposing two different methods. This is because they were considering the problem within different contexts. Context is extremely important when defining a voting rule; there is no best rule that we can choose to apply in every case. That is why it makes sense to ask questions to the committee and really understand what it means in their context for an alternative to be ranked first rather than third. The answers could vary a lot depending on what kind of preferences are being aggregated and what is being elected. This idea will come back later when we will discuss Chapter 7.

Another important problem -which we mentioned introducing the field of Computational Social Choice-when deciding on a voting rule is its cost. This is a point that we also find in our first research question. In this case it is represented by the cognitive cost for non-experts to formalize a voting rule on the basis of some generic preferences. But, as we know, the cost is also related to voters when they have to order a large set of preferences, and computational in transmitting all this information. This awareness leads us to study strategies of voters preferences elicitation:

• how can we acquire the most relevant information at the lowest cost?

We study this question for different voting rules (Positional Scoring Rules and Majority Judgment) in Chapters 4 and 6. In particular, in Chapter 4, we combine this research question with the first one and we try to understand whether, in a context of zero information, interleaving the elicitation of voter preferences and the elicitation of the voting rule yields better result than 1.3. ORGANIZATION OF THE THESIS a more linear approach. In Chapter 6 we will study concrete scenarios taken from real voting situations, in which voter preferences are obtained by asking a given number of random questions to voters. Among other things, we will investigate how to identify the minimum number of questions to be asked so that the probability of eliciting the winner, using the Majority Judgment rule, is high.

Coming back to the idea "different contexts, different definitions" we began to wonder how different situations could justify the use of different voting rules that seek to achieve the same goal. In the literature, various notions of compromise have been proposed, and with them various voting rules that more or less attempt to implement these definitions. When we talk about compromise what we mean depends very much on the context, when we want to decide where to dine we are probably fine with voters trying to find a middle ground even if the outcome does not turn out to be a compromise. This is the case with some voting rules that we will discuss later on, such as Fallback Bargaining, where it may happen that the outcome is the best choice for some voters but highly disliked by many others. However, when we deal with contexts where egalitarianism -which we will interpret as everyone conceding equally-is a major concern, this notion of compromise is not acceptable anymore. On these bases, we develop the grounds for our concept of compromise:

• how can we define the notion of compromise where each voter concedes as equally as possible?

In Chapter 7 we address this question and analyze which of the existing rules, if any, satisfy this new definition. We will see that different definitions make sense in different contexts and that one is not necessarily better than the other.

Organization of the Thesis

In what follows we will describe how this manuscript is organized.

Chapter 2 collects the important notions that are the basis of the themes discussed in this thesis and that will return recurrently in subsequent chapters. We will describe the difference between voting with different types of ballots: ranked ballots, which we will use in Chapters 4 and 7, and rated ballots, which we will consider in Chapter 6. We will describe the voting rules we will use in our contributions and some of the axioms that characterize them.

In Chapter 3, using the same approach used in this introduction, we will dig into the past to position our work. In particular, in Section 3.1, starting from the meaning of compromise we will trace its use throughout history. We will analyze the definitions that have been given of compromising rules in social choice theory and point out how some of them do not represent certain ideas of compromise. We will show how our approach fits within this literature. Noting that the Majority Judgment rule is seen as a form of compromise in the literature, we will delve into this rule in Section 3.2. We will study its introduction, its uses and also its criticisms. As the last topic of this chapter, we cover in Section 3.3 another important aspect of this thesis: Preference Elicitation. In fact, if so far it has been assumed to know the preferences of voters and the voting procedure, this cannot be taken for granted. That of preference elicitation is a well studied problem and we will describe the different approaches by which it has been tackled in the literature. In addition, we will mention how it has been addressed in different fields, particularly in the decision aiding and machine learning literature, and the similarities with our approach.

Part II includes our contributions. Specifically, Chapter 4 is an article published in an international conference [START_REF] Napolitano | Simultaneous elicitation of scoring rule and agent preferences for robust winner determination[END_REF] and Chapter 7 is an article published in a journal [START_REF] Cailloux | Compromising as an equal loss principle[END_REF]. Chapter 5 accompanies Chapter 4 by describing the code provided in support of the contribution. Finally, Chapter 6 is an original contribution, not yet published, whose goal is to study the consequences of the elicitation process in a voting situation that uses Majority Judgment.

To conclude, Chapter 8 provides a summary of the contributions of this thesis and some perspectives for future directions.

CHAPTER 2

PRELIMINARIES AND NOTATION

In the introductory chapter we have mentioned different concepts like voting, preference aggregation processes, voting rules. All these terms are rather vague if we do not provide precise definitions. In this chapter we will present the main notions we will use throughout the course of the dissertation and assign them precise meanings.

It is worth specifying that when we talk about voting we imply an aggregation of votes expressed through a ballot. The term ballot comes from the ancient Italian ballotta, a small ball used in medieval elections to cast a vote. We can already find references to golden or silver balls used by the members of the various committees in the long procedure of electing the Doge after Venice's ordinance [START_REF] Doglioni | Le Cose Notabili Et Maravigliose Della Citta[END_REF]. Over time, the term has assumed the generic meaning of a method to cast a vote (often secret). In this dissertation we mainly use linear orders of preferences as ballots, i.e. each voter specifies which candidate is her best choice, her second choice and so on. However, this representation is often blamed as the reason for the impossibility results described by [START_REF] Arrow | A difficulty in the concept of social welfare[END_REF]. Other types of ballots have been proposed, for example [START_REF] Balinski | Majority Judgment: Measuring, Ranking, and Electing[END_REF] consider voters' judgments on candidates rather than preferences. To give an idea of the difference between these two representations we can imagine that in the case of ordered ballots a voter would say "I prefer alternative a to alternative b" while using judgments he would say "I consider alternative a excellent and alternative b mediocre". The latter notion will be explored in Section 2.2 and further on in Chapter 6.

A set of ballots constitutes the input of the aggregation function, since there are different representations of this object, this means that we can define different functions on different inputs. But what is the output? Here again, there is no single answer. One can consider resolute functions, i.e. functions that return a unique winner. In such cases, whenever there are ties between candidates, mechanisms are designed to break them. However, this is not the assumption we will make in the course of this manuscript. The functions we will describe return the set of winning candidates.

It is important to emphasize that since these functions can be defined on different inputs and outputs, they are different mathematical objects. If we define a desirable property of a function that uses ranked ballots it might not be possible to convert it into a property of a function that uses judgments, and vice-versa.

Voting with ranked ballots

A social choice setting consists of a set N of n individuals-or voters-who have preferences over a set A of m alternatives. A social choice problem deals with aggregating those preferences, through the use of a social choice rule, to obtain a common choice for the group. The preferences of individuals are represented by linear orders over the set of alternatives A. In general, a linear order ≻ on a set X is a relation that is:

• irreflexive: a ̸ ≻ a, ∀a ∈ X • transitive: a ≻ b ∧ b ≻ c ⇒ a ≻ c, ∀a, b, c ∈ X • complete: a ≻ b ∨ b ≻ a, ∀a ̸ = b ∈ X
We can also define a non-strict linear order ⪰ on a set X as a relation that is transitive, complete, reflexive (a ⪰ a, ∀a ∈ X) and antisymmetric (a

⪰ b ∧ b ⪰ a ⇒ a = b, ∀a, b ∈ X).
For each non-strict linear order ⪰ there exists an associated linear order ≻ obtained by removing all pairs a ⪰ a, ∀a ∈ X. In other words, we have

a ≻ b ⇐⇒ a ⪰ b ∧ a ̸ = b, ∀a, b ∈ X.
L(A) denotes the set of all linear orders over A. A generic element ≻ i ∈ L(A) stands for the preference ranking of the individual i ∈ N . A profile P : N → L(A) associates with each individual i ∈ N a preference P (i) = ≻ i . We will use ≻ i instead of P (i) when the profile is clear from the context. L(A) N denotes the set of all functions from N to L(A), thus all possible profiles given N .

Example 2.1. Given a set of alternatives A = {a, b, c} and a set N = {v 1 , v 2 , v 3 , v 4 } of voters, we represent a profile P as:

v 1 v 2 v 3 v 4 a b c c b c a a c a b b ,
where each column is the preference ranking associated to a certain voter. In this example the voter v 1 prefers the alternative a over b over c, v 2 prefers b over c over a, and both v 3 and v 4 prefer c over a over b.

A Social Choice Rule (SCR) is a mapping f : L(A) N → 2 A \ {∅} that associates to each profile a set of (tied) winners. As we saw in Chapter 1, scholars have realized that the most efficient way to define aggregation functions is through the formulation of desirable properties. These properties are called axioms and they are helpful in dividing rules into classes whose elements satisfy the same set of axioms. Or, in the same way, one can prove that a given class is empty, i.e. that it is impossible to satisfy a set of axioms simultaneously. As we shall see, axioms that independently seem to be reasonable requirements can result, when combined, in undesirable effects that are often difficult to detect without an systematical analysis.

In what follows we will describe the axioms and the voting rules that we will consider through the rest of this dissertation. In particular we will divide the ones based on preference rankings from the ones using judgments as ballots, and we will see which axioms each rule satisfies.

Axioms

As already mentioned, an axiom formalizes an appealing property of a voting rule. A first intuitive desideratum is that the rule should not favor specific voters or candidates. In many real cases, when a committee has to make a decision, in case of a tie a member, usually the chair, has the power to break it at his discretion. Similarly, in many legislatures in case of a tie between approving a law or not, the status quo wins, highlighting an inequality between the alternatives. However, these behaviors are not always desired or accepted. In what follows we present two axioms that promote equality among voters, anonymity, and among candidates, neutrality.

Anonymity. An SCR f is anonymous iff for any i, j ∈ N and P, P

′ ∈ L(A) N such that ≻ ′ k = ≻ k , ∀k ∈ N \ {i, j} and ≻ ′ i = ≻ j , ≻ ′ j = ≻ i , we have that f (P ) = f (P ′ ).
In other words, if the identity of voters is irrelevant.

Neutrality. An SCR f is neutral iff for any P, P ′ ∈ L(A) N such that P ′ is obtained from P by swapping the position of two alternatives in every preference rankings, we can obtain f (P ′ ) from f (P ) via the same swap. In other words, if the identity of alternatives is irrelevant.

Example 2.2. With this in mind we can rewrite Example 2.1 by considering anonymity. In fact, if we are not interested in the identity of the voters, P can be expressed as:

1 1 2 a b c b c a c a b ,
where each column represents the preference ranking associated to a certain number of voters. Here, one voter prefers the alternative a over b over c, one voter prefers b over c over a, and two voters prefer c over a over b. This way of denoting a profile will be used often throughout the dissertation.

We could also consider a weaker form of anonymity were the voters are not necessarily equal but which does not allow for a dictator-a specific voter whose preferred choice is always the outcome of the voting rule.

Nondictatoriality. An SCR f is nondictatorial iff ∀i ∈ N there exists a profile P ∈ L(A) N such that ≻ i (1) ̸ ∈ f (P ); where ≻ i (1) is the first element of the linear order representing i preferences. In other words, if no voter acts as a dictator.

Another fairly obvious property that might come to mind is that if enough voters agree on an alternative then it must be selected as the winner. To better define the concept of enough, given a profile P ∈ L(A) N and an alternative a ∈ A, we consider the number of preference rankings for which a is ranked first:

η(a) = |{≻ i , i ∈ N | ≻ i (1) = a}|.
Majority. An SCR f is majoritarian iff for any P ∈ L(A) N and a ∈ A such that η(a) > n 2 then f (P ) = {a}. In other words, if the majority of voters rank the same alternative first, then that alternative should be the sole winner.

This idea leads us to two more general considerations. First, if all voters prefer an alternative a to another one b then this preference must be translated into the result: b cannot be part of the winners. Second, if a majority of voters prefer an alternative a to any other, then a should be the winner. To better define this last concept, given a profile P ∈ L(A) N An SCR f is a Condorcet procedure if it elects the Condorcet winner whenever it exists.

Note that for an SCR f being majoritarian implies that there is an alternative a ∈ A that is preferred to any other by a majority of the voters: µ(a, b) > n 2 , ∀b ∈ A \ {a}. This also means that µ(a, b) > µ(b, a), ∀b ∈ A \ {a} so that a is the Condorcet winner. The converse is not always true, if an alternative is the Condorcet winner then it is not necessarily the majority choice.

Example 2.3. Consider the following profile P :

1 1 1 a c d b b b c a a d d c , µ(a, b) = 1, µ(a, c) = 2 µ(a, d) = 2 µ(b, a) = 2, µ(b, c) = 2 µ(b, d) = 2 µ(c, a) = 1, µ(c, b) = 1 µ(c, d) = 2 . µ(d, a) = 1, µ(d, b) = 1 µ(d, c) = 1
b is the Condorcet winner but it is not the majority choice.

We conclude that the Condorcet criterion is a stronger axiom and its satisfaction implies that of the majority criterion: if f is a Condorcet procedure then f is also majoritarian.

It is also worth to mention that the Condorcet winner does not always exist and that, with three or more alternatives, majority cycles may occur.

Example 2.4. Consider the following profile P :

1 1 1 a b c b c a c a b , µ(a, b) = 2, µ(b, a) = 1 µ(b, c) = 2, µ(c, b) = 1 . µ(c, a) = 2, µ(a, c) = 1
Thus, a is preferred to b, b is preferred to c, but c is preferred to a, so there is no Condorcet winner. Such cycle of preferences is also known as Condorcet's paradox.

In all properties considered so far we have assumed that voters report their sincere preferences. But what if a voter can achieve better results by casting an insincere ballot rather than expressing her true preferences?

Manipulability. An SCR f is manipulable iff there exist two profiles P, P ′ ∈ L(A) N and a voter j ∈ N such that ≻ ′ i = ≻ i , ∀i ∈ N \ {j} and f (P ′ ) ≻ j f (P ). In other words, if there exists a voter who by changing her preference ranking can change the outcome to something more appealing to her.

Strategy-Proofness. An SCR f is strategyproof iff it is not manipulable.

Voting rules

Having established desirable properties for aggregating preferences, we can now describe some methods designed for this purpose. Probably, one of the most intuitive approaches when a group of people get together and wish to find a common choice, is to elect the alternative supported by the majority of voters. The first thing we note is that this rule, as formulated, would not allow for the existence of multiple winners. Thus, while it might produce acceptable results with only two alternatives and an odd number of voters, in all other cases it would not always yield a winner.

Nevertheless, let us step back from these considerations for a moment and assume that there is always a majority that agrees on the choice of the winner. What would the decision of the majority imply? In his rules for a open society, Popper [1945, vol. 2, ch. 19] writes: "Democracy cannot be the majority, although fully characterized as the rule of the institution of general elections is most important. For a majority might rule in a tyrannical way. (The majority of those who are less than 6 ft. high may decide that the minority of those over 6 ft. shall pay all taxes.)". Also thanks to his example, it is easy to imagine what Popper meant when he said that the majority can rule tyrannically. But one thing that is also very important to point out is that a sort of tyranny could also lie in the election itself, in the sense that the majority choice could be hated by the rest of the population. Imagine a situation where in a group of 100 voters, 51 of them have the following preference ranking a ≻ b ≻ . . . ≻ z and 49 instead z ≻ y ≻ . . . ≻ a. A majority of 51 individuals would elect the candidate a who is detested by the remaining 49.

This makes us realize that rather intuitive methods, which seem fair at a first glance, can actually have unintended implications.To mitigate this problem and analyze the properties of voting rules, we can make use of the axioms just described.

The literature on voting rules is extensive and many have been proposed over the years, here we will present just a few examples of three particular categories: Positional Scoring Rule, that are methods assigning points to positions and electing the candidate with the greatest cumulative score; Condorcet Procedures, which are methods satisfying the Condorcet criterion, i.e. always electing the Condorcet winner whenever it exists; BK Compromises, which is the term we use to refer to the generalization of bargaining rules explored by [START_REF] Brams | [END_REF], where, starting from the top choice of each voters, we fall back until one or more candidates have enough support to be considered winner.

Let us analyze these procedures in more detail.

Positional Scoring Rule (PSR)

The PSR f w is the voting rule defined by the scoring vector w = (w 1 , . . . , w m ) which associate weights w r ∈ R to positions, with w 1 ≥ w 2 ≥ . . . ≥ w m . Let α a r be the number of times that alternative a was ranked in the r-th position, then the score of a is defined by

s(a) = i∈N w ≻ i (x) = m r=1 α a r w r . (2.1)
The winners f w (P ) = {a ∈ A | s(a) ≥ s(b), ∀b ∈ A \ {a}} are the alternatives with highest score, we will write this as f w (P ) = argmax a∈A s(a). Different scoring vector w define different rules, here we describe three of them.

Plurality.

The vector defining plurality rule is w = (1, 0, . . . , 0). This means that the score of each candidate corresponds to the number of times she was ranked first s(a) = η(a). The winners are the candidates who are ranked first by the largest number of voters.

Anti-Plurality.

The vector defining anti-plurality rule is w = (1, . . . , 1, 0). The winners are the candidates who are ranked last by the smallest number of voters.

k-Approval.

Plurality and Anti-Plurality can be seen as particular cases of a more general approval voting where each voter assigns a score of 1 to, respectively, only one candidate and m -1 candidates. For a generic k ∈ 1, m -1 , the vector defining k-approval rule is

w = (1, . . . , 1 k , 0, . . . , 0 m-k
).

Borda.

The vector defining Borda rule is w = (m -1, m -2, . . . , 0). This means that, for each preference ranking, each candidate gets points inversely proportional to her ranking. The winners are the candidates with the highest score. As we mentioned in Chapter 1, the Borda count is also known as Lull's method.

These are only few examples of scoring rules, but more can be defined by changing the vector.

In some instances of real applications:

• the Eurovision Song Contest uses a PSR with scoring vector w = (12, 10, 8, 7, 6, 5, 4, 3, 2, 1, 0, . . . , 0);

• the Formula One racing uses a PSR with scoring vector w = (25,18,15,12,10,[START_REF]candidats au lieu de leur classement permet d'obtenir plus d'informations grâce à une plus grande expressivité[END_REF]6,4, 2, 1, 0, . . . , 0)

Condorcet Procedures

Any method satisfying the Condorcet criterion is a Condorcet procedure. As we saw in the previous section, however, the Condorcet winner does not always exist. In these cases different ways to solve this ambiguity have been used, resulting in different procedures. These rules proposed over the years are many and go beyond the scope of this thesis, here we will describe only two of them but, for more details, [START_REF] Fishburn | Condorcet social choice functions[END_REF] describes and compares nine famous Condorcet procedures.

We would like to warn the reader, that these two specific rules will not be mentioned again in the course of the thesis. The following material could be skipped (until the next set of BK rules) without compromising the understanding of the rest of the manuscript. However, it seems worthwhile to us to give an example of Condorcet procedures and, in particular, two methods which, as we shall see, do not satisfy the same axioms.

Given a profile P ∈ L(A) N and two alternatives a, b ∈ A, recall that µ(a, b) = |{≻ i , i ∈ N | a ≻ i b}| represents the number of preference rankings for which a is preferred to b. We denote with ▷ a simple majority win, and we say that a ▷ b iff µ(a, b) > µ(b, a).

Copeland.

Copeland's method -which was also proposed by Lull as we saw in Chapter 1 -is often considered to be an extension of Condorcet's method. In fact, the idea of this procedure is based on the fact that if a candidate whose pairwise wins are greater than anyone else is deserving of winning, then one whose number of pairwise wins minus pairwise losses is greater than everyone else is even more deserving. Let us formalize this concept, we define with γ(a)

= |{b ∈ A \ {a} | a ▷ b}| -|{b ∈ A \ {a} | b
▷ a}| the number of simple majority wins of a minus the number of simple majority losses of a. The winners under the Copeland rule are the alternatives for which this value is the greatest f C (P ) = argmax a∈A γ(a).

Schwartz.

The idea behind the procedure proposed by [START_REF] Schwartz | Rationality and the myth of the maximum[END_REF] is to identify the sets of alternatives such that every member in the set wins in simple majority all other alternatives outside the set. The union of all these sets represents the Schwartz set. We say that a Schwartz dominates b, a ⊢ b, iff ∃x 1 , . . . ,

x k ∈ A | a ▷ x 1 ∧ x 1 ▷ x 2 ∧ • • • ∧ x k ▷ b and ∄y 1 , . . . , y l ∈ A | b ▷ y 1 ∧ y 1 ▷ y 2 ∧ • • • ∧ y l ▷ a.
In other words, if there exists a path from a to b in ▷ but not vice-versa. The members of the Schwartz set are all candidates who are not Schwartz dominated. The winners are all the candidates in the Schwartz set,

f S (P ) = {a ∈ A | ∄b ∈ A \ {a} s.t. b⊥a}.
Theorem 2.1 [START_REF] Fishburn | Condorcet social choice functions[END_REF]). f S (P ) is not Paretian.

Proof. Consider the following profile P :

1 1 1 a d c b a d c b a d c b ,
Consider, for each pair of alternatives, the number of profiles that prefer one alternative to the other.

µ(a, b) = 3, µ(a, c) = 2 µ(a, d) = 1 µ(b, a) = 0, µ(b, c) = 2 µ(b, d) = 1 µ(c, a) = 1, µ(c, b) = 1 µ(c, d) = 2 . µ(d, a) = 2, µ(d, b) = 2 µ(d, c) = 1
From this we deduce that a Pareto dominates b and, also, that the simple majority relations are

a ▷ b, a ▷ c, b ▷ c, c ▷ d, d ▷ a, d ▷ b.
For an alternative a to be in the Schwartz set, there must not be an alternative b for which there is a path from b to a in ▷ but no path from a to b. If we represent the preferences with a graph in which each node is an alternative and the arcs correspond to the ▷ relations, it is easy to see that from whichever node we start we can always reach any other node. a

b c d a ▷ b ∧ b ▷ c ∧ c ▷ d ∧ d ▷ a a ▷ c ∧ c ▷ d ∧ d ▷ a a ▷ c ∧ c ▷ d ∧ d ▷ a b ▷ c ∧ c ▷ d ∧ d ▷ b b ▷ c ∧ c ▷ d ∧ d ▷ b c ▷ d ∧ d ▷ a ∧ a ▷ c
This means that the Schwartz set is equal to the set of all alternatives, thus that f S (P ) = {a, b, c, d}. But b is a Pareto dominated alternative, thus the Schwartz rule does not satisfy the Pareto criterion.

This example shows us that even "basic" properties like Pareto are worth verifying, because rules that seem reasonable may not satisfy them. And, to be fair, deviating a little, this may lead us to another consideration that will be useful later on: is Pareto really that basic and essential? [START_REF] Sen | The impossibility of a paretian liberal[END_REF][START_REF] Sen | Rationality and Freedom[END_REF] thinks that this is not always the case. In fact, he introduced the concept of Minimal Liberty, according to which there should be at least a pair of alternatives a, b such that if an individual prefers a to b then society prefers a ≻ b. Considering all preference orders to be possible (Unrestricted Domain), he showed that there is no way to aggregate preferences into a single common choice that simultaneously satisfies the Pareto criterion and Minimal Liberty. Sen suggests that one way to escape this paradox is to give up Paretian efficiency: "While the Pareto criterion has been thought to be an expression of individual liberty, it appears that in choices involving more than two alternatives it can have consequences that are, in fact, deeply illiberal." [START_REF] Sen | The impossibility of a paretian liberal[END_REF] In our quest to identify rules that could reflect a true compromise between voters (Chapter 7), we will come across a class of rules that we find reasonable in some contexts but which do not satisfy the Pareto criterion.

BK compromises

In order to describe the next set of rules it is necessary to make a premise. We have decided to group under the umbrella name of Brams and Kilgour (BK) compromises, all those rules which, starting from everyone's ideal alternative, fall back to the voters' second, third and more generally k-th best, until a certain quota of voters q support some of the alternatives considered so far.

This method, in its main idea, has been rediscovered several times over the years. Its proposal can be traced back to de Condorcet [1789[START_REF] De Condorcet | Sur les élections[END_REF], whose procedure, translated by McLean and Hewitt [1994, pp. 249-250], reads: "If one candidate has the absolute majority of first votes, he will be elected. If one candidate has the absolute majority of first votes and second votes together, he will be elected. If several candidates obtain this majority, the one with the most votes will be preferred. If one candidate has the absolute majority of the three votes together, he will be elected, and if several candidates obtain this majority, the one with the most votes will be preferred". Here the quota q of supporters an alternative must have to get elected is ⌊ n 2 ⌋ + 1, i.e. the majority of voters. It is important to note, however, that Condorcet specifies a tie-breaking procedure to apply when several alternatives are supported by at least q voters. The rules belonging to the BK Compromise family do not use a tie-breaking procedure, in such instances they return the set of alternatives respecting the quota.

As [START_REF] Camps | Choosing by means of approval-preferential voting. the revised approval choice[END_REF] point out, the same method was later analyzed by Lhuilier [1793] and adopted in Geneva. Sometime after that, in the early 20th century, this procedure was promoted by the politician James W. Bucklin and adopted first in the municipality of Grand Junction (Colorado, USA) and then in many other cities of the United States [Barber, 2000, p. 167]. In 1986 it was proposed again by [START_REF] Sertel | Lecture notes on microeconomics[END_REF] and [START_REF] Sertel | The majoritarian compromise is majoritarian-optimal and subgameperfect implementable[END_REF] under the name of Majoritarian Compromise. Later, [START_REF] Brams | [END_REF] generalized this concept and introduced a class of SCR called q-approval fallback bargaining, where q is the required quantity of support that can vary from a single voter up to unanimity. Different choices of q lead to different SCRs. Considering n voters, the choice of q = 1 corresponds to the plurality rule and q = n represents a bargaining procedure called Fallback bargaining, which has been further analyzed by [START_REF] Kibris | Bargaining over a finite set of alternatives[END_REF] and [START_REF] Congar | A characterization of the maximin rule in the context of voting[END_REF]. Again, Brams and Kilgour do not use a tie-breaking mechanism, thus the BK rule with q = ⌈ n 2 ⌉ is similar but not equal to Majoritarian Compromise, which, instead, is a subset of the former.

To describe these BK compromises, recall that we are considering a finite set N of n individuals and a finite set A of m alternatives. A profile P : N → L(A) associates with each individual i ∈ N a preference

P (i) = ≻ i . We write r ≻ i (a) = #{b ∈ A | b ≻ i a} + 1 for the rank of a ∈ A at ≻ i ∈ L(A).
Given any 1 ≤ q ≤ n and 1 ≤ d ≤ m, consider the (q, d)-compromise set, i.e. the set of alternatives that are ranked among the top d by at least q voters CS q d (P ) = {a ∈ A | #{r ≻ i (a) ≤ d, ∀i ∈ N } ≥ q}. The q-approval fallback bargaining depth, d * q , is the smallest value that makes this set nonempty: d * q = min{d | CS q d (P ) ̸ = ∅}. The SCR q-approval fallback bargaining is defined as the set of all alternatives that are ranked d * q for at least q bargainers: f q BK = CS q d (P ) where d = d * q . Consider the maximum support at depth d as the biggest value that makes the compromise set nonempty: q * d = max{q | CS q d (P ) ̸ = ∅}. We can define a tie breaking version of the BK rule, in a Condorcet fashion, by adding an extra step. If multiple alternatives are ranked d * q for at least q bargainers, the tie breaking q-approval fallback bargaining returns the ones with the greatest support:

f q * d tbBK = CS q * d d (P ) where d = d * q .
Note that when CS is a singleton, when q = n and when all the alternatives in CS are supported by the same amount of voters then f q BK = f q tbBK . Example 2.5 shows how different quotas lead to different results.

Example 2.5 ( [START_REF] Brams | [END_REF]). Consider the following profile P :

1 1 1 1 a a a d b c d b c b b c d d c a
, when q = 1 then d * 1 = 1 and f 1 BK = {a, d} and f 1 tbBK = {a}; when q = 2 then d * 2 = 1 and f 2 BK = {a} and f 2 tbBK = {a}; when q = 3 then d * 3 = 1 and f 3 BK = {a} and f 3 tbBK = {a}; when q = 4 then d * 4 = 3 and f 4 BK = {b} and f 4 tbBK = {b}.

When q = n the BK rule is referred to as Fallback Bargaining (FB):

f n BK = f FB . When q = ⌈ n 2 ⌉ the revised BK rule is denoted as Majoritarian Compromise (MC): f ⌈ n 2 ⌉ tbBK = f MC .
Example 2.6 shows a profile where the two sets of outcomes f MC and f

⌈ n 2 ⌉ BK do not coincide.
Example 2.6 [START_REF] Sertel | The majoritarian compromise is majoritarian-optimal and subgameperfect implementable[END_REF] and [START_REF] Brams | [END_REF]). Consider the following profile P : To conclude this section we show in Table 2.1 an overview of which of the axioms described is satisfied by the rules discussed so far. Note that we say that an axiom is satisfied by the class BK Compromises, which we informally use to design the class of q-approval fallback bargaining, if it is satisfied by every element in the class, and the converse if there is at least one element in the class for which it is not satisfied.

1 1 1 a c b
Anon. Neut. Nondict. Pareto Condorcet Majority Manipul. SP Plurality ✓ ✓ ✓ ✓ × ✓ ✓ × Anti-Plurality ✓ ✓ ✓ × × × ✓ × Borda ✓ ✓ ✓ ✓ × × ✓ × Copeland ✓ ✓ ✓ ✓ ✓ ✓ ✓ × Schwartz ✓ ✓ ✓ × ✓ ✓ ✓ × BK Compromises ✓ ✓ ✓ ✓ × ✓ ✓ ×
Table 2.1: Axioms satisfied by the voting rules described.

Voting with rated ballots

In the classical Arrovian framework for social choice a set of voters is assumed to give a complete preferences order over a set of alternatives [START_REF] Arrow | A difficulty in the concept of social welfare[END_REF]. When we think about it, this is not so obvious to achieve. For example, there may be too many alternatives and the cost for the voters to provide a complete order is simply too high. In this situation, one could opt for an approval system, in which voters approve only the desired alternatives [START_REF] Brams | Approval Voting[END_REF]]. Yet, this does not resolve other criticisms raised against the system of ranked ballots: that of preference intensity. One may argue that preference rankings provide already some level of intensity, but they do not capture the full story. Different voters may have the same order but prefer one alternative to another with different intensity levels. Suppose that a slight majority of voters slightly prefer alternative a to alternative b, these would appear in the preference rankings as a ≻ b. Now consider that the remaining slight minority despises a, and strongly prefers b to a. There is no way for any rule in the framework of ranked preferences to distinguish the difference in intensity between a ≻ b in the first group and b ≻ a in the second. How to decide what is the most desirable alternative for society? A possibility is to evaluate candidates according to a common language shared by society. Note that from the evaluation of candidates we can deduce a ranking, but the converse is not true. Thus, an evaluation is more informative than a ranking. This describes the framework introduced by [START_REF] Smith | Range voting[END_REF], and later analyzed by [START_REF] Pivato | Formal utilitarianism and range voting[END_REF], [START_REF] Gaertner | A general scoring rule[END_REF], [START_REF] Zahid | The borda majority count[END_REF], when proposing his Range Voting rule. Here the common language consists of a range of numerical scores, for example from 0 to 100, and the rule works as follows: each voter assigns a score to all or some alternatives, the one with the highest average score is elected. If more than one alternative has the same highest score then the tie is broken randomly.

But a whole bunch of new questions arise. What is the right size for this scale? If it is too large it may create manipulation problems because voters may exaggerate their preferences; if it is not large enough it reduces expressiveness. Is it better to use a numerical scale or a more immediate language? Are there really benefits to using ratings instead of rankings? Luckily for us, there is a vast literature of economists and psychologists who have addressed these questions, even sometimes arriving at very different answers. Unfortunately, to discuss this would go beyond the scope of this thesis, but for a (non-exhaustive) list of work on the subject one can read [START_REF] Cox | The optimal number of response alternatives for a scale: A review[END_REF], [START_REF] Sparling | Rating: How difficult is it?[END_REF], [START_REF] Churchill | Research design effects on the reliability of rating scales: A meta-analysis[END_REF], [START_REF] Preston | Optimal number of response categories in rating scales: reliability, validity, discriminating power, and respondent preferences[END_REF], [START_REF] Maio | Rankings, ratings, and the measurement of values: Evidence for the superior validity of ratings[END_REF].

In this manuscript we are going to focus on a specific scale of seven expressions: Excellent, Very Good, Good, Passable, Inadequate, Mediocre, Bad. This scale was used by [START_REF] Balinski | A theory of measuring, electing, and ranking[END_REF] when proposing their Majority Judgment (MJ) rule. Each voter judges all the candidates and the one with the highest median is elected. We describe this rule in more detail in the next section. For now, we would like to conclude our introduction with a small anecdote. During a 2012 interview Arrow was asked how he thought voting systems should be evaluated in the future, he replied: "I'm a little inclined to think that score systems where you categorize in maybe three or four classes probably (in spite of what I said about manipulation) is probably the best" [START_REF] Hamlin | Podcast 2012-10-06: Interview with nobel laureate dr. kenneth arrow[END_REF].

Majority judgment

MJ is a voting method proposed by [START_REF] Balinski | Réponse à des critiques du jugement majoritaire[END_REF]Laraki [2007, 2011] to elect one out of m candidates based on the judgments of n voters. The latter express their preferences by assigning to each candidate one of the following adjectives: Excellent, Very good, Good, Average, Mediocre, Inadequate, To be rejected. Those adjectives represent a common language whose semantic is assumed to be a shared knowledge among the voters carrying thus an absolute meaning. For each candidate the median of the grades she received is computed, this is called majority-grade. The candidate with the highest majority-grade is elected. Ties are broken by considering the majority-grade of first order: one vote associated with the majority-grade of each tied candidates is removed and their medians are recomputed. The candidate with the highest new median is elected. If there is still a tie the process is repeated until a unique winner is found.

In order to formalize this description, consider a finite set N of voters (or judges) with #N = n and a finite set A of alternatives (or competitors) with #A = m. A common language △ = {δ 1 , δ 2 , . . . , δ 7 } is a set of strictly ordered grades. The notation δ 1 ≥ δ 2 indicates that δ 1 is a better or equivalent grade than δ 2 . Here δ 1 corresponds to Excellent, δ 2 to Very good etc. A profile P : A × N → △ is a m by n matrix of grades.

The operator ρ : △ N → △ |N | defines an ordering function that given a vector of grades P i returns the vector ordered by decreasing grades.

The majority-grade, f maj , is the function that associates to a vector of grades v ∈ △ N its median grade value:

f maj (v) = ρ(v) ⌊ |v| 2 ⌋+1
. Note that in case |v| is even two medians could be used, but in [START_REF] Balinski | Majority Judgment: Measuring, Ranking, and Electing[END_REF] definition the lower grade is picked.

The Majority Judgment function F maj : △ A×N → A is a function that selects the alternative with the highest median grade as winner. We can define it as F maj (P ) = argmax i∈A f maj (P i ) assuming it is a singleton. To avoid adding further complexity to the notation, we describe only informally what happens when this is not the case, in other words when two or more alternatives are associated with the same highest median grade h = max i∈A f maj (P i ). In this case, ties are broken by removing one h grade from the vectors of grades of each tied alternative, recomputing the new median grade and repeating the process until one unique winner is found or there are no more grades to remove. When n is odd, this is equivalent to take the next element after the median, i.e. the one at index (⌊ n 2 ⌋ + 1) + 1, if there is still a tie we then look at the previous element before the median, i.e. the one at index (⌊ n 2 ⌋ + 1) -1, and keep alternating until the tie is broken or there are no more elements in the vector. When n is even the process is similar but we alternate starting from the element before the median, ⌊ n 2 ⌋, then the one after, ⌊ n 2 ⌋ + 2, and so on. If after applying the mechanism there are still ties we break them using an arbitrary ordering defined on all alternatives, e.g. lexicographical order.

Criticisms of this rule include that the median does not respect the majority principle, meaning that if a majority of voters prefer an alternative a to an alternative b, the latter could still win with an higher median. Consider the following example.

Example 2.7 ( [START_REF] Laslier | The strange "majority judgment[END_REF]). Consider the following profile formed by three voters i 1 , i 2 , i 3 and two candidates a, b. Suppose the voters assign to candidates a grade between 0 and 20. Is it worth mentioning that the same example is also studied by Balinski and Laraki [2011, p. 281], where the authors reproduce the example with MJ grades.

Example 2.8 ( [START_REF] Balinski | Majority Judgment: Measuring, Ranking, and Electing[END_REF]). For the effect to be reproduced in the MJ setting the example should be translated as:

50 50 1 a Excellent Mediocre Mediocre b
Good To be rejected Average .

However, the authors stress the fact that is very unlikely that the last voter would associate a different grade to 9 and 10. In a large electorate the distinction would be too fine to make a significant difference between 20 and 19 or 10 and 9, so they affirm that the example would more realistically translate to:

50 50 1 a Excellent Mediocre Mediocre b Average To be rejected Mediocre .
And a would be elected.

Another criticism regards manipulability. MJ is manipulable to the extent that voters can exaggerate by excess the judgments of their top choices and by defect those of their worst choices. It must be mentioned that [START_REF] Bassett | Robust voting[END_REF] proved that the high breakdown property of the median-which is the sensitivity to outlying observations -makes difficult for a minority to manipulate the ranking. However, [START_REF] Gehrlein | On some limitations of the median voting rule[END_REF] studied that the probability of being subject to manipulation is just slightly smaller than other methods like Borda and Copeland.

CHAPTER 3 HISTORY AND LITERATURE REVIEW

In this chapter we will analyze in detail the topics covered in this manuscript. We will describe the different definitions and approaches to the issues considered that have been proposed in the literature. In the first part of this chapter, Section 3.1, we will focus on the meaning of compromise. All voting rules can be considered a compromise between voters preferences, but some more than others. We will consider several notions of compromise and analyze different aggregation methods that satisfy them. In the second part, Section 3.2, we will focus on a specific rule that has been considered, by some authors, a compromising rule: Majority Judgment. We will describe its introduction, its uses in real life voting procedures and also its criticisms. In the final part, Section 3.3, highlighting how some assumptions made so far, notably the complete knowledge of preferences, are too stringent, we will analyze the literature on preference elicitation. We will consider different fields and different approaches within the same field. In all sections we will present the definitions introduced in our contributions and position them in the existing literature. We will show how our approach differ from existing works and lay the foundation for the content of the next chapters.

Voting as a compromise

After having described voting rules as procedures designed to aggregate a set of preferences into a common choice, we could say that each one of these mechanism reflects some sort of compromise. In fact, reaching a collective choice by unanimous accord is a fairly rare situation, especially in elections with a large number of voters. In all other cases, someone has to give up their top preference in favor of a second, or third etc., choice. Yet, can we call this a compromise? What do we mean when we talk about this notion?

How do people compromise? One way of approaching the analysis of a concept is to start from the etymology of the word itself. The word compromise comes from the Latin compromissus, past participle of compromittere: com together and promittere to promise. The idea of compromise can indeed be found in texts dating back to Roman times, where two disputing parties who wished to submit their contention to arbitration, would appoint a third party (an arbitrator) and make the mutual promise to abide by the latter's unquestionable judgment. If either party broke this promise, it would have had to pay a penalty. In a fragment of a letter written by Proculus, which is reported by Zimmermann [1996, p.529], it is clear that the two disputants agreed to give the arbitrator unlimited powers in his decision. No appeal was possible against the final award, which was binding no matter how unjust and unequal it was. This idea of compromise as a mere arbitration process seems very different from the notion we have of it today. Let us consider the definitions of the two verbs in a modern dictionary: to arbitrate "to settle a dispute between two people or groups after hearing the arguments and opinions of both" [Merriam-Webster, 2022a]; to compromise "to come to agreement by mutual concession" [Merriam-Webster, 2022b]. The mutual concession is the element that immediately makes us think of a compromise and it is precisely the missing factor in the description of the Roman compromise and modern arbitration. Quoting [START_REF] Braybrooke | The possibilities of compromise[END_REF] "It is simply a bad joke to speak of someone's being a party to a compromise when she has got nothing out of it.".

However, Roman society is not the first one to use mechanisms of compromise; we find references to use of arbitration and selection of arbitrators in Aristotle's Constitution of the . Moreover, Aristotle is the first to associate the concept of fairness with that of arbitration: "Fairness, for example, seems to be just; but fairness is justice that goes beyond the written law."Aristotle trd. Kennedy [2006][1.13.13] "And it is fair to want to go into arbitration rather than to court; for the arbitrator sees what is fair, but the jury looks to the law, and for this reason arbitrators have been invented, that fairness may prevail."Aristotle trd. Kennedy [2006][1.13.19] Throughout history, however, compromise has been intended in its Roman meaning: the resolution of a dispute by a third party whose judgment individuals agree to abide by. The use of arbitration as a mean of compromise continued until the end of the Middle Ages, only to be overshadowed by the advent of absolute monarchies, like the one of Louis XIV, that tended to centralize all powers in a single strong figure [START_REF] Zappalá | Memoria storica dell'arbitrato. Meritum[END_REF]. However, this did not last long. In France, for example, the first constitution approved after the revolution, in 1791, defended the right of arbitration: "Chapitre V. Article 5. -Le droit des citoyens, de terminer définitivement leurs contestations par la voie de l'arbitrage, ne peut recevoir aucune atteinte par les actes du Pouvoir législatif." [Constitution de 1791[Constitution de , 1791] ] It would seem at this point that we are straying a little from the topics treated in this thesis. However, this excursus on how the notion of compromise has been understood for centuries can give us insights on how compromise has been approached in the history of social choice theory. In fact, as Examples 3.2 and 3.3 in Section 2.1.2 show, the best-known voting rules grouped under the name of compromise rules start with the intention of seeking a compromise among voters, however they do not ensure that the outcome of the procedure represents a mutual concession.

Consider an example used by [START_REF] Luban | Bargaining and compromise: Recent work on negotiation and informal justice[END_REF]. Rich and Poor are offered 1000 dollars which they can obtain provided they reach a compromise on how to divide this sum. Rich who knows to have leverage over Poor offers him 100 dollars threatening to walk from the deal if he does not accept. Poor, who is in desperate need of money, accepts. Luban points out that this is considered a compromise because 1) it produces an agreement 2) the criterion of "equal satisfaction" is met if we imagine that 100 dollars give Poor the same level of satisfaction that 900 dollars give Rich. Most of us, however, would consider this outcome as a ridiculous extortion rather than a compromise. What is then the best compromise possible between Rich and Poor? There is no clear answer. If we were to value equity as a fundamental concept of wealth redistribution, then an equitable solution would be for Rich to get 100 dollars and Poor 900 dollars. However, if equality is an important social value, we would intuitively think that the only acceptable result is a 500/500 split. That is, the result where, in the interpretation of compromise as "mutual concession", both parties concede equally. This consideration is the basis for our version of compromise rules presented in Chapter 7.

On equality, fairness and the principle of equal losses. It is important to point out, however, that the concepts of equality and fairness have very specific meanings depending on the considered literature. In this manuscript we consider equality with respect to losses from one's ideal point. We denote a compromise as a situation in which all parties are not only willing to concede, but that at the end of the process they all give up as equally as possible. One of the first author to refer to the equal-loss principle was Mill [1849, p. 396] who, when discussing fairness of taxation, wrote: "As a government ought to make no distinction of persons or classes in the strength of their claims on it, whatever sacrifices it requires from them should be made to bear as nearly as possible with the same pressure upon all, which, it must be observed, is the mode by which least sacrifice is occasioned on the whole. [...] Equality of taxation, therefore, as a maxim of politics, means equality of sacrifice." Since then, the equal-loss principle has received a lot of attention, especially in the problems of taxation [START_REF] Edgeworth | The pure theory of taxation[END_REF][START_REF] Young | Progressive taxation and the equal sacrifice principle[END_REF] and bankruptcy [START_REF] Herrero | The three musketeers: four classical solutions to bankruptcy problems[END_REF]Villar, 2001, Aumann and[START_REF] Aumann | Game theoretic analysis of a bankruptcy problem from the talmud[END_REF], and there has been much discussion about the interpretation of sacrifice, which is ultimately a very subjective concept. [START_REF] Chun | The equal-loss principle for bargaining problems[END_REF] was the first to apply the equal loss principle to bargaining theory. This new bargaining solution, called the equal-loss solution, aims at equalizing across agents the losses from their ideal point.

Following [START_REF] Nash | The bargaining problem[END_REF] description, a bargaining problem is a pair (S, d) where S is the set of feasible agreements and d is the disagreement point or status quo, i.e. what each agent gets in case an agreement is not reached. A solution, defined on a class of problems, is a function that maps each problem (S, d) to a point in S representing the agreement reached. Nash proposed to analyze solutions based on the properties, axioms, they satisfy. His solution consists of each agent getting at least what they would get if they disagreed, plus a share of the benefit the group would get if they cooperated. The outcome of this procedure satisfies certain desirable properties including Pareto optimality. It is important to mention that the Nash model is based on a two individuals bargain, but an extension to n individuals can be formulated. Nash's equilibrium, however, has been criticized for several reasons. Sen [2017, pp. 177-180] points out that his solution relies too much on the bargaining power of individuals. Even assuming that the outcome of a bargaining procedure is better than what each agent would have gotten in case of disagreement, it does not make such outcome fair or desirable. To support this thesis, Sen makes an example where some unemployed workers may accept extremely low wages and unfair employments treatments just because in the absence of agreement they may starve. He argues that although this outcome is a Nash equilibrium, the workers were exploited due to their poor bargaining power. Other solutions have been proposed, for example [START_REF] Kalai | Other solutions to nash's bargaining problem[END_REF] focused on equalizing the gains of each player relative to their maximum possible gain, and [START_REF] Kalai | Proportional solutions to bargaining situations: interpersonal utility comparisons[END_REF] introduced the egalitarian bargaining solution which equalizes the gains of the agents from the disagreement points. The latter solution is similar in its idea to the concept of compromise advanced by [START_REF] Yu | A class of solutions for group decision problems[END_REF] which, instead, equalizes the losses of the agents from the ideal point. Both of those approaches are in accordance with Rawls' idea of fairness [Rawls, 1958[Rawls, , 1967]], whose approach to inequalities is to increase the welfare level of the worst-off individual as much as possible. In other words, a maximin procedure.

Equal-loss vs Pareto. To return to the equal-loss solution, [START_REF] Chun | The equal-loss principle for bargaining problems[END_REF] himself mentions the analogies with Kalay's solution and he points out that it is a variant of Yu's solution, but he offers a characterization of it. Given a problem (S, d), the ideal point, a(S, d), corresponds to the maximal utility level each agent could obtain provided that all agents obtain at least what they would get in case of disagreement. That is, for each agent i, a i (S, d) = max{x i |x ∈ S, x ≥ d}. The equal-loss solution is defined as the maximal point x ∈ S with a i (S, d)-x i = a j (S, d)-x j for all agents i, j. As we already mention, the idea is to equalize across agents the losses from the ideal point. Although this sounds very appealing, one of the main criticisms of Chun's solution is that it does not satisfy the Pareto criterion.

Example 3.1 (Adapted from Sen [2017] pp.194-195). Consider two individuals i, j and three states a, b and c with the following welfare levels:

i j a 20 1 b 10 1 c 0 0
, where c is the disagreement point. Despite the state a being Pareto optimal, Chun's procedure would consider the states a and b indifferent. In fact, the worst off individual j is not better off under a than under b (nor the converse).

Sen uses this example to criticize the failure of maximin rules to satisfy the Pareto criterion. We added the state c of disagreement in order for it to apply in the context studied by Chun.

To "solve this problem", a few years later, [START_REF] Chun | The lexicographic equal-loss solution[END_REF] defined a lexicographic version of the equal-loss solution. First, a lexicographic order is defined on the domain of the feasible outcomes, then the equal loss solution is applied: the maximal outcome in which the individuals suffer equal losses from the ideal point is chosen. If this outcome is not Pareto optimal then the next one in lexicographic order is taken until a Pareto optimal outcome is found. Other characterizations of lexicographic maximin solutions have been proposed by [START_REF] Sen | Collective Choice and Social Welfare: Expanded Edition[END_REF] and [START_REF] Chang | A characterization of the leximin solution of the bargaining problem[END_REF].

We have put "solve this problem" in quotes because we do not believe the failure to satisfy the Pareto criterion to be a problem. Consider again Example 3.1, agent j is indifferent to the two states a and b as she would get the same utility in both cases, but agent i clearly prefers a to b. The state a is therefore the Pareto optimal alternative. Nevertheless, let us imagine that a and b represent different distributions of money within a society. If we wanted to pursue an ideal of social justice and reduce inequalities immediately the alternative b seems the most appealing. Sen also makes a criticism of the Pareto criterion [Sen, 2017, Chapter 6]. While he acknowledges that it is not always satisfied in literature, he notes that the Pareto criterion is always treated as a missed opportunity. Sen, however, observes that it is not a criterion that is so obviously desirable. In fact, he shows that even a weak Pareto condition conflicts with a weak condition of individual freedom [Sen, 2017, Theorem 6*3]. Example 3.1 can represent a variation of an illustration given by Sen himself to propose the rejection of the Pareto principle. Imagine that agents i and j have to decide who reads a given somewhat scandalous book. Agent i is what is considered a prude, she would not want to read that book, but she would rather be the one to read it than have the impressionable agent j read it. For agent j it is indifferent because she would like to read it, but she would be just as happy with agent i reading it. Consider a to be the state in which the book is read by i, b to be the state in which it is read by j and c to be the state in which none reads the book. We can use the utilities of the Example 3.1 to represent this situation. Again, a is the Pareto optimal alternative but only because i has the presumption of wanting to decide for others. Sen argues that it is not only important to know the preferences of individuals but also why individuals have that preference: "Preferences based on excessive nosiness about what is good for others, should be, it could be argued, ignored." [Sen, 2017, Chapter 6.5] In Chapter 7 we will introduce two different versions of our vision of compromise, in particular one that prioritizes equality at the expense of Pareto efficiency. Moreover, we consider the concept of equal-loss as the basis of any successful compromise in all situations where egalitarianism, in the sense of conceding equally, is a major concern. This is a novelty in the literature of social choice rules, which so far have only imposed willingness to compromise without actually ensuring that all parties concede something. The philosopher [START_REF] Day | [END_REF] attempts an explanation for this phenomenon, thinking that it stems from the negation of the adjective "uncompromising": "An uncompromising person is one who is not disposed to make any concessions, so (it is erroneously inferred) a compromising person is one who is pliant and disposed to make concessions-regardless of whether he receives any concession in return. However this may be, one must insist, as it is generally agreed, that compromise necessarily involves mutual concessions.". This might explain why all voting rules that try to compromise actually settle for the will of the agents to compromise.

Compromising rules. [START_REF] Merlin | Compromise rules revisited[END_REF] discuss the most famous of these procedures proposing to gather them in the same class of compromise rules. In Section 2.1.2 we already defined the Majoritarian Compromise, introduced by [START_REF] Sertel | Lecture notes on microeconomics[END_REF] and further analyzed by [START_REF] Sertel | The majoritarian compromise is majoritarian-optimal and subgameperfect implementable[END_REF]. Based on a revision of the Condorcet-Bucklin rule, this procedure starts from everyone's ideal choice to find an alternative supported by the majority of voters. If no such alternative exists, then it falls back to the voters' second, third and more generally k-th best choice, until at least one of the alternatives considered appears among the first k best for a majority. If instead of considering an agreement for the majority of voters we wish to select as winners the alternatives supported by the unanimity of voters, then the procedure corresponds to the Fallback Bargaining rule. More generally, if we consider the support of a certain quota q of voters we refer to the q-approval fallback bargaining rule [START_REF] Brams | [END_REF].

All these SCRs impose to voters a willingness to compromise, but we argue that they do not effectively ensure an outcome where the agents have, indeed, compromised. Example 3.2 motivates our view. .

When q ∈ 1, n 2 + 1 , all BK compromises pick a and c while the tie breaking BK compromise selects a. These outcomes do not appear as a compromise as almost half of the voters obtain their best choice while the remaining half have to be contented with their worst one. Observe that b receives unanimous support when each voter falls back one step from her ideal point.

Although we will not study it in this context, it is interesting to mention that [START_REF] Merlin | Compromise rules revisited[END_REF] also include the Majority Judgment in the class of compromise rules. Introduced by [START_REF] Balinski | Réponse à des critiques du jugement majoritaire[END_REF]Laraki [2007, 2011], we defined this procedure in Section 2.2 and we discuss it in more detail in Section 3.2. In particular, the authors consider MJ to be a compromise by transposing the possible grades into ranks of the preference orders, with the condition that each voters use the same grade only once. In this context the alternative with the median rank is the compromise. If more of such alternatives exist, the tie breaking mechanism proposed by [START_REF] Balinski | Majority Judgment: Measuring, Ranking, and Electing[END_REF] is used: one of the median rank is removed to each candidate winner until one of those will get the new highest median.

Other mechanisms studied in different contexts may still fit into the classification of compromise rules. For example, if we consider only two voters, de Clippel et al. [2014] analyze two methods for the selection of arbitrators: the Veto-Rank mechanism (VR)-which is the most common procedure for assigning arbitrators [de Clippel et al., 2014, Online Appendix]-and Shortlisting (SL). Consider a list of m (odd) alternatives (that are candidates to be arbitrators), and two voters (that are the two parties that must agree on an arbitrator). In the VR procedure, both voters simultaneously veto their worst m-1 2 alternatives. The selected alternatives are the ones with the highest Borda score among the non-vetoed alternatives. In the SL procedure, one of the two parties starts by vetoing her worst m-1 2 alternatives, and then the second party chooses her best alternative out of the remaining ones. As the outcome of the procedure depends on the party that starts, symmetry among players is ensured by defining the solution as the union of the two outcomes where one and the other party starts. Another class of two voters rules based on the veto power is the one denoted as Pareto-and-Veto rules (PV) by [START_REF] Laslier | A solution to the two-person implementation problem[END_REF]. The same class was also studied by [START_REF] Moulin | The strategy of social choice[END_REF], who refers to it with the name of veto-core, and by [START_REF] Abreu | Virtual implementation in nash equilibrium[END_REF]. This procedure distribute a veto power of v 1 and v 2 alternatives to voters 1 and 2, respectively, with v 1 + v 2 = m -1. Both voters, i = 1, 2, simultaneously veto their worst v i alternatives. The selected alternatives are all the non-vetoed and Pareto optimal ones. Similar to the case n ≥ 3, Example 3.3 motivates our argument in the case of two voters.

Example 3.3. Consider the following preference profile with n = 2:

i 1 i 2 a y 1 x 1 y 2 x 2 b x 3 a b x 1 y 1 x 2 y 2 x 3 .
All the rules aforementioned, except for PV when v 1 < v 2 , selects the alternative a as winner: FB: a is the first alternative to reach unanimous consent; VR: both voters veto their 7-1 2 = 3 worst alternatives so i 1 vetoes {b, y 1 , y 2 } and i 2 vetoes {x 1 , x 2 , x 3 }, the only alternative left is a; SL: when i 1 starts she vetoes her 7-1 2 = 3 worst alternatives thus {b, y 1 , y 2 }, then i 2 picks her best alternative among the remaining ones thus a. When i 1 starts she vetoes {x 1 , x 2 , x 3 } and i 2 picks a. The outcome of the SL procedure is then a;

PV: when v 1 ≥ v 2 : -v 1 = 5, v 2 = 1, i 1 vetoes {x 2 , x 3 , b, y 1 , y 2 } and i 2 vetoes {x 3 } PV selects a; -v 1 = 4, v 2 = 2, i 1 vetoes {x 3 , b, y 1 , y 2 } and i 2 vetoes {x 3 } PV selects a; -v 1 = 3, v 2 = 3, i 1 vetoes {b, y 1 , y 2 } and i 2 vetoes {x 2 , x 3 } PV selects a.
It is worth mentioning that PV does not select a as the winner in this profile when the veto powers are v1 < v2. However, this profile is extended as a desirable property of our notion of compromise that we will describe in more detail in Chapter 7. Generalizing this example we will show that PV, whatever the distribution of veto power is, fails to select what would be for us the compromise outcome: b.

Median compromise: the Majority Judgment rule

As mentioned in Section 3.1, an example of compromise can be represented by Majority Judgment, a voting system where voters assign grades to candidates using an ordinal scale. The evaluation of candidates instead of their ranking yields more information as a result of a higher expressiveness. In MJ each voter evaluates, or judges, each candidate and the winner is the candidate with the highest median of the grades received. This method was introduced by Balinski and Laraki [2007] in the most recent period of social choice history. Yet, it has attracted increasing attention of french associations and political parties which have started to use MJ for internal decisions or local elections.

An overview of the use of the median as aggregator. The idea of using the median in voting is not new, one of the first use can be traced back to Sir Francis Galton's middlemost method [Galton, 1907a,b]. He considered a situation where a group of people has to assess a damage. Galton argued that the aggregation metric that poses the least problems in this context is the median because it is not affected by over-or under-exaggerations. In is words "According to the democratic principle of one vote one value, the middlemost estimate expresses the vox populi, every other estimate being condemned as too low or too high by a majority of the voters". In other words, the median for Galton represents the most accurate estimate of people's voice. He also precised that in the occurrence of even votes two medians are possible, in this case the average of those is taken.

Numerous observers described the median grade as the highest level at which a candidate obtains the support of the majority of the voters. In other words, starting for the highest grade d we check if the majority of the voters assigned at least d to some alternative a. If this is not the case, we descend in the grading scale until such level d * is found where a candidate a * satisfies half population. The grade d * is then the median of a * grades, and, since it is the first level we stopped at, it corresponds to the best possible median. As we know from Section 2.1.2, this method was rediscovered several times and proposed under the name of Bucklin's rule [START_REF] Hoag | Proportional representation[END_REF], Majoritarian Compromise [START_REF] Sertel | Lecture notes on microeconomics[END_REF][START_REF] Sertel | The majoritarian compromise is majoritarian-optimal and subgameperfect implementable[END_REF]] and qapproval fallback bargaining [START_REF] Brams | [END_REF]. Moreover, note that when the number of grades is equal to two (approve, disapprove) then this method is reduced to Approval Voting.

More recently [START_REF] Bassett | Robust voting[END_REF] proposed the use of the median as voting rule for elections advocating for its robustness. In fact, they argue that the high breakdown property of the median minimizes the risk of outcome manipulation by a minority of voters. The authors also insist on the fact that the median is the only method with a high breakdown that also satisfies the monotonicity criteria [START_REF] Bassett | Rating skating[END_REF]. However, [START_REF] Gehrlein | On some limitations of the median voting rule[END_REF], considering only three candidates elections, proved that plurality rule has only a slightly greater probability of manipulability than the median voting rule proposed by [START_REF] Bassett | Robust voting[END_REF] while having a significant greater probability of producing a decisive result. They also study Borda rule and Copeland rule finding similar results: Borda has a higher probability of manipulation but also of decisiveness, Copeland has even lower probability of manipulation and higher probability of decisiveness.

Other studies on the use of the median have been conducted. In particular, [START_REF] Bibliography | The median procedure in cluster analysis and social choice theory[END_REF] survey mathematical problems and properties related to the notion of median in the context of cluster analysis and social choice theory. [START_REF] Nehring | The median rule in judgement aggregation[END_REF] analyze the median rule in judgment aggregation and they define a weighted median rule that is equivalent to MJ except for the treatment of ties.

Real-life use cases of the MJ procedure. In France, MJ has being adopted by a progressively larger number of associations and political parties including: Le Parti Pirate, Génération(s), LaPrimaire.org, France Insoumise and La République en Marche. "Mieux Voter" [MieuxVoter, 2022a] is a french association that promotes the use of MJ as voting method whenever a collective choice has to be selected: public administration, associations, companies. On their website it is possible to find all the citizens lists -party lists that are not affiliated to any national political party -that used MJ to rank their candidates during the local elections of 2020. In two cases, Bordeaux et Annecy, the candidate selected using MJ was then elected as a mayor. LaPrimaire.org [LaPrimaire.org, 2016] is a french political initiative whose goal is to select an independent candidate for the french presidential election using MJ as voting rule. All french citizens over 18 with rights to vote can participate as candidates or voters. The association Democratech implemented the platform for the first time in 2016 in view of the 2017 presidential elections. The number of voters who participated in the election was 10676 during the first round and 32685 during the second round. Any eligible citizen can submit her nomination to the platform and those who gets at least 500 supports are the candidates of the election. The vote is conducted in two rounds. In the first round each voter is asked to express her judgment, using MJ, on five random candidates. At the end of this phase the five candidates with the highest medians are considered the finalists who qualify for the second round. In the second round each voter is asked to express her judgment, using MJ, on all the five finalists. The candidate with the best median at the end of this phase is selected as representative for the presidential election. However, the participation of this candidate to the actual presidential election in France is not granted. In fact, by the french law a candidate must collect at least 500 signatures of elected officials in order to participate to the presidential election. The candidate selected by the voters of LaPrimaire.org in 2016 collected only 135 signatures and did not participate in the 2017 presidential elections.

Criticism and concerns. Despite his public popularity, MJ has received several criticisms from part of the scientific community. In particular, Felsenthal and [START_REF] Machover | The majority judgment voting procedure: A critical evaluation1[END_REF], [START_REF] Zahid | Majority judgment theory and paradoxical results[END_REF] and [START_REF] Laslier | The strange "majority judgment[END_REF] have shown that this procedure can lead to undesirable and counterintuitive results. The authors of MJ highlight the various strengths of their model insisting on:

• the maximization of voters expressiveness -as we saw in Section 2.2;

• the satisfaction of anonymity, neutrality, unanimity, monotonicity and independence from irrelevant alternatives -the axiom for which if the winner of an election is a, and a new candidate b is added, then the winner will be either a or b;

• the immunity to candidate cloning -the axiom for which if a new candidate b similar to a candidate already existing a is added, then the changes of a to win do not change;

• the fact that truth is a dominant strategy, i.e. a single voter has no incentives to lie.

However, Felsenthal and [START_REF] Machover | The majority judgment voting procedure: A critical evaluation1[END_REF], [START_REF] Laslier | The strange "majority judgment[END_REF] show that the monotonicity axiom holds only for a fixed population. This leads to the no show paradox [START_REF] Fishburn | Paradoxes of preferential voting[END_REF]]: a voter can obtain a more desirable outcome if she does not participate in the election than the one she obtains by participating and voting sincerely. Felsenthal and [START_REF] Machover | The majority judgment voting procedure: A critical evaluation1[END_REF], [START_REF] Zahid | Majority judgment theory and paradoxical results[END_REF] prove that the two mechanisms to resolve ties proposed by [START_REF] Balinski | Majority Judgment: Measuring, Ranking, and Electing[END_REF] as equivalents, do not always yield the same result. Other criticisms involve the consistency axiom, also known as reinforcement [START_REF] Young | An axiomatization of borda's rule[END_REF][START_REF] Young | Social choice scoring functions[END_REF]. The axioms says that if a candidate a wins in two separate elections, then this candidate must also win when combining the two electorates. Felsenthal and [START_REF] Machover | The majority judgment voting procedure: A critical evaluation1[END_REF] show that MJ violates consistency. It is worth mentioning that the authors of MJ defend their model against criticisms [START_REF] Balinski | Réponse à des critiques du jugement majoritaire[END_REF]Laraki, 2011, Balinski, 2019]. They believe that many of the problems mentioned are not major concerns in practice but, instead, arise from particular toy cases. Moreover, the authors claim that no voting model is perfect and are convinced that the pros of MJ outweigh the cons.

In this manuscript we refrain from personal judgments on the voting rule. We believe that it is worth to investigate any rule that is used in practical applications. In Chapter 6 we will analyze MJ in more detail, in particular in a situation that has not been studied yet: incomplete information.

Preference elicitation

All the methods described so far assume complete information about the preference orders of all voters over the entire set of alternatives, and about the voting mechanism itself. But how reasonable is this assumption? If the set of alternatives is very large, it is unreasonable to expect voters to provide a complete order of preferences. First from a cognitive point of view: experimental psychological studies describe how in many situations our preferences are not predefined, but rather we construct them only at the moment when we have to express them [START_REF] Lichtenstein | The Construction of Preference[END_REF]. Asking voters to express preferences when the set of choices is very wide can lead to various problems, such as confusion and low participation. Second, but no less important, this represents a huge communication cost. [START_REF] Conitzer | Communication complexity of common voting rules[END_REF] studied the communication complexity of some of the most common voting rules and, for each, provided an upper and lower bound on the number of bits of information that voters are required to communicate before the rule can select a winner. Other metrics exist, such as the number of questions voters must answer before the rule can determine a winner. This approach was used by [START_REF] Procaccia | A note on the query complexity of the condorcet winner problem[END_REF] to determine the minimum number of questions to select the Condorcet winner. In presidential elections, for example, we tend to prefer accuracy over cost, but this is not true in all applications. When it comes to choosing a restaurant to have dinner at with friends, we are likely to settle for an approximate winner rather than having to spend the entire evening ranking all the restaurants in town.

Possible and necessary winners. On these basis, [START_REF] Konczak | Voting procedures with incomplete preferences[END_REF] introduced the concepts of possible and necessary winners. Given a partial profile there are many ways to add preferences in order to build a complete profile. If an alternative a is a winner in some of these completion then a is a possible winner in the partial profile. If a is a winner in all completion then a is a necessary winner. This information can be very important during an elicitation process because if we reach a necessary winner then we may decide to stop the elicitation process. Numerous studies have been published on the computational complexity of finding possible and necessary winners [START_REF] Konczak | Voting procedures with incomplete preferences[END_REF][START_REF] Pini | Incompleteness and incomparability in preference aggregation[END_REF][START_REF] Walsh | Uncertainty in preference elicitation and aggregation[END_REF][START_REF] Xia | Determining possible and necessary winners under common voting rules given partial orders[END_REF], 2011[START_REF] Baumeister | Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules[END_REF]. See [START_REF] Lang | Collective decision making under incomplete knowledge: Possible and necessary solutions[END_REF] for a survey on possible and necessary winner not only in voting but also in other social choice scenarios like fair division, partial tournaments and hedonic games.

Although being an important concept from a theoretical point of view, the problem still persists. It is often necessary to know all, or almost all, preference rankings in order to compute a necessary winner. As for possible winners, yes, they can be used to reduce the set of alternatives, but how to choose the right approximation? [START_REF] Boutilier | Constraint-based optimization and utility elicitation using the minimax decision criterion[END_REF], and later Lu and Boutilier [2011a], proposed the use of minimax regret: the alternative a that minimizes the regret of choosing a instead of the winner in the worst case-which is the winner in the worst possible completion of the preference profile from a's perspective-is the best "current" approximation. Our elicitation procedure presented in Chapter 4 is based on this approach, but others have been suggested. For example, [START_REF] Bachrach | Probabilistic possible winner determination[END_REF] proposed a probabilistic method in which they considered for each possible winner the number of completions for which it is a winner. [START_REF] Lu | Vote elicitation with probabilistic preference models: Empirical estimation and cost tradeoffs[END_REF] suggested a mix of these two strategies to determine a minimal value k such that by asking the voters their best k alternatives is it possible to determine an approximate winner with a low regret.

Building an elicitation procedure. This brings us to another point, established that in many cases it is convenient to ask for only partial information rather than to demand the complete preferences from the beginning, how to conduct this elicitation process? And when to stop it? [START_REF] Conitzer | Vote elicitation: Complexity and strategy-proofness[END_REF], and [START_REF] Walsh | Complexity of terminating preference elicitation[END_REF] later on, studied the complexity of determining when to stop the elicitation process and concluded that it depends on the choice of elicitation procedure and voting rule. The authors proved that for some rules, like Single Transferable Vote (STV), the problem can be resolved in a polynomial time if voters are asked to provide their full preference rankings but it becomes NP-hard when considering pairwise comparison queries that ask voters to compare two specific alternatives. However, those two problems are both polynomials for some other rules like Borda and plurality.

Although there are some studies investigating the "one-shot" preference elicitation, as the work of [START_REF] Lu | Vote elicitation with probabilistic preference models: Empirical estimation and cost tradeoffs[END_REF] cited earlier, much attention has focused on incremental preference elicitation. [START_REF] Kalech | Practical voting rules with partial information[END_REF] proposed both approaches. In their first algorithm, Iterative Voting, at each round all voters are asked, at the same time, to provide their (next) best alternative. Possible and necessary winners are computed and once found one (or all) necessary winner(s) the elicitation stops. Their second algorithm, Greedy Voting, instead, ask all voters their best k alternatives and then stops the elicitation procedure. However, this method does not guarantee to find a necessary winner. Lu and Boutilier [2011a] also proposed an iterative procedure that use the minimax regret to find the next question to ask, as already mentioned, but also to decide when to stop the elicitation process. In fact, they define a threshold such that if the regret is lower than this threshold the current approximate winner is returned. [START_REF] Benabbou | Incremental preference elicitation in multi-attribute domains for choice and ranking with the borda count[END_REF] extended this work to multi-attribute domains-settings in which voters express their preferences over a set of interrelated alternatives, e.g. a multiple referendum. The authors provided an iterative elicitation procedure that stops as soon as a Borda winner can be determined and also returns an aggregated ranking of the best k alternatives. Naamani-Dery et al. [2015] proposed two incremental procedures that differ in their heuristic for choosing the next question. Their first approach selects the query, among the possible ones, that maximizes the probability of information gain. The second mechanism selects first the candidate most likely to win and then identifies the query that maximizes its possibility of winning.

There are other aspects of preference elicitation that we will not cover, for example the complexity of queries, or situations where the set of alternatives is uncertain. For more on these topics, we recommend reading Brandt et al. [2016, Ch. 10].

Uncertainty of the voting rule. In this manuscript, we will instead deal with an aspect that has not been treated much in the literature: the uncertainty of the voting rule. It is often assumed that the uncertainty of the voting rule may be due to an attempt of manipulation by the body responsible for defining the procedure. In the concluding remarks of his work, [START_REF] Walsh | Uncertainty in preference elicitation and aggregation[END_REF], mentioned as a future direction:

"Other forms of uncertainty have yet to be studied in detail. For instance, there may be uncertainty in the weight vector used by a scoring rule. The Chair may want to manipulate the election by collecting all the votes and then deciding on the weights in such a way that ensures that their preferred candidate wins. As a second example, the Chair may want to hinder strategic voting by not announcing the weights in advance or by choosing weights randomly."

A similar perspective has been adopted by subsequent works dealing with the uncertainty of the voting rule. These, just like the second part of Walsh consideration, focused on the impact of this uncertainty on voters' manipulation and strategic behavior [START_REF] Baumeister | Computational complexity of two variants of the possible winner problem[END_REF][START_REF] Elkind | Manipulation under voting rule uncertainty[END_REF][START_REF] Holliday | Strategic voting under uncertainty about the voting method[END_REF].

However, we do not believe that this is the only interesting scenario. Similarly to the case of preference profile uncertainty where it is difficult to obtain voter preferences from a cognitive and computational point of view, it may be difficult for a committee of non-experts to define an aggregation procedure. Consider the example suggested by Walsh where a committee has to formalize a scoring rule. The members of the committee may have an idea about the importance of weights, but it may be very difficult for them to properly define the scoring vector. Consider, for example, the board of a company that must decide how to aggregate experts opinions about the candidate to hire. Maybe they consider that being ranked first is "much more" valuable than being ranked second and so on, but how to define this "much more"? Should the first position be worth twice the second position? On which basis can non-experts choose this parameter? It is important to mention that the problem of how to choose the weights associated with a scoring rule has been extensively studied and it has been shown how a winner with given weights might not be one when changing the scoring vector [START_REF] Cook | A data envelopment model for aggregating preference rankings[END_REF][START_REF] Llamazares | Aggregating preferences rankings with variable weights[END_REF][START_REF] Llamazares | Ranking candidates through convex sequences of variable weights[END_REF].

To the best of our knowledge very few works tackle the problem of eliciting a voting rule. We mention the works of [START_REF] Llamazares | Aggregating preferences rankings with variable weights[END_REF], [START_REF] Viappiani | Positional scoring rules with uncertain weights[END_REF], that considers scoring rules with uncertain weights, and that of [START_REF] Cailloux | Eliciting a suitable voting rule via examples[END_REF] that proposes a framework for explaining the consequences of choosing a specific set of axioms to non-expert users so that they can take an informed decision on which rule to choose. We use this methodology of reasoning through examples when building questions to the committee to elicit their preference.

In Chapter 4, we propose an elicitation procedure that considers both preference profile and scoring vector as sources of uncertainty at the same time. This represents a novelty in the literature of voting under incomplete preference. It is important to mention that the elicitation process is conducted by a hypothetical third party external to the voting process. The committee cannot be influenced by voters preferences and vice versa. We focus on positional scoring rules with convex weights and develop elicitation strategies based on minimax regret.

Types of questions and preferences inconsistency. We consider two kind of questions: the questions to the agents are pairwise comparisons between two alternatives; the questions to the chair ask to select a winner out of an example profile. Empirical psychological studies show how alternative phrasing of the same question give rise to different preferences [START_REF] Tversky | Rational choice and the framing of decisions[END_REF]. For example, in an experiment about this phenomenon conducted by [START_REF] Irwin | Preference reversals and the measurement of environmental values[END_REF], several participants were asked to evaluate problems such as:

1 Improving the air quality in Denver.

2 Upgrading their TV. When asked to choose an alternative in a pairwise comparisons between those two options, an overwhelming majority choose to improve the air quality. However, when participants were presented these options separately, most of them were willing to pay more for upgrading their TV.

There is no best method of asking questions because all of them, in one way or another, are bound to produce inconsistencies. However, we want to provide some considerations on the two chosen formulations.

The Analytic Hierarchy Process (AHP) is a mathematical model, widely used in decision making theory, to make complex decision. It was proposed by [START_REF] Saaty | Axiomatic foundation of the analytic hierarchy process[END_REF] and it is based on the law of comparative judgment conceived by [START_REF] Thurstone | A law of comparative judgment[END_REF]. The latter is a model to retrieve information through the use of pairwise comparisons. Thus, AHP is a model that, to arrive to a complex decision, uses pairwise comparisons between the various alternatives. Although it has some criticisms, such as the inconsistency of preferences that we mentioned earlier, it is one of the most used decision-making methods. Dividing a complex problem into a hierarchy of smaller, more addressable sub-problems allows users to analyze different aspects at the time, making the choice less complicated.

Regarding the uses of example profile to elicit preferences about the voting rule, other than the work of [START_REF] Cailloux | Eliciting a suitable voting rule via examples[END_REF], we want to mention a real life experiment performed by [START_REF] Giritligil | Does majoritarian approval matter in selecting a social choice rule? an exploratory panel study[END_REF]. The authors of the latter paper, in an attempt to understand how non-experts perceived the majoritarian approval principle, created a survey in which they presented different profiles to 288 participants who had to choose a winner in each one of them. In each profile they accurately created a Majoritarian Compromise-winner, a Borda-winner and a Condorcet-winner, making sure that the first is always distinct from the other two. They concluded that, although many of the participants consistently chose the Borda-winner, the Majoritarian-winner was also well supported.

Preference elicitation in Decision

Aiding. The problem of information elicitation is extensively studied in the domain of decision aiding. In this context, there is a Decision Maker (DM) who seeks the help of an expert party, an analyst, to develop recommendations that the DM can later use to make her choices. In this process, there is a stage where the analyst has to formalize the problem in the form of a mathematical model. To do so, it is important to get the preferences of the DM, who, as a non-expert, often fails to identify the parameters relevant to the problem. It is the job of the analyst to ask the right questions to obtain the preference information. Different approaches to elicitation have been proposed based on the choice of those questions, but also the availability (and patience) of the DM, or whether the DM is a real person or a digital database. Please see [START_REF] Bouyssou | Evaluation and Decision Models with Multiple Criteria: Stepping Stones for the Analyst[END_REF] for a more detailed account on the matter and [START_REF] Mousseau | A general framework for constructive learning preference elicitation in multiple criteria decision aid[END_REF], in the context of Multiple Criteria Decision Aid, and [START_REF] Belahcene | Towards accountable decision aiding : explanations for the aggregation of preferences[END_REF] for an overview of these methods. In particular, the latter, much like [START_REF] Cailloux | Eliciting a suitable voting rule via examples[END_REF], proposes a framework for the explanation of the elicitation process itself. In fact, similarly to how [START_REF] Cailloux | Eliciting a suitable voting rule via examples[END_REF] tries to elicit the voting rule through concrete examples, Belahcene [2018] tries to do the same to elicit preference information instead of explaining the result of the recommendation. As a side note, it is also interesting to mention that it is often assumed that in an elicitation process the analyst tries to elicit information that the DM has but which is unknown by the analyst. This is not always the case. Bouyssou et al. [2000, Ch. 8] presented a scenario of information uncertainty with a real case example. A company dealing with the production and distribution of electricity-which here represents the DM-asked the help of a research group-which embodies the analyst-for the realization of a decision-aiding tool that would help them with the company choices. Every three years the company had to reevaluate its plan of building or closing its various (coal, nuclear, and gas) power plants. When formalizing the model, the authors realized that the values to assign to the various criteria were mostly uncertain. For example, the fuel price fluctuates according to the market, the electricity demand may depend on the weather, and a specific pollution legislation may have an impact on the company policy. The authors proposed a model based on successive pairwise comparisons: at each step it compares the consequences of two different decision in the same scenario. The model was adopted by the company, however, the authors showed some drawbacks of the model, in particular how it can lead to inconsistencies, and discussed why they did not adopt a probabilistic approach. Although it is not in the scope of our research, because we assume that the unknown information exists somewhere but is unknown to us, this consideration opens the door to many other potentially interesting scenarios to investigate.

Preference Elicitation in Machine Learning. In general, when we think of machine learning problems we tend to divide them into classification problems-in which the goal is to predict the category into which a particular instance falls-and regression problems-in which the purpose is to predict the value of a particular variable associated with an instance. However, many reallife problems are based on preferences of individuals. Consider, as an example, the enormous amount of information on the Web. It is impossible for users to find something without efficient Information Retrieval (IR) mechanisms. Given a query submitted by the user, an IR mechanism provides a list of documents ranked in order of relevance. The ranking is the key element that defines a good system. We might approach the problem by predicting whether or not a document is relevant to the query, as in a classification problem, or by calculating the probability that a document is relevant, like a regression problem. However, we are leaving out an important piece of information that is the correlation between the documents that are not independent variables but are all potential answers to the query. This makes ranking a fundamentally different problem than classification and regression. Document retrieval is only one example of the use of rankings in IR, a detailed account of which can be found in [START_REF] Liu | Learning to rank for information retrieval[END_REF], but other uses can be found like recommender systems.

The uses of preferences and rankings play a key role in many machine learning problems. The process of learning preference models from already existing and, available, preference information is denoted as Preference Learning. [START_REF] Fürnkranz | Preference Learning[END_REF] provided a comprehensive overview of this sub-field of machine learning. Given a set of items and a set of preferences over these items, the goal of a preference learning task is to learn a function that predicts preferences for a different set of items producing, as a result, a total order of the whole set of items-this task is denoted as Object Ranking-, or that predicts preferences of new users over the same set of items-denoted as Label Ranking. The training preference information is usually given as a set of pairwise preferences. This looks quite similar to our elicitation problem, where we have incomplete information that we need to learn. However, there are many differences between the two approaches. First, in elicitation we try to learn about each individ-ual preferences in order to find the most accurate approximation, in preference learning, on the other hand, the goal is to find a good prediction that is good on average on the entire population. Moreover, preference elicitation often assumes that, as seen in the psychological studies aforementioned, preferences are constructed concurrently with the elicitation process. This involves a third party who communicates interactively with each individual. In cases of inconsistencies this party could notice and correct them, perhaps by asking clarifying questions to the individuals who produced such inconsistency. In preference learning, on the contrary, a ground truth is assumed and the quality of the prediction is measured based on its differences from the truth. Moreover, these preferences exist in a database and are always accessible but there is no interactive process that can help correct inconsistencies. Note that, in Chapter 4, we assume the existence of a generic external party, that could represent the analyst in decision aiding, but we do not implement the idea of resolving inconsistencies.

There are, however, works that position themselves between these two approaches filling the gaps. For example, in Chapter 4 we assume the existence of a ground truth, and [START_REF] Bachrach | Probabilistic possible winner determination[END_REF], [START_REF] Lu | Vote elicitation with probabilistic preference models: Empirical estimation and cost tradeoffs[END_REF] studied preference elicitation in a probabilistic setting. On the machine learning side, many studies try to put "humans-in-the-loop" to receive feedback on predictions and, in general, to get more accurate results [START_REF] Wu | A survey of human-in-the-loop for machine learning[END_REF]; and active learning relaxes the hypothesis under which data are always accessible and instead queries users to provide labels for instances [START_REF] Settles | Active learning literature survey[END_REF]. CHAPTER 4

SIMULTANEOUS ELICITATION OF SCORING RULE AND AGENT PREFERENCES FOR ROBUST WINNER DETERMINATION

Social choice deals with the problem of determining a consensus choice from the preferences of different agents. In the classical setting, the voting rule is fixed beforehand and full information concerning the preferences of the agents is provided. This assumption of full preference information has recently been questioned by a number of researchers and several methods for eliciting the preferences of the agents have been proposed. In this paper we argue that in many situations one should consider as well the voting rule to be partially specified. Focusing on positional scoring rules, we assume that the chair, while not able to give a precise definition of the rule, is capable of answering simple questions requiring to pick a winner from a concrete profile. In addition, we assume that the agent preferences also have to be elicited. We propose a method for robust approximate winner determination and interactive elicitation based on minimax regret; we develop several strategies for choosing the questions to ask to the chair and the agents in order to converge quickly to a near-optimal alternative. Finally, we analyze these strategies in experiments where the rule and the preferences are simultaneously elicited.

Introduction

Aggregation of preference information is a central task in many computer systems (recommender systems, search engines, etc). In many situations, such as in group recommender systems, the goal is to find a consensus choice; social choice theory can provide foundations for such applications. The traditional approach to social choice assumes that 1) the full preference orderings of the agents and 2) the social choice function are expressed beforehand. These represent two strong hypotheses. Requiring agents to express full preference orderings can be prohibitively costly (in terms of cognitive and communication cost). This observation has motivated several works assuming partial preference orders: one early work is by [START_REF] Conitzer | Communication complexity of common voting rules[END_REF] who studied the complexity of communication when using different voting rules; [START_REF] Konczak | Voting procedures with incomplete preferences[END_REF] studied the computation of possible and necessary winners for various voting rules; [START_REF] Xia | Determining possible and necessary winners under common voting rules given partial orders[END_REF] then showed that, while the identification of a necessary co-winner in scoring rules is polynomial, the determination of possible co-winners is NP-hard; additional complexity results were given by [START_REF] Walsh | Uncertainty in preference elicitation and aggregation[END_REF] and [START_REF] Pini | Incompleteness and incomparability in preference aggregation[END_REF].

Since in many practical situations there would be too many possible winners but no necessary winners, several works addressed the problem of agent preferences elicitation using a variety of approaches (minimax regret, Bayesian methods, etc.) with the goal of converging to a necessary winner [START_REF] Naamani-Dery | Preference elicitation for group decisions using the borda voting rule[END_REF][START_REF] Kalech | Practical voting rules with partial information[END_REF], Lu and Boutilier, 2011a[START_REF] Pini | Aggregating partially ordered preferences[END_REF][START_REF] Benabbou | Incremental preference elicitation in multi-attribute domains for choice and ranking with the borda count[END_REF][START_REF] Dey | Preference elicitation for single crossing domain[END_REF]. Among those, [START_REF] Walsh | Complexity of terminating preference elicitation[END_REF] and [START_REF] Conitzer | Eliciting single-peaked preferences using comparison queries[END_REF] analyzed when to stop the elicitation process.

A second concern is the ability of the chair (the person or organization supervising the voting process) to provide a precise definition of the voting rule, suggesting the relaxation of the second hypothesis. Indeed, it is often difficult for non-experts to formalize a voting rule on the basis of some generic preferences over a desired aggregation method. Here we provide two examples of such situations.

Consider, as a first example, a chair that is about to hire a new employee whose performances are evaluated by several experts. The members of the chair may not have a voting rule in mind at the start of the process, and might not wish to agree on a specific voting rule. However, they might be willing to answer a few questions requiring to select who should be the winner out of specific profiles.

Consider, as a second example, the reviewing process of a conference where the best paper must be elected. The agents express their preferences on the papers they reviewed, but they are not aware of the voting rule the Program Chair will apply when aggregating them. Nonetheless, reviewers are still willing to participate in the process. Also, the PC may not have a specific voting rule in mind, and she will find it hard to provide a precise scoring vector if asked. Maybe she strongly believes that being ranked once in the first position is "much more" valuable than being ranked two times second, but does not know exactly how much more (though she can judge example cases).

In this paper, we focus on positional scoring rules with convex weights, that are a particularly common method used to aggregate rankings. We develop methods, based on the notion of minimax regret, for determining a robust "winner" under uncertainty of both the voting rule and the agent preferences. We provide incremental elicitation methods that at each step of the elicitation question either one of the agents or the chair, and we discuss several heuristics to choose questions that quickly reduce the regret. Answers to questions are encoded as constraints; questions to the agents are comparisons between pairs of alternatives while questions to the chair ask to select a winner out of a synthetic profile.

While some previous works have considered partially specified aggregation methods [START_REF] Stein | A stochastic dominance analysis of ranked voting systems with scoring[END_REF][START_REF] Llamazares | Aggregating preferences rankings with variable weights[END_REF][START_REF] Viappiani | Positional scoring rules with uncertain weights[END_REF], we do not know of any work considering both sources of uncertainty at the same time. Actually, very few works altogether have considered the problem of eliciting a voting rule by asking questions to the chair. We mention the work of [START_REF] Cailloux | Eliciting a suitable voting rule via examples[END_REF] that assumes a different representation for the rule. Additionally, some works address the manipulability of voting rules [START_REF] Elkind | Manipulation under voting rule uncertainty[END_REF][START_REF] Dey | Complexity of manipulation with partial information in voting[END_REF], Conitzer et al., 2011[START_REF] Baumeister | Manipulative design of scoring systems[END_REF] and strategic behaviors [START_REF] Endriss | Strategic voting with incomplete information[END_REF][START_REF] Lev | Heuristic voting as ordinal dominance strategies[END_REF][START_REF] Reijngoud | Voter response to iterated poll information[END_REF].

Our approach is evaluated on simulations with synthetic and real datasets where both the voting rule and the agent preferences are initially unknown to the system and incrementally re-4.2. SOCIAL CHOICE WITH PARTIAL INFORMATION vealed through questioning. We assume the chair to be human, thus able to answer questions about a limited number of alternatives, so we focus on small scale social choice situations. We compare the effectiveness of several questioning strategies based on the current knowledge of the rule and preferences. To summarize our contributions: 1) we provide a novel mechanism for eliciting a voting rule by translating abstract questions about weights to a choice of an alternative given a concrete profile; 2) we show that with our elicitation method it is possible to reach low regret with a reasonable number of questions; 3) we present elicitation strategies that achieve good results within reasonable computation time; 4) we show that for the class of rules considered, asking a few questions to the chair suffice to reach low regret; 5) our experiments suggest that low degree of similarity among preferences (as in impartial culture) is a more challenging setting than less varied profiles.

Social choice with partial information

We now introduce some basic concepts. We consider a set A of m alternatives (products, restaurants, public projects, job candidates, etc.) and an infinite set N of potential agents.

A profile (≻ j , j ∈ N ) considers a finite subset of agents N ⊂ N and associates to each agent a preference order ≻ j ∈ L(A), a linear order over the alternatives. A profile is equivalently represented by v = (v j , j ∈ N ) where v j (x) ∈ {1, . . . , m} denotes the rank of alternative x in the preference order ≻ j . A social choice function f : ∪ ∅̸ =N ⊂N,N finite L(A) N → P * (A) associates to each profile a set of (tied) winners, where P * (A) is the powerset of A excluding the empty set. Among the many possible social choice functions, we consider convex positional scoring rules (PSRs). A PSR f w is parameterized by a scoring vector w associating weights w r ∈ [0, 1] to positions, with 1 = w 1 ≥ w 2 ≥ . . . ≥ w m = 0. Let α x r be the number of times that alternative x was ranked in the r-th position. Given v and w, an alternative x ∈ A obtains the score

s(x; v, w) = j∈N w v j (x) = m r=1 α x r w r . (4.1)
The winners f w (v) are the alternatives with highest score. An important class of PSRs is the one using convex weights [START_REF] Stein | A stochastic dominance analysis of ranked voting systems with scoring[END_REF][START_REF] Llamazares | Ranking candidates through convex sequences of variable weights[END_REF], meaning that the difference between the weight of the first position and the weight of the second position is at least as large as the difference between the weights of the second and third positions, etc.

∀r ∈ {1, . . . , m -2} :

w r -w r+1 ≥ w r+1 -w r+2 . (4.2)
The constraint above is a natural and common assumption, often used when aggregating rankings in sport competitions (such as F1 racing, alpine skiing world cup): losing ranks at the top is more damaging than losing ranks at the bottom. Let W denote the set of such convex weight vectors. We consider a specific finite set of agents N * ⊂ N and let v * = (≻ * j , j ∈ N * ) and w * denote the profile and weight vector, unknown to us, that represent the preferences of the agents in N * and of the chair. The vector w * is also unknown but we assume that the chair is able to specify additional preference information taking the form of linear constraints about w * . Let W ⊆ W denote the set of weight vectors compatible with the preferences expressed by the chair about the scoring vector. We will show in Section 4.4 that the additional preferences we use can be elicited by showing a complete profile of a synthetic election and asking who should be elected in this case.

Robust winner determination

It is desirable in an elicitation protocol such as ours to be able to stop before reaching full knowledge of the agent preferences or of the preferences of the chair about the voting rule. As, often, there are no necessary winners and too many possible winners, it is useful to declare a winner given partial information. As a decision criterion to determine a winner, we propose to use minimax regret [START_REF] Savage | The Foundations of Statistics[END_REF]. This decision criterion has been used for robust optimization under data uncertainty [START_REF] Kouvelis | Robust Discrete Optimization and Its Applications[END_REF] as well as in decision-making with uncertain utility values [START_REF] Salo | Preference ratios in multiattribute evaluation (PRIME)elicitation and decision procedures under incomplete information[END_REF]Hämäläinen, 2001, Boutilier et al., 2006]. In particular, Lu and Boutilier [2011a] have adopted minimax regret for winner determination in social choice where the preferences of agents are partially known, while the social choice function is known.

We consider the simultaneous presence of incomplete knowledge in agent preferences and in the weights of the PSR. We use maximum regret to quantify the worst-case error, and let the alternatives that minimize this quantity win, giving some robustness in face of ignorance. Intuitively, the quality of a proposed alternative a is how far a is from the optimal one in the worst case, given the current knowledge.

Given p and W (that represent the current knowledge about agent preferences and the PSR), the maximum regret is considered by assuming that an adversary can both 1) extend the partial profile p into a complete profile, and 2) instantiate the weights choosing among any weight vector in W . We formalize the notion of minimax regret in multiple steps. First of all, Regret(x, v, w) is the "regret" of selecting x as a winner instead of the optimal alternative under v and w:

Regret(x, v, w) = max y∈A s(y; v, w) -s(x; v, w).

The pairwise maximum regret of x relative to y given the partial profile p and the set of weights W is the worst-case loss of choosing x instead of y under all possible realizations of the full profile and all possible instantiations of the weights:

PMR(x, y; p, W ) = max w∈W max v∈C(p)

s(y; v, w) -s(x; v, w).

The maximum regret is the worst-case loss of x:

MR(x; p, W ) = max y∈A PMR(x, y; p, W ) = max w∈W max v∈C(v)
Regret(x; v, w). (4.3) MR(x; p, W ) is the result of an adversarial selection of the complete profile v ∈ C(p) and of the scoring vector w ∈ W that jointly maximize the loss between x and the true winner under v and w. Finally, MMR(p, W ) = min x∈A MR(x; p, W ) is the value of minimax regret under p and W , obtained when recommending a minimax optimal alternative x * p,W ∈ A * p,W = argmin x∈A MR(x; p, W ). Picking as consensus choice an alternative associated with minimax regret provides a recommendation that gives worst-case guarantees. In cases of ties, we can return all minimax alternatives A * p,W as winners or pick one of them using some tie-breaking strategy.

Observe that if MMR(p, W ) = 0, then any x * p,W ∈ A * p,W is a necessary winner: any valid completion of the profile and choice of w ∈ W gives to x * p,W the highest score. We note that our notion of regret gives some cardinal meaning to the scores: instead of just being used to select winners under the corresponding PSR, their differences are considered as representing the regret of the chair.

Computation of minimax regret Given a voting rule and a partially specified profile, [START_REF] Xia | Determining possible and necessary winners under common voting rules given partial orders[END_REF] determine necessary winners by showing constructions that attempt to maximize the score difference between a proposed winner and a chosen alternative. This reasoning was later adopted by Lu and Boutilier [2011a] who used the considerations on the worst-case completions for computing the minimax regret.

In order to compute pairwise maximum regret, and therefore minimax regret, we decompose the PMR into the contributions associated to each agent by adapting this same reasoning to our setting. The context is however more challenging due to the presence of uncertainty in the weights.

Recall that, in the computation of s(x; v, w), w v j (x) represents the score that x obtains in the ranking v j (see Eq. (4.1)). Since scoring rules are additively decomposable, we can consider separately the contribution of each agent to the total score. Thus, we can write the actual regret of choosing x instead of y as s(y; v, w) -s(x; v, w) = j∈N w v j (y) -w v j (x) , and we obtain PMR(x, y; p, W ) = max

w∈W j∈N max v j ∈C(≻ p j ) [w v j (y) -w v j (x) ].
The following propositions show that the procedure for completing a partial profile, proposed by Lu and Boutilier [2011a] when considering a fixed weight vector, also applies in our setting. We write a ⪰

a ≻ j x ⇔ ¬(x ⪰ p j a); (4.4) y ≻ j a ⇔ ¬(a ⪰ p j y) ∧ ¬((x ⪰ p j y) ∧ ¬(x ⪰ p j a)). (4.5)
Proof Sketch. Consider our knowledge ⪰ p j about the preference of the agent j. The adversary's goal is to make the score of y as high as possible and the score of x as low as possible. To do this, he should complete ≻ p j to ≻ j by placing above x as many alternatives as possible; that is, all the alternatives except those that are known to be worse than x (those a such that x ⪰ p j a); and similarly, he should put below y all the alternatives he can. Two conditions must be excluded for a to go below y. The alternatives such that a ⪰ p j y can't be put below y. Furthermore, the first objective must take priority over the second one: when an alternative should go above x according to the first objective (because ¬(x ⪰ p j a)), and x is known to be better than y (thus x ⪰ p j y), then a should be put above x (irrespective of whether a ⪰ p j y), which will move both x and y one rank lower than if a had been put below y. This maximizes the adversary's interests: because the weight vector is convex, the score difference will be lower when both alternatives are ranked lower (Equation 4.2), and that difference of scores is in favor of x when x ≻ p j y, thus to be minimized from the the adversary's point of view. Proof. The rank of x is directly obtained from Eq.(4.4). The rank of y is obtained by complementing Eq.(4.5), obtaining a ⪰ j y ⇔ (a

⪰ p j y) ∨ ((x ⪰ p j y) ∧ ¬(x ⪰ p j a)
), and, observing that a ≻ j y ⇔ a ̸ = y ∧ a ⪰ j y, obtaining that a ≻ j y if and only if The max regret MR(x; p, W ) is determined by computing the pairwise regret of x with all other alternatives in A, and the recommended alternatives are the ones with least max regret. Observe that when the PMR of an alternative x (against some other alternative y) exceeds the best MR value found so far, we do not need to further evaluate x. This idea can be exploited using a minimax-search tree [START_REF] Braziunas | Decision-Theoretic Elicitation of Generalized Additive Utilities[END_REF].

(a ̸ = y) ∧ [(a ⪰ p j y) ∨ ((x ⪰ p j y) ∧ ¬(x ⪰

Interactive Elicitation

We propose an incremental elicitation method based on minimax regret. At each step, the system may ask a question either to one of the agents about her preferences or to the chair about the voting rule. The goal is to obtain relevant information to reduce minimax regret as quickly as possible. The elicitation can be terminated either after a given number of questions, or when the minimax regret is lower than a threshold (or when it drops to zero if we wish optimality).

Question types

We distinguish between questions asked to the agents and questions asked to the chair. As questions asked to the agents we consider comparison queries relating two alternatives. The effect of a response to a question asked to an agent is the increase in our knowledge about the agent rankings, thus augmenting the partial profile p. If agent j answers a comparison query stating that alternative a is preferred to b, then the partial order ≻ p j is augmented with a ≻ p j b and by transitive closure. A bit more discussion is needed about questions asked to the chair. Such questions aim at refining our knowledge about the scoring rule; a response gives us a constraint on the weight vector w. In particular, we want to obtain constraints of the type w r -w r+1 ≥ λ(w r+1 -w r+2 ) for r ∈ {1, . . . , m -2}, relating the difference between the importance of ranks r and r + 1 with the difference between ranks r + 1 and r + 2.

Building concrete questions for the chair Even if the chair might be considered able to answer directly such abstract questions, we want to ensure that these questions can also, in principle, be asked in a more concrete way: in terms of winners of example profiles. Such questions have clear semantics whose understanding can be assumed to be shared by the chair, contrary to abstract questions about weights. Moreover, this way of questioning the chair is independent of the voting rule that is being elicited; whereas questions about weights only make sense when considering PSRs. Asking who should win in specific profiles has been used in experimental settings investigating the feeling of justice of individuals [START_REF] Giritligil | Does majoritarian approval matter in selecting a social choice rule? an exploratory panel study[END_REF], but, to the best of our knowledge, the use of such questions to systematically guide an elicitation process about voting rules is novel. This is similar to favor, in decision theory, direct choice questions ("please choose either a or b") compared to, say, questioning the decision maker about the shape of her utility function. The former are considered "observable": acts of choice are translated to preference statements [Mas-Colell et al., 1995, Ch. 1].

Although questioning in terms of profiles and in terms of weights is logically equivalent in our setting, there is no a priori certainty that questioning the chair using different phrasing would yield logically equivalent answers: research in experimental psychology shows that participants' answers differ widely when changing the phrasing of preference-related questions [START_REF] Lichtenstein | The Construction of Preference[END_REF]. To get out of such conundrums, we need a language considered "fundamental". Questions of the form "In this profile, who should win?" arguably provides such a natural language.

Thus, our task is to build a profile, given λ and r ≤ m -2, in such a way that the set of (tied) winners picked by the chair reveals whether w r -w r+1 ≥ λ(w r+1 -w r+2 ).

Proposition 4.4. Given a rational λ = p/q > 1 and a rank r between 1 and m -2, there exists a profile P such that, for any weight vector w ∈ W, a ∈ f (P ) iff w r -w r+1 ≥ λ(w r+1 -w r+2 ) and b ∈ f (P ) iff w r -w r+1 ≤ λ(w r+1 -w r+2 ), where f is the PSR parameterized with w.

Proof. Define a linear order > 1 over A as placing a at rank r, b at rank r + 1, and the remaining alternatives arbitrarily. Define > 2 over A as placing a at rank r + 2, b at rank r + 1, and the remaining alternatives arbitrarily. Define an arbitrary linear ordering > over A \ {a, b}. Define a linear order > 3 as placing a first, b second, and following the order of > for the remaining positions. Finally, define a linear order > 4 as placing b first, a second, and following the inverse order of > for the remaining positions.

Define P as the profile of 3(p + q) agents containing q times > 1 , p times > 2 , and > 3 and > 4 each p + q times. As a result, a obtains the following ranks: q times r, p times r + 2, p + q times first, and p + q times second. The alternative b obtains the ranks r + 1, 2 and 1, each p + q times. Consider any alternative c ∈ A \ {a, b}. Its score is maximal when it comes first in > 1 , first in > 2 and first in >, by convexity of the weights. In that case, c is positioned at the ranks 1, 3 and m, each p + q times.

Letting s(x) denote the score of x at P , we obtain s(a) = qw r + pw r+2 + (p + q)w 1 + (p + q)w 2 , thus, s(a) ≥ (p+q)w m +(p+q)w 1 +(p+q)w 2 ; s(b) = (p+q)w r+1 +(p+q)w 2 +(p+q)w 1 ; and, ∀c ∈ A \ {a, b}, s(c) ≤ (p + q)w 1 + (p + q)w 3 + (p + q)w m . It follows that a or b maximize s (as s(a) ≥ s(c)). We conclude by observing that a ∈ f (P ) ⇔ s(a) ≥ s(b) ⇔ qw r +pw r+2 ≥ (p + q)w r+1 ⇔ w r -w r+1 ≥ (p/q)(w r+1 -w r+2 ), and similarly for b ∈ f (P ).

Example 4.1. Suppose we want to ask the following question to the chair: w 2 -w 3 ≥ 2(w 3w 4 ). We show the profile in Figure 4.1a to the chair and ask who should win (each column is the preference of one agent). Both a and b have scores higher than c and d for all convex weights, thus either a or b will be picked under our hypothesis; and s(a) ≥ s(b) ⇔ w 2 + 2w 4 ≥ 3w 3 . Figure 4.1b represents the same profile using a compressed view, the numbers in bold indicating the number of agents having the preference in the corresponding column. As the proof shows, constructed profiles require only four different linear orders.

Elicitation strategies We develop several strategies for simultaneous elicitation of agent preferences and of the PSR. While it is of course possible to first fully elicit the agent preferences and afterwards elicit weights, we want to investigate approaches that are able to recommend winning alternatives before obtaining complete knowledge of the profile or the rule. We define here various strategies; a strategy tells us, given the current partial knowledge (p, W ), which question to ask next.

The Random strategy is used as a baseline. It first chooses equiprobably whether to question the chair or the agents. In the first case, it draws one rank in 1 ≤ r ≤ m -2 equiprobably, takes the middle of the interval of values for λ that are still possible considering our knowledge so far, and asks whether w r -w r+1 ≥ λ(w r+1 -w r+2 ). In the second case, it draws equiprobably among the agents whose preference is not known entirely; it then draws an alternative a among those involved in some incomparabilities in ≻ p j and an alternative b among those incomparable with a in ≻ p j . Let (x * , ȳ, v, w) be the current solution of the minimax regret, where x * is the minimax optimal alternative and ȳ, v, w the corresponding adversarial choices. The Pessimistic strategy considers a set of n + (m -2) candidate questions: one per agent, and one per rank (excluding the first and the last one which are known).

The candidate questions to the agents are chosen by extending the idea of Lu and Boutilier [2011a], that privilege learning about the relationship of x * and ȳ to the other alternatives if possible. Given j ∈ N * , if x * and ȳ are incomparable in ≻ p j , the candidate question concerns the pair (x * , ȳ), otherwise, it concerns the pair (x * , z) for some z incomparable to x * (randomly chosen), or if none such z exist, the pair (ȳ, z) for some z incomparable to ȳ, or, if both x * and ȳ are comparable to every alternatives in ≻ p j , any incomparable pair is picked at random. The candidate questions to the chair are determined as in the Random strategy. Once having selected n + m -2 candidate questions, the Pessimistic strategy selects the one that leads to minimal regret in the worst case. Assume that a question q 1 has type t 1 (being "chair" or "agent"), and leads to the new knowledge states (p 1 , W 1 ) if answered positively and

(p ′ 1 , W ′ 1 ) if the answer is negative. Define R max 1 = max{MMR(p 1 , W 1 ), MMR(p ′ 1 , W ′ 1 )} and R min 1 = min{MMR(p 1 , W 1 ), MMR(p ′ 1 , W ′ 1 )}ϵ t + ϵ ′ t .
The terms ϵ t and ϵ ′ t are real numbers associated to the type t of question; these parameters are used to fine tune the choice of the question type. Define similarly t 2 , R max 2 and R min 2 for q 2 . Pessimistic considers question q 1 to be better than q

2 iff R max 1 < R max 2 or [R max 1 = R max 2 and R min 1 < R min 2 ].
In other words if the maximal a posteriori MMR of two questions are (approximately) equal, then it considers the (penalized) minimal MMR values.

The Extended pessimistic strategy uses the same criterion as the pessimistic strategy, but extending it to a bigger set of candidate questions, the same as those considered by the Random strategy. These candidate questions are then evaluated using the same operator as for the Pessimistic strategy. Extended pessimistic is applicable only to very small problem instances: its complexity is in O(n 2 m 5 ), because we consider O(m 2 ) questions for each agent and need for each question to compute MMR twice, whose complexity is O(nm 3 ).

The Two phases strategy is developed in order to investigate the effect of varying the proportion of questions of the two types, when asking all questions to the chair at the beginning or at the end. It is parameterized by q c , the number of questions to be asked to the chair. The Two phases-ca variant first asks q c questions to the chair, then k -q c questions to the agents, using in both cases Pessimistic to select the specific questions; whereas the Two phases-ac variant starts with k -q c questions to the agents, then questions the chair.

Finally, the Elitist strategy aims at uncovering as quickly as possible the top alternatives of all agents. For any agent j, it asks to compare an alternative currently undominated in ≻ p j with one that is currently incomparable. Thus, the top alternative for j will be known after having asked exactly m -1 questions to j. After having asked n(m -1) questions to the agents, it questions the chair only, using the same approach as Pessimistic. This strategy can be expected to perform well when the chair assigns a large weight to the first rank, as compared to the other ranks. It is used to further challenge Pessimistic, which is not specifically tailored to such a situation.

Empirical Evaluation

We performed several numerical experiments using both real data and randomly generated profiles in order to validate our approach and test the performance of our elicitation strategies.

Given a problem size (m, n), a number of questions k and a strategy to test, we first create an "oracle", representing the true preferences of the agents (randomly generated or coming from real data) and the weights associated with the chair's scoring rule (randomly generated). We start with empty knowledge (p = ∅, W = W) about the preference orderings of the agents and the weights of the chair. We obtain the first question to be asked using the strategy under test. We then use the oracle to answer the question and update the system's knowledge, which is thus used to obtain the next question. This is repeated until k answers have been obtained, computing the resulting MMR values along the way for various values of k. We repeat this whole experiment a variable number of times, for a given (m, n, k), and report the average resulting MMR and standard deviation sd. The sizes of the considered scenarios are comparable to the ones used by [START_REF] Cailloux | Eliciting a suitable voting rule via examples[END_REF].

The oracle is built as follows. For the real preferences, we used three datasets from PrefLib [START_REF] Mattei | Preflib: A library of preference data PREFLIB[END_REF] k Pes. ± sd Eli. ± sd 0 20.0 ± 0.0 20.0 ± 0.0 50 16.0 ± 0.5 17.3 ± 0.4 100 12.5 ± 0.9 15.6 ± 0.4 150 9.6 ± 1.4 13.9 ± 0.8 200 7.4 ± 1.3 11.0 ± 1.1 250 5.3 ± 1.5 6.6 ± 0.8 300 3.5 ± 1.3 6.6 ± 0.8 datasets, we follow an Impartial Culture (IC) assumption: the linear order of each agent is drawn i.i.d. uniformly. We believe IC to be a challenging situation and expect the number of questions to ask, in order to reach a certain level of regret, to decrease with less varied profiles. To generate the scoring rule weights, we first draw m-1 numbers uniformly at random (in the interval 0, 1 representing weight "differences"), normalize and sort them; a sequence of convex decreasing weights is then obtained by a decumulative sum. The penalty parameters for the Pessimistic and Extended pessimistic strategies are ϵ chair = 1.1, ϵ ′ chair = 10 -6 , ϵ agent = 1.0 and ϵ ′ agent = 0.

Comparison of strategies Our first experiment concerns small size situations. Figure 4.2 compares some of our strategies in the case m = 5, n = 10 (variations around this size yield similar conclusions), where the results are averaged over 200 runs. We see that asking random questions does not allow to reach a low regret level even after having asked 100 questions, whereas a low regret level (MMR = 1) is reached by Pessimistic before having asked 60 questions. This also holds for other problem sizes. For instance, for m = 10, n = 20 and 500 questions, Random strategy reaches an average regret (over 20 runs) of 9.3 (±0.7) and Pessimistic 0.5 (±0.5). We notice that Pessimistic performs slightly better than Extended pessimistic, showing that Pessimistic chooses candidate questions wisely; this is good news since Pessimistic is much faster: it takes on average only 16s for a complete elicitation session (for m = 5, n = 10 and 100 questions), while Extended pessimistic takes 50s. Although their performance is close, Pessimistic performs systematically better in multiple runs of the experiment. We also compared the Pessimistic strategy against Elitist in a situation specifically tailored to advantage Elitist. For that experiment specifically, instead of drawing the weights of the oracle randomly, we fix it to a "geometric" weight vector, such that w r -w r+1 = 2(w r+1 -w r+2 ), for all r ≤ m -2, so as to dramatically increase the importance of the weights associated to the top ranks. Even in that case, we see in Table 4.1 that Pessimistic performs better than Elitist.

Evaluation of Pessimistic Strategy Our next set of experiments evaluate the Pessimistic strategy in absolute terms. We first wonder how many questions should be asked in order to achieve low regret, fixed at n/10: this is equivalent to the difference of score of an alternative x that results from switching from a profile P to a profile P ′ where a tenth of the agents rank x last instead of first. Table 4.2, first five columns, contains the result: it displays, for each dataset, the number of questions asked to the chair (q MMR≤n/10 c ), and the quartiles of the number of questions asked to the agents (q MMR≤n/10 a ), averaged over 20 runs. It is interesting to note that about twenty or thirty questions per agent on average suffice to reach a low regret in those instances. We find also noteworthy that the Pessimistic strategy chooses to ask zero questions to the chair but still achieves low regret, in most of those instances.

Another interesting measure is the average number of questions asked to the chair (q MMR=0 c ) and to the agents (q MMR=0 a ) before reaching zero regret. The results for various sizes are displayed in the last two columns of Table 4.2. Here, we see that the Pessimistic strategy does choose to question the chair when reaching low enough regret values. The m15n30 dataset did not reach zero regret in 1000 questions.

Figure 4.3 shows the decrease in MMR according to the number of questions asked for various problem sizes. In particular, this shows important differences between some real datasets and the problems generated using IC. In the Skate problem, the value MMR = 1 is reached after less than 100 questions, while the IC case of the same size (m = 14, n = 9) requires more than 200 questions to reach that value. This reasoning also applies to the Courses dataset but not to the T Shirt dataset. This can be explained by the high degree of similarity in the preference rankings of the Skate and the Courses problems, which helps reducing the regret faster. For example, in Skate the top-2 alternatives are the same for all agents, and 8 out of 9 agents rank the same alternative at position 3. By contrast, in T Shirt, the alternatives are evenly distributed in the preference rankings.

Comparison with Two Phases

The experiments so far let the strategy free to question either the chair or an agent at each step. One may wonder what is lost in terms of regret by asking different proportions of questions to the chair and the agents. Such restrictions may be useful because of (partial) unavailability of the chair, or because the estimated cognitive costs may differ sensibly.

Table 4.3 shows the MMR value reached in problems of size m = 10, n = 20 after 500 questions, using the Two phases strategy, in the "ca" (chair then agents) and in the "ac" (agents then chair) variants. These numbers are to be compared with the MMR value reached after 500 questions with the Pessimistic strategy (displayed in Fig. 4.3), which is 0.7; the Pessimistic strategy asks on average 13 (± 13) questions to the chair in this setting. The line q c = 0, where no question is asked to the chair, suggest that it is possible to obtain a good-quality recommendation while knowing only that the voting rule is a scoring rule with convex weights, which is our basic hypothesis. However, we observe that asking no questions to the chair does not permit to reach MMR = 0. The strategy, indeed, obtains full knowledge of the profile after an average of 500 questions to the agents but never reaches zero.

Conclusions

In this paper we have considered a social choice setting with partial information about the agent preferences and voting rule. We have proposed the use of minimax regret both as a means of robust winner determination and as a guide to the process of simultaneous elicitation of preferences and voting rule. Our experimental results suggest that regret-based elicitation is effective and allows to quickly reduce worst-case regret significantly. They also show that, in our setting, good quality (low regret) recommendations can be achieved short of having full knowledge of weights or profile.

As part of our contribution, we provide an open-source library that can be found at https: //github.com/oliviercailloux/minimax, to reproduce our experiments and perform many more.

Some directions for future works include developing new elicitation strategies, considering alternative heuristics; extending the elicitation to voting rules beyond scoring rules; eliciting preferences while restraining to concrete and easy questions.

CHAPTER 5

JAVA PACKAGE TO SUPPORT ELICITATION IN SOCIAL CHOICE

UML

The Unified Modeling Language (UML) is a standard language for modeling, building and documenting the design of a software system. It is often defined as the language in which the system's blueprint is written. In fact, various aspects of the system can be described by UML diagrams: use cases, interactions between different components, various logical and physical elements. In this chapter, we will describe the logical system of the preference elicitation software developed to accompany the article in Chapter 4. In particular, we will illustrate the classes that constitute the various components of the system and the relationships between them. A class describes the attributes and the properties of a group of objects. An object is an instance of a class. Classes may inherit from other classes their actions and attributes. They can implement abstract methods and add new functionality. Associations between classes represent these behaviors.

A class is represented as follows: As we can see, the description of a class is divided into three sections, in the first there is its name, in the second its attributes and in the third its methods or behaviors. Attributes and methods can be either private (-) to the class itself, protected (#) to the class and its children, or public (+) to every other class.

In the example presented here there is a class named Class with three attributes: a public attribute named d of type Double, a private attribute named i of type Integer and a protected attribute named b of type Boolean. Moreover, Class has three methods:

• a method equals which takes an element of the class Class as input, compares it to the object on which this method is called and returns True if they are the same objects, False otherwise. The implementation of the method itself determine the meaning of similarity. • a method toString which does not take any input and returns the String corresponding to the current object. This value is often used for visualization purposes. • a method hashCode which does not take any input and produces an Integer value associated to the current object. This value is often used by the method equals since same objects must return the same hash value.

We described these three methods because they are basic methods that are automatically inherited by all classes. In fact, every class is an implicit child of a more general Object class. If not specified these methods return the default mechanism that can lead to unexpected results. Although specified in our code, we decided to omit these methods from the uml diagrams as a matter of the clarity of the figure.

Preference Representation

Figure 5.1 describes the basic elements of our elicitation software. The two basic elements are represented by the Alternative and Voter objects. A Preference is a list of alternatives in which the order represents the preference order. Multiple alternatives can have the same rank but an alternative cannot be associated to multiple ranks, i.e. it represents a linear order. Methods allow, for example, to know the alternative in a given rank or, conversely, to know the rank of a given alternative. A StrictPreference is an extension of the Preference object. This means that it inherits all of its behaviors and attributes but can redefine a given mechanism. In particular, StrictPreference does not allow two alternatives to have the same rank, i.e. it represents a strict order. A VoterStrictPreference links a Voter to her StrictPreference. A PrefGraph is a graph of preferences that can be added or modified. Specifically, each node represents an alternative, and an arc from a node a to a node b means that the alternative a is preferred over the alternative b. A VoterPartialPreference links a Voter to her PrefGraph.

Knowledge Representation

Figure 5.2 describes our approach to the representation of knowledge. We defined Preference-Knowledge as an interface, i.e. a completely abstract entity that define the structure that concrete objects must implement. An instance of PreferenceKnowledge must implements, among others, methods to return the alternatives, the voters, the profile and the constraints on the weights associated to rank positions. A possible implementation is given by UpdateablePreferenceKnowledge which keeps, as attributes, a partial profile and the constraints on weights and allows you to modify them. The ConstraintsOnWeights are equations relating the difference between the weights of two consecutive pairs of ranks. It provides method to add constraints and to return an optimal set of weights that satisfies the constraints. Those weights are represented by PSR-Weights which is a list of rational numbers associated to the Positional Scoring Rule. Since in our framework we assume the convexity of weights the satisfaction of this condition is automatically checked when creating a new instance of this class. Finally, in the diagram we can see an Oracle class. This represents "true" knowledge, which exists but is unknown to us and which we try to elicit by asking questions. It contains the set of alternatives, the preferences of the chair-which are the weights of the scoring rule-and the preferences of the voters-which is the profile. During our elicitation procedure we ask questions to this entity.

Questions Representation

Figure 5.3 shows the diagram related to the questions implementation. A Question can be either a question to the chair, about their preferences on the voting rule, or a question to one of the voters, about their preferences over the alternatives. This is represented by the use of an enumeration QuestionType that admits only two values: VOTER_QUESTION and COMMITTEE_ QUESTION. The method getType() of Question returns one of those two values. A Question-Voter is a comparison query relating two alternatives a and b, where getPositiveInformation() returns the VoterPreferenceInformation (see Figure 5.4) associated to that specific voter and the alternative a and b. Conversely, getNegativeInformation() returns the information regarding the alternative b and a. In other words, the first method returns the information when the answer to the question "a ≻ b?" is yes, thus a is preferred to b, and the second method that when the answer is no, thus b ≻ a. A QuestionCommittee tries to improve the knowledge about the scoring rule by refining the multiplier λ in the constraint w r -w r+1 ≥ λ(w r+1 -w r+2 ) for some r ∈ {1, . . . , m -2}. Given a λ and a rank defined by an elicitation strategy, getPositiveInformation() returns the response to the following question "w r -w r+1 ≥ λ(w r+1 -w r+2 )?". The complementary method, getNegativeInformation(), returns the information of the opposite question "w r -w r+1 ≤ λ(w r+1 -w r+2 )?". Positive and negative information is used by the elicitation strategies for the choice of the next question to ask. In particular, the Pessimistic strategy considers, for each potential question, the information in case of positive and negative answer and picks the question that leads to minimal regret in the worst case. This is described in Figure 5.6, in particular in the class diagram of MmrLottery.

Preference Information

Regret Computation

Figure 5.5 is the diagram representing the procedure described in Section 4.3. The Pairwise-MaxRegret is the building block of the regret computation. Given two alternatives, their ranks and the weights associated to ranks, it computes the regret of choosing the first alternative instead of the second one. This is used by the Regrets instance, which calculate the minimal max regret value and it can return all the alternatives associated to such value. A small constant epsilon is introduced to express the granularity of this similarity. In fact, we may want to consider two weights equals if, for example, they are equal up to the third decimal place. Re-gretComputer is the class that handles the proper calling of the methods specified by the classes aforementioned. For example by providing the pairwise maximum regret computation with the worst-case scenario: the worst completion of profile and scoring vector.

Strategies

Figure 5.6 describe our design of elicitation strategies. A Strategy is an interface that specify two methods: setKnowledge that sets and updates the knowledge collected so far, and nextQuestion that returns the next question to ask. Every strategy, i.e. every implementation of Strategy, must define those two methods. We created an enumeration for the StrategyType based on the different strategies we implemented and tested. In particular, the ones discussed in Section 4.4 are StrategyByMmr that, depending on the parameters with which it is invoked, corresponds to Pessimistic, Extended pessimistic or Two Phases, StrategyElitist that corresponds to Elitist and StrategyRandom that corresponds to Random. Please see Section 4.4 for a detailed explanation of their behaviors and performances. From a design point of view, each strategy defines the interface methods and it makes use of a StrategyHelper for all those functions common to each strategy. For example, to get all the pairs of alternatives whose order is already known and therefore it does not make sense to ask about; or to find the voters to whom we can still ask questions and, eventually,all those possible questions. Finally, StrategyFactory is an object that handles the creation of the desired strategy without disclosing to the user the strategy's creation logic.

The java package containing all those classes and also the UML diagrams can be found at administration, associations, companies. On their website it is possible to find all the citizens lists -party lists that are not affiliated to any national political party -that used MJ to rank their candidates during the local elections of 2020. In two cases, Bordeaux et Annecy, the candidate selected using MJ was then elected as a mayor.

In particular, LaPrimaire.org [LaPrimaire.org, 2016] is a french political initiative whose goal is to select an independent candidate for the french presidential election using MJ as voting rule. The association Democratech implemented the platform for the first time in 2016 in view of the 2017 presidential elections. The number of voters who participated in the election was 10676 during the first round, and 32685 during the second round.

The procedure that they adopted consists of two rounds. In the first round each voter is asked to express her judgment, using MJ, on five random candidates. At the end of this phase the five candidates with the highest medians are considered the finalists who qualify for the second round. In the second round each voter is asked to express her judgment, using MJ, on all the five finalists. The candidate with the best median at the end of this phase is selected as representative for the presidential election.

In this paper we analyze this elicitation process of voters preferences. In particular, we investigate the consequences of randomness when asking the voters to judge candidates. We evaluate the cost of this procedure -which can be quantified as number of questions per voter -and its fairness for candidates -which reflects the idea that a potential winner should not loose for lack of information.

Related work

One of the earliest uses of the median as an aggregator in voting theory can be identified in the middlemost method proposed by Galton [1907a,b]. In particular, in situations where a group of people had to assess a damage, he suggested the median as the only method that does not suffer from over-or under-exaggerations.

We can consider the median grade as the highest level at which a candidate obtains the support of the majority of the voters. Starting for the highest grade δ we check if the majority of the voters assigned at least δ to some alternative. If this is not the case, we descend in the grading scale until such level δ * is found. The grade δ * is the median of grades associated to some alternative, and, since it is the first level we stopped at, it corresponds to the best possible median. This method was rediscovered several times and proposed under the name of Bucklin's rule [START_REF] Hoag | Proportional representation[END_REF], Majoritarian Compromise [START_REF] Sertel | Lecture notes on microeconomics[END_REF][START_REF] Sertel | The majoritarian compromise is majoritarian-optimal and subgameperfect implementable[END_REF] and q-approval fallback bargaining [START_REF] Brams | [END_REF]. Moreover, when the number of grades is equal to two (approve, disapprove) then it is reduced to Approval Voting.

More recently [START_REF] Bassett | Robust voting[END_REF] proposed the use of the median as voting rule for elections advocating for its robustness. Several studies on the use of the median have been conducted. In particular, [START_REF] Bassett | Rating skating[END_REF] and [START_REF] Gehrlein | On some limitations of the median voting rule[END_REF] study its manipulation. [START_REF] Bibliography | The median procedure in cluster analysis and social choice theory[END_REF] survey mathematical problems and properties related to the notion of median in the context of cluster analysis and social choice theory. [START_REF] Nehring | The median rule in judgement aggregation[END_REF] analyze the median rule in judgment aggregation and they define a weighted median rule that is equivalent to MJ except for the treatment of ties.

NOTATION

However, there is a significant concern that has never been analyzed when considering MJ. Asking voters to provide a grade for each of the candidates can have a high cognitive and communicative cost. In situations where the set of alternatives is very large, voters may not be able to assign a significant and informed grades. [START_REF] Conitzer | Communication complexity of common voting rules[END_REF] studied the complexity of communication of some of the most common voting rules. In these cases, elicitation strategies exist to retrieve the most relevant information. [START_REF] Konczak | Voting procedures with incomplete preferences[END_REF] introduced the notion of possible and necessary winners. This paved the way for procedures that attempted to find necessary winners by asking voters the fewest questions possible [START_REF] Kalech | Practical voting rules with partial information[END_REF]. Considering scoring rules, Lu and Boutilier [2011a] suggested the use of minimax regret as a guide to the elicitation procedure. [START_REF] Bachrach | Probabilistic possible winner determination[END_REF] proposed a probabilistic approach. Several authors studied the complexity of determining when to stop the elicitation process for some of the most common voting rules [START_REF] Conitzer | Eliciting single-peaked preferences using comparison queries[END_REF]Sandholm, 2002, Walsh, 2008]. However, to the best of our knowledge, there are no works on preferences elicitation considering MJ.

Very recently, [START_REF] Varloot | Level-strategyproof belief aggregation mechanisms[END_REF] considered a version of MJ under uncertainties in order to study its strategyproof properties. Their premise, however, is based on the fact that voters who are uncertain about the degree to assign to an alternative would instead assign to it a probability distribution. In other words, if a voter does not know whether to assign good or excellent to a certain alternative, then she may assign to it, for example, good with 1 3 of the probability and excellent with 2 3 of the probability. This approach requires the submission of even more information and is very far from our idea of incomplete knowledge.

Notation

Consider a finite set N = {i 1 , . . . , i n } of voters (or judges) and a finite set A = {j 1 , . . . , j m } of alternatives (or competitors). A common language △ = {δ 1 , δ 2 , . . . } is a set of strictly ordered grades, and the notation δ 1 ≥ δ 2 indicates that δ 1 is a better or equivalent grade than δ 2 . A profile P : A × N → △ is a m by n matrix of grades. Given any N ′ ⊆ N , the operator ρ : △ N ′ → △ |N ′ | defines an ordering function that given a vector of grades P j returns the vector ordered by decreasing grades.

Consider a set of alternatives S ⊆ A, we denote by P S ∈ △ S×N a restriction of the profile P to only the alternatives in S, P S ⊆ P . Note that when S = A then P S = P .

We let f maj : △ N → △, denote the majority-grade function that associates to a vector of grades

∅ ̸ = v ∈ △ N ′ , N ′ ⊆ N its median grade value: f maj (v) = ρ(v) ⌊ |v| 2 ⌋+1
. Note that in case |v| is even, two medians could be used, but, as in [START_REF] Balinski | Majority Judgment: Measuring, Ranking, and Electing[END_REF] definition, the lower grade is picked.

Given any S ⊆ A, the winner function F S maj : △ S×N → A is a function that given |S| alternatives and their median grade, selects the alternative with the highest median grade as winner. We can define it as F S maj (P S ) = argmax j∈S f maj (P S j ) assuming it is a singleton. For brevity, we will write F maj when considering S = A. To avoid adding further complexity to the notation, we describe only informally what happens in case multiple alternatives are tied for the highest median grade h, thus, when argmax j∈S f maj (P S j ) is not a singleton. In this case, ties are broken by removing one h grade from the vectors of grades of each tied alternative, recomputing the new median grade and repeating the process until one unique winner is found or there are no more grades to remove. When n is odd, this is equivalent to take the next element after the median, i.e. the one at index (⌊ n 2 ⌋ + 1) + 1. If there is still a tie we then look at the previous element before the median, i.e. the one at index (⌊ n 2 ⌋ + 1) -1, and keep alternating until the tie is broken or there are no more elements in the vector. When n is even the element before the median, i.e. the one at index ⌊ n 2 ⌋, is taken first and, if there is still a tie, then the element after the median is considered, i.e. the one at index ⌊ n 2 ⌋ + 2, and so on. If after applying the mechanism there are still ties we break them using an arbitrary ordering defined on all alternatives, e.g. lexicographical order.

Similarly to the winner function, given any x ∈ 1, m , we can define a more general selection function F S x : △ S×N → P * (A), where P * (A) is the powerset of A excluding the empty set, that selects exactly the x alternatives with the x highest median grades. Thus,

F S x (P S ) = F S maj (P S ) ∪ F S ′ maj (P S ′ ) ∪ • • • ∪ F S k-1 maj (P S k-1 ) where S ′ = S \ F S maj (P S ), S ′′ = S \ F S maj (P S ) \ F S ′ maj (P S ′ ) etc.

Incomplete knowledge

In order to analyze the elicitation procedure used by LaPrimaire.org, we need to adapt the notation just described to incomplete profiles. Let P be our knowledge about the profile P . The voters have full knowledge of their own judgments but we ignore them; our goal is to elicit them by questioning the voters starting from zero knowledge. We introduce an additional grade δ, and, given a language ∆, δ < δ, ∀δ ∈ ∆. The common language in the incomplete knowledge setting is then △ = △ ∪ δ. Voters cannot use this grade to express their judgment over an alternative and it does not count in the computation of the median grade as we will explain formally. We refer to the grades in △, the ones used by voters, as "defined" grades.

Let P ∈ △ A×N denote an incomplete profile, i.e. a matrix m × n of grades some of which are "undefined". The starting knowledge is represented by a matrix m × n of δ grades. Given k ∈ N, we define with K i ⊆ A a set of k alternatives that we ask the voter i ∈ N to evaluate.

After having asked every voter in N to judge k candidates, we obtain an incomplete profile P k , that is a matrix m × n of grades of which kn are "defined". Note that when k = m, the resulting profile P k corresponds to the complete profile P . Let C(P ) be the set of all completions of P obtained by substituting all δ grades with "defined" ones, note that P ∈ C(P ).

Let g : △ N → N ′ ⊆N △ N ′ be the function that given an incomplete vector of grades q ∈ △ N , thus q ⊆ N × △, returns the vector composed only of the "defined" grades.

The majority-grade for incomplete profile f maj : △ N → △ corresponds to f maj that only considers the "defined" grades in the computation of the median. Consider an incomplete grade vector P j and let P ′ j = g(P j ) be the partial vector of P j of only "defined" grades, then

f maj (P j ) =    f maj (P ′ j ) = ρ(P ′ j ) ⌊ |P ′ j | 2 ⌋+1 for P ′ j ̸ = ∅ δ otherwise
In a similar fashion, we can define F S maj (P ) = argmax j∈S f maj (P S j ) and, given a value x ∈ 1, m , the selection function of the x best alternatives is

F S x (P S ) = F S maj (P S ) ∪ F S ′ maj (P S ′ ) ∪ 6.3. REASONING ON INCOMPLETENESS • • • ∪ F S x-1 maj (P S x-1
) where

S ′ = S \ F S maj (P S ), S ′′ = S \ F S maj (P S ) \ F S ′ maj (P S ′
) etc. To summarize the elicitation process we want to investigate, starting with zero knowledge, each voter is asked to evaluate k candidates. Given the partial information at our disposal, we are able to define the "known" median grade for each alternative by applying f maj (P k j ), ∀j ∈ A. We can then use the selection function F k to select the k alternatives with the highest "known" median grades. We denote this set of alternatives with K = F k ⊆ A. The alternatives in K will be presented to all voters, who must provide a grade for each of them, thus obtaining a restriction of the complete profile to this subset of k alternatives. From here, we can use F K maj (P K ) to select the winning alternative of the restricted profile P K . Remark 6.1. Because we are interested into investigating MJ, we are going to use an alphabet with the same size of the one proposed by [START_REF] Balinski | Majority Judgment: Measuring, Ranking, and Electing[END_REF] which is composed of the following adjectives: To be Rejected, Inadequate, Mediocre, Average, Good, Very Good, Excellent. For brevity we are gonna rename those adjectives respectively from δ 1 , corresponding to To be Rejected, to δ 7 , corresponding to Excellent. Therefore, △ = {δ 1 , δ 2 , δ 3 , δ 4 , δ 5 , δ 6 , δ 7 }

Reasoning on incompleteness

Let us now consider the effects of incomplete knowledge on the selection of a winner. In particular, we want to prove that if we consider an incomplete profile and take the k alternatives with the highest median grade, with any k being between 1 and m-1, it is possible to miss the winner of one of its completion. This is important because in the elicitation process implemented by LaPrimaire.org, only the full grade vectors of the k alternatives with the highest median grade are considered. Clearly, if the winning alternative in the complete profile is in this set K ⊂ A, then she will also be the winner of the incomplete profile. This is because the voters will be asked to provide a grade for all those k alternatives, providing thus a restriction of the complete profile to only the alternatives in K. If a candidate is a winner for a complete profile, then she is also a winner for any of its restrictions that include her. Note that this is not true in case of multiple winners where ties that cannot be broken by tie-breaking procedures and for which arbitrary ordering is, therefore, necessary. In what follows we assume the absence of such ties. We want to show that it is possible for the winning alternative of the complete profile not to be included in this subset K of alternatives. Theorem 6.1. Given a set A of alternatives m ≥ 2, a set of voters N and a value k ∈ 1, m -1 , there exist a complete profile P and an incomplete profile P such that P ∈ C(P ) and F maj (P ) ⊈ F k (P ).

Proof. Consider the following complete profile P i 1 i 2 . . . i n j 1 δ 7 δ 7 . . . δ 7 j 2 δ 6 δ 6 . . . δ 6

. δ 6 δ 6 . . . δ 6 j m δ 6 δ 6 . . . δ 6 ,

REASONING ON INCOMPLETENESS

When k = m -1, the proof follows from the proof of Theorem 6.1. The set of the m -1 alternatives with the highest medians is K = {j 2 , j 3 , . . . , j m }. Thus, F maj (P ) = j 1 / ∈ K. For any other k < m -1 we can follow the same reasoning by building P k making sure that we never ask anyone the grade of j 1 . The grade vector of j 1 is P k j 1 = (δ, . . . , δ) and f maj (P k j 1 ) = δ. Two situations are now possible, either all voters grade the same k alternatives and their associated grade vectors are complete; or each voter evaluates a set of k different alternatives from A \ j 1 . In the first case we have exactly k alternatives whose majority grade is defined and they would form the set K. In the second case there are at least k alternatives with at least one "defined" grade and, thus, with a defined majority grade. Therefore f maj (P k j 1 ) = δ will be lower than at least k others and it will not be selected in K.

From Theorem 6.2, considering k = 1 we have that: Remark 6.3. Given a set A of alternatives m ≥ 2, a set of voters N and a value k ∈ 1, m -1 , there exist a complete profile P and an incomplete profile P k such that P ∈ C(P k ) and

F maj (P ) ̸ = F maj (P k ).
In the proofs of Theorems 6.1 and 6.2 we showed the existence of an incomplete profile whose k ∈ 1, m -1 best alternatives did not include the winner of one of its completions. To do so, we assumed that no questions were asked about an alternative j winner in the complete profile P . Although the theoretical result remains, how likely is this to happen in practice? Proposition 6.1. Given a set A of m alternatives, a set N of n voters, a value k ∈ 1, m -1 and considering an elicitation strategy in which each voter is asked independently to evaluate k alternatives picked equiprobably, the probability that an alternative j ∈ A is never asked about is (1 -k m ) n . Proof. To prove this let us first consider e i the event of asking a voter i ∈ N to grade the alternative j in k questions, and let us compute the probability P of this event to happen. There are m-1 k-1 ways to select k alternatives among m that include the alternative j. This is because once we select the alternative j we can still pick k -1 alternatives to ask the voter among the remaining m -1. Moreover, there are m k ways to select k alternatives among m with no constraints. Thus, the probability of asking a voter to grade the alternative j in k questions is:

P(e i ) = m-1 k-1 m k = (m-1)! (k-1)!(m-1-k+1)! m! k!(m-k)! = (m -1)! (k -1)!(m -k)! • k(k -1)!(m -k)! m(m -1)! = k m .
The probability that one voter is never questioned about an alternative is then:

P(e i ) = 1 -P(e i ) = 1 - k m .
Because questionings different voters are independent events, we can express the probability that no voter is asked to grade an alternative j as the product of the individual probabilities. Denoting this event with e j we have that:

P(e j ) = P(e i ) n = 1 - k m n .
This observation comes from the proof of Proposition 6.1. Given an alternative j ∈ A and a voter i ∈ N the probability that i is asked about j, thus that P k j (i) is defined, is k m . This gives us an approximation on the number of elements of the grade vector, because for each of the n elements, we have k m probability that the element is defined. The value found in Proposition 6.1 is very low to occur in real examples, if, for example, we consider k = 3, n = m = 10 the probability that none is asked to grade the winner of the complete profile is 0.7 10 (which approximated is 0.0282%). However, this is also very restrictive. For an alternative j, winner of the complete profile, not to be the winner of the incomplete profile it suffices for her median to be smaller than the one of other k alternatives. We do not need the vector of the alternative considered to be empty, just to be misrepresented enough to have a median lower than k others.

Example 6.1. Consider the following profile P :

i 1 . . . i ⌊ n 2 ⌋+1 i ⌊ n 2 ⌋+2 . . . i n j 1 δ 7 . . . δ 7 δ 5 . . . δ 5 j 2 δ 6 . . . δ 6 δ 6 . . . δ 6 . δ 6 . . . δ 6 δ 6 . . . δ 6 j m δ 6 . . . δ 6 δ 6 . . . δ 6 .
Exactly ⌊ n 2 ⌋+1 voters grade the alternative j 1 with the highest grade δ 7 and the rest of the voters grade her δ 5 . All voters grade any other alternative δ 6 . The median grade of j 1 is f maj (P j 1 ) = δ 7 and the one of all the other alternatives is f maj (P x ) = δ 6 , ∀x ∈ A \ {j 1 }. Thus, j 1 is the winner of the profile P . For j 1 not to be the winner of any P k such that P ∈ C(P k ), it must be that f maj (j 1 ) = δ 5 . This happens when the incomplete grade vector of j 1 has a number of δ 5 grades at least as great as the number of δ 7 grades. Let us denote with q = |P k j 1 | the size of the incomplete grade vector of j 1 . Assume, for the sake of simplicity, that n and q are both even, although this reasoning can easily be adapted in case they are odd. An incomplete grade vector whose median is δ 5 , could be formed by q/2 δ 7 grades and q/2 δ 5 grades. To compute the probability of this vector to be formed, we must consider that there are

n 2 +1 q 2
ways of taking q/2 of the n 2 + 1 δ 7 grades of the complete vector. Moreover, there are

n 2 -1 q 2
ways of taking q/2 of the n 2 -1 δ 5 grades. If we consider no restrictions there are n q ways of taking a vector of q grades out of a vector of n elements. However, this is not the only vector whose median is δ 5 . In fact, we could have q/2 -1 δ 7 grades and q/2 + 1 δ 5 grades. If we iterate this reasoning on all the possible division of q we have that:

P = q/2 i=0 n 2 +1 q 2 -i • n 2 -1 q 2 +i n q 6.4. EXPERIMENTAL RESULTS
Because we know from Remark 6.4 that the average size of any grade vector is q = n • k m , we experimentally computed this probability with different values of n, m and k. Except when k is very close to m, and then we have almost the whole vector, we have that this probability is P ≈ 1 2 . Again, the profile considered here is rather peculiar and not of practical use. In the next section we investigate experimentally different profile distributions.

Experimental results

In our experiments we assume the existence of an Oracle who knows the complete profile, to whom we ask questions to elicit voters preferences. Specifically, we want to investigate what is the probability that starting from zero knowledge and asking k questions to each voter the winner of the complete profile is not within the k alternatives with the best medians of the incomplete profile. One of the first observations, also from the previous examples, is that given a number n of voters, this probability is highly dependent on how well each grade vector is represented. Because the average size of each vector is equal to q = n • k m , we are particularly interested in how the probability of "missing the winner" varies as a function of k/m. This, in fact, can be interpreted as the percentage of representation of the whole grade vector of n elements. By knowing this relation we therefore know the percentage of each vector, on average, that must be known in order to have a given probability of missing the winner. From this, we can infer important information, for example how many questions, k, to ask each voter so that the probability of missing the winner is less than a given threshold. Another measure we are interested in follows somewhat the opposite reasoning, given a number of questions k that I want to ask each voter, which can be fixed for reasons of cognitive and computational complexity, how large the electorate n must be for the vectors to be well represented?

In what follows we consider two different scenarios. In the first we assume that each grade vector is randomly selected from a uniform distribution, somewhat like in the Impartial Culture model used to evaluate ranking methods. In the second we consider that the grade vectors associated with the alternatives are distributed following the results of a real survey carried out during the French presidential election in 2022. The code to run the experiments is available at https://github.com/xoxor/elicitationMJ.

Profile uniformly distributed

For the first experiment we consider a profile where each voter has equal probability of assigning a grade δ ∈ ∆ to each alternative. Because we observed that with a low number of voters the probability of missing the winner P is very high, and with an high number of voters it is very low, we arbitrarily take n = 100 and m = 50. Moreover, in order to avoid the use of tie breaking mechanisms, that can be non resolute in case of ties that cannot be broken, we assume a profile P where there is an alternative j 1 whose median is always δ 7 and there are no other alternatives with the same median. Given such a profile P , we ask k questions to each voter for all k ∈ {1, m/2}. We consider this interval because we observed that already with k = m/2 the probability P is very close to 0. After the elicitation procedure is complete and the incomplete are often seen as unrepresentative of reality we decided to construct the grade vectors for each alternative following the grade distribution obtained in a real experiment conducted during the 2022 French presidential election. Given 12 political candidates, voters were asked to give a grade from To be rejected, corresponding to our δ 1 , to Excellent, corresponding to δ 7 , to each of the alternatives. The winner is determined using MJ.

The same experiment was carried out independently by the association Mieux Voter and the experimental study Un Autre Vote (UAV). The results, that can be found respectively at MieuxVoter [2022b] and [START_REF] Delemazure | Un autre vote résultats 2022[END_REF], are extremely similar. We chose to use the distribution obtained from the candidates in the UAV experiment, see Figure 6.2, for no particular reason. The code can be easily adapted to the results obtained from MieuxVoter. Note that in the UAV study, some voters were asked to judge the alternatives on a 5-grade scale and others to provide judgments on a 7-grade scale. We consider the profile obtained in the second case. Also, if you have followed the French presidential election you may notice that the distribution shown in Figure 6.2 is not an accurate portrait of the country's political situation. This is because the study did not capture a representative sample of the population. In their analysis of the results, [START_REF] Delemazure | Un autre vote résultats 2022[END_REF] try to correct this bias while acknowledging, nonetheless, that a discrepancy may still remain. However, this is not relevant to us for the purpose of our work. We take a voting profile and consider what happens when we do not know all the grades. We are not interested in the identity of the candidates nor in the purpose of the vote, taking the profile out of context it could represent voters opinions on a set of restaurants or movies. Our study focuses on considering a distribution of preferences in a realistic profile, a profile in which grades are not uniformly distributed but some alternatives are generally preferred over others.

The grade vector associated to the candidate Jean-Luc Mélenchon is composed for: 29% of Excellent grades, 22% of Very good, 16% of Good, 11% of Average, 7% of Mediocre, 5% of Inadequate and for 9% of To be rejected. Because it is the winner of the complete profile this alternative will be our j 0 and its complete grade vector will be formed following the same proportions: 29% of δ 7 , 22% of δ 6 , 16% of δ 5 , 11% of δ 4 , 7% of δ 3 , 5% of δ 2 and for 9% of δ 1 . We follow the same reasoning for the other grade vectors in order to have the complete profile.

Given m = 12 alternatives we fix a value of n and see what is the probability that j 0 is not in K for k from 1 to 5. Using the same reasoning as in the previous experiment we repeat this a total of 1, 000, 000 times and we average over the probability. After that we increase n and repeat the same experiment. We note that the probability decreases dramatically as n increases so, although we varied n from 10 to 1500, in Figure 6.3 we show the results only for a limited number of n values. Table 6.2 shows the data for the same values of n, the complete dataset can be found at https://github.com/xoxor/elicitationMJ. We see that when we have n = 50 voters by asking k = 3 questions per voter already we have an almost zero probability of not electing j 0 . This result is obtained by asking 2 questions per voter when n = 100 and 1 question when n = 500.

These results suggest that in small profiles with few voters this method can pose a serious risk of not electing the "correct" alternative unless many questions are asked. This risk, however, is almost absent for elections in which a large number of voters are involved. Although we cannot use these findings to reach a definite conclusion, working in this direction might help in the formulation of a more comprehensive result.

Conclusions

In this paper we analyzed a procedure proposed by the association Mieux Voter and used in a real life application by LaPrimaire.org for eliciting judgments of a set of voters over a set of alternatives. The procedure consists of randomly asking each voter to judge k candidates on the m available. The k alternatives with the best medians are then presented to all voters in a 6.5. CONCLUSIONS Figure 6.3: Average probability of missing the winner using a real case distribution of preferences, given m = 12 for n ∈ {10, 25, 50, 100, 250, 500} and k ∈ 1, 5 . to different SCRs. Considering n voters, the choice of q = 1 corresponds to the plurality rule BN: not true , q = ⌈ n 2 ⌉ is closely related, but not identical, to the majoritarian compromise and q = n represents a bargaining procedure called fall-back bargaining, which has been further analyzed by [START_REF] Kibris | Bargaining over a finite set of alternatives[END_REF] and [START_REF] Congar | A characterization of the maximin rule in the context of voting[END_REF]. We will refer to these rules as Brams and Kilgour (BK) compromises with threshold q.

As Özkal-Sanver and Sanver [2004] discuss, the concept of compromising is mostly understood as the trade off between the number of voters supporting an alternative (i.e., the quantity of support) and the distance of that alternative from the supporters' ideal alternative (i.e., the quality of support). This trade off, which is explicit for q-approval fall-back bargaining, is also the basis for several other SCRs such as the median voting rule proposed by [START_REF] Bassett | Robust voting[END_REF] and further analyzed by [START_REF] Gehrlein | On some limitations of the median voting rule[END_REF] or the Condorcet practical method described by [START_REF] Nurmi | Voting paradoxes and how to deal with them[END_REF]. [START_REF] Merlin | Compromise rules revisited[END_REF] identify and analyze a large class of compromise rules that explore this trade off.

One can argue that a collective choice per se implies a compromise. After all, except extreme cases such as dictatorships, a SCRs operates on the principle that all voters could fall back from their ideal position. Whether all voters effectively do fall back and whether this fall is "equal among voters" is the subject of our analysis. In what follows, we will present examples where they do not, which could be considered counter to the spirit of compromising. 1Consider the following example. At P , all BK compromises, except when q = n (i.e. fallback bargaining that would select b) and q = 1 (which would select both a and c), will ignore the single voter and will pick a as the collective outcome.

As a matter of fact, almost every SCR will ignore this "marginal minority" and choose a in this situation. While this choice is defensible on the grounds of qualified majoritarianism, it is questionable whether a can be qualified as a compromise. Observe that b receives unanimous support when each voter falls back one step from his ideal point. The question becomes more compelling when a remains the collective choice even if the ignored group is much larger. When q ∈ 1, n 2 -1 , all BK compromises pick {a, c}, and, when q = n 2 and q = n 2 + 1, all BK compromises pick {a}. Again, it does not appear as a compromise as almost half of voters reach their best alternative while the remaining half have to be contented with their worst one.

INTRODUCTION

Observe that all these SCRs impose to voters a willingness to compromise, but do not effectively ensure a compromise as the collective choice. In fact, the term "compromise" in this literature refers to procedural compromises that differ from outcome oriented compromises, a conceptual distinction that seems to be overlooked in the literature. This can also be viewed as a distinction between ex-ante and ex-post compromises, where the profile is the source of uncertainty.

To define an ex-post compromise, we adapt a concept of equal losses that considers allocation of continuous utilities. This principle is used for bargaining [START_REF] Chun | The equal-loss principle for bargaining problems[END_REF][START_REF] Chun | The lexicographic equal-loss solution[END_REF] and bankruptcy problems [START_REF] Herrero | The three musketeers: four classical solutions to bankruptcy problems[END_REF]. We introduce two definitions of compromise. In both of them, we pick a spread measure that determines how equally a given vector of numbers is distributed and we propose to make a collective choice where voters give up from their ideal points "as equally as possible". The difference between the two is that one, called egalitarian compromise, insists on equality at the expense of Pareto efficiency while the other, called Paretian compromise, is constrained to pick among the Pareto efficient alternatives. We show that Pareto efficient SCRs cannot ensure egalitarian compromises under any spread measure. We prove that several well-known SCRs such as Condorcet extensions, scoring rules, q-approval fall-back bargaining, all fail to be Paretian compromises under any spread measure.

We provide examples for which being a Paretian compromise would necessitate to pick an alternative that is, although Pareto optimal, ranked very low by all voters. Such alternative would never be picked by any of the above-mentioned SCRs.

We conclude that the equal-loss principle appears adequate for collective choice problems with at least three individuals, when egalitarianism, in the sense of conceding equally, is a major concern. Imagine a situation where the head of a laboratory needs to decide which project to fund and she asks for the preferences of the laboratory members. The workplace harmony is extremely important and, in order to avoid conflicts, the winning project must be equally supported by all members.

Consider now a situation with only two voters. As the vast literature on the ultimatum game [START_REF] Güth | More than thirty years of ultimatum bargaining experiments: Motives, variations, and a survey of the recent literature[END_REF] suggests, mutual consent is hard to obtain when one individual sees injustice at the levels of mutual losses. The equal-loss principle seems to be crucial in this new scenario.

Collective choice models with two individuals can be interpreted as bargaining or arbitration problems. While the bargaining interpretation necessitates an explicitly defined disagreement outcome [START_REF] Kibris | Bargaining over a finite set of alternatives[END_REF], the arbitration interpretation [START_REF] Sprumont | Intermediate preferences and rawlsian arbitration rules[END_REF] remains within the classical collective choice environment with no explicit disagreement outcome. In this paper, we consider the latter interpretation.

Arbitration rules are thoroughly discussed by [START_REF] Barberà | Compromising on compromise rules[END_REF]. As prominent examples, we have fallback bargaining proposed by [START_REF] Brams | [END_REF], the veto-rank and short listing procedures analysed by [START_REF] De Clippel | On the selection of arbitrators[END_REF] and the Pareto-and-veto rules analysed by [START_REF] Laslier | A solution to the two-person implementation problem[END_REF]. These models consider discrete alternatives which are not contained by the classical [START_REF] Nash | The bargaining problem[END_REF] bargaining environment with convex utilities. We make the same assumption. However, as [START_REF] Mariotti | Nash bargaining theory when the number of alternatives can be finite[END_REF] and [START_REF] Nagahisa | An axiomatization of the kalai-smorodinsky solution when the feasible sets can be finite[END_REF] illustrate, the two worlds can be interconnected, as we do for the equal-loss principle of [START_REF] Chun | The equal-loss principle for bargaining problems[END_REF] and [START_REF] Chun | The lexicographic equal-loss solution[END_REF]. The arbitration environment presents an instance where the equal-loss principle could matter and it is rather surprising to discover that most interesting SCRs used as arbitration solutions fail to be Paretian compromises.

The rest of the paper is organized as follows. Section 7.2 presents the basic notions and notation. Section 7.3 introduces egalitarian compromises and Paretian compromises, two concepts that turn out to be logically incompatible. Section 7.4 shows that with at least three individuals, many SCRs fail to pick a compromise. Section 7.5 considers the two-individual case, showing that most SCRs of the literature fail to pick compromises. Section 7.6 makes some concluding remarks.

Basic notions and notation

Consider a finite set N of individuals with #N = n ≥ 2 and a finite set A of alternatives with #A = m ≥ 3. We write L(A) for the set of linear orders over A. A generic element ≻ i of L(A) stands for a preference of i ∈ N . This implies that, given any x ̸ = y ∈ A, precisely one of x ≻ i y and y ≻ i x holds while x ≻ i x holds for no x ∈ A. Moreover, x ≻ i y and y ≻ i z implies x ≻ i z ∀x, y, z ∈ A.

A profile P : N → L(A) associates with each individual i ∈ N a preference

P (i) = ≻ i . A Social Choice Rule (SCR) is a mapping f : L(A) N → 2 A \ {∅}.
We write

r ≻ i (x) = #{y ∈ A | y ≻ i x} + 1 for the rank of x ∈ A at ≻ i ∈ L(A)
. We denote by λ ≻ i (x) = r ≻ i (x) -1 the loss in terms of ranks for i ∈ N with preference ≻ i , when x is elected instead of the best alternative for i. The mapping λ P : A → 0, m -1 N assigns to each x ∈ A the loss vector λ P (x) = (λ ≻ i (x)) i∈N induced by the election of x. The double brackets denote intervals in the integers.

We are interested in measuring the spread of loss vectors. To this end, we define a spread measure σ : 0, m -1 N → R + as a function that associates a spread value to every possible loss vector. We write Σ for the set of spread measures σ that satisfy, for every l ∈ 0, m -1 N , σ(l) = 0 ⇔ l i = l j ∀i, j ∈ N . Thus, the spread of l gets its lowest value 0 in case of perfect equality and only in this case. Note that this condition incorporates the minimal requirement to identify a spread measure and leads to the largest set of spread measures one could define. As discussed in Section 7.4.4, this flexibility has the advantage of making our results more general.

Given any distinct x, y ∈ A, we say that x Pareto dominates y at P ∈ L(A) N (or equivalently y is Pareto dominated by x at P ) iff x ≻ i y, ∀i ∈ N . We denote by PO(P ) = {x ∈ A | ∀y ∈ A \ {x}, ∃i ∈ N | x ≻ i y} the set of Pareto optimal alternatives at P . A SCR f is Paretian iff f (P ) ⊆ PO(P ) ∀P ∈ L(A) N .

Egalitarian versus Paretian compromises 7.3.1 Egalitarian compromises

We let argmin X (σ • λ P ) = {x ∈ X | ∀y ∈ X : σ(λ P (x)) ≤ σ(λ P (y))} denote the minimal elements of X ⊆ A according to (σ • λ P ). In other words, argmin X (σ • λ P ) denotes the alternatives in X whose loss vectors are the most equally distributed according to the spread measure σ.

EGALITARIAN VERSUS PARETIAN COMPROMISES

In what follows, we define some classes of SCRs that we are interested in analyzing.

Definition 7.1. A SCR f is an Egalitarian Compromise (EC) iff ∃σ ∈ Σ | ∀P ∈ L(A) N we have f (P ) ⊆ min A (σ • λ P ). Definition 7.2. A SCR f is Egalitarian Compromise Compatible (ECC) iff ∃σ ∈ Σ | ∀P ∈ L(A) N we have f (P ) ∩ min A (σ • λ P ) ̸ = ∅.
Under a SCR that is EC (resp., ECC), all (resp., some) winners are among the alternatives with most equally distributed losses. Clearly, EC is a subclass of ECC. Perhaps less obviously, being ECC (or EC) is incompatible with being Paretian. This will be deduced from the following proposition, which will also be useful to prove other theorems.

Proposition 7.1. For n ≥ 2, m ≥ 3, there exists a profile P ∈ L(A) N and an alternative a m such that ∀i ∈ N : r ≻ i (a m ) = m, and such that ∀σ ∈ Σ : min A (σ

• λ P ) = {a m }; hence, min A (σ • λ P ) ∩ PO(P ) = ∅.
Proof. Consider the following profile P :

1 a 1 a 2 . . . a m-1 a m n -1 a π (1) a π (2) . . . a π (m-1) a m ,
where π is the following permutation over 1, m -1 :

π(i) = i + 1 if i ∈ 1, m -2 1 if i = m -1 .
In P , a m is the only alternative such that r ≻ i (a m ) is independent of i; hence, σ(λ P (a)) > 0, ∀a ∈ A \ {a m }, ∀σ ∈ Σ. Thus, the set min A (σ • λ P ) consists of the sole element a m , and, because a m is Pareto dominated, min A (σ • λ P ) ∩ PO(P ) = ∅.

Our main result for Section 7.3.1 follows easily.

Theorem 7.1. For n ≥ 2, m ≥ 3, no Paretian SCR is ECC.

Proof. Proving this amounts to show that ∀σ ∈ Σ, ∃P ∈ L(A) N | PO(P ) ∩ min A (σ • λ P ) = ∅. Suffices to use Proposition 7.1, which asserts that there exists a profile P such that ∀σ ∈ Σ : min A (σ • λ P ) ∩ PO(P ) = ∅.

Paretian compromises

Having seen the tension for a SCR being Paretian and ECC, we investigate the consequences of inverting the order of priorities by insisting that at least some of the winning alternatives are Pareto optimal, and considering the most equally distributed loss vectors among those. We consider two classes of SCRs. Observe that min PO(P ) (σ • λ P ) denotes the set of Pareto optimal alternatives whose loss vectors are the most equally distributed according to the spread measure σ.

i = 1 a 2 . . . a m a 1 2 ≤ i ≤ m -2 a 1 . . . a m a i m -1 ≤ i ≤ n a 1 . . . a m a m-1
, where all alternatives except a m appear at least once in the last rank. Thus, for every σ ∈ Σ, we have σ(λ P (x)) > 0 ∀x ∈ A \ {a m } while σ(λ P (a m )) = 0. Moreover, a m ∈ PO(P ). Thus, min PO(P ) (σ • λ P ) = {a m } ∀σ ∈ Σ. On the other hand, s w (a 1 ; P ) = n -1, s w (a m ; P ) = n • w m-1 and as n > 1 1-w m-1 (or, equivalently, n -1 > nw m-1 ), we have s w (a 1 ; P ) > s w (a m ; P ), establishing a m / ∈ f w (P ), thus f w (P ) ∩ min PO(P ) (σ

• λ P ) = ∅ ∀σ ∈ Σ.

BK compromises

Given any k ∈ 1, m , we write n k (x, P ) = #{i ∈ N | r ≻ i (x) ≤ k} for the k-support that x gets at P , that is, the number of individuals for whom the rank of alternative x ∈ A is lower than or equal to k in the profile P ∈ L(A) N . Note that n k (x, P ) ∈ 1, n is non-decreasing on k and n m (x, P ) = n. For each q ∈ 1, n , we define ρ q (x, P ) = min{k ∈ 1, m | n k (x, P ) ≥ q} as the minimal rank k at which the k-support that x gets at P is at least q. We write ρ q (P ) = min x∈A {ρ q (x, P )} for the minimal rank k at which the k-support that some alternative gets at P is at least q. A BK compromise with threshold q is the SCR f q defined for each P ∈ L(A) N as f q (P ) = {x ∈ A | n ρq(P ) (x, P ) ≥ q}. We can also define a tie breaking version of the BK compromise where among the winners only the alternatives with the greatest support are selected: f ′ q (P ) = {x ∈ A | n ρq(P ) (x, P ) ≥ n ρq(P ) (y, P ), ∀y ∈ A} We first consider the BK compromise with threshold q = n, f n , which corresponds to the rule also known as fallback bargaining [START_REF] Brams | [END_REF]].

Theorem 7.7. Let n ≥ 3 and m ≥ 3. The BK compromise f n satisfies PC.

Proof. Define σ ∈ Σ as, ∀l ∈ 0, m-1 N : σ(l) = 1 iff ∃i, j ∈ N | l i ̸ = l j ; σ(l) = 0 otherwise. Considering any x ∈ f n (P ), let us show that x ∈ min PO(P ) (σ • λ P ). Because x ∈ f n (P ), x ∈ PO(P ), and therefore, suffices to show that ∀y ∈ PO(P ), σ(λ P (y)) ≥ σ(λ P (x)). Given the choice of σ, picking any y ∈ PO(P ) with y ̸ = x, suffices to show that σ(λ P (y)) = 1, equivalently, that ∃i, j ∈ N | r ≻ i (y) ̸ = r ≻ j (y). Because x ∈ f n (P ), ρ n (P ) = ρ n (x, P ) = max N r ≻ i (x). It follows from ρ n (P ) = min z∈A {ρ n (z, P )} that ρ n (y, P ) ≥ ρ n (x, P ), thus, ∃i ∈ N | r ≻ i (y) ≥ ρ n (P ). Also, y ∈ PO(P ) implies that ∃j ∈ N | r ≻ j (y) < r ≻ j (x), thus ∃j ∈ N | r ≻ j (y) < ρ n (P ). Therefore, r ≻ i (y) ̸ = r ≻ j (y).

Theorem 7.8. Let n ≥ 3 and m ≥ 3. The BK compromise f n fails ECC.

Proof. As f n is Paretian, the proof comes straightforward from Theorem 7.1. Theorem 7.9. Let n ≥ 3 and m ≥ 3. A BK compromise f q with threshold q ∈ 1, n -1 is neither ECC nor PCC.

Proof. Consider the following profile P (also used in the proof of Theorem 7.3), where the dots represent the sequence a 4 to a m : or PCC except for the antiplurality rule (Theorems 7.5 and 7.6), BK compromises are neither ECC or PCC (Theorems 7.8 and 7.9) except for fallback bargaining that is PC (Theorem 7.7).

Our impossibility results are stated for the set of spread measures Σ, but they prevail for any subset of Σ. As Σ is the largest set of sensible spread measures, they are valid for any specific concept of equity one might pick. On the other hand, our possibility results on fallback bargaining and antiplurality are not propagated to subsets of Σ. In fact, as soon as a reasonably mild restriction on Σ is imposed, both rules are no longer PCC (Theorem 7.10). With two individuals and a similar restriction on Σ, all well-known two-person SCRs of the literature, namely, fallback bargaining, Pareto and veto rules, short listing and veto rank, fail to pick expost compromises (Theorem 7.11).

The exclusion of the equal-loss principle by almost all SCRs of the literature leads to ask whether the principle is uninteresting in a discrete social choice context. This seems to be the case for voting situations where the number of voters exceeds the number of candidates and usually every candidate is ranked last by at least one voter. In these cases, the main concern is about the support of alternatives rather than equality. On the other hand, two-person collective choice problems are typically interpreted as arbitration or bargaining situations where mutual consent is a critical element in reaching a solution. Thus, the equal-loss principle appears to be valid for two-person collective choice problems and our analysis raises the question of designing new discrete arbitration rules compatible with the equal-loss principle.

We also want to mention that different notions of compromise can be conceived. [START_REF] Börgers | Undominated strategies and coordination in normalform games[END_REF] defines as compromises all Pareto-optimal alternatives that are not the top choice of any individual. In this context a compromise does not always exist. This is also a possible approach to adopt and we thank an anonymous reviewer for this remark.

We close by noting, as one anonymous reviewer to whom we are grateful remarked, that the tension between equity and efficiency is not new in economics. In our paper we try to cast this tension in a context where it does not seem to have been considered yet. We certainly hope that this is only the beginning of a discussion that may lead to further progress in the future. In particular, viewing a compromise through the equal loss principle can be especially interesting in richer informational settings with a status-quo point, cardinal individual preferences or a continuum of alternatives. CHAPTER 8

CONCLUSION

Throughout this manuscript, we have addressed several problems related to the field of social choice. In particular, we focused on two scenarios. Considering a classical model in which the preferences of a set of voters over a set of alternatives are known, we defined two classes of voting rules able to reflect a notion of compromise in which egalitarianism, in the sense of conceding equally, is a major concern. Moreover, we stepped back from this standard perspective in which preferences are assumed to be known from the beginning and investigated the problem of preference elicitation in different settings. In what follows we describe the results of our works in more detail.

Summary of the contributions

Simultaneous Elicitation of PSR and Agent Preferences In Chapter 4 we studied the second of the aforementioned scenarios. Considering positional scoring rules with convex weights, we developed methods for preference elicitation under uncertainty of both the voting rule and the agent preferences. Assuming that those preferences are initially unknown to the system, the goal of the procedures is to incrementally reveal them through questioning and quickly acquire the most relevant information. We proposed the use of minimax regret both as a means of robust winner determination and as a guide to the process of simultaneous elicitation of preferences and voting rule. This serves mainly for two reasons, first to give an indication of the relevance of potential questions, but also to give us a measure of how many questions it takes to get to a low regret or to stop the elicitation process once the regret reaches a certain threshold. We presented incremental elicitation methods that at each step of the elicitation question either one of the agents or the chair, and we discussed several heuristics to choose questions quickly reduce the regret. Answers to questions are encoded as constraints: questions to the agents are comparisons between pairs of alternatives, while questions to the chair ask to select a winner out of a synthetic profile. We compared the effectiveness of several questioning strategies based on the current knowledge of the rule and preferences. Our experimental results suggest that regret-based elicitation is effective and allows to quickly reduce worst-case regret significantly. In particular:

• we defined different elicitation strategies that achieve good results within reasonable computation time and we compared their performances;

• we showed that with our elicitation methods, in particular with the Pessimistic strategy, it is possible to reach low regret with a reasonable number of questions;

PART III, CHAPTER 8. CONCLUSION

• we analyzed the strategies on both real data and randomly generated profiles and found that low degree of similarity among preferences (as in impartial culture) is a more challenging setting than less varied profiles (as real preferences profiles);

• we showed that for the class of rules considered, asking a few questions to the chair suffice to reach low regret.

Moreover, as a part of our contribution, we proposed a novel mechanism for eliciting a voting rule by translating abstract questions about weights to a choice of the winning alternative on a concrete profile.

Preference Elicitation Under Majority Judgment In Chapter 6 we analyzed the preference elicitation mechanism used in a real voting scenario by the french political initiative LaPrimaire.org. In fact, they proposed a voting procedure to select an independent candidate for the french presidential election using MJ as voting rule. The procedure that they adopted consists of two rounds. In the first round each voter is asked to express her judgment, using MJ, on five random candidates. At the end of this phase the five candidates with the highest medians are considered the finalists who qualify for the second round. In the second round each voter is asked to express her judgment, using MJ, on all the five finalists. The candidate with the best median at the end of this phase is selected as representative for the presidential election. We investigated the consequences of randomness in the described preference elicitation procedure. We analyzed its cost, quantified as number of questions per voter, and its fairness, stating that a winner for the complete profile should not loose for lack of information. In particular, we have proven that this latter case it is possible. Given a complete profile it is possible to find an incomplete profile (such that a possible completion is equal to the considered profile) with a different winner. We also showed that the probability of this happening depends on the profile considered and we showed, as an extreme example, a case for which this probability is almost 1/2. By denoting this as the probability of "missing the winner", we computed the average size of a grade vector after a given number of questions to each voter and studied what percentage of this vector we need to know so that this probability is low. Considering randomly generated vector of grades following a uniform distribution, we have found that when knowing only the 20% of the vector (thus after having asked 10 questions) the probability of missing the winner is close to zero. We have also considered a profile created following the grade distribution of a real voting scenario and analyzed the probability of missing the winner as a function of the number of voters. We have found that this greatly decreases as the number of voters increases, suggesting that this method is more suitable for elections with large numbers of voters but less appropriate for small profiles.

Compromising as an Equal-Loss Principle In Chapter 7 we analyzed the concept on compromise in the literature. We observed that almost all the voting rules that are known as compromise rules impose over individuals a willingness to compromise but they do not ensure an outcome where everyone has effectively compromised. We revisited the notion of compromise from an equal-loss perspective, favoring an outcome where every voter concedes as equally as possible, and we proposed some class of rules reflecting this concept. We denoted a voting ), if all (resp., some) winners are among the Pareto optimal alternatives with the most equally distributed losses. We proved that no Condorcet procedure is ECC or PCC, no scoring rule is ECC or PCC except for the antiplurality rule, BK compromises are neither ECC or PCC except for fallback bargaining that is PC. We showed that, although our results are stated for a broad set of spread measures Σ, they prevail for any subset of Σ. Moreover, as soon as a we consider such subset where a reasonably mild restriction on Σ is imposed, fallback bargaining and antiplurality are no longer PCC. We also considered a specific voting scenario with two individuals and a similar restriction on Σ, and we proved that all well-known two-person voting rules of the literature, namely, fallback bargaining, Pareto and veto rules, short listing and veto rank, are not PCC.

Future work

There are many interesting directions for future works for each of the problems considered.

Regarding the simultaneous elicitation of voting rule and agent preferences, one could develop more strategies with different heuristics to compare to the ones we proposed. For example, less computationally costly strategies would allow testing of larger datasets, with more voters and more alternatives. It would also be interesting to expand the elicitation of the voting rules other than scoring rules or to relax the convexity constraint. Furthermore, we think that transforming questions into example profiles is a very interesting concept that is not explored much in the literature and could be applied in different settings.

The chapter on the analysis of the elicitation procedure using MJ is not yet fully mature so there are many ideas for possible extensions. One could investigate, for example, the manipulability of the elicitation process itself. In particular, how the party in charge of questioning the voters can manipulate the outcome by directing questions to specific voters. Another direction may involve the explainability of this process. Voters may find difficult to believe that judging only one person gives a good approximation of the result that would be obtained by asking for the full profile.

Finally, when considering the concept of compromise, different notions of compromise can be conceived. One approach might consider choosing alternatives that are neither the best nor the worst of any voter. It all depends on the idea of justice one wants to represent and the priorities in the scenario under consideration. Furthermore, the trade-off between equity and efficiency can be explored in other, and richer, settings.

To conclude, we like to think that each of our contributions is merely the beginning of a long series of future expansions.

Introduction

La prise de décision collective est un processus dans lequel les préférences individuelles sont agrégées pour former un choix collectif unique. Cette définition large permet à de nombreux cas, qui semblent très différents les uns des autres, d'entrer dans cette catégorie. Parmi les exemples, citons les problèmes d'allocation équitable-qui traite du problème de la répartition équitable de certaines ressources entre des individus qui ont des intérêts différents, par exemple l'allocation de maisons, la création d'un horaire de travail, etc.-problèmes d'appariement-qui traite du problème de l'appariement d'individus de deux groupes distincts en tenant compte de leurs préférences, par exemple, des étudiants aux écoles, des locataires aux maisons etc.-et problèmes d'agrégation de jugements-qui tentent de regrouper les croyances de différents individus en un jugement qui reflète la société en tant qu'entité unique. Dans cette thèse, nous nous concentrerons sur un autre exemple de prise de décision collective : le vote. Étant donné un ensemble d'individus qui expriment leurs préférences sur un ensemble donné de candidats, comment choisir le meilleur candidat pour le groupe ? Il s'agit d'un dilemme très ancien qui a été affronté de multiples fois au cours des siècles et que nous allons aborder tout au long de ce manuscrit. Comme nous allons le voir, la réponse dépend de nombreux facteurs, tels que les informations dont nous disposons-connaissons-nous les préférences de tous les électeurs par rapport à tous les candidats ?-et les propriétés que nous voulons que le résultat satisfasse-qu'entendons-nous par le meilleur candidat ? Qui décide de ce qui est le meilleur ? Une méthodologie importante dans notre travail consiste à définir les propriétés souhaitables que nous voulons qu'une règle satisfasse. Cela nous permet, d'une part, de diviser les règles d'agrégation en classes de méthodes satisfaisant les mêmes propriétés, et, d'autre part, de faire le processus inverse : partir d'une méthode déjà définie pour aider le décideur à comprendre ses propriétés. Le manque d'information et l'aide aux décideurs sont deux des thèmes explorés au cours de ce travail.

Nous avons mentionné l'analyse des processus d'agrégation par la définition de desiderata, mais cette approche axiomatique est très récente et n'a commencé qu'après la publication de la thèse de doctorat de Kenneth [START_REF] Arrow | Social Choice and Individual Values[END_REF]. La théorie des processus de prise de décision collective est cependant beaucoup plus ancienne et, comme l'a écrit [START_REF] Mclean | The borda and condorcet principles: Three medieval applications[END_REF], "la théorie du vote est connue pour avoir été découverte trois fois et perdue deux fois". En partant des premières traces des processus de décision, nous décrivons le début et l'évolution de la théorie du choix social.

Questions de recherche et contributions. En étudiant l'histoire des méthodes d'agrégation, nous avons réalisé qu'à partir d'un large éventail de procédures, nous pouvons identifier des classes dont les éléments satisfont des propriétés communes. Étant donné une méthode, nous pouvons analyser les axiomes qu'elle satisfait. L'intérêt de cette démarche est que nous pouvons aussi faire l'inverse : étant donné certaines préférences sur les propriétés que la règle doit respecter, nous pouvons aider le décideur à définir la méthode d'agrégation qu'il souhaite. C'est précisément l'un des points sur lesquels nous allons nous concentrer :

• comment pouvons-nous aider le décideur à définir formellement une règle électorale sur la base de préférences génériques sur ses propriétés ?

Dans Chapter 4, nous étudions une situation dans laquelle un comité de non-experts doit décider comment agréger les préférences des électeurs. Supposons que le comité attribue un score à chaque position dans l'ordre des préférences des électeurs. Ainsi, par exemple, le premier classé obtient 10 points, le second 5, etc. Imaginez maintenant que le comité souhaite que le score du meilleur choix soit "beaucoup plus élevé" que celui du troisième meilleur choix. Comment traduire ce "beaucoup plus" en une règle de vote ? Qu'est-ce que cela signifie exactement ? Dans cette thèse, nous nous concentrons sur une classe particulière de règles, les Règles de notation positionnelle -que nous décrivons en détail dans Chapter 2 -et développons une méthode pour poser des questions au comité en termes de choix des gagnants dans un exemple de profil. Ainsi, nous transformons une question complexe impliquant des différences de poids entre des positions consécutives en des questions auxquelles un comité humain peut plus facilement répondre, telles que "qui devrait gagner dans ce profil" ? De la réponse à cette question, nous déduisons la réponse à la question initiale. Un autre problème important lors du choix d'une règle de vote est son coût. C'est un point que nous retrouvons également dans notre première question de recherche. Dans ce cas, il est représenté par le coût cognitif pour les non-experts de formaliser une règle de vote sur la base de certaines préférences génériques. Mais, comme nous le savons, le coût est également lié aux électeurs lorsqu'ils doivent ordonner un grand ensemble de préférences, et au calcul de la transmission de toutes ces informations. Cette prise de conscience nous amène à étudier les stratégies d'élicitation des préférences des électeurs :

• comment pouvons-nous acquérir les informations les plus pertinentes au moindre coût ? Nous étudions cette question pour différentes règles de vote (règles de notation positionnelle et jugement majoritaire) dans Chapters 4 and 6. En particulier, dans Chapter 4, nous combinons cette question de recherche avec la première et nous essayons de comprendre si, dans un contexte d'information nulle, l'imbrication de l'élicitation des préférences des électeurs et de l'élicitation de la règle de vote donne de meilleurs résultats qu'une approche plus linéaire. Dans Chapter 6, nous étudions des scénarios concrets tirés de situations de vote réelles, dans lesquels les préférences des électeurs sont obtenues en posant un nombre donné de questions aléatoires aux électeurs. Entre autres, nous cherchons comment identifier le nombre minimum de questions à poser pour que la probabilité d'obtenir le gagnant, en utilisant la règle du jugement majoritaire, soit élevée.

Nous avons commencé à nous demander comment différentes situations pouvaient justifier l'utilisation de différentes règles de vote qui cherchent à atteindre le même objectif. Dans la littérature, diverses notions de compromis ont été proposées, et avec elles diverses règles de vote qui tentent plus ou moins de mettre en oeuvre ces définitions. Lorsque nous parlons de compromis, ce que nous entendons dépend beaucoup du contexte. Lorsque nous voulons décider où dîner, nous sommes probablement d'accord pour que les électeurs essaient de trouver un terrain d'entente, même si le résultat ne s'avère pas être un compromis. C'est le cas avec certaines règles de vote dont nous parlerons plus tard, comme le Fallback Bargaining, où il peut arriver que le résultat soit le meilleur choix pour certains électeurs, mais qu'il déplaise à beaucoup d'autres. Cependant, lorsque nous avons affaire à des contextes où l'égalitarisme -que nous interpréterons comme le fait que tout le monde concède également -est une préoccupation majeure, cette notion de compromis n'est plus acceptable. Sur ces bases, nous développons les fondements de notre concept de compromis :

• comment pouvons-nous définir la notion de compromis où chaque électeur concède de manière aussi égale que possible ? Dans Chapter 3, en utilisant la même approche que dans cette introduction, nous fouillerons dans le passé pour positionner notre travail. En particulier, dans Section 3.1, en partant de la signification du compromis, nous retraçons son utilisation à travers l'histoire. Nous analysons les définitions qui ont été données des règles de compromis dans la théorie du choix social et soulignons comment certaines d'entre elles ne représentent pas certaines idées du compromis. Nous montrons comment notre approche s'inscrit dans cette littérature. Constatant que la règle du jugement majoritaire est considérée comme une forme de compromis dans la littérature, nous approfondirons cette règle dans Section 3.2. Nous étudierons son introduction, ses utilisations et aussi ses critiques. Comme dernier sujet de ce chapitre, nous couvrons dans Section 3.3 un autre aspect important de cette thèse : l'élicitation des préférences. En effet, si jusqu'à présent on a supposé connaître les préférences des électeurs et la procédure de vote, cela ne peut être considéré comme acquis. L'élicitation des préférences est un problème bien étudié et nous décrirons les différentes approches par lesquelles il a été abordé dans la littérature. En outre, nous décrirons comment il a été abordé dans différents domaines, notamment dans la littérature sur l'aide à la décision et l'apprentissage automatique, et les similitudes avec notre approche.

Part II inclut nos contributions. Plus précisément, Chapter 4 est un article publié dans une conférence internationale [START_REF] Napolitano | Simultaneous elicitation of scoring rule and agent preferences for robust winner determination[END_REF] et Chapter 7 est un article publié dans une revue [START_REF] Cailloux | Compromising as an equal loss principle[END_REF]. Chapter 5 accompagne Chapter 4 en décrivant le code fourni à l'appui de la contribution. Enfin, Chapter 6 est une contribution originale, non encore publiée, dont le but est d'étudier les conséquences du processus d'élicitation dans une situation de vote utilisant le jugement majoritaire.

Pour conclure, Chapter 8 fournit un résumé des contributions de cette thèse et quelques perspectives pour les directions futures.

Contributions 8.2 Simultaneous Elicitation of PSR and Agent Preferences

Le cadre classique du choix social suppose une information complète sur les ordres de préférence de tous les électeurs, et sur le mécanisme de vote lui-même. Mais dans quelle mesure cette hypothèse est-elle raisonnable ? Si l'ensemble des alternatives est très vaste, il n'est pas raisonnable d'attendre des électeurs qu'ils fournissent un ordre complet de leurs préférences. D'abord d'un point de vue cognitif : des études de psychologie expérimentale décrivent comment, dans de nombreuses situations, nos préférences ne sont pas prédéfinies, mais que nous les construisons seulement au moment où nous devons les exprimer [START_REF] Lichtenstein | The Construction of Preference[END_REF]. Demander aux électeurs d'exprimer leurs préférences lorsque l'éventail de choix est très large peut entraîner divers problèmes, tels que la confusion et une faible participation. Deuxièmement, mais non moins important, cela représente un énorme coût de communication. [START_REF] Conitzer | Communication complexity of common voting rules[END_REF] ont étudié la complexité de communication de certaines des règles de vote les plus courantes et, pour chacune d'entre elles, ont fourni une limite supérieure et inférieure sur le nombre de bits d'information que les électeurs doivent communiquer avant que la règle puisse sélectionner un gagnant. D'autres mesures existent, comme le nombre de questions auxquelles les électeurs doivent répondre avant que la règle puisse déterminer un gagnant. Cette approche a été utilisée par [START_REF] Procaccia | A note on the query complexity of the condorcet winner problem[END_REF] pour déterminer le nombre minimum de questions permettant de sélectionner le gagnant de Condorcet. Dans les élections présidentielles, par exemple, nous avons tendance à préférer la précision au coût, mais ce n'est pas vrai dans toutes les applications. Lorsqu'il s'agit de choisir un restaurant pour dîner avec des amis, nous nous contenterons probablement d'un gagnant approximatif plutôt que de devoir passer toute la soirée à classer tous les restaurants de la ville.

Cette observation a motivé plusieurs travaux supposant des ordres de préférence partiels : un des premiers travaux est celui de Conitzer and Sandholm [2005] qui a étudié la complexité de la communication lors de l'utilisation de différentes règles de vote ; [START_REF] Konczak | Voting procedures with incomplete preferences[END_REF] a étudié le calcul des gagnants possibles et nécessaires pour différentes règles de vote ; [START_REF] Xia | Determining possible and necessary winners under common voting rules given partial orders[END_REF] ont ensuite montré que, si l'identification d'un co-gagnant nécessaire dans les règles de notation est polynomiale, la détermination des co-gagnants possibles est NP-dure ; D'autres résultats de complexité ont été donnés par [START_REF] Walsh | Uncertainty in preference elicitation and aggregation[END_REF] et [START_REF] Pini | Incompleteness and incomparability in preference aggregation[END_REF].

Puisque dans de nombreuses situations pratiques, il y aurait trop de gagnants possibles mais pas de gagnants nécessaires, plusieurs travaux ont abordé le problème de l'élicitation des préférences des agents en utilisant une variété d'approches (regret minimax, méthodes bayésiennes, etc.) dans le but de converger vers un gagnant nécessaire : [START_REF] Naamani-Dery | Preference elicitation for group decisions using the borda voting rule[END_REF][START_REF] Kalech | Practical voting rules with partial information[END_REF], Lu and Boutilier, 2011a[START_REF] Pini | Aggregating partially ordered preferences[END_REF][START_REF] Benabbou | Incremental preference elicitation in multi-attribute domains for choice and ranking with the borda count[END_REF][START_REF] Dey | Preference elicitation for single crossing domain[END_REF]. Parmi ceux-ci, [START_REF] Walsh | Complexity of terminating preference elicitation[END_REF] et [START_REF] Conitzer | Eliciting single-peaked preferences using comparison queries[END_REF] ont analysé quand arrêter le processus d'élicitation.

Une deuxième préoccupation concerne la capacité de la personne ou l'organisation qui supervise le processus de vote à fournir une définition précise de la règle de vote, ce qui suggère l'assouplissement de la deuxième hypothèse. En effet, il est souvent difficile pour des nonexperts de formaliser une règle de vote sur la base de quelques préférences génériques sur une méthode d'agrégation souhaitée. Nous donnons ici deux exemples de telles situations.

Considérons, comme premier exemple, une commission qui est sur le point d'embaucher un nouvel employé dont les performances sont évaluées par plusieurs experts. Les membres de la commission peuvent ne pas avoir de règle de vote en tête au début du processus et ne pas vouloir se mettre d'accord sur une règle de vote spécifique. Cependant, ils pourraient être disposés à répondre à quelques questions exigeant de sélectionner le gagnant parmi des profils spécifiques.

Considérons, comme deuxième exemple, le processus d'évaluation d'une conférence où le meilleur article doit être élu. Les agents expriment leurs préférences sur les articles qu'ils ont évalués, mais ils ne sont pas conscients de la règle de vote que le président du programme appliquera lorsqu'il les regroupera. Néanmoins, les évaluateurs sont toujours prêts à participer au processus. De plus, le CP peut ne pas avoir de règle de vote spécifique en tête, et il lui sera difficile de fournir un vecteur de notation précis si on le lui demande. Peut-être croit-elle fermement que le fait d'être classé une fois en première position a "beaucoup plus" de valeur que le fait d'être classé deux fois en deuxième position, mais ne sait pas exactement de combien (bien qu'elle puisse juger des cas d'exemple).

Nous nous concentrons sur les règles de notation positionnelle avec des poids convexes, qui sont une méthode particulièrement courante utilisée pour agréger les classements. Nous développons des méthodes, basées sur la notion de regret minimax, pour déterminer un "gagnant" robuste en cas d'incertitude à la fois sur la règle de vote et sur les préférences des agents. Nous fournissons des méthodes d'élicitation incrémentales qui, à chaque étape de l'élicitation, interrogent l'un des agents ou le président, et nous discutons de plusieurs heuristiques pour choisir des questions qui réduisent rapidement le regret. Les réponses aux questions sont encodées sous forme de contraintes ; les questions aux agents sont des comparaisons entre des paires d'alternatives tandis que les questions au président demandent de sélectionner un gagnant parmi un profil synthétique.

Conclusions. Notre approche est évaluée sur des simulations avec des ensembles de données synthétiques et réelles où la règle de vote et les préférences de l'agent sont initialement inconnues du système et progressivement révélées par des questions. Nous supposons que le président est humain, donc capable de répondre à des questions sur un nombre limité d'alternatives, et nous nous concentrons donc sur des situations de choix social à petite échelle. Nous comparons l'efficacité de plusieurs stratégies de questionnement basées sur la connaissance actuelle de la règle et des préférences. Pour résumer nos contributions :

1) Nous fournissons un nouveau mécanisme pour éliciter une règle de vote en traduisant des questions abstraites sur les poids en un choix d'une alternative étant donné un profil concret. Supposons, par example, que nous voulions poser la question suivante à la commission : w 2w 3 ≥ 2(w 3 -w 4 ). Cela signifie que nous voulons savoir si la différence de poids entre la Eli.

Rnd.

Table 8.1: MMR moyen dans des problèmes de taille (10, 20) après 500 questions, parmi lesquelles q c à la commission.

q c 2 ph. ca ± sd 2 ph. ac ± sd 0 0.6 ± 0.6 0.6 ± 0.6 15 0.5 ± 0.5 0.6 ± 0.6 30 0.3 ± 0.5 0.4 ± 0.5 50 0.1 ± 0.2 0.1 ± 0.3 100 0.4 ± 0.6 0.2 ± 0.5 200 2.1 ± 1.6 2.4 ± 1.2 300 5.8 ± 1.7 6.7 ± 1.5 400 11.3 ± 1.1 11.9 ± 1.2 500 20.0 ± 0.0 20.0 ± 0.0 ayant la meilleure médiane à la fin de cette phase est sélectionné comme représentant pour l'élection présidentielle. Cependant, la participation de ce candidat à l'élection présidentielle réelle en France n'est pas acquise. En effet, selon la loi française, un candidat doit recueillir au moins 500 signatures d'élus pour pouvoir participer à l'élection présidentielle. Le candidat sélectionné par les électeurs de LaPrimaire.org en 2016 n'a recueilli que 135 signatures et n'a pas participé à l'élection présidentielle de 2017. La sélection aléatoire de candidats est-elle une bonne technique d'élicitation ? Nous explorons les conséquences de l'incomplétude du profil et prouvons que cette méthode peut échouer à élire le candidat gagnant du profil complet. De plus, nous réalisons des expériences sur des profils générés aléatoirement et des profils suivant la distribution des notes d'un scénario de vote réel. Nous constatons que la probabilité de ne pas sélectionner le gagnant du profil complet diminue fortement lorsque le nombre de votants augmente et nous étudions quelle partie du vecteur de notes nous devons connaître pour que cette probabilité soit faible.

Conclusions. Nous avons prouvé que, étant donné un profil complet, il est possible de trouver un profil incomplet (tel qu'un achèvement possible est égal au profil considéré) avec un gagnant différent du profil complet. Nous avons également montré que la probabilité que cela se produise dépend du profil considéré.

De plus, nous avons réalisé des expériences sur des profils dans lesquels chaque vecteur de note a une distribution de note générée aléatoirement. En fixant le nombre de votants, nous avons analysé quelle part du vecteur de note nous devons connaître pour que la probabilité de manquer le gagnant soit faible, voir Figure 8.4. Nous avons également considéré un profil créé à partir de la distribution des notes d'un scénario de vote réel illustré par Figure 8.5. Nous avons constaté que la probabilité de ne pas sélectionner le gagnant du profil complet diminue fortement lorsque le nombre d'électeurs augmente, ce qui rend cette méthode adaptée aux élections avec un grand nombre d'électeurs mais moins appropriée pour les petits profils, voir Figure 8.6.

Les travaux futurs sur ce sujet pourraient étudier la possibilité de manipuler ce processus d'élicitation. En particulier du côté de l'"analyste" chargé d'interroger les électeurs et de la manière dont il peut potentiellement manipuler le résultat en posant des questions particulières à des groupes spécifiques d'électeurs. Par exemple, si elle sait que les électeurs d'une circonscription électorale donnée ont tendance à voter majoritairement pour un parti donné, elle peut décider de ne jamais interroger ces électeurs sur le candidat de ce parti (ou vice-versa, selon le parti qu'elle favorise).

Une autre étape pourrait concerner l'explicabilité de ce processus aux électeurs. En effet, les électeurs peuvent ne pas comprendre comment le fait de juger une seule personne donne une bonne approximation du résultat qui serait obtenu en demandant le profil complet. De plus, ils peuvent ne pas apprécier de juger un candidat au hasard et non leur favori.

Le code permettant de reproduire les expériences de cet article et les fichiers contenant les données rapportées sont disponibles sur https://github.com/xoxor/elicitationMJ.

Compromising as an equal loss principle

Le mot compromis vient du latin compromissus, participe passé de compromittere : com ensemble et promittere promettre. L'idée de compromis se retrouve en effet dans des textes datant de l'époque romaine, où deux parties en conflit qui souhaitaient soumettre leur différend à l'arbitrage désignaient un tiers (un arbitre) et promettaient mutuellement de se conformer au jugement incontestable de ce dernier. Si l'une des parties avait rompu cette promesse, elle aurait dû payer une pénalité. Dans un fragment d'une lettre écrite par Proculus, qui est rapporté par Zimmermann [1996, p.529], il est clair que les deux parties au conflit ont accepté de donner à l'arbitre des pouvoirs illimités dans sa décision. Aucun recours n'était possible contre la sentence finale, qui était contraignante, aussi injuste et inégale soit-elle. Cette idée du compromis comme simple processus d'arbitrage semble très différente de la notion que nous en avons aujourd'hui. Considérons les définitions des deux verbes dans un dictionnaire moderne : arbitrer "régler un différend entre deux personnes ou groupes après avoir entendu les arguments et les opinions de chacun" ; compromettre "parvenir à un accord par concession mutuelle". La concession mutuelle est l'élément qui nous fait immédiatement penser à un compromis et c'est précisément le facteur manquant dans la description du compromis romain et de l'arbitrage moderne. En citant [START_REF] Braybrooke | The possibilities of compromise[END_REF] "C'est tout simplement une mauvaise plaisanterie que de dire qu'une personne est partie à un compromis alors qu'elle n'en a rien retiré.".

Dans Chapter 7, nous présentons deux versions différentes de compromis, en particulier une qui privilégie l'égalité aux dépens de l'efficacité de Pareto. De plus, nous considérerons le concept de "equal-loss" (perte égale) [START_REF] Chun | The equal-loss principle for bargaining problems[END_REF][START_REF] Chun | The lexicographic equal-loss solution[END_REF] comme la base du compromis dans toutes les situations où l'égalitarisme, au sens de concéder également, est une prérogative importante. Il s'agit d'une nouveauté dans la littérature des règles de choix social, qui jusqu'à présent n'ont fait qu'imposer la volonté de compromis sans réellement garantir que toutes les parties concèdent quelque chose. Le philosophe [START_REF] Day | [END_REF] tente d'expliquer ce phénomène en pensant qu'il découle de la négation de l'adjectif "intransigeant" : "Une personne intransigeante est une personne qui n'est pas disposée à faire des concessions, donc (on en déduit à tort) une personne compromettante est une personne souple et disposée à faire des concessions-indépendamment du fait qu'elle reçoive une concession en retour. Quoi qu'il en soit, il faut insister, car il est généralement admis que le compromis implique nécessairement des concessions mutuelles." Cela pourrait expliquer pourquoi toutes les règles de vote qui tentent de faire un compromis se contentent en fait de la volonté des agents de faire un compromis. [START_REF] Merlin | Compromise rules revisited[END_REF] discutent des plus célèbres de ces procédures en proposant de les rassembler dans la même classe de règles de compromis. Dans Section 2.1.2, nous avons déjà défini le Majoritarian Compromise, introduit par [START_REF] Sertel | Lecture notes on microeconomics[END_REF] et analysé plus en détail par [START_REF] Sertel | The majoritarian compromise is majoritarian-optimal and subgameperfect implementable[END_REF]. Basée sur une révision de la règle de Condorcet-Bucklin, cette procédure part du choix idéal de chacun pour trouver une alternative soutenue par la majorité des votants. Si une telle alternative n'existe pas, elle se rabat sur le deuxième, le troisième et plus généralement le k-e meilleur choix des votants, jusqu'à ce qu'au moins une des alternatives considérées figure parmi les k premiers meilleurs pour une majorité. Si au lieu de considérer un accord pour la majorité des votants, nous souhaitons sélectionner comme gagnants les alternatives soutenues par l'unanimité des votants, alors la procédure correspond à la règle Fallback Bargaining. Plus généralement, si nous considérons le soutien d'un certain quota q d'électeurs, nous nous référons à la règle de "q-approval fallback bargaining" [START_REF] Brams | [END_REF].

Toutes ces SCRs imposent aux électeurs une volonté de compromis, mais nous soutenons qu'elles ne garantissent pas efficacement un résultat où les agents ont effectivement fait des compromis. Cet exemple motive notre point de vue: .

Lorsque q ∈ 1, n 2 + 1 , tous les compromis BK choisissent a et c tandis que les compromis BK révisés choisissent a. Ces résultats n'apparaissent pas comme un compromis car près de la moitié des votants obtiennent leur meilleur choix tandis que l'autre moitié doit se contenter de leur pire choix. Observez que b reçoit un soutien unanime lorsque chaque électeur recule d'un pas par rapport à son point idéal.

When q ∈ 1, n 2 + 1 , all BK compromises pick a and c while the revised BK compromises select a. These outcomes do not appear as a compromise as almost half of the voters obtain their best choice while the remaining half have to be contented with their worst one. Observe that b receives unanimous support when each voter falls back one step from her ideal point.

Nous définissons qu'une règle est Egalitarian Compromise (EC) (resp., Egalitarian Compromise Compatible (ECC)), si tous (resp., quelques) les gagnants sont parmi les alternatives avec les pertes les plus également distribuées. Évidemment, EC est une sous-classe de ECC.

De plus, nous définissons qu'une règle est Paretian Compromise (PC) (resp., Paretian Compromise Compatible (PCC)), si tous (resp., quelques) les gagnants sont parmi les alternatives Pareto optimales avec les pertes les plus également distribuées. Évidemment, PC est une sousclasse de PCC.

Conclusions. Nous prouvons que : aucune procédure de Condorcet n'est ECC ou PCC (Theorem 7.3), aucune règle de score n'est ECC (Theorem 7.4) ou PCC à l'exception de la règle d'antipluralité (Theorems 7.5 and 7.6), les compromis BK ne sont ni ECC ni PCC (Theorems 7.8 and 7.9) à l'exception de fallback bargaining qui est PC (Theorem 7.7).

Nos résultats d'impossibilité sont énoncés pour l'ensemble des mesures d'écart Σ, mais ils prévalent pour tout sous-ensemble de Σ. Comme Σ est le plus grand ensemble de mesures d'écart sensibles, ils sont valables pour tout concept spécifique d'équité que l'on pourrait choisir. D'autre part, nos résultats de possibilité sur le fallback bargaining et l'antipluralité ne se propagent pas aux sous-ensembles de Σ. En fait, dès qu'une restriction raisonnablement légère sur Σ est imposée, les deux règles ne sont plus PCC (Theorem 7.10). Avec deux individus et une restriction similaire sur Σ, tous les SCR à deux personnes bien connus de la littérature, à savoir le fallback bargaining, les règles de fallback bargaining, Pareto and veto rules, short listing et veto rank, ne parviennent pas à trouver des compromis ex-post (Theorem 7.11).

  erences, given n = 100, m = 50 and k ∈ 1, 25 for 1000 batches of 1000 runs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Result obtained from UAV experiment by asking n = 1147 voters to judge m = 12 alternatives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Average probability of missing the winner using a real case distribution of preferences, given m = 12 for n ∈ {10, 25, 50, 100, 250, 500} and k ∈ 1, 5 . . . . 8.1 Profil représentant une question posée à la commission sous forme étendue (a) et compacte (b). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 MMR moyen (normalisé par n) après k questions avec la stratégie pessimiste pour différents ensembles de données. . . . . . . . . . . . . . . . . . . . . . . 8.3 MMR moyen dans des problèmes de taille (5, 10) après k questions. . . . . . . 8.4 Probabilité moyenne de ne pas trouver le gagnant dans le cadre d'une distribution uniforme des préférences, étant donné n = 100, m = 50 pour 1000 lots de 1000 exécutions et k ∈ 1, 25 . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.5 Résultat obtenu à partir d'une expérience de vote en demandant à n = 1147 électeurs de juger m = 12 alternatives. . . . . . . . . . . . . . . . . . . . . . . 8.6 Probabilité moyenne de ne pas trouver le gagnant en utilisant une distribution des préférences de cas réel, étant donné m = 12 pour n ∈ {10, 25, 50, 100, 250, 500} et k ∈ 1, 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  and two alternatives a, b ∈ A, we denote with µ(a, b) = |{≻ i , i ∈ N | a ≻ i b}| the number of preference rankings for which a is preferred to b. Pareto Property. Given a profile P ∈ L(A) N and any distinct a, b ∈ A, a Pareto dominates b at P (or equivalently b is Pareto dominated by a at P ) iff a ≻ i b, ∀i ∈ N . We denote by PO(P ) = {a ∈ A | ∀b ∈ A \ {a}, ∃i ∈ N, a ≻ i b} the set of Pareto optimal alternatives at P . An SCR f is Paretian iff f (P ) ⊆ PO(P ) ∀P ∈ L(A) N . In other words, f is Paretian if f (P ) never contains Pareto dominated alternatives. Condorcet criterion. Given a profile P ∈ L(A) N , an alternative a ∈ A is the Condorcet winner iff µ(a, b) > µ(b, a), ∀b ∈ A \ {a}. In other words, if a beats every other alternatives in pairwise comparisons.

  ⌈ n 2 ⌉ = 2. Therefore, d * 2 = 2 and the two SCRs return f 2 BK = {a, c} and f MC = {c}.

..

  The median of a is 9 and the median of b is 10, thus b is elected although only one voter slightly prefers b to a. This example can be reproduced with a larger number of voters:The alternative b is elected even if almost the unanimity of the voters strongly prefers a to b and only one voter slightly prefers b to a.

Example 3. 2 .

 2 Consider the following preference profile with n = 100:

  At a given time, our knowledge of agent j's preference is encoded by a partial order ≻ p j ⊆ ≻ * j over the alternatives, a transitive and asymmetric relation (we assume that preference information is truthful). An incomplete profile p = (≻ p j , j ∈ N * ) maps each agent to a partial preference. Let C(≻ p j ) = {≻ ∈ L(A) | ≻ p j ⊆ ≻} denote the set of possible completions of ≻ p i and C(p) = j∈N C(≻ p j ) the set of complete profiles extending p. Note that v * ∈ C(p).

p

  j b iff a ≻ p j b ∨ a = b and adopt the canonical notation when considering a relation as a function, writing ⪰ p j (x) for {y | x ⪰ p j y}. Proposition 4.1. There exists a completion v ∈ C(p) of the partial profile p such that PMR(x, y; p, W ) = max w∈W [s(y; v, w) -s(x; v, w)] and such that the linear order vj of each agent j satisfies:

Proposition 4. 2 .

 2 The rank of x in the PMR-maximizing linear orders of agent j is vj (x) = 1+|A|-|⪰ p j (x)|, and the rank of y is vj (y) = 1+|≺ p j (y)|+|β|, where |β| = |A\(⪰ p j (x)∪≺ p j (y))| if (x ⪰ p j y) and |β| = 0 otherwise.

  ⇒ a ̸ = y (as when a = y, (x ⪰ p j y) and ¬(x ⪰ p j a) are opposite claims). Suffices now to rewrite Eq. (4.7) to let the two disjuncts designate disjoint sets:a ≻ j y ⇔ (a ≻ p j y) ∨ ((x ⪰ p j y) ∧ ¬(x ⪰ p j a) ∧ ¬(a ≻ p j y)). (4.8)Note that in Proposition 4.2, in the case (x ⪰ p j y), β is the number of alternatives incomparable with both x and y.Proposition 4.3. The PMR can be written as: PMR(x, y; p, W ) = max w∈W j∈N w vj (y) -w vj (x) . αx r ) is the number of times y (resp. x) has rank r in the complete profile v defined in Proposition 4.2.Proposition 4.3 shows that PMR is linear in the weights. The pairwise max regret PMR(x, y; p, W ) can thus be obtained by solving the following linear program defined on the variables w 1 , . . . , w m : r )w r s.t. w 1 = 1 ≥ . . . ≥ w m = 0, Eq. (4.2) and w ∈ W.(4.10)

Figure 4 . 1 :

 41 Figure 4.1: Profile representing a question to the chair in extended (a) and compact (b) form.

  Figure 4.2: Average MMR in problems of size (5, 10) after k questions.

Figure 4

 4 Figure 4.3: Average MMR (normalized by n) after k questions with Pessimistic strategy for different datasets.

Figure 5 .

 5 Figure 5.4 illustrates the diagram related to the information about preferences acquired by asking questions. With a similar representation to the questions themselves, PreferenceInformation can be of two types: CommitteePreferenceInformation or VoterPreferenceInformation. The type of the information depends on the type of the question asked.

Figure 6 . 1 :

 61 Figure 6.1: Average probability of missing the winner under uniform distribution of preferences, given n = 100, m = 50 and k ∈ 1, 25 for 1000 batches of 1000 runs.

Figure 6 . 2 :

 62 Figure 6.2: Result obtained from UAV experiment by asking n = 1147 voters to judge m = 12 alternatives.

Example 7. 1 .

 1 Let N be a set of n ≥ 3 voters and A a set of alternatives. L(A) represents the set of linear orders over A. Consider the following preference profile P ∈ L(A) N , 1 c b a n -1 a b c , which represents one individual who prefers c to b, b to a, hence c to a; and n -1 individuals who prefer a to b, b to c, hence a to c.

Example 7. 2 .

 2 Consider the following preference profile with n = 100: 49 c b a 51 a b c .

Figure 8 . 1 :

 81 Figure 8.1: Profil représentant une question posée à la commission sous forme étendue (a) et compacte (b).

Figure 8

 8 Figure 8.2: MMR moyen (normalisé par n) après k questions avec la stratégie pessimiste pour différents ensembles de données.

Figure 8 .

 8 Figure 8.3: MMR moyen dans des problèmes de taille (5, 10) après k questions.

Figure 8 . 4 :

 84 Figure 8.4: Probabilité moyenne de ne pas trouver le gagnant dans le cadre d'une distribution uniforme des préférences, étant donné n = 100, m = 50 pour 1000 lots de 1000 exécutions et k ∈ 1, 25 .

Figure 8 .

 8 Figure 8.5: Résultat obtenu à partir d'une expérience de vote en demandant à n = 1147 électeurs de juger m = 12 alternatives.

Figure 8 .

 8 Figure 8.6: Probabilité moyenne de ne pas trouver le gagnant en utilisant une distribution des préférences de cas réel, étant donné m = 12 pour n ∈ {10, 25, 50, 100, 250, 500} et k ∈ 1, 5 .

Example 8 . 1 .

 81 Considérons le profil de préférence suivant avec n = 100:

Table 4

 4

.1: Average MMR in problems of size (10, 20) after k questions assuming geometric weights.

Table 4 .

 4 2: Questions asked by Pessimistic strategy on several datasets to reach n 10 regret, columns 4 and 5, and zero regret, last two columns.

	dataset	m	n	q MMR≤n/10 c	q MMR≤n/10 a	q MMR=0 c	q MMR=0 a
	m5n20	5	20	0.0	[ 4.3 | 5.0 | 5.8 ]	5.3	[ 5.4 | 6.2 | 7.2 ]
	m10n20	10	20	0.0	[ 13.9 | 16.1 | 18.4 ]	32.0	[ 19.7 | 21.8 | 24.7 ]
	m11n30	11	30	0.0	[ 16.6 | 19.0 | 22.3 ]	45.2	[ 23.1 | 25.7 | 28.9 ]
	tshirts	11	30	0.0	[ 13.1 | 16.6 | 19.6 ]	43.2	[ 28.2 | 32.0 | 35.6 ]
	courses	9	146	0.0	[ 6.0 | 7.0 | 7.0 ]	0.0	[ 6.8 | 7.0 | 7.0 ]
	m14n9	14	9	5.4	[ 30.3 | 33.5 | 36.7 ]	64.1	[ 37.6 | 40.5 | 44.3 ]
	skate	14	9	0.0	[ 11.4 | 11.6 | 12.3 ]	0.0	[ 11.5 | 11.8 | 12.8 ]
	m15n30	15	30	0.0	[ 25.0 | 29.5 | 33.7 ]

Table 4 .

 4 3: Average MMR in problems of size (10, 20) after 500 questions, among which q c to the chair.

	q c 2 ph. ca ± sd 2 ph. ac ± sd
	0	0.6 ± 0.6	0.6 ± 0.6
	15	0.5 ± 0.5	0.6 ± 0.6
	30	0.3 ± 0.5	0.4 ± 0.5
	50	0.1 ± 0.2	0.1 ± 0.3
	100	0.4 ± 0.6	0.2 ± 0.5
	200	2.1 ± 1.6	2.4 ± 1.2
	300	5.8 ± 1.7	6.7 ± 1.5
	400	11.3 ± 1.1	11.9 ± 1.2
	500	20.0 ± 0.0	20.0 ± 0.0

Table 6 .

 6 2: Average probability of missing the winner using a real case distribution of preferences, given m = 12 for different values of k and n. k avg P n=10 avg P n=25 avg P n=50 avg P n=100 avg P n=250 avg P n=500

	1	0.71	0.50	0.34	0.17	0.03	0.00
	2	0.50	0.22	0.07	0.01	0.00	0.00
	3	0.34	0.10	0.01	0.00	0.00	0.00
	4	0.18	0.04	0.00	0.00	0.00	0.00
	5	0.07	0.01	0.00	0.00	0.00	0.00

  8.2. FUTURE WORK rule as Egalitarian Compromise (EC) (resp., Egalitarian Compromise Compatible (ECC)), if all (resp., some) winners are among the alternatives with the most equally distributed losses. Furthermore, we denoted a voting rule as Paretian Compromise (PC) (resp., Paretian Compromise Compatible (PCC)

  Dans Chapter 7, nous abordons cette question et analysons quelles règles existantes, le cas échéant, répondent à cette nouvelle définition. Nous verrons que différentes définitions ont un sens dans différents contextes et que l'une n'est pas nécessairement meilleure que l'autre.Organisation de la thèse Chapter 2 rassemble les notions importantes qui sont à la base des thèmes abordés dans cette thèse et qui reviendront de manière récurrente dans les chapitres suivants. Nous y décrivons la différence entre le vote avec différents types de scrutins : les scrutins classés, que nous utiliserons dans Chapters 4 and 7, et les scrutins notés, que nous considérerons dans Chapter 6. Nous allons décrire les règles de vote que nous utiliserons dans nos contributions et certains des axiomes qui les caractérisent.

https://github.com/oliviercailloux/minimax.

This objection to the compromise nomenclature was raised by Jean-François Laslier during a CNRS workshop on compromising hosted by Istanbul Bilgi University in

L'exclusion du principe d'égalité des pertes par la quasi-totalité de la littérature conduit à se demander si le principe ne présente pas d'intérêt dans un contexte de choix social discret. Cela semble être le cas pour les situations de vote où le nombre d'électeurs dépasse le nombre de candidats et où, en général, chaque candidat est classé dernier par au moins un électeur. Dans ces cas, la principale préoccupation concerne le soutien des alternatives plutôt que l'égalité. D'autre part, les problèmes de choix collectifs à deux personnes sont généralement interprétés comme des situations d'arbitrage ou de négociation où le consentement mutuel est un élément essentiel pour parvenir à une solution. Ainsi, le principe de perte égale semble être valide pour les problèmes de choix collectifs à deux personnes et notre analyse soulève la question de la conception de nouvelles règles d'arbitrage discrètes compatibles avec le principe de perte égale.

Conclusions et Perspectives

Tout au long de ce manuscrit, nous avons abordé plusieurs problèmes liés au domaine du choix social. En particulier, nous nous sommes concentrés sur deux scénarios. En considérant un modèle classique dans lequel les préférences d'un ensemble de votant sont connues, nous avons défini deux classes de règles de vote capables de refléter une notion de compromis dans laquelle l'égalitarisme, au sens de concéder également, est une préoccupation majeure. En outre, nous avons pris de la distance par rapport à cette perspective standard dans laquelle les préférences sont supposées être connues dès le départ et nous avons étudié le problème de l'élicitation des préférences dans différents contextes.

Il existe de nombreuses directions intéressantes pour les travaux futurs pour chacun des problèmes considérés. En ce qui concerne l'élicitation simultanée des règles de vote et des préférences des agents, on pourrait développer davantage de stratégies avec différentes heuristiques pour les comparer à celles que nous avons proposées. Par exemple, des stratégies moins coûteuses en calcul permettraient de tester des ensembles de données plus importants, avec plus de votants et plus d'alternatives. Il serait également intéressant d'étendre l'élicitation des règles de vote autres que les règles de position. En outre, nous pensons que la transformation des questions en profils d'exemple est un concept très intéressant qui n'est pas beaucoup exploré dans la littérature et qui pourrait être appliqué dans différents contextes.

Le chapitre consacré à l'analyse de la procédure d'élicitation à l'aide de MJ n'est pas encore tout à fait terminé, de sorte qu'il existe de nombreuses idées d'extensions possibles. On pourrait, par exemple, étudier la possibilité de manipuler le processus d'élicitation lui-même. En particulier, comment la partie chargée d'interroger les électeurs peut manipuler le résultat en dirigeant les questions vers des électeurs spécifiques. Une autre piste peut concerner l'explicabilité de ce processus. Les électeurs peuvent avoir du mal à croire que le fait de juger une seule personne donne une bonne approximation du résultat qui serait obtenu en demandant le profil complet.

Enfin, lorsque l'on considère le concept de compromis, différentes notions de compromis peuvent être conçues. Une approche pourrait consister à choisir des alternatives qui ne sont ni les meilleures ni les pires d'un électeur. Tout dépend de l'idée de justice que l'on veut représenter et des priorités du scénario considéré. En outre, le compromis entre équité et efficacité peut être exploré dans d'autres contextes, plus riches. Pour conclure, nous aimons penser que chacune de nos contributions n'est que le début d'une longue série de développements futurs.

INFORMATION

MJ is a voting system where voters assign grades to candidates using an ordinal scale. The winner is the candidate with the highest majority-grade -which is the median of the grades received. This method has attracted increasing attention of french associations and political parties which have started to use MJ for internal decisions or local elections. In particular LaPrimaire.org is a french association that uses MJ to choose its candidate for the french presidential election. The vote is conducted in two rounds: in the first one the voters judge five candidates randomly picked; the five candidates with the highest medians pass at the second round as finalists and the voters are asked to judge them. Is the random selection of candidates a good elicitation technique? In this paper we explore the consequences of profile incompleteness and prove that this method can fail to elect the winning candidate of the complete profile. Furthermore, we perform experiments on randomly generated profiles and profiles following the grade distribution of a real voting scenario. We find that the probability of not selecting the winner of the full profile greatly decreases as the number of voters increases and we investigate how much of the grade vector we should know in order for this probability to be low.

Introduction

MJ is a voting method proposed by [START_REF] Balinski | Réponse à des critiques du jugement majoritaire[END_REF]Laraki [2007, 2011] to elect one out of m candidates based on the judgments of n voters. The latter express their preferences by assigning to each candidate one of the following adjectives: Excellent, Very good, Good, Average, Mediocre, Inadequate, To be rejected. Those adjectives represent a common language whose semantic is assumed to be a shared knowledge among the voters carrying thus an absolute meaning. For each candidate the median of the grades she received is computed, this is called majority-grade.

The candidate with the highest majority-grade is elected. Ties are broken by considering the majority-grade of first order: one vote associated with the majority-grade of each tied candidates is removed and their medians are recomputed. The candidate with the highest new median is elected. If there is still a tie the process is repeated until a unique winner is found.

In the last few years MJ has being adopted by a progressively larger number of french political parties including: Le Parti Pirate, Génération(s), LaPrimaire.org, France Insoumise and La République en Marche. "Mieux Voter" [MieuxVoter, 2022a] is a french association that promotes the use of MJ as voting method whenever a collective choice has to be selected: public INCOMPLETE INFORMATION where all voters judge all alternatives δ 6 except for the alternative j 1 which is judged δ 7 by everyone. The median grade of the alternative j 1 is f maj (P j 1 ) = δ 7 and the one of all the other alternatives is f maj (P x ) = δ 6 , ∀x ∈ A \ {j 1 }. Thus, the winner in the profile P is F maj (P ) = {j 1 }. Consider now the following incomplete profile P :

. δ 6 δ 6 . . . δ 6 j m δ 6 δ 6 . . . δ 6 .

The median grade of j 1 under the profile P is f maj (P j 1 ) = δ and the one of all the other alternatives is f maj (P x ) = δ 6 , ∀x ∈ A \ {j 1 }. Because δ < δ 6 , F k (P ) will be any subset of k elements of {j 2 , j 3 , . . . , j m }, for any k ∈ 1, m -1 . Since all those alternatives have the same grade vectors, some orderings can be used to define the members of F k (P ). Thus, j 1 / ∈ F k (P ), and F maj (P ) ⊊ F k (P ), for any k ∈ 1, m -1 .

From Theorem 6.1, considering k = 1 and recalling that F k=1 (P ) = F maj (P ) we can conclude that there exist an incomplete profile and one of its completion that do not have the same winner. Remark 6.2. Given a set of alternatives A and a set of voters N , there exist a complete profile P and an incomplete profile P such that P ∈ C(P ) and F maj (P ) ̸ = F maj (P ).

We have shown that it is possible to find a complete profile P whose winner is not in the set K of alternatives with the highest medians for an incomplete profile P , with P ∈ C(P ). If we look at the procedure used by LaPrimaire.org, however, the situation is slightly more complex. We are not considering just any incomplete profile, but a k value is set from the beginning and the incomplete profile is formed by asking each voter to rate k random chosen candidates. They set k = 5. The k alternatives with the highest medians on this incomplete profile form K. Note that, the example profile P considered in the proof of Theorem 6.1 could be the result of a random process of questioning the voters about k = m -1 alternatives, and they never got the chance to grade the alternative j 1 .

We recall that P k is an incomplete profile where every voter judges k ∈ 1, m -1 alternatives. If we consider the matrix m × n of grades, then the columns, i.e. the vectors of grades expressed by each voter, are composed of only k "defined" grades.

Theorem 6.2. Given a set A of alternatives m ≥ 2, a set of voters N and a value k ∈ 1, m -1 , there exist a complete profile P and an incomplete profile P k such that P ∈ C(P k ) and

Proof. Consider the complete profile P defined in the proof of Theorem 6.1, we will show how to construct an incomplete profile for any value of k ∈ 1, m -1 such that the statement is true. Let us call K = F k (P k ). Note that we can select any complete profile where there is one alternative j graded the highest by everyone, and all the other alternatives are considered worst by everyone.

INCOMPLETE INFORMATION

Remark 6.4. After asking each of the n voters to grade k ∈ 1, m -1 of the m alternatives, the average size of the grade vectors is q = n • k m . grade vectors are found, we compute the median for each of those vectors. The k alternatives with the highest medians form the set K and we check if j 1 is in this set. If yes, then we know it will be the winner in the next phase when the complete preferences are asked to each voters. Otherwise, j 1 will not be the winner and we count this incomplete profile P k for our P. In fact,

INCOMPLETE INFORMATION

given the profile P we repeat this operation 1000 times, and P will be the number of profiles P k for which j 1 is not a winner, over the total number of incomplete profiles considered which is 1000. Moreover, we repeat this operations 1000 times. Thus, we generate 1000 complete profiles P and for each we consider 1000 incomplete profiles. At the end we obtain 1000 probabilities for which we consider average and standard deviation. Table 6.1 shows the average probability for each value k with the standard deviation over the 1000 runs. We varied k from 1 to 25 but omitted the results after k = 13 because they are too small to be relevant. The complete results can be found at https://github.com/xoxor/ elicitationMJ and they are displayed on Figure 6.1. In fact, if we take the first line of Table 6.1, we have that when we ask k = 1 question to each voter we have 64% of probability not to find j 1 in the set K. This happens when the incomplete vectors are, on average, k/m = 1/50 (2%) of the complete vector. If we take k = 5, we know on average 1/10 of each grade vector, and the probability drops at 0.19%. Figure 6.1 shows this correlation.

Profile real scenario

In the next experiment we want to investigate a different problem. Given a number of alternatives m, we assume that we want to ask a limited number of questions k because asking questions is costly. How large the electorate n must be for an incomplete grade vector of n • k/m elements to be sufficiently representative of a complete vector? Because randomly constructed profiles INCOMPLETE INFORMATION second round of voting, and the best alternative is selected by MJ as the winner. We have proven that given a complete profile it is possible to find an incomplete profile (such that a possible completion is equal to the considered profile) with a different winner from the complete profile. We also showed that the probability of this happening depends on the profile considered.

Moreover, we have performed experiments on profiles in which each grade vector has a randomly generated distribution of grade. Fixing the number of voters, we analyzed how much of the grade vector we must know in order for the probability missing the winner to be low. We have found that when knowing only the 20% of the vector (thus after having asked 10 questions) the probability of missing the winner is close to zero. We have also considered a profile created from the grade distribution of a real voting scenario. We have found that the probability of not selecting the winner of the complete profile greatly decreases as the number of voters increases, making this method suitable for elections with large numbers of voters but less appropriate for small profiles.

Future work on this topic could investigate the manipulability of this elicitation process. Especially on the side of the "analyst" who is in charge of questioning voters and how she can potentially manipulate the outcome by asking particular questions to specific groups of voters. For example, if she knows that voters in a given electoral district tend to vote predominantly for a given party she may decide never to ask those voters about that party's candidate (or vice-versa depending on the party she favors).

Another step might involve the explainability of this process to voters. In fact, voters may find difficult to believe that judging only one person gives a good approximation of the result that would be obtained by asking for the full profile. Also, they may not appreciate judging a random candidate and not their favorite.

The code to reproduce the experiments in this article and the files with the reported data are available at https://github.com/xoxor/elicitationMJ.

CHAPTER 7 COMPROMISING AS AN EQUAL-LOSS PRINCIPLE

A social choice rule aggregates the preferences of a group of individuals over a set of alternatives into a collective choice. The literature admits several social choice rules whose recommendations are supposed to reflect a compromise among individuals. We observe that all these compromise rules can be better described as procedural compromises, i.e., they impose over individuals a willingness to compromise but they do not ensure an outcome where everyone has effectively compromised. We revisit the concept of a compromise in a collective choice environment with at least three individuals having strict preferences over a finite set of alternatives. Referring to a large class of spread measures, we view the concept of compromise from an equal loss perspective, favoring an outcome where every voter concedes as equally as possible. As such, being a compromise may fail Pareto efficiency, which we ensure by asking voters to concede as equally as possible among the Pareto efficient alternatives. We show that Condorcet consistent rules, scoring rules (except antiplurality) and Brams-Kilgour compromises (except fallback bargaining) all fail to ascertain an outcome which is a compromise. A slight restriction on acceptable spread measures suffices to extend the negative result to antiplurality and fallback bargaining. This failure also prevails for social choice problems with two individuals: all wellknown two-person social choice rules of the literature, namely, fallback bargaining, Pareto and veto rules, short listing and veto rank, fail to pick ex-post compromises. We conclude that there is a need to propose and study rules that satisfy this equal loss, or outcome oriented, notion of a compromise.

Introduction

In a typical social choice problem, several individuals express their preferences over a set of alternatives and one shall be picked as the collective outcome. Although the literature admits several SCRs with different properties, there is a common understanding that collective choices must reflect "compromises". One of the first to explicitly refer to a SCR as a compromise is [START_REF] Sertel | Lecture notes on microeconomics[END_REF] introducing the majoritarian compromise. This SCR, further analyzed by [START_REF] Sertel | The majoritarian compromise is majoritarian-optimal and subgameperfect implementable[END_REF], is a rediscovery of a method suggested by James W. Bucklin at the beginning of the 20 th century [START_REF] Erdélyi | Control complexity in bucklin and fallback voting: A theoretical analysis[END_REF]. Starting from everyone's ideal alternative, it falls back to the voters' second, third and more generally k-th best, until one of the alternatives considered appears among the first k best for a majority. [START_REF] Brams | [END_REF] generalize this concept and introduce a class of SCRs called q-approval fall-back bargaining, where q is the required quantity of support that can vary from a single voter up to unanimity. Different choices of q lead Definition 7.

Again, it is clear that PC is a subclass of PCC. It will also probably come with no surprise that for a SCR, being PC is incompatible with being ECC, as being PC requires to be Paretian, which permits to use Theorem 7.1. On the other hand, it is less immediate that being EC is incompatible with being PCC, because being PCC does not require to be Paretian. This is however true.

Theorem 7.2. For n ≥ 2, m ≥ 3, no SCR is both EC and PCC.

Proof. Considering the profile P of Proposition 7.1, with a m the alternative mentioned there, any EC f and any σ ∈ Σ, suffices to prove that f (P ) ∩ min PO(P ) (σ

First, from Proposition 7.1 we have that {a m } ∩ PO(P ) = ∅, hence {a m }∩ min PO(P ) (σ

Second, because f is EC, for some σ, f (P ) ⊆ min A (σ • λ P ). Using Proposition 7.1 again, we see that min A (σ

That f (P ) ∩ min PO(P ) (σ • λ P ) = ∅ follows from these two facts.

It is interesting to note that the incompatibility is not complete, however.

Remark 7.1. For n ≥ 2, m ≥ 3, there exist SCRs that are both ECC and PCC, such as the SCR that selects the whole set of alternatives at every profile. However, this SCR fails to be Paretian, as is any SCR that is ECC.

Which SCRs are compromises?

In this section we assume n ≥ 3 and leave the analysis of n = 2 to the next section.

Condorcet consistent rules

An alternative

So each profile admits either no or a unique Condorcet winner. An SCR f is Condorcet consistent iff f (P ) = {x} at each P ∈ L(A) N that admits x as the (unique) Condorcet winner.

Theorem 7.3. Let n ≥ 3 and m ≥ 3. A Condorcet consistent SCR f is neither ECC nor PCC.

Proof. Consider the following profile P , where the dots represent the sequence a 4 to a m :

Consider any Condorcet consistent SCR f . Thus, f (P ) = {a 1 }. However, min A (σ • λ P ) = min PO(P ) (σ•λ P ) = {a 2 } ∀σ ∈ Σ, so there exists a profile P such that both f (P )∩min A (σ•λ P ) and f (P ) ∩ min PO(P ) (σ • λ P ) are empty.

Note that Condorcet consistent rules need not be Paretian so the fact that they all fail ECC does not follow from Theorem 7.1.

Scoring rules

A score vector is an m-tuple w = (w 1 , . . . , w m ) ∈ 0, 1 m with w 1 = 1, w m = 0 and w i ≥ w i+1 ∀i ∈ 1, m -1 . Given a score vector w, we write s w (x, P ) = i∈N w r≻ i (x) for the score of x ∈ A at P ∈ L(A) N . Each vector w identifies a scoring rule f w n defined as f w n (P ) = {x ∈ A : s w (x, P ) ≥ s w (y, P ) ∀y ∈ A} for every P ∈ L(A) N . We first show that no scoring rule is ECC, for any value of n and m at least 3.

Theorem 7.4. Let n ≥ 3 and m ≥ 3. No score vector w induces a scoring rule f w n that is ECC. Proof. Take any score vector w. Consider the profile P of Proposition 7.1. Observe that min A (σ • λ P ) = {a m } ∀σ ∈ Σ. However, as w 1 > w m , we have s w (a 1 , P ) > s w (a m , P ) which implies a m / ∈ f w (P ).

We call antiplurality score vector the vector w such that w i = 1, ∀i ∈ 1, m -1 , and w m = 0.

Theorem 7.5. Let m ≥ 3 and let w be the antiplurality score vector. The SCR f w n satisfies PCC for all n ≥ 3.

Proof. Define σ ∈ Σ as, ∀l ∈ 0, m-1 N : σ(l) = 1 iff ∃i, j ∈ N | l i ̸ = l j ; σ(l) = 0 otherwise. We show the non-emptiness of f w n (P ) ∩ min PO(P ) (σ • λ P ) for any profile P . Let k = min PO(P ) {(σ • λ P )(x)} be the minimal value attained by σ • λ P over PO(P ). By construction of σ, k equals either 0 or 1.

For k = 1, take any x ∈ f w n (P ) ∩ PO(P ). This intersection is non-empty because whenever the antiplurality rule picks a Pareto dominated alternative z, it also picks all alternatives which Pareto dominate z. By definition of σ, σ(x) ≤ 1, hence, x ∈ min PO(P ) (σ • λ P ).

For k = 0, take any x ∈ min PO(P ) (σ • λ P ). As σ(λ P (x)) = 0, we have, ∀i, j ∈ N :

It is worth noting that the antiplurality rule f w n is not Paretian, hence fails PC for all n ≥ 3. This can be seen by picking a unanimous profile

Theorem 7.6. Let m ≥ 3. Take any score vector w which is not the antiplurality score vector. For some n ≥ 3, the SCR f w n fails PCC. Proof. Take any m ≥ 3 and any score vector w that is not the antiplurality score vector; therefore, w m-1 < 1. Pick any n such that n ≥ m -1 and n >

When q = 1 we have that f 1 (P ) = {a 1 , a 3 } and when q ∈ 2, n-1 we have that f q (P ) = {a 1 }.

Because σ(λ P (a 2 )) = 0 and σ(λ P (a 1 )) > 0 and σ(λ P (a 3 )) > 0, neither min A (σ • λ P ) nor min PO(P ) (σ • λ P ) contain a 1 nor a 3 for any σ ∈ Σ.

Note that for q ∈ 1, n -1 we have that f ′ q (P ) = {a 1 } since the tie breaking version of the BK compromise selects the alternatives with the greatest support. This version of the rule was used in the proof for Theorem 7.9 published by [START_REF] Cailloux | Compromising as an equal loss principle[END_REF].

Restrictions on sigma

The perfect equality recognition condition we adopt for spread measures, i.e., that the spread gets its lowest value 0 in case of perfect equality and only in this case, is very basic. Unless this condition is violated, Σ is the largest set of spread measures we could conceive. On the other hand, it is possible to let Σ shrink by imposing additional conditions over spread measures. Nevertheless, as the satisfaction of PC, PCC, EC, or ECC requires the existence of a spread measure, all of our negative results, namely, those expressed by Theorems 7. 1, 7.2, 7.3, 7.4, 7.6, 7.8 and 7.9 prevail when Σ is restricted. In a similar vein, the positive results in Theorems 7.5 and 7.7 risk to be lost with additional conditions over spread measures. Indeed, this section shows that a mild restriction removes the positive results concerning the only two rules that we found to be compatible with any of our compromise concepts.

Definition 7.5. Given any m ≥ 4 and n ≥ max{4, m -1}, we say that a spread measure σ satisfies condition C m,n iff we have σ(m -3, m -1, m -2, . . . , m -2) < σ(m -2, m -3, . . . , 1, 0, . . . , 0).

As both vectors are n dimensional, the term m -2 repeats n -2 times in the first vector and the term 0 repeats n -m + 2 times in the second vector.

This condition imposes a very reasonable requirement on spread measures for large values of m and n. Asking for σ(1, 3, 2, 2) to be smaller than σ(2, 1, 0, 0) is demanding while asking for σ (5,7,6,6,6,6,6) to be smaller than σ(6, 5, 4, 3, 2, 1, 0) reflects a mild assumption. In any case, as we state below, several well-known spread measures of the literature (see [START_REF] Allison | Measures of inequality[END_REF] for a comprehensive account) satisfy Definition 7.5. Letting l = n i=1 l i /n denote the arithmetic mean of the values of l = (l 1 , . . . , l n ), we consider the following measures:

Remark 7.2. We checked experimentally that σ mad , σ ad , σ sd and σ G all satisfy condition C m,n , for m ∈ 4, 1000 and n ∈ b, 1000 where b = max{4, m -1}.

We write Σ Cm,n ⊆ Σ for the set of spread measures that satisfy condition C m,n .

Theorem 7.10. For all m ≥ 4, n ≥ max{4, m -1}, under Σ Cm,n , 1) f w n fails PCC when w is the antiplurality score vector;

2) the BK compromise f n fails PCC.

Proof. Given any σ ∈ Σ Cm,n , let us show that there exists a profile P such that f w n ∩min PO(P ) (σ• λ P ) = ∅ and f n ∩ min PO(P ) (σ • λ P ) = ∅. To that aim, consider some x, y ∈ A and some

Note that f w n (P ) = f n (P ) = {y}. On the other hand, λ P (x) = (m -3, m -1, m -2, . . . , m-2) and λ P (y) = (m-2, m-3, . . . , 1, 0, . . . , 0). As σ(λ P (x)) < σ(λ P (y)) (because σ ∈ Σ Cm,n ), we see that y / ∈ min PO(P ) (σ • λ P ).

Two-voters case

In addition to fallback bargaining (FB) [START_REF] Brams | [END_REF] (defined in Section 7.4.3), we consider three prominent solutions of the literature.

Pareto-and-Veto rules (PV) [START_REF] Moulin | The strategy of social choice[END_REF][START_REF] Abreu | Virtual implementation in nash equilibrium[END_REF][START_REF] Laslier | A solution to the two-person implementation problem[END_REF] distribute a veto power of v 1 and v 2 alternatives to voters 1 and 2, respectively, with v 1 +v 2 = m-1. So, every voter i = 1, 2 (simultaneously) vetoes his worst v i alternatives. The SCR picks all non-vetoed and Pareto optimal alternatives.

The Veto-Rank mechanism (VR) is commonly used in the selection of arbitrators [START_REF] De Clippel | On the selection of arbitrators[END_REF]. Given a list of m (odd) alternatives (that are candidates to be arbitrators), each of the two voters (that are the two parties that must agree on an arbitrator) simultaneously vetoes his worst m-1 2 alternatives. The selected alternatives are the ones with the highest Borda score among the non-vetoed alternatives.

Again within the context of selecting arbitrators, de [START_REF] De Clippel | On the selection of arbitrators[END_REF] propose and analyze Shortlisting (SL) where one of the two parties starts by vetoing her worst m-1 2 alternatives (m being odd), and then the second party chooses her best alternative out of the remaining ones. As the outcome of the procedure depends on the party that starts, symmetry among players is ensured by defining the solution as the union of the two outcomes where one and the other party starts.

Definition 7.6. Given any m ≥ 7, a spread measure σ

). For m = 7 the condition requires σ(4, 2) < σ(0, 3) and σ(2, 4) < σ(3, 0) which is reasonable in our context. When the value of m is larger, the condition appears even more convincing. As m grows, the distance between 0 and ⌈ m 2 ⌉ -1 grows, while the distance between ⌈ m 2 ⌉ and 90 7.6. CONCLUDING REMARKS ⌈ m 2 ⌉ -2 remains constant. Requiring, for example, the spread of (15, 13) to be smaller than the spread of (0, 14) is very reasonable.

We write Σ Dm ⊆ Σ for the set of spread measures that satisfy condition D m .

Theorem 7.11. Let m ≥ 7. Under Σ Dm , FB and PV fail PCC. Furthermore, when m is odd, VR and SL also fail PCC.

Proof. Take any m ≥ 7 and any σ ∈ Σ Dm . Define α = ⌈ m 2 ⌉ -1 and β = ⌈ m 2 ⌉ -2. It follows from σ ∈ Σ Dm , that σ(α + 1, β) < σ(0, β + 1) and σ(β, α + 1) < σ(β + 1, 0). For m odd, note that α + β + 2 = m and consider the profile P where voter i 1 has the preference

For m even, note that α + β + 3 = m, and define the profile P in the same way, except that a supplementary alternative z is added at the bottom of both rankings.

Note that σ(λ P (y)) = σ(α+1, β) and that σ(λ P (x)) = σ(0, β+1). Therefore, σ(λ P (y)) < σ(λ P (x)). As y is not Pareto-dominated, an SCR that uniquely picks x at P cannot be PCC. In a similar vein, at the profile P ′ which is obtained by the inversion of the preferences of i 1 and i 2 at P , an SCR that is PCC cannot pick x uniquely.

The proof will be concluded by showing that FB, PV, and (when m is odd) VR and SL all pick only x at P or at P ′ .

We readily see that FB picks only x at P (and at P ′ ) since x is the first alternative which reaches the unanimous consent. For PV, let

, and consider the profile P . Observe that the first voter vetoes at least y and every b j (1 ≤ j ≤ β) while no voter vetoes x. As x Pareto-dominates every a j (1 ≤ j ≤ α), PV picks only x at P . When v i 2 ≥ v i 1 , a similar reasoning yields that PV picks only x at P ′ . Now let m be odd.

For VR, a reasoning similar to the one applied to PV yields x as the unique choice at P : each voter vetoes her worst m-1 2 alternatives, thus i 1 vetoes y and every b j (1 ≤ j ≤ β) and i 2 vetoes every a j (1 ≤ j ≤ α). The alternative x is the only non-vetoed alternative, so it is selected as the sole winner.

Finally, SL also picks x, as it is the unique winner no matter which voter starts the veto phase. If i 1 starts, y and every b j (1 ≤ j ≤ β) get vetoed, then i 2 chooses her best alternative out of the remaining ones which is x. If i 2 starts, every a j (1 ≤ j ≤ α) get vetoed, then i 1 chooses her best alternative which is x.

Concluding remarks

We define an ex-post compromise as an outcome where individuals give up as equally as possible from their ideal points. With three or more individuals, several well known SCRs fail to pick ex-post compromises, under any reasonable meaning attributed to "giving up equally". Our findings cover Condorcet extensions and scoring rules but also BK compromises, which impose a willingness to compromise without ensuring a compromised outcome. In particular we find that: no Condorcet procedure is ECC or PCC (Theorem 7.3), no scoring rule is ECC (Theorem 7.4)

MOTS CLÉS

Intelligence Artificielle, Computational Social Choice, Théorie de la décision, Élicitation de préférence, Modélisation des préférences.

RÉSUMÉ

Les règles de vote représentent des moyens formels d'agréger les préférences d'un groupe d'électeurs en une décision collective. Mais quelle règle choisir dépend du contexte et de la conception de la justice de la société concerné. Bien que toutes les règles de vote puissent être considérées comme un compromis entre individus, certaines le sont plus que d'autres. Dans ce manuscrit, nous proposons deux définition de compromis basées sur une notion de «equal-loss», favorisant un résultat où chaque électeur concède le plus également possible. Nous étudions plusieurs règles qui reflètent un certain concept de compromis et nous montrons comment, bien qu'elles imposent une volonté de compromis aux individus, elles ne garantissent pas un résultat où chacun a effectivement concédé. De plus, nous remettons en question l'hypothèse, souvent faite dans le cadre classique, que la règle de vote est fixée à l'avance et qu'une information complète sur les préférences des individus est fournie. En nous concentrant sur les règles de vote positionnelle, nous proposons des procédures d'élicitation capables de poser des questions aux votants et à l'entité responsable de la conception de la règle de vote, afin d'obtenir rapidement les informations les plus pertinentes. En considérant la règle de Jugement Majoritaire, nous analysons une procédure d'élicitation des préférences utilisée dans des scénarios de vote réels. Sur la base d'une information partielle sur les préférences des individus, nous analysons la probabilité de sélectionner un gagnant différent de celui obtenu en considérant le profil complet et nous étudions le nombre minimum de questions à poser aux électeurs pour que cette probabilité soit faible.

ABSTRACT

Voting rules are formal means of aggregating preferences of a group of voters over a set of alternatives into a collective decision. But which rule to use is a difficult question and the answer depends on the conception of justice of the concerned society or committee. Although all voting rules can be seen as a compromise between individuals, some are more so than others. In this manuscript we provide two notions of compromise based on an equal-loss perspective, favoring an outcome where every voter concedes as equally as possible. We study several rules that reflect some idea of compromise and show how, although imposing a willingness to compromise on individuals, they fail to ensure an outcome where everyone has effectively compromised. Moreover, we question the assumption, often made in the classical setting, that the voting rule is fixed beforehand and full information on the preferences of the individuals is provided. Focusing on positional scoring rules, we propose elicitation procedures based on minimax regret, able to interleave questions to the voters and to the entity responsible for designing the voting rule in order to quickly obtain the most relevant information. Considering Majority Judgment rule, we analyze a particular preference elicitation procedure used in real voting scenarios. Given a partial information on individuals preferences, we analyze the probability of selecting a different winner from the one obtained by considering the full profile and study the minimum number of questions to ask voters in order for this probability to be low.

KEYWORDS

Artificial Intelligence, Computational Social Choice, Decision Theory, Preference Elicitation, Preference Modeling.