On 09.01.2022 00:58, Daniel Carrera wrote:

Ranked Pairs is in the minmax group (second type).

Perhaps you misspelled it - it isn't Behman but Benham. You should be
able to find it at https://electowiki.org/wiki/Benham's_method :-)

As for why the Condorcet-IRV methods resist strategy better, I think
it's a combination of dominant mutual third burial resistance (which
also renders the method immune to the DH3 scenario) and chicken dilemma
resistance.

An example of the three categories can be seen on the left in
https://www.votingmatters.org.uk/ISSUE29/I29P1.pdf, on page 8. Borda is
in the top category, minmax is well, in minmax, and IRV and the
Condorcet-IRV hybrid (Woodall) are at the bottom.

Unfortunately, pretty much every method in the resistant category is
nonmonotone. fpA-fpC (which Kevin calls my Linear method) is monotone
and passes both DMTBR and chicken resistance, but I don't know how to
extend it to a Smith set of more than three candidates.

It should be possible - my integer programs have found optimally
resistant methods for more than three candidates, for a low number of
voters, but only in lookup table form. The results show that insisting
on monotonicity doesn't make the methods any more susceptible to
strategy, at least not with few voters. But how to do it remains a
mystery, still.

-km

Kevin,

Great data!

See my inline response to your astute musings below ...

El sáb., 8 de ene. de 2022 2:48 p. m., Kevin Venzke stepjak@yahoo.fr
escribió:

I agree completely. All Condorcet methods elect ballot Condorcet candidates
(when they exist) 100% of the time by definition.

Now which methods will elect the sincere CW candidate C, when the sincere
(not ballot) preferences are given by

40 A>C
35 B>C
25 C>A

???

Answer: The methods that are known to automatically backfire on an A
faction burial of C under B.

TACC is such a method. If it is the official method, and word gets around
that burial doesn't pay under TACC, then there will be no burial, so C will
be elected.

But if the official method is Shulze, RP, MinMax, or any other method that
breaks a cycle at its weakest defeat ... that method may very well elect A,
depending on how opportunistic the A faction is.

If the A faction buries the sincere CW under B, and the majority that
prefers C over A takes no deliberate counter measure, then A will win.

To me, this means that effectively TACC has greater Condorcet efficiency
than any of the highly vaunted Condorcet methods.

Their problem is that their design is based on Condorcet's quaint heuristic
of setting out to correct mistaken opinions or "propositions," as opposed
to guarding against intentional gaming of the method.

"The opinion of a larger majority is more likely to be correct than that of
a smaller majority." ... in other words, a naïve statistical heuristic
versus a realistic game theoretic guide.

A cycle that was created intentionally is treated as though it was an
innocent error to be corrected by an information theoretic/statistical
approach. "The weakest link is the proposition least likely to be correct."

Trying to divine the true message from an intentionally garbled signal is
like trying to put humpty-dumpty back together... the proverbial highly
fraught cure (ambulance at the bottom of the ckiff) instead of prevention
(guard rail at the top).

Crime shouldn't pay! Even though most people are honest, let's observe the
wisdom of the anti-fragility design principle!

The Quick & Dirty/Clean version of TACC is a simple, transparent method
that holds up to this robust design principle:

Elect the most approved candidate not defeated pairwise by the least
implicitly approved Smith candidate.

(So the elected candidate is not the one responsible for the low implicit
approval of the presumed burial victim.)

What about the possibility of a sincere cycle where the Condorcet/Eppley
heuristic is actually relevant?

The highest approval candidate not beaten by the weakest Smith candidate
has to be a Smith candidate itself .. no small achievement ... and can
respond to a complaint from an higher approval Smith candidate, "At least I
was not beaten pairwise by the weak approval candidate that beat you!"

So taking into account its monotonicity and at least marginal clone
independence (no worse than Approval's), this Q&D/C method seems fairly
promising in the class of Universal Domain methods ... so far, so good!

Richard,

Here are two hand count methods for constructing the Smith set (off the top
of my head):

Method 1:

List the candidates in any convenient order. Then sort the list pairwise.
The Smith set consists of all of the candidates in the sorted list above
some cutoff level.

Usually that cutoff level can be quickly found by "inspection." But here's
a systematic procedure.

Start with the tentative cutoff just below the candidate at the top of the
sorted list. Then ..
While there remains any candidate with questionable Smith status,  let C be
the highest such candidate. If C pairwise defeats a candidate above the
current cutoff, then lower the cutoff to the position immediately below C.
Else mark C as "non-Smith".
EndWhile

Method 2:

Borrow a handheld calculator having matrix multiplication capability.
Initialize an n×n matrix (where n is the number of candidates) with all
ones, including the main diagonal.

For each (i, j) combination where i  and j are not equal, if candidate i
does not defeat candidate j pairwise, then zero out the j_th element of the
i_th row.

Now square this matrix repeatedly until the number of zero entries
stabilizes.

[This will take fewer than ceiling(log(n)/log(2)) squarings. So for 1000
candidates, fewer than ten squarings.]

The rows that end up with all positive entries are the Smith candidate
rows. Rows with one or more zero entries correspond to non-Smith candidates.

If you are doing this by hand, you can speed this up drastically by
replacing the sums of products that define matrix multiplication with "sups
of infs":

For squaring the matrix M, replace the (i,k) entry of M^2  given by the sum
of products

Sum (over j) of m(i,j)*m(j,k)

with the max of mins

Max(over j) of Min(m(i,j), m(j,k))

This limits all entries to zeros and ones, making the computations trivial
(though still tedious in the case of hundreds of candidates). It gets
faster with practice... the limit to your speed is how fast you can write
zeros and ones into n×n arrays.

It's kind of fun once you get the hang of it ... you haven't really lived
without having mastered this technique!

El vie., 7 de ene. de 2022 5:42 p. m., Richard, the VoteFair guy <
electionmethods@votefair.org> escribió:

See a slight correction in the first method, below ...

Also, once you have Smith, the TopTwoRunoff is no longer necessary; just
elect the  Smith candidate ranked on the most ballots.

If you wanted to go the extra mile so as to have a burial resistant method,
Elect the candidate ranked on the most ballots that is not defeated
pairwise by the Smith candidate ranked on the fewest ballots.

-Forest

El sáb., 8 de ene. de 2022 7:01 p. m., Forest Simmons <
forest.simmons21@gmail.com> escribió:

Change this designation to "not a Smith set cutoff candidate"

EndWhile

On Sat, Jan 8, 2022 at 6:20 PM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:

Thanks! I've read the paper. This is really interesting. I tried to write a
program to reproduce the experiment so I could add other Condorcet-IRV
methods (IRV-BTR and Raynaud(Gross Loser)) but I got stuck. I couldn't
figure out how to implement the coalition of strategic voters. The paper
doesn't really explain how it's done. It says:

"In order to avoid massive computational
cost, I make the restrictive assumption that all
voters in the strategic coalition must cast the
same ballot"

I couldn't figure out how to decide which voters need to be in the
coalition or what ballot they need to cast to maximize their chances.

In any event, I was also interested in that big table that shows the
features of the systems (MAP/MA, ISDA, etc). I would love to see a table
like that for Condorcet systems. Something like the one on Wikipedia, but
more granular. For example, I saw on the electowiki that IRV-BTR and
Raynaud pass ISDA, but it wasn't clear whether Raynaud(Gross Loser). In the
paper, the methods that pass ISDA (Smith-AV and Tideman) also
fail mono-add-plump and mono-append and I'm wondering if that's always
true, or if it's just incidental.

I'm not familiar with fpA-fpC. Is that in the wiki somewhere?

--
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University

On 09.01.2022 23:07, Daniel Carrera wrote:

In quadelect (my election simulator), I just do this:

for n = 1...numiters:
e_A = sample a random v-voter c-candidate election according to some
given distribution
w_A = winner of e_A according to method M
for c_k in every candidate but w_A:
for i = 1...strategy_iters:
e_B = e_A
for every ballot B in e_B:
if B ranks c_k ahead of w_A:
replace B with a random preference order
w_B = winner of e_B according to method M
if w_B = c_k:
then strategy successful
if strategy successful:
increment number of strategy successes SS
else:
increment number of strategy failures SF

strategic susceptibility = SS/(SS+SF)

It underestimates susceptibility with large numbers of voters but should
give approximately the same results as JGA with his orders of magnitude.
You could of course optimize the pseudocode by aborting the inner loop
as soon as you have a successful strategy (and skipping the whole test
if there's a candidate with a majority of the first preferences).

I also have some quick and dirty code for exact strategic susceptibility
for impartial culture with small numbers of voters and candidates (3 or
4 candidates, <11 voters) where enumerating every election is possible,
but it's not particularly nice.

If you want to do it JGA style, you would replace the inner loop with
something like:

for 1...strategy_iters:
e_B = e_A
b_B = random preference order
for every ballot B in e_B:
if B ranks c_k ahead of w_A:
B = b_B
w_B = winner of e_B according to method M
if w_B = c_k:
then strategy successful

https://electowiki.org/wiki/Raynaud suggests that all versions of
Raynaud pass ISDA, including Raynaud(GL). I agree, it would be useful to
have a table, but it wouldn't be practical to render it for all criteria
defined on electowiki; it would need some kind of interactive component
so you could select just the criteria (and methods) that interest you.

I don't know if ISDA implies failure of the two monotonicity criteria. I
know that it's open whether Smith is compatible with mono-add-top (which
imples mono-add-plump), and that you can't have all three of Smith,
Plurality, and mono-add-top. But I don't think anyone has investigated
whether ISDA implies failure of the two other monotonicity criteria.

Yep, https://electowiki.org/wiki/fpA-fpC should do it.

-km

On Sun, Jan 9, 2022 at 4:41 PM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:

Hmm... The numbers I'm getting are a lot smaller than those in the paper.
I'm using Benham, V=99, N=1, C=6 and the voters and candidates follow a
standard normal, just as in the paper. I chose those parameters because
Table 1 gives a strategic susceptibility of 0.622 which should be easy to
detect, but I'm only getting 0.00196; so off by over two orders of
magnitude. I don't have as many iterations (numiter = 100, strategy_iters =
100) but that should not change the overall scale.

It's hard to see how randomly shuffling ballots would be a strategy. I
tried changing the strategy: after the random ballot is generated,
candidate c_k is moved to the top and w_A to the bottom. That simple
strategy increases the susceptibility to 0.0785, but that's still one order
of magnitude off from the paper.

https://electowiki.org/wiki/Raynaud suggests that all versions of

I shouldn't get distracted with this right now, but maybe in a few months I
could make a Google spreadsheet --- a poor man's interactive database.

--
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University

On 10.01.2022 01:14, Daniel Carrera wrote:

Try using impartial culture (every preference order is equally likely;
just do a standard shuffle on the order of candidates to get the ballot
order) and both iter counts = 1000. This should be easier to test than
Gaussian; I remember I got different results than JGA on Gaussian myself.

For comparison purposes, here are some results from quadelect for
Condorcet,IRV. The ranges are a 95% c.i.:

Gaussian, sigma = 0.2: 15 voters, 3 candidates: 0.0784-0.0862
Gaussian, sigma = 0.2: 30 voters, 3 candidates: 0.0784-0.0862
Gaussian, sigma = 0.2: 100 voters, 3 candidates: 0.0404-0.0462
Gaussian, sigma = 0.2: 1000 voters, 3 candidates: 0.0256-0.0303

Impartial culture: 15 voters, 3 candidates: 0.1101-0.1191
Impartial culture: 30 voters, 3 candidates: 0.1491-0.1593
Impartial culture: 100 voters, 3 candidates: 0.2428-0.2550
Impartial culture: 1000 voters, 3 candidates: 0.1588-0.1692

And to try to reproduce JGA's results under impartial culture:

29 voters, 3 candidates: 0.1363-0.1461 (JGA: 0.099)
29 voters, 4 candidates: 0.2838-0.2967 (JGA: 0.188)
29 voters, 5 candidates: 0.3936-0.4074 (JGA: 0.282)
29 voters, 6 candidates: 0.5065-0.5206 (JGA: 0.355)
29 voters, 7 candidates: 0.5761-0.5901

The JGA figures aren't entirely comparable because they're for Benham,
Woodall, and Smith-IRV, while one would expect Condorcet-IRV to be
slightly more manipulable. I probably get higher values because I'm not
restricted to a single ballot for the strategizers' choice.

And 99 voters:

3 candidates: 0.1353-0.1451 (JGA: 0.088)
4 candidates: 0.261-0.2735  (JGA: 0.180)
5 candidates: 0.3779-0.3916 (JGA: 0.255)
6 candidates: 0.4602-0.4743 (JGA: 0.312)
7 candidates: 0.5245-0.5386

This is with numiters=1000, strategy_iters=512.

It sounds like you interpreted my "random preference order" to mean
"some other random ballot in that election"... I mean just a random
preference order (drawn from impartial culture). So e.g. if the honest
ballots are

10: A>B>C
10: C>B>A
1: B>A>C

and A wins, then one of the C>B>A ballots can well be replaced by say,
B>C>A even though that ballot occurs nowhere in the honest election.

On Mon, Jan 10, 2022 at 11:27 AM Kristofer Munsterhjelm <
km_elmet@t-online.de> wrote:

No, I understood that part. However, looking at your pseudocode again, I
just realized that you choose the random ballot once per strategy_iters and
reuse that ballot for every single voter that did not prefer w_A:

for 1...strategy_iters:
e_B = e_A
b_B = random preference order
for every ballot B in e_B:
if B ranks c_k ahead of w_A:
B = b_B
w_B = winner of e_B according to method M
if w_B = c_k:
then strategy successful

That makes a lot more sense now. Now I see what the paper means when it
says that it gets every voter in the strategic coalition to cast the same
ballot. When I read your first pseudocode I thought it meant that every
single voter with c_k > w_A would draw a different random permutation. So
you see why I was confused and why it didn't work. So I fixed this, and
fixed other bugs. I also followed your advice and switched to "impartial
culture".

Impartial culture: 15 voters, 3 candidates:

Your result:  0.1101-0.1191
My result:  ~0.06

So I'm still off by a fair bit, but at least now I'm in the correct
magnitude range. I'm going to look around to see if I find another bug.

Cheers,

Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University

On Tue, Jan 11, 2022 at 2:32 PM Daniel Carrera dcarrera@gmail.com wrote:

Aha! I had the SS += 1 vs SF += 1 counter in the wrong loop. Using your
pseudocode:

for n = 1...numiters:
e_A = sample election
w_A = winner of e_A according to method M
for c_k in every candidate but w_A:
for i = 1...strategy_iters:
...
if strategy successful:
increment number of strategy successes SS
else:
increment number of strategy failures SF

I had the if statement in the for c_k in every ... loop. Moving it back
down where it belongs gives me strategy success rates in the same range as
yours.

Your result:  0.1101-0.1191  (95% c.i.)
My result:    0.0923-0.1250  (95% c.i.)

It is comforting that my interval contains yours. The wider interval
probably just reflects that I'm using fewer elections because I'm testing
the code. I'm running sets of 1,000 elections and the paper uses 10,000.

Thanks for the help!

Cheers,

Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University