[EM] A proxy for Monroe's "strategic election of universally loathed candidates" criterion

[Kristofer Munsterhjelm]

So I'm gonna try this list thing again. We'll see how the plonking goes. 
But I'm kind of tired of debate, (particularly the sort that ends in 
back-and-forth insults,) so let's try something a bit closer to research.

Before I left, there was a mention of Monroe's Nonelection of Irrelevant 
Alternatives as a measure of burial resistance, so I tried to play with 
it a bit. But I found it very hard because you have to come up with 
separate Myerson-Weber strategies depending on the method and their 
state spaces. (So hard that Monroe might actually have got some of the 
failure results in his draft paper wrong!) So I thought I'd try to find 
a more... mechanically applicable criterion that would imply NIA - i.e. 
if a method passes this, it passes NIA.

And I think I've found two. One that's still pretty complex but that can 
be checked purely mechanically (at least for ranked methods), and 
another that's much easier but limited to majoritarian unrestricted 
domain methods. Both criteria only properly cover/imply NIA if the 
method also passes a (pretty straightforward) mono-add-plump-related 
criterion.

(One might seriously question the relevance or realism of the knife's 
edge election that follows, but such a knife's edge is what Monroe based 
his reasoning on, so...)

Both criteria start with a three-candidate honest election of the form:

	N: A>B>C
	N: B>A>C
	1: C>A>B
	1: C>B>A

with N being a very large number (or equivalently, replace the C-faction 
weights with some infinitesimal epsilon). The idea is that most methods 
will give this as an A=B tie. Then there might exist some risky 
strategic ballot that the A faction can cast, and some risky strategic 
ballot that the B faction can cast, so that if one of them does so, then 
their candidate wins, but if both do it, then C wins.

The A and B factions are balanced so that there's initially a tie. And 
the incredibly weak C faction exists to stop a method from passing the 
criteria by refusing to elect candidates who have no first preferences. 
The C-faction also helps restore results that Monroe might have got 
wrong, thus being closer to the spirit of his criterion.

So let's go to the criteria.

The complex criterion is the "strong non-collapse tie criterion" or 
SNCTC for short. I'm going to limit myself to deterministic methods 
because handling nondeterministic ones seems to come with a ton of 
corner cases.

I'll also call the A-faction just "A" and similarly for the other factions.

Here's the SNCTC definition:

===

If C is elected (wins or ties) in the honest election, then the method 
fails.

Otherwise, define an effective ballot s for A as one that:
	1. when A casts s instead of his honest ballot, A becomes the only 
winner, and
	2. no matter what ballot t B casts, if A casts s and B casts t, B does 
not become the unique winner.
If A has no such effective ballots, then let every ballot that satisfies 
the first point above be an effective ballot for A. (If A still has no 
effective ballots, that's okay.)

B's effective ballots are defined similarly. Note that the honest ballot 
may be effective if the faction's favorite wins outright.

If only one side has any effective ballots, then we pass (because the 
side without effective ballots can't unilaterally make their candidate 
win, so the collapse can't occur).

If there exists an effective ballot s for A so that no matter what 
effective ballot t that B chooses, if A casts s and B casats t, then C 
doesn't win; and the same is true (with the faction labels flipped) of 
the B faction; then we pass.

Otherwise, we fail.

For methods that are more expressive than ranked ones, the above must 
hold for every election whose rank data correspond to the honest ranked 
election. E.g. for a rated method, every rated ballot where the A 
faction rates A higher than B and B higher than C, the B faction rates B 
higher than A and A higher than C, etc., must pass. The criterion is 
inapplicable to methods that are *less* expressive (like Approval).

===

The point is that an effective ballot by A is a strategy (either safe or 
risky) that can't be exploited by B: i.e. A casting it improves A's 
winning chances without B being able to exploit this by casting some 
other ballot that makes B the winner.

By reasoning this way, when A and B strategize, they'll limit themselves 
to effective ballots.

Then we pass if A and B can't step on each other's toes no matter what 
effective ballots they use. No matter what they do, C is not going to win.


This is still pretty cumbersome, but for ranked methods with truncation 
and/or equal-rank, we can at least test every possible ballot to 
determine which ballots are effective. Rated methods require more 
general reasoning and can't be done mechanically.

So, let's say we want to simplify it even more. Here's a criterion for 
majoritarian unrestricted domain methods (i.e. no equal-rank or truncation):

DH2:

Let election e1 be:

		N: A>B>C
		N: B>A>C
		1: C>A>B
		1: C>B>A

Let election e2 be:

		N: A>C>B
		N: B>A>C
		1: C>A>B
		1: C>B>A

Let election e3 be:

		N: A>B>C
		N: B>C>A
		1: C>A>B
		1: C>B>A

And let election e4 be:

		N: A>C>B
		N: B>C>A
		1: C>A>B
		1: C>B>A

1. If C wins or ties for first in e1, the method fails.
2. If A doesn't uniquely win in e2, the method passes.
3. If B doesn't uniquely win in e3, the method passes.
4. If C doesn't win or tie for first in e4, the method passes.
Otherwise, the method fails.

The criterion is named after Warren Smith's DH3 ("dark horse plus 
three") because, in a sense, this is "dark horse plus two".

The explanation is:
	For 1.: if C wins in the first election, then C wins even without 
strategy, which is a failure. (I don't expect that to happen, but why 
not cover our bases?)

	For 2. and 3.: if unilateral burial doesn't break the tie in favor of 
the buriers, then the buriers have no reason to do it. (Particularly not 
if it makes C win too.) And if only one side (at most) has a reason to 
bury, then the combined effect of two sides burying can never happen, 
because only one side (at most) has any incentive to bury.

	And for 4.: if they both have incentive to bury, then the two burying 
at once must not make C win.

Why is this equivalent to SNCTC? Consider the effective ballots for A. 
By the majority criterion, ranking anybody but A first will make that 
candidate win. So the effective ballots must either be A>B>C or A>C>B. 
If it's A>B>C, then B can't unilaterally break the tie, hence B has no 
reason to strategize, and we pass. If it's A>C>B, then we get e2, e3, 
and e4.

===

I've skipped my reasoning about how SNCTC plus a mono-add-plumpish 
criterion implies NIA, what criterion is required for the implication, 
and what methods pass SNCTC or DH2, because this post is long enough. 
Just ask if you'd like more info.

But I can say that if method M passes DH2, then all of Condorcet,M and 
Resistant,M and Condorcet//M and Condorcet,M pass. Resistant//M pass for 
all M. Resistant,M may fail for some M (e.g. Borda) but there's a tweak 
that makes them pass for all M.

Range with any sufficiently large discrete scale passes SNCTC, as does 
discrete lp-cumulative vote with any p-norm >= 1. (The continuous 
versions fail on a technicality.)

Smith passes DH2, but (surprisingly) Schwartz fails!

Ranked methods with no burial incentive immediately pass DH2 because the 
only possible strategic effective vote (as established) is A>C>B, but 
this buries B, and if there's no burial incentive, that has no effect.

DH2 requires unrestricted domain. In one direction, consider a method 
that's like Plurality, but each faction may also indicate "I'm serious". 
If one faction does so, that faction's candidate wins, but if both do, 
then C wins. This fails SNCTC but its UD version, Plurality, passes DH2. 
In the other direction, if I got it right, Bucklin fails DH2 but passes 
SNCTC because truncation is just as good as burial and doesn't come with 
its risks.

-km