[EM] A possible low-strategy PR concept when picking n-1 winners from n candidates

[Kristofer Munsterhjelm]

When picking a winner from two candidates, majority rule is 
strategyproof. I was playing with ways to generalize this to multiwinner 
to find at least *some* domain where a method can be both Droop 
proportional and strategy-proof, and found this for elections with n 
candidates and (n-1) seats:

Consider a set of n-1 winners {A_1, ..., A_(n-1)}, and call the loser B.
If there exists strictly more than a Droop quota of voters who prefers 
A_k to B for any k, (but not necessarily the same voters for each A_k) 
then say that this set is a stable set. (That is, some subset of the 
voters prefers A_1 to B, another subset of the voters prefers A_2 to B 
and so on, and all of these subsets contain more than a Droop quota's 
woth of voters.)

If there is only a single stable set, and the method elects that set, 
then it passes the DPC for that election and it's also strategyproof.

Suppose that some group of voters wants to kick out A_k and replace him 
with B. These voters must necessarily (honestly) rank B over A_k. But 
we've established that there exists some Droop quota of voters who rank 
A_k over B. The B>A_k voters can do nothing to stop the existence of 
such a contingent of voters, because they are already maximally 
contributing to B over A_k, so they can't break the stable set's 
condition of a Droop quota or more ranking A_k over B, and thus they 
can't undo this stable set.

So the only thing they can try to do is to establish another stable set 
and hope that the method switches over. Their objective is to kick out 
A_k, so this other candidate set must be {A_1, ..., A_(k-1), A_(k+1), 
..., A_(n-1), B}. But for such a set to exist, there must exist at least 
a Droop quota's worth of voters who rank B over A_k. Since the B>A_k 
voters are already ranking B over A_k, they can't contribute to the 
creation of such a subset either. Hence if they create another stable 
set by altering their ballots, it is not the one they want.

Since this argument holds for all A_k, there should be nothing anybody 
who has an incentive to get B elected can do to get B elected.

(I'd imagine there's also a Condorcet extension for this concept for 
electing k out of n candidates, but I can't quite see it yet. From a DSV 
perspective, such a generalization would be "automatic vote management" 
if single-winner Condorcet is "automatic compromising".

The argument above also resembles the reasoning I used for the resistant 
set, so maybe there's a generalization that connects it with that.)

The problem is that there may be multiple stable sets. Impartial culture 
elections are almost certain to have more than one. Here's an example:

  50: A>B>C
306: A>C>B
  65: B>A>C
426: B>C>A
260: C>A>B
  93: C>B>A
1200 voters in total, and the quota for two seats is 400.

{A,B} is a stable set because we can assign
	306 A>C>B voters,
	 50 A>B>C voters, and
	 65 B>A>C voters
to the group that prefers A to C. This is more than a Droop quota in 
total. Similarly, we can assign 426 B>C>A voters to the group that 
prefers B to C.

But {B, C} is also a stable set:
	 65 B>A>C
	378 B>C>A
	= 443 voters preferring B to A, and
	260 C>A>B
	 93 C>B>A
	 48 B>C>A
	= 401 voters preferring C to A.

So what we might wonder is: does there exist a way for a voting method 
to pick a particular stable set when more than one exists, and to stick 
to that stable set no matter what the voters who prefer the other stable 
set may do?

Unless my simulations are wrong, Schulze STV is almost always 
strategyproof for impartial culture and (n-1) out of n, so that suggests 
that it's possible at least some of the time. But Schulze STV has a 
nonzero coalitional manipulability rate for (n-1) out of n with other 
models, say a spatial model. Is that because the method it uses to pick 
a particular stable set is strategyproof almost always for IC but not in 
a spatial model? What's special about it in that case? Is it something 
like "for three candidates and two to be elected, it's strategyproof 
whenever there are only two stable sets" and then spatial model, but not 
IC, sometimes has three?

For three candidates, at least, there should always be at least one 
stable set, unless there's an exact tie. I don't know if that holds for 
every (n-1) of n election.

In any case, it might be something to investigate further at some point.

-km