[EM] Random Ballot Favorite Chain Climbing/Building

[Forest Simmons]

Good news ... the monotone decreasing property of (1/r)-r does indeed show
that in our prototypical three candidate cycle that the winner is A, B, or
C, depending on which of r, p, or q is smaller. In other words, depending
on which of fpC, fpA, or fpB is smaller.

In other words, un the three candidate Smith case the RBFCB method (the
deterministic version) is equivalent to Ranked Pairs or Beatpath CSSD, or
River with defeat strength gauged by bow few (not how many!) first place
votes the losing candidate has in opposition to the winner.

For all practical purposes RP(lack of losing first place opposition) is
equivalent to RBFPCB. The public proposal could describe it either way ...
you could just call it "lack of first place votes" or LFPV Condorcet.

For clarity, in the ABCA cycle if C has fewer first place votes against A,
than A has against B, or B against C, then the cycle is broken at the
weakest link ... the CA link, so the ABCA cycle is replaced with the
(strongest) beatpath ABC, making A the winner.

Thanks for your patience!

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

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