LESSWRONG
LW

Is this voting system strategy proof?
1 min read
Comment Permalink
Answer by Scott Garrabrant202

I proposed this same voting system here: https://www.lesswrong.com/s/gnAaZtdwjDBBRpDmw


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.)

Reply
See in context
by Donald Hobson
1 min read
A
39

17

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?

New to LessWrong?

Getting Started

FAQ

Library

World Modeling1
Frontpage

17

Is this voting system strategy proof?
New Answer
New Comment


3 Answers sorted by
top scoring

Scott Garrabrant

202

I proposed this same voting system here: https://www.lesswrong.com/s/gnAaZtdwjDBBRpDmw


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.)

Charlie Steiner

75

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.

[-]Donald Hobson40

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. 

Reply
7Charlie Steiner
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?"
2Donald Hobson
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? 
[-]James Payor10

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.

Reply
3Charlie Steiner
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.

Anon User

3-2

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

[-]Donald Hobson20

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. 

Reply
Moderation Log
A
30