Hacker News new | ask | show | jobs
by sologirlcamper 1704 days ago
There's also the much stronger Hylland's theorem, which shows that any cardinal system of voting, one where votes also show how much they prefer one candidate to another, must either encourage strategic voting, or be a randomized dictatorship.

https://www.researchgate.net/publication/24064783_Strategy-p...

"This paper analyses strategy-proof mechanisms or decision schemes which map profiles of cardinal utility functions to lotteries over a finite set of outcomes. We provide a new proof of Hylland’s theorem which shows that the only strategy-proof cardinal decision scheme satisfying a weak unanimity property is the random dictatorship. Our proof technique assumes a framework where individuals can discern utility differences only if the difference is at least some fixed number which we call the grid size. We also prove a limit random dictatorship result which shows that any sequence of strategy-proof and unanimous decision schemes defined on a sequence of decreasing grid sizes approaching zero must converge to a random dictatorship."

2 comments

"Strategy-proof" is a really strange thing to strive for. Making dishonest strategic voting "really really hard" is more than good enough.

By way of example, exploiting a strategic voting vulnerability in certain ranked ballot elections can require both near-perfect information about how everyone else is voting and then solving an NP-hard math problem.

Saying that such an exploit is theoretically possible and then to start talking about dictatorships as being immune is like saying there's a risk someone will win the lottery unless we ban earning money.

Polling tries to figure out how everyone is going to vote, and if you look at the trends, it still mostly works. NP-hard problems can be estimated. I'm not saying that systems like RCV aren't better when compared to others, but that parties can still attempt to game the system.

Ultimately, the real tradeoffs with voting systems are societal I feel. Districts aren't mentioned enough in conversations like this. You can have districts and elect multiple people, through smaller and closer elections. If you must elect one person, you can still have an odd number of districts and pick a winner. To game neutrally drawn districts, people would have to move.

Also ran across:

> It states that for any deterministic process of collective decision, at least one of the following three properties must hold:

> 1. The process is dictatorial, i.e. there exists a distinguished agent who can impose the outcome;

> 2. The process limits the possible outcomes to two options only;

> 3. The process is open to strategic voting: once an agent has identified their preferences, it is possible that they have no action at their disposal that best defends these preferences irrespective of the other agents' actions.

> […] Gibbard's theorem can be proven using Arrow's impossibility theorem.

> Gibbard's theorem is itself generalized by Gibbard's 1978 theorem[2] and Hylland's theorem, which extend these results to non-deterministic processes, i.e. where the outcome may not only depend on the agents' actions but may also involve an element of chance.

* https://en.wikipedia.org/wiki/Gibbard%27s_theorem