GT method: Game-theory based voting system by Shen/Rivest vs other ranked-choice methods?

[Neal McBurnett]

In 2010 Rivest and Shen published

An Optimal Single-Winner Preferential Voting System Based on Game Theory
http://people.csail.mit.edu/rivest/gt/latest_conf.pdf

The abstract reads:

We describe an optimal single-winner preferential voting system, called the “GT method” because of its use of symmetric two-person zero-sum game theory to determine the winner. Game theory is used not to describe voting as a multi-player game between voters, but rather to define when one voting system is better than another one. The cast ballots determine the payoff matrix, and optimal play corresponds to picking winners optimally.

The GT method is a special case of the “maximal lottery methods” proposed by Fishburn [14], when the preference strength between two candidates is measured by just the margin between them. We suggest that such methods have been somewhat underappreciated and deserve further study.

The GT system, essentially by definition, is optimal: no other preferential voting system can produce election outcomes that are preferred more by the voters, on the average, to those of the GT system. We also look at whether the GT system has several standard properties, such as monotonicity, Condorcet consistency, etc. We also briefly discuss a deterministic variant of GT, which we call GTD.

We present empirical data comparing GT and GTD against other voting systems on simulated data.

The GT system is not only theoretically interesting and optimal, but simple to use in practice; it is probably easier to implement than, say, IRV. We feel that it can be recommended for practical use.

Code, simulation experiments, etc is on github:

https://github.com/ron-rivest/game-theory-voting-system

I'm surprised to not see much more about it on the web.

What do people think of it? How does it compare to other methods, via other criteria?

Cheers,

Neal McBurnett http://neal.mcburnett.org/

[Brian Olson]

The good news is that there's a handy Python reference implementation of the GT election method

https://github.com/ron-rivest/game-theory-voting-system/blob/master/vs.py

The bad news is it's 1500 lines I don't have time to read right now. Sounds interesting though.

--
You received this message because you are subscribed to the Google Groups "The Center for Election Science" group.
To unsubscribe from this group and stop receiving emails from it, send an email to electionscience+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Nevin Brackett-Rozinsky]

I find the idea interesting and worthy of consideration.

The approach of comparing voting systems holistically, to identify an optimal strategy for choosing a winner from a given set of ranked ballots, is theoretically sound and its impact on voting theory could be profound.

One point of subjectivity is the choice of metric by which to compare outcomes. The proposed GT system uses the head-to-head margin of “how many more voters prefer candidate X over Y, than vice versa”. If instead one were to take the difference in rank position as a measure of strength of preference, then the same conceptual system would resolve to exactly the Borda count.

The authors’ choice of head-to-head tally margin has merit, as it accords every voter equal voice in all pairwise matchups. Even so, in the case where multiple strategies are game-theoretically optimal, their proposed choice (minimize sum of squared probabilities) leaves something to be desired with regard to weakly-dominated candidates.

For example, consider the following 3-candidate election with 4 voters:

2 ABC

1 BAC

1 BCA

The head-to-head “row beats column by…” tally margins are:

   A  B  C

A  0  0  2

B  0  0  4

C -2 -4  0

Note that A is weakly dominated by B, since A never outperforms B but can equal it against some opposing strategies.

The set of optimal strategies consists of “choose A or B with any probability”. Clearly those strategies all tie against each other, and each of them outperforms all other strategies (ie. those which sometimes elect C), so they are optimal.

The proposed GT system picks the strategy “choose A or B with equal probability”, eg. it has a 50% chance to select A or B as the winner. This is indeed an optimal strategy. However it is obvious at a glance that B is superior to A against all non-optimal strategies and equal against optimal strategies, so the “best” choice is B when comparing against other voting systems which may not be optimal.

I have not explored the full scope of this shortcoming, and there is a well-known difficulty with removing weakly-dominated options, namely that the order of elimination affects the outcome.

The situation we are concerned with, though, involves performance against non-optimal strategies. Thus we cannot make any assumptions about what the opponent will do—they may even choose a strongly-dominated strategy. That means we cannot eliminate dominated columns at all, only dominated rows. So there will be no “chaining” or “cascading” of eliminations, and we do not have to worry about their order because there is just a single step.

Consequently, I think it is acceptable and desirable to say, “if an optimal strategy gives positive probability to a weakly-dominated candidate, use a different optimal strategy”. This is always possible, because the dominated candidate’s probability of winning can be reassigned to the dominator. Note that the identification of weak dominance is done across the entire table, without eliminating any columns.

It is less obvious whether we should include in our assessment, and thus eliminate, candidates who are weakly dominated by a probabilistic mixture of other candidates. For example, in the following margin table, W is weakly dominated by 50% X and 50% Y (actually by any mix of them between 1/3 and 2/3):

   W  X  Y  Z  Q

W  0  0  0  4  4

X  0  0  0  8  2

Y  0  0  0  2  8

Z -4 -8 -2  0  0

Q -4 -2 -8  0  0

From a game-theoretic perspective, when facing a sub-optimal opponent here it is strictly superior to choose X and Y with equal likelihood than it is to choose W, so it seems reasonable that W should not win, and in general that a candidate who is weakly-dominated by any mixed strategy should not win. This is also always possible, because there cannot be a cycle of dominance.

Another more pragmatic difficulty with the proposed GT system is simply explaining how it works. The actual algorithm to find optimal strategies is quite tractable with linear programming though, and I may add it to my simulator in the future.

Nevin

[Nevin Brackett-Rozinsky]

Further observations:

• The GT method always elects a candidate from the Smith set.

• The GT method applied to the just Smith set yields the same outcome as it does for the full election.

• The results of the GT method are not always intuitive, but upon deeper inspection they do indeed make sense.

To expand on that last point, consider the following election with 3 candidates and 100 voters:

49 ABC

48 CAB

3 BCA

This has a Condorcet cycle:

A beats B by 94

B beats C by 4

C beats A by 2

At first glance, we notice that A has the largest victory and the smallest defeat, as well as the highest Borda total. However, the GT method elects A just 4% of the time.

Can that really be optimal?

Let’s think about it.

Okay, B gets crushed by A and barely squeaks by C. We don’t want to get crushed because that is bad for our long-term average, so B probably should not win. And if B loses (or didn’t run at all) then C defeats A.

It seems that A’s victory over B is mostly ephemeral. As much as we would like to score that +94 to improve our long-term average, the only way it happens is if we pick A *and* the system we’re up against picks B. But since B shouldn’t win, we expect the other system won’t pick B either.

In particular, if we usually pick A and the other system usually picks C, then we are going to lose frequently. We would rather be that other system and pick C most often, which is exactly what GT does. The optimal distribution is:

A wins 4%

B wins 2%

C wins 94%

Moreover, in any 3-way Condorcet cycle, the probability of each candidate winning is always proportional to the margin of victory between the *other two* candidates. And this is provably optimal.

I foresee great difficulty in explaining to people that C really and truly should win this election almost every time, yet the fact remains that this is the only choice which cannot be beaten in the long run!

Nevin

[Andy Jennings]

Thanks for this excellent analysis, Nevin.

I do remember this feature now (from when we discussed this system years ago).  In a 3-candidate Condorcet cycle, the probability of each candidate winning is proportional to the margin of victory between the other two candidates.

So if there are only three candidates and there is a Condorcet cycle, then all the voters completely reversing their preference orders wouldn't change the winning lottery at all!  Don't you find this strange?  It makes me wonder if what the margin of victory in a Condorcet cycle even means.  And it's another thing that would be difficult to explain to voters.

~ Andy

--

[Nevin Brackett-Rozinsky]

So if there are only three candidates and there is a Condorcet cycle, then all the voters completely reversing their preference orders wouldn't change the winning lottery at all!  Don't you find this strange?

Indeed, at first glance it does seem counterintuitive that reversing every voter’s rankings would yield the same outcome. And yet, the situation we are looking at with a 3-way Condorcet cycle is in some sense a generalized tie.

If we had a rule that said “In case of a tie, elect the most moderate candidate”, then that would also exhibit reversal symmetry here because inverting the rankings will leave the same candidate in the center.

The conceptual principle of electing the moderate shows that reversal symmetry may actually be desirable in certain circumstances.

It makes me wonder if what the margin of victory in a Condorcet cycle even means.

Well, of course we know what it *literally* means, but at a higher level I find the competing-species model to be analogous.

If we consider the head-to-head results to quantify how much the candidates inconvenience each other, then those who are highly inconvenienced will see their prospects rapidly diminish. That in turn means they are much less detrimental to the rest, and the process continues.

The parallel is not exact, but the concept is valid: if the presence of B is the only thing keeping C in check, and A drives off B rapidly, then C will eventually dominate.

And it's another thing that would be difficult to explain to voters.

Completely agreed.

Although, imagine three people playing laser tag in a mutual standoff:

A aims at B

B aims at C

C aims at A

If A and B are close together with C more distant, then the situation is similar: A can hit B with high accuracy, while B can hit C and C can hit A with low accuracy.

Nobody wants to act first, but especially not B because if B zaps C then A will instantly zap B. So B aiming at C is an empty threat, and both A and C know this.

Now A has no reason to keep B around: B won’t take out C, and if A turns away from B then B might turn toward A. Thus A may as well zap B then face C. And as soon as A zaps B, then C will go after A.

It takes time for A to aim at C, so the most likely outcome is a victory by C.

Or maybe C tries to zap A first. Accuracy is low at this distance, so A can probably react. But there’s no way A turns away from B without zapping first, so once again the most likely outcome is a victory by C.

At this point B recognizes they have nothing to lose, so maybe everyone starts zapping all at once. Again, A is unlikely to miss and B is unlikely to hit, hence the most probable outcome is still a victory by C.

How’s that for an interpretation of a Condorcet cycle? It even explains the reversal symmetry: switch where everyone is aiming and the result will be the same.

Nevin

To unsubscribe from this group and stop receiving emails from it, send an email to electionscien...@googlegroups.com.

[Toby Pereira]

On Sunday, 28 August 2016 15:03:22 UTC-4, Nevin Brackett-Rozinsky wrote:

Moreover, in any 3-way Condorcet cycle, the probability of each candidate winning is always proportional to the margin of victory between the *other two* candidates. And this is provably optimal.

I haven't read the whole article yet, but surely optimal depends on what property you are trying to maximise. Is it maximising the "right" thing?

 

I foresee great difficulty in explaining to people that C really and truly should win this election almost every time, yet the fact remains that this is the only choice which cannot be beaten in the long run!

Beaten in what sense? 

[Markus Schulze]

Hallo,

there are many papers where some author makes presumptions
about the distribution of the voters and the candidates,
about the used strategies, about how the performance of an
election method is measured in concrete test cases, etc..
The author then proposes a new election method that performs
better than every other known election method.

However, this is not surprising. When you know how the
test cases are generated and when you know how the
performance of an election method in a given test case
is defined, you can always find an election method that
performs as well as possible. This is true, especially
when criteria (like monotonicity) are not considered
important so that you can define your election method
for each test case independently. In the paper "An

Optimal Single-Winner Preferential Voting System Based

on Game Theory" by Ronald L. Rivest and Emily Shen,
the authors write that their own method (GT, GTD)
violates monotonicity.

Therefore, a more interesting question is which election
method performs the second best. Here, Rivest and Shen
write that the Schulze method performs the second best
after their own method (GT, GTD). They write:

* "GT and GTD are perfect by definition in this metric,
but Schulze is amazingly close."

* "Plurality does quite poorly (agreeing with GTS only
55.15% of the time), as does IRV (72.99%), but minimax
(99.15%) and the Schulze method (99.51%) have nearly
perfect agreement with the support of GT."

In my opinion, this shows how robust the Schulze method
is when it has to compete with other election methods in
randomly generated test cases.

Markus Schulze

[Andy Jennings]

On Mon, Aug 29, 2016 at 2:51 PM, Nevin Brackett-Rozinsky <nevin.brack...@gmail.com> wrote:

Although, imagine three people playing laser tag in a mutual standoff:

A aims at B

B aims at C

C aims at A

If A and B are close together with C more distant, then the situation is similar: A can hit B with high accuracy, while B can hit C and C can hit A with low accuracy.

Nobody wants to act first, but especially not B because if B zaps C then A will instantly zap B. So B aiming at C is an empty threat, and both A and C know this.

Now A has no reason to keep B around: B won’t take out C, and if A turns away from B then B might turn toward A. Thus A may as well zap B then face C. And as soon as A zaps B, then C will go after A.

It takes time for A to aim at C, so the most likely outcome is a victory by C.

Or maybe C tries to zap A first. Accuracy is low at this distance, so A can probably react. But there’s no way A turns away from B without zapping first, so once again the most likely outcome is a victory by C.

At this point B recognizes they have nothing to lose, so maybe everyone starts zapping all at once. Again, A is unlikely to miss and B is unlikely to hit, hence the most probable outcome is still a victory by C.

How’s that for an interpretation of a Condorcet cycle? It even explains the reversal symmetry: switch where everyone is aiming and the result will be the same.

I like that analogy.  It does seem to have something to do with letting the other candidate eliminate the one who could defeat you, doesn't it?

[Toby Pereira]

I don't like the deterministic GTD variant.

"Instead of randomly picking a candidate according to this probability distribution, GTD chooses the candidate with the maximum probability in this optimal mixed strategy."

This would clearly fail independence of clones. We could have the probabilities A: 30%, B: 30%, C: 40%. C would be elected, but A and B could be clones of each other, so would win without the other one.

[Toby Pereira]

As far as I understand it then, for a given election, system A beats system B if more people prefer the result from system A than the result from system B - the difference being the margin. And that this GT system, over the long term, will never have an average margins defeat compared to any other system.

So, if you have an A>B>C>A cycle, then any deterministic system will lose against some other one. A system that picks A lose to a system that picks C, a system that picks B loses to a system that picks A, and a system that picks C loses to a system that picks B.

I'm not entirely convinced by this though. If you have a candidate A that beats B and C in basically every deterministic Condorcet method, I'm not sure it really means much to say that deterministically electing A isn't the best thing to do because a system picking C is preferred by most people for this election. It's optimal only in the sense that it maximises what the paper authors want to maximise.

Presumably a better method would be one that has the best margins result again the GT method over the long term, rather than using this simplistic plurality logic. 

[Toby Pereira]

On Tuesday, 30 August 2016 05:42:11 UTC-4, Markus Schulze wrote:

Therefore, a more interesting question is which election
method performs the second best. Here, Rivest and Shen
write that the Schulze method performs the second best
after their own method (GT, GTD). They write:

* "GT and GTD are perfect by definition in this metric,
  but Schulze is amazingly close."

* "Plurality does quite poorly (agreeing with GTS only
  55.15% of the time), as does IRV (72.99%), but minimax
  (99.15%) and the Schulze method (99.51%) have nearly
  perfect agreement with the support of GT."

In my opinion, this shows how robust the Schulze method
is when it has to compete with other election methods in
randomly generated test cases.

Markus Schulze

Second best doesn't really mean much considering the lack of other methods tested. The only other Condorcet method tested was minimax, so we're really just saying that it beats minimax. And even minimax has over 99% agreement. It's likely that all reasonable Condorcet methods will have 99%+ agreement.

 

[Andy Jennings]

On Tue, Aug 30, 2016 at 2:42 AM, Markus Schulze <Markus....@alumni.tu-berlin.de> wrote:

In the paper "An
Optimal Single-Winner Preferential Voting System Based
on Game Theory" by Ronald L. Rivest and Emily Shen,
the authors write that their own method (GT, GTD)
violates monotonicity.

Do we have an example where it violates monotonicity?

Take Nevin's example:

49 ABC

48 CAB

3 BCA

One voter moving C up will only decrease the margin for B's defeat of C, slightly decreasing the probability of A winning, hence slightly increasing the probability of B and C winning.  It appears we can't do it with only these cyclical orderings.  Let's add one ABC voter and one CBA voter, which doesn't change the margins:

50 ABC

48 CAB

3 BCA

1 CBA

If the CBA voter moves B up:

50 ABC

48 CAB

4 BCA

That increases the margin for B's defeat of C, which slightly increases A's probability of winning, hence slightly decreasing B and C's probability of winning.

In particular, B's probability of winning goes from 2% to 1.96%.  Is there any excuse for this?

~ Andy

[Toby Pereira]

On Tuesday, 30 August 2016 12:23:30 UTC-4, Andrew Jennings wrote:

In particular, B's probability of winning goes from 2% to 1.96%.  Is there any excuse for this?

~ Andy

Presumably it wouldn't be optimal in the sense they are after if it didn't do this?

I was thinking more generally about the optimality of this system. In a sense it could be said to be the "ultimate Condorcet" method given what it is maximising. For any set of ballots, no other method will produce results that are preferred by a majority over the long term (if the election is run many times). So if it was compared to another system and for each election people voted on which system gave them a better result and these votes added up, this would never lose to another system in the long haul.

But on the other hand, we can see Condorcet as a criterion rather than a class of method. A Condorcet method is just one that passes the Condorcet criterion. For comparison, we don't class methods that pass the monotonicity criterion as "monotonic methods". Well, we call them monotonic methods, but we don't see them as a class in the same way as Condorcet methods. The point being that if we shift our viewpoint, we are not necessarily looking for the "ultimate in Condorcetness" even if we want a method that passes the Condorcet criterion. It's just one criterion that we want our method to pass, along with monotonicity but not at the expense of everything else. Wanting a monotonic method doesn't mean we just look for the "ultimate in monotonicity" at the expense of everything else.

[Toby Pereira]

Looking at Nevin's example - it's interesting to note that if you compare the GT method against elect A, elect B or elect C, it doesn't actually "beat" any of them. All three are a tie. Is this always the case for GT v any member of the Smith set?

On Sunday, 28 August 2016 15:03:22 UTC-4, Nevin Brackett-Rozinsky wrote:

[Andy Jennings]

On Tue, Aug 30, 2016 at 2:42 AM, Markus Schulze <Markus....@alumni.tu-berlin.de> wrote:

Hallo,

there are many papers where some author makes presumptions
about the distribution of the voters and the candidates,
about the used strategies, about how the performance of an
election method is measured in concrete test cases, etc..
The author then proposes a new election method that performs
better than every other known election method.

However, this is not surprising. When you know how the
test cases are generated and when you know how the
performance of an election method in a given test case
is defined, you can always find an election method that
performs as well as possible. This is true, especially
when criteria (like monotonicity) are not considered
important so that you can define your election method
for each test case independently. In the paper "An
Optimal Single-Winner Preferential Voting System Based
on Game Theory" by Ronald L. Rivest and Emily Shen,
the authors write that their own method (GT, GTD)
violates monotonicity.

I agree that just because an election method is defined sensibly for each possible voter profile, it doesn't mean the method will have good global properties, for example resistance to strategic voting or strategic nomination.

 

Therefore, a more interesting question is which election
method performs the second best. Here, Rivest and Shen
write that the Schulze method performs the second best
after their own method (GT, GTD). They write:

* "GT and GTD are perfect by definition in this metric,
  but Schulze is amazingly close."

* "Plurality does quite poorly (agreeing with GTS only
  55.15% of the time), as does IRV (72.99%), but minimax
  (99.15%) and the Schulze method (99.51%) have nearly
  perfect agreement with the support of GT."

I don't see too much value in the percentage agreement with GTS.  I mean, it's useful to tell us how bad plurality and IRV are, but the "support of GT" is any candidate given a nonzero probability of winning.  I'm imagining it's usually equal to the Smith set.  That is, it's a pretty easy criterion for a Condorcet method to meet.  Seeing one of the failures may be interesting, though...

 

In my opinion, this shows how robust the Schulze method
is when it has to compete with other election methods in
randomly generated test cases.

Markus Schulze

--
You received this message because you are subscribed to the Google Groups "The Center for Election Science" group.

To unsubscribe from this group and stop receiving emails from it, send an email to electionscience+unsubscribe@googlegroups.com.

[Nevin Brackett-Rozinsky]

On Tuesday, August 30, 2016 at 9:53:28 PM UTC-4, Toby Pereira wrote:

Looking at Nevin's example - it's interesting to note that if you compare the GT method against elect A, elect B or elect C, it doesn't actually "beat" any of them. All three are a tie. Is this always the case for GT v any member of the Smith set?

Not necessarily the entire Smith set. For example, in the following margin table the Smith set comprises all 4 candidates:

   D  E  F  G

D  0  0 -2 -2

E  0  0  2 -2

F  2 -2  0  2

G  2  2 -2  0

Here E, F, and G form a Condorcet cycle, while D ties with E and loses to the others. The optimal strategy is to pick from E, F, and G with equal probability, thus GT does so. Any system which picks D will lose against GT in the long run, despite D’s presence in the Smith set.

The GT method will, however, tie on average against any strategy that always elects a candidate who appears in the support of an optimal strategy. This is due to the principle of indifference in game theory, which states “If there exists an optimal strategy for I giving positive probability to row i, then every optimal strategy of II gives I the value of the game if he uses row i.” [ref: §3]

Of particular note, if a voting system always elects a candidate whom the GT method gives a positive probability of winning, then in the long run neither system will outperform the other. However most such strategies (eg. “elect E”), even though they tie against GT, are not themselves optimal because they can be beaten.

Remember that optimal strategies are *unbeatable*.

Nevin

[Markus Schulze]

Hallo,

a frequently used strategy to "solve" impossibility theorems is simply by
keeping the proposed election method undefined for problematic situations.
Therefore, in my opinion, an important requirement for every properly
defined election method should be that it is defined for every possible
situation.

In the paper "An Optimal Single-Winner Preferential Voting System Based on
Game Theory", Ronald L. Rivest and Emily Shen write:

> We randomly generated 10,000 profiles for m = 5 candidates, as follows.
> Each profile had n = 100 full ballots. Each candidate and each voter was
> randomly assigned a point on the unit sphere-think of these points as
> modeling candidates' and voters' locations on Earth. A voter then lists
> candidates in order of increasing distance from her location. With this
> "planetary" distribution, about 64.3% of the profiles had a Condorcet
> winner, and about 77.1% of the 10,000 simulated elections had a unique
> optimal mixed strategy.

So the proposed election method is defined only in 77.1% of all test cases.

In the full version of their paper, they also write a few words about
the remaining 22.9%. For example, they write:

> The GT voting system satisfies the independence of clones properties in
> the following sense. If x is an optimal mixed strategy for the game based
> on the margin matrix for the given election, then when B is replaced by
> B1, B2, ..., Bk then in the game for the new election it is an optimal
> mixed strategy to divide B's probability according to x equally among
> B1, B2, ..., Bk. To see this, note that equations (9) and (10) will
> continue to hold. However, if the original game does not have a unique
> optimal mixed strategy, then balancing the probabilities in the derived
> game may affect probabilities outside of the clones in a different way
> than the balancing affects those probabilities in the original game --
> consider what must happen with an empty profile, where all candidates
> are tied.

So only in those 77.1% where the proposed method is defined, it
satisfies independence of clones. In the remaining 22.9% it can
violate independence of clones.

It is also important to notice that Rivest and Shen use
a significantly weaker version of independence of clones
because they add the presumption that every voter is indifferent
between all clones. They write:

> A voting system satisfies the independence of clones property
> if replacing an existing candidate B with a set of k > 1 clones
> B1, B2, ..., Bk doesn't change the winning probability for candidates
> other than B. These new candidates are clones in the sense that
> with respect to the other candidates, voters prefer each Bi to the
> same extent that they preferred B, and moreover, the voters are
> indifferent between any two of the clones.

See:

https://people.csail.mit.edu/rivest/gt/2010-04-10-RivestShen-AnOptimalSingleWinnerPreferentialVotingSystemBasedOnGameTheory_full.pdf

Markus Schulze

[Nevin Brackett-Rozinsky]

about 77.1% of the 10,000 simulated elections had a unique optimal mixed strategy.

So the proposed election method is defined only in 77.1% of all test cases.

Incorrect.

The authors specified which optimal strategy the GT will use when more than one is available, namely the distribution which minimizes the sum of squared probabilities. I commented previously on a shortcoming I perceived in that choice, but they did indeed make a choice.

Nevin