-
Notifications
You must be signed in to change notification settings - Fork 1
/
Beatpath.mw
134 lines (79 loc) · 9.41 KB
/
Beatpath.mw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
(For information about the '''Beatpath method''', see [[Schulze method]]).
In an election, a '''beatpath''' is a sequence of candidates such that each candidate in the sequence beats the next one in a pair-wise contest.
Beatpaths can be used to describe the [[Condorcet paradox]], the [[Schulze method]], and the [[Schwartz set]]. The related concept of a [[#Beat-or-tie_path | Beat-or-tie path]] can be used to describe the [[Smith set]].
==Beatpath definition==
Beatpaths can be defined for any election in which candidates are evaluated in pair-wise contests.
A '''beatpath''' from candidate X to candidate Y is a series of candidates, C(0),...,C(n), for some n >= 1, where:
# X = C(0)
# Y = C(n)
# for every k = 0,...,n-1: C(k) beats C(k+1) in their pair-wise contest.
Note: The same candidate can occur more than once in the sequence. Also, the definition excludes zero-length paths, where n=0.
==Beatpath strength==
The '''strength''' of a beatpath is the minimum '''winning strength''' of each of the pair-wise victories of C(k) over C(k+1) in the beatpath. Different measures of winning strength for a pair-wise contest result in different measures of beatpath strength.
Winning strength can be expressed quantitatively as a number. Common quantitative measures of winning strength include:
* margins: the difference between the number of votes for the winning candidate
* winning votes: the number of votes for the winning candidate
* losing votes: the number of total votes minus the number of votes for the losing candidate
* ratio: the number of votes for the losing candidate divided by the number of votes for the winning candidate
These measures of winning strength can produce different effects to the extent that:
: Total votes = votes for the winning candidate + votes for the losing candidate + abstaining votes.
More generally, winning strength can be expressed comparatively as a relation on parameters of a pair-wise contest. The parameters can include the number of votes for the winning and losing candidate, as for example with recent specifications of the [http://home.versanet.de/~chris1-schulze/schulze1.pdf Schulze method].
==Cycles==
A '''cycle''' is a beatpath that starts and ends at the the same candidate.
Two candidates X and Y are '''in a cycle''' when there is a cycle C(0),...,C(n) with X=C(i) and Y=C(j) for some i and j, i ≠ j.
* Two candidates are in a cycle if and only if there is a beatpath from X to Y and there is a beatpath from Y to X.
==Cycle equivalence==
An [http://en.wikipedia.org/wiki/Equivalence_relation equivalence relation] can be defined on the set of candidates by:
:Candidate X is '''cycle equivalent''' to candidate Y if and only if X and Y are in a cycle or X = Y.
* For every candidate X, the '''cycle equivalence class of X''', '''Cec(X)''', is the set consisting of X and all candidates that are in a cycle with X.
* For any candidates X and Y, either Cec(X) = Cec(Y) or Cec(X) is disjoint from Cec(Y).
==Beatpath order==
Beatpaths create a [http://en.wikipedia.org/wiki/Partial_order partial order] on the set of all cycle equivalence classes.
===Definition===
The '''beatpath order''' is defined by:
:Cec(X) > Cec(Y) if and only if there is a beatpath from X to Y and there is not a beatpath from Y to X,
or correspondingly:
:Cec(X) ≥ Cec(Y) if and only if X = Y or there is a beatpath from X to Y.
===Compared to pair-wise wins===
* If X beats Y, then Cec(X) ≥ Cec(Y); but it is not necessarily true that Cec(X) > Cec(Y).
* If Cec(X) > Cec(Y), then every candidate in Cec(X) pair-wise beats or ties every candidate in Cec(Y), and it is possible that every candidate in Cec(X) pair-wise ties with every candidate in Cec(Y).
* If Cec(X) > Cec(Y) and Cec(X) is next to Cec(Y) [meaning there is no candidate W with Cec(X) > Cec(W) > Cec(Y)], then there is a candidate in Cec(X) that pair-wise beats a candidate B in Cec(Y).
===Ties===
With an ordering, there are three possible comparisons between two items:
* Cec(X) = Cec(Y)
* Cec(X) > Cec(Y)
* Cec(Y) > Cec(X)
The beatpath ordering is a partial ordering, because there may be candidates X and Y such that Cec(X) and Cec(Y) are '''not comparable''', meaning none of the three comparisons are true.
* If Cec(X) and Cec(Y) are not comparable, then every candidate in Cec(X) pair-wise ties with every candidate in Cec(Y).
* If there are no pair-wise ties among any of the candidates, then the beatpath order becomes a [http://en.wikipedia.org/wiki/Linear_order linear order].
===Maximal cycle equivalence classes===
A cycle equivalence class Cec(X) is [http://en.wikipedia.org/wiki/Maximal_element '''maximal'''] in the beatpath order if and only if there is no other candidate Y with Cec(Y) > Cec(X).
Because the beatpath order may only be a partial order, there can be more than one maximal cycle equivalence class. But if Cec(X) and Cec(Y) are different and both are maximal, then they are not comparable, and hence only have pair-wise ties between them.
If there are no pair-wise ties, the beatpath order is linear and there is exactly one cycle equivalence class set that is maximal.
The [[Schwartz set]] is the union of the maximal cycle equivalence classes in the beatpath order.
===Alternative formulation===
An alternative but equivalent formulation of the beatpath order is based on the [http://en.wikipedia.org/wiki/Binary_relation binary relation] ''Beat'' over the set of candidates defined by:
:(X,Y) is in ''Beat'' if and only if candidate X pair-wise beats candidate Y
The [http://en.wikipedia.org/wiki/Binary_relation#Operations_on_binary_relations transitive-reflexive closure] of ''Beat'' is a [http://en.wikipedia.org/wiki/Preorder preorder] on the set of candidates, and the [http://en.wikipedia.org/wiki/Preorder#Constructions natural partial order generated from that preorder] is the beatpath order defined previously.
Typically, ''Beat'' is [http://en.wikipedia.org/wiki/Irreflexive irreflexive] and [http://en.wikipedia.org/wiki/Antisymmetric_relation anti-symmetric], but this formulation does not depend on those properties. When ''Beat'' is irreflexive and anti-symmetric, the cycle equivalence classes can have 1, 3, or more candidates, but never exactly 2 candidates.
This alternative formulation highlights that beatpaths are used in the first definition of the beatpath order mostly as a way of expressing the transitive closure of the pair-wise victories.
The cycle equivalence classes are the [http://en.wikipedia.org/wiki/Strongly_connected_component strongly connected components] of the [http://en.wikipedia.org/wiki/Graph_%28mathematics%29#Directed_graph graph] of ''Beat''.
===Examples===
* [[Beatpath examples 3 | Examples of beatpath orders with 3 candidates]]
* [[Beatpath example 12 | An example of a beatpath order with 12 candidates]]
==Beat-or-tie path==
A parallel concept is the beat-or-tie path, differing from beatpaths in that each candidate in the sequence is only required to beat or tie the next candidate in the sequence in their pair-wise contest. Beat-or-tie paths create beat-or-tie cycles, beat-or-tie cycle equivalence classes, and a beat-or-tie order on those beat-or-tie cycle equivalence classes.
Alternatively but equivalently, the beat-or-tie order is generated from the ''Beat-or-tie'' relation defined by:
:(X,Y) is in ''Beat-or-tie'' if and only if candidate X pair-wise beats or ties candidate Y
The [http://en.wikipedia.org/wiki/Binary_relation#Operations_on_binary_relations transitive-reflexive closure] of ''Beat-or-tie'' is a [http://en.wikipedia.org/wiki/Preorder preorder] on the set of candidates, and the [http://en.wikipedia.org/wiki/Preorder#Formal_definition natural partial order generated from that preorder] is the beat-or-tie order defined by beat-or-tie paths.
If the election requires every candidate to be evaluated against every other candidate in a pair-wise contest which always results in one of the candidates beating the other, or in a tie, then the beat-or-tie order is a linear order. This is because for any two candidates X and Y, X beats-or-ties Y or Y beats-or-ties-X, so the beat-or-tie cycle equivalence classes of X and Y are always comparable. When the beat-or-tie order is linear, it has a single maximal cycle equivalence class that is the [[Smith set]].
==Algorithms==
Given either the ''Beat'' relation or the ''Beat-or-tie'' relation as an N × N matrix, [http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm Kosaraju's algorithm] can be used to partition the set of candidates into cycle equivalence classes (the [http://en.wikipedia.org/wiki/Strongly_connected_components strongly connected components] of the graph of the relation). Kosaraju's algorithm runs in Θ(N<sup>2</sup>) time. The corresponding order and/or the maximal elements can also be determined in Θ(N<sup>2</sup>) time.
A version of the [http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm Floyd-Warshall algorithm] can be used to identify the candidates in the maximal elements of the beatpath order or the beat-or-tie order. The Floyd-Warshall algorithm runs in Θ(N<sup>3</sup>) time.
Here are [[Maximal elements algorithms | pseudo-code examples of these algorithms]] applied to calculating the [[Schwartz set]] and [[Smith set]] for an election.
==See also==
* [[Beatpath examples 3 | Examples with 3 candidates]]
* [[Beatpath example 12 | Example 12 candidates]]
* [[Maximal elements algorithms | Algorithms to calculate the Schwartz set and Smith set]]
* [[Schwartz set]]
* [[Smith set]]