[EM] Testing rank strategy incentives given explicit approval cutoffs

[Kevin Venzke]

(the image links for easy access:)
https://votingmethods.net/img/cutoffs_5b4c_topvsbottom.png
https://votingmethods.net/img/cutoffs_5b4c_cond.png

Hello,

One possible motivation for rank ballot methods that incorporate an explicit approval
cutoff, is the possibility of removing the voter's incentives to strategically
misrepresent their rankings, and instead, as a lesser evil, we try to confine
strategy to the placement of the approval cutoff.

How to measure the extent to which ranking strategy is reduced? One possible
approach is to assume that voters primarily care about whether one (any) of their
approved candidates wins. In that case, we can at least say that when a voter
rearranges their rankings on either side of their approval cutoff, this should not
change whether the winner is one of the voter's approved candidates.

Intuitively this suggests four properties, something like "top (or bottom) shuffle
no help (or harm)." Though each pair of "help" and "harm" ought to be associated,
since e.g. any failure of "top shuffle no harm" can simply be reversed to obtain a
failure of "top shuffle no help." But it's easier to try to detect the four issues
separately.

A small class of methods can get perfect scores on these properties, but as a rule
they don't satisfy Majority Favorite. These methods either purely use the approval
data to find a winner (like Approval itself, and 2-slot MMPO), or they find two
finalists using the approval data and elect the pairwise winner between them (like
"ATAR," an approval-based take on STAR).

Among methods that do satisfy Majority Favorite, a few (such as FPP and IRV) still
get a perfect score with the "bottom shuffle" properties.

Also, nothing stops us from applying these criteria to rank methods without an
explicit cutoff. We can understand that the voter placed a cutoff and the method
ignored it in its resolution.

For an experiment I ran 10k elections of 4 candidates and 5 blocs (random sizes).
Every bloc submits a full ranking, and an approval cutoff placed at a random
position (but such that at least one candidate is on each side of the cutoff). This
should make the approval scores, on their own, a mediocre indication of the "best"
winner.

For each election, for each bloc, where logical, I made a single random attempt for
each of the four properties mentioned above, to shuffle the bloc's rankings on one
side of the cutoff. If the property was violated, then the scenario was counted to
the tally of failures for that property. Then for simplicity I added the two "top
shuffle" properties together to get one score for top shuffling, and likewise for
bottom shuffling. I also found an overall score by adding all four tallies
together. Since these tallies consequently can double-count the same scenario, it's
difficult to describe what the final scores are measuring. But I'm not that worried
about it currently.

Here are a couple of scatter charts showing some results.

First: "top shuffle" failures on the X axis, and "bottom shuffle" failures on the Y
axis. Condorcet methods are colored red.
https://votingmethods.net/img/cutoffs_5b4c_topvsbottom.png

Second: the sum of shuffle failures on the X axis, and voted Condorcet efficiency on
the Y axis. Condorcet methods just sit along the top, at 100%, because scenarios
without a Condorcet winner were disregarded for the Condorcet metric.
https://votingmethods.net/img/cutoffs_5b4c_cond.png

Note that every method that normally uses an approval concept is here using an
explicit approval cutoff (for example, TACC, MAMPO, MDDA v2, C//A...).

I want to call out just a few of the best performances shown in these images.

1. Among methods satisfying Majority Favorite, Approval Elimination Runoff (AER)
appeared to be the best method from the shuffle strategy standpoint. The "top
shuffle" performance was very slightly better than the best Condorcet methods, and
the "bottom shuffle" performance was an IRV-like perfect score. That is to say,
rearranging your disapproved candidates in AER can't change whether the winner is
one of your approved candidates. But note that AER's voted Condorcet efficiency was
only 91.6%.

(I define AER like this: Determine an elimination order using ascending approval
scores. Voters have a transferable vote as in IRV that starts with their top
preference. While there is no candidate with a majority of votes from the
non-exhausted ballots, eliminate the next candidate. But recall that in this
simulation, all the rankings were full.)

2. Among Condorcet methods, the overall best methods are the trio of Definite
Majority Choice (DMC), Approval Elimination Condorcet (AEC), and MinMax(Winner's
Approval) which are, all three, practically identical methods. Among Condorcet
methods these minimize both top and bottom shuffling failures, with one asterisk.

3. The asterisk to this is what I've labeled "BAW" for "Beats Approval Winner." This
is an approval-based adaptation of Eivind Stensholt's BPW method, extended to 4+
candidates using chain climbing. That is to say, we start with an empty "chain," and
we go through the candidates in order of decreasing approval. At each candidate, we
add them to the end of the chain if they pairwise defeat every candidate already in
the chain (if any). Elect the last candidate added to the chain.

This is an asterisk in that, among Condorcet methods, BAW showed the fewest "bottom
shuffle" failures. This reflects a difficulty in executing a burial strategy in BAW.
Suppose that A won as CW, but you as a voter want B to win, and you want to use some
candidate C to create an artificial pairwise win C>A. What happens in BAW?

a) if A is the approval winner (AW), then A has only one loss, to C. A is added to
the chain immediately; no one else but C can be added afterwards, and so C is
elected. The strategy backfires.
b) if B is the AW, we know that B definitely does not win, because at least one
candidate (such as A) will be able to be added to the chain after B.
c) if C is the AW, then it's possible that B could win and the strategy succeeds.
However, it is unusual to think of using the approval winner as a pawn in a burial
strategy, because it's intuitively dangerous to give "fake" support to a candidate
who has a lot of viability already.
d) if some other candidate is the AW, then this candidate won't win, but aside from
that it's not clear what happens.

Of course BAW, like BPW, is non-monotone in a jarring way. In a cycle, the
"strongest" candidate always loses.

Different simulation parameters could give different results from this, but for a
first look I thought it was worth a post.

Kevin
votingmethods.net