November 30, 2012

• Asymmetric Julius-Hofstadter equilibrium

  JDN 2456262 EDT 15:06.

   

  I made a mistake in my earlier post in which I proposed the idea of Julius-Hofstadter equilibrium. You can’t actually diagonalize the payoff matrix, at least not for certain games. Even some symmetric games can’t be diagonalized.

  For instance, consider the classic “Chicken” game, which actually I think should be called the “Right-of-Way” game because it only describes “Chicken” if you’re aggressive and irresponsible, whereas it describes the right-of-way at an intersection no matter who you are.

  You arrive at an intersection at the same time as another car on the perpendicular road. You have two options, Go and Stop. If you go and the other driver stops, you’re best off: You get to drive on toward your destination. If you stop and the other driver goes, it’s not too bad: You have to wait for them, but then you’ll be able to go. If you both stop, it’s really annoying; both cars sit there and nobody knows what to do. But if you both go, you’ll collide, ruin everyone’s day, possibly get hurt, and definitely have to pay your insurance deductible.

   

  	G	S
  G	0, 0	10, 4
  S	4, 10	3, 3

   

  There are two Nash equilibria for this game, one in which you go and the other driver stops, and one in which you stop and the other driver goes. It’s to your advantage to make a public commitment to going as soon as possible; that way, you force the other driver to stop. And indeed, this is generally what happens, and even though we’re supposed to have regulations that specify which driver goes first, a lot of people can’t remember them and don’t use them. The ideal solution would be to have road signs or something that remind people of the rules. Because this is a Nash equilibrium, once the rule is specified, everyone has an incentive to obey it. The problem is that the equilibrium isn’t unique, so you have to choose which one somehow.

  This game cannot be diagonalized. If you followed the procedure I outlined in the previous post, you’d get the result that both cars stop. I’ve actually seen this happen at real intersections, because people can’t remember the regulations and no one is bold enough to make the public assertion of commitment. (Usually it’s because I don’t have the right of way but the other person thinks I do. Eventually I just act as if I do, to break the deadlock.)

  Instead, we must redefine the Julius-Hofstadter equilibrium slightly. A superrational agent does not assume that other superrational agents behave the same; they assume that other superrational agents think the same. Not the naive Golden Rule, but Kant’s Categorical Imperative.

  Instead of diagonalizing, they restrict the set of payoffs to Pareto-efficient alternatives. Knowing that both players will do this, they generate the same set, and thereby don’t have to worry about choosing any Pareto-inefficient results (as neoclassically “rational” agents often will).

  In fact, I think we can go further, and say that any Julius-Hofstadter equilibrium must be Strongly Rawls, if I may use that as an adjective. A payoff is Rawls if it maximizes the payoff for the worst-off player. It is Strongly Rawls if it is Rawls and excluding the minimum yields a remaining set that is Rawls, and so on for the entire set. (This is also sometimes called leximin.)

  A Julius-Hofstadter equilibrium is Pareto-efficient and Strongly Rawls. (Actually, Strongly Rawls implies Pareto-efficient.) The basic concept remains the same: A choice is a Julius-Hofstadter equilibrium if all players have no incentive to change multilaterally.

  A Strong Nash Equilibrium is a Julius-Hofstadter equilibrium, but the converse is not true. A Julius-Hofstadter equilibrium always exists, while a Strong Nash Equilibrium typically does not. It’s pretty simple to prove that a Julius-Hofstadter equilibrium always exists in a finite game. First, suppose that there is no Pareto-efficient alternative. Then, for all alternatives x, there must exist some x’ for which all payoffs are at least as high and at least one payoff is greater. This implies that the sum of payoffs in x’ is greater than the sum of payoffs in x. If we rank-order alternatives by the sum of their payoffs, this is a well-ordering since it’s just comparing real numbers. Since every x is Pareto-dominated, we have for all x, there exists x’ > x. But this contradicts the assumption that the game is finite. Therefore, there is at least one Pareto-efficient alternative. Within that set of Pareto-efficient alternatives, make a new well-ordering such that y’ >= y if the minimum payoff of y’ is at least as large as the minimum payoff of y. Again, this is a finite set, so the well-ordering must produce a maximum. That maximum is Rawls, and therefore a Julius-Hofstadter equilibrium.

  In the Right-of-Way game, there are two Rawls alternatives, the same as the Nash equilibria. And indeed, the Julius-Hofstadter equilibria of this game are identical to the Nash equilibria for this game. That’s no accident; in this game, there really are two equally good solutions, corresponding to different right-of-way regulations. “Right goes first” is the usual rule in the US, but “left goes first” would be equally valid; the key is to be consistent and (this is the real problem) universally known. There’s also another problem, which is when two drivers seeking to turn left arrive at the same time from opposite directions on the same road. I actually don’t think we have good regulations for this; I think we should just make something up, like “north and east go first”. Actually, there’s a very good general solution which is in wide use: It’s called a traffic light.

   

  This new definition of the equilibrium can be easily extended to any normal-form game, even asymmetric games. For example, here’s a completely arbitrary game that bears no relation to any real situation I can think of (I’ve bolded the best response for each player):

  	A	B	C
  D	2, 9	1, 7	3, 4
  E	0, 4	5, 1	1, 6
  F	9, 2	4, 3	1, 2

   

  This game has no dominant strategies. In fact, it has no pure Nash equilibria. There’s a mixed Nash equilibrium somewhere, which I know simply because Nash’s Theorem proves that there always is. I have no idea what it is actually, and don’t particularly care to find out.

  Instead, we’ll find the Julius-Hofstadter equilibria. First, we exclude any Pareto-dominated alternatives. 0,4 and 1,2 and 1,6 are all dominated by 1,7. That leaves the following:

   

   

  	A	B	C
  D	2, 9	1, 7	3, 4
  E		5, 1
  F	9, 2	4, 3

   

  Of these Pareto-efficient alternatives, only 4,3 and 3,4 are Rawls.

   

  	A	B	C
  D			3, 4
  E
  F		4, 3

   

  Therefore, there are two Julius-Hofstadter equilibria. Which one should we choose? Well, I don’t know. And it really doesn’t matter, because they are morally equivalent. Indeed, they must be, by definition. If either of the 3s were increased, the other 3 wouldn’t be Rawls anymore. If either the 3 or the 4 were decreased, the result would not be Pareto-efficient anymore. And if the 4 were increased, the other 4 would no longer be Pareto-efficient. The two must be the same, except for being assigned to opposite players.

  This is a general result. A game’s Julius-Hofstadter equilibria are always identical except for a permutation of the players. To see this, consider a game with n players, and two different Julius-Hofstadter equilibria of that game, A and B. By definition, A and B are Strongly Rawls. Order the players by a permutation i -> j such that A_i are in increasing order and B_j are in increasing order as well. We now prove that for i=j, A_i = B_j.

  [I wouldn't include this in a formal paper of course, but pronouncing the previous equation out loud I realized it says, "Artificial Intelligence equals a blowjob." Might want to change that notation later? Of course, that statement has some truth: One of the obvious applications of advanced robotics is sex toys.]

  Because A and B are Rawls, A_1 = B_1.

  Therefore, exclude i=j=1 from consideration and look at i=j=2.

  Because A and B are Strongly Rawls, the set A-A_1 is Rawls and the set B-B_1 is Rawls. Now the smallest element in each is A_2 and B_2, which are maximal, and thus the same.

  Continue until A_n = B_n. Therefore, aside from this permutation of players i -> j, A = B.

  What happens when we get a result like this, where there are two Julius-Hofstadter equilibria that differ by a permutation? We need to select one somehow, as we did for the Right-of-Way game earlier. There really can’t be any moral reason behind that choice, so we choose, in essence, arbitrarily. We must choose however; if both players don’t know what to do, we can end up in an outcome that is not Rawls or one that is even Pareto-inefficient.

  If one group of people is systematically given one player slot and another group is systematically assigned to another, then we may want to alternate in some way, to ensure fairness. But in most circumstances this isn’t a problem–as in the Right-of-Way game, where you’re as likely to be on the right as you are to be on the left. Pick one, stick with it, make sure everyone knows the rule. Is “right goes first” inherently better than “left goes first”? Is “green means go” inherently better than “red means go”? No. But having a consistent rule is better than not having a consistent rule, and all we have to do is ask whether some other rule would be better. (For “right goes first”, the answer is of course “green means go”. But for “green means go”? There might really not be anything better than that.)

  I have thus proved that for any finite game, at least one Julius-Hofstadter equilibrium always exists, and that if multiple equilibria exist, they are all equivalent except for a permutation of the players. This fits on a deep level with superrationality and Kantian morality, which are fundamentally about the idea that permutations of individuals don’t change results.

  Nash equilibrium does have one nice feature that Julius-Hofstadter equilibrium lacks, which is that Nash equilibria are self-enforcing. If you can alter the game so that the Julius-Hofstadter equilibrium is a Nash equilibrium, that’s great; and processes like reciprocity can often make this happen. But Julius-Hofstadter equilibrium has a very major advantage over Nash equilibrium: It is always morally right. That seems fairly important.

  • 4:27 pm
  • 2 Comments