Thomas Cool, February 12 & 18 2002
Thomas Cool Consultancy & Econometrics
Scheveningen, Holland
http://thomascool.eu, cool / AT / dataweb.nl
JEL A00
Summary
Theory shows that voting is subject to paradoxes, while
it also appears that a voting result is as much caused by the used procedure
as by the voters’ preferences. From a moral point of view, the choice of
the procedure then naturally is the major issue. A key insight is that
morality presumes time. In a static world everything is given, and there
is no place for individuals who have to ponder their moral choices. The
real world is dynamic however, and the most challenging voting paradoxes
concern budget changes. The paper develops a new "Borda Fixed Point" mechanism
that provides a better protection to surprises by such budget changes.
The analysis is put into context with a review of the proper meaning of
Kenneth Arrow’s Impossibility Theorem and a review of Donald Saari’s argument
on symmetry.
Introduction
Kenneth Arrow (1951, 1963) presented an Impossibility Theorem in which he showed that decisions about ‘the general welfare’ are impossible in certain cases or have to be left to a dictator. Arrow presented some five axioms that each seemed reasonable when considered by itself, and he argued as well that these axioms are morally desirable and fitting to the concept of ‘general welfare’. He also formulated the problem in general terms so that it concerns choices on goods or people. Subsequently, he derived a contradiction. This result caused quite some consternation, but eventually the mathematical rigour caused acceptance, and since then the Theorem forms the core of many books, such as Sen (1970) and Mueller(1989). The Theorem was also one of the reasons to award Arrow the Nobel Prize in economics.
A voting example is given by the US Presidential election of 2000. Apart from the problems around the ballot process itself, there was a more basic problem: with main contenders Bush, Gore and Nader, Bush got elected, but in another system, such as a runoff between the two ‘major’ contenders, the Nader vote apparently would have switched largely to Gore, making him the US President. So the choice depends as much upon the system chosen as on the preferences. Can we find a generally good system ? Arrow’s Theorem suggests ‘No’.
Arrow’s Theorem has had a huge influence on scientific and political thought. Part of this influence is subtle, where skepsis arises about the concept of ‘democracy’. That shiny goal loses its appeal when we don’t know how people should be elected, and when morally desirable rules would be impossible. Opting for the natural forces in the social process may be more pragmatic. The influence of the Theorem can sometimes be more explicit. Next to the model of the utility maximising individual, there is the model for society as a whole and then the maximisation of a Social Welfare Function (SWF). But when a morally acceptable SWF is impossible, what would be the use of research into such an inherently flawed concept ? Many nations coordinate their economic policy, and have created institutions for this, like the Council of Economic Advisors (US), the Commissariat du Plan (France), the Sachverständigenrat (Germany), and the Central Planning Bureau (Holland). Such an institution, given its role in the coordination of economic policy, could be expected to reseach the national SWF. However, those institutions tend to abstain from that kind of research, pointing to Arrow’s Theorem as one of the arguments, if not the major one.
In this manner an ‘accepted view’ has grown over the years concerning the meaning of Arrow’s Theorem. This accepted view however has also implied a kind of moral stagnation.
As shown in my book "Voting Theory for Democracy" (Cool (2001)), there are two main reasons to reconsider the accepted wisdom on the meaning of the Theorem, and to rekindle the debate on it. The first reason is destructive, since it rejects Arrow’s position; the second reason is constructive, since it provides an alternative. These reasons are: (1) There is a distinction between the mathematical framework on one side and its interpretation on the other side. The Theorem holds, and the impossibility holds for Arrow’s axioms, but the questions of reasonableness and moral desirability are of a different kind. (2) The area of application of Arrow’s axioms seems rather static, while reality is dynamic. By considering the role of time, there is more scope for morality.
This paper will summarise these two arguments in this
order. Readers interested in more details are referred to the book. For
clarity: the book does more than these two points. It develops the theory
of direct single seat elections from the bottom up, while it also provides
programs (in Mathematica) to eliminate the tedious work of the calculations
of the various voting procedures.
Rationality
When Arrow’s axioms would be reasonable, then they would have to be consistent as well. However, they are inconsistent. Thus they are not reasonable. This seems a rather simple scheme of reasoning, but it destroys the impact of the Theorem.
For the axioms, there is the subtle difference between ‘reasonable’ and ‘seemingly reasonable when considered by itself’. The following is a good analogy. For a bicycle we want round wheels for when it rides. For a bicycle we also want square wheels, so that it does not fall when it stands still. But there are no round squares ! Ergo, conditions that seem reasonable by themselves, create something impossible and decidedly unreasonable when combined. To conclude ‘there is no good bike’ would however be absurd. Admittedly, it is a good teaching method to first convince students that something would be reasonable, and then have them derive a contradiction. As with the buying of a bad secondhand car, the students learn to be careful, and they learn a respect for science and the value of modesty. This teaching method however overshoots when people remain believers of the reasonableness of the assumptions  as apparently happened with the assumptions of Arrow’s Theorem. A paradox is only a seeming contradiction, and there must exist a system that we are willing to accept as the optimal one.
Many mathematicians have been sensitive to the distinction between ‘reasonable’ and ‘seemingly reasonable when considered by itself’, but the literature also abounds with instances where this distinction is not applied with sufficient care. Part of the accepted view thus is a case of bad communication of the profession with the general public. (Though there are also ‘professionals’ who are misguided  and then the question is how to determine who are the real professionals. Quis custodet custodes ?)
Morality
Morality arises when preferences acquire an imperative weight. ‘You should not kill’ is more imperative than ‘John prefers cheese over candy’. Preferences and moral principles however can be depicted with a single utility ordering, which then becomes ‘lexicographic’ to express the point that moral principles come first. Using deontic logic, i.e. the logic of morals, on these orderings shows that Arrow’s Theorem causes a contradiction within morality as well, so that the axioms should be rejected also for this reason.
The moral argument has the same structure as the argument on rationality. When the axioms would be morally desirable, then the derived contradiction would be morally desirable  but nobody can be asked to do the impossible. Hence the axioms are not morally desirable. Again a seemingly simple reasoning scheme, and again it is destructive to the accepted view.
See Cool (2001) for the formal development of deontic logic, that leads to the rejection of Arrow’s metamathematical interpretation.
Our interpretation of the situation thus changes. The
currently accepted view is sometimes expressed as that ‘there is no ideal
voting scheme’. This however is wrong. Since the axioms must be rejected,
they do not form an ideal. An ideal still can exist, but apparently it
is different than originally thought.
Constructive
The arguments above on rationality and morality have a destructive character since they reject the accepted view. In another perspective they are constructive, since they allow the formalisation of metamathematical notions, and bring these back into mathematics again. Indeed, it appears possible now to show formally  see Cool (2001), chapter 9.2  that the accepted view does not stand.
This does not answer the positive question yet what would be a generally good system. The main point here is that everyone should determine this for oneself. Theory can only help to remain consistent.
One important idea is that time plays a role. The basis for this idea is that, abstractly, morality presupposes time. Without time there would be no morality. In a static world everything is given, and there is no place for an individual who has to ponder his or her moral choices. As economists, we can draw static utility functions and isoquants, but those are abstractions, and they might distract from the real moral problem. The moral problem is that now a decision has to be made while the consequences appear later. Afterwards, everything can be explained deterministically (which is the meaning of ‘explanation’), and by hypothesis, determinism will also hold for the for the future. Yet, in the mean time forecasts are imperfect, there is fundamental uncertainty, and that creates the possibility of morality (or the illusion of morality).
Economic science is intended to help explain reality. In this reality, we see an evolution of human beings in a social process of natural forces. The basic concept is power, in a continuous process, so that the basic approach uses ratio scales and cardinal utility and not ordinal scales. Other assumptions than cardinality enter the discussion only when the group wants to control power, and for example introduce democracy. A common notion is that economists reject cardinality and interpersonal comparison of utility. However, the concept of ‘one person, one vote’ actually imposes an interpersonal comparison of utilities. Also comparing orderings of preferences implies some comparison of utilities. The proper perspective is rather that cardinality is deficient since people can cheat about their preferences (at least in the current state of technology). The major argument for ordinality is that it limits the room for cheating. If people could not cheat, interpersonal comparison likely would be much more popular amongst economists. That ordinality reduces interpersonal comparison thus seems less relevant than the point that cardinal comparisons are unreliable since people can cheat.
For example, when a family goes on holiday and has the choice between Spain or Greece, then little Robby might exaggerate his preference for Greece and say that he might as well die when Spain is selected. When the aggregation of preferences would be cardinal, such a huge negative weight for one option would certainly block it. Imposing ordinality limits the impact of cheating however. In common textbooks on voting theory, cheating comes in relatively late, but it is more adequate to start right away with that notion. The crucial insight is: Arrow’s Theorem and the voting paradoxes are the price that we have to pay in order to limit that impact of ‘stategic’ voting behaviour.
Arrow’s orginal question whether there could not exist
a generally good voting mechanism remains a valid question, though. As
history has shown, mathematicians are proficient in identifying paradoxes
and in deriving new impossibilities, and one will not quickly find a suggestion
for a generally good system. But it appears that when we consider the issue
of time, then a solution tends to suggest itself. To understand this solution,
it is useful to first consider three main contenders, i.e. the ‘traditional’
solutions provided by Plurality, Borda and Condorcet. There are other methods,
but their properties are such that they need no consideration here.
Three traditional methods
In Plurality, all voters have one vote, and the candidate with the highest number is selected. Note the problems with this method. The criterion of ‘highest number’ does not imply that the winner must also have more than 50% of the vote. If this is additionally imposed, then this may require more rounds of voting, and then there is the difficult issue whether candidates have to drop out, and if so, how.
Borda’s method is to let each voter rank the candidates by importance, then assign weights given by the rank position, to add the weights per candidate for all voters, and then select the candidate with the highest value. Note that the method appears sensitive to preference reversal, see below.
Condorcet’s method is to vote on all pairs of candidates, and to select the one who wins from all alternatives. Note that such a "Condorcet winner" does not need to exist. In that case the margins of winning can be used to solve the deadlock  but this increases the sensitivity to who participates.
An example can help. The following is taken from Saari
(2001ab). Consider a budget of three candidates A, B and C,
and let there be 114 voters. Table 1 contains an arbitrary allocation of
those voters and their preferences. With 3 candidates, there are 3! = 6
possible ways of ranking them (where we neglect indifference and only use
strict preference). The highest ranking candidate gets rankorder weight
3, the second gets weight 2, and the least preferred candidate gets weight
1. In the table we can read for example that there are 33 candidates with
preference A > B > C.
Table 1: Voting example
Candidates and their rank order weight  
Number of voters 



33 



0 



25 



17 



14 



25 



Plurality total 



Borda weighted total 



A versus B 



A versus C 



B versus C 


The different voting schemes result into different decisions:
Fixed point Borda
Let us reconsider the dynamic process that occurs within an economy. We see that under the influence of time, the budget changes continuously. A voting scheme naturally requires that there is a list of candidates, but one cause for paradoxes is that that list is not fixed. For example, in the Borda vote above, B is selected, but if C decides to withdraw, then we would expect B to remain the winner, but suddenly it is A (see the Condorcet vote A versus B). Remember also the Bush, Gore and Nader case. We could consider a procedure to be better when the choice is less dependent upon changes in the budget.
A way to achieve this is to use the notion of a ‘fixed
point’. For a function f: D ® R,
for some domain = D = range = R, that point p is a
fixed point iff f(p) = p. Let us consider this concept for voting.
Let P be the voting procedure, and let X = {x_{1},
..., x_{n}} be the budget with all the candidates. Let the
winner be w = P(X). Let Y be the budget
when w does not participate, Y = X \ {w}. Let
the ‘alternative winner’ v(w) be the candidate who
wins when the first winner w does not participate, so that v
= P(Y). This alternative winner can be seen as a ‘summary’
of the opposition to w. The ability to win from the alternative
winner can be seen as an additional condition for winning in general. This
gives the fixed point condition:
w = P(w, v) = P(w, P(X \ {w})).
Note that we can define f(x) = P(x, P(X \ {x})), which is the general function ‘the vote result of x and its alternative winner’. In the above, w would also be the solution to the fixed point condition x = f(x). However, when w is not a fixed point, i.e. when the unrefined winner w = P(X) appears to lose from v, so that w ¹ P(w, v), then the search process can start again from v.
It appears that this fixed point voting procedure reduces the dependence upon budget changes. There can still be a dependence, but it is not as large as without the condition. The Fixed Point Borda scheme also appears to be a compromise between Borda and Condorcet, since the Borda scheme is used to start the search, and the Condorcet pairwise condition is included as a criterion (for the winner and the alternative).
In Table 1, the Borda Fixed Point winner is A. With B the Borda winner, A is the alternative winner when B does not participate, and B loses from A in a pairwise match; starting the search from A, then its alternative winner is B  and A wins from B.
Note: Cool (2001) also is intended as a textbook, and
it developed Mathematica programs for the various voting schemes
and data manipulations. Given the complexity of the matter, this working
environment has appeared a great advantage.
Relation to Saari’s work
Donald Saari (2001ab) showed that Borda’s method is the only method that satisfies certain symmetries, and he suggests that the Borda rule ‘therefor is best’. This argument does not convince me since ‘symmetry’ is not by itself a moral category. Dynamics is linked to morality, by the notion that morality presumes time, and thus seems a better angle.
Consider direct symmetry first. Suppose that your preference is A > B > C and that my preference is C > B > A. The direct symmetry consideration is that we might both abstain from a vote and stay home, since our preferences strictly oppose each other. You may check that also the Borda Fixed Point method allows for this symmetry.
Saari noted that voting cycles can be catalogued under the mathematical concept of rotational symmetry, and his suggestion is that cancellation should hold for all symmetries for all subsets of voters. The discussion here becomes a bit more complex because of semantics. Some clarification of terms is required.
Consider the typical Condorcet problem when there are three preferences A > B > C, B > C > A and C > A > B. Pairwise voting results in majorities for A > B, B > C and C > A, which is called a ‘cycle’. As an aggregate preference, this result can only be understood as a deadlock or indifference. These votes can be seen to cancel each other. Note that pairwise voting does not allow this conclusion of indifference  and this omission has been a long standing argument, also by me, that Arrow’s Theorem is not so useful since it so relies on pairwise methods.
So I tend to agree with cancellation of votes for the
whole budget set. What happens when cancellation of ‘rotational symmetry’
is also applied to subsets ? The following is an example by Saari that
cancellation then no longer is trivial. In Table 2 there are 48 voters,
and B is selected by both Borda and Condorcet. In Table 3, 27 voters
are added who have the mentioned rotational symmetry, with 9 for each subgroup.
Now Borda still selects B, but Condorcet, and the Borda Fixed Point,
select A. In Saari’s view, Borda satisfies symmetry, and ‘hence’
is the better method.
Table 2: Start with 48 voters: Borda B, Condorcet B
Candidates and their rank order weight  
Number of voters 



20 



28 



Borda weighted total 



A versus B 



A versus C 



B versus C 


Table 3: Add 27 ‘neutral’ others: Borda B, Condorcet A
Candidates and their rank order weight  
Number of voters 



20 



28 



9 



9 



9 



Borda weighted total 



A versus B 



A versus C 



B versus C 


My reasoning is a bit different. Note that I myself have used an argument similar to that of Saari. In my view, the typical Condorcet situation of A > B > C, B > C > A and C > A > B results into indifference rather than a cycle; and I use this against Arrow’s analysis. So I agree with Saari’s point of view that such votes cancel. I applaud Saari’s mathematical insight, that if you apply cancellation for all cycles in all subsets, then the logic is to get rid of Condorcet’s method and to use Borda’s method. My problem however is that there is the additional problem of budget changes. The Borda method would be best, only when the budget would be really given. When it might change, the application of cancellation to all subsets becomes doubtful.
There is a fundamental uncertainty with respect to the future. Consider the following example. At a specific point in time, the population of a nation is given, and thus the vote for a President has a specified budget: the population. But, uncertainty sets in again, when people may withdraw from the race. Hence, we might well want a rule to deal with possible changes in the budget. Hence, it is not logically required that we cancel votes for all possible subcycles (also for candidates who are not in the race). Saari is very strong on the argument that when we accept cancellation in one case, then we should do so in all cases, but I am more sensitive to the exception, and that not all cases are the same.
Concering Table 2 and Table 3, my reasoning is  contrary to Saari  that the added votes cannot be neglected. The argument of rotational symmetry breaks down when we compare a winner with the alternative winner  which is a pair  while rotational symmetry requires a third candidate or more. For the pair, the addition has an effect. When we consider unrefined winner B and its alternative winner A, then the added votes are in favour of A and no longer ‘neutral’. While C is important since it shows a cycle for a subgroup of voters, another view is that C could be neglected since it is not a fixed point. Canditate C is a typical example of an irrelevant candidate that can cause a preference reversal in Borda voting. Namely, let us consider Table 3 under Borda voting, and let C decide to drop from the race: then A becomes the winner. The Borda Fixed Point method has been developed precisely to deal with that kind of preference reversal.
When you select your voting method then you thus must choose between the properties exemplified by this case. (1) Borda is subject to preference reversal. In the example of Table 3, when C drops out, then there would be switch from B to A. (2) The Borda Fixed Point method still depends upon the voting field. In this example, when 27 voters drop out, then there is a switch from A to B.
The choice basically is whether we attach more importance either to the voters or to the candidates. Saari suggests that the candidates are more important, since he cancels the votes of 27 voters and keeps C in the race. I would say that the voters are important and that candidate C is less relevant. The proper question would be whether the winner is a convincing winner. Of course, C can become an important candidate when we add other voters. But then the argument is that those voters count, rather than C.
Consider the importance of these semantics. While it has been a long standing notion that Condorcet type cycles may also be taken as indifference, so that the votes cancel, Saari now rephrases this as rotational symmetry, and he suggests that acceptance of rotational symmetry implies acceptance for all cases and subsets. The label might be a common mathematical label, but I have a problem with that label in the realm of morality (and the implied universality). Human beings seem to have biological preference for symmetry, and by labelling something as ‘symmetry’, it becomes more attractive. When discussing the different voting schemes, we should be aware of such effects, and try to focus on what the properties really mean, and we should make a proper distinction between a property that is universal and a property that is dependent upon the situation. Perhaps it might be analysed as the ‘mathematical frame of mind’ that acceptance of a property for one set also implies acceptance for all other (sub) sets, but my conclusion is that when we look closer, that there is room for more subtlety.
Another example for this need for subtlety is that the ‘rotational symmetry’ argument breaks down on the status quo (see below).
Note: Saari has also developed an ingenious way to depict
voting schemes geometrically. For 3 candidates, this becomes a triangle,
and the different procedures can be calculated from that. It appears that
these triangles are a good educational tool. However, my experience is
that the computer programs (Cool (2001) uses Mathematica) are easier
to use, since they take away the need for calculations, are available for
more dimensions, and also allow for indifference and not just strict preference.
A more complicated scheme like the Borda Fixed Point also requires more
work with the triangle, while it is a simple procedure call. Of course,
the theory should be developed fully mathematically. Some points are in
the appendix.
Pareto
Another consequence of the switch from statics to dynamics is the recognition of a status quo.
There appears to exist another widespread confusion about ‘majority voting’. This idea is that a majority result like Borda or Condorcet, even over a simple binary pair A versus B, still would be democratically valid, even if the winner implies a real loss for the opposition (and not just the loss of the election). The obvious example is when the majority decides that the minority pays $1 to the majority: this is not necessarily a morally acceptable situation, even though there is a majority. On the contrary, from a moral point of view, each voting scheme should have a first round to select the Pareto improving points compared to the status quo. In elections of persons, the status quo can be a vacancy, and in that respect all candidates could be taken as Paretian. But the Paretian precondition cannot be skipped in general.
The Paretian condition may require some subtlety. Consider the family choice for a holiday to Greece or Spain. If little Robby considers the holiday to Spain to be a deterioration from the status quo of not having a holiday at all, then there is moral argument to say that Spain is not a valid option to take a vote on. However, if it can be established in a first round that going on a holiday is unanimously a good idea, then Robby has to accept a possible majority decision in favour of Spain and against Greece. Note that, in that sense, a majority rule is only a tiebreaking rule for the deadlock when there are more Pareto improving points.
One argument against the selection of Pareto improving
points is that people might also cheat about these points. This argument
is not convincing, since Pareto improvement is in one’s own interest. Indeed,
little Robby might try to veto Spain by saying that he does not want a
holiday, and thus he might be trying to bargain to get everybody to accept
Greece. However, this ploy can be prevented by having that first round
on having a holiday, since if he really wants a holiday anyhow, then he
has to show this then. Careful construction of the voting process thus
remains an issue.
Conclusion
An election result is as much the result of the selected procedure as of the preferences. Arrow’s Impossibility Theorem is complex and full with paradoxes, but the dependence of morality upon time provides a way towards solution.
There are two key conclusions:
Literature
Cool, Th. (1997), "The solution to Arrow's difficulty in social welfare", ewpget/9707001, included in Cool (2001) as chapter 9.2.
Cool, Th. (2001), "Voting theory for democracy", www.dataweb.nl/~cool en www.gopher.nl
Mueller, D. (1989), "Public Choice II", Cambridge
Saari, D. (2001a), "Chaotic elections", AMS, 2001, www.ams.org; or
Saari, D. (2001b), "Decisions and Elections. Explaining the unexpected", CUP
Sen, A. (1970), "Collective choice and social welfare",
North
Holland
The following is not complete but will help to understand the fixed point issue formally.
Let {.} denote unordered lists and [.] denote ordered lists. Let X = {x_{1}, ..., x_{n}} be the budget with all the candidates. Let there be m voters with preferences P = {p_{1}, .., p_{m}}, with p_{j} the preference list for voter j. An individual preference is an ordered list, with the best last, and with the possibility of indifference. For example for three candidates, [B, {A, C}] means that B < A, B < C, and A = C. The rankorder weight of the candidate is the position in the ordered list, with average values for indifference.
For a voting procedure, we should write P with subscriptP, since the procedure outcome depends upon the state of preferences. With that understood, it suffices to write P. The domain of a voting procedure P is not just the single set X itself, but also its subsets, since we also want to vote on a winner and the alternative winner etcetera. The range is neither X itself, since we allow for ties. Hence P : 2^{X} ® 2^{X} where 2^{X} is the set of subsets of X. Thus w = P(X) ÍX.
Ties thus cause these problems: (a) They destroy the simplicity of the math of unique winners. We cannot use Î but have to use Í instead. (b) Introduction of ‘tiebreaking rules’ can restore that simplicity, but also introduces a degree of arbitrariness (die, chairperson, ...). Such rules also generate paradoxes again, but then those are no argument against the overal voting method.
Voting procedure P is a ‘social decision function’ (SDF) that selects only the winner(s). Next to that there is the ‘social welfare function’ (SWF) that gives the aggregate preference ordering. These are intimately connected. Each SWF generates a SDF  namely take the top of the list. Each SDF generates a SWF, namely by subsequently eliminating the winner of the remaining budget. The aggregate ordering for P is [..., P(X \ P(X)), P(X)]. The ordering thus depends upon the budget (which is a better summary than Arrow’s conclusion of ‘impossibility’). Note: For the Borda scheme, the first voting round also suggests an ordering of all candidates, but the method of subsequently eliminating winners can generate a different ordering. The elimination method would be better from the viewpoint of budget changes.
The implied ordering suggests the concept of the ‘alternative winner’. The alternative winner of x ÍX is v(x) = P(X \ x), and P’s implied ordering is [..., v(w), w].
An intuition is that the winner w ‘represents’
the budget X. The representation can be denoted as w ÛX.
Representation
w Û X.
is used in an ‘up’
direction, but it can also be tried in a ‘down’ direction within a budget,
for example as X Ûx
È
v(x) for any xÍX.
The set x È v(x) can also
be represented by its winner f(x) = P(x
È
v(x)). Hence for any subset
x we have w ÛX
Ûx
È
v(x) Ûf(x). This
holds in particular for w, and then taking representation as transitive:
w Û f(w)
This inspires us to consider the ‘fixed point’ set, solved from z = f(z), though it need not be the case that z = w. Being a fixed point seems like a property of a ‘strong’ winner, since it means winning from the alternative winner when one would not participate, and, being the representation of the whole group, one would represent oneself. The basic argument is that the fixed point allows more protection against budget changes. In this way, the intuition of representation inspires the acceptance of fixed pointness as a criterion for electoral strength (replacing Û with =). A procedure P generates an associate fixed point procedure P’ with ordering [..., P’(X \ z), z]. Note that always a P’ is possible such that fixed points are generated. For example, when there is an epicycle, such that A wins when B does not participate, and that B wins when A does not participate, then z = {A, B} = P’(X).
The following comments concern practical computing.
The fixed point condition allows any subset. For a global search, raw computing power can be used to test every subset of X on the condition z = f(z). My suggestion and hope is that other theorists look at ways to do this more efficiently. It might suffice if an efficient theory is developed only for the Borda method.
The ‘Borda fixed point’ procedure implemented in Cool (2001) uses, as said, a local scheme starting at the top. Note also that the fixed point concept does not necessarily imply pairwise voting. In the case of ties, the z È v(z) can have more than two elements. But the pairwise approach would often be most useful for practical algorithms. The implemented method then is:
For curiosity’s sake, the issue of the global search can be looked into. The following comments are to indicate the problem.
A global search would accept any SWF ordering that results into [..., v(z), z] for any fixed point z. The problem is that we could start with sets of any size, either at the bottom or at the top.
For example, we might use pairwise comparisons that start at the bottom and branch out over the possible combinations. Such trees are known for finding the voting strategy in standard pairwise voting, but we can also introduce a branch count, and then get a different implementation of pairwise voting. Let a winner earn 1 point for each branch won, and let a tie earn the average value. When voting over a pair {t, u} then it suffices that one item has a majority larger than 50%, and the size of the winning margin has no impact. When there is a Condorcet winner, then it wins each branch. If there is no Condorcet winner, then the item with the largest branch count could be taken. (The winning margins might however be useful again when there are ties.)
For example, for X = {r, s, t, u}, we get
the following tree. The first row is evaluated in this fashion: first the
winner of {t, u} is determined, then compared with s, and
the winner of that is compared to r.
Table 4: Pairwise branching of 4 elements
r  s  t  u 
r  t  s  u 
r  u  s  t 
s  r  t  u 
s  t  r  u 
s  u  r  t 
t  r  s  u 
t  s  r  u 
t  u  s  r 
u  r  s  t 
u  s  r  t 
u  t  r  s 
For example, when there are three equal voters with preferences
[2, 4, 3, 1], [4, 1, 2, 3], [2, 1, 3, 4], the branch winners are [r,
[r, t, u], t, u], meaning (a) that r wins in the first
three rows, (b) that [r, t, u] win respectively in the next three
rows, (c) that t wins in the third three rows, and (d) that u
wins in the final three rows (branches). Then r, t, u all have a
branch count of 4. They come out equally with each a share of 1/3 of the
vote. Borda and the local Borda Fixed Point method also find this result.
This however is not always so. Consider the same tree but now with five
equal voters, with 3 having preferences [4, 3, 2, 1] and 2 having preferences
[1, 4, 2, 3]: then all brances give r, which then is the Condorcet
winner. Borda would give s, but the local Borda Fixed Point is r
as well. Another example is this however. Let the items be {u, v, x,
y, z}, with a tree that has 5 times more branches, and let there be
three parties with weights [.4, .4, .2] and respective preferences [1,
5, 2, 3, 4], [1, 2, 4, 5, 3], [1, 3, 5, 2, 4]. There is no Condorcet winner,
Borda gives {y, z}, the local Borda Fixed Point gives {x, y,
z}, and the pairwise tree gives the result that x has a (perhaps
less convincing) maximum score of 11/24.
All this is to show the complexity of a global search. We have used pairs now, but the true aggregate ordering [..., v(z), z] may have different steps than pairs. The conclusion is that, if one would be interested in the global condition, then it is more efficient to do research on the method that starts at the top, and to determine whether the local search can find the global result as well and quick enough.