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