[EM] Manipulation Resistant Voting

[Kristofer Munsterhjelm]

On 7/19/21 1:01 AM, Susan Simmons wrote:
>  >Now suppose there's a typical Condorcet cycle A>B>C>A and the agenda
> ordering is A>B>C; so the method proceeds by matching B and C, and then
> matching the winner with A, and then the outcome of this is the final
> winner.
> 
> Good point ... just concatenating binary choices together is not 
> enough.  It is important that the outcome of each binary decision be 
> final, not just the last decision in the sequence.
> 
> Suppose, for example, that the method, at every stage, either (1) 
> accepts the next remaining agenda item X as the final winner or (2) 
> eliminates X and applies the method recursively to the remainder of the 
> list?
> 
> Then every C supporter would vote sincerely to stick with C, and the A 
> supporters would vote sincerely to eliminate C. The B>C supporters would 
> sincerely vote to keep C, while the B>A supporters would sincerely vote 
> to eliminate C.
> 
> So the winner would be A or C depending on whether or not the B>A 
> faction was larger than the B>C faction.

I think Benham can be defined that way. At every stage, either X is 
accepted as the final (because he beats every candidate ranked higher 
than him), or X is eliminated and the method is recursively applied to 
the rest of the list.

The list, then, consists of the winners in IRV order, last man standing 
ranked first.

But Benham is just IRV if all the candidates are in a top cycle. So if 
we have IRV order A>B>C and an ABCA cycle, wouldn't the point stand above?

Before strategy: the method checks whether C is the CW. It is not, so 
then C is eliminated. Then it checks if B is the CW among the remaining 
candidates. It isn't, so B is eliminated, then A wins.

If the method is manual, there must be something the voters can report 
on in the agenda method itself. If pairwise preferences are hoisted from 
the IRV ballots, then the agenda method is entirely automatic, so there 
would be nothing to report.

So since the method has to ask the voters *something* in the agenda 
method itself, that something must be whether the last placed candidate 
is a CW. The manual Benham method would take form of first calculating 
the IRV order, then asking the voter "does the last placed candidate 
beat everybody else pairwise?".

Now suppose you're a B>C>A voter. In the first round, if you report your 
true preference ("B>C>A"), this would indicate, along with everybody 
else's true preferences, that C is not the CW. So C is eliminated, after 
which A wins. So you should instead falsify your preference to C>B>A so 
that C's chance of becoming a CW is maximized.

That's what you say above ("the B>C voters would sincerely vote to keep 
C"), but it doesn't strike me as very sincere. See more below.

> So given the agenda, and the special finality rule (once an option is 
> chosen the winner must be a member of that option) all of the rational 
> choices will be sincere in the sense that they are the choices whose 
> rational outcomes are preferred.
> .....
> 
>  >In reference to an earlier post of mine, suppose we define honesty as
> what a Random Ballot type method would return. In your method, this
> would be a trace down the tree that ends at the candidate who the voter
> prefers most of the candidates at the bottom level of the tree.
> 
> But a voter is not at liberty to choose an entire trace. You probably 
> mean that as long as Favorite is a descendant of the current node, if 
> you do not choose the branch that leads to Favorite, then your vote is 
> insincere.
> 
> If that's your definition of "sincere" in this context, then you are 
> right ... sincere strategy is not rational.
> 
> But it seems to me that when presented with only two choices, branchA or 
> branchB, leading almost surely to final wins for X and Y, respectively, 
> then voting for branchA should not be impunged as "insincere strategy,"  
> if you truly prefer X over Y.
> 
> It's a matter of definition. So perhaps we could distinguish between 
> "naive sincerity" and "rational sincerity."

This is a bit too reminiscent of the cardinal supporters' arguments that 
Burr dilemmas can't happen because you'd be using polls to anticipate 
the support of the relative candidates, so that adjusting your Approval 
vote to either Approve of Best and Good or only Best is not a tactical 
burden on the voter.

That said, I seem to have misunderstood your method. So I'll describe it 
(and my insincerity argument) and then let's see if I understood it 
properly.

Your method consists of two stages. In the first stage, what's 
essentially a hierarchical clustering is constructed as a binary tree 
with all the candidates at the leaves. Then the tree is published and 
the voters either participate in log(n) runoffs (if it's a manual 
method) or submit the necessary information to automatically do those 
runoffs (if it's an automatic one).

To revise my example, the tree is something like:

            ----- A
       -----+
       |    ----- D
   ----+
       |    ----- B
       -----+
            ----- C

Now suppose that a voter's mental preference ordering of the candidates 
is A>B>C>D. In a Random Ballot/Dictator situation, the voter would first 
choose the top branch, then the top branch again to arrive at A.

Now suppose there's an election, and the voter has to choose whether to 
support the top branch or the bottom branch from the root. Suppose 
furthermore that the voter knows that if the top branch is chosen, the 
outcome is very likely to be D. Now that voter has an incentive to lie 
about his decision relative to a random dictator situation, by throwing 
his support in favor of the bottom branch so that the lesser evil wins.

That, I would say, is strategy. It may not *seem* like strategy because 
the ballot format fails universal domain. Like Approval, the voter is 
limited in what he can express by the state of the rest of the 
electorate; and there exists a choice that is consistent with his 
preferences, conditioned upon what the rest of the electorate will let 
him do. The voter is being honest under the constraint (i.e. he's not 
reversing any preferences, because his choice is consistent with trying 
to optimize the expected outcome). However, he still has to adapt his 
choice to what the other voters are doing.

The comparison to Approval is that in a Burr dilemma, a voter isn't 
preference-reversing (e.g. Approving both Best and Bad when his 
preference order is Best > Good > Bad). But the failure of universal 
domain exhibited by the Approval ballot means that he's still 
constrained by the rest of the voters: the proper way to vote is Best 
only if Bad is far behind, or Best and Good if Bad is close.

Now, there is a difference to Approval. A voter who truly values honesty 
above all else can behave as if under Random Ballot in your method; 
that's impossible in Approval. But your method and Approval are only 
strategy-proof under a definition of honesty where there are multiple 
sincere votes, and the voter adapts to the electorate by choosing one of 
the many sincere votes.

In the stricter Gibbardian sense that "it's strategy if you have to 
adapt your answer to what other people are doing", then both Approval 
and your method are susceptible to strategy. This stricter sense is what 
stops feedback cycles, regret after anticipating wrong, etc.

As I don't like the sort of manual DSV that's implied by Approval, I'm 
inclined to use the stricter definition, and so I probably wouldn't like 
the method above, either. (Well, it *might* be a good method if paired 
with DSV and accepting a ranked ballot; I don't know whether it would.)



Consider this analogy: Say we have a two-step method where, in the first 
round, the Benham and Ranked Pairs winners are chosen, and if they 
differ, there's a manual runoff for the second round.

Now suppose for the sake of the analogy that you *know* everybody else's 
honest pairwise preferences so you can perfectly predict the outcome of 
the second round. In particular, in a runoff between A and D, D will 
win; and in a runoff between B and C, C will win.

Furthermore, your honest preference is A>B>C>D, and you know that if you 
vote A>B>C>D, then A and D will be the Benham and RP winners 
respectively, whereas if you vote B>C>A>D, B and C will be the winners.

Isn't then voting B>C>A>D in the first round strategy? If so, why is 
taking the bottom branch any different?

It seems to me that the only difference is that B>C>A>D feels wrong 
because it's indisputably tactical voting in either Benham or RP alone, 
so we know it's dishonest. But it's easier to conceal the strategic 
behavior when your hand is forced by the constraints placed upon you by 
the method, so in the context of a two-round system, voting B>C>A>D is 
also "rational sincerity" in the sense that choosing the bottom branch is.

> So one can say naive sincerity is violated by this choose-a-branch 
> method, but (it seems to me) realistic, rational, strategic sincerity 
> that accepts the premise of the method is not violated.
> 
> The "premise" is that when you choose a branch, you are showing a 
> preference for the likely winner of that branch over the likely winner 
> of the other branch ... NOT implying support for any other preference.  
> So it cannot be dishonest or "falsification" unless you actually prefer 
> the likely winner of the other branch over the one you chose.
> 
> 
> I think this notion of sincerity gives us some traction ... the other 
> one is too stringent to lead to a manipulation proof Condorcet method.

Right. I'm perfectly content to say that no Condorcet method (for that 
matter, no deterministic *election method!*) is strategy-proof, and 
point at Gibbard. In the strict sense "you don't have to anticipate 
other people's responses", it's perfectly true.

But methods that fail universal domain and so collapse some subset of 
strategic (in the Gibbard sense) voting into sincere ballots leave too 
much of a burden on the minds of the voter. If the voters' model of 
reality is off too much, then they may end up regretting making the 
choices they did.

And I would like mental burden to be a game you choose: if you're 
honest, just go ahead and submit your true preference. Otherwise, if you 
want to play (devise a strategy) then you accept taking the heat (chance 
of backfire, regret, etc.) but that's a deliberate choice you're making.

Now, you *could* be naively sincere in your method, but I have the 
intuition that it would perform rather badly in that case, because it 
doesn't have contingency logic.