[EM] Descending Solid Coalitions Variant for de-cloning Copeland

[Kevin Venzke]

Hi Forest,

Le mardi 10 mai 2022, 00:02:19 UTC−5, Forest Simmons <forest.simmons21 at gmail.com> a écrit :
> Let's say that a subset S of candidates is "uninterrupted" on ballot B  iff no candidate
> that is not a member of S is ranked between two members of S.
> 
> An uninterrupted set that contains some top ranked candidate is "top tethered." Similarly,
> a "bottom tethered" 
> uninterrupted set has at least one candidate that does not outrank any candidate.
> 
> Every "solid coalition" of Woodall is an example of a top tethered uninterrupted set.
> Each completely ranked ballot of n candidates has n of these (non-empty) solid coalitions,
> as also n bottom tethered uninterrupted sets, and many more untethered uninterrupted sets.
> In fact, the total number of uninterrupted sets on a fully ranked ballot of n candidates
> would have to be C(n+1,2) or n(n+1)/2, since it takes two cutoffs to delineate an
> uninterrupted set, and there are n+1 slots for those boundary marks.
> 
> Let beta be a set of ballots. Then for each subset S of candidates, let UI(S) be the number
> of ballots in beta on which S is uninterrupted.

This sounds like UI(S) measures how likely it is that S consists of clones. It
seems like every singleton set would have a 100% score. (With the untethered
definition.)

> For each ballot B we determine a representative candidate K(B) by considering the
> uninterrupted sets S in order of decreasing UI(S).
> When a set S is considered, every candidate not in the set becomes ineligible to represent
> ballot B, unless this would cause all candidates to be ineligible, in which case that set
> is ignored.
> When only one candidate is still eligible to represent ballot B, that candidate is selected
> as K(B).

If I'm right about the above then every ballot immediately runs into a massive
tie. But supposing it doesn't, I am not sure why a high UI score suggests that the
candidate should be representative of the ballot.

> For each candidate k, let N(k) be the number of ballots for which k=K(B). 
> De-cloned Copeland:
> Elect the candidate X  with the greatest sum (over those k that do not defeat X) of N(k).
> Does that work?
> 
> Really, there are at least three versions ... top tethered, bottom tethered, and untethered
> ... not to mention acquiescing variants.

I think your definition is already acquiescing.

With top tethering you might cut down on the UI scores so that only clone sets at
the tops of ballots register. Especially if you use solid and not acquiescing. The
result could be that lone candidates have the highest UI score, according to their
first preference count.

It's a little unclear to me whether the choice of tethering rule affects the
calculation of UI, the sets on B that can be considered, or both. If both, then I
guess you'll usually end up with the first preference as K(B).

> If the descending uninterrupted sets end in a tied set of candidates T(B) to represent
> ballot B, then B contributes to each of their N(k) values 1/#T(B).

This is potentially tedious because the possible results of all ties can't usually
be found by a single pass through the sets (unless no sets have tied strength). And
you need to assess this potentially for each unique ballot.

> Is this the right way to adapt Woodall's idea for this context?

Woodall used this concept in a lot of different ways (not just solid and
acquiescing), including reproducing versions of Schulze. But in all cases the score
of a set would correspond in some way to voter support for the set. Of course, he
was always looking to find the winning candidate at the end. Maybe other
applications are possible.

Kevin