Monetization Impossibility Theorem for Voting

By Warren D. Smith, 19 June 2013, PRELIMINARY

Here is one formulation. There are probably other interesting formulations.

MONETIZATION IMPOSSIBILITY THEOREM I: ("I" since there undoubtably are others...)

ASSUMPTIONS:

1. Each voter has within her mind, some (unrestricted real) money-value for the election of each candidate.
2. The voters each cast "votes," i.e. submit information-packets to election authority.
3. Each voter acts (when voting) in ignorance of the candidate-values within the minds of all other voters. However, each voter has a realistic probability model which tells her, for each possible vote she could cast, the probability each candidate would then win.
       [The meaning of "realistic"? Well, in the proof we shall set up a situation where these probabilities will be exactly known and this can be used as the model.]
4. The "winner" (who is one of the candidates) is a publicly-known function of those votes. Winner is announced by election authority after all votes have been cast. Optionally the system then could also announce the 2nd, 3rd, etc finishers.
5. Each voter must PAY some real amount of money when voting, and this amount is a publicly known function of that voter's ballot, and of the name of the winner, and (if announced) also the names of the 2nd, 3rd, etc finishers, (and perhaps also of random bits) only.
6. There is unique max-expected-profit ballot that each voter could cast.
       (I.e. the monetization scheme induces unique voter behaviors.)
7. If each voter casts that vote, then an "optimal" candidate (with max summed-value) must win. (And the 2nd, 3rd etc finishers, if announced, must be the ones with 2nd, 3rd etc greater summed values.)
       (I.e. the monetization's induced voter behaviors cause "optimality.")
8. In the limit of a large number V of voters, each voter's expected profit |difference| between casting her optimal ballot, and casting a "randomly altered" version of it (will be defined later), will not become negligible -- instead it will be bounded below by a positive constant, at least for voters whose honest money values for the two candidates always differ by at least 1 dollar.
       The point of this assumption is that without it, the voters will be influenced by other effects (call them collectively "noise") besides the profit motive alone, which will swamp the profit motive and render it, relatively speaking, a negligibly tiny motivational force.

MAIN CLAIM: No monetized voting system obeying assumptions 1-8 can exist.

PROOF SKETCH:

LEMMA A: each voter's max-expected-profit vote must include (in some form) her honest value for each candidate. Because: if even a single voter omitted or altered that info, then the other voters by assumption 3 could not supply or correct it, and by assumption 4 the voting system therefore could not know or use it to influence its choice of winner, which could then be the wrong choice (not maximizing summed value) thus violating assumption 7 (because even a single changed score always can be enough to alter the identity of the optimal candidate).

LEMMA B: given lemma A, the voting system in assumption 4 must simply elect the max-summed-score winner (ignoring all other "auxiliary" information, if any, present in the ballots besides the candidate-scores), Because: otherwise there would be a violation of assumption 7.

DEFINITION: "Randomly altered ballot" shall mean the voter's C scores (for the C candidates) will be permuted acccording to a random permutation (all C! permutations equally likely).

For the rest of the proof I shall assume C=2 candidates. (Since I am proving impossibility, all I need is to set up even one counterexample situation. So I choose a situation that is easy to analyse.) Then we need only use the score-differences between the two candidates to assess who wins, and we may wlog call the candidates "yes" and "no." Further, I shall assume each voter's honest money-value-difference (for yes minus no) is either {-√3, -1, +1, +√3} dollars, selected for each voter with independent probabilities (1/4, 1/4, 1/4, 1/4) each.

LEMMA C: given lemmas A & B, the pricing must wlog depend only on the scores and not on the auxilary information (which is unused for winner-selection purposes, hence wlog is unused for price purposes too).

In our scenario, by central limit theorem in the limit V→∞ we get a probability distribution which is asymptotically normal with variance=2V and mean=0 for the score-sum. This causes the chance your ballot's honest score U will swing the election to be asymptotic to (U/2)(πV)^-1/2. Now there are 8 numerically possible payments (depending on your 4 possible honest scores and 2 possible winners: 8=4·2).

What are these 8 fixed (and published, by assumption 5) numbers? (Incidentally, re assumption 5 allowing dependence on random bits, that will not matter because we shall only need to consider the expected payments, which due to summation over all configurationsof the random bits, are deterministic.) Whatever they are, they must satisfy certain linear inequalities which say that your max-expected-profit vote, is unique and always is your honest score (assumption 6). Also, by assumption 8 they must satisfy the inequality that two among these 8 numbers must differ by at least a positive constant, even when V→∞. The collection of these linear inequalities is called a "linear program." It now is mechanical ("solving the linear program") to verify that our particular linear program has no solution ("infeasible") once V is great enough.

This also can be understood directly: if the price-penalty were too small for exaggerating ±1 to ±√3, then voters would do it; but if it were too large then honest-√3 voters would pretend their value were 1. The allowed penalties thus fall within a range which width is proportional to V^-1/2. But that contradicts the demand that two such penalties must differ by at least a positive constant even when V is made arbitrarily large. You could try to evade that by making the +1 and +√3 penalties be close, and the the -1 and -√3 penalties be close, but these two pairs be far apart (further than some positive constant) but then voters would be incentivized to change the sign of their score.

Q.E.D.

Remarks on the proof:

1. The number √3 could be replaced by any fixed irrational number, and the proof (after easy modifications) would still work.
2. If the 8 prices were not all equal (i.e. some two differ by a positive constant) then the election will in the limit V→∞ become massively distorted – all voters would vote just one |score| if they vote for max believed expected profit in the probability model of our scenario, causing (if, e.g, that score were ±1) the opinions of all the ±√3 voters to be reduced.
3. On the other hand, if the prices all were equal, then the monetization has no effect. In that case all ±1 voters are motivated to exaggerate to ±√3, also causing massive distortion.

The net effect of these remarks seems to indicate (but as yet is not a full proof)

CONJECTURED EXTENSION OF IMPOSSIBILITY THEOREM(?): Indeed, it is not even possible to weaken assumptions 7 & 8 to only demand "ε-approximate" optimality (while perhaps also weakening assumption 6). Specifically, assuming the "noise" is adversarially chosen, then it is not possible for any monetized voting scheme to force the expected regret ("regret" meaning the difference between the max possible summed honest money values for any winner, minus that sum for the actual winner) to be less than some positive constant times the sum of all honest money |value|s for both candidates (in the probabilistic election scenario constructed in the proof).

Return to main page