[EM] Friendly Voting: Some Criteria Compliance Proof Sketches

[Forest Simmons]

An example of a lottery L that could be better (in some contexts) than
random ballot favorite: let L(Y) be the percentage of ballots B on which Y
is the highest ranked alternative that has a beatpath to each of the other
alternatives that are ranked on ballot B.

This choice of lottery L would (1)make compromising less of a temptation,
and (2) make winning ties less likely.

Another example: Let L(Y) be the percentage of ballots B on which Y is the
alternative with the worst rank on ballot B that is not pairwise defeated
by any alternative with a better rank on ballot B.

In general, L(Y) should be the percentage of ballots B on which Y would be
an  optimal compromise alternative for the ballot B voter in a Plurality
election.

One more: Bubble sort pairwise the alternatives ranked on ballot B, giving
rectification priority to the out of order pairs closest to the bottom
(worst end) of the ballot. Then let L(Y) be the percentage of the ballots
on which Y ends up on top.

Finally: For each ballot B, while the alternative h currently ranked
highest on B is covered by some alternative y ranked lower on B, swap out t
for the highest such y. Then let L(Y) be the percentage of ballots on which
alternativeY ends up top ranked.

More ideas for lottery L?

-Forest

On Tue, Oct 11, 2022, 5:44 PM Forest Simmons <forest.simmons21 at gmail.com>
wrote:

> In the quoted text below I gave a slight generalization of Friendly Voting
> (FV) in a formulation that will be more convenient for the voting method
> criteria proofs offered in this message (EM List posting).
>
> "Let L be any proportional lottery on the alternatives.
>
> Elect argmin S(X), given by
>
> Sum over Y of d(X,Y)*L(Y),
>
> Where d(X,Y) is the number of steps in the shortest beatpath from X to Y.
>
> When L is the random ballot favorite lottery, the above method description
> becomes an equivalent formulation of Friendly Voting."
>
> First, FV is Landau efficient:
> Suppose that X is the FV winner and X' covers X. Then if there is a
> beatpath from X to Y of length d(X, Y), then replacing X with X' in that
> beatpath will give a beatpath of the same length from X' to Y. If X'
> directly defeats any later member of that beatpath, then d(X',Y) will be
> strictly less than d(X,Y). because of the shortcut ... ETC
>
> Next, Clone Independence:
> As Kristofer pointed out to me, cloning a member Z of the shortest
> beatpath from X to Y doesn't change the length of the shortest beatpath,
> because you can just replace Z with any of its clones.
> So it was Kristofer who gave us the courage to use the number of steps in
> the shortest beatpath, rather than the customary "strength of the weakest
> link" metric used in the (Markus Schulz) CSSD Beatpath method.
>
> Monotonicity:
> Suppose the winner X moves up in rank on one or more ballots, while the
> other alternatives maintain there ranks relative to each other. It is
> obvious that this change cannot increase the value of S(X). But could it
> decrease the value of some S(Z) more than it decreases the value of S(X)?
>
> Well, if S(Z) decreases, it has to be because, for some Y, d(Z,Y) has
> decreased, i.e. the shortest beatpath from Z to Y just got shorter due to a
> shortcut newly created by a defeat of some alternative A that was not
> defeated before X got raised in the ranks.
> Let's compare the changes:
> Before the change the minimal beatpath from X to Y had a length of d(X,Y),
> and after the change it had a length of d(X,A) plus d(A,Y). Meanwhile the
> length of the shortest beatpath from Z to Y changed from d(Z,X)+d(X,Y) to
> d(Z,X)+d(X,A)+d(A,Y).
> In both cases the net effect on the Y term in the S sum of the distances
> is d(X,A)+d(A,Y)-d(X,Y).
> In summary, S(Z) cannot decrease more than S(X) does when X is raised on a
> ballot.
> [The other factor, L(Y), in the corresponding terms of the sum S does not
> depend on X or Z]
>
> So, barring some subtle, but fatal error in my reasoning, it appears that
> the method is (1) Clone independent, (2) Landau efficient, and (3)
> Monotonic.
>
> If the simulations of Kevin and Kristofer  (and anybody else who wants to
> experiment) continue to confirm these claims, we can be increasingly
> confident that FV is worth proposing for public elections.
>
> Kristofer and Kevin have done most of the heavy lifting ... I'm just the
> lucky guy who got to help out a little with the window dressing!
>
> Thanks!
>
> Forest
>
>
>
> ---------- Forwarded message ---------
> From: Forest Simmons <forest.simmons21 at gmail.com>
> Date: Tue, Oct 11, 2022, 10:07 AM
> Subject: Re: Friendly Voting
> To: Jobst Heitzig <heitzig at pik-potsdam.de>
> Cc: Kristofer Munsterhjelm <km_elmet at t-online.de>
>
>
> Jobst,
>
> Your remark connecting Friendly Voting to the benchmark lottery suggested
> the following generalization of FV:
>
> Let L be any proportional lottery on the alternatives.
>
> Elect argmin S(X), given by
>
> Sum over Y of d(X,Y)*L(Y),
>
> Where d(X,Y) is the number of steps in the shortest beatpath from X to Y.
>
> If L is the benchmark lottery, we get Friendly Voting.
>
> Kristofer invented the key concept of the important role of
> "friendliness:" The fewer beatpath steps from X to Y the friendlier Y is to
> X.
>
> All I did was make the connection to the generalized median concept. It
> was Andy Jennings and Rob LeGrand (and you) who got me thinking about the
> median as a way of lowering incentive for insincere strategy.
>
> All My Best,
>
> Forest
>
> On Mon, Oct 10, 2022, 11:36 AM Jobst Heitzig <heitzig at pik-potsdam.de>
> wrote:
>
>> Hi guys!
>>
>> I like this a lot since it makes really smart use of the actual ballots
>> rather than just the defeat matrix, and it treats voters' favourites
>> seriously and as a kind of benchmark, almost like in MaxParC :-)
>>
>> Best regards from the workshop on Algorithmic Technology for Democracy,
>> Jobst
>>
>>
>> Am 10. Oktober 2022 17:03:52 MESZ schrieb Forest Simmons <
>> forest.simmons21 at gmail.com>:
>>>
>>> Friendly Voting is a form of Generalized Median Voting (GMV) adapted to
>>> Ranked Choice Ballots.
>>>
>>> GMV methods elect the candidate whose total distance to the ballots is
>>> minimal. Friendly Voting gauges the distance from a candidate X to a ballot
>>> B as the number of steps in the shortest beatpath from X to ballot B's
>>> first place favorite f(B).
>>>
>>> Example: Consider the ballot set profile...
>>>
>>> x ABC
>>> y BCA
>>> Z CAB
>>>
>>> The cyclic beat order is ABCA.
>>>
>>> So the total distance from A to the ballot set is ...
>>> x×d(A,A)+y×d(A,B)+z×d(A,C),
>>> which simplifies to
>>> 0+y+2z.
>>> Similarly, the total distance from B to the ballot set is
>>> 2x+0+z,
>>> and the total distance from C to the ballot set is
>>> x+2y+0
>>>
>>> If we subtract x+y+z from each of these totals, the respective scores
>>> become ...
>>> z-x, x-y, and y-z.
>>>
>>> Candidate A wins if z-x is the smallest of these, i.e. if fpC-fpA is
>>> smallest, i.e. if ...
>>> fpA-fpC is largest, i.e. larger than both fpB-fpA and foC-fpB.
>>>
>>> So this seems to be the appropriate generalization of the fpA-fpC method
>>> that Kristofer has persisted in pestering Kevin and me about for about half
>>> a decade!
>>>
>>> Thanks, Kristofer !!!! Bullseye🎯
>>>
>>> -Forest
>>>
>>>
>>>
>> --
>> Diese Nachricht wurde von meinem Android-Gerät mit K-9 Mail gesendet.
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20221011/76ea357e/attachment-0001.htm>