[EM] Trying to get at the Condorcification proof

[Kristofer Munsterhjelm]

James Green-Armytage (and independently Durand) showed that if M is a 
method that has a property that a coordinated majority can always force 
an outcome (the InfMC property), and neither equal-rank nor truncation 
is allowed, then there's no election E where the outcome can be 
strategically altered in Condorcet//M but not in M.

Furthermore, Durand stated that the same result holds with equal rank 
and/or truncation as long as "Condorcet" is replaced with "AbsCondorcet" 
- absolute Condorcet, where the absolute Condorcet winner is a candidate 
who some absolute majority (50% + 1 or more) of the voters strictly 
prefer to any other candidate.

I've tried to understand the proof myself as JGA and Durand's notes are 
kind of terse. Here's my attempt:

I'll say "Election E is manipulable under M" if, when the winner of E 
according to M is W, then there exists some group who all prefer some 
other candidate X to W, and this group can alter their ballots so that X 
wins instead of W.

1. Consider an initial honest election E. We want to show that if E is 
manipulable under AbsCondorcet//M, then it's also manipulable under M.

2. If E has an absolute Condorcet winner C and M doesn't elect him, then 
by definition, a majority prefers C to M. Due to InfMC, this majority 
can force C to win. So E is manipulable under M; even if E is 
manipulable under AbsCondorcet//M, the latter is no worse than M.

3. Now suppose that M is the winner of election E according to M, and an 
absolute majority prefers some other candidate Y to X. Then E is 
manipulable under M. By the same reasoning, AbsCondorcet//M can do no 
worse than M.

4. Thus, if E is unmanipulable under M, there can be no majority 
pairwise preference X>W where W is the winner according to M. So M and 
AbsCondorcet//M agree that W is the winner (no matter if W is an 
absolute Condorcet winner or not). So the only way to make E manipulable 
under AbsCondorcet//M but not under M is to somehow make manipulators 
create an absolute CW, so that the post-manipulation election for 
AbsCondorcet//M changes but the election for M doesn't.

5. But that's impossible. Suppose we want candidate X to become the new 
absolute CW. To do so, a majority must prefer X to W. But by point 3, no 
such majority exists. The manipulators can't change this fact because E 
was initially honest, so they already maximally expressed their 
preference for X over W.

6. Thus the only way for an election to be manipulable under 
AbsCondorcet//M but not under M is impossible, which was what was wanted.

Does that seem right?

Essentially, the trick seems to be that absolute Condorcet is a sort of 
DSV for compromising within the constraints of InfMC. An absolute 
Condorcet winner C is someone who, if the winner was someone else, InfMC 
enablest a group of people who all prefer C to the current winner, to 
force the election of C by compromising for C. By electing C outright, 
the method removes the need to compromise for C in such a case.

"If a majority prefers A to B, then B is not elected", as Robert would 
say.  ... in this case because otherwise, that majority could force the 
election of A by strategizing!

Some more thoughts:

I *think* the proof works for "Absolute Smith" too as long as we use 
ASmith,M (not //): if M elects someone not in the Absolute Smith set, 
then strategists can make any candidate in that set win (not the same 
group for each, of course).
Manipulators trying to change the winner according to ASmith,M have two 
options: to keep the Smith set the same or expand it. In the former 
case, any strategy they use will also work on M since ASmith,M uses M's 
order to break the ASmith tie. In the latter case, no absolute majority 
prefers some X outside the set to any inside (same reasoning as for 
Condorcet). But to get X inside the ASmith set, we must make an absolute 
majority prefer X to someone in it, which is impossible (again, same 
reasoning).

But it doesn't really help, because ASmith,M is manipulable whenever the 
absolute Smith set has more than one candidate in it, because if the 
majority preferring A to B (in an A>B>C.. cycle) unite, then they can 
force the election of A using InfMC. Still, at least we don't *lose* 
anything.

Making a similar proof for relative majorities would require some 
"natural" property similar to InfMC but relating to relative majorities 
(e.g. something like "if everybody else is indifferent between A and B, 
then a majority of the remaining voters can force whether A or B wins").

There may be clever things one can do with the DSV idea, e.g. consider 
something like: Let A ~> B in election E if either A has a higher Borda 
score than B, or people who prefer A to B can bury B to make A's Borda 
score higher than B's. Then let the Bury Top set be the maximal elements 
set of this ~> relation. Is "Bury Top,Borda" less susceptible to Burial 
than Borda? Maybe?

Or how about: Let a candidate X be "tenable" in election E if it's 
possible to lower X in E to make X be eliminated no earlier under IRV; 
let a candidate Y be "untenable" if it's possible to raise Y in E to 
make Y be eliminated earlier under IRV. Let the net tenable set be every 
candidate in the tenable set but not in the untenable set, or all 
candidates if no such candidate exists. Elect the net tenable set 
candidate ranking highest in IRV's social ordering (i.e. eliminated 
last). Is this method monotone? Does it retain IRV's burial resistance?

-km