Kristofer Munsterhjelm
2018-07-10 11:00:22 UTC
While implementing DSC in my quadelect voting program, I thought of a
way to find out what candidate is in second place, third, etc., in such
a way that also gives a support level and thus also shows if candidates
are tied.
The method works like this: To find the support of candidate X, sort the
coalitions descending in order of support as usual. As an example, for
the following ballot set:
16: A>B>C
29: A>C>B
20: B>A>C
18: B>C>A
17: C>A>B
27: C>B>A
we get the coalitions
127: ABCD
46: AC
45: BC
45: A
44: C
38: B
36: AB
Then go down the list, starting with an eligible candidate set of all
candidates, and intersecting it with the coalitions unless that leads to
either the eligibles set becoming empty (just like when we evaluate a
winner in DAC/DSC) or X dropping out of the set. The support of X is the
support of the first coalition that leads to X being the only candidate
left, when following the skipping rules above.
For the example above, from the perspective of A, we intersect with AC,
skip BC, then intersect with A. Now the set is reduced to A alone, so
A's support is the support of the A set, i.e. 45.
From the perspective of B, we skip AC, intersect BC, skip A and C, and
intersect B, so B's support is 38.
From the perspective of C, we intersect AC and then intersect BC. The
result of that intersection is C, so C's support is also 45.
The social ordering is thus A=C>B.
This approach should also be neutral without having to use random
tiebreakers. Suppose we're calculating the support of candidate X. We
can remove all coalitions not containing X from the coalition list and
get the same result, since the skipping rule will skip them anyway.
Then consider a set of coalitions that are tied in support. There are
two possibilities: either intersecting all the coalitions in the
same-support set leaves us with X alone, or we have multiple candidates
left after doing so. In the latter case, the order of the coalitions in
the same-support set obviously doesn't matter, since we're going to
intersect all of them anyway. In the latter case, the order of the
coalitions determine how many we have to go through before X is the only
candidate left and the procedure returns the support of X. But since
every coalition in the set has the same support, we get the same support
for X no matter how many coalitions in the set we have to go through, so
again, the order doesn't matter.
Since we get the same results no matter how ties are broken in the
sorting stage, we don't have to do any tiebreaking, and since DAC/DSC is
neutral in the absence of any such ties, so is this extension.
Suppose X is the winner of DAC/DSC by the ordinary rules. Since X is the
winner, and not Y, that means that the only non-X coalitions we
encountered were ones that would have emptied the eligibles set. Suppose
the coalition that reduced the eligibles set to X had support s_X. Then
there exists some subset of coalitions, all with support greater than or
equal to s_X, that reduced the eligibles set to X. However, there does
not, for any other candidate Y, exist a subset of coalitions of support
greater than s_X that reduces the eligibles set to Y; if there were,
then Y would have been the winner, not X. So any other candidate Y has
support level at most s_X. Hence X is also a winner using the
per-candidate procedure above.
If there's no way of tiebreaking equal support coalitions that would
cause the DAC/DSC winner by ordinary rules to be Y, then there exists no
subset of coalitions of support >= s_X that reduces the eligibles set to
Y, and X is the unique winner using the per-candidate procedure above.
----
Election-Methods mailing list - see http://electorama.com/em for list info
way to find out what candidate is in second place, third, etc., in such
a way that also gives a support level and thus also shows if candidates
are tied.
The method works like this: To find the support of candidate X, sort the
coalitions descending in order of support as usual. As an example, for
the following ballot set:
16: A>B>C
29: A>C>B
20: B>A>C
18: B>C>A
17: C>A>B
27: C>B>A
we get the coalitions
127: ABCD
46: AC
45: BC
45: A
44: C
38: B
36: AB
Then go down the list, starting with an eligible candidate set of all
candidates, and intersecting it with the coalitions unless that leads to
either the eligibles set becoming empty (just like when we evaluate a
winner in DAC/DSC) or X dropping out of the set. The support of X is the
support of the first coalition that leads to X being the only candidate
left, when following the skipping rules above.
For the example above, from the perspective of A, we intersect with AC,
skip BC, then intersect with A. Now the set is reduced to A alone, so
A's support is the support of the A set, i.e. 45.
From the perspective of B, we skip AC, intersect BC, skip A and C, and
intersect B, so B's support is 38.
From the perspective of C, we intersect AC and then intersect BC. The
result of that intersection is C, so C's support is also 45.
The social ordering is thus A=C>B.
This approach should also be neutral without having to use random
tiebreakers. Suppose we're calculating the support of candidate X. We
can remove all coalitions not containing X from the coalition list and
get the same result, since the skipping rule will skip them anyway.
Then consider a set of coalitions that are tied in support. There are
two possibilities: either intersecting all the coalitions in the
same-support set leaves us with X alone, or we have multiple candidates
left after doing so. In the latter case, the order of the coalitions in
the same-support set obviously doesn't matter, since we're going to
intersect all of them anyway. In the latter case, the order of the
coalitions determine how many we have to go through before X is the only
candidate left and the procedure returns the support of X. But since
every coalition in the set has the same support, we get the same support
for X no matter how many coalitions in the set we have to go through, so
again, the order doesn't matter.
Since we get the same results no matter how ties are broken in the
sorting stage, we don't have to do any tiebreaking, and since DAC/DSC is
neutral in the absence of any such ties, so is this extension.
Suppose X is the winner of DAC/DSC by the ordinary rules. Since X is the
winner, and not Y, that means that the only non-X coalitions we
encountered were ones that would have emptied the eligibles set. Suppose
the coalition that reduced the eligibles set to X had support s_X. Then
there exists some subset of coalitions, all with support greater than or
equal to s_X, that reduced the eligibles set to X. However, there does
not, for any other candidate Y, exist a subset of coalitions of support
greater than s_X that reduces the eligibles set to Y; if there were,
then Y would have been the winner, not X. So any other candidate Y has
support level at most s_X. Hence X is also a winner using the
per-candidate procedure above.
If there's no way of tiebreaking equal support coalitions that would
cause the DAC/DSC winner by ordinary rules to be Y, then there exists no
subset of coalitions of support >= s_X that reduces the eligibles set to
Y, and X is the unique winner using the per-candidate procedure above.
----
Election-Methods mailing list - see http://electorama.com/em for list info