[EM] Determining the shape of the least manipulable ranked method

[Kristofer Munsterhjelm]

A thought that occurred to me the other day:

Say that a method is manipulable whenever it elects A and a group that
prefers B to A can modify their ballots in such a way that B is elected
after the modification.

Then we could in principle determine the least manipulable method by
minimizing the number of elections where this is possible.

To put it another way, we could get something like Venzke's DNA but on a
much larger scale. Consider every possible election that involves say,
four voters and three candidates, with complete rankings and no equal
rank. There are 3! = 6 different ways to rank and 4 voters, so 126
different elections.

In the absence of ties, that would be 3^126 different methods (either A
wins, B wins, or C wins for each). With ties, it would be 2^(3*126)
instead (true/false: three per election as to who wins).

But I think it's possible to minimize manipulability by using an integer
programming formulation. Whether this is actually tractable is another
matter, but it can't be worse than brute-forcing.

For each election k [1...126], let election_n(k, B>A) be the number of
elections where at least one of the B>A voters changed one of their
ballots. Then let election(k, B>A, p) be one such election. Clearly, the
number of different values of p can at most be 126. Then election k is
manipulable if
	the assigned winner for k is A and:
		there exists some election(k, B>A, p) where B wins
	or	there exists some election(k, C>A, p) where C wins

(same goes for the case where B wins or C wins). Or in linear
implication terms, suppose election(x)(A wins) is 0 if A doesn't win,
and 1 if A does win, then:

      manipulable(k, if A wins) >= election(k, B>A, 0)(B wins)
                                >= election(k, B>A, 1)(B wins)
                                              ....
                                >= election(k, C>A, p)(C wins)

      manipulable(k, and A wins) >= manipulable(k, A wins) -
(election(k)(B wins) + election(k)(C wins))
      manipulable(k) = manipulable(k and A wins) + manipulable(k and B
wins) + manipulable(k and C wins),

with all free variables being binary. The second statement forces
manipulable(k, and A wins) to be true if neither B nor C actually wins,
and manipulable(k, if A wins) is true. The third statement then sums up
manipulability over every candidate.

Then the LP/IP formulation is simply:
	minimize sum over all k: manipulable(k)
for impartial culture, and
	minimize sum over all k: p(k) * manipulable(k)
for other election models, with p(k) being the probability of getting
that election in that model.

We'd probably also need some basic criteria like neutrality (of all
the possible elections, A must win or be tied for first in a third of
them, and same for B and C; and that in an election where every
permutation of the candidates gives the same election, you must have a
three-way tie).

The objective function gives a bound on how unmanipulable *any* ranked
system can be in this particular setting (e.g. 4 voters, 3 candidates,
all voting weights integer), and would give an indication as to whether
e.g. IRV is close to that bound. As a side effect, the election(k)(X
wins) free variables will provide a partial election method that meets
that bound.

I may have been a bit sloppy in defining manipulable(k, if A wins). It
should strictly speaking take ties into account: being able to go from
one election where A and B are tied, to another where A and B are tied,
does not constitute successful manipulation, even if (A wins) is true
for the first election and (B wins) is true for the second. But
accommodating ties may lead to the pathological "smartass" election
method that always produces a three-way tie no matter what election it is.

Perhaps there's a way to insert the reinforcement/resolvability
constraint? I don't remember its actual name at the moment, but the one
that says, if there's a tie, then there must exist at least one election
you can get to by altering the ballots so that there's no longer a tie.
Perhaps that's what forces integer programming instead of just linear.

Some constraints are easy to impose as they simply say "in election X, Y
must win/Z mustn't win". For these types of constraint just let
election(k)(A wins) = 1, election(k)(B wins) = 0, election(k)(C wins) =
0 if A's the required winner (e.g. CW) in the kth election. A program
could easily check all 126 and import the necessary forced outcomes into
the linear program.

Dynamic criteria like monotonicity are harder. Suppose we can go from
election b (for before) to a (for after) by raising A on a ballot. Then
monotonicity says that if A wins in b, then A must win in a too. If we
know neither a nor b will have any ties, then it's easy to impose this
constraint:
     election(a)(A wins) >= election(b)(A wins)
will do. This forces "A wins" to be true on a if "A wins" is true on b.
However, ties complicate matters more. If A wins with certainty in b,
and A ties with B in a, then that's still a violation of monotonicity
even if A wins in both. I can see three possible options:
    1. use integer programming and "big M" constraints to force that the
number of winning candidates cannot increase from b to a - but only if A
is already the winner in a.
    2. let the winner indicators be integers instead of binary, so that
election(q)(A wins) = 6 if A wins with certainty, 3 if there's one other
candidate A ties with, and 2 if A ties with both (0 if A doesn't win),
with an additional constraint that the sum over all candidates for a
particular election should be 6. Then the greater-than constraint above
still works, because it implies that A must tie with no more candidates
in a than he does in b. The problem is that the values {5, 4, 1} are
undefined and have to be forced to be unassigned somehow.
    3. drop integer programming and let the free variables be
probabilities (that a given candidate is elected, e.g. 1/3 in a perfect
three-way tie). The problem is that this allows for methods that leave
too much to chance, like random ballot.


As an example of the use of such a formalization: I suspect that a
method that elects only from the uncovered set must by necessity be
considerably more manipulable than a method that elects only from the
Smith set. I have no proof of this, only a hunch from that Landau,IRV
does worse than Smith,IRV.

But solving the integer program for a low number of voters and for four
candidates (the minimal number of candidates where someone can be in the
Smith set but still be covered) could show whether that is actually the
case. Without knowing what the least manipulable four-candidate
uncovered and Smith-consistent methods are, the program could be used to
determine how manipulable these methods are in the (limited) domain of
only a few voters.

>From Monte-Carlo experiments, it seems that not many voters are needed
to distinguish Landau,IRV's performance from Smith,IRV's. I think I
found four or five sufficient. OTOH, the integer program might still be
unsolvable. I wouldn't know until I try it.