Does Gibbard's theorem allow for a method to be un-manipulable in practice?

rob

So, an analogy first. As we all know, it is mathematically proven that you can't represent Pi as a decimal. 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481 is not actually Pi. It's close, but it isn't Pi.
( https://en.wikipedia.org/wiki/Proof_that_π_is_irrational )

But that is going to be close enough to Pi to be good enough for any real world purpose. Or if it isn't, they can just run their computers for a bit longer, and work out Pi to a few hundred more decimal places, and it will do fine for whatever kind of super-precise rocket science they need to do.

So no engineer makes the excuse that their calculations can't be fully trusted because Pi is irrational so everything is just an approximation. They may admit to other slop in their calculations, but accuracy of Pi is never going to be a limiting factor. That proof is utterly a non-issue, since it is easy enough to use an approximation of Pi that is to the accuracy needed, whether as a decimal value, a fraction made of integers, or some binary representation. The proof is interesting from a certain theoretical point of view, but has no real world impact that I am aware of.

So my question is this: is this sort of thing possible, at least in theory, with voting methods? Could there be a method that can get arbitrarily close to being un-manipulable? Is it theoretically possible to have a method that you can just use computer power to get it "close enough" that https://electowiki.org/wiki/Gibbard-Satterthwaite_theorem simply doesn't have any meaningful real world impact?

@rob

One way to think about frequency of manipulability is just as the size of the subdomain of all possible preferences which admit manipulation. You could either count this as the number of profiles which admit any manipulation, or you could count it as the number of pairs of profiles which display a successful manipulation. The answer here will also depend on if you count a manipulation as only a single voter changing their ballot or any subset.

Let's take the most generous case and say that a manipulation only counts if a single voter can deviate from the sincere profile for personal gain, so we're going to try to make those manipulability numbers look as small as possible (I believe this is also the definition used by Gibbard-Satterthwaite?)

If you have M candidates and N voters, assuming each ballot is a strict linear order there are M!^N possible profiles. Now take some random profile and call it "sincere." The sincere profile has (M! - 1)*N neighbors where a single voter has changed their ranking. If only one of these comes at a benefit to the voter then the probability of a random voter randomly changing their ballot giving a better outcome (given this particular fixed sincere profile) is 1 / ((M! -1)*N).

Now if we even further assume that any other choice of sincere profile actually has zero manipulations, then our probability from the outset if we randomly sample a sincere profile, then randomly sample a manipulated neighbor and see if it improves the outcome, is only 1/ ( (M! -1)*N * M!^N). This grows asymptotically something like M^(- M*N), which as you might imagine is um, pretty small.

So I guess tl;dr is it kind of depends on your definition, but it is true that you can get pretty damn close to zero strategic manipulability.

rob

@andy-dienes said in Does Gibbard's theorem allow for a method to be un-manipulable in practice?:

So I guess tl;dr is it kind of depends on your definition,

I guess I'd define strategic-manipulability as a situation where some subset of voters who have similar preferences are able to change their ballots from their sincere preferences to get a better outcome for all of them, if they knew enough about how other voters were voting. I don't like to say "single voter" simply because of the most you can do by changing one ballot is to cause it to go from a non-tie situation to a tie-situation or vice versa.

We know that in Burlington (I know, I know.... ) that if even 25% of voters who preferred one candidate had rated that candidate lower, he would have won. Of course, this was the fault of IRV not choosing the Condorcet winner. But supposedly, a similar thing could happen with (most?) Condorcet methods, it's just less likely.

What I am wondering is, whether it should be theoretically possible to to reduce the chance of that sort of situation to, like, one in a trillion elections or lower. In which case I'd argue "fretting over Gibbard is stupid."

Does your "pretty damn close to zero strategic manipulability" still apply if we are talking about a group of voters?

cfrank

@rob Gibbard's theorem does not prevent the strategies that would be effective in manipulating a voting system from being computationally infeasible to devise or execute, such as being NP-complete or NP-hard or beyond. I don't think it would be reasonable to assume that there is always a polynomial-time method to manipulate a voting system any more than it would be reasonable to assume that P=NP.

The literature on the computational complexity of manipulation, control and bribery is (no pun intended) complicated. This is the subject of section 4.3: Complexity of Voting Problems of chapter 4: Preference Aggregation by Voting of "Economics and Computation." I'm not sure whether practically un-manipulable systems themselves become complicated, but I don't think that's necessary as there are many problems that are simple to state but that are computationally intractable to solve.

For example, two problems are defined as CONSTRUCTIVE-COALITIONAL-WEIGHTED-MANIPULATION (CCWM) and DESTRUCTIVE-COALITIONAL-WEIGHTED-MANIPULATION (DCWM). I haven't looked into what that means exactly yet, but CCWM has been proved to be NP-complete for Bucklin, Borda and STV all with at least three candidates, as well as for Simpson and Nanson voting with at least four candidates.

DCWM is also known to be NP-complete for STV, and it is an open question whether DCWM is NP-complete for Nanson voting with more than 3 candidates. There are various other more subtle results mentioned in terms of alternative complexity classes as well. Existence of systems with winner determination in P and CCWM being PSPACE-complete is known. It seems that DCWM is a more difficult problem to circumvent with NP-hardness.

There is also an interesting table about control complexity results (control = candidate nomination and deletion, voter addition and deletion, partitioning, etc.). In fact Condorcet methods are shown to be vulnerable to various forms of control, in particular "Destructive Control by Partition of Voters" (DCPV), while for example Bucklin voting is shown to be highly resistant to the analyzed control problems. Of course, existence of polynomial-time algorithms doesn't imply that the algorithms are at all feasible anyway.

The next section on bribery is short, all of the bribery problems considered are shown to be NP-complete for almost all considered voting systems. I won't pretend to understand the full implications of any of this for practical purposes, I'm just reporting the results as stated in this text.

rob

@cfrank There is a difference, though, between being able to manipulate it (which seems to require mass mind reading as much as computation), and simply realizing after the fact that it could have been manipulated if you had known enough about how others were going to vote. Because as long as even the latter can happen (as happened in Burlington in 2009 under IRV and we'll never hear the end of it), I think there is an issue we should aspire to solve.

People always say that Condorcet methods are strategically manipulable, but usually fail to say by how much. I know they are a lot harder to manipulate than IRV, but it is still supposedly possible if a group of voters (with similar preferences) can cause a cycle to occur. A certain member of this forum just keeps bringing up Gibbard and the "impossibility" of solving this, so I want to directly address that.

As far as I know, I am the only one to have proposed a method where the "quality" can be "dialed up" by simply changing an input parameter. So, the method rIRV(10) is recursive IRV, that goes 10 levels deep (*). Computationally expensive, especially with lots of candidates, sure. But if adding an extra level of recursion can make it harder to manipulate, and there is no theoretical limit to how many levels of recursion you can have, I would argue that that is significant in terms of demonstrating that Gibbard is a red herring.

* I mentioned this in other threads, a method where it uses the same IRV process of elimination, in determining who to eliminate. So it is a nested loop. I've since demonstrated that it works quite effectively at least in terms of making IRV be Condorcet compliant, even at rIRV(2). (that is, one additional level of nesting than plain-old-IRV) But the interesting thing is that as you dial up the recursion depth, it seems to continue to make it less and less sensitive to irrelevant alternatives, with no real limit.

cfrank

@rob said in Does Gibbard's theorem allow for a method to be un-manipulable in practice?:

which seems to require mass mind reading as much as computation

That or mass media control + many sheep-le! I joke here (but also don't).

In any case there are also some sections on how or if electoral chairs could try to handle the intractable complexity of their control tactics if they wanted to, I still need to read through this textbook somehow and also read about your recursive IRV system.

Generally I think I agree with you, and the known results support the idea that voting systems can in principle be devised where effective manipulation by voters using almost any reasonable tactic is virtually impossible. Gibbard’s theorem is mostly just a wild-goose-chase ender. I think corruption, control and bribery are also important to consider when devising a voting system, though I'm not sure to what degree in comparison to manipulation.

rob

@cfrank said in Does Gibbard's theorem allow for a method to be un-manipulable in practice?:

I think corruption, control and bribery are also important to consider

They are, although to me they are a bit out of scope. Comparatively, fixing the voting method itself (rather than all the things surrounding it) just seems like a lower hanging fruit. Like, this is just a dumb design (and therefore directly fixable), rather than a human nature thing.

cfrank

@rob definitely man. It’s pretty ridiculous, I hope it can get fixed soon. It seems to be growing in public awareness, which is definitely a good thing.