[EM] Getting support levels and a social ordering from DAC/DSC

[Kristofer Munsterhjelm]

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.