VOTING PROFILES WITH DISJOINT CONDORCET CYCLES
by
DAVID ALAN SUTHERLAND JR.
B.S., Metropolitan State College, 1987
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Mathematics
1996
This thesis for the Master of Science
degree by
David Alan Sutherland Jr.
has been approved
by
Stanley E. Payne
'tpv Â£
Date
DEDICATION
I dedicate this thesis to my parents and grandparents in gratitude for what they
have given me.
David Alan Sutherland
Frances Sutherland
James Glenn Sutherland
Nina Geneva Sutherland
Ramon Palomino Guerrero
Josefa De La Torre Guerrero
Sutherland, David Alan Jr. (M.S., Mathematics)
Voting Profiles With Disjoint Condorcet Cycles
Thesis directed by Associate Professor William E. Cherowitzo
ABSTRACT
Condorcet voting can be used to order all the candidates or alternatives in an
election; however, Condorcet voting is not always successful in producing such
an order but may instead result in the voting paradox which is also called
Condorcet's paradox. This thesis discusses the interrelationships amongst
Condorcet voting, tournaments of graph theory, and the algebraic structure of
latin squares. The notion of pgroupoids is developed and it is shown how
these algebraic structures decompose complete graphs of odd order into disjoint
cycles. The thesis then shows the relationship between idempotent symmetric
quasigroups and pgroupoids. This relationship is then exploited to construct
voting profiles which, under Condorcet voting, produce the Condorcet paradox.
IV
This abstract accurately represents the content of the candidate's thesis. I
recommend its publication.
Signed
CONTENTS
Chapter
1. Introduction ......................................................1
2. Preliminaries......................................................6
3. Condorcet Voting, the Condorcet Winner Criterion, and the Condorcet
Paradox (Condorcet Cycles) .......................................11
4. Tournament Representation of Condorcet Voting.....................18
5. Square Voting Profiles, Hamiltonian Cycles, Latin Squares, and
Rotational Tournaments ...........................................26
6. Algebraic Structure of Latin Squares .............................35
7. Decomposition of Prime Order Latin Square Profiles into Disjoint
Hamiltonian Cycles ...............................................39
8. The Construction..................................................46
References .............................................................53
VI
1. Introduction
This thesis investigates the interrelationships among discrete structures
connected with Condorcet voting such as latin squares and quasigroups, and
tournaments, a topic in graph theory. In particular, this paper describes a
method to construct square voting profiles of odd order that yield an extreme
form of the paradox that can result under Condorcet voting. Condorcet
voting stems from the idea that a candidate that wins all pairwise elections
against the other candidates should be elected.
The Condorcet voting procedure was first described by John Charles
Borda, a French scientist who lived during the end of the 1700's. In the
literature of voting theory, Borda is best known for the social choice function
which bears his name, the Borda count, see chapters 2 and 3 However,
Borda had a wide and varied adult life. He was an officer in the French
navy and also served as a soldier, even serving for a time with French forces
aiding the American revolution. He is mostly known for his contributions to
fluid dynamics, navigation, and the development of the metric system.
Toward the end of his life he was a member of the French Revolutionary
Committee on Weights and Measures from which sprang the metric system.
1
He also developed trigonometric tables during this time as an aid to
navigation. Although bom to the nobility, Borda did not seem to suffer any
tragic consequences due to the French Revolution.
Borda was not satisfied with the Condorcet voting scheme since it did
not always work, that is, it sometimes does not give an answer or even a tie
result. He later developed his (Borda count) system, which always yields a
result which could be a tie. It is interesting that the Borda count is not
necessarily compatible with Condorcet voting, see chapter 3. [9]
Borda is contrasted with his contemporary Marie Jean Antoine
Nicolas Caritat Marquis de Condorcet, a mathematician and philosopher of
the enlightenment. Bom to an important aristocratic family, Condorcet was
known for his progressive views. He supported enfranchisement of women,
advocated abolition of slavery, was in favor of free speech, and supported the
American revolution. He was widely known to be sympathetic to the
suffering of the French people and called for the end of compulsory labor.
Because of these attitudes he did not suffer because of his noble birth during
the revolution, at least at first. He became heavily involved in politics after
the revolution. He represented Paris in the Legislative Assembly after the
revolution and was presiding officer of that body for a time. He was
instrumental in the establishment of a republic and the educational systems
2
which came about after the revolution (and after Condorcet's death).
Condorcet drafted a constitution for the French Republic, but this was
rejected in favor of a constitution drafted by the radical Jacobins whose
leader was Maximilien Robespierre. The ascendancy of the Jacobins saw
Condorcet and many of his fellow and more moderate Girondins outlawed
and arrested. Condorcet was arrested after an extended period in hiding
during which he wrote some of his most important philosophical works. He
died in prison probably by his own hand.
Condorcet accepted the principle of the voting system which carries
his name. He proposed that any voting system which did not select a
Condorcet winner when one existed should not be adopted. He was critical
of the Borda count for this very reason.
Condorcet was critical of Borda in general as an experimentalist and
even denounced him in the French Academy of Sciences as having
abandoned the philosophical purity of mathematics for the pettiness of the
applied sciences [1].
Since this era, the problem with Condorcet voting, usually referred to
as the Condorcet paradox was rediscovered every few years and many
solutions have been offered to fix the problem.
3
This thesis does not offer a solution but examines aspects of a
restricted domain of the Condorcet social choice function. Condorcet voting
is applied to finding an acceptable ordering of candidates or alternatives. A
situation is cited in which no ordering is possible and a method of finding
such situations is demonstrated.
Preliminaries of voting theory which are important to the
developments in the paper are given in chapter 2. Chapter 3 describes the
Condorcet phenomenon and related topics in detail. The tournament
representation of Condorcet voting is shown in chapter 4 with several results
from graph theory which have direct consequences to the Condorcet problem.
In chapter 5 is a discussion leading to the problem of finding voting profiles
which lead to disjoint hamiltonian cycles. This chapter also describes the
results of a computer search to examine the cyclic structure of certain square
voting profiles. Chapter 6 shifts gears to a discussion on the structure of
latin squares which is preliminary to the construction of a voting profile with
disjoint hamiltonian cycles. Chapter 7 introduces pgroupoids and shows that
these structures decompose complete graphs of odd order into disjoint
hamiltonian cycles. This chapter also shows the relationship between
pquasigroups and idempotent symmetric latin squares which is the main tool
used in constructing the desired voting profiles. And finally, chapter 8
4
shows the constructions of the desired square voting profiles of order 5 and
of order 7.
5
2. Preliminaries
Let A = {a^ a2, am} be the set of m alternatives or m candidates
presented to a society for decision (or priority ordering). The set A is also
called the choice set. The society, committee, or voting body, is indexed by
a subset of N, the natural numbers, {1, 2, ..., n) where n is the size of the
society.
Assume that an individual in the' society can rationally order the
alternatives in accordance with her own personal preferences and that such an
ordering is independent of the orderings by the other voters. Each such
preference order, p, is a total order (linear order) on A which is a relation R
on A which is
irreflexive: (a;, a;) g R for all a{ e A;
antisymmetric: (a;, ap e R implies (a^ a;) g R; and
transitive: (aj5 aj), (aj5 ak) e R implies (ai5 ak) e R.
Note that antisymmetry implies that "ties" are not allowed in the preference
order. The usual notation is a; > aj if (aj5 aj) e R and is read "a, beats a^" or
"a; is preferred to a^" The preference order, p;, for the i* voter, can be
represented as the column vector
6
Pi =
a:
a,
(2.1)
z
\ w
where the candidate on top is the most preferred by voter i. A preference
profile is an assignment of preference orders by the members of the society
from the set of permutations of the choice set (candidates). A preference
profile will be represented by an m x n matrix where each column, i, is the
preference order for the ith voter.
The major goal in studying social choice or voting theory is to
produce a social ordering of the alternatives from the preference profile that
reflects "the will of the people." This social ordering is a preference order
with the same qualities as the individual preference order above, although
antisymmetry is usually relaxed, that is, tie results are allowed (the order is
actually a partial order with symbol <). The notion of "the will of the
people" rests not only upon the confidence of the voters that the result is true
but also on the voter's trust in the honesty of the results, that is, that the
results were not altered by manipulation due to the choice of the voting
7
method or by strategic voting, which means that some voters vote other than
how they feel to obtain a desired result.
A social choice function is a function from the set of preference
profiles to the set of permutations of the choice set, A. The social choice
function is the voting method that produces the desired social ordering.
These functions are also called social welfare functions. Since a social
choice function produces a social preference order on the choice set, then any
subset of the choice set will also be ordered. Examples of social choice
functions are plurality, the Borda count, the Hare system, and a dictator.
In plurality voting, given a preference profile, the alternative with the
most first place votes has the first place in the social preference order.
Another round of plurality voting on a reduced preference profile fixes the
second place of the social order. This second preference profile is made up
of the same individual profiles with the winner removed. A third round on
another reduced profile fixes the third place of the social order and so on.
It is easy to see that ties cannot be avoided in plurality voting. In
practice, another social choice function would be used to break ties when
necessary: for example, a runoff election or vote, or even a coin toss.
The Borda count is a weighted voting scheme, or a scoring function
[11]. The position of an alternative in an individual's preference list
8
determines the weight assigned to that alternative. The sum of all weights
assigned to the alternatives by the entire profile determines the social
ordering. In the case of the Borda count the scoring vector is
(m 1, m 2, m 3, ..., 2, 1,0) where m is the number of candidates. The
alternative in first place in a preference list would receive m 1 points and
the second m 2 points, while the last place candidate receives no points.
The points for each candidate are totaled with the order established by the
point totals. Simply, a; > aj if and only if candidate a; has more points than
candidate a^.
The Hare system is a sequential system which in modified form is in
use at present to decide elections in several countries. If one candidate has
more than half of the first place votes, then that candidate is assigned first
place on the social preference order. If not, then all candidates which do not
have a first place vote in the profile are eliminated from further consideration
for first place and the reduced profile is examined. The candidates with the
least number of first place votes are eliminated. The resulting reduced
profile is examined for a candidate that now has more than half of the first
place votes. If there is no such candidate, again, the candidates with the
least number of first place votes are eliminated. This procedure is continued
until a winner is produced. Then the original profile is reduced by the
9
candidate(s) that have already been selected. The entire Hare process is
repeated for each position on the social choice preference list until the choice
set has been prioritized.
If one of the voter's preference list always coincides with the social
preference list no matter what social choice function is used then that person
is a dictator.
10
3. Condorcet Voting, the Condorcet Winner Criterion, and the Condorcet
Paradox (Condorcet Cycles)
The Condorcet voting procedure was first discovered by Jean Charles
Borda but was later popularized by the Marquis de Condorcet and hence
bears his name. Given a preference profile, the Condorcet procedure selects
alternative a{ to be preferred over aj in the social choice preference list if and
only if a; > aj in more than half of the preference lists. If no such preference
exists then the social preference list determined by Condorcet voting does not
exist. For example, alternative 2 is the Condorcet winner, first place in the
the following profiles.
2 2 2 3 1
2 2 2 1 3 4 4 5
3 1 3 3 15 5 4
1 3 1 5 4 113 4 5 3 2 2
(3.1)
The alternative, 2, is the Condorcet winner since it beats every other
alternative in pair wise comparisons 3 to 0 in the 3 x 3 preference profile.
In the 5 x 5 profile alternative 2 beats every other alternative 3 to 2 since it
is first in three preference lists and last in two lists.
11
A related concept is that of the Condorcet loser. The Condorcet loser
doesn't beat any of the other alternatives in the pairwise comparisons over all
the preference lists, that is, a; is the Condorcet loser if and only if aj > in
more than half of the preference lists.
The Condorcet winner criterion is a property applied to the
comparison of social choice functions. Simply, a voting procedure satisfies
the Condorcet winner criterion if whenever the Condorcet winner exists then
the social choice function in question also picks that same alternative for a
winner. This appears to be a completely reasonable expectation of
prospective social choice functions. Unfortunately, the social choice
functions mentioned in the previous section do not satisfy the Condorcet
winner criterion [10]!
Theorem 3.1: The following voting procedures do not satisfy the Condorcet
winner criterion:
a) the Hare system,
b) the dictator,
c) the Borda count, and
d) the plurality procedure.
12
Proof: By contradictions: Consider this preference profile made up of 5
alternatives with 17 voters:
11111223334445555
2222 2 332222222222
33345444513333331
44534551455554443
5 5 453 1 15141111114
(3.2)
Alternative 2 is the Condorcet winner since it beats all other alternatives in
pairwise comparisons, by at least 12 to 5 (over alternative 1) and by at most
14 to 3 (over alternatives 3 and 4).
Consider this same profile under the Hare procedure. There is no
alternative that has a clear majority. So we must iterate through the Hare
process. Every alternative has at least one first place vote, so we proceed by
eliminating the alternative with the least number of first place votes, which is
alternative 2. Since alternative 2 is eliminated it cannot be the winner under
the Hare procedure. Therefore the Condorcet winner is not the Hare winner.
Consider this preference profile made up of three voters deciding
among three alternatives.
13
(3.3)
1 3 3
2 2 2
3 1 1
If the voter with preference list in the first column is a dictator then the
dictator chooses alternative 1 as the winner; however, the Condorcet winner
is alternative 3 since it beats 1 and 2 in two lists. So a dictator does not
always pick the Condorcet winner. In fact, in this case, the dictator has
picked the Condorcet loser.
Now, consider this preference profile of five voters on four
candidates.
1 1 1 2 2
2 2 2 3 3
3 3 3 1 1
4 4 4 4 4
Alternative 1 is the Condorcet winner since it beats alternatives 2 and 3, by 3
to 2 in the pairwise comparisons and alternative 4, by 5 to 0. Under the
Borda count alternative 1 has 11 points while alternative 2 has 12 points. So
alternative two is the Borda count winner. And the Borda count does not
satisfy the Condorcet winner criterion. Notice the presence of the decisive
Condorcet loser.
14
Finally, consider the preference profile of nine preference lists on
three candidates.
1 1 1 1 2 2 2 3 3
222233322
3 3 3 3 1 1 1 1 1
(3.5)
Candidate 2 is the Condorcet winner since it beats both candidate 1, by 5 to
4, and candidate 3, 5 to 2. Candidate 1 is chosen by the plurality procedure
since it has the most first place votes. So plurality does not satisfy the
Condorcet winner criterion.
Is there any social choice function that does satisfy the Condorcet
winner criterion?
Sequential pairwise voting is a social choice procedure by which an
agenda is used to determine the order that the pairs are compared. The
winner of each pairwise comparison moves onto the next comparison and the
winner of the final comparison is the winner selected by the procedure. For
example, consider the 3x9 preference profile given in (3.5) with an agenda
of (1, 2, 3). First 1 is compared to 2 with the result that alternative 2 wins
the comparison 5 to 4. Then the winner, alternative 2 is compared to 3
15
with alternative 2 winning by a margin of 7 to 2. So alternative 2 is the
social choice. [9]
Theorem 3.2: Sequential pairwise voting with a fixed agenda satisfies the
Condorcet winner criterion [10].
Proof: Suppose aj is the Condorcet winner in a given preference profile.
Then a( already beats any a^ j =Â£ i in more than half of the preference lists.
So a; will win all of its comparisons with any other alternative. Therefore
the Condorcet winner will always be the social choice with sequential
pairwise voting.
The Condorcet winner may not exist as seen in the following profile
112 2
2 3 13
3 2 3 1
(3.6)
where candidates 1 and 2 are tied for first place in the social preference list
by beating each other, 2 to 2 and by both beating alternative 3, by 3 to 1.
This situation is only avoided by considering odd numbers of voters, since
for every pairwise comparison there will be a clear winner. Thus, for even
numbers of voters, Condorcet voting may not yield a social preference
16
list. But even odd numbers do not guarantee that Condorcet voting yields a
social preference profile as illustrated in the following simple 3x3 profile.
1 2 3
2 3 1
3 1 2
(3.7)
Condorcet voting produces a result of 1 beats 2, by 2 to 1; 2 beats 3, by 2 to
1; and 3 beats 1, also by 2 to 1. This situation is a clear violation of
transitivity and is known as the voting paradox or the Condorcet paradox and
was known by both Condorcet and de Borda.
Of the voting procedures previously mentioned only the dictator
always produces a clear winner and sequential pairwise voting produces a
clear winner that is dependent on the agenda. To see this, note that for any
pairwise comparison on (3.7) the winner of that comparison is defeated by
the remaining alternative. To guarantee the winner it is only necessary that
given the situation of the Condorcet paradox the desired winner be placed
last in the agenda. Sequential pairwise voting is commonly used in the
United States Congress.
The Condorcet paradox result, a, > a2 > a3, a3 > au is also called a
Condorcet cycle.
17
4. Tournament Representation of Condorcet Voting
A tournament Tn (on n vertices) is an orientation of the complete
graph K,, which is the graph on n nodes such that every pair of vertices is
joined by an edge. An orientation of a graph is an assignment of direction to
each edge in the graph.
A tournament gives a graph theoretical representation of any voting
method which uses some system of paired comparisons in which the most
preferred of each pair is indicated [5].
Condorcet voting by an odd number of voters on m alternatives
defines a tournament as follows: Let the vertices of the tournament Tm be
labeled by the m alternatives. Let the edge joining a pair of vertices be
oriented away from the vertex most preferred by Condorcet voting. If a; > ay
by the pairwise comparisons, then the edge between the two vertices is
oriented from a; and toward ay For example, the results of the 3x3 profile
given by (3.7), 1 beats 2, 2 beats 3, and 3 beats 1, defines the tournament in
Figure 4.1. The cycle indicated by the Condorcet paradox is apparent.
Another example is the tournament defined by the 5 x 5 profile in (3.1) in
Figure 4.2. Notice that the Condorcet winner, 2, has all the edges pointing
18
1
Figure 4.1 A Condorcet tournament on three alternatives.
l
Figure 4.2 A Condorcet tournament on five alternatives.
19
away, that is, it has maximum outdegree. The presence of the Condorcet
loser is indicated by vertex 5 which has all edges coming in or maximum
indegree.
Condorcet voting with an even number of voters may not have a
tournament representation since there may be ties. And hence some edges
may not be oriented.
We already know that the Condorcet paradox implies a failure of
transitivity, and that the presence of a voting cycle is the mark of a
Condorcet paradox. Before giving a related result for tournaments, notice
that the following result on tournaments makes it not really surprising that
Condorcet cycles exist.
A path is a sequence of vertices alternating with edges beginning at
one vertex and ending at another such that both the vertices and the edges
are distinct. A hamiltonian path is a path such that all the vertices in the
graph are contained in the sequence. In a tournament the direction of the
path is determined by the directed edges. The edges in the sequence defining
the path are usually suppressed.
Theorem 4.1: Every tournament has a hamiltonian path [6].
Proof: By mathematical induction. This is clear for a tournament on 2
20
vertices. Assume that the theorem is true for a tournament with k vertices.
Let Tk+1 be an arbitrary tournament with k + 1 vertices. Let a; be an
arbitrary vertex in Tk+1. Consider the subgraph Tk+1 {aj. This subgraph is
still a tournament since it is an orientation of the complete graph on k
vertices. By assumption this subgraph has a hamiltonian path. Suppose the
hamiltonian path is the sequence {al5 a^ ..., ak}. If there is an edge directed
from a; to aL then {af, als a2, ..., ak} is a hamiltonian path on Tk+1. If not, then
there is an edge directed from a, to a;. Let j be the greatest integer such that
there is an edge directed from a, to af. If j = k, then {a19 a2, ..., ak, aj is a
hamiltonian path on Tk+1. But if j < k, then there is a directed edge from aj
to a; and a directed edge from a; to aj+1. And {al5 a^ ..., a^ a;, aj+1, ...ak} is a
hamiltonian path on Tk+1.
Since a hamiltonian path exists in every tournament then the existence
of a hamiltonian cycle depends on the direction of the edge between the
vertex at the start of the path and the vertex at the end of the path. Further,
the existence of a cycle depends on the direction of the edge between any
two pairs on the path.
This result implies that a hamiltonian path exists but does not say that
the path is unique. The existence of a unique path in a tournament defined
21
by Condorcet voting implies the existence of a social preference list, that is
that the Condorcet voting procedure has successfully produced the social
preference list. What are the conditions that such a path exists? Transitivity
in a tournament is defined similarly as transitivity in a preference list. A
tournament is transitive if for every set of three vertices {a^ aak} in the
tournament an edge directed from a, to aj5 and an edge directed from aj to ak
implies that a directed edge exists from a, to ak.
Theorem 4.2: In a tournament, the following statements are equivalent [8]:
a. There is a unique hamiltonian path.
b. There are no cycles of length 3.
c. The tournament is acyclic.
d. The tournament is transitive.
Proof: By proving that a=>b=>c=>d=>a. To prove a => b, suppose there is
a unique hamiltonian path {a,, a2, ..., am}. Show that for i < j there is an
edge from ai to a^ Suppose this is false, then pick the smallest i such that
there is a j so that there is an edge from a, to a^ Now pick the largest such j.
Assume 1 < i and that j < m, for now. There is an edge from aM to ai+1
since i was chosen as small as possible. There is also an edge from a; to aj+1
since j was chosen as large as possible. Therefore, the sequence
22
{al5 aj, ..., a^, ai+1, ai+2, aj5 ai; aj+1, aj+2,..., am} is a second hamiltonian path,
a contradiction. If i = 1 then {ai+1, ai+2, a^ a;, aj+1, aj+2,..., am} is the second
hamiltonian path. And if j = m then {aI; a^ ..., aul, ai+1, ai+2, ..., aj5 af) is the
second hamiltonian path. Therefore for i < j there is an edge from aj to
implying there are no cycles of length 3.
For b => c, let a tournament have no cycles of length 3. By induction,
show that the presence of a cycle of length k > 3 implies the presence of a
3cycle which provides the contradiction. Suppose that the sequence
{al5 a^ a3, a4} is a cycle in the tournament. Consider the subtoumament
induced by the vertices in the 4cycle. Consider one of the chords, say the
edge between ^ and a4. Then since that edge is directed (the subgraph is a
tournament), either {a a2, a4} or {a^ a3, a4} is a 3cycle on both the
subtoumament and the original tournament.
Now assume that a cycle of length k in a tournament implies the
presence of a 3cycle. Show that a cycle of length k + 1 implies the
presence of a 3cycle. Let {a1? a^ ..., ak, ak+1} be a cycle of length k + 1 in
the tournament. Consider the subtoumament induced by the vertices in the
k+1cycle. Consider two vertices separated by a third vertex, say for
example a, and a3. The edge between is directed since we are in a
tournament. So either (a!, a3} is a 3cycle or {al5 a3, a4, ..., ak, ak+1} is a
23
kcycle. Either way implies the presence of a 3cycle which provides the
contradiction.
For c => d, is immediate. No three cycles imply transitivity.
For d => a, let the tournament be transitive and suppose that there are
two different hamiltonian paths. Then there must be a pair of vertices a, and
aj such that a; follows a} on one path but aj follows a; on the other (if such a
pair does not exist then the hamiltonian paths are identical to begin with).
By extending transitivity along the paths, the fact that ai follows a^ implies
that there is a directed edge from a; to aj5 while transitivity along the other
path implies that there is a directed edge from aj to at which is a
contradiction. Therefore, the two hamiltonian paths are identical.
This theorem implies that the Condorcet paradox means that there
may be many Condorcet cycles not just one and that only one three cycle is
sufficient to preclude the social ordering from Condorcet voting since
transitivity has broken down.
A further issue is that, although a preference profile with an odd
number of voters under Condorcet voting defines a specific tournament, a
tournament does not necessarily define a preference profile since the number
of voters cannot be determined. Also, even if the number of voters is
24
known, the direction of an edge only indicates which alternative received a
majority in the comparisons between the two endpoint vertices, the score of
the pairwise comparison is not indicated at all. Indeed, these two 5x5
profiles yield the same tournament on 5 vertices, given in Figure 4.3.
11111
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
1 2 2 3 3
2 1115
5 4 4 2 1
3 3 5 4 2
4 5 3 5 4
(4.1)
l
Figure 4.3 Tournament on five alternatives.
25
5. Square Voting Profiles, Hamiltonian Cycles, Latin Squares, and
Rotational Tournaments
The restriction to studying profiles under Condorcet voting with only
odd numbers of voters is due to the unavoidable tie results in the pairwise
comparisons. These tie results preclude the desired total ordering of the
alternatives by the society.
So the voting profiles are restricted to odd numbers of voters. It is a
natural restriction to consider voting profiles with the number of candidates
or alternatives equal to the number of voters. In the sense of determining
tournaments by the method of paired comparisons all profiles with an odd
number of voters on an odd number of alternatives can be thought of as
equivalent to a square voting profile on the same (odd) number of
alternatives if they have the same tournament representation.
The third limitation is in studying voting profiles which cause
hamiltonian cycles under Condorcet voting. In the attempt to order all of the
alternatives under question into a social preference list that is a total order, it
is clear that a single 3cycle causes a failure since transitivity is violated.
This may not preclude Condorcet voting from arriving at a clear winner (or
loser) on this profile. The presence of hamiltonian cycles prevents
26
"anything" from being obtained about such voting profiles and may be the
most chaotic or unacceptable result possible.
There are 216 different 3x3 preference profiles. This number is
computed by first noting that there are 3! =6 different preference lists, the
number of permutations on three letters. Since there are three preference
lists we have 63 = 216 possible preference profiles.
A latin square of order n is an n x n square matrix in which each of n
elements appears once in each row and once in each column. A preference
profile already meets this criteria in its columns only.
Theorem 5.1: A 3 x 3 square preference profile produces a Condorcet
paradox if and only if the preference profile is a latin square.
Proof: If one of the candidates or alternatives appears two or three times in
the first row that candidate will be the Condorcet winner, beating the other
candidates by at least 2 to 1. Hence, for a Condorcet cycle to exist, each of
the candidates must only appear once each in the first row. Since the first
row of the preference profile contains a particular candidate once, then the
second row can have that candidate twice but in different columns than the
first row appearance. If so, then that candidate is the Condorcet winner. So,
for a hamiltonian cycle to exist the alternatives can appear only once in the
27
first and second rows. If a candidate can appear only once in each of the
first two rows then that candidate can appear only once in the last row. This
implies that each candidate appears only once in any of the three rows for a
hamiltonian cycle to exist.
There are only twelve profiles that produce a Condorcet paradox or
the associated hamiltonian cycle in the tournament produced by the paired
comparisons. But if we reorder the preference lists so that the top row is
{1, 2, 3} then we see that there are only two such preference lists, one given
in (3.7) with the associated tournament given in Figure 4.1, and the other
preference list given by the profile
1 2 3
3 1 2
2 3 1
(5.1)
and the related tournament is just the same as Figure 4.1 with the directions
reversed.
Since the pairwise comparisons of Condorcet voting do not depend on
the order of the individual preference lists, the reordered preference lists
which are identical will have the same results and produce the same
tournaments. This characteristic is called anonymity of the voters which is
28
more carefully defined as invariance of results under permutation of the
voters [12].
When we look at the 5x5 square profiles the situation is much more
complicated. There are 5! = 120 different individual preference lists,
therefore there are 120s = 24,883,200,000 = 2.5 x io10 preference profiles.
That combinatorial explosion is evident is driven home by the approximate
number of 7 x 7 square profiles: 8.2 x 1025.
A computer program was utilized to study the 5x5 squares. To
make the search more tractable, the program searches for cycles in all of the
5squares with first lines of one appearance of each element, (1, 2, 3, 4, 5},
two appearances of one element and one appearance of 3 of the 4 remaining,
{1, 1, 2, 3, 4}, and two appearances of two distinct elements and one out the
other three, {1, 1, 2, 2, 3}. The 5squares with 3 or more appearances of one
element on the first line have Condorcet winners and therefore have no
hamiltonian cycles. Anonymity of results allows for considering only one
permutation of each first line category (the permutations presented here)
since the results are the same as for the other permutations. And since all
other profiles with the first line in one of these patterns are just relabellings
of the elements of the profile the results apply to all squares that do not
automatically produce a Condorcet winner in the first line. This results in
29
only 23,887,872 5squares to check. Additional testing within the program
precluded matrices that would yield a Condorcet winner by combinations of
elements of the first and second line and effectively eliminated about 20% of
the squares to be tested.
The 5squares had up to three hamiltonian cycles. Latin squares had
either 2 or 3 cycles while nonlatin squares had 03 cycles.
The surprise result is that there are over 60,000 of the profiles, with
{1, 2, 3, 4, 5} as the first line, with three hamiltonian cycles in the
tournament representation. For example, the profile
1 2 3 4 5
5 1 4 2 3
3 4 1 5 2
4 5 2 3 1
2 3 5 1 4
produces the three hamiltonian cycles {1, 5, 3, 4, 2}, {1, 4, 2, 5, 3}, and
{1, 4, 5, 3, 2}, see Figure 5.1. It is interesting that these three cycles
coincide on the edge from vertex 5 to vertex 3 and that pairwise the
hamiltonian cycles coincide on two edges. Note that (5.2) is a latin square.
30
1
Figure 5.1 Tournament with three hamiltonian cycles.
The following profile is obviously not a latin square.
112 3 4
2 2 5 2 5
3 4 3 4 3
4 5 4 5 1
5 3 112
(5.3)
Nevertheless, (5.3) under Condorcet voting still produces the three
hamiltonian cycles: {1, 2, 3, 4, 5}, {1, 2, 4, 5, 3}, and (1, 2, 5, 3, 4}, see
Figure 5.2.
31
1
Figure 5.2 Tournament with three hamiltonian cycles.
Are there any odd square profiles for which there is more than one
hamiltonian cycle such that the cycles are disjoint in the tournament
representation? Two cycles are disjoint if they do not share any of the same
edges. A tournament on five vertices with two disjoint hamiltonian cycles
must have a structure as in Figure 5.3. This is just a rotational tournament.
A regular tournament is a tournament such that the outdegrees of all vertices
are equal. A rotational tournament is a regular tournament such that the
vertices of the tournament can be labelled 0, 1, 2, ... m 1 in such a way
that for some subset S of {1, 2, ..., m}, vertex i beats vertex i + j (mod m) if
and only if j e S. S is called the symbol of the tournament [6], For the
tournament in Figure 5.2, S = {1, 2}. The rotational tournaments have an
32
odd number of vertices. It is clear that the rotational tournaments have a
cyclic structure. For those cycles to be hamiltonian the tournament must
have a prime number of vertices.
1
Figure 5.3 A rotational tournament.
For example, consider the following voting profile which is a latin
square of order 5.
1 2 3 4 5
2 1 5 3 4
3 4 1 5 2
4 5 2 1 3
5 3 4 2 1
(5.4)
33
The pairwise comparisons of Condorcet voting result in the tournament
representation in Figure 5.4. But this is just a rotational tournament as can
1
Figure 5.4 A tournament on five vertices.
be seen by switching the labels on vertices 3 and 4 and redrawing to arrive at
Figure 5.3.
34
6. Algebraic Structure of Latin Squares
Latin squares were discovered by Leonard Euler in 1782. The word
"latin" refers to the latin letters that he used in his examples.
A set S forms a groupoid (S, *) with respect to a binary operation (*)
if, each ordered pair of elements a, b e S is associated with a uniquely
determined element a b e S called their product. The definition of
groupoid essentially establishes what an algebraic structure on a set is: a set
with a binary operation defined on it is a groupoid. For example, this is the
multiplication table of a groupoid.
Table 6.1 Multiplication Table
of a Groupoid
* 1 2 3 4 5
1 1 5 5 5 3
2 4 2 4 3 4
3 5 4 3 2 1
4 2 3 2 4 2
5 3 1 1 1 5
35
A groupoid S is a quasigroup if for all a, b e S the equations
a x = b and y a = b each have exactly one solution. The two conditions
are referred to as left divisibility and right divisibility, respectively. Many
examples of a multiplication table of a quasigroup are given by the next
result.
Theorem 6.1: The multiplication table of a groupoid is a latin square if and
only if the groupoid is a quasigroup [2].
Proof: Suppose that al5 a2, ..., an are the elements of a quasigroup S. Let the
ar s entry, the entry in row r and column s, of the multiplication table be the
product of ar and as, ar as. If the same element occurred twice in the same
row then there would be two solutions to the equation ar x = b for some
b e S, since we now have ars = art = b (where s and t indicate the column).
This contradicts the definition of quasigroup. Similarly if the same entry
occurred twice in a column there would be two solutions to the equation
y as = c for some ceS. Therefore, each element of G occurs exactly once
in each row and once in each column of the multiplication table. The
unbordered multiplication table is therefore a latin square.
Conversely, suppose the multiplication table of a groupoid S is a latin
square. Then clearly the definition of quasigroup holds.
36
A matrix with n rows is referred to as column latin if each of n
elements is in each column. There are no restrictions on the rows.
Similarly, a matrix with n columns is referred to as row latin if each row is a
permutation of the same n elements. A voting profile is column latin since
the individual preference lists have each of the alternatives listed once and
only once. Obviously, a latin square is both row latin and column latin.
A latin square is in standard form (or reduced form) if the elements of
the first row and column are in their natural order top to bottom and left to
right. These are obtained by permuting rows and columns of a given latin
square. For example, in the following, the latin square on the right is the
standard form of the latin square on the left after column permutations and
then row permutations.
1 3 5 2 4
5 2 4 1 3
4 13 5 2
3 5 2 4 1
2 4 13 5
1 2 3 4 5
5 1 2 3 4
4 5 1 2 3
3 4 5 1 2
2 3 4 5 1
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4
For a square preference profile which is a latin square, Condorcet
voting allows column permutations by anonymity. However, row
permutations will change the individual preference lists.
37
An idempotent latin square of order n is a latin square in which each
of the n elements appears on the main diagonal. These squares are also
known as transversal squares. The idempotent law states that a a = a for
all a.
A quasigroup is commutative or symmetric if a b = b a. The
multiplication table of a symmetric quasigroup is a symmetric latin square.
38
7. Decomposition of Prime Order Latin Square Profiles into Disjoint
Hamiltonian Cycles
A pgroupoid is a groupoid (V,*) which has the following properties:
a. a a = a for all a e V,
b. a b implies a ^ a b ^ b for all a,b e V, and
c. a b = c implies and is implied by c b = a for all a, b, c eV.
The leading "p" in pgroupoid stands for partition. Condition a means that a
pgroupoid is idempotent. The multiplication table given in section 6 is an
example of a pgroupoid. We first establish a correspondence between
pgroupoids with n elements and decompositions of the complete undirected
graph on n vertices, Kn, into disjoint cycles.
Let G be a graph. A partition of G into disjoint cycles is a set, Z, of
cycles such that any edge of G belongs to exactly one cycle in Z. If Z
contains only one element then that graph is eulerian.
Let Z be a partition of G into disjoint cycles. Let H(i) be the set of
all edges incident to vertex a; in G and let d; be the degree of a;, that is, the
number of edges in H(i). When do such partitions exist?
39
Theorem 7.1: A partition of a connected graph G into disjoint cycles
exists if and only if all the d/s are even.
Proof: Suppose Z is a partition of G into disjoint cycles. Then each cycle
contributes twice to the degree of each vertex it passes through. Therefore
the dj's are all even.
Suppose all the d/s in a connected graph G are even. Let m be the
number of edges in G. Suppose m = 3. This graph is K3 and contains one
3cycle. Suppose all connected graphs with number of edges less than m and
with all dj's even can be partitioned into disjoint cycles. For a graph G with
m edges and all d/s even, there must be a cycle, C, since the total degree of
G is even. Let G' be the graph obtained by deleting the edges of C from G.
Since G' may be disconnected, consider the subgraphs of G': G G2, ..., Gk.
No two of the G/s have a common vertex. So, every vertex in each Gj has
even degree and each G( is connected. By the induction hypothesis each Gj
has a partition of disjoint cycles. The partition of G into disjoint cycles is
made up of all the disjoint cycles of each Gj and C.
A transition of a kcycle W = {a el5 a2, e2, ...,ak_ ek_ ak, ek} through
a vertex a; is the triple {e^, ai5 ej. The transition through a,, is {ek, al9 e,}.
Let d; = 2Cj where Cj is an integer. Within the cycles of Z there are
40
k = 1, 2, Cj transitions for each vertex a;. The set of transitions through
the vertex a; are the triples (e^k), aj, fj(k)}. The union of all the edges in the
Cj transitions for each vertex is just H(i), the set of edges incident upon the
vertex aj. The edges of different transitions of a vertex are disjoint.
The partition
D, = jje,(l), f,(l)}, e,(2), f,(2)}, je,(c,), f,(Cj)}} ()
of H(i) into pairs of edges is called a 5partition in a; formed by Z. And
D = {Dj, D2, ..., Dn} is called a 5system formed in G by Z and is denoted
D 5(Z).
Theorem 7.2: For every partition Z there is a unique 5system in G, and for
every 5system D there is exactly one partition Z of G into disjoint
cycles so that D = S(Z).
Proof: Let Z be a partition of G into disjoint cycles. Suppose there are two
5systems, D and E, formed in G. So D = {Dl5 D2, ..., Dn} and
E {Ej, E2, ..., En} where D; and Ef are partitions of H(i) into pairs of edges
formed by c; transitions for each vertex by the cycles of Z. Since c; counts
the cycles through a;, and therefore the transitions through a;, the classes of
Dj and Ef are identical.
41
Suppose that D is a 8system formed in G by Z and by X where Z
and X are partitions of G into disjoint cycles. Since C; counts the number of
cycles through vertex a;, the number of cycles in Z and X through vertex a;
must be equal. Consider the cycles of Z through af and the cycles of X
through a;. The transitions caused by X and the transitions caused by Z
through a; form a 8partition in a;. But since there is only one 8partition in
a; the transitions caused by X and caused by Z through a; must be identical
which implies that the cycles of X and the cycles of Z must be identical.
And therefore X = Z.
Theorem 7.3: Every pgroupoid of order n forms a 8system on Kn, the
complete undirected graph on n vertices.
Proof: Let (V,*) be a pgroupoid. Let V = {al5 a2, ..., a} label the vertices
of Kn. Construct D; of the set H(i) of all edges in Kn as follows: Let the
edge e;j joining vertices a; and aj be in the same class of Dj as the edge eik if
and only if aj af = ak. Since (V,*) is a pgroupoid we also have ak a; = a^.
Every class of D; contains two edges and D; is a partition of H(i) into pairs
of edges. Therefore D = {D1? D2, ..., Dn) is a 8system in Kn.
42
The last two results say that not only does every pgroupoid of order
n form a 8system on Kn, but every pgroupoid also corresponds to one and
only one partition of Kn into disjoint cycles.
Theorem 7.4: For a pgroupoid (V,*) the number of elements n is odd, and
x b = c is uniquely soluble for x [3].
Proof: Let (V,*) be a pgroupoid with n elements. Label the vertices of the
complete undirected graph on n elements, Kn, with the elements of V. Let
the edges (a,b) and (b,c) belong to the same closed path in the graph if and
only if a b = c, a ^ b for all a, b, c e V. For example, the pgroupoid given
in the multiplication table in section 6 results in the disjoint cycles of Kn in
Figure 7.1.
Now since an arbitrary vertex, v e Kn, is part of at least one closed
path determined by V the number of edges incident upon each vertex is an
even number. This implies that v is connected to an even number of vertices
hence the number of vertices of Kn determined by V is odd and the number
of elements in V is odd.
For a pgroupoid x b = c implies c b = x and for a groupoid c and
b have a unique product c b, and so x b = c has a unique solution.
43
1
Figure 7.1 K5 decomposed into disjoint cycles.
Corollary 7.5: The multiplication table of a pgroupoid is a column latin
square.
Proof: Suppose that c appears twice in column b. Then x b = c does not
have a unique solution. A contradiction. And since the choice of c and b
are arbitrary, c can only appear once in any column.
This result implies that the multiplication tables of pgroupoids can be
considered as voting profiles. A pgroupoid which is also a quasigroup is
called a pquasigroup. The tools are almost available to construct square
voting systems of prime order which result in disjoint hamiltonian cycles in a
tournament representation of Condorcet voting.
44
Theorem 7.6: Let (V,) be a pquasigroup and let a groupoid (V,*) be
defined by the statement that a (a b) = b holds for all a, b e V.
Then (V,*) is an idempotent and commutative quasigroup. Also, with
any given idempotent commutative quasigroup (V,*) there is
associated a pquasigroup (V,*) related to (V,*) by the correspondence
a b = c if and only if a c = b [3].
Proof: The operation is well defined since a x = b is uniquely soluble
for x since (V,*) is a quasigroup. (V,*) is commutative since a x = b
implies b x = a, so a (a b) = b implies that b (b a) = a, therefore
a *b = b a. We also have a a = a because (V,*) is a pquasigroup. This
implies that a (a a) = a and therefore a a = a so (V, *) is idempotent.
The association is proved in reverse by noting that a (a b) = b for
all a,b e V.
Note that the multiplication table of the new quasigroup (V, *) in the
above theorem is a symmetric idempotent latin square.
Theorem 7.7: Idempotent symmetric latin squares exist only for odd orders.
Proof: Idempotency implies that each element appears once on the diagonal.
Symmetry implies that each element appears off the diagonal in pairs. Each
element must then appear an odd number of times in the square.
45
8. The Construction
To construct a square voting profile with a tournament representation
under Condorcet voting, that has disjoint hamiltonian cycles, begin with an
idempotent symmetric latin square (the unbordered idempotent symmetric
quasigroup multiplication table), for example
1 4 2 5 3
4 2 5 3 1
2 5 3 1 4
5 3 14 2
3 14 2 5
(8.1)
Now applying Theorem 7.6 to (8.1) defines the pquasigroup
1 3 5 2 4
5 2 4 1 3
4 13 5 2
3 5 2 4 1
2 4 13 5
(8.2)
which partitions K5 into disjoint hamiltonian cycles. Consider this square as
a voting profile and column permute this square into
46
1 2 3 4 5
5 1 2 3 4
4 5 1 2 3
3 4 5 1 2
2 3 4 5 1
(8.3)
from which it is easy to see that Condorcet voting applied to this square
results in the rotational tournament in Figure 8.1. It is also apparent that the
disjoint hamiltonian tournament cycles follow the undirected cycles of the
decomposition of K5 from (8.2).
1
Figure 8.1 A rotational tournament.
The voting profile in (8.3) above also indicates that these tournaments
with disjoint hamiltonian cycles can be easily produced since the voting
47
preference lists, the matrix columns, are rotations of the column to the left,
while the first is a rotation of the last. This is the case for order 5, but for
order 7 the situation is more complicated, since there is more than one way
to decompose K7 into disjoint cycles than just following the paths of the
rotational tournament of order 7. Of the seven idempotent symmetric latin
squares of order 7, only one has a rotational structure among the columns
that is similar to the structure given in (8.1). As an example, at order 7,
without such a structure, consider this idempotent symmetric quasigroup of
order 7.
1 3 5 2 6 7 4
3 2 6 5 7 4 1
5 6 3 7 4 1 2
2 5 7 4 1 3 6
6 7 4 1 5 2 3
7 4 1 3 2 6 5
4 1 2 6 3 5 7
(8.4)
By applying Theorem 7.6 we arrive at the following pquasigroup of
order 7.
48
1 4 2 7 3 5 6
7 2 1 6 4 3 5
6 7 3 5 1 2 4
5 1 6 4 2 7 3
4 6 7 3 5 1 2
3 5 4 2 7 6 1
2 3 5 1 6 4 7
(8.5)
which decomposes K7 into the following disjoint cycles in Figure 8.2:
{1,2, 4, 6, 7},
{1,3, 2, 7, 5, 6},
{1,4, 7, 3, 5}, and
{3, 4, 5, 2, 6}.
i
Figure 8.2 A Decomposition of K7 into Disjoint Cycles.
Considering the latin square above in (8.5) as a voting profile and applying
Condorcet voting results in the rotational tournament of Figure 8.3.
49
1
Figure 8.3 Rotational tournament of order 7.
Notice that the disjoint cycles from the decomposition of K7 listed
above do not provide a path for the tournament cycles produced by the
paired comparisons of Condorcet voting.
Kotzig has shown that there are only 7 distinct idempotent symmetric
quasigroups, up to isomorphism. Each of these under Theorem 7.6 results in
a pquasigroup that, as a voting profile under Condorcet voting, defines the
rotational tournament of order 7. It is a conjecture that this works for all
prime orders. Kotzig has also conjectured that a decomposition of this nature
works for all odd orders [4].
To see why the construction works in the case of the rotational
column structure consider the idempotent symmetric quasigroup given by
50
(8.1) as a voting profile. Under the pairwise comparisons of Condorcet
voting this profile results in the tournament given in Figure 8.4 below. This
tournament has the peculiar characteristic that the two disjoint hamiltonian
1
Figure 8.4 Tournament on 5 vertices.
cycles rotate or circulate in opposite directions. Consider the outside cycle
{1, 2, 3, 4, 5}. And notice that from the multiplication table (8.1) that we
have: 1 *2 = 4, 2 *3 = 5, 3 *4=1, 4 *5 = 2, and 5*1=3 where we
have taken the order of multiplication from the direction of the cycle and the
products are the pairs in the order they occur in the cycle. If we apply the
defining equation of Theorem 7.6, a (a b) = b, to the five equations
above we get the set of equations: 1*4 = 2, 2*5 = 3, 3*1 = 4,
4*2 = 5, and 5 3 = 1, respectively where () is multiplication in the
51
pquasigroup given in (8.2). If we rearrange these differently we have:
1 4 = 2, 42 = 5, 2*5 = 3, 53 = 1, and 3 1 = 4. These are the
equations for one of the undirected hamiltonian cycles {1, 4, 2, 5, 3} on K5
determined by the pquasigroup. The order of operation is determined by the
direction of the cycle caused by the pairwise comparisons due to Condorcet
voting. In a sense, the cycles in the tournament representation of the
idempotent symmetric quasigroup under Condorcet voting are preserved
under the equation that defines the pquasigroup.
52
References
[1] K. M. Baker, Condorcet: From Natural Philosophy to Social
Mathematics, University of Chicago Press, Chicago, 1975.
[2] P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms,
Cambridge University Press, Cambridge, England, 1994.
[3] J. Denes and A. D. Keedwell, Latin Squares and Their Applications,
Academic Press, New York, 1974.
[4] A. Kotzig, Groupoids and partitions of complete graphs, PROC. Calgary
Intemat. Conf. on Combinatorics, (1969), pp. 215221.
[5] J. W. Moon, Topics on Tournaments, Holt, Rinehart and Winston, New
York, 1968.
[6] K. B. Reid and L. W. Beineke, Tournaments, in Selected Topics in
Graph Theory, L. W. Beineke and R. J. Wilson, eds., Academic Press,
New York, 1978.
[7] F. S. Roberts, Applied Combinatorics, Prentice Hall, Englewood Cliffs,
N.J., 1984.
[8] F. S. Roberts, Discrete Mathematical Models, Prentice Hall, Englewood
Cliffs, N.J., 1976.
[9] D.G. Saari, Basic Geometry of Voting, SpringerVerlag, New York,
1995.
[10] A. D. Taylor, Mathematics and Politics: Strategy, Voting, Power and
Proof, SpringerVerlag, New York, 1995.
[11] H. P. Young, Social choice scoring functions, SIAM J. Appl. Math., 28
(1975), pp. 824838.
53
[12] S. C. Young, A.D. Taylor, and W.S. Zwicker, Counting quota systems:
a combinatorial question from social choice theory, Mathematics
Magazine, 68 (1995), pp. 331342.
54

PAGE 1
VOTING PROFILES WITH DISJOINT CONDORCET CYCLES by DAVID ALAN SUTHERLAND JR. B S., Metropolitan State College, 1987 A thesis submitted to the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Mathematics 1996 [@
PAGE 2
This thesis for the Master of Science degree by David Alan Sutherland Jr has been approved by Stanley E. Payne J Richard Lundgren / Date
PAGE 3
DEDICATION I dedicate this thesis to my parents and grandparents in gratitude for what they have given me. David Alan Sutherland Frances Sutherland James Glenn Sutherland Nina Geneva Sutherland Ramon Palomino Guerrero Josefa De La Torre Guerrero
PAGE 4
Sutherland, David Alan Jr. (M.S., Mathematics) Voting Profiles With Disjoint Condorcet Cycles Thesis directed by Associate Professor William E. Cherowitzo ABSTRACT Condorcet voting can be used to order all the candidates or alternatives in an election; however, Condorcet voting is not always successful in producing such an order but may instead result in the voting paradox which is also called Condorcet's paradox. This thesis discusses the interrelationships amongst Condorcet voting, tournaments of graph theory, and the algebraic structure of latin squares. The notion of pgroupoids is developed and it is shown how these algebraic structures decompose complete graphs of odd order into disjoint cycles. The thesis then shows the relationship between idempotent symmetric quasigroups and pgroupoids. This relationship is then exploited to construct voting profiles which, under Condorcet voting, produce the Condorcet paradox. iv
PAGE 5
This abstract accurately represents the content of the candidate's thesis. I recommend its publication. v
PAGE 6
CONTENTS Chapter 1. Introduction . . . . . . . . . . . . . . . . . . . . 1 2. Preliminaries ........................................ 6 3. Condorcet Voting, the Condorcet Winner Criterion, and the Condorcet Paradox (Condorcet Cycles) ............................ 11 4. Tournament Representation of Condorcet Voting .............. 18 5. Square Voting Profiles, Hamiltonian Cycles, Latin Squares, and Rotational Tournaments ............................... 26 6. Algebraic Structure of Latin Squares . . . . . . . . . . . 35 7. Decomposition of Prime Order Latin Square Profiles into Disjoint Hamiltonian Cycles .................................. 39 8. The Construction . . . . . . . . . . . . . . . . . . 46 References ............................................. 53 Vl
PAGE 7
1. Introduction This thesis investigates the interrelationships among discrete structures connected with Condorcet voting such as latin squares and quasigroups, and tournaments, a topic in graph theory. In particular, this paper describes a method to construct square voting profiles of odd order that yield an extreme form of the paradox that can result under Condorcet voting. Condorcet voting stems from the idea that a candidate that wins all pairwise elections against the other candidates should be elected. The Condorcet voting procedure was first described by John Charles Borda, a French scientist who lived during the end of the 1700's. In the literature of voting theory, Borda is best known for the social choice function which bears his name, the Borda count, see chapters 2 and 3 However, Borda had a wide and varied adult life. He was an officer in the French navy and also served as a soldier, even serving for a time with French forces aiding the American revolution. He is mostly known for his contributions to fluid dynamics, navigation, and the development of the metric system. Toward the end of his life he was a member of the French Revolutionary Committee on Weights and Measures from which sprang the metric system. 1
PAGE 8
He also developed trigonometric tables during this time as an aid to navigation. Although born to the nobility, Borda did not seem to suffer any tragic consequences due to the French Revolution. Borda was not satisfied with the Condorcet voting scheme since it did not always work, that is, it sometimes does not give an answer or even a tie result. He later developed his (Borda count) system, which always yields a result which could be a tie. It is interesting that the Borda count is not necessarily compatible with Condorcet voting, see chapter 3. [9] Borda is contrasted with his contemporary Marie Jean Antoine Nicolas Caritat Marquis de Condorcet a mathematician and philosopher of the enlightenment. Born to an important aristocratic family Condorcet was known for his progressive views. He supported enfranchisement of women, advocated abolition of slavery, was in favor of free speech, and supported the American revolution. He was widely known to be sympathetic to the suffering of the French people and called for the end of compulsory labor. Because of these attitudes he did not suffer because of his noble birth during the revolution, at least at first. He became heavily involved in politics after the revolution. He represented Paris in the Legislative Assembly after the revolution and was presiding officer of that body for a time. He was instrumental in the establishment of a republic and the educational systems 2
PAGE 9
which came about after the revolution (and after Condorcet's death). Condorcet drafted a constitution for the French Republic, but this was rejected in favor of a constitution drafted by the radical Jacobins whose leader was Maximilien Robespierre. The ascendancy of the Jacobins saw Condorcet and many of his fellow and more moderate Girondins outlawed and arrested. Condorcet was arrested after an extended period in hiding during which he wrote some of his most important philosophical works. He died in prison probably by his own hand. Condorcet accepted the principle of the voting system which carries his name. He proposed that any voting system which did not select a Condorcet winner when one existed should not be adopted He was critical of the Borda count for this very reason. Condorcet was critical of Borda in general as an experimentalist and even denounced him in the French Academy of Sciences as having abandoned the philosophical purity of mathematics for the pettiness of the applied sciences [1]. Since this era, the problem with Condorcet voting, usually referred to as the Condorcet paradox was rediscovered every few years and many solutions have been offered to fix the problem. 3
PAGE 10
This thesis does not offer a solution but examines aspects of a restricted domain of the Condorcet social choice function. Condorcet voting is applied to fmding an acceptable ordering of candidates or alternatives. A situation is cited in which no ordering is possible and a method of finding such situations is demonstrated. Preliminaries of voting theory which are important to the developments in the paper are given in chapter 2. Chapter 3 describes the Condorcet phenomenon and related topics in detail. The tournament representation of Condorcet voting is shown in chapter 4 with several results from graph theory which have direct consequences to the Condorcet problem. In chapter 5 is a discussion leading to the problem of fmding voting profiles which lead to disjoint hamiltonian cycles. This chapter also describes the results of a computer search to examine the cyclic structure of certain square voting profiles. Chapter 6 shifts gears to a discussion on the structure of latin squares which is preliminary to the construction of a voting profile with disjoint hamiltonian cycles. Chapter 7 introduces pgroupoids and shows that these structures decompose complete graphs of odd order into disjoint hamiltonian cycles. This chapter also shows the relationship between pquasigroups and idempotent symmetric latin squares which is the main tool used in constructing the desired voting profiles. And finally, chapter 8 4
PAGE 11
shows the constructions of the desired square voting profiles of order 5 and of order 7. 5
PAGE 12
2. Preliminaries Let A = { a1 az, ... am} be the set of m alternatives or m candidates presented to a society for decision (or priority ordering). The set A is also called the choice set. The society, committee, or voting body, is indexed by a subset of N, the natural numbers, {1, 2, ... n} where n is the size of the society. Assume that an individual in the society can rationally order the alternatives in accordance with her own personal preferences and that such an ordering is independent of the orcJerings by the other voters. Each such preference order, p, is a total order (linear order) on A which is a relation R on A which is irreflexive: antisymmetric: transitive: (ai, ai) R for all ai E A; ( ai, aj) E R implies ( aj, ai) R; and ( ai, aj), ( aj, ak) E R implies ( ai, ak) E R. Note that antisymmetry implies that "ties" are not allowed in the preference order. The usual notation is ai > aj if ( ai, aj) E R and is read "ai beats aj," or "ai is preferred to a/ The preference order, Pi for the ith voter, can be represented as the column vector 6
PAGE 13
a. II a. '2 (2.1) pi = a lm where the candidate on top is the most preferred by voter i. A preference profile is an assignment of preference orders by the members of the society from the set of permutations of the choice set (candidates). A preference profile will be represented by an m x n matrix where each column, i, is the preference order for the i1 h voter. The major goal in studying social choice or voting theory is to produce a social ordering of the alternatives from the preference profile that reflects "the will of the people." This social ordering is a preference order with the same qualities as the individual preference order above, although antisymmetry is usually relaxed, that is, tie results are allowed (the order is actually a partial order with symbol The notion of "the will of the people" rests not only upon the confidence of the voters that the result is true but also on the voter's trust in the honesty of the results, that is, that the results were not altered by manipulation due to the choice of the voting 7
PAGE 14
method or by strategic voting, which means that some voters vote other than how they feel to obtain a desired result. A social choice function is a function from the set of preference profiles to the set of permutations of the choice set, A. The social choice function is the voting method that produces the desired social ordering. These functions are also called social welfare functions. Since a social choice function produces a social preference order on the choice set, then any subset of the choice set will also be ordered. Examples of social choice functions are plurality, the Borda count, the Hare system, and a dictator. In plurality voting, given a preference profile, the alternative with the most first place votes has the first place in the social preference order. Another round of plurality voting on a reduced preference profile fixes the second place of the social order. This second preference profile is made up of the same individual profiles with the winner removed. A third round on another reduced profile fixes the third place of the social order and so on. It is easy to see that ties cannot be avoided in plurality voting. In practice, another social choice function would be used to break ties when necessary: for example, a runoff election or vote, or even a coin toss. The Borda count is a weighted voting scheme, or a scoring function [11]. The position of an alternative in an individual's preference list 8
PAGE 15
determines the weight assigned to that alternative. The sum of all weights assigned to the alternatives by the entire profile determines the social ordering. In the case of the Borda count the scoring vector is (m1, m2, m3, ... 2, 1, 0) where m is the number of candidates. The alternative in first place in a preference list would receive m 1 points and the second m2 points, while the last place candidate receives no points. The points for each candidate are totaled with the order established by the point totals. Simply, ai > aj if and only if candidate ai has more points than candidate aj. The Hare system is a sequential system which in modified form is in use at present to decide elections in several countries. If one candidate has more than half of the first place votes, then that candidate is assigned first place on the social preference order. If not, then all candidates which do not have a first place vote in the profile are eliminated from further consideration for first place and the reduced profile is examined. The candidates with the least number of first place votes are eliminated. The resulting reduced profile is examined for a candidate that now has more than half of the first place votes. If there is no such candidate, again, the candidates with the least number of first place votes are eliminated. This procedure is continued until a winner is produced. Then the original profile is reduced by the 9
PAGE 16
candidate(s) that have already been selected. The entire Hare process is repeated for each position on the social choice preference list until the choice set has been prioritized. If one of the voter's preference list always coincides with the social preference list no matter what social choice function is used then that person is a dictator. 10
PAGE 17
3. Condorcet Voting, the Condorcet Winner Criterion, and the Condorcet Paradox (Condorcet Cycles) The Condorcet voting procedure was first discovered by Jean Charles Borda but was later popularized by the Marquis de Condorcet and hence bears his name. Given a preference profile, the Condorcet procedure selects alternative ai to be preferred over aj in the social choice preference list if and only, if ai > aj in more than half of the preference lists. If no such preference exists then the social preference list determined by Condorcet voting does not exist. For example, alternative 2 is the Condorcet winner, first place in the social preference list, in the following profiles. 2 2 2 3 1 2 2 2 1 3 4 4 5 3 1 3 3 1 5 5 4 (3.1) 1 3 1 5 4 1 1 3 4 5 3 2 2 The alternative, 2, is the Condorcet winner since it beats every other alternative in pair wise comparisons 3 to 0 in the 3 x 3 preference profile. In the 5 x 5 profile alternative 2 beats every other alternative 3 to 2 since it is first in three preference lists and last in two lists. 11
PAGE 18
A related concept is that of the Condorcet loser. The Condorcet loser doesn't beat any of the other alternatives in the pairwise comparisons over all the preference lists, that is, ai is the Condorcet loser if and only if aj > ai in more than half of the preference lists. The Condorcet winner criterion is a property applied to the comparison of soCial choice functions. Simply, a voting procedure satisfies the Condorcet winner criterion if whenever the Condorcet winner exists then the social choice function in question also picks that same alternative for a winner. This appears to be a completely reasonable expectation of prospective social choice functions. Unfortunately, the social choice functions mentioned in the previous section do not satisfy the Condorcet winner criterion [10]! Theorem 3.1: The following voting procedures do not satisfy the Condorcet winner criterion: a) the Hare system, b) the dictator, c) the Borda count, and d) the plurality procedure. 12
PAGE 19
Proof: By contradictions: Consider this preference profile made up of 5 alternatives with 1 7 voters: 1 1 1 1 1 2 2 3 3 3 4 4 4 5 5 5 5 2 2 2 2 2 3 3 2 2 2 2 2 2 2 2 2 2 3 3 3 4 5 4 4 4 5 1 3 3 3 3 3 3 1 (3.2) 4 4 5 3 4 5 5 1 4 5 5 5 5 4 4 4 3 5 5 4 5 3 l 1 5 1 4 1 1 1 1 1 1 4 Alternative 2 is the Condorcet winner since it beats all other alternatives in pairwise comparisons, by at least 12 to 5 (over alternative 1) and by at most 14 to 3 (over alternatives 3 and 4). Consider this same profile under the Hare procedure. There is no alternative that has a clear majority. So we must iterate through the Hare process. Every alternative has at least one first place vote, so we proceed by eliminating the alternative with the least number of first place votes, which is alternative 2. Since alternative 2 is eliminated it cannot be the winner under the Hare procedure. Therefore the Condorcet winner is not the Hare winner. Consider this preference profile made up of three voters deciding among three alternatives. 13
PAGE 20
1 3 3 2 2 2 3 1 1 (3.3) If the voter with preference list in the first column is a dictator then the dictator chooses alternative 1 as the winner; however, the Condorcet winner is alternative 3 since it beats 1 and 2 in two lists. So a dictator does not always pick the Condorcet winner. In fact, in this case, the dictator has picked the Condorcet loser. Now, consider this preference profile of five voters on four candidates. 1 1 1 2 2 2 2 2 3 3 3 3 3 1 1 4 4 4 4 4 (3.4) Alternative 1 is the Condorcet winner since it beats alternatives 2 and 3, by 3 to 2 in the pairwise comparisons and alternative 4, by 5 to 0. Under the Borda count alternative 1 has 11 points while alternative 2 has 12 points. So alternative two is the Borda count winner. And the Borda count does not satisfy the Condorcet winner criterion. Notice the presence of the decisive Condorcet loser. 14
PAGE 21
Finally, consider the preference profile of nine preference lists on three candidates. 1 1 1 1 2 2 2 3 3 2 2 2 2 3 3 3 2 2 3 3 3 3 1 1 1 1 1 (3.5) Candidate 2 is the Condorcet winner since it beats both candidate 1, by 5 to 4, and candidate 3, 5 to 2. Candidate 1 is chosen by the plurality procedure since it has the most first place votes. So plurality does not satisfy the Condorcet winner criterion. Is there any social choice function that does satisfy the Condorcet winner criterion? Sequential pairwise voting is a social choice procedure by which an agenda is used to determine the order that the pairs are compared. The winner of each pairwise comparison moves onto the next comparison and the winner of the fmal comparison is the winner selected by the procedure. For example, consider the 3 x 9 preference profile given in (3.5) with an agenda of (1, 2, 3). First 1 is compared to 2 with the result that alternative 2 wins the comparison 5 to 4. Then the winner, alternative 2 is compared to 3 15
PAGE 22
with alternative 2 winning by a margin of 7 to 2. So alternative 2 is the social choice. [9] Theorem 3.2: Sequential pairwise voting with a fixed agenda satisfies the Condorcet winner criterion [10]. Proof: Suppose ai is the Condorcet winner in a given preference profile. Then ai already beats any aj, j i in more than half of the preference lists. So ai will win all of its comparisons with any other alternative. Therefore the Condorcet winner will always be the social choice with sequential pairwise voting. The Condorcet winner may not exist as seen in the following profile 1 1 2 2 2 3 1 3 3 2 3 1 (3.6) where candidates 1 and 2 are tied for first place in the social preference list by beating each other, 2 to 2 and by both beating alternative 3, by 3 to 1. This situation is only avoided by considering odd numbers of voters, since for every pairwise comparison there will be a clear winner. Thus, for even numbers of voters Condorcet voting may not yield a social preference 16
PAGE 23
list. But even odd numbers do not guarantee that Condorcet voting yields a social preference profile as illustrated in the following simple 3 x 3 profile. 1 2 3 2 3 1 3 1 2 (3.7) Condorcet voting produces a result of 1 beats 2, by 2 to 1; 2 beats 3, by 2 to 1; and 3 beats 1, also by 2 to 1. This situation is a clear violation of transitivity and is known as the voting paradox or the Condorcet paradox and was known by both Condorcet and de Borda. Of the voting procedures previously mentioned only the dictator always produces a clear winner and sequential pairwise voting produces a clear winner that is dependent on the agenda. To see this, note that for any pairwise comparison on (3.7) the winner of that comparison is defeated by the remaining alternative. To guarantee the winner it is only necessary that given the situation of the Condorcet paradox the desired winner be placed last in the agenda. Sequential pairwise voting is commonly used in the United States Congress. The Condorcet paradox result, a1 > > a3 a3 > a1 is also called a Condorcet cycle. 17
PAGE 24
4. Tournament Representation of Condorcet Voting A tournament T n (on n vertices) is an orientation of the complete graph which is the graph on n nodes such that every pair of vertices is joined by an edge. An orientation of a graph is an assignment of direction to each edge in the graph. A tournament gives a graph theoretical representation of any voting method which uses some system of paired comparisons in which the most preferred of each pair is indicated [5]. Condorcet voting by an odd number of voters on m alternatives defmes a tournament as follows: Let the vertices of the tournament Tm be labeled by the m alternatives. Let the edge joining a pair of vertices be oriented away from the vertex most preferred by Condorcet voting. If ai > aj, by the pairwise comparisons, then the edge between the two vertices is oriented from ai and toward aj. For example, the results of the 3 x 3 profile given by (3.7), 1 beats 2, 2 beats 3, and 3 beats 1, defmes the tournament in Figure 4.1. The cycle indicated by the Condorcet paradox is apparent. Another example is the tournament defmed by the 5 x 5 profile in (3.1) in Figure 4.2. Notice that the Condorcet winner, 2, has all the edges pointing 18
PAGE 25
1 3 2 Figure 4.1 A Condorcet tournament on three alternatives. 1 5 2 4 3 Figure 4.2 A Condorcet tournament on five alternatives. 19
PAGE 26
away, that is, it has maximum outdegree. The presence of the Condorcet loser is indicated by vertex 5 which has all edges coming in or maximum in degree. Condorcet voting with an even number of voters may not have a tournament representation since there may be ties. And hence some edges may not be oriented. We already know that the Condorcet paradox implies a failure of transitivity, and that the presence of a voting cycle is the mark of a Condorcet paradox. Before giving a related result for tournaments, notice that the following result on tournaments makes it not really surprising that Condorcet cycles exist. A path is a sequence of vertices alternating with edges beginning at one vertex and ending at another such that both the vertices and the edges are distinct. A hamiltonian path is a path such that all the vertices in the graph are contained in the sequence. In a tournament the direction of the path is determined by the directed edges. The edges in the sequence defining the path are usually suppressed. Theorem 4.1: Every tournament has a hamiltonian path [6]. Proof: By mathematical induction. This is clear for a tournament on 2 20
PAGE 27
vertices. Assume that the theorem is true for a tournament with k vertices. Let Tk+I be an arbitrary tournament with k + 1 vertices. Let ai be an arbitrary vertex in Tk+I Consider the subgraph Tk+I {aJ. This subgraph is still a tournament since it is an orientation of the complete graph on k vertices. By assumption this subgraph has a hamiltonian path. Suppose the hamiltonian path is the sequence { a1 .... ak}. If there is an edge directed from ai to a1 then {ai, a1 .... ak} is a hamiltonian path on Tk+I If not, then there is an edge directed from a1 to ai. Let j be the greatest integer such that there is an edge directed from aj to ai. If j = k, then { a1 .... ak, ai} is a hamiltonian path on Tk+I' But if j < k, then there is a directed edge from aj to ai and a directed edge from ai to aj+I. And { a1 .... aj, ai, ajw ... ak} is a hamiltonian path on Tk+I Since a hamiltonian path exists in every tournament then the existence of a hamiltonian cycle depends on the direction of the edge between the vertex at the start of the path and the vertex at the end of the path. Further, the existence of a cycle depends on the direction of the edge between any two pairs on the path. This result implies that a hamiltonian path exists but does not say that the path is unique. The existence of a unique path in a tournament defmed 21
PAGE 28
by Condorcet voting implies the existence of a social preference list, that is that the Condorcet voting procedure has successfully produced the social preference list. What are the conditions that such a path exists? Transitivity in a tournament is defined similarly as transitivity in a preference list. A tournament is transitive if for every set of three vertices { ai, aj, ak} in the tournament an edge directed from ai to aj, and an edge directed from aj to ak implies that a directed edge exists from ai to ak. Theorem 4.2: In a tournament, the following statements are equivalent [8]: a. There is a unique hamiltonian path. b. There are no cycles of length 3. c. The tournament is acyclic. d. The tournament is transitive. Proof: By proving that a=> b => c => d =>a. To prove a=> b suppose there is a unique hamiltonian path { a1 a2 am}. Show that for i < j there is an edge from aj to a i Suppose this is false, then pick the smallest i such that there is a j so that there is an edge from ai to aj. Now pick the largest such j. Assume 1 < i and that j < m, for now. There is an edge from ait to ai+I since i was chosen as small as possible. There is also an edge from a i to aj+ I since j was chosen as large as possible. Therefore, the sequence 22
PAGE 29
{ a1 aiI ai+I ai+2 aj, ai, aj+I aj+2 am} is a second hamiltonian path a contradiction. If i = 1 then { ai+I ai+2 aj, ai, aj+I aj+2 am} is the second hamiltonian path. And if j = m then {a1 aiI ai+I ai+2 ai, aJ is the second hamiltonian path. Therefore for i < j there is an edge from aj to ai implying there are no cycles of length 3. For b => c, let a tournament have no cycles of length 3. By induction, show that the presence of a cycle of length k > 3 implies the presence of a 3cycle which provides the contradiction. Suppose that the sequence { a1 a3 a4 } is a cycle in the tournament. Consider the subtournament induced by the vertices in the 4cycle. Consider one of the chords, say the edge between and a4 Then since that edge is directed (the subgraph is a tournament), either {a1 a2 a4 } or a3 a4 } is a 3cycle on both the subtournament and the original tournament. Now assume that a cycle of length k in a tournament implies the presence of a 3cycle. Show that a cycle of length k + 1 implies the presence of a 3cycle. Let { a1 ak, ak+I} be a cycle of length k + 1 in the tournament. Consider the subtournament induced by the vertices in the k+ 1cycle. Consider two vertices separated by a third vertex, say for example a1 and a3 The edge between is directed since we are in a tournament. So either {a1 a3 } is a 3cycle or {a1 a3 a4 ak, ak+I} is a 23
PAGE 30
kcycle. Either way implies the presence of a 3cycle which provides the contradiction. For c => d, is immediate. No three cycles imply transitivity. For d => a, let the tournament be transitive and suppose that there are two different hamiltonian paths. Then there must be a pair of vertices ai and aj such that ai follows aj on one path but aj follows ai on the other (if such a pair does not exist then the hamiltonian paths are identical to begin with). By extending transitivity along the paths, the fact that ai follows aj implies that there is a directed edge from ai to aj, while transitivity along the other path implies that there is a directed edge from aj to ai which is a contradiction. Therefore, the two hamiltonian paths are identical. This theorem implies that the Condorcet paradox means that there may be many Condorcet cycles not just one and that only one three cycle is sufficient to preclude the social ordering from Condorcet voting since transitivity has broken down. A further issue is that, although a preference profile with an odd number of voters under Condorcet voting defines a specific tournament, a tournament does not necessarily defme a preference profile since the number of voters cannot be determined. Also, even if the number of voters is 24
PAGE 31
known, the direction of an edge only indicates which alternative received a majority in the comparisons between the two endpoint vertices, the score of the pairwise comparison is not indicated at all. Indeed, these two 5 x 5 profiles yield the same tournament on 5 vertices, given in Figure 4.3. 1 1 1 1 1 1 2 2 3 3 2 2 2 2 2 2 1 1 1 5 3 3 3 3 3 5 4 4 2 1 (4.1) 4 4 4 4 4 3 3 5 4 2 5 5 5 5 5 4 5 3 5 4 1 5 2 4 3 Figure 4.3 Tournament on five alternatives. 25
PAGE 32
5. Square Voting Profiles, Hamiltonian Cycles, Latin Squares, and Rotational Tournaments The restriction to studying profiles under Condorcet voting with only odd numbers of voters is due to the unavoidable tie results in the pairwise comparisons. These tie results preclude the desired total ordering of the alternatives by the society. So the voting profiles are restricted to odd numbers of voters. It is a natural restriction to consider voting profiles with the number of candidates or alternatives equal to the number of voters. In the sense of determining tournaments by the method of paired comparisons all profiles with an odd number of voters on an odd number of alternatives can be thought of as equivalent to a square voting profile on the same (odd) number of alternatives if they have the same tournament representation. The third iimitation is in studying voting profiles which cause hamiltonian cycles under Condorcet voting. In the attempt to order all of the alternatives under question into a social preference list that is a total order, it is clear that a single 3cycle causes a failure since transitivity is violated. This may not preclude Condorcet voting from arriving at a clear winner (or loser) on this profile. The presence of hamiltonian cycles prevents 26
PAGE 33
"anything" from being obtained about such voting profiles and may be the most chaotic or unacceptable result possible. There are 216 different 3 x 3 preference profiles. This number is computed by first noting that there are 3! = 6 different preference lists, the number of permutations on three letters. Since there are three preference lists we have 63 = 216 possible preference profiles. A latin square of order n is an n x n square matrix in which each of n elements appears once in each row and once in each column. A preference profile already meets this criteria in its columns only. Theorem 5.1: A 3 x 3 square preference profile produces a Condorcet paradox if and only if the preference profile is a latin square. Proof: If one of the candidates or alternatives appears two or three times in the first row that candidate will be the Condorcet winner, beating the other candidates by at least 2 to 1. Hence, for a Condorcet cycle to exist, each of the candidates must only appear once each in the first row. Since the first row of the preference profile contains a particular candidate once, then the second row can have that candidate twice but in different columns than the first row appearance. If so, then that candidate is the Condorcet winner. So, for a hamiltonian cycle to exist the alternatives can appear only once in the 27
PAGE 34
first and second rows. If a candidate can appear only once in each of the first two rows then that candidate can appear only once in the last row. This implies that each candidate appears only once in any of the three rows for a hamiltonian cycle to exist. There are only twelve profiles that produce a Condorcet paradox or the associated hamiltonian cycle in the tournament produced by the paired comparisons. But if we reorder the preference lists so that the top row is { 1, 2, 3} then we see that there are only two such preference lists, one given in (3.7) with the associated tournament given in Figure 4.1, and the other preference list given by the profile 1 2 3 3 1 2 2 3 1 (5.1) and the related tournament is just the same as Figure 4.1 with the directions reversed. Since the pairwise comparisons of Condorcet voting do not depend on the order of the individual preference lists, the reordered preference lists which are identical will have the same results and produce the same tournaments. This characteristic is called anonymity of the voters which is 28
PAGE 35
more carefully defined as invariance of results under permutation of the voters [12]. When we look at the 5 x 5 square profiles the situation is much more complicated. There are 5! = 120 different individual preference lists, therefore there are 1205 = 24,883,200,000 "" 2.5 x 1010 preference profiles. That explosion is evident is driven home by the approximate number of 7 x 7 square profiles: 8.2 x 1025 A computer program was utilized to study the 5 x 5 squares. To make the search more tractable, the program searches for cycles in all of the 5squares with first lines of one appearance of each element, { 1, 2, 3, 4, 5}, two appearances of one element and one appearance of 3 of the 4 remaining {1, 1, 2, 3, 4}, and two appearances of two distinct elements and one out the other three, { 1, 1, 2, 2, 3}. The 5squares with 3 or more appearances of one element on the first line have Condorcet winners and therefore have no hamiltonian cycles. Anonymity of results allows for considering only one permutation of each first line category (the permutations presented here) since the results are the same as for the other permutations. And since all other profiles with the first line in one of these patterns are just relabellings of the elements of the profile the results apply to all squares that do not automatically produce a Condorcet winner in the first line. This results in 29
PAGE 36
only 23,887,872 5squares to check. Additional testing within the program precluded matrices that would yield a Condorcet winner by combinations of elements of the first and second line and effectively eliminated about 20% of the squares to be tested. The 5squares had up to three hamiltonian cycles. Latin squares had either 2 or 3 cycles while nonlatin squares had 0 3 cycles. The surprise result is that there are over 60,000 of the profiles, with { 1, 2, 3, 4, 5} as the frrst line, with three hamiltonian cycles in the tournament representation. For example, the profile 1 2 3 4 5 5 1 4 2 3 3 4 1 5 2 (5.2) 4 5 2 3 1 2 3 5 1 4 produces the three hamiltonian cycles {1, 5, 3, 4, 2}, {1, 4, 2, 5, 3}, and {1, 4, 5, 3, 2}, see Figure 5.1. It is interesting that these three cycles coincide on the edge from vertex 5 to vertex 3 and that pairwise the hamiltonian cycles coincide on two edges. Note that (5.2) is a latin square. 30
PAGE 37
1 5 2 4 3 Figure 5.1 Tournament with three hamiltonian cycles The following profile is obviously not a latin square. ; 1 1 2 3 4 2 2 5 2 5 3 4 3 4 3 (5.3) 4 5 4 5 1 5 3 1 1 2 Nevertheless (5.3) under Condorcet voting still produces the three hamiltonian cycles: { 1, 2, 3, 4, 5}, { 1, 2, 4, 5, 3 }, and { 1, 2, 5, 3, 4 }, see Figure 5.2 31
PAGE 38
1 5 2 4 3 Figure 5.2 Tournament with three hamiltonian cycles. Are there any odd square profiles for which there is more than one hamiltonian cycle such that the cycles are disjoint in the tournament representation? Two cycles are disjoint if they do not share any of the same edges. A tournament on five vertices with two disjoint hamiltonian cycles must have a structure as in Figure 5.3. This is just a rotational tournament. A regular tournament is a tournament such that the outdegrees of all vertices are equal. A rotational tournament is a regular tournament such that the vertices of the tournament can be labelled 0, 1, 2, ... m1 in such a way that for some subset S of { 1, 2, ... m}, vertex i beats vertex i + j (mod m) if and only if j E S. S is called the symbol of the tournament [6]. For the tournament in Figure 5.2, S = {1, 2}. The rotational tournaments have an 32
PAGE 39
odd number of vertices. It is clear that the rotational tournaments have a cyclic structure. For those cycles to be hamiltonian the tournament must have a prime number of vertices. 1 5 2 4 3 Figure 5.3 A rotational tournament. For example, consider the following voting profile which is a latin square of order 5. 1 2 3 4 5 2 1 5 3 4 3 4 1 5 2 (5.4) 4 5 2 1 3 5 3 4 2 1 33
PAGE 40
The pairwise comparisons of Condorcet voting result in the tournament representation in Figure 5.4. But this is just a rotational tournament as can 1 5 2 4 3 Figure 5.4 A tournament on five vertices. be seen by switching the labels on vertices 3 and 4 and redrawing to arrive at Figure 5.3. 34
PAGE 41
6. Algebraic Structure of Latin Squares Latin squares were discovered by Leonard Euler in 1782. The word "latin" refers to the latin letters that he used in his examples. A set S forms a groupoid (S, *) with respect to a binary operation ( *) if, each ordered pair of elements a, b E S is associated with a uniquely determined element a b e S called their product. The definition of groupoid essentially establishes what an algebraic structure on a set is: a set with a binary operation defmed on it is a groupoid. For example, this is the multiplication table of a groupoid. Table 6.1 Multiplication Table of a Groupoid 1 2 3 4 5 1 1 5 5 5 3 2 4 2 4 3 4 3 5 4 3 2 1 4 2 3 2 4 2 5 3 1 1 1 5 35
PAGE 42
A groupoid S is a quasigroup if for all a, b e S the equations a x = b and y a = b each have exactly one solution. The two conditions are referred to as left divisibility and right divisibility, respectively. Many examples of a multiplication table of a quasigroup are given by the next result. Theorem 6.1: The multiplication table of a groupoid is a latin square if and only if the groupoid is a quasigroup [2]. Proof: Suppose that a1 a2 a0 are the elements of a quasigroup S. Let the ar,s entry, the entry in row rand column s, of the multiplication table be the product of ar and as, ar as. If the same element occurred twice in the same row then there would be two solutions to the equation ar x = b for some b E S, since we now have ar,s = ar,t = b (where s and t indicate the column). This contradicts the defmition of quasigroup. Similarly if the same entry occurred twice in a column there would be two solutions to the equation y a5 = c for some c E S. Therefore, each element of G occurs exactly once in each row and once in each column of the multiplication table. The unbordered multiplication table is therefore a latin square. Conversely, suppose the multiplication table of a groupoid S is a latin square. Then clearly the defmition of quasigroup holds. 36
PAGE 43
A matrix with n rows is referred to as column latin if each of n elements is in each column. There are no restrictions on the rows. Similarly, a matrix with n columns is referred to as row latin if each row is a permutation of the same n elements. A voting profile is column latin since the individual preference lists have each of the alternatives listed once and only once. Obviously, a latin square is both row latin and column latin. A latin square is in standard form (or reduced form) if the elements of the first row and column are in their natural order top to bottom and left to right. These are obtained by permuting rows and columns of a given latin square. For example, in the following, the latin square on the right is the standard form of the latin square on the left after column permutations and then row permutations. 1 3 5 2 4 1 2 3 4 5 1 2 3 4 5 5 2 4 1 3 5 1 2 3 4 2 3 4 5 1 4 1 3 5 2 4 5 1 2 3 3 4 5 1 2 (6.1) 3 5 2 4 1 3 4 5 1 2 4 5 1 2 3 2 4 1 3 5 2 3 4 5 1 5 1 2 3 4 For a square preference profile which is a latin square, Condorcet voting allows column permutations by anonymity. However, row permutations will change the individual preference lists. 37
PAGE 44
An idempotent latin square of order n is a latin square in which each of the n elements appears on the main diagonal. These squares are also known as transversal squares. The idempotent law states that a a= a for all a. A quasigroup is commutative or symmetric if a b = b a. The multiplication table of a symmetric quasigroup is a symmetric latin square. 38
PAGE 45
7 Decomposition of Prime Onler Latin Square Profiles into Disjoint Hamiltonian Cycles A pgroupoid is a groupoid (V,*) which has the following properties: a. a a = a for all a E V, b. a =1= b implies a =1= a b =1= b for all a,b E V, and c. a b = c implies and is implied by c b = a for all a, b, c EV. The leading "p" in pgroupoid stands for partition. Condition a means that a pgroupoid is idempotent. The multiplication table given in section 6 is an example of a pgroupoid We first establish a correspondence between pgroupoids with n elements and decompositions of the complete undirected graph on n vertices, into disjoint cycles. Let G be a graph. A partition of G into disjoint cycles is a set, Z, of cycles such that any edge of G belongs to exactly one cycle in Z. If Z contains only one element then that graph is eulerian. Let Z be a partition of G into disjoint cycles. Let H(i) be the set of all edges incident to vertex ai in G and let d i be the degree of a i that is, the number of edges in H(i). When do such partitions exist? 39
PAGE 46
Theorem 7.1: A partition of a connected graph G into disjoint cycles exists if and only if all the di's are even. Proof: Suppose Z is a partition of G into disjoint cycles. Then each cycle contributes twice to the degree of each vertex it passes through. Therefore the di's are all even. Suppose all the di's in a connected graph G are even. Let m be the number of edges in G. Suppose m = 3. This graph is K3 and contains one 3cycle. Suppose all connected graphs with number of edges less than m and with all di's even can be partitioned into disjoint cycles. For a graph G with m edges and all d/s even, there must be a cycle, C, since the total degree of G is even. Let G' be the graph obtained by deleting the edges of C from G. Since G' may be disconnected, consider the subgraphs of G': G1 G2 Gk. No two of the G/s have a common vertex. So, every vertex in each Gi has even degree and each Gi is connected. By the induction hypothesis each Gi has a partition of disjoint cycles. The partition of G into disjoint cycles is made up of all the disjoint cycles of each Gi and C. A transition of a kcycle W = {a1 e1 a2 e2 ,akl ekI ak, ek} through a vertex ai is the triple { ei_1 ai, eJ. The transition through a1 is { ek, a1 e1}. Let di = 2ci where ci is an integer. Within the cycles of Z there are 40
PAGE 47
k = I, 2, ... ci transitions for each vertex ai. The set of transitions through the vertex ai are the triples {elk), ai, :(k)}. The union of all the edges in the c i transitions for each vertex is just H(i), the set of edges incident upon the vertex ai. The edges of different transitions of a vertex are disjoint. The partition Di = { {ei(l ), fi(l) }' {ei(2), fi(2) }' ... {ei( ci), fi( ci)}} (7 1) of H(i) into pairs of edges is called a opartition in ai formed by Z. And D = {D1 D2 00 } is called a osystem formed in G by Z and is denoted D = o(Z). Theorem 7.2: For every partition Z there is a unique osystem in G, and for every osystem D there is exactly one partition Z of G into disjoint cycles so that D = o(Z). Proof: Let Z be a partition of G into disjoint cycles. Suppose there are two osystems D and E, formed in G SoD= {D1 D2 D0 } and E = {E1 E2 E0 } where Di and Ei are partitions of H(i) into pairs of edges formed by ci transitions for each vertex by the cycles of Z. Since ci counts the cycles through ai, and therefore the transitions through ai, the classes of Di and E i are identical. 41
PAGE 48
Suppose that D is a 8system formed in G by Z and by X where Z and X are partitions of G into disjoint cycles. Since ci counts the number of cycles through vertex ai, the number of cycles in Z and X through vertex ai must be equal. Consider the cycles of Z through ai and the cycles of X through ai. The transitions caused by X and the transitions caused by Z through ai form a: 8partition in ai. But since there is only one 8partition in ai the transitions caused by X and caused by Z through ai must be identical which implies that the cycles of X and the cycles of Z must be identical. And therefore X = Z. Theorem 7.3: Every pgroupoid of order n forms a 8system the complete undirected graph on n vertices. Proof: Let (V,*) be a pgroupoid. Let V = {a1 the vertices of Kn. Construct Di of the set H(i) of all edges in Kn as follows: Let the edge eij joining vertices ai and aj be in the same class of Di as the edge ei,k if and only if aj ai = ak. Since (V,*) is a pgroupoid we also have ak ai = aj. Every class of Di contains two edges and Di is a partition of H(i) into pairs of edges. Therefore D = {D1 D2 Dn} is a 8system in Kn. 42
PAGE 49
The last two results say that not only does every pgroupoid of order n form a 8system on Kn, but every pgroupoid also corresponds to one and only one partition of Kn into disjoint cycles. Theorem 7.4: For a pgroupoid (V,*) the number of elements n is odd, and x b = c is uniquely soluble for x [3]. Proof: Let (V,*) be a pgroupoid with n elements. Label the vertices of the complete undirected graph on n elements, Kn, with the elements of V. Let the edges (a,b) and (b,c) belong to the same closed path in the graph if and only if a b = c, a =1= b for all a, b, c E V. For example, the pgroupoid given in the multiplication table in section 6 results in the disjoint cycles of Kn in Figure 7.1. Now since an arbitrary vertex, v E Kn, is part of at least one closed path determined by V the number of edges incident upon each vertex is an even number. This implies that v is connected to an even number of vertices hence the number of vertices of Kn determined by V is odd and the number of elements in V is odd. For a pgroupoid x b = c implies c b = x and for a groupoid c and b have a unique product c b, and so x b = c has a unique solution. 43
PAGE 50
1 5 2 4 3 Figure 7.1 K5 decomposed into disjoint cycles Corollary 7.5: The multiplication table of a pgroupoid is a column latin square. Proof: Suppose that c appears twice in column b. Then x b = c does not have a unique solution. A contradiction. And since the choice of c and b are arbitrary, c can only appear once in any column. This result implies that the multiplication tables of pgroupoids can be considered as voting profiles. A pgroupoid which is also a quasigroup is called a pquasigroup. The tools are almost available to construct square voting systems of prime order which result in disjoint hamiltonian cycles in a tournament representation of Condorcet voting. 44
PAGE 51
Theorem 7.6: Let (V,) be a pquasigroup and let a groupoid (V, *)be defined by the statement that a (a b)= b holds for all a, b E V. Then (V,*) is an idempotent and commutative quasigroup. Also, with any given idempotent commutative quasi group (V, *) there is associated a pquasigroup (V, ) related to (V, *) by the correspondence a b = c if and only if a c = b [3]. Proof: The operation is well defined since a x = b is uniquely soluble for x since (V, ) is a quasigroup. (V, *) is commutative since a x = b implies b x = a, so a (a b)= b implies that b (b a) = a, therefore a b = b a. We also have a a= a because (V,) is a pquasigroup. This implies that a (a a) = a and therefore a a = a so (V, *) is idempotent. The association is proved in reverse by noting that a (a b) = b for all a,b E V. Note that the multiplication table of the new quasi group (V, *) in the above theorem is a symmetric idempotent latin square. Theorem 7.7: Idempotent symmetric latin squares exist only for odd orders. Proof: ldempotency implies that each element appears once on the diagonal. Symmetry implies that each element appears off the diagonal in pairs. Each element must then appear an odd number of times in the square. 45
PAGE 52
8. The Construction To construct a square voting profile with a tournament representation under Condorcet voting, that has disjoint hamiltonian cycles, begin with an idempotent symmetric latin square (the unbordered idempotent symmetric quasi group multiplication table), for example 1 4 2 5 3 4 2 5 3 1 2 5 3 1 4 (8.1) 5 3 1 4 2 3 1 4 2 5 Now applying Theorem 7.6 to (8.1) defmes the pquasigroup 1 3 5 2 4 5 2 4 1 3 4 1 3 5 2 (8.2) 3 5 2 4 1 2 4 1 3 5 which partitions K5 into disjoint hamiltonian cycles. Consider this square as a voting profile and column permute this square into 46
PAGE 53
1 2 3 4 5 5 1 2 3 4 4 5 1 2 3 (8.3) 3 4 5 1 2 2 3 4 5 1 from which it is easy to see that Condorcet voting applied to this square results in the rotational tournament in Figure 8.1. It is also apparent that the disjoint hamiltonian tournament cycles follow the undirected cycles of the decomposition of K5 from (8.2). 1 5 2 4 3 Figure 8.1 A rotational tournament. The voting profile in (8.3) above also indicates that these tournaments with disjoint hamiltonian cycles can be easily produced since the voting 47
PAGE 54
preference lists, the matrix columns, are rotations of the column to the left, while the first is a rotation of the last. This is the case for order 5, but for order 7 the situation is more complicated, since there is more than one way to decompose K7 into disjoint cycles than just following the paths of the rotational tournament of order 7 Of the seven idempotent symmetric latin squares of order 7, only one has a rotational structure among the columns that is similar to the structure given in (8.1). As an example, at order 7, without such a structure, consider this idempotent symmetric quasigroup of order 7. 1 3 5 2 6 7 4 3 2 6 5 7 4 1 5 6 3 7 4 1 2 2 5 7 4 1 3 6 (8.4) 6 7 4 1 5 2 3 7 4 1 3 2 6 5 4 1 2 6 3 5 7 By applying Theorem 7.6 we arrive at the following pquasigroup of order 7. 48
PAGE 55
1 4 2 7 3 5 6 7 2 1 6 4 3 5 6 7 3 5 1 2 4 5 1 6 4 2 7 3 (8.5) 4 6 7 3 5 1 2 3 5 4 2 7 6 1 2 3 5 1 6 4 7 which decomposes K7 into the following disjoint cycles in Figure 8.2: {1, 2, 4, 6, 7}, {1, 3, 2, 7, 5, 6}, { 1, 4, 7, 3, 5}, and {3, 4, 5, 2, 6}. 1 0 6 5 4 Figure 8.2 A Decomposition of K7 into Disjoint Cycles. Considering the latin square above in (8.5) as a voting profile and applying Condorcet voting results in the rotational tournament of Figure 8.3. 49
PAGE 56
1 6 3 5 4 Figure 8.3 Rotational tournament of order 7. Notice that the disjoint cycles from the decomposition of K7 listed above do not provide a path for the tournament cycles produced by the paired comparisons of Condorcet voting. Kotzig has shown that there are only 7 distinct idempotent symmetric quasigroups up to isomorphism. Each of these under Theorem 7.6 results in a pquasigroup that, as a voting profile under Condorcet voting defmes the rotational tournament of order 7 It is a conjecture that this works for all prime orders. Kotzig has also conjectured that a decomposition of this nature works for all odd orders [ 4]. To see why the construction works in the case of the rotational column structure consider the idempotent symmetric quasigroup given by 50
PAGE 57
(8.1) as a voting profile. Under the pairwise comparisons of Condorcet voting this profile results in the tournament given in Figure 8.4 below. This tournament has the peculiar characteristic that the two disjoint hamiltonian 1 5 2 4 3 Figure 8.4 Tournament on 5 vertices. cycles rotate or circulate in opposite directions. Consider the outside cycle { 1, 2, 3, 4, 5}. And notice that from the multiplication table (8.1) that we have: 1 2 = 4, 2 3 = 5, 3 4 = 1, 4 5 = 2, and 5 1 = 3 where we have taken the order of multiplication from the direction of the cycle and the products are the pairs in the order they occur in the cycle. If we apply the defining equation of Theorem 7.6, a (a b) = b, to the five equations above we get the set of equations: 1 4 = 2, 2 5 = 3, 3 1 = 4, 4 2 = 5, and 5 3 = 1, respectively where ( ) is multiplication in the 51
PAGE 58
pquasigroup given in (8.2). If we rearrange these differently we have: 1 4 = 2, 4 2 = 5, 2 5 = 3, 5 3 = 1, and 3 1 = 4. These are the equations for one of the undirected hamiltonian cycles { 1, 4, 2, 5, 3} on K5 determined by the pquasigroup. The order of operation is determined by the direction of the cycle caused by the pairwise comparisons due to Condorcet voting. In a sense, the cycles in the tournament representation of the idempotent symmetric quasigroup under Condorcet voting are preserved under the equation that defmes the pquasigroup. 52
PAGE 59
References [1] K. M. Baker, Condorcet: From Natural Philosophy to Social Mathematics, University of Chicago Press, Chicago, 1975. [2] P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, Cambridge, England, 1994. [3] J. Denes and A. D. Keedwell, Latin Squares and Their Applications, Academic Press, New York, 1974. [4] A. Kotzig, Groupoids and partitions of complete graphs, PROC. Calgary Intemat. Conf. on Combinatorics, (1969), pp. 215221. [5] J. W. Moon, Topics on Tournaments, Holt, Rinehart and Winston, New York, 1968. [6] K. B. Reid and L. W. Beineke, Tournaments, in Selected Topics in Graph Theory, L. W. Beineke and R. J. Wilson, eds. Academic Press, New York, 1978. [7] F. S. Roberts, Applied Combinatorics, Prentice Hall, Englewood Cliffs, N.J., 1984. [8] F. S. Roberts, Discrete Mathematical Models, Prentice Hall, Englewood Cliffs, N.J., 1976. [9] D G. Saari, Basic Geometry of Voting, SpringerVerlag, New York, 1995. [10] A. D. Taylor, Mathematics and Politics: Strategy, Voting, Power and Proof, SpringerVerlag, New York, 1995. [11] H. P. Young, Social choice scoring functions, SIAM J. Appl. Math., 28 (1975), pp. 824838. 53
PAGE 60
[12] S. C. Young, A.D. Taylor, and W.S. Zwicker, Counting quota systems: a combinatorial question from social choice theory, Mathematics Magazine, 68 (1995), pp. 331342. 54
