# [EM] STAR challenge

Forest Simmons forest.simmons21 at gmail.com
Wed Jun 8 11:48:00 PDT 2022

Both Benham-Score and Score based Sequential Pairwise Elimination can be
cast as Pairwise Sorted Score methods.

In both cases you start with the candidates listed in Score order, high to
low, top to bottom, and swap adjacent candidates that are out of order
pairwise until the final list is a pairwise "beat path" finish order. All
of the out-of-order adjacent pairs have been "rectified."

The difference in the two methods is the rectification priority. For
Benham, as long as there remains any adjacent pair out of order, rectify
the pair closest to the top of the list. For SPE, as long as there is any
adjacent pair out of order,  rectify the pair closest to the bottom of the
list. Thus we make a distinction between bubble sort and sink sort.

In either case the Smith set will end up at the top of the list.

However, if we think of rectification as correction of a tentative order,
based on error prone estimated merit, why not start with the pair for which
the score order is most tentative ... least confident?

Suppose the tentative order looks like
A*****************B**C, with B and C close in estimated score. Which
adjacent pair appears to be more secure, i.e. less tentative in its order?
Thinking in terms of hypothesis testing, which hypothesis would yield
higher confidence A>B or B>C?

That is the rationale for "Score Sorted Margins": prioritize rectifications
with least confidence in their score order ... i.e. where their positions
are only marginally distinguished by score.

This sorting rule makes use of information that is ignored by the bubble
and sink sort rules, and so gives it an edge (no matter how slight) on
accuracy.

It also satisfies a strong Reverse Symmetry property not enjoyed by other
sorts of sorting: if every ballot score x is replaced by 100-x, the finish
order will be precisely reversed.

For these reasons, all else being equal, I currently recommend Score Sorted
Margins over the other potential score/pairwise hybrids.

Here's an analogy that might help explain it:

Suppose that we want to have a Round Robin basketball tournament to rank
the teams from best to least.

It is agreed that if one team defeats all of the other teams, it will be
the champion team. But what if no team beats all of the others? Then the
teams tied for the most wins will have a free-throw contest to resolve the
tie.

But that just decides which team is ranked first. How about second, third
etc?

Somebody comes up with the idea of having the free throw contest moved up
front to the beginning of the tornament, to serve not only its tie breaking
purpose (should the need arise) but also to effectively and fairly seed the
match order.

Each team has each of their 12 players make as many free throws in a row as
possible before missing. The teams are listed in order of total team
successful free-throws, their team "seed score".

We start by interspersing question marks between the adjacent teams on the
list.

Then as long as there remains one or more question marks, find the question
mark separating the two teams closest in their team seed scores. Have these
teams play each other. If the one with the higher seed score beats (or
ties) the one with the lower seed score, simply remove the question mark.

Otherwise, swap the positions of the two teams in the list, remove the
question mark between them, and place question marks between them and their
other neighbors (if not already in place) to reflect the fact that their
relative rank order has not yet been confirmed.

When all of the question marks are gone, the final team finish order has
been reached.

Why is contest priority given to the teams closest in seed score?

Because if two teams are far apart in seed score, it is less likely that a
game between them would result in a swap, i.e. it is less likely that they
are out of order, i.e. more likely that just leaving them alone would not
be a mistake ... so not as urgent to test them against each other.

Thanks!

-Forest

P.S. IRV is like having a tournament consisting of successive free for all
games, where the team making the fewest points is eliminated from the next
free for all. until there are only two teams left, at which point a
regulation game by standard rules determines the tournament winner ... in
all more like a demolition derby than a sports tournament.

El mar., 7 de jun. de 2022 4:29 p. m., Andy Dienes <andydienes at gmail.com>
escribió:

> Hi Forest,
>
> If I am understanding RSTAR correctly, it should be the same as electing
> "the lowest score candidate that defeats all of the higher score
> candidates," right?
>
> It certainly sounds intuitive. How would it compare to, e.g. Score Chain
> Climbing?
>
> -Andy
>
> On Tue, Jun 7, 2022 at 6:36 PM Forest Simmons <forest.simmons21 at gmail.com>
> wrote:
>
>> Benham-Range is ISDA (department of agriculture?). In fact, it elects the
>> lowest score candidate that defeats all of the higher score candidates.
>>
>> So it is a simple proposal with lots of heuristic rationales and criteria
>> compliances going for it.
>>
>> Another similar ISDA proposal that I call RSTAR for reasons soon
>> apparent, always elects the highest score Smith candidate in the three
>> candidate case:
>>
>> RSTAR like STAR can be formulated as a procedure that takes a set of
>> score ballots as input, and selects as output a winner from among the
>> scored candidates on the input ballots.
>>
>> For comparison, here's a formulation of STAR in that format:
>>
>> Let beta be a set of Score ballots.
>>
>> Then the STAR output STAR(beta) is the winner of the two candidate runoff
>> between X=Score(beta) and Y=Score(beta'), where beta' is the set of ballots
>> with candidate X temporarily removed.
>>
>> The RSTAR output RSTAR(beta) is the winner of the two candidate runoff
>> between X=Score(beta) and Y=RSTAR(beta'), where beta' is the set of ballots
>> with candidate X temporarily removed.
>>
>> See the comparison (and tiny contrast)? If you see it and understand it,
>> then you know that RSTAR must stand for Recursive STAR.
>>
>> This is the most succinct formulation of SPE(Score), Sequential Pairwise
>> Elimination with a Score based agenda.
>>
>> Since SPE is a respectable, classical method with a hoary history of use
>> in deliberative assemblies, as prescribed by Robert's Rules of Order, this
>> would be an impeccable public proposal.
>>
>> The Recursive formulation should serve only as a bridge between STAR and
>> the less exotic SPE formulation; we don't want any heads to explode!
>>
>> What say ye?
>>
>> -Forest
>>
>> ["Ye" is an archaic form of "ya'll" or "youse guys" ;>)]
>>
>> El mar., 7 de jun. de 2022 10:51 a. m., Forest Simmons <
>> forest.simmons21 at gmail.com> escribió:
>>
>>> Very good observations ...and I like your method suggestions.
>>> Benham-Range (without the renormaliization),unlike ordinal Benham, should
>>> also be monotone and precinct summable if I understand it correctly.
>>>
>>> El mar., 7 de jun. de 2022 5:12 a. m., Kristofer Munsterhjelm <
>>> km_elmet at t-online.de> escribió:
>>>
>>>> On 07.06.2022 05:49, Forest Simmons wrote:
>>>> > VSE (voter satisfaction efficiency) simulations seem to bear out that
>>>> > STAR is a significant improvement over plain old Score voting, but not
>>>> > quite as good as Score restricted to the Smith Set.
>>>> >
>>>> > So it appears that simple STAR is the low hanging fruit worth some
>>>> trial
>>>> > and error tweaking experiments to convert it into the best public
>>>> proposal.
>>>>
>>>> I'd say there are two ideas of generalizing STAR, call them cardinal and
>>>> ordinal. The cardinal one should preserve the property that in an LCR
>>>> election where the centrist is highly rated, he wins, but where he's
>>>> ranked poorly, he loses. (Making this cloneproof without just degrading
>>>> to plain Range is hard!)
>>>>
>>>
>>> That's the idea of my suggestion ... pit the Martin Harper Lottery top
>>> probability candidate against the score winner ... or I could have
>>> suggested a runoff between the two top probability lottery candidates.
>>>
>>> Better yet ... do Sequential Pairwise Elimination on the support of the
>>> MH Lottery, where the agenda order is from least to greatest probability.
>>>
>>> The MH Lottery is based on an idea for
>>> Range-->Plurality DSV: given all of the Range ballots, how should you
>>> decide which candidate ballot B should support (from the superstitious
>>> one-person-one-vote point of view)?
>>>
>>> Answer: the candidate X should have a high score B(X) on ballot B, and
>>> should have high support  from the other ballots as well. The support of X
>>> from the other candidates can be gauged by its total score S(X). So X
>>> should be the candidate that maximizes the product B(X)S(X).
>>>
>>> Which is why the Martin Harper Lottery probability for candidate X is
>>> the percentage of the ballots B for which X maximizes the product B(X)S(X).
>>>
>>> [In 2001 Martin Harper posted to the EM list a definitive explanation
>>> for diehard IRV supporters of how Approval utterly satisfies "one person
>>> one vote" by way of a memorable Maxwell's Demon vote shuttling mechanism.
>>> So it is only fitting that Harper get the credit for this lottery idea!]
>>>
>>>>
>>>> The ordinal one, on the other hand, should find the CW whenever he
>>>> exists, and probably also elect from some nice set (Smith, Landau or
>>>> Banks). STAR itself doesn't do this.
>>>>
>>>> > Some brainstorming is definitely in order. Ted Stern has been working
>>>> on
>>>> > this.
>>>> >
>>>> > Some possible directions:
>>>> >
>>>> > 1. Simplify the description of Score restricted to Smith to be on a
>>>> par
>>>> > with the simplest description of STAR
>>>> >
>>>> > 2. Find a better runoff opponent for the score winner.
>>>> >
>>>> > 3. Compare STAR with Score Sorted Margins and Sequential Pairwise
>>>> > Elimination based on a Score agenda.
>>>> >
>>>> > Here's one idea:
>>>> >
>>>> > For each ballot B, and  each candidate X, let B(X) be ballot B's score
>>>> > for candidate X. Let S(X) be the sum over B of B(X). Then the score
>>>> > winner is the candidate X that maximizes S(X). Elect the winner of the
>>>> > runoff between the score winner and the candidate X that on the
>>>> greatest
>>>> > number of ballots B, maximizes the product B(X)S(X).
>>>>
>>>> I haven't thought about it in detail, but I think Range's de jure IIA
>>>> compliance implies that Benham-Range and BTR-Range are both Smith. They
>>>> might even be equivalent to Smith,Range. So if you want to look for a
>>>> simpler way of explaining Smith,Range, those may be it.
>>>>
>>>> My thinking is like this, for Benham-Range:
>>>>
>>>> Benham-Range eliminates the current Range loser until there's a CW.
>>>> Since Range passes IIA, eliminating without normalization doesn't change
>>>> the order of the other candidates. Hence all but one Smith set member
>>>> will be eliminated, after which the highest scoring Smith set member
>>>> becomes the CW and wins. So Benham-Range is just Smith,Range and may be
>>>> easier to explain.
>>>>
>>>> Benham-BTR I'm much less sure about because it protects the loser who
>>>> pairwise defeats the other. This is more like STAR. It might be that a
>>>> prospective loser is protected all the way up the Smith set, and then
>>>> beats the highest rated Smith set member pairwise -- unless such a
>>>> scenario is impossible.
>>>>
>>>> For runoffs, I think you could argue in two ways. Either the runoff is
>>>> about telling two quite good candidates apart, or it's about giving each
>>>> faction of the electorate "their" candidate to vote for. The former
>>>> suggests (if it's a manual runoff) just picking the two Smith set
>>>> members with the highest rating; the latter, something more like "the
>>>> candidate rated highest by voters who rated the first candidate low".
>>>>
>>>> If I had to choose, I'd probably go for the former, though it could
>>>> affect the turnout in the general: if both candidates are good, a lot of
>>>> voters may simply decide not to vote in the general.
>>>>
>>>> Automating the former, STAR would probably do a good job because it's
>>>> unusual for a candidate to be the CW yet not in the top two by highest
>>>> rating. At least it gets the bang for the buck award, even if it's not
>>>> perfect :-)
>>>>
>>>> -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/20220608/cf66c804/attachment-0001.html>