Nash Score for Voting Techniques

by abramdemski6 min read26th Nov 20205 comments

13

Voting TheoryMechanism DesignWorld OptimizationRationality
Frontpage

This is a follow-up to my thoughts on voting methods. As I discussed there, I worry that a utilitarian score for voting techniques, called VSE, doesn't capture everything important. In particular, I worry that it doesn't sufficiently push toward compromise solutions. I also raised several other concerns, but that's the concern I'll be discussing here.

The basic idea here will be to use the Nash bargaining solution to define "equitable" outcomes. I mentioned in my previous post that there were two conflicting ways of pointing out what's wrong with VSE: (a) it doesn't push toward equitable outcomes, (b) it doesn't push against transfers of wealth. An equitabillity-first solution would push toward wealth redistribution to reduce inequality. An anti-transfer solution would instead seek to uphold property rights more, decrease taxes, etc. Interestingly, the current proposal ends up somewhere between the two.

As I've described before, the Nash bargaining solution first shifts utilities so that each person's zero point is their best alternative to negotiating an agreement (called the BATNA point). Then, all utilities are multiplied together. This has the advantage of being invariant to meaningless transformations of people's utility functions, unlike just summing up utilities. (It also has a number of other advantages which Nash outlined.)

We can think of the BATNA point as the utility of "vote of no confidence" -- some electoral reformists propose that "no confidence" should be added to all ballots, representing the possibility of rejecting all candidates and putting together a new election.

Just as score voting would maximize VSE best if voters were entirely honest, we can design a voting method which would maximize Nash Score if voters were perfectly honest. The ballot is exactly like score voting plus a score for "no confidence":

Fill in one bubble in each row.012345678910
AliceOOOOOOOOOOO
BobOOOOOOOOOOO
CarolOOOOOOOOOOO
No ConfidenceOOOOOOOOOOO

However, instead of adding up all the scores to find the winner, we proceed as follows:

  • Subtract the "no confidence" score from the rest of the scores, on each ballot.
  • Eliminate any candidates who, on any ballot, score below zero. If all candidates are eliminated in this way, "no confidence" wins.
  • Score the remaining candidates by multiplying together all their scores on individual ballots.

This voting method is, of course, patently absurd. Any one person can throw the whole election by putting "no confidence" above everything else. This could only be appropriate for very small group elections, and even then, it's questionable.

This is because a real democracy doesn't actually seek the voluntary participation of every single member; even small groups aren't always OK giving every single member veto power over the group's existence. (I'm assuming that repeated "no confidence" votes would at some point lead to the dissolution of whatever governing body is holding the elections.) Bargaining theory is about contracts which have not yet been made, so it is more appropriate to assume voluntary compliance is required of each person.

Note that this is not just a problem of dishonest voting -- it's true that in a large vote such as a national election, some random person would vote "no confidence" regardless of whether it was rational for them to do so; but, it's also true that in a large election there would be someone who would honestly prefer to nullify the election, and even the government.

I'll think about solutions to that problem in a minute, but let's talk about advantages of this system (under an assumption of honesty):

  • Egalitarian: because we're maximizing the product, we much prefer a candidate who is a 2 for everyone as opposed to another candidate who is a 1 for half of people and a 3 for the other half.
  • Doesn't sacrifice Pareto-optimality: we never prefer egalitarianism at the expense of costless improvements to someone's welfare. This could be a problem if we just modified utilitarianism with a bonus score for equality, or something.
  • Moderately anti-transfer: people with a lot of resources are usually going to have higher BATNA points, which means that taking a bunch of their resources away isn't going to count as increasing equality. (This might be a point against the system, depending on your politics, and depending on how big of an effect this turns out to be.)

Correcting the No Confidence Problem

Alright, so, this is mostly unusable -- the score will too often be zero, which is what you get for dropping below anyone's BATNA (it should arguably go negative, but I don't know what the formula for that should be). Likewise, the Nash-score voting method will too often result in "no confidence".

What's to be done?

Assume Confidence 

One correction could be to get rid of the "no confidence" option, and just rate everything on a scale starting at 1 (so no one can "zero out" the election):

Fill in one bubble in each row.12345678910
AliceOOOOOOOOOO
BobOOOOOOOOOO
CarolOOOOOOOOOO

If voters are honest, this is just like score voting except that we multiply everything rather than add. (In a large election, this will get you astronomical numbers, but we can deal with that by calculating everything in the log domain.) This still gets us a more egalitarian result.

The corresponding score isn't very theoretically motivated, but at least it won't just report "zero" all the time.

Assume Confidence + STAR

Realistically, of course, voters will be strategic, meaning that a lot of people will rate most candidates 1 or 10. This devolves into range voting, which isn't too bad, but we can do better.

To be more precise: you should estimate the expected utility of the election (based on who you think will win), and score any candidate better than that average as a 10, and any candidate lower than that average as a 1.

To encourage voters to report a more honest spread of votes, we can take the STAR voting idea: select the two finalists by taking the candidates with highest multiplicative score, and then select the winner by whoever is most often scored higher than the other person. This heavily incentivises differentiating your preferences by scoring different candidates differently, because otherwise your vote doesn't count in the final step. It can also be justified as a kind of instant runoff: rather than letting voters estimate the probable winners and extreme-ize the scores based on that, you're finding the top two probable winners for them, and strategically extreme-izing voter scores for them to select between them. This is an approximate application of the revelation principle.

Unfortunately, this is vulnerable to clone problems (which I discussed extensively in a previous post). I'm not sure how to solve this problem while preserving the spirit of Nash Score voting.

Collective No Confidence

It doesn't really make sense to totally eliminate the "no confidence" option, though. If just one person would be better off with their BATNA, this shouldn't totally cancel the election. If a significant number of people prefer to cancel the election, however, then it should be cancelled.

Let's modify the Nash bargaining game.  We can pick a number -- for example, if at least 50% of people are better off with their BATNA, then we get "no deal". If a majority of people want the bargain to go through, however, then they can force the bargain on the minority. This reflects the reality that if a majority are unhappy with an election, the election won't stand, but an unhappy minority can be forced to accept the result. (50% is probably too high, realistically; a sizable minority who refuse to accept the election result is still a big problem.)

Now, ideally, we would solve that game by finding a game-theoretic equilibrium, in order to derive a generalization of the Nash score. However, this is a quick post, so I'm not going to really do the work of solving the game. Instead, my rough solution is as follows:

As with the first scoring method I described, subtract BATNA values from other utilities to set a zero value for each voter. Then, score each candidate by multiplying the utilities of each voter for whom they score positively, ignoring zero or negative scores -- except if a candidate gets a zero or negative score for 50% or more of ballots (or whatever the chosen cutoff), in which case, that candidate scores zero.

This score kind of sucks, because it entirely ignores the preferences which fall below the BATNA point, so long as less than 50% of people think similarly. Possibly a proper game-theoretic solution would be more sensitive to these negative values.

In any case, the voting method corresponding to this score is pretty obvious:

  • Use the Nash-inspired ballot from before.
  • Score candidates as described.
  • If any candidate scores above zero, then the candidate with the highest score wins. Otherwise, the election gets a "no confidence" result.

If voters are honest, then this obviously maximizes our score.

Of course, voters won't be 100% honest. We can apply the STAR-like correction again, using score to select two finalists and then doing an instant runoff. This encourages honesty for how voters score candidates. I'm not sure about the strategy for setting BATNA values, though. On the one hand, voters should set their BATNAs fairly high in order to try and eliminate candidates they don't like. On the other hand, if you can't successfully eliminate candidates, then a high BATNA means your preferences below the BATNA value don't count (until the final runoff step). So that incentivises you not to set your BATNA too high. But nothing about this suggests that people will use their true BATNA values.

Not sure how good this method is overall.

Embracing No-Confidence

Another route would be to embrace the high degree of no-confidence outcomes as a new type of voting, specifically for situations where everyone does need to be on board.

However, this seems like a fairly uncommon use-case.

A more common use-case would be a kickstarter-like situation, where some number of people have to be on board for anything to happen, but unlike regular kickstarter, the outcome is also in question. For example, the rationality community's location problem. This is a difficult problem because it requires aggregating the preferences of a lot of people, and creating consensus about the outcome, but also requires a great deal of deliberation. It would be nice if we had a voting method with the following properties:

  • We can elect representatives who speak for our interests. For example, it could be like liquid democracy where anyone can delegate their vote to anyone. Delegates can then put in the time and effort to form coherent opinions about which options best serve their constituency -- or, can delegate even further, creating a hierarchy of delegates. Delegation implies consent to abide by the result of the vote, so it's a consensus-building tool.
  • Each person can indicate additional conditions for a move. For example, Alice could state a condition that >100 other rationalists sign on to a move, and further state that the list must include Bob and Carol.
  • Delegates representing a sufficient number of people get involved with discussions, so that the difficult deliberations can (1) represent a sufficient number of people, while (2) involving a feasible number of people in discussion. Unlike classic liquid democracy, this creates a significant incentive to delegate your vote to another person (even if you are personally well-informed in the issues), because a small number of delegates can have a meaningful discussion and reach consensus, whereas a large number of people can't, no matter how well-informed they are.

I'm not sure what such a voting method should really look like, however.

13

5 comments, sorted by Highlighting new comments since Today at 1:32 PM
New Comment

This voting method is, of course, patently absurd. Any one person can throw the whole election by putting "no confidence" above everything else. This could only be appropriate for very small group elections, and even then, it's questionable.

This is because a real democracy doesn't actually seek the voluntary participation of every single member...

This is great explaining throughout, but especially the block quote.  You communicated to me (as in, I had a click/eureka moment) the idea you were trying to teach using very close to the least number of words required.

If 30% of people can block the election, someone's going to have to be command the troops. The least perverse option seems to be the last president. Trump could probably have gotten 30% to block it to stay in that chair. A minority blocking the election seems supposed to simulate (aka give a better alternative to) civil war, which is uncommon because it is costly. So perhaps blocking should be made costly to the populace. Say, tax everyone heavily for each blocked election and donate the money to foreign charities. This also incentivizes foreign trolls to cause blocked elections, which seems fair enough - if the enemy controls your election, it should crash, not put a puppet in office.

STAR is useless if people can assign real-valued scores. That makes me think that if it works, it's for reasons of discrete mathematics, so we should analyze the system from the perspective of discrete mathematics before trusting it.

Instead of multiplying values >= 1 and "ignoring" smaller values, you should make explicit that you feed the voter scores through a function (in this case \x -> max(0, log(x))) before adding them up. \x -> max(0, log(x)) does not seem like the optimal function for any seemly purpose.

STAR is useless if people can assign real-valued scores. That makes me think that if it works, it's for reasons of discrete mathematics, so we should analyze the system from the perspective of discrete mathematics before trusting it.

A fair point. If voters were allowed real-valued scores, they could make scores very close, and things still basically devolve into approval voting.

\x -> max(0, log(x)) does not seem like the optimal function for any seemly purpose.

Also true. I just don't know how to continue log into the negative ;p

Have you thought about treating 'no confidence' as a candidate? How would it play out if there were a variant of the approach detailed under 'Assume Confidence + STAR' where instead of assuming confidence you have an extra n.c. 'candidate' who gets scored the same as the others, and if it wins then the election is rerun?

I think part of the point (for me) of the Nash bargaining analogy is that "no confidence" isn't like other candidates... but, yeah, that being said, treating it as a candidate would produce more reasonable results here. I agree that "assume confidence + STAR" with an extra no-confidence candidate would be pretty reasonable compared to what I've come up with so far.

Still holding out hope for a more theoretically justified solution if the game theory can be solved for the "collective no confidence" bargaining game, though.