## Puzzle #??: Good voting systems incentivizing voter to reveal honest utilities

Let X be any (pre-specified) single-winner voting system which inputs votes and outputs a winner, a second-place finisher, and a third-place finisher; and let ε>0 be any arbitrarily-small positive real number. Construct a single-winner voting system (which includes randomness) with the following properties.

Includes range-style sub-ballot:
Each ballot includes a continuum range-voting type ballot, i.e. on which the voter scores each candidate between 0 (bad) and 1 (good); plus additional information (you will need to describe what), to be provided by the voter.
Elects X's winner, second choice, or third choice:
The winner with your voting method, will always be either the method-X winner, or its second-place finisher, or its third place finisher.
Only ε worse than voting method X:
Your voting method's Bayesian Regret (BR) will be within ε of the BR of voting method X since the election winner with your method, will be the same as X's election winner with probability≥1-ε. Further, the only way your election winner can differ from X's winner is when a majority of the voters sincerely prefers some "lottery" L over that winner (and, in such cases, they will get L).
Incentivizes honest scores:
Strategic voters (as well as honest ones) will always provide all-sincere scores (positive-slope linear functions of their true utilities for the candidates) on their range-style sub-ballot. Any dishonest scoring (or omitted scores) is, strategically speaking, strictly suboptimal.
Majoritarian if X is:
If X is a majoritarian voting method, here meaning one in which a voter-majority can always force their common-favorite candidate to be elected, then your voting method will also be majoritarian.

## In other words

This scheme will convert any member X of a wide class of voting systems into a voting system in which voting honestly is the (generally uniquely) best voting strategy, thus essentially totally evading the Gibbard-Satterthwaite impossibility theorem, probably the single most important theorem in voting theory!!

The catch is, each ballot will now have two parts, (i) the "be honest here" part and (ii) the other part. A smart voter will indeed be honest in part (i), but the problem is that the winner is determined by both parts, not just by part (i), of the ballots.

The main idea behind this solution is due to Forest Simmons, 19 Nov 2009. (For a quite different utility-reading method, which seems of less practical value, see puzzle #104.) However we've also incorporated contributions by Jobst Heitzig, Jameson Quinn, and Warren D. Smith.

The rules of our new voting method (which is not voting method X, but is derived from X) are as follows.

1. Each voter supplies two ballots: the "range-style sub-ballot" (scoring each candidate with a real number in [0,1]) and an "X-style sub-ballot" (obeying the rules for voting system X).
2. From the X-style sub-ballots, determine who the winner A, the second-placer B, and the third-placer C would have been using voting method X.
3. Let L denote the following lottery: With probability p, the winner is C; otherwise it is B. Here p is the fraction of X-style sub-ballots which express a clear preference for C over B.
4. If at least half of all range-style sub-ballots score A greater than the expected rating for L, that is if    scoreη(A)>p·scoreη(C)+(1-p)·scoreη(B)    is satisfied by at least half of all ballots η, then elect A and stop.
5. Randomly-uniformly select a real number q with 0<q<1. If q>ε then elect A and stop.
6. Randomly select an X-style ballot (all equally likely). If it expresses a clear preference for C over B, elect C; otherwise elect B. Stop.

#### Why this works

We use as a lemma the known fact that in 2-choice simple-majority elections, honest voting is the optimal strategy; and if there is uncertainty about the other votes, it is the uniquely optimal strategy.

• If any voter dishonestly scores any candidate on her range-style sub-ballot, she risks voting wrong in the simple-majority 2-choice election in the rules step 4. Because p and the identities of B and C are unpredictable, only honest scoring is risk-free. And note these scores are not used for any purpose other than this vote in step 4.
• Clearly only A, B, or C can win.
• Because of step 5 in the rules, A will win with probability≥1-ε.
• If X is majoritarian and the voter-majority votes on their X-style sub-ballots in such a way as to force their common-favorite A to win; and also scores A maximum and everybody else minimum on their range-style sub-ballots; that forces A to win.

This has assumed that voting a sincere range-style ballot is "free" – that it doesn't cost time or "cognitive energy," either for candidate research or for evaluation.

Of course, in a large democracy, voting at all would scarcely ever be selfishly rational if it weren't free, and people still vote. So that assumption can't be too wrong. Still, I think we'd need ε>0.001 to motivate sufficient voters to be sufficiently careful with their range voting.

Also, note that to the extent anybody extracts and publishes useful data from the honest range totals, we unfortunately add strategic incentives to that vote. (We were pretending "strategic voters" were solely interested in who won. Trouble is, they might also be interested in influencing who gets the "moral victory" of winning the unofficial "honest vote.") For instance, if I vote strategically on the X-style sub-ballot, I may choose to vote the same strategy on the "honest" range-style sub-ballot to inflate the published "sincere score" of my candidate, even though this risks sacrificing my chance to favorably-change the real winner.

Finally, note that, presuming we're electing some sort of official who has given term of office, this system could, instead of using randomness, split the term of office between two candidates. A relatively-short deterministic term in office for the "backup" candidate elected using the honest-range-backed choice-between-lotteries may motivate voters to vote well on the range ballot, better than a small chance that the backup wins, with the probabilistic system. It may also be more manifestly "fair," because it is nonrandom.

If ε≥1 then step 5 can be erased.

If X happens (also) to be range voting, then we get a double range voting election-method where each ballot consists of one "sincere" and one "strategic" range-voting-style ballot. Observe that this voting method (and some of the others described here) all evade the Gibbard-Satterthwaite impossibility theorem, i.e. "accomplishing the impossible." This double range voting method with ε=1 will in practice (in terms of the winners it generates) very much resemble "range + (later) top-2-runoff," which is pretty good.