Is this voting system strategy proof?
post by Donald Hobson (donald-hobson) · 2024-09-06T20:44:46.691Z · LW · GW · No commentsThis is a question post.
Contents
Answers 20 Scott Garrabrant 7 Charlie Steiner 3 Anon User None No comments
My voting system works like this. Each voter expresses their preferences for all candidates on a real numbered utility scale.
Then a Maximal lottery takes place over all lotteries over candidates. https://en.wikipedia.org/wiki/Maximal_lotteries
Lets describe this in more detail. Suppose there are 3 candidates. A,B,C.
The set of candidates is
A probability distribution over candidates looks like
This probability distribution is in the set of all probability distributions over .
A probability distribution over probability distributions looks like
Though note that there are infinitely many distributions, so most distributions-of-distributions will be assigning probability densities.
Also note that we can sample a candidate from this distribution over distributions by first sampling a distribution, and then sampling a candidate from that distribution. This is equivalent to integrating a distribution-of-distributions into a distribution over candidates and then sampling that.
A distribution is equivalent to a point in a triangle. A distribution over distributions is a probability density over a triangle, ie a non-negative function over the triangle (may include dirac deltas)
So the voters all mark their preferences on a numerical scale.
Then these votes get sent to Fred and George, 2 perfectly rational players in a 0 sum game.
Fred and George both propose probability distributions over the candidates.
Fred's utility is the number of candidates that strictly prefer Fred's proposed probability distribution over Georges, minus the number of voters that strictly prefer Georges distribution over Freds.
This game has a unique Nash equilibrium. This equilibrium is a distribution over distributions. Sample a candidate from this equilibrium to get the election winner.
I know that this has a few nice properties. If candidate is the first choice of the majority, then definitely wins. If everyone prefers A to B, then B has no chance of winning. If C has no chance of winning, the candidates existence doesn't influence the election.
Is this system strategy proof, or can it be gamed? Will voters ever be incentivized to lie about their preferences?
Answers
I proposed this same voting system here: https://www.lesswrong.com/s/gnAaZtdwjDBBRpDmw [? · GW]
It is not strategy proof. If it were, that would violate https://en.wikipedia.org/wiki/Gibbard–Satterthwaite_theorem [Edit: I think, for some version of the theorem. It might not literally violate it, but I also believe you can make a small example that demonstrates it is not strategy proof. This is because the equilibrium sometimes extracts all the value from a voter until they are indifferent, and if they lie about their preferences less value can be extracted.]
Further, it is not obviously well defined. Because of the discontinuities around ties, you cannot take advantage of the compactness of the space of distributions, so it is not clear that Nash equilibria exist. (It is also not clear that they don't exist. My best guess is that they do.)
Epistemic status: I don't actually understand what strategic voting means, caveat lector
Suppose we have three voters, one who prefers A>B>C, another B>C>A, the third C>A>B. And suppose our preferences are that the middle one is 0.8 (on a scale where the top one is 1 and bottom 0).
Fred and George will be playing a mixed Nash equilibrium where they randomize between catering to A, B, or C preferrers - treating them as a black box the result will be 1/3 chance of each, all voters get utility 0.59.
But suppose I'm the person with A>B>C, and I can predict how the other people will vote. Should I change my vote to get a better result? What happens if I vote B>C>A, putting my own favorite candidate at the bottom of the list? Well, now the Nash equilibrium for Fred and George is 100% B, because 2 the C preferrer is outvoted, and I'll get utility 0.8, so I should vote strategically.
↑ comment by Donald Hobson (donald-hobson) · 2024-09-07T11:39:07.437Z · LW(p) · GW(p)
Your right. This is a situation where strategic voting is effective.
I think your example breaks any sane voting system.
I wonder if this can be semi-rescued in the limit of a large number of voters each having an infinitesimal influence?
Edit: No it can't. Imagine a multitude of voters. As the situation slides from 1/3 on each to 2/3 on BCA, there must be some point at which the utility for an ABC voter increases along this transition.
Replies from: Charlie Steiner↑ comment by Charlie Steiner · 2024-09-07T12:39:42.081Z · LW(p) · GW(p)
Yeah, "3 parties with cyclic preferences" is like the aqua regia of voting systems. Unfortunately I think it means you have to replace the easy question of "is it strategy-proof" with a hard question like "on some reasonable distribution of preferences, how much strategy does it encourage?"
Replies from: donald-hobson↑ comment by Donald Hobson (donald-hobson) · 2024-09-07T16:56:36.066Z · LW(p) · GW(p)
Yep. And I'm seeing how many of the traditional election assumptions I need to break in order to make it work.
I got independence of irrelevant alternatives by ditching determinism and using utility scales not orderings. (If a candidate has no chance of winning, their presence doesn't effect the election)
What if those preferences were expressed on a monetary scale and the election could also move money between voters in complicated ways?
↑ comment by James Payor (JamesPayor) · 2024-09-09T17:09:34.264Z · LW(p) · GW(p)
The part that I don't quite follow is about the structure of the Nash equilibrium in the base setup. Is it necessarily the case that at-equilibrium strategies give every voter equal utility?
The mixed strategy at equilibrium seems pretty complicated to me, because e.g. randomly choosing one of 100%A / 100%B / 100%C is defeated by something like 1/6A 5/6B. And I don't have a good way of naming the actual equilibrium. But maybe we can find a lottery that defeats any strategy that priveliges some of the voters.
Replies from: Charlie Steiner↑ comment by Charlie Steiner · 2024-09-09T18:47:20.804Z · LW(p) · GW(p)
Yeah, I'm not actually sure about the equilibrium either. I just noticed that not privileging any voters (i.e. the pure strategy of 1/3,1/3,1/3) got beaten by pandering, and by symmetry there's going to be at least a three-part mixed Nash equilibrium - if you play 1/6A 5/6B, I can beat that with 1/6B 5/6C, which you can then respond to with 1/6C 5/6A, etc.
The 3rd paragraph of the Wikipedia page you linked to seems to answer the very question you are asking:
Maximal lotteries do not satisfy the standard notion of strategyproofness [...] Maximal lotteries are also nonmonotonic in probabilities, i.e. it is possible that the probability of an alternative decreases when a voter ranks this alternative up
↑ comment by Donald Hobson (donald-hobson) · 2024-09-07T11:31:58.987Z · LW(p) · GW(p)
That isn't proof, because the wikipedia result is saying there exists situations that break strategy-proofness. And these elections are a subset of Maximal lotteries. So it's possible that there exists failure cases, but this isn't one of them.
No comments
Comments sorted by top scores.