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

Sat Feb 29 15:22:08 PST 2020

 Hi Kristofer,
Isn't 4 voters an unfortunate number for this purpose, due to all the ties you would have?
On permitted ballot types, it seems like you don't plan to allow much. My (most recent) DNA system supports more ballot types (bullet voting, equal ranking, and ranked-but-disapproved), but maybe by limiting these options, an interesting question could be answered by exhaustively analyzing DNA possibilities.
The major limitations of DNA are:1. each candidate has to be top-ranked by one of the three voting blocs. We can speculate that strict majority favorites would have to be elected, but such scenarios have no location in the DNA string.2. DNA strings can't be uniquely determined for methods that can't be resolved knowing only the ranking of faction sizes. A scheme with four equal-sized voters would avoid that problem.
So if we at least allow bullet voting, each faction has 3 ways to vote (X, X>Y>Z, X>Z>Y), there are 27 scenarios, and at least 3^27 methods (assuming no ties). I guess that is a lot.
If we only allow complete strict rankings, there are only 8 scenarios and 6561 methods, and I've sort of already analyzed this. Except it's in terms of criteria, not overall manipulability. I think there are at most a dozen reasonable methods there. There is not much freedom.
the cycles:A>B, B>C, C>A: A usually wins; Bucklin picks B; BPW (beats-plurality-winner cyclebreaker) picks C.
A>C, B>A, C>B: A usually wins; IRV, C//IRV, and BPW pick B; some odd methods (QR) do pick C.
where the plurality loser is the CW:
A>C, B>C, C>A: C is more common; IRV and DAC/DSC pick A.
A>C, B>C, C>B: C wins except under IRV, which picks B.

where the CW is in majority coalition with the plurality winner:A>B, B>A, C>B: B usually wins; DAC/DSC picks A.
MinMax is probably the least manipulable in this setting, but it would be interesting to measure it.
Kevin

    Le mardi 25 février 2020 à 17:24:38 UTC−6, Kristofer Munsterhjelm <km_elmet at t-online.de> a écrit :  

 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.
----
Election-Methods mailing list - see https://electorama.com/em for list info

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20200229/74f8aa59/attachment-0001.html>