[EM] Random Ballot Favorite Chain Building

[Forest Simmons]

In some informal settings it is convenient and appropriate to use a chance
event to make a decision ... flipping a coin to see which team is first at
bat ... drawing straws to see who is point man on patrol ... rock paper
scissors to see who washes the dishes.

In 1965 when I turned 18, a selective service lottery picked me to be one
of the lucky guys eligible for conscription into Uncle Sam's VietNam war.

In the context of voting methods the "benchmark" lottery draws one or more
ballots (depending on the number of recruits needed) at random to see whom
is to be elected/selected.

Some times it is appropriate to turn a chance method into a deterministic
method by simply selecting/electing the nominated candidate(s) with the
greatest chance of winning the election lottery ... e.g. the one(s) with
the most votes.

That brings us to the "Random Ballot Favorite Chain Building" RBFCB voting
method.

First, we will give the chance version, and then the associated
deterministic version ... both based on the voter submitted, non-random,
ranked choice ballots.

As usual, we start by tallying the ballot preferences to find out all of
the head-head matchup winners.

Naturally if X outranks Y on more ballots than Y outranks X, then X is the
matchup winner for the X vs Y match.

Then we start to build up our "chain" by drawing a ballot B at random and
initializing a list named FavoredChain (FC for short) with the name of the
candidate most favored by ballot B.

We continue building up the FC chain by drawing additiomal ballots and
inserting the names of their respective favorites into their appropriate
positions relative to the other FC chain members ... above all of the ones
they defeated in the matchup tally, and below all of the ones by whom they
were defeated.

If some particular candidate cannit be fit into the FC list in this way,
then it is left out of list as we turn our attention to the next randomly
drawn ballot.

When no additional candidate can be fit into the FC chain order in a way
that respects the relevant matchup wins, then the FC chain is complete,
i.e. "maximal."

The candidate that ended up at the head of the list is the winner of this
round of the Random Ballot Favorite Chain Building lottery.

The winner of the corresponding deterministic method is simply the
candidate with the best chance of winning additional rounds of the RBFCB
lottery.

How is it determined from the ballots which candidate has the best chance
of winning the RBFCB lottery?

Usually, it can be determined without running the lottery simulation even
once.

For example, if (as per usual) there is one candidate that wins all of its
matchups in the matchup tally, she will go straight to the head of the FC
chain as soon as any ballot is drawn on which it is the most favored
candidate. Thereafter all additional favorites will be incorporated in the
FC list below this undefeated matchup winner.

In the rare case when no candidate is undefeated in the matchups, and the
winning probabilities cannot be easily calculated from the table of matchup
winners in conjunction with the first place vote totals information ... in
that very rare case the lottery can be run as many times as necessary to
get the winning probabilities with any desired degree of statistical
certainty.

I hope that this exposition will be clearer than mud to most EM list
readers ...perhaps even most Scientific American readers could catch the
drift.  Math Monthly readers might be miffed at the lack of algebra.

Still a ways to go for the voters' pamphlet version:-)

-Forest



On Fri, Oct 21, 2022, 6:56 AM Forest Simmons <forest.simmons21 at gmail.com>
wrote:

> It turns out that what we want is chain building by fitting each newly
> drawn ballot favorite into the chain where-ever possible without destroying
> its total order relation. (A chain is a totally ordered set.)
>
> So chain building can ascend or descend ad libitum ... as they say, "Just
> follow your nose"
>
> Also it simplifies everything conceptually and computationally if we
> replace and shuffle the ballots between all consecutive drawings.
>
> Remember that the proto example was the candidate cycle ABCA with
> respective first place probabilities of p=fpA, q=fpB, and r=fpC.
>
> The possible maximal chains are ...
> A>B, B>C, and C>A,
> with probabilities proportional to ...
> pq, qr, and rp, respectively,
> when chains are built ad libitum.
>
> The condition for A winning is
> pq>max(qr,rp),
> which (turns out to be) equivalent to
> (p-r)>max(q-p, r-q),
> within this probability context of p+q+r=1.
>
> This last inequality is our fpA-fpC condition for A winning in our proto
> example.
>
> Next, a simple introduction to the method suitable for a voters' pamphlet
> ...
>
>
>
>
>
>
>
> On Thu, Oct 20, 2022, 1:24 PM Forest Simmons <forest.simmons21 at gmail.com>
> wrote:
>
>> One important (but easy) correction:
>>
>> In order to make this method Monotone, we have to start the chain from
>> the bottom of the list ListF. That's what puts the "Climbing" in Random
>> Ballot Favorite Chain Climbing!
>>
>> A comment on exposition for public consumption ... no mention of
>> Condorcet  Smith, Landau, or Banks should be included in the method
>> description, any more than a brief introduction to IRV needs to explain
>> what to do if the last three remaining candidates have the same first place
>> transferred vote totals.  Every generic public ballot set will have a Banks
>> member with at least one first place vote, so no need to get people worried
>> right off the bat about what to do in the impossibly rare contrary case.
>> Stick with generic conditions in the voters' pamphlets ... just make sure
>> that the rare exceptional possibilities are covered in the published
>> official legal definition, as well as the RAQ's (Rarely Asked Questions) if
>> not the FAQ's!
>>
>> I only mentioned it at all because of its earlier mention in related EM
>> list threads.
>>
>> -Forest
>>
>> On Thu, Oct 20, 2022, 11:48 AM Forest Simmons <forest.simmons21 at gmail.com>
>> wrote:
>>
>>> First a preliminary procedure to make sure no single candidate defeats
>>> every member of the support of the random ballot favorite:
>>> As long as there is such a candidate, retain only candidates of this
>>> índole, recalibrating between elimination steps.
>>>
>>>
>>> Next: a non-deterministic lottery method ... Random Ballot Favorite
>>> Chain Climbing (RBFCC):
>>>
>>> Shuffle the ballots into some random order B1, B2, B3, ... and let ListF
>>> be a list of the candidates in the order induced by the first choices of
>>> the respective ballots in their order ... i.e. according to the order of
>>> their first appearance as a first choice on a ballot in the sequence B1,
>>> B2, B3, ...
>>>
>>> Now, Chain climb the list ListF by initializing the set variable CHAIN
>>> as the empty set, and then ....
>>> While some member of ListF defeats every member of CHAIN, add the first
>>> such candidate into CHAIN. EndWhile
>>>
>>> The head of the completed chain is the RBFCC (random trial) winner.
>>>
>>> Next, for each candidate X, let RBFCC(X) be the winning probability for
>>> X under this lottery.
>>>
>>> Finally, elect argmax RBFCC(X).
>>>
>>> Note that this method is Banks efficient, and obviously reduces to
>>> "fpA-SumfpC" in the eponymous three candidate case.
>>>
>>> On a practical note, should the computation of the RBFCC probabilities
>>> be intractable for some ballot set, then repeated trials in a MonteCarlo
>>> simulation of the lottery can be used to determine argmax RBFCC(X) with
>>> arbitrarily low error probability epsilon.
>>>
>>> Is this the simplest formulation of what we've been looking for?
>>>
>>> It doesn't seem like an easy method to "game".
>>>
>>> Other comments? Questions?
>>>
>>> Who can write this up in a way that Joe Q Public can easily relate to?
>>>
>>> -Forest
>>>
>>>
>>>
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20221021/323b54f7/attachment-0001.htm>