Read Mathematics and the Real World Online
Authors: Zvi Artstein
Gale and Shapley's analysis and algorithm had a marked effect on theoretical research into staffing and choice, and also on the practical side. The basic algorithm and its results were extended to more complex frameworks much closer to reality, and they were also extended conceptually,
with proposals for changes and improvements. For example, it can readily be seen that when this algorithm is used, there is no advantage to either side in not revealing his or her real priority. This is in contrast to various situations in social conduct in which it is worthwhile to someone participating in a procedure to lie regarding his or her private preferences.
Several institutions have adopted classification and selection procedures that are consistent with Gale and Shapley's proposal, including hospitals selecting new interns. It is interesting to note that in both of the above instances the institutions chose to adopt the algorithm that was optimal from the candidates’, interns’ or students’ point of view. Their reason for this choice was apparently social. The institutions rated it more important that the candidates should feel that they had obtained the best possible position, consistent with the definition of stability, than that the institution itself should feel the same. Other institutions select candidates using different methods. American universities, for example, send candidates for faculty positions offers to which they must respond within a relatively short period of time; they do this to enroll their chosen faculty before they receive offers from other universities that they might prefer. The result is instability, as Gale and Shapley's basic assumption predicts.
Joint winner of the Nobel Prize in Economics in 2012 was Alvin Roth of Harvard University, who has moved since then to Stanford University. He developed an application of Gale and Shapley's method to match candidates for organ transplants with organs available for transplant, taking into consideration the quality of the match, the chances of success, personal details, and so on. Roth's research addressed also the issue of market design, namely, examination of the rules and procedures related to organ transplants, aiming at rules that take into account public beliefs and faith, yet increase the number of potential donors, a nontrivial goal that has deepened the use of the mathematical principles.
It is also interesting to compare the algorithm derived by mathematicians with the solutions to the problem of matching that nature arrived at via evolutionary development, at least in those cases where the couple must invest effort in establishing an economic base for themselves, such as a home for a human couple, or a nest for mating birds. That is why we can
observe the stability characteristic in many species of animals that remain with their mate for many years, and even extreme cases in which their original choice of mate remains their lifelong partner. Nature, however, found ways of reaching stability that differ from the algorithm proposed by Gale and Shapley. In many types of animals, stability, in the form of loyalty to one partner, is embedded in the animals’ genes. Those that maintained their relationship survived, and now that whole species has the characteristic of maintaining the stability of their relationships. Another method, which can be seen in an acute form in human societies, is the imposition of difficulties or fines for breaching a partnership. If the very act of separating from a partner causes unpleasantness for the disloyal individual or for the couple that decides to split up, the tendency to preserve stability will grow.
46. THE AGGREGATION OF PREFERENCES AND VOTING SYSTEMS
The roots of the second example we will present trace back to the beginning of the use of mathematics to understand human conduct. The marquis de Condorcet, Marie Jean Antoine Nicolas (1743–1794), of the de Caritat noble family, was a mathematician and a political philosopher of social science in France. Together with his interest in mathematics, in which he excelled from an early age, he involved himself in questions of society and economics. In contrast to many political leaders and thinkers of his time, he publicly expressed radical liberal views, including support for the equality of women and blacks. He reached the exalted position of secretary of the illustrious French Academy, and he was one of the leading supporters of the French Revolution. He then came into conflict on ideological grounds with some of the leaders of the revolution, and like many of his intellectual colleagues he had to flee and hide from the authorities, but eventually he was arrested. The marquis de Condorcet died in jail under mysterious circumstances, and it may reasonably be assumed that he was murdered.
The marquis's mathematical background is quite apparent in his social and economic writings, and with some degree of justification he is credited
with initiating the mathematical approach to social and economic issues. In the spirit of the time, Condorcet tried to examine different systems of election in a democracy. In his writings he constructed and presented a very basic example of the difficulty of agreeing on a good electoral system. The example is sometimes referred to as
Condorcet's paradox
. The situation he examined was that in which a group of voters have to reach an agreement on one individual from a number of candidates. Let us examine the criterion, said the marquis, in which the majority decides. In other words, one candidate is preferable to another if most of the electors prefer him or her. Does this relation of preference define a victorious candidate?
In his answer, Condorcet described the following example. Three electors have to select one representative from among three candidates, whom we shall denote A, B, and C. Each of the electors has his own rating of the three candidates. The first elector rates A above B, and B above C. The second elector prefers B to C, and C to A. The third elector prefers C to A, and A to B. Now we will see the result arising from the criterion we set. It can easily be seen that according to our criterion A is preferable to B (the first and the third electors, i.e., the majority, preferred A to B), B is preferable to C (the preference of both the first and the second electors, i.e., again the majority), and C is preferable to A (according to the second and third electors, a majority). The result is that despite each elector having a clearly defined order of preference, the system of the majority deciding leads to a circular position with no winning candidate indicated.
Condorcet's paradox illustrates the difficulty inherent in adopting the criterion of decision by majority. The marquis himself defended the system and tried to promote it in those situations in which it was applicable. He even suggested and strongly urged the adoption of the algorithm that would lead to a situation that if there is a preferred candidate according to this criterion, that is, a candidate who is preferable to all other candidates, then he should be the elected candidate.
A contemporary opponent of the marquis, Jean-Charles, chevalier de Borda (1733–1799), proposed another system. He suggested that every elector should rank the candidates according to his preferences, and the sum of the points, or their weighted combination according to an agreed
system, would determine the victorious candidate. This method is still in current use in many situations in which candidates have to be ranked in accordance with the electors’ preferences. Clearly, Borda's method does not comply with Condorcet's criterion.
Attempts to find a better or fairer system continued for many years, until in 1951 Kenneth Arrow, a mathematical economist from Stanford University, presented a result that puts the issue of aggregate preferences in a surprising new light. Arrow was awarded the Nobel Prize in Economics in 1972 for this result, among others. Arrow's result also has implications for an individual in complex situations. We will present this interpretation toward the end of this section.
Arrow chose the axiomatic approach. Instead of proposing and analyzing actual systems of choice, he formulated a number of requirements that a system of aggregate preferences should satisfy. The framework is similar to that of the marquis de Condorcet, that is, every elector has his own grading of the candidates. The system has to yield a rating of the candidates that will eventually reflect the will of the group of electors. The requirements, listed below, are quite minimalistic.
Reservations may be expressed about these requirements, but it should be borne in mind that they really are minimalistic. Requirement 2, for example, is much easier to satisfy than Condorcet's parallel requirement,
according to which it is sufficient for a majority of the electors to prefer A to B for that to become the group preference. Arrow requires only that if
all
the electors prefer A to B, then that will be the group choice. If it is not the case that all members of the group share the same preference for A over B, then the second requirement places no restrictions on the final rating. Similarly, if the withdrawal of one of the candidates does change the rating of one of the electors, the first requirement does not impose any restrictions on the final rating. The no-director condition prevents the situation in which the preference of the dictator is the decisive factor even in cases where the other electors, however many they are, have preferences different than those of the dictator.
Arrow's surprising result, referred to as
Arrow's impossibility theorem
, states that there is no system of selection that satisfies the three requirements (when there are at least three electors and at least three candidates).
The result, whose mathematical proof is not at all difficult, had a great impact on social scientists. Mathematics drew the boundaries of what could be achieved. Research is continuing, of course, in different directions. For example, in the framework discussed above, all possible private orders of priority are taken into account. We could consider a framework in which only certain orders of priority are considered, and then it might be possible to fulfill Arrow's axioms. Attempts have also been made to use other axioms. On the other hand, generalizations have been worked out that show that the impossibility theorem is far wider ranging than in Arrow's restricted example of methods of choice. There were also attempts to present selection methods in which the axioms are fulfilled with regard to the preferences of most of the electors. This subject became a popular area of research in the mathematics of social sciences; it is called
social choice
. The study and research have not led to any clear conclusion as to the ideal system of choice, but they have presented tools that help in the examination of the appropriateness of the different systems to given situations.
Did the research into methods of choice have an effect on day-to-day life? Not much of one. It is true that in a few instances, particularly when policy makers took the trouble to consult with experts, it can be seen that the limitations of the methods of choice were taken into account.
In most cases, however, that is not so. The scientific council of the institute in which I work comprises about two hundred professors, each one a leader in her or his scientific field. On one occasion this body had to decide between two alternatives, and from the discussion it appeared that both had the same chance of being selected. One of the professors, wishing to make the motion he preferred more attractive, proposed a small change in the wording of the proposal. The chairperson, who also favored the same course of action, immediately accepted the idea and announced that the choice would be between the three possibilities, and whichever received most votes would be accepted. The chairperson apparently did not realize that by so doing he blocked the chances of his preferred choice, because the votes of those who supported that choice would be divided between the two similar proposals (one of the original two and its slightly amended version). In the discussion someone pointed out that it would not be right to vote on three options, but in the hubbub that ensued it was impossible to explain why. The argument that helped to prevent the proposed vote taking place was a comparison with a parliament. Parliaments, it was explained to the chairperson, always choose between two alternatives, they either accept or reject a proposal, and the scientific council acted like a parliament. However, the system whereby one always chooses between two alternatives also has drawbacks. For example, the order in which the alternatives are put to the vote has a marked effect on the outcome. Let us look again at the example of the marquis de Condorcet. Assume that the first vote is between A and B, and the winner then stands against C in a second vote. The result will be that C is successful. If the first vote is between B and C, and the winner stands against A, A will win. This gives considerable power to whoever determines the agenda.
Some interpretations of Arrow's result are indeed far-reaching. In some cases the blame may be put on a formulation of the result that, from the logical aspect, is equivalent to Arrow's result but is such that it is likely to divert the users in very different directions. Instead of claiming that there is no system of voting that satisfies all three of the requirements listed above, it can be claimed that if we want to fulfill requirements 1 and 2, we must agree that the rating will be determined by a single elector, a
dictator. As axioms 1 and 2 are so elementary, the distinction is interpreted as meaning that the options are either allowing for a dictator or ignoring the mathematical analysis. I can illustrate this with a real instance that I witnessed.