Voting Theory has a HOLE
[[epistemic status: I am sure of the facts I present regarding algorithms’ functionality, as well as the shared limitation inherent in Gibbard’s Theorem, et al. Yet, these small certainties serve my ultimate conclusion: “There is an unexplored domain, for which we have not made any definitive conclusions.” I then hypothesize how we might gain some certainty regarding the enlarged class of voting algorithms, though I am likely wrong!]]
TL;DR—Voting theory hit a wall in ’73; Gibbard’s Theorem proved that no voting method can avoid strategic voting (unless it is dictatorial or two-choices only). Yet, Gibbard’s premise rests upon a particular DATA-TYPE—a ranked list. In contrast, we know for a fact from machine-learning research that other data-types can succeed even when a ranked list fails. So, the ‘high-dimensional latent-space vectors’ of artificial neural networks are NOT inherently limited as Gibbard’s rank lists were. Either Gibbard does apply to that data-type, as well (which is a new research paper waiting to happen) OR Gibbard does not apply, in which case we might find a strategy-less voting method. That seems worth looking into!
Gibbard’s Theorem
I am not taking issue with any of Gibbard’s steps; I am pointing to a gap in his premise. He restricted his analysis to all “strategies which can be expressed as a preference n-tuple”… a ranked list. And, the assessment presumed as a result of this by Voting Theorists seems to be “because ranked-lists fail, then ALL data-types must also fail.” That claim is factually incorrect, and a failure of logic.
Disproof: In machine learning, a Variational Auto-Encoder converts an input into a vector in a high-dimensional latent-space. Because those vectors maintain important relational data, then the VAE is able to accurately reconstruct the inputs. Yet, if you converted those latent-space vectors into scalars, using ANY distance-metric, then you have LOST all that information. Now, with only a ranked-list to compute upon, the Variational Auto-Encoder will fail. The same is true for Transformers, the most successful form of deep neural networks (Transformers use a dot-product to compare vector similarity; any reduction to scalars becomes meaningless).
This is proof by existence that “An algorithm CAN function properly when fed latent-space vectors, DESPITE that algorithm failing when given ONLY a ranked-list.” So, the claim of Voting Theorists that “if ranked-lists fail, then everything must fail” is categorically false. There is an entire domain left unexplored, abandoned. We can’t make sure claims upon “the impossibility of strategy-less voting algorithms” when given latent-space vectors. No one has looked there, yet.
Some Hope?
There are reasons to suspect that we might find a strategy-less voting algorithm in that latent-space. Fundamentally, when neural networks optimize, they are ‘guaranteed convex’ - eventually, they roll to the true bottom. So, if one was to ‘minimize regret’ for that neural network, we should expect it to reach the true minimum. (eventually!) However, the more important reason for hope comes from looking at how latent-spaces cluster their voters, and what that would do to a strategic ballot.
In a latent-space, each self-similar group forms a distinct cluster. So, a naïve voting algorithm could seek some ‘mode’ of the clusters, trimming-away the most aberrant ballots first. Wait! Those ‘aberrant’ ballots are the ones who didn’t fit in a cluster—and while a few weirdoes might be among them (myself included), that set of ballots which are outside the clusters will ALSO contain ALL the strategic ballots! Thus, a naïve ‘modal’ algorithm would ignore strategic ballots first, because those ballots are idiosyncratic.
Purpose!
If we can find a strategy-less voting algorithm, that would be a far superior future. I don’t know where to begin to evaluate the gains from better decision-making. Though, considering that governments’ budgets consume a large fraction of the global economy, there are likely trillions of dollars which could be better-allocated. That’s the value-statement, justifying an earnest effort to find such a voting algorithm OR prove that none can exist in this case, as well.
I hope to hear your thoughts, and if anyone would like to sit down to flesh-out a paper, I’m game. :)
I’m having some trouble understanding your post, and I think it could be useful to:
State the exact problem setting you are addressing,
State Gibbard’s theorem, and
Show how exactly machine learning has solutions for that problem.
As far as I understand Gibbard’s theorem, it does not only apply to ranked lists (as opposed to Arrow’s theorem). Rather, it applies for any situation where each participant has to choose from some set of personal actions, and there’s some mechanism that translates every possible combination of actions to a social choice (of one result from a set). In this context either the mechanism limits the choice to only two results; or there’s a dictatorship, or there’s an option for strategic voting.
This isn’t my area so I’m taking a risk here that I might say something stupid, but: The existence of strategic voting is a problem, since it disincentivises truthfulness; But intuitively that doesn’t mean it’s the end of the world—all voting mechanisms we’ve had so far were very obviously open to strategic voting, and we still have functioning governments. Also choices that are limited to two options are often important and interesting, e.g. whether we improve the world or harm it, whether we expand into space or not, or whether the world should act to limit population growth.
I can point you to where I did those things...
1] “State the exact problem setting you are addressing,”
- “There is an unexplored domain, for which we have not made any definitive conclusions.” I then hypothesize how we might gain some certainty regarding the enlarged class of voting algorithms, though I am likely wrong! [at the top, in epistemic status]
2] “State Gibbard’s theorem, and”
- Gibbard’s Theorem proved that no voting method can avoid strategic voting (unless it is dictatorial or two-choices only) [In the TL;DR at the top]
- He restricted his analysis to all “strategies which can be expressed as a preference n-tuple”… a ranked list. [Second sentence of the first paragraph under “Gibbard’s Theorem” header, at the beginning of the body of the post]
3] “Show how exactly machine learning has solutions for that problem.”
- This is proof by existence that “An algorithm CAN function properly when fed latent-space vectors, DESPITE that algorithm failing when given ONLY a ranked-list.” So, the claim of Voting Theorists that “if ranked-lists fail, then everything must fail” is categorically false. [The third paragraph of the “Gibbard’s Theorem” section, first sentence]
4] “Rather, it applies for any situation where each participant has to choose from some set of personal actions, and there’s some mechanism that translates every possible combination of actions to a social choice (of one result from a set).”
No, specifically, Gibbard frames all those choices as a particular data-type: “the domain of the function g consisting of all n-tuples...”, (p.589) and he presumed that such a data-type would be expressive enough to find any voting algorithm that would be non-strategic, if any such an algorithm could exist. By restricting himself to that data-type, he missed the proof by existence I mentioned above.
5] “that doesn’t mean it’s the end of the world”
At no point did I claim this was an existential risk—neither is shrimp welfare. I’m not sure what point you’re trying to make with this comment. At the bottom of my post, the section titled “Purpose!” I outline the value statement: “considering that governments’ budgets consume a large fraction of the global economy, there are likely trillions of dollars which could be better-allocated. That’s the value-statement, justifying an earnest effort to find such a voting algorithm OR prove that none can exist in this case, as well.”
I’m not sure why I was able to answer all your questions with only quotes from my post. Did I clump the thoughts into paragraphs in a way that all of them were missed?
I think Guy Raveh is right, at least about what Gibbard’s theorem states. The second paragraph of Gibbard’s theorem (Gibbard, Allan. “Manipulation of Voting Schemes: A General Result.” Econometrica, vol. 41, no. 4, The Econometric Society, July 1973, pp. 587–601. JSTOR, https://doi.org/10.2307/1914083.) begins: “The result on voting schemes follows from a theorem I shall prove which covers schemes of a more general kind. Let a game form be any scheme which makes an outcome depend on individual actions of some specified sort, which I shall call strategies. A voting scheme, then, is a game form in which a strategy is a profession of preferences, but many game forms are not voting schemes. Call a strategy dominant for someone if, whatever anyone else does, it achieves his goals at least as well as would any alternative strategy.”
I’m trying to understand his proof, since otherwise I’m a bit skeptical that it’s actually valid. One thing that tripped me up is that (1b) does not state transitivity of strict preference, but merely that everything has to be either greater than the minimum of a pair or less than their maximum. However, its contrapositive states transitivity of non-strict preference: ~xPy | ~yPz → ~xPz, i.e. yRx | zRy → zRx. One key thing it implies is that a preference cannot be formed from a chain of solely indifference.
But by also using (1a), we can deduce transitivity from (1b): Assume xPy and yPz. Since xPy, by (1b), xPz | zPy. Meanwhile, by (1a), ~(yPz & zPy), i.e. ~yPz | ~zPy. Since yPz, ~yPz is impossible, so ~zPy. Bringing them back together, since xPz | zPy but ~zPy, xPz. QED.
Thank you for diving into the details! And, to be clear, I am not taking issue with any of Gibbard’s proof itself—if you found an error in his arguments, that’s your own victory, please claim it! Instead, what I point to is Gibbard’s method of DATA-COLLECTION.
Gibbard pre-supposes that the ONLY data to be collected from voters is a SINGULAR election’s List of Preferences. And, I agree with Gibbard in his conclusion, regarding such a data-set: “IF you ONLY collect a single election’s ranked preferences, then YES, there is no way to avoid strategic voting, unless you have only one or two candidates.”
However, that Data-Set Gibbard chose is NOT the only option. In a Bank, they detect Fraudulent Transactions by placing each customer’s ‘lifetime profile’ into a Cluster (cluster analysis). When that customer’s behavior jumps OUTSIDE of their cluster, you raise a red flag of fraud. This is empirically capable of detecting what is mathematically equivalent to ‘strategic voting’.
So, IF each voter’s ‘lifetime profile’ was fed into a Variational Auto-Encoder, to be placed within some Latent Space, within a Cluster of similarly-minded folks, THEN we can see if they are being strategic in any particular election: if their list of preferences jumps outside of their cluster, they are lying about their preferences. Ignore those votes, safely protecting your ballot from manipulation.
Do you see how this does not depend upon Gibbard being right or wrong in his proof? As well as the fact that I do NOT disagree with his conclusion that “strategy-proof voting with more than two candidates is not possible IF you ONLY collect a SINGLE preference-list as your one-time ballot”?