[EM] Friendly Cover, a burial-resistant monotone almost cloneproof method

[Forest Simmons]

Congratulations!... a major tour de force ... discouraging the most common
insincere strategies like never before, while retaining monotonicity and
even inhancing Smith to Landau efficiency!

On Mon, Sep 12, 2022, 2:27 AM Kristofer Munsterhjelm <km_elmet at t-online.de>
wrote:

> Here's a method that generalizes fpA - sum fpC to pass:
>         - Landau (with a certain provision)
>         - monotonicity
>         - independence of twins (a weaker clone independence)
>         - output scores (not just rankings)
> and probably also passes DMTCBR and a weaker DMTBR (as yet unnamed
> criterion). My simulator indicates as such, but I don't have a proof
> yet. In addition, unlike IRV, it's summable.
>
> Let's call it Friendly Cover for now, for lack of a better name. Any
> name suggestions would be appreciated!
>
> (In addition, Friendly Cover passes all the three-candidate criteria
> that fpA-fpC does, like the chicken dilemma criterion.)
>
> This is quite a step towards getting strategy resistance, clone
> independence, and summability!
>
> I'll describe a simple version, then a more complex one, and then do
> some proofs for the criteria.
>
> First, the simple version. It has two problems, one of which a patch
> handles; I'll give an explicit version later that incorporates that
> patch more directly.
>
> For any candidate X:
>         Let X's defeaters be the candidates who beat X pairwise,
>         Let X's intermediates be the candidates who beat some defeater and
> are
> not defeaters themselves,
>         and let X's friends be everybody else (including X himself).
>
>         Then X's score is the sum of first preferences of X's friends,
> minus
> the sum of first preferences of X's defeaters.
>
> In a three candidate A>B>C>A cycle, this reduces to fpA - fpC because C
> is A's defeater and B is an intermediate, so the friend set is only A.
>
> However, there are two problems. First, we only get Landau if every
> candidate gets at least one first preference vote. Otherwise it's
> possible that A is the CW and has no first preferences, and B beats
> everybody but the CW and, despite being beaten by the CW, ties him by
> score. That happens because the only defeater of B is A, and A has zero
> first preferences, so B's score is A's score minus zero.
>
> I don't know how to robustly handle that yet, so I'm going to leave it
> for now. Perhaps funny is that people who make a big deal out of core
> support could see this as a feature and not a bug :-)
>
> Second, which *can* be fixed: if A ties C pairwise, C's defeat set
> contains B but not A, and A's friend set also contains B, then raising A
> on a B>A ballot could give C an additional point while not changing A's
> score, thus violating monotonicity. To fix that, we need this patch:
>
>         Before calculating X's score, remove from X's friend set everybody
> who's a defeater of someone who X ties pairwise.
>
> But that's fairly inelegant, so instead I'll give an explicit version
> that's equivalent in the absence of pairwise ties. Thanks to Forest
> Simmons for discovering that equivalence:
>
> For any candidate X:
>         Let X's defeaters be the candidates who beat X pairwise,
>         Let X's friends be everybody X weakly covers,
>
>         and the score is calculated as above.
>
> Ordinary covering is similar to "A defeats B", i.e. you can't be
> covering someone and that someone also be covering you. Weak covering is
> more like "A defeats or ties B": you can be weakly covering someone else
> who is also weakly covering you, and that means you, in the covering
> sense, tie that other candidate.
>
> The weak covering relation is defined like this: "A weakly covers B if A
> beats everybody B does, and B is beaten by everybody A is beaten by,
> pairwise". (Note that A covers himself.)
>
> Hence the "Cover" in "Friendly Cover". It can be shown that if there are
> no pairwise ties, X's friend set is exactly X and everybody X covers in
> the ordinary Landau sense, but I don't want to clutter up the post.
>
> This solves the problem we patched out because A can't cover B if B is a
> defeater of some C that A ties pairwise, because then A doesn't beat
> everybody B does (in particular, A doesn't beat C!)
>
> ----
>
> Proofs:
>
> Proving Landau compliance involves a lot of nitty-gritty details, so
> I'll show it for a related strict covering that differs from
> Landau/Fishburn when there are ties. I think it can be shown for actual
> Landau too, but again, I don't want to clutter up the post; just ask me
> if you'd like the full thing.
>
> First assume that everybody has a first preference. That's the caveat I
> mentioned at the start.
>
> Let A strictly cover B if A weakly covers B, A beats B pairwise, and
> either A beats someone B doesn't, or B is beaten by someone A isn't. And
> let the uncovered set be everybody who isn't strictly covered by anyone.
>
> Suppose A strictly covers B. If B is beaten by one more candidate than
> A, then B's defeat set contains more candidates than A's. And since
> covering relations are transitive (if A covers B and B covers C, then A
> covers C), A's friend set is no smaller than B's. Hence B's sum over
> defeaters is larger than A's, and B's sum over friends is at most equal
> to A's. Thus A outscores B, as desired.
>
> If, on the other hand, A beats one more candidate than B (but both A and
> B are beaten by the same set), then since A beats B pairwise, A weakly
> covers B but B doesn't weakly cover A. So A's friend set contains A
> himself as well as everybody weakly covered by B, but B's friend set
> doesn't contain A. Hence B's sum over defeaters is the same as A's while
> A's sum over friends is greater than B's, so again A outscores B.
>
>
> Monotonicity is pretty easy: raising A can't make anyone appear in A's
> defeater set who wasn't there before, and can't remove someone from
> someone else's defeater set. Since fpA - fpC itself is monotone, that's
> all we need.
>
>
> Independence of twins: this is a weaker clone independence that minmax
> also passes. It says that if we replace a candidate X by two clones X1
> and X2, then the outcome can't change.
>
> First, let's show that there's no teaming incentive. Suppose A wins and
> we clone A. Since everybody who beats A also beats all the clones, this
> can't remove any defeaters of A from the clones' defeater sets. And
> since the clones all beat candidates who the original A beats, it can't
> introduce new friends to any of the clones. Since the sum over defeaters
> can't decrease and the sum over friends can't increase, the A clones'
> scores can't increase.
>
> Now suppose that the winner is X and we clone Y. If Y is a defeater of
> X, then all the clones will be defeaters of X. If Y is covered by X,
> then every clone will also be covered by X. So cloning Y doesn't affect
> X's score. Since we know from the previous paragraph that it can't
> increase Y's score, Y can't go from loser to winner by being cloned. So
> there is no teaming incentive (and this is fully general, i.e. not just
> for twins).
>
> Now suppose A wins and we replace A with two candidates A1 and A2.
> Suppose also without loss of generality that A1 beats or ties A2
> pairwise. Then if A1 ties A2, both weakly cover each other. Since they
> beat the same non-clone candidates and are beaten by the same non-clone
> candidates as A, all that happens is that their friend sets go from
> containing A to containing A1 and A2. And since the sum of clones' first
> preferences is the same as the original candidate's first preferences,
> the clones' scores don't change. If A won, both clones will still win;
> if A lost, both clones will still lose.
>
> If A1 strictly beats A2, then A1 weakly covers A2 but not vice versa. So
> A1's score is the same as A used to be while A2's score will at most be
> equal to A1 (and may be lower). In any case, if A won, A1 will win after
> the cloning, and if A lost, both clones will still lose afterwards.
>
> The problem is that in the more general case, it's possible that A could
> be cloned into A1, A2, and A3, who are in a cycle (i.e. A1>A2>A3>A1).
> Then each clone gets one of the other clones into his defeat set, which
> lowers all the clones' score and may make them lose. So if you have at
> least five candidates and a Landau set with three clones in it, there
> could be trouble.
>
> -km
> ----
> Election-Methods mailing list - see https://electorama.com/em for list
> info
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220912/3a8e126a/attachment.htm>