space and games

Last year I introduced cabal equilibria. This post is a summary of my research on cabal equilibria and election methods. Since this is just a short summary, I’m going to skip over any caveats about exact ties in elections.

In any game, a cabal equilibrium is a strategy profile in which no set C of players can simultaneously change strategies in such a way that at least one member of C benefits and no member of C is worse off. Every cabal equilibrium is a Nash equilibrium, but the reverse is not true. For example, in the prisoner’s dilemma, the Nash equilibrium is for both players to defect. This is not a cabal equilibrium, because if both players changed their strategy to cooperate, then both players would benefit. Thus, the prisoner’s dilemma has no cabal equilibria.

The cabal equilibria in elections are particularly interesting, and are related to the notion of a Condorcet winner. In a ranked voting method, a Condorcet winner is a candidate A such that, for any other candidate B, more than half of the voters ranked A higher than B. Of course, the existence and identity of the Condorcet winner (as defined above) depends on how the voters actually vote, not on their true preferences, so for our discussion it’s important to define a pure Condorcet winner as any candidate A such that, for any other candidate B, more than half of the voters actually prefer A to B.

Before I can give my first result, I have to define an election method criterion. An election method is weakly majority-controllable if any majority of voters can cooperate to dictate the outcome of the election, assuming that they already know how the remaining voters are voting. Plurality voting, range voting, all Condorcet voting methods, instant-runoff voting, and the Borda count are all weakly majority-controllable.

My first result is that in any weakly majority-controllable election method, a cabal equilibrium will always elect a pure Condorcet winner.

This is quite easy to see: if an election selects some candidate A who is not a pure Condorcet winner, then there must be some other candidate B whom a majority prefers to A. Since the election is weakly majority-controllable, that majority could change their votes to force B to be elected. That majority has just benefited by changing strategies, so the original election must not have been a cabal equilibrium. Thus any election which does not elect a pure Condorcet winner is not a cabal equilibrium; by contraposition, any cabal equilibrium elects a pure Condorcet winner.

Now let’s define a strongly majority-controllable election method as one in which a majority can control the outcome of the election in which they have to choose their strategies first, even if some members of the majority betray the majority afterwards (as long as it remains a majority). The Borda count is not strongly majority-controllable, but all of the other election methods I mentioned above are.

My second result is that in any strongly majority-controllable election method, the existence of a pure Condorcet winner guarantees the existence of a cabal equilibrium, so this is a partial converse of the first result.

To see this, suppose A is a pure Condorcet winner. Then there is some way that the electorate could vote that guarantees that A will be elected, even if some minority were to change strategies.

Now suppose that there exists a set C of voters that can change their strategies in a way that is beneficial for them. In order for there to be any benefit, the outcome of the election must be changed. No minority of voters has the power to change the outcome, so C must be a majority, and since they consider the change beneficial, none of them may prefer A to the new election outcome. But then A is not a pure Condorcet winner – contradiction.

The Borda count is not strongly majority-controllable, so the existence of a pure Condorcet winner does not guarantee that there is a cabal equilibrium. Here’s an example:

The preferences of the voters are:
5: A > B > C
4: C > B > A
A is the pure Condorcet winner, but the majority cannot simultaneously guard against B and C. For example, if 3 of the majority vote ABC and 2 vote ACB, then the minority can all vote BCA to elect B. Thus there is no cabal equilibrium.

In Hay voting, there are no cabal equilibria except in some degenerate cases. Since every cabal equilibrium is a Nash equilibrium, the only thing that might be a cabal equilibrium is the Nash equilibrium in which each voter votes his or her true preferences. If there exist two players whose utility functions are not scalar multiples of each other, then they can cooperate by each transferring some voting mass between a pair of candidates between which they are relatively indifferent.

Similarly in random ballot, the Nash equilibrium is for each voter to vote for his or her favorite candidate. If there’s a pair of voters who most prefer A and B respectively, but who would choose some compromise C over a coin toss between A and B, then they can cooperate by switching their votes to C.

In both of the above examples, there’s a way for two players can cooperate to get a result that is better than the Nash equilibrium, but now each player has an incentive to betray the other and vote their original choice. This mirrors the Prisoner’s Dilemma, which also has no cabal equilibrium.

I’d like to find an election method where cabal equilibria are likely to exist even with a very large number of candidates, but such a method could not be weakly majority-controllable because the probability of a pure Condorcet winner vanishes as the number of candidates increases (assuming random preferences). This is what I’m thinking about now.

Clearly, it’s absurd that paper beats rock, but if rock beat paper then the game would become pointless.

Suppose we changed the rules such that paper only scores 1/2 point against rock. A full victory (rock against scissors or scissors against paper) scores 1 point, and a loss scores -1 point. Draws score 0 points. What mixed strategy is best in this game?

I found this equilibrium: p(rock) = p(paper) = 2/5, and p(scissors) = 1/5. If the opponent plays this strategy, then anything we do has an expected utility of 0. If both players use this strategy, then neither player has an incentive to change, so it’s an equilibrium.

This result seems strange to me. The rule change makes paper worse, and yet in the resulting equilibrium, we increase the probability of throwing paper. Who wants to explain this?

The germ that infects you was selected for its ability to spread across hosts, but the germ population in your body is being selected for its ability to spread within your body. The latter is more destructive than the former, so the germ population in your body becomes more destructive over time. Thus for any infectious disease, we should expect the period of maximal transmissibility to precede the period of maximal suffering.

Go players have hundreds of proverbs — pithy sentences that convey important heuristics. It is not enough to simply read proverbs; you must study them at length to unfold them into procedural knowledge.

Most proverbs are particular to Go (e.g. six die but eight live), but some generalize to other adversarial situations, and a few proverbs contain important lessons about rationality.

One of my favorite proverbs states that a rich man should not pick quarrels. Go, in its most common formulations, is a game of satisficing. The player with more points wins the game, and winning is enough; there is no extra reward for winning by a large margin. The proverb says that if you are currently winning (i.e. you are a rich man), then you should not do things (such as picking quarrels) that make the outcome more random. By decreasing the variance in the probability distribution for your final score, you increase the probability that you will hold onto enough points to win. Anything that makes the game simpler and more predictable is good for you.

We can see this in Chess (the winning player should seek to trade pieces) and in epee fencing (the winning player should seek double-touches).

If, on the other hand, you are a poor man, then you should pick quarrels. There’s a good example of this in Indiana Jones and the Temple of Doom. In one scene, Indy is in the middle of a rope bridge, and swordsmen are approaching from either side, so Indy cuts the bridge.

If you are winning, simplify. If you are losing, complexify.

Eliezer Yudkowsky₁₉₉₉ famously categorized beliefs about the future into discrete “shock levels.” Michael Anissimov later wrote a nice introduction to future shock levels. Higher shock levels correspond to belief in more powerful and radical technologies, and are considered more correct than lower shock levels. Careful thinking and exposure to ideas will tend to increase one’s shock level.

If this is really true, and I think it is, shock levels are an example of human insanity. If you ask me to estimate some quantity, and track how my estimates change over time, you should expect it to look like a random walk if I’m being rational. Certainly I can’t expect that my estimate will go up in the future. And yet shock levels mostly go up, not down.

I think this is because people model the future with point estimates rather than probability distributions. If, when we try to picture the future, we actually imagine the single outcome which seems most likely, then our extrapolation will include every technology to which we assign a probability above 50%, and none of those that we assign a probability below 50%. Since most possible ideas will fail, an ignorant futurist should assign probabilities well below 50% to most future technologies. So an ignorant futurist’s point estimate of the future will indeed be much less technologically advanced than that of a more knowledgeable futurist.

For example, suppose we are considering four possible future technologies: molecular manufacturing (MM), faster-than-light travel (FTL), psychic powers (psi), and perpetual motion (PM). If we ask how likely these are to be developed in the next 100 years, the ignorant futurist might assign a 20% probability to each. A more knowledgeable futurist might assign a 70% probability to MM, 8% for FTL, and 1% for psi and PM. If we ask them to imagine a plethora of possible futures, their extrapolations might be, on average, equally radical and shocking. But if they instead generate point estimates, the ignorant futurist would round the 20% probabilities down to 0, and say that no new technologies will be invented. The knowledgeable futurist would say that we’ll have MM, but no FTL, psi, or PM. And then we call the ignorant person “shock level 0″ and the knowledgeable person “shock level 3.”

So future shock levels exist because people imagine a single future instead of a plethora of futures. If futurists imagined a plethora of futures, then ignorant futurists would assign a low probability to many possible technologies, but would also assign a relatively high probability to many impossible technologies, and there would be no simple relationship between a futurist’s knowledge level and his or her expectation of the overall amount of technology that will exist in the future, although more knowledgeable futurists would be able to predict which specific technologies will exist. Shock levels would disappear.

I do think that shock level 4 is an exception. SL4 has to do with the shocking implications of a single powerful technology (superhuman intelligence), rather than a sum of many technologies.

In light of my previous post, I’d like to suggest a vote-matching scheme. Let’s start with an example:

Suppose there’s a presidential election between Kodos, Kang, and Washington. Kodos and Kang seem to be the leading candidates.

Alf and Beth are trying to decide who to vote for. They both like Washington, but they don’t want to waste their votes. Alf thinks Kodos is the “lesser of two evils,” while Beth prefers Kang.

If Alf votes for Kodos and Beth votes for Kang, as they are inclined to do, then their two votes will “cancel out,” at least in the race between Kodos and Kang. This means that if they both agree to switch their votes to Washington, the balance of votes between Kodos and Kang will not change. Washington gets two extra votes!

This sort of vote-matching should be able to benefit some third-party candidates in real life, too. The key requirement is that voters who prefer the third-party candidate disagree about which of the two front-runners is worse. In that case, two voters can promise to vote for the third-party candidate instead of their “lesser of two evils.” If this sort of vote-matching scheme took off, I think we could see a big change in politics.

If you think that Condorcet voting would be a good thing, then you should also be in favor of voter collusion, such as Nader Trading, or political analogues of Facebook groups like “Once we reach 4,096 members, everyone will donate $256 to SingInst.org” or “1 million people, $100 million to defeat aging.” When groups can collectively change strategies to benefit group members, the global situation will start to look like a cabal equilibrium, and cabal equilibria in plurality or approval votes always elect a Condorcet winner. Of course, this only works to the extent that people follow through on their promises.

The other day, I was reading a wikipedia article related to a topic we had been discussing in one of my classes. One of the statements in the second section confused me, and after a bit of thought I was convinced that it was indeed a mistake. Looking at the history, I noticed that this mistake was the result of an edit that had been made the day before.

Naturally, I reverted the article to the previous version. Looking at the history again, I noticed that the mistake had come from someone with an IP address very similar to my own. A quick search revealed that this person was in Philadelphia.

I decided that I was about 60% sure that it was someone in my class. Immediately I singled out a single person with 30% confidence.

There are about 1.5 million people in Philadelphia. There are about 15 people in my class. It would take a likelihood ratio of about 100,000 to pick out my class, and a likelihood ratio of about 1.5 million to pick out one person.

In class the next day, when I asked if anyone had edited wikipedia recently, they all said no.

And that’s how I lost 1.3 bits from my Bayes score.

This summer, I was involved in a summer research program at the Singularity Institute. Here we are:

While I was there, I wrote a follow-up to my old Expected Utility paper. The new paper says basically the same thing as the old paper, but for repeated decisions rather than one-off decisions.

Roko Mijic and I have also started a paper about the problem of generalizing utility functions to new models – the sort of problem I call an “ontological crisis.” These situations arise for humans when we discover that the goals and values which we ascribe to ourselves do not correspond to objects in reality. Obvious examples include god, souls, and free will, but we’re just as interested in how AIs can deal with more mundane problems such as generalizing the notion of “temperature” from a classical to a quantum model. Unfortunately, we didn’t have time to finish the paper this summer, but you can expect to see it soon.

Towards the end of the summer, I made a few resolutions for the new year (as a grad student, my year starts in late August). In particular, I’ve resolved to write a popular blog. In the short term this will mean reducing the quality of my posts in exchange for much greater quantity, but in the long term I expect quality to rise again as I gain more experience writing. I’ll probably write about some of my less serious projects, such as the computer game I’ve been developing on and off for the past year.

In other news, the Singularity Summit will be in New York this year, on October 3-4. Anyone who wants to chat me up can do so at the summit, if you can find me among the horde of attendees. See you there!

In game theory, a Nash equilibrium is an assignment of strategies to players, such that no player can benefit from changing vis own strategy (assuming the other players’ strategies remain the same). For example, in the one-shot Prisoner’s Dilemma, mutual defection is the only Nash equilibrium. There are several other ideas for how to define an “equilibrium” of a game, many of which are “refinements” of Nash Equilibrium, in the sense that the set of equilibria is smaller.

Here’s another one: a “cabal equilibrium” is an assignment of strategies to players, such that no subset (or “cabal”) K of players can simultaneously change strategies in such a way that some players in K benefit and no players in K are worse off. In other words, each cabal of players is playing a strategy which is Pareto optimal for the players within that cabal. Note that any subset of players is considered a cabal, so if there are N players, then there are 2^N cabals.

Any cabal equilibrium is also a Nash equilibrium. A single player is just a cabal of size one, so if no cabal of players wishes to change strategies, then single no player wishes to change strategy. So this definition of equilibrium is “stronger” than the Nash equilibrium, in the sense that it is a more stringent test.

For example, the Prisoner’s Dilemma has no cabal equilibrium. First observe that mutual defection is the only Nash equilibrium, so there is at most one cabal equilibrium. But mutual defection is not an cabal equilibrium, because both players would prefer to simultaneously switch their strategy to cooperation.

Stag hunt has two Nash equilibria but only one cabal equilibrium. Battle of the Sexes has two Nash equilibria, both of which are cabal equilibria.

Mike Dobbins and I talked about cabal equilibria in voting. Because the outcome of an election depends on the voters in such a coarse way, the Nash equilibrium does not seem like a strong enough definition to apply to voting situations. For example, any election in which the winner beats the first loser by more than one vote is a Nash equilibrium, because no single voter can change the outcome by changing vis strategy. So not only are there multiple Nash equilibria, but in fact almost any election is a Nash equilibrium.

So let’s consider cabal equilibria in a plurality or approval vote. Suppose there is an equilibrium, and this equilibrium elects candidate A.

Suppose that more than half of the voters preferred B over A. Then they could all vote for B (and disapprove of A in an approval vote), resulting in a better outcome from their point of view. Then the original election was not a cabal equilibrium: contradiction! So there is no candidate that is preferred over A by a majority.

So if we ignore the possibility that exactly half the voters prefer some other candidate over A, this would mean that A is a Condorcet winner!

Now let’s consider the converse. Suppose that there is no cabal equilibrium. Then, in particular, it is not a cabal equilibrium for everyone to vote for the same candidate A. Then there exists some cabal K of voters which could make a Pareto improvement by changing votes. In order for the new strategy to be a Pareto improvement, it must affect the outcome of the election somehow; thus it must cause some other candidate B to be elected instead of A. In order to change the outcome of the election, we must have changed at least half of the votes (since originally everyone was voting for A), so K must contain at least half of the voters. Since no member of K prefers B over A, we know A is not preferred over B by a majority, and thus is not a Condorcet winner.

So if there is no cabal equilibrium, then A is not a Condorcet winner. Since the same argument works for any other candidate (not just candidate A), this means that no cabal equilibrium implies no Condorcet winner. Taking the contrapositive, this means that in an election with a Condorcet winner, there is a cabal equilibrium!

So we’ve just proven a theorem: A plurality or approval vote with an odd number of voters has a cabal equilibrium iff there is a Condorcet winner, and a cabal equilibrium always elects the Condorcet winner.