[EM] Random Ballot Favorite Chain Climbing/Building

[Forest Simmons]

In the quoted message I did a sloppy job of hand waving to convince myself
that Random Ballot Favorite Chain Building (RBFCB) gives the same result as
fpA-fpC in the prototypical example.

I sloppily conjured a formula out of the clear blue for the RBFCB winning
probabilities, and then asserted without proof that it turned out to be
equivalent to the max(fpA-fpC) criterion.

I was depending on mental graphs of the two formulae to coincide for a
quick confirmation of my intuition, but it turns out that the online
Wolfram Alpha plotter is very persnickety about 3D graphics ... it just
gives up way too soon!

So let's take a more careful run at it, and let the chips fall where they
may ... if it turns out that these two methods are not equivalent, then we
have two nice voting methods instead of only one:-)

Let's approach the problem from a Markov process point of view. The
possible states of the chain are the initial empty set {}, the singletons
A, B, and C; and the possible completed maximal chains A>B, B>C, and C>A.

We need to construct a transition matrix of the transition probabilities
from the various states to the new states as the process evolves. One
should draw a directed graph with arrows showing the state transitions.
Those arrows should be labeled with the respective transition
probabilities.
Once the digraph is properly labeled, the transition matrix can be read off
directly from the digraph.

In this case the digraph is a tree, with the initial empty state {}  as the
root node.

The three arrows emanating from it enter the three singleton states A, B,
and C. The corresponding arrows are labeled with the transition
probabilities p, q, and r, respectively.

These singleton states have arrows connecting them to the maximal states:

arrows from A to A>B and from A to C>A, as well as arrows from B to both
B>C and  A>B, and arrows from C to both C>A and B>C.

What are the respective transition probabilities that should serve as
labels for these arrows from the singleton states to the final states?

This is where we have to be careful ... sloppy handwaving will not do here!

Why is it so tricky? Because the transitions from the single states to the
final states are "conditional probabilities."

For example, the transition from A to A>B has a conditional probability of
q/(q+r), rather than the straight probability q.

Why is that? Because (at this stage) when we draw a ballot whose favorite
candidate is A, we must ignore it and draw again until we get a ballot with
a B or C favorite, since we already have an A in our current Markov state.

So the respective transitions from A to A>B and from A to C>A, are the only
possibilities, which means their probabilities must sum to unity.

Imagine that there are 20 A ballots, 35 B ballots and 45 C ballots, and we
must ignore all of the A ballots if drawn, because only one A can be
incorporated into the chain, which it already has, since our transition is
from state A to A>B or to C>A.

There are 80 currently active ballots still in play at this juncture... 35
B's and 45 C's, so the respective conditional transition probabilities are
evidently 35/80 and 45/80.  In general, they would be q/(q+r) and r/(q+r).

Check that they add up to unity, just as 35/80 and 45/80 do.

Now that we have the transition arrows labeled, how do we figure the
probabilities of the final states, the leaves of the tree representing the
completed chain?

First we multiply the transition probabilities along each path to get the
probability of the leaf state the end of the path.

For A the path from A>B through singleton B has a value of qp/(p+r), while
the path through the singleton A state has a value of pq/(q+r).

We add these two path values together to get the probability of the chain
A>B.
This sum, qp/(p+r)+pq/(q+r),
 is A's chance of winning the RBFCB election lottery :

Similar expressions give the winning probabilities for B and C.

To simplify the expressions we make use of the grand common denominator
(q+r)(r+p)(p+q). This common denominator can be employed to clear the
fractions on the rationale that when all denominators are equal, the
largest fraction is the one with the largest numerator.

So A's numerator will be
pq(p+q)(q+r+r+p), which simplifies to
pq(1-r)(1+r), since q+r+p is just 1.

If we divide every such expression by pqr, we maintain the proportionality,
and we see that the winning probability for A is proportional to (1-rr)/ r,
or 1/r -r. In other words, the bigger 1/r-r, the better  A's chance of
winning. But this expression is monotone decreasing in r, so the smaller r,
the greater A's chance of winning.

Can we conclude that A wins iff and only if r<min(p,q)?

At least we can safely conclude that A wins if (1/r-r)>max(1/p-p,1/q-q).

This makes sense intuitively because r is the probability of drawing a
ballot favoring C, which is the only candidate that defeats A.

One should compare graphically the above condition(1/r-r)>max(1/p-p,1/q-q)
with the corresponding fpA-fpC condition
(p-q)>max(q-r,r-p)
to see how close they are.

I think we can see how useless it is for the A supporters to bury C. It
does not change A's chance of winning the RBFCB lottery at all!

On the other hand, increasing A's first place support can help A only
indirectly ...by competing for C's first place support.

Check my algebra and Markov tree reasoning.

It would be easy to check these results independently with MonteCarlo
simulations.

-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/7ac1a082/attachment.htm>