Game Theory (Part 5)

23 January, 2013

Here are a bunch of puzzles about game theory, to see if you understand the material so far.

Classifying games

For each of the following games, say whether it is:

a) a single-player, 2-player or multi-player game

b) a simultaneous or sequential game

c) a zero-sum or nonzero-sum game

d) a symmetric or nonsymmetric game

e) a cooperative or noncooperative game

If it can be either one, or it is hard to decide, explain why! You will probably not know all these games. So, look them up on Wikipedia if you need to:

1) chess

2) poker

3) baseball

4) rock-paper-scissors

5) rock-paper-scissors-lizard-Spock

6) Prisoner’s Dilemma


    

7) solitaire with cards (also known as “patience”)

8) the ultimatum game

9) guess 2/3 of the average

10) Nim

Battle of the Sexes

Suppose that Alice and Bob are going to the movies. Alice wants to see the movie This is 40 while Bob wants to see Zero Dark Thirty. Let’s say Alice and Bob each have two strategies:

1. Watch the movie they really want to see.
2. Watch the movie the other one wants to see.

If they both watch the movie they really want, each goes out alone and gets a payoff of 5. If they both watch the movie the other wants to see, they again go out alone and now each gets a payoff of -5, because they’re both really bored as well as lonely. Finally, suppose one watches the movie they want while the other kindly watches the movie their partner wants. Then they go out together. The one who gets to see the movie they want gets a payoff of 10, while the one who doesn’t gets a payoff of 7. (They may not like the movie, but they get ‘points’ for being a good partner!)

Call Alice A for short, and call Bob B. Write down this game in normal form.

Prisoner’s Dilemma

Now suppose Alice and Bob have been arrested because they’re suspected of having conspired to commit a serious crime: an armed robbery of the movie theater!

They are interrogated in separate rooms. The detectives explain to each of them that they are looking at 3 years of jail even if neither of them confess. If one confesses and the other denies having committed the crime, the one who confesses will get only 1 year of jail, while the one who denies it will get 25 years. If they both confess, they will both get 10 years of jail.

Suppose the two strategies available to both of them are:

1. confess to the crime.
2. deny having done it.

Write down this game in normal form, where n years of jail time counts as a payoff of -n.

Game theory concepts

Now, for both the Battle of the Sexes and Prisoner’s Dilemma games, answer these questions:

a) Is this a zero-sum game?

b) Is this a symmetric game?

c) Does player A have a strictly dominant pure strategy? If so, which one?

d) Does player B have a strictly dominant pure strategy? If so, which one?

e) Does this game have one or more Nash equilibria? If so, what are they?

Zero-sum and symmetric games

For the next two problems, suppose we have a game in normal form described by two m \times n matrices A and B. Remember from Part 2 of our course notes that if player A chooses strategy i and player B chooses strategy j, A_{ij} is the payoff to player A and B_{ij} is the payoff to player B.

a) What conditions on the matrices A and B say that this game is a zero-sum game?

b) What conditions on the matrices A and B say that the game is symmetric?


Game Theory (Part 4)

18 January, 2013

Last time we talked about Nash equilibria for a 2-player normal form game. We saw that sometimes a Nash equilibrium doesn’t exist! Sometimes there’s more than one! But suppose there is at least one Nash equilibrium. How do we find one? Sometimes it’s hard.

Strict domination

But there’s a simple trick to rule out some possibilities. Sometimes player A will have a choice i that gives them a bigger payoff than some choice i' no matter what choice player B makes. In this case we say choice i strictly dominates choice i'. And in this case, there’s no way that i' could be A’s choice in a Nash equilibrium, because player A can always improve their payoff by switching to choice i.

For example, look at this game:

1 2
1    (0,0)   (-1,1)  
2 (2,-1)   (0,0)  
3 (-2,1)   (1,-1)  
4 (0,1)   (2,0)  

For player A, choice 4 strictly dominates choice 3. No matter what player B does, player A gets a bigger payoff if they make choice 4 than if they make choice 3. Stare at the black numbers in the table in rows 3 and 4 until you see this.

You can also see it using the payoff matrix for player A:

A = \left( \begin{array}{rr} 0 & -1 \\ 2 & 0 \\ -2 & 1 \\ 0 & 2 \end{array} \right)

Each number in row 4 here is bigger than the number directly above it in row 3. In other words:

0 = A_{41} > A_{31} = -2

and

2 = A_{42} > A_{32} = 0

Puzzle. Are there any other examples of a choice for player A that strictly dominates another choice?

And of course the same sort of thing works for player B. If player B has a choice j that gives them a better payoff than some choice j' no matter what player A does, then j' can’t show up as B’s choice in a Nash equilibrium.

We can make our remarks more precise:

Definition. A choice i for player A strictly dominates a choice i' if

A_{ij} > A_{i'j}

for all j. Similarly, a choice j for player B strictly dominates a choice j' if

B_{ij} > B_{ij'}

for all i'.

Theorem 1. If a choice i for player A strictly dominates a choice i', then no choice j for player B gives a Nash equilibrium (i',j). Similarly, if a choice j for player B strictly dominates a choice j', then no choice i for player A gives a Nash equilibrium (i,j').

Proof. We’ll only prove the first statement since the second one works the exact same way. Suppose i strictly dominates i'. This means that

A_{i j} > A_{i' j}

for all j. In this case, there is no way that the choice i' can be part of a Nash equilibrium. After all, if (i',j) is a Nash equilibrium we have

A_{i' j} \ge  A_{i'' j}

for all i''. But this contradicts the previous inequality—just take i'' = i.

Strict dominance

Definition. We say a choice is strictly dominant if it strictly dominates all other choices for that player.

Let me remind you again that a pure strategy is a way for one player to play a game where they always make the same choice. So, there is one pure strategy for each choice, and one choice for each pure strategy. This means we can be a bit relaxed about the difference between these words. So, what we’re calling strictly dominant choices, most people call strictly dominant pure strategies. You can read more about these ideas here:

Strategic dominance, Wikipedia.

We’ve seen that if one choice strictly dominates another, that other choice can’t be part of a Nash equilibrium. So if one choices strictly dominates all others, that choice is the only one that can be part of a Nash equilibrium! In other words:

Theorem 2. If a choice i for player A is strictly dominant, then any Nash equilibrium (i',j') must have i' = i. Similarly, if a choice j for player B is strictly dominant, then any Nash equilibrium (i',j') must have j' = j.

Proof. We’ll only prove the first statement since the second one works the exact same way. Theorem 1 says that if a choice i for player A strictly dominates a choice i', then no choice j for player B gives a Nash equilibrium (i',j). So, if i strictly dominates all other choices for player A, it is impossible to have a Nash equilibrium (i',j) unless i' = i.

We can go even further:

Theorem 3. If choice i for player A is strictly dominant and choice j for player B is strictly dominant, then (i, j) is a Nash equilibrium, and there is no other Nash equilibrium.

Proof. Suppose choice i for player A is strictly dominant and choice j for player B is strictly dominant. Then by Theorem 2 any Nash equilibrium (i',j') must have i' = i and j' = j. So, there is certainly no Nash equilibrium other than (i, j).

But we still need to check that (i, j) is a Nash equilibrium! This means we need to check that:

1) For all 1 \le i' \le m, A_{i'j} \le A_{ij}.

2) For all 1 \le j' \le m, B_{ij'} \le B_{ij}.

Part 1) is true because choice i is strictly dominant. Part 2) is true because choice j is strictly dominant. █

We can restate Theorem 3 is a less precise but rather pretty way:

Corollary. If both players have a strictly dominant pure strategy, there exists a unique Nash equilibrium.

Here I’m saying ‘pure strategy’ instead of ‘choice’ just to prepare you for people who talk that way!

Domination

I realize that the terminology here has a kind of S&M flavor to it, with all this talk of ‘strict domination’ and the like. But there’s nothing I can do about that—it’s standard!

Anyway, there’s also a less strict kind of dominance:

Definition. A choice i for player A dominates a choice i' if

A_{ij} \ge A_{i'j}

for all j. Similarly, a choice j for player B dominates a choice j' if

B_{ij} \ge B_{ij'}

for all i.

But there is less we can do with this definition. Why? Here’s why:

Puzzle. Find a normal-form two player game with 2 choices for each player, where (i,j) is a Nash equilibrium even though i is dominated by the other choice for player A and j is dominated by the other choice for player B.


Game Theory (Part 3)

17 January, 2013

Last time we started looking at 2-player normal form games. The idea is that player A has m different choices of which move to make, while player B has n choices, and we have two m \times n matrices of payoffs, A and B. If player A makes choice i and player B makes choice j, then the payoff to player A is A_{i j}, while the payoff to player B is B_{i j}.

What should you do if you’re playing a game like this? As we saw when playing rock-paper-scissors, sometimes the best thing is to adopt a strategy with some built-in randomness. In this game, if your opponent knows what you’re going to do, he can exploit that and beat you!

A strategy involving randomness is called a mixed strategy. They’re very important, and we’ll talk about them a lot. But today we’ll only consider pure strategies, where we definitely choose one of the choices available, with no randomness.

Notice: there are as many pure strategies as there are choices! For each choice, there’s a pure strategy where you always make that choice when playing the game. So, a lot of people say ‘pure strategy’ for what I call a ‘choice’. Other people use the word ‘action’.

Anyway: let’s try to figure out the best pure strategy for each player, if we can.

Sometimes this is impossible. For example, rock-paper-scissors has no best pure strategy. Could playing rock be best? No, because paper beats rock. Could playing paper be best? No, because scissors beats paper. Could playing scissors be best? No, because rock beats scissors.

But sometimes we can find a best pure strategy, and the ideas we meet will help us later when we study mixed strategies. So, let’s dive in!

Nash equilibria

Suppose player A makes choice i and player B makes choice j. Then we say (i,j) is a Nash equilibrium if neither player can improve their payoff by changing their choice.

For example, look at this game:

1 2
1    (10,10)   (9,-1)
2 (-1,1) (-1,-1)

Here we are writing the matrices A and B together in one table, like last time, with A in black and B in red. But we could also separate them out:

A = \left( \begin{array}{rr} 10 & 9 \\ -1 & -1 \end{array} \right) , \qquad B = \left( \begin{array}{rr} 10 & -1 \\ 1 & -1 \end{array} \right)

It’s just a different way of conveying the same information.

Either way, it’s pretty clear what the players should do in this game! Both players should make choice 1. That way, they both win 10 points.

Furthermore, this pair of choices (i,j) = (1,1) is certainly a Nash equilibrium. In other words: neither player can improve their payoff by unilaterally changing their choice! If player A switches to choice 2, their payoff drops to -1 points. If player B switches to choice 2, their payoff drops to 9 points.

Let’s give an official definition of Nash equilibrium and then look at some trickier examples. Remember, player A’s choices are i = 1, 2, \dots , m, while player B’s choices are j = 1, 2, \dots, n.

Definition. Given a 2-player normal form game, a pair of choices (i,j) is a Nash equilibrium if:

1) For all 1 \le i' \le m, A_{i'j} \le A_{ij}.

2) For all 1 \le j' \le n, B_{ij'} \le B_{ij}.

Condition 1) says that player A can’t improve their payoff by switching their choice from i to any other choice i'. Condition 2) says that player B can’t improve their payoff by switching their choice from j to any other choice j'.

Examples

Let’s look at more examples of Nash equilibria, to see some funny things that can happen. First let’s modify the last game a little:

1 2
1    (10,10)   (-1,10)
2 (10,-1) (-1,-1)

Is there a Nash equilibrium? Yes—and just as before, it happens when both players pick pure strategy 1. Now player A’s payoff doesn’t get any worse when they switch to pure strategy 2. But it doesn’t improve, either! It stays equal to 10. Similarly, player B’s payoff doesn’t get any worse when they switch to pure strategy 2… but it doesn’t improve. So, neither player is motivated to change their strategy.

I said a Nash equilibrium is a situation where neither player can improve their payoff by changing their choice. But it might be clearer to say: neither player can improve their payoff by unilaterally changing their choice.

What do I mean by ‘unilaterally’ changing their choice? I mean that one player changes their choice while the other player does not change their choice.

But if both players change their choices simultaneously, sometimes they can improve both their payoffs! Lets see an example of that:

1 2
1    (10,10)   (9,-1)
2 (-1,8) (20,20)

Now it looks like both players will be happiest if they pick pure strategy 2. And it’s true! Moreover, this is a Nash equilibrium. Check and see.

But what if both players pick choice 1? This is also a Nash equilibrium! Shocking but true. If they both use pure strategy 1, neither player can improve their payoff by unilaterally changing their choice. If player A changes her choice, her payoff drops to -1. And if player B changes his choice, his payoff drops to -1.

Of course, they can improve their payoff if they both simultaneously change their choice to 2. But that’s not what the concept of Nash equilibrium is about.

This raises the question of whether Nash equilibrium is a good definition of ‘the best’ choice for each player. The big problem is figuring out what ‘best’ means—we’ll have to talk about that more. But we’re also seeing some problems with the word ‘the’. There may be more than one Nash equilibrium, so we can’t always talk about ‘the’ Nash equilibrium.

In other words, our example shows there isn’t always a unique Nash equilibrium.

Furthermore, a Nash equilibrium doesn’t always exist! Check out the game of rock-paper-scissors:

rock paper scissors
rock    (0,0)   (-1,1)   (1,-1)  
paper     (1,-1)   (0,0)   (-1,1)  
scissors     (-1,1)   (1,-1)   (0,0)  

It’s easy to see that there’s no Nash equilibrium. No matter what both players choose, at least one of them can always improve their payoff by switching to a different choice. If one of them wins the game, the loser can improve their payoff by switching to a different choice. If it’s a tie, either player can improve their payoff by switching to a different choice.

So: Nash equilibria are interesting, but they don’t always exist— at least not when we consider only pure strategies, as we’ve been doing. And even when they do, they’re not always unique! This is a bit frustrating. We’d like game theory to tell us how to play games well.

We can improve the situation by allowing mixed strategies, where a player picks different choices with different probabilities. If we do this, there is always at least one Nash equilibrium! This result was proved by—you guessed it!—John Nash. He did it in 1950, in this astoundingly short paper:

• John F. Nash, Jr., Equilibrium points in n-person games, Proceedings of the National Academy of Sciences 36 (1950), 48–9.

He eventually won the Nobel prize in economics for this work.

In fact, Nash was not the first to think about Nash equilibria; this idea goes back to the French economist Antoine Cournot, who wrote about it way back in 1838! However, Nash was the first to consider Nash equilibria for mixed strategies for general simultaneous multi-player games, and prove they always exist. (As we’ll see later, von Neumann and Morgenstern had already done this for the zero-sum 2-player games.)

John Nash

If you haven’t seen the movie about Nash called A Beautiful Mind, you should! Here’s the scene where Nash figures out something about multiplayer games:

It’s not very clear, mathematically speaking… but oh well. It’s a good movie and it gives you some sense of how Nash battled with mental illness for much of his life. He has now largely recovered and spends his time at Princeton University.

Here’s the young Nash—click for more details:


A ‘practical’ question

A student in my class asked what’s the best book or website on how to play blackjack well. I asked this on Google+ and got over 50 replies, which you can read here. If you know more, please tell me!


Network Theory for Economists

15 January, 2013

Tomorrow I’m giving a talk in the econometrics seminar at U.C. Riverside. I was invited to speak on my work on network theory, so I don’t feel too bad about the fact that I’ll be saying only a little about economics and practically nothing about econometrics. Still, I’ve tried to slant the talk in a way that emphasizes possible applications to economics and game theory. Here are the slides:

Network Theory.

For long-time readers here the fun comes near the end. I explain how reaction networks can be used to describe evolutionary games. I point out that in certain classes of evolutionary games, evolution tends to increase ‘fitness’, and/or lead the players to a ‘Nash equilibrium’. For precise theorems you’ll have to click the links in my talk and read the references!

I conclude with an example: a game with three strategies and 7 Nash equilibria. Here evolution makes the proportion of these three strategies follow these flow lines, at least in the limit of large numbers of players:

This picture is from William Sandholm’s nice expository paper:

• William H. Sandholm, Evolutionary game theory, 2007.

I mentioned it before in Information Geometry (Part 12), en route to showing a proof that some quantity always decreases in a class of evolutionary games. Sometime I want to tell the whole story linking:

reaction networks
evolutionary games
the 2nd law of thermodynamics

and

Fisher’s fundamental theorem of natural selection.

But not today! Think of these talk slides as a little appetizer.


Game Theory (Part 2)

13 January, 2013

Last time we classified games in a few ways. This time we’ll start by looking at a very simple class of games: simultaneous noncooperative two-player games.

Simultaneous games

Remember that in a simultaneous game, each player makes their moves without knowing anything about the other player’s move. Thanks to this, we can condense each player’s move into a single move. For example, in a card game, if one player lays down a king and then an ace, we can mathematically treat this as a single move, called “lay down a king and then an ace”. So, we’ll say each player makes just one move—and they make it without knowing the other player’s move.

In class we’ll play these games like this. I will decide on my move and write it down on a piece of paper. You’ll make your move and click either A,B,C,D, or E on your clicker.

Then I’ll reveal my piece of paper! At that point, we’ll each know what both of us did… but neither of us can change our move.

So, we each make our move without knowing each other’s move.

Two-player games

Since lots of you will be clicking your clicker at once, you could say there are more than two players in this game. But your payoff—the number of points you win or lose—will depend only on what you did and what I did. So, we can treat this game as a bunch of independent two-player games—and that’s what we’ll do.

Noncooperative games

Remember, we use words in funny ways in mathematics! An ‘imaginary’ number is not imaginary in the usual sense; a ‘partial’ differential equation isn’t just part of a differential equation, and so on. In game theory we use the word ‘noncooperative’ in a funny way. We say a game is noncooperative if the players aren’t able to form binding commitments. This means that when we play our games, you and I can’t talk before the game and promise to do certain things.

There will, however, be games where both of us win if we make the right choice, and both of us lose if we don’t! In games like this, if we can figure out how to cooperate without communicating ahead of time and making promises, that’s allowed!

Chicken

Now let’s actually look at an example: the game of chicken. In this game we drive toward each other at high speed along a one-lane road in the desert. The one who swerves off the road at the last minute gets called a chicken, and the other driver gets called a hero. If we both swerve off the road at the last minute, we’re both called chickens. But if neither of us does, our cars crash and we both die!

Sounds fun, eh?

In real life we could each wait as long as possible and see if the other driver starts to swerve. This makes chicken into a sequential rather than simultaneous game! You could also promise that you wouldn’t swerve. This makes chicken into a cooperative game!

Indeed there are all sorts of variations and complications in real life. You can see some in the famous movie Rebel Without a Cause, starring James Dean. Take a look at what happens:

This movie version actually involves driving toward a cliff and jumping out at the last possible moment.

But mathematics, as usual, is about finding problems that are simple enough to state precisely. So in our simple mathematical version of chicken, we’ll say each player has just two choices:

1: stay on the road.
2: swerve off the road at the last second.

Also, we’ll express our payoffs in terms of numbers. A negative payoff is bad, a positive one is good:

• If either player swerves off the road they get called a chicken, which is bad, so let’s say they get -1 points.

• If one player stays on the road and other swerves off the road, the one who stays on the road gets called a hero, so let’s say they get 1 point.

• If both players stay on the road they both die, so let’s say they both get -10 points.

We can summarize all this in a little table:

1 2
1    (-10,-10)   (1,-1)
2 (-1,1) (-1,-1)

Let’s say the players are you and me. Your choices 1 and 2 are shown in in black: you get to pick which row of the table we use. My choices 1 and 2 are in red: I get to pick which column of the table we use.

There are four possible ways we can play the game. For each of the four possibilities we get a pair of numbers. The first number, in black, is your payoff. The second, in red, is my payoff.

For example, suppose you choose 1 and I choose 2. Then you’re a hero and I’m a chicken. So, your payoff is 1 and mine is -1. That’s why we get the pair of numbers (1,-1) in the 1st row and 2nd column of this table.

Now let’s play this game a bit! Later we’ll study it in different ways.

Rock-paper-scissors

Here’s another famous game: rock-paper-scissors.

Each player can choose either rock, paper or scissors. Paper beats rock, scissors beats paper, and rock beats scissors. In these cases let’s say the winner gets a payoff of 1, while the loser gets a payoff of -1. If both players make the same choice, it’s a tie, so let’s say both players get a payoff of 0.

Here’s a table that describes this game:

rock paper scissors
rock    (0,0)   (-1,1)   (1,-1)  
paper     (1,-1)   (0,0)   (-1,1)  
scissors     (-1,1)   (1,-1)   (0,0)  

Your choices and payoffs are in black, while mine are in red.

For example, if you choose rock and I choose paper, we can look up what happens, and it’s (-1,1). That means your payoff is -1 while mine is 1. So I win!

To make this table look more mathematical, we can make up numbers for our choices:

1: rock
2: paper
3: scissors

Then the table looks like this:

1 2 3
1    (0,0)   (-1,1)   (1,-1)  
2 (1,-1)   (0,0)   (-1,1)  
3 (-1,1)   (1,-1)   (0,0)  

Let’s play this game a bit, and then discuss it!

Normal form

In the games we’re studying now, each player can make various choices. In game theory these choices are often called pure strategies. We’ll see why later on in this course.

In our examples so far, each player has the same set of pure strategies. But this is not required! You could have some set of pure strategies and I could have some other set.

For now let’s only think about games where we both have a finite set of pure strategies. For example, you could have 4 pure strategies and I could have 2. Then we could have a game like this:

1 2
1    (0,0)   (-1,1)  
2 (2,-1)   (0,0)  
3 (-2,1)   (1,-1)  
4 (0,1)   (2,0)  

This way of describing a game using a table of pairs of numbers is called normal form, and you can read about it here:

Normal-form game, Wikipedia.

There are other ways to describe the same information. For example, instead of writing

1 2
1    (0,0)   (-1,1)  
2 (2,-1)   (0,0)  
3 (-2,1)   (1,-1)  
4 (0,1)   (2,0)  

we can write everything in black:

1 2
1    (0,0)   (-1,1)  
2 (2,-1)   (0,0)  
3 (-2,1)   (1,-1)  
4 (0,1)   (2,0)  

All the information is still there! It’s just a bit harder to see. The colors are just to make it easier on you.

Mathematicians like matrices, which are rectangular boxes of numbers. So, it’s good to use these to describe normal-form games. To do this we take our table and chop it into two. We write one matrix for your payoffs:

A = \left( \begin{array}{rr} 0 & -1 \\ 2 & 0 \\ -2 & 1 \\ 0 & 2 \end{array} \right)

and one for mine:

B = \left( \begin{array}{rr} 0 & 1 \\ -1 & 0 \\ 1 & -1 \\ 1 & 0 \end{array} \right)

The number in the ith row and jth column of the matrix A is called A_{i j}, and similarly for B. For example, if you pick choice 3 in this game and I pick choice 2, your payoff is

A_{32} = 1

and my payoff is

B_{32} = -1

Definition

Let’s summarize everything we’ve learned today! Remember, an m \times n matrix has m rows and n columns. So, we can say:

Definition. A 2-player normal-form game consists of two m \times n matrices of real numbers, A and B.

This definition is very terse and abstract. That’s what mathematicians like! But we have to unfold it a bit to understand it.

Let’s call you ‘player A’ and me ‘player B’. Then the idea here is that player A can choose among pure strategies i = 1,2,\dots , m while player B can choose among pure strategies j = 1,2,\dots, n. Suppose player A makes choice i and player B makes choice j. Then the payoff to player A is A_{i j}, and the payoff to player B is B_{i j}.


Game Theory (Part 1)

6 January, 2013

I’m teaching an undergraduate course on game theory and I thought I’d try writing my course notes on this blog. I invite students (and everyone else in the universe) to ask questions, correct my mistakes, add useful extra information and references, and so on.

However, I should warn the geniuses who usually read this blog that these notes will not be filled with deep insights: it’s just a introductory course and it’s the first time I’ve taught it.

I should also warn the students in my class that these notes are not a substitute for taking notes in class! I’ll tell you a lot of other stuff in class!

Let’s get started.

Examples of games

Mathematicians use words differently from normal people. When you hear the word ‘game’ you probably think about examples like:

• board games like checkers, chess, go, Scrabble, Monopoly, Risk and so on.

• card games like solitaire, poker, bridge, blackjack, and so on.

• sports involving athletic skill like football, basketball, baseball, hockey, tennis, squash, golf, croquet, horseshoes and so on.

• video games and computer games—I’m too much of an old fogey to even bother trying to list some currently popular ones.

• game shows on TV—ditto, though Jeopardy is still on the air.

• role-playing games—ditto, though some people still play Dungeons and Dragons.

• ‘war games’ used by armies to prepare for wars.

Game theory is relevant to all these games, but more generally to any situation where one or more players interact, each one trying to achieve their own goal. The players can be people but they don’t need to be: they can also be animals or even other organisms! So, game theory is also used to study

• biology

• economics

• politics

• sociology

• psychology

For example, here is a ‘game’ I often play with my students. Some students want to get a passing grade while coming to class as little as possible. I want to make them come to every class. But, I want to spend as little time on this task as possible.

What should I do? I don’t want to take attendance every day, because that takes a lot of time in a big class. I give quizzes on random days and make it hard for students to pass unless they take most of these quizzes. I only need to give a few quizzes, but the students need to come to every class, since they don’t know when a quiz will happen.

How do the students respond? Lots of them come to class every time. But some try to ‘bend the rules’ of the game, mainly trying to get my sympathy. They invent clever excuses for why they missed the quizzes: dying grandmothers, etc. They try to persuade me to ‘drop the lowest quiz score’. They try to convince me that it’s unreasonable to make quizzes count for so much of the grade. After all, it’s easy to get a bad score on a quiz, when there’s not much time to answer a question about something you just learned recently.

How do I respond? Only the last idea moves me. So, I set things up so missing a quiz gives you a much worse score than taking the quiz and getting it completely wrong. In fact, just to dramatize this, I give students a negative score if they miss a quiz.

How the students respond? Some of them argue that it’s somehow evil to give people negative scores. But at this point I bare my fangs, smile, and nod, and the game ends.

It’s important to emphasize that other students have different goals: some want to come to class every time and learn as much as possible! In this case my goals and the students’ goals don’t conflict very much. As we’ll see, in mathematical game theory there are plenty of games where the players cooperate as well as compete… or even just cooperate.

Mathematical game theory tends to focus on games where the most important aspect of the game is choosing among different strategies. Games where the most important aspect is physical ability are harder to analyze using mathematics. So are games where it’s possible to ‘bend the rules’ in a huge number of different ways.

Game theory works best when we can:

• list the set of choices each player can make,

• clearly describe what happens when each player makes a given choice.

• clearly describe the ‘payoff’ or ‘winnings’ for each player, which will of course depend on the choices all the players make.

Classifying games

We can classify games in many different ways. For example:

The number of players. There are single-player games (like solitaire), two-player games (like chess or ‘rock, paper, scissors’), and multi-player games (like poker or Monopoly).

Simultaneous versus sequential games. There are games where all players make their decisions simultaneously, or if they do not move simultaneously, the later players are unaware of the earlier players’ actions, making them effectively simultaneous. These are called simultaneous games. There are also games
where some players make decisions after knowing something about what other players have decided. These are called sequential games.

The games people play for fun are very often sequential, but a surprisingly large part of the game theory we’ll discuss in class focuses on simultaneous games. ‘Rock, paper, scissors’ is an example of a simultaneous game, but we’ll see many more.

Zero-sum versus nonzero-sum games. A zero-sum game is one where the total payoff to all the players is zero. Thus, any player benefits only at the expense of others.

An example of a zero-sum game is poker, because each player wins exactly the total amount their opponents lose (ignoring the possibility of the house’s cut). Chess, or any other two-player game with one winner and one loser, can also be seen as a zero-sum game: just say the winner wins $1 and the loser loses $1.

In nonzero-sum games, the total payoff to all players is not necessarily zero. An example is ‘chicken’, the game where two people drive their cars at each other, and both cars crash if neither pulls off the road. When this happens, both players lose. There are also games where both players can win.

In two-person zero-sum games, the players have no reason to cooperate, because whatever one wins, the other loses. In two-person nonzero-sum games, cooperation can be important.

Symmetric and non-symmetric games. In a symmetric game the same rules apply to each player. More precisely, each player has the same set of strategies to choose from, and the payoffs to each player are symmetrical when we interchange which player chooses which strategy.

In a non-symmetric game, this is not the case. For example, we can imagine a non-symmetric version of poker where my hand always contains at least two aces, while no other player’s does. This game is ‘unfair’, so people don’t play it for fun. But games in everyday life, like the teacher-student game I mentioned, are often non-symmetric, and not always fun.

Cooperative and non-cooperative games. A game is cooperative if the players are able to form binding commitments. That is, some players can promise to each that they will choose certain strategies, and these promises must be kept. In noncooperative games there is no way to make sure promises are kept.

Our legal system has the concept of a ‘contract’, which is a way people can make binding commitments.

Warning

There’s a lot more to say about these ways of classifying games. There are also other ways of classifying games that we haven’t discussed here. But you can already begin to classify games you know. Give it a try! You’ll run into some interesting puzzles.

For example, chess is a two-person zero-sum sequential non-cooperative game.

Is it symmetric? The strategies available to the first player, white, are different from those available to the second player, black. This is true of almost any sequential game where the players take turns moving. So, we can say it’s not symmetric.

Or, we can imagine that the first move of chess is flipping a coin to see which player goes first! Then the game becomes symmetric, because each player has an equal chance of becoming white or black.

Puzzle

I may put some puzzles on this blog, which are different than the homework for the course. You can answer them on the blog! If you’re a student in the course and you give a good answer, I’ll give you some extra credit.

Puzzle. What’s a ‘game of perfect information’ and what’s a ‘game of complete information’? What’s the difference?


Rolling Circles and Balls (Part 5)

2 January, 2013

Last time I promised to show you how the problem of a little ball rolling on a big stationary ball can be described using an 8-dimensional number system called the split octonions… if the big ball has a radius that’s 3 times the radius of the little one!

So, let’s get started.

First, I must admit that I lied.

Lying is an important pedagogical technique. The teacher simplifies the situation, so the student doesn’t get distracted by technicalities. Then later—and this is crucial!—the teacher admits that certain statements weren’t really true, and corrects them. It always makes me uncomfortable to do this. But it works better than dumping all the technical details on the students right away. In classes, I sometimes deal with my discomfort by telling the students: “Okay, now I’m going to lie a bit…”

What was my lie? Instead of an ordinary ball rolling on another ordinary ball, we need a ‘spinorial’ ball rolling on a ‘projective’ ball.

Let me explain that.

A spinorial ball

In physics, a spinor is a kind of particle that you need to turn around twice before it comes back to the way it was. Examples include electrons and protons.

If you give one of these particles a full 360° turn, which you can do using a magnetic field, it changes in a very subtle way. You can only detect this change using clever tricks. For example, take a polarized beam of electrons and send it through a barrier with two slits cut out. Each electron goes through both slits, because it’s a wave as well as a particle. Next, put a magnetic field next to one slit that’s precisely strong enough to rotate the electron by 360° if it goes through that slit. Then, make the beams recombine, and see how likely it is for electrons to be found at different locations. You’ll get different results than if you turn off the magnetic field that rotates the electron!

However, if you rotate a spinor by 720°—that is, two full turns—it comes back to exactly the way it was.

This may seem very odd, but when you understand the math of spinors you see it all makes sense. It’s a great example of how you have to follow the math where it leads you. If something is mathematically allowed, nature may take advantage of that possibility, regardless of whether it seems odd to you.

So, I hope you can imagine a ‘spinorial’ ball, which changes subtly when you turn it 360° around any axis, but comes back to its original orientation when you turn it around 720°. If you can’t, I’ll present the math more rigorously later on. That may or may not help.

A projective ball

What’s a ‘projective’ ball? It’s a ball whose surface is not a sphere, but a projective plane. A projective plane is a sphere that’s been modified so that diametrically opposite points count as the same point. The north pole is the same as the south pole, and so on!

In geography, the point diametrically opposite to some point on the Earth’s surface is called its antipodes, so let’s use that term. There’s a website that lets you find the antipodes of any place on Earth. Unfortunately the antipodes of most famous places are under water! But the antipodes of Madrid is in New Zealand, near Wellington:

When we roll a little ball on a big ‘projective’ ball, when the little ball reaches the antipodes of where it started, it counts as being back to its original location.

If you find this hard to visualize, imagine rolling two indistinguishable little balls on the big ball, that are always diametrically opposite each other. When one little ball rolls to the antipodes of where it started, the other one has taken its place, and the situation looks just like when you started!

A spinorial ball on a projective ball

Now let’s combine these ideas. Imagine a little spinorial ball rolling on a big projective ball. You need to turn the spinorial ball around twice to make it come back to its original orientation. But you only need to roll it halfway around the projective ball for it to come back to its original location.

These effects compensate for each other to some extent. The first makes it twice as hard to get back to where you started. The second makes it twice as easy!

But something really great happens when the big ball is 3 times as big as the little one. And that’s what I want you to understand.

For starters, consider an ordinary ball rolling on another ordinary ball that’s the same size. How many times does the rolling ball turn as it makes a round trip around the stationary one? If you watch this you can see the answer:


Follow the line drawn on the little ball. It turns around not once, but twice!

Next, consider one ball rolling on another whose radius is 2 times as big. How many times does the rolling ball turn as it makes a round trip?

It turns around 3 times.

And this pattern continues! I don’t have animations proving it, so either take my word for it, read our paper, or show it yourself.

In particular, a ball rolling on a ball whose radius is 3 times as big will turn 4 times as it makes a round trip.

So, by the time the little ball rolls halfway around the big one, it will have turned around twice!

But now suppose it’s a spinorial ball rolling on a projective plane. This is perfect. Now when the little ball goes halfway around big ball, it returns to its original location! And turning around the little ball twice gets it back to its original orientation!

So, there is something very neat about a spinorial ball rolling on a projective ball whose radius is exactly 3 times as big. And this is just the start. Now the split octonions get involved!

The rolling ball geometry

The key is to ponder a curious sort of geometry, which I’ll call the rolling ball geometry. This has ‘points’ and ‘lines’ which are defined in a funny way.

A point is any way a little spinorial ball can touch a projective ball that is 3 times as big. The lines are certain sets of points. A line consists of all the points we reach as the little ball rolls along some great circle on the big one, without slipping or twisting.

Of course these aren’t ‘points’ and ‘lines’ in the usual sense. But ever since the late 1800s, when mathematicians got excited about projective geometry—which is the geometry of the projective plane—we’ve enjoyed studying all sorts of strange variations on Euclidean geometry, with weirdly defined ‘points’ and ‘lines’. The rolling ball geometry fits very nicely into this tradition.

But the amazing thing is that we can describe points and lines of the rolling ball geometry in a completely different way, using the split octonions.

Split octonions

How does it work? As I said last time, the split octonions are an 8-dimensional number system. We build them as follows. We start with the ordinary real numbers. Then we throw in 3 square roots of -1, called i, j, and k, obeying

ij = -ji = k
jk = -kj = i
ki = -ik = j

At this point we have a famous 4-dimensional number system called the quaternions. Quaternions are numbers like

a + bi + cj + dk

where a,b,c,d are real numbers and i, j, k are the square roots of -1 we just created.

To build the octonions, we would now throw in another square root of -1. But to build the split octonions, we instead throw in a square root of +1. Let’s call it \ell. The hard part is saying what rules it obeys when we start multiplying it with other numbers in our system.

For starters, we get three more numbers \ell i, \ell j, \ell k. We decree these to be square roots of +1. But what happens when we multiply these with other things? For example, what is \ell i times j, and so on?

Since I don’t want to bore you, I’ll just get this over with quickly by showing you the multiplication table:

This says that \ell i (read down) times j (read across) is -\ell k, and so on.

Of course, this table is completely indigestible. I could never remember it, and you shouldn’t try. This is not the good way to explain how to multiply split octonions! It’s the lazy way. To really work with the split octonions you need a more conceptual approach, which John Huerta and I explain in our paper. But this is just a quick tour… so, on with the tour!

A split octonion is any number like

a + bi + cj + dk + e \ell + f \ell i + g \ell j + h \ell k

where a,b,c,d,e,f,g,h are real numbers. Since it takes 8 real numbers to specify a split octonion, we say they’re an 8-dimensional number system. But to describe the rolling ball geometry, we only need the imaginary split octonions, which are numbers like

x = bi + cj + dk + e \ell + f \ell i + g \ell j + h \ell k

The imaginary split octonions are 7-dimensional. 3 dimensions come from square roots of -1, while 4 come from square roots of 1.

We can use them to make up a far-out variant of special relativity: a universe with 3 time dimensions and 4 space dimensions! To do this, define the length of an imaginary split octonion x to be the number \|x \| with

\|x\|^2 = -b^2 - c^2 - d^2 + e^2 + f^2 + g^2 + h^2

This is a mutant version of the Pythagorean formula. The length \|x\| is real, in fact positive, for split octonions that point in the space directions. But it’s imaginary for those that point in the time directions!

This should not sound weird if you know special relativity. In special relativity we have spacelike vectors, whose length squared is positive, and timelike ones, whose length squared is negative.

If you don’t know special relativity—well, now you see how revolutionary Einstein’s ideas really are.

We also have vectors whose length squared is zero! These are called null. They’re also called lightlike, because light rays point along null vectors. In other words: light moves just as far in the space directions as it does in the time direction, so it’s poised at the brink between being spacelike and timelike.

The punchline

I’m sure you’re wondering where all this is going. Luckily, we’re there. We can describe the rolling ball geometry using the imaginary split octonions! Let me state it and then chat about it:

Theorem. There is a one-to-one correspondence between points in the rolling ball geometry and light rays through the point 0 in the imaginary split octonions. Under this correspondence, lines in the rolling ball geometry correspond to planes containing the point 0 in the imaginary split octonions with the property that whenever x and y lie in this plane, then xy = 0.

Even if you don’t get this, you can see it’s describing the rolling ball geometry in terms of stuff about the split octonions. An immediate consequence is that any symmetry of the split octonions is a symmetry of the rolling ball geometry.

The symmetries of the split octonions form a group called ‘the split form of G2’. With more work, we can show the converse: any symmetry of the rolling ball geometry is a symmetry of the split octonions. So, the symmetry group of the rolling ball geometry is precisely the split form of G2.

So what?

Well, G2 is an ‘exceptional group’—one of five groups that were discovered only when mathematicians like Killing and Cartan systematically started trying to classify groups in the late 1800s. The exceptional groups didn’t fit in the lists of groups mathematicians already knew.

If, as Tim Gowers has argued, some math is invented while some is discovered, the exceptional groups were discovered. Finding them was like going to the bottom of the ocean and finding weird creatures you never expected. These groups were—and are—hard to understand! They have dry, technical sounding names: E6, E7, E8, F4, and G2. They’re important in string theory—but again, just because the structure of mathematics forces it, not because people wanted it.

The exceptional groups can all be described using the octonions, or split octonions. But the octonions are also rather hard to understand. The rolling ball geometry, on the other hand, is rather simple and easy to visualize. So, it’s a way of bringing some exotic mathematics a bit closer to ordinary life.

Well, okay—in ordinary life you’d probably never thought about a spinorial ball rolling on a projective ball. But still: spinors and projective planes are far less exotic than split octonions and exceptional Lie groups. Any mathematician worth their salt knows about spinors and projective planes. They’re things that make plenty of sense.

I think now is a good time for most of you nonmathematicians to stop reading. I’ll leave off with a New Year’s puzzle:

Puzzle: Relative to the fixed stars, how many times does the Earth turn around its axis in a year?

Bye! It was nice seeing you!

The gory details

Still here? Cool. I want to wrap up by presenting the theorem in a more precise way, and then telling the detailed history of the rolling ball problem.

How can we specify a point in the rolling ball geometry? We need to say the location where the little ball touches the big ball, and we need to describe the ‘orientation’ of the little ball: that is, how it’s been rotated.

The point where the little ball touches the big one is just any point on the surface of the big ball. If the big ball were an ordinary ball this would be a point on the sphere, S^2. But since it’s a projective ball, we need a point on the projective plane, \mathbb{R}\mathrm{P}^2.

To describe the orientation of the little ball we need to say how it’s been rotated from some standard orientation. If the little ball were an ordinary ball we’d need to give an element of the rotation group, \mathrm{SO}(3). But since it’s a spinorial ball we need an element of the double cover of the rotation group, namely the special unitary group \mathrm{SU}(2).

So, the space of points in the rolling ball geometry is

X = \mathbb{R}\mathrm{P}^2 \times \mathrm{SU}(2)

This makes it easy to see how the imaginary split octonions get into the game. For starters, \mathrm{SU}(2) is isomorphic to the group of unit quaternions. We can define the absolute values of quaternions in a way that copies the usual formula for complex numbers:

\displaystyle{ |a + bi + cj + dk| = \sqrt{a^2 + b^2 + c^2 + d^2} }

The great thing about the quaternions is that if we multiply two of them, their absolute values multiply. In other words, if p and q are two quaternions,

|pq| = |p| |q|

This implies that the quaternions with absolute value 1—the unit quaternions—are closed under multiplication. In fact, they form a group. And in fact, this group is just SU(2) in mild disguise!

The unit quaternions form a sphere. Not an ordinary ‘2-sphere’ of the sort we’ve been talking about so far, but a ‘3-sphere’ in the 4-dimensional space of quaternions. We call that S^3.

So, the space of points in the rolling ball is isomorphic to a projective plane times a 3-sphere:

X \cong \mathbb{R}\mathrm{P}^2 \times S^3

But since the projective plane \mathbb{R}\mathrm{P}^2 is the sphere S^2 with antipodal points counted as the same point, our space of points is

\displaystyle{ X \cong \frac{S^2 \times S^3}{(p,q) \sim (-p,q)}}

Here dividing or ‘modding out’ by that stuff on the bottom says that we count any point (p,q) in S^2 \times S^3 as the same as (-p,q).

The cool part is that while S^3 is the unit quaternions, we can think of S^2 as the unit imaginary quaternions, where an imaginary quaternion is a number like

bi + cj + dk

So, we’re describing a point in the rolling ball geometry using a unit quaternion and a unit imaginary quaternion. That’s cool. But we can improve this description a bit using a nonobvious fact:

\displaystyle{ X \cong \frac{S^2 \times S^3}{(p,q) \sim (-p,-q)}}

There’s an extra minus sign here! Now we’re counting any point (p,q) in S^2 \times S^3 as the same as (-p,-q). In Proposition 2 in our paper we give an explicit formula for this isomorphism, which is important.

But never mind. Here’s the point of this improvement: we can now describe a point in the rolling ball geometry as a light ray through the origin in the imaginary split octonions! After all, any split octonion is of the form

a + bi + cj + dk + e \ell + f \ell i + g \ell j + h \ell k =  p + \ell q

where p and q are arbitrary quaternions. So, any imaginary split octonion is of the form

bi + cj + dk + e \ell + f \ell i + g \ell j + h \ell k =  p + \ell q

where q is a quaternion and p is an imaginary quaternion. This imaginary split octonion is lightlike if

-b^2 - c^2 - d^2 + e^2 + f^2 + g^2 + h^2 = 0

But this just says

|p|^2 = |q|^2

Given any light ray through the origin in the imaginary split octonions, it consists of all real multiples of some lightlike imaginary split octonion. So, we can describe it using a pair (p,q) where p is an imaginary quaternion and q is a quaternion with the same absolute value as p. We can normalize them so they’re both unit quaternions… but (p,q) and its negative (-p,-q) still determine the same light ray.

So, the space of light rays through the origin in the imaginary split octonions is

\displaystyle{\frac{S^2 \times S^3}{(p,q) \sim (-p,-q)}}

But this is the space of points in the rolling ball geometry!

Yay!

So far nothing relies on knowing how to multiply imaginary split octonions: we only need the formula for their length, which is much simpler. It’s the lines in the rolling ball geometry that require multiplication. In our paper, we show in Theorem 5 that lines correspond to 2-dimensional subspaces of the imaginary split octonions with the property that whenever x, y lie in the subspace, then x y = 0. In particular this implies that x^2 = 0, which turns out to say that x is lightlike. So, these 2d subspaces consist of lightlike elements. But the property that x y = 0 whenever x, y lie in the subspace is actually stronger! And this is how the full strength of the split octonions gets used.

One last comment. What if we hadn’t used a spinorial ball rolling on a projective ball? What if we had used an ordinary ball rolling on another ordinary ball? Then our space of points would be S^2 \times \mathrm{SO}(3). This is a lot like the space X we’ve been looking at. The only difference is a slight change in where we put the minus sign:

\displaystyle{ S^2 \times \mathrm{SO}(3) \cong \frac{S^2 \times S^3}{(p,q) \sim (p,-q)}}

But this space is different than X. We could go ahead and define lines and look for symmetries of this geometry, but we wouldn’t get G2. We’d get a much smaller group. We’d also get a smaller symmetry group if we worked with X but the big ball were anything other than 3 times the size of the small one. For proofs, see:

• Gil Bor and Richard Montgomery, G2 and the “rolling distribution”.

The history

I will resist telling you how to use geometric quantization to get back from the rolling ball geometry to the split octonions. I will also resist telling you about ‘null triples’, which give specially nice bases for the split octonions. This is where John Huerta really pulled out all the stops and used his octonionic expertise to its full extent. For these things, you’ll just have to read our paper.

Instead, I want to tell you about the history of this problem. This part is mainly for math history buffs, so I’ll freely fling around jargon that I’d been suppressing up to now. This part is also where I give credit to all the great mathematicians who figured out most of the stuff I just explained! I won’t include references, except for papers that are free online. You can find them all in our paper.

On May 23, 1887, Wilhelm Killing wrote a letter to Friedrich Engel saying that he had found a 14-dimensional simple Lie algebra. This is now called \mathfrak{g}_2, because it’s the Lie algebra corresponding to the group G2. By October he had completed classifying the simple Lie algebras, and in the next three years he published this work in a series of papers.

Besides the already known classical simple Lie algebras, he claimed to have found six ‘exceptional’ ones. In fact he only gave a rigorous construction of the smallest, \mathfrak{g}_2. Later, in his famous 1894 thesis, Élie Cartan constructed all of them and noticed that two of them were isomorphic, so that there are really only five.

But already in 1893, Cartan had published a note describing an open set in \mathbb{C}^5 equipped with a 2-dimensional ‘distribution’—a smoothly varying field of 2d spaces of tangent vectors—for which the Lie algebra \mathfrak{g}_2 appears as the infinitesimal symmetries. In the same year, and actually in the same journal, Engel noticed the same thing.

In fact, this 2-dimensional distribution is closely related to the rolling ball problem. The point is that the space of configurations of the rolling ball is 5-dimensional, with a 2-dimensional distibution that describes motions of the ball where it rolls without slipping or twisting.

Both Cartan and Engel returned to this theme in later work. In particular, Engel discovered in 1900 that a generic antisymmetic trilinear form on \mathbb{C}^7 is preserved by a group isomorphic to the complex form of G2. Furthermore, starting from this 3-form he constructed a nondegenerate symmetric bilinear form on \mathbb{C}^7. This implies that the complex form of G2. is contained in a group isomorphic to \mathrm{SO}(7,\mathbb{C}). He also noticed that the vectors x \in \mathbb{C}^7 that are null—meaning x \cdot x = 0, where we write the bilinear form as a dot product—define a 5-dimensional projective variety on which G2 acts.

In fact, this variety is the complexification of the configuration space of a rolling fermionic ball on a projective plane! Futhermore, the space \mathbb{C}^7 is best seen as the complexification of the space of imaginary octonions. Like the space of imaginary quaternions (better known as \mathbb{R}^3), the 7-dimensional space of imaginary octonions comes with a dot product and cross product. Engel’s bilinear form on \mathbb{C}^7 arises from complexifying the dot product. His antisymmetric trilinear form arises from the dot product together with the cross product via the formula

x \cdot (y \times z).

However, all this was seen only later! It was only in 1908 that Cartan mentioned that the automorphism group of the octonions is a 14-dimensional simple Lie group. Six years later he stated something he probably had known for some time: this group is the compact real form of G2.

As I already mentioned, the octonions had been discovered long before: in fact the day after Christmas in 1843, by Hamilton’s friend John Graves. Two months before that, Hamilton had sent Graves a letter describing his dramatic discovery of the quaternions. This encouraged Graves to seek an even larger normed division algebra, and thus the octonions were born. Hamilton offered to publicize Graves’ work, but put it off or forgot until the young Arthur Cayley rediscovered the octonions in 1845. That this obscure algebra lay at the heart of all the exceptional Lie algebras and groups became clear only slowly. Cartan’s realization of its relation to \mathfrak{g}_2, and his later work on a symmetry called ‘triality’, was the first step.

In 1910, Cartan wrote a paper that studied 2-dimensional distributions in 5 dimensions. Generically such a distibution is not integrable: in other words, the Lie bracket of two vector fields lying in this distribution does not again lie in this distribution. However, it lies in a 3-dimensional distribution. The Lie bracket of vector fields lying in this 3-dimensional distibution then generically give arbitrary tangent vectors to the 5-dimensional manifold. Such a distribution is called a (2,3,5) distribution. Cartan worked out a complete system of local geometric invariants for these distributions. He showed that if all these invariants vanish, the infinitesimal symmetries of a (2,3,5) distribution in a neighborhood of a point form the Lie algebra \mathfrak{g}_2.

Again this is relevant to the rolling ball. The space of configurations of a ball rolling on a surface is 5-dimensional, and it comes equipped with a (2,3,5) distribution. The 2-dimensional distibution describes motions of the ball where it rolls without twisting or slipping. The 3-dimensional distribution describes motions where it can roll and twist, but not slip. Cartan did not discuss rolling balls, but he did consider a closely related example: curves of constant curvature 2 or 1/2 in the unit 3-sphere.

Beginning in the 1950’s, Francois Bruhat and Jacques Tits developed a very general approach to incidence geometry, eventually called the theory of ‘buildings’, which among other things gives a systematic approach to geometries having simple Lie groups as symmetries. In the case of G2, because the Dynkin diagram of this group has two dots, the relevant geometry has two types of figure: points and lines. Moreover because the Coxeter group associated to this Dynkin diagram is the symmetry group of a hexagon, a generic pair of points a and d fits into a configuration like this, called an ‘apartment’:

There is no line containing a pair of points here except when a line is actually shown, and more generally there are no ‘shortcuts’ beyond what is shown. For example, we go from a to b by following just one line, but it takes two to get from a to c, and three to get from a to d.

Betty Salzberg wrote a nice introduction to these ideas in 1982. Among other things, she noted that the points and lines in the incidence geometry of the split real form of G2 correspond to 1- and 2-dimensional null subalgebras of the imaginary split octonions. This was shown by Tits in 1955.

In 1993, Bryant and Hsu gave a detailed treatment of curves in manifolds equipped with 2-dimensional distributions, greatly extending the work of Cartan:

• Robert Bryant and Lucas Hsu, Rigidity of integral curves of rank 2 distributions.

They showed how the space of configurations of one surface rolling on another fits into this framework. However, Igor Zelenko may have been the first to explicitly mention a ball rolling on another ball in this context, and to note that something special happens when their ratio of radii is 3 or 1/3. In a 2005 paper, he considered an invariant of (2,3,5) distributions. He calculated it for the distribution arising from a ball rolling on a larger ball and showed it equals zero in these two cases.

(In our paper, John Huerta and I assume that the rolling ball is smaller than the fixed one, simply to eliminate one of these cases and focus on the case where the fixed ball is 3 times as big.)

In 2006, Bor and Montgomery's paper put many of the pieces together. They studied the (2,3,5) distribution on S^2 \times \mathrm{SO}(3) coming from a ball of radius 1 rolling on a ball of radius R, and proved a theorem which they credit to Robert Bryant. First, passing to the double cover, they showed the corresponding distribution on S^2 \times \mathrm{SU}(2) has a symmetry group whose identity component contains the split real form of G2 when R = 3 or 1/3. Second, they showed this action does not descend to original rolling ball configuration space S^2 \times \mathrm{SO}(3). Third, they showed that for any other value of R except R = 1, the symmetry group is isomorphic to \mathrm{SU}(2) \times \mathrm{SU}(2)/\pm(1,1). They also wrote:

Despite all our efforts, the ‘3’ of the ratio 1:3 remains mysterious. In this article it simply arises out of the structure constants for G2 and appears in the construction of the embedding of \mathfrak{so}(3) \times \mathfrak{so}(3) into \mathfrak{g}_2. Algebraically speaking, this ‘3’ traces back to the 3 edges in \mathfrak{g}_2's Dynkin diagram and the consequent relative positions of the long and short roots in the root diagram for \mathfrak{g}_2 which the Dynkin diagram is encoding.

Open problem. Find a geometric or dynamical interpretation for the ‘3’ of the 3:1 ratio.

As you can see from what I’ve said, John Huerta and I have offered a solution to this puzzle: the ‘3’ comes from the fact that a ball rolling once around a ball 3 times as big turns around exactly 4 times—just what you need to get a relationship to a spinorial ball rolling on a projective plane, and thus the lightcone in the split octonions! The most precise statement of this explanation comes in Theorem 3 of our paper.

While Bor and Montgomery’s paper goes into considerable detail about the connection with split octonions, most of their work uses the now standard technology of semisimple Lie algebras: roots, weights and the like. In 2006, Sagerschnig described the incidence geometry of \mathrm{G}_2 using the split octonions, and in 2008, Agrachev wrote a paper entitled ‘Rolling balls and octonions’. He emphasizes that the double cover S^2 \times \mathrm{SU}(2) can be identified with the double cover of \mathrm{PC}, the projectivization of the set of null vectors in the imaginary split octonions. He then shows that given a point \langle x \rangle \in \mathrm{PC}, the set of points \langle y \rangle connected to \langle x \rangle by a single roll is the annihilator

\{ x \in \mathbb{I} : y x = 0 \}

where \mathbb{I} is the space of imaginary split octonions.

This sketch of the history is incomplete in many ways. As usual, history resembles a fractal: the more closely you study it, the more details you see! If you want to dig deeper, I strongly recommend these:

• Ilka Agricola, Old and new on the the exceptional group G2.

• Robert Bryant, Élie Cartan and geometric duality.

This paper is also very helpful and fun:

• Aroldo Kaplan, Quaternions and octonions in mechanics.

It emphasizes the role that quaternions play in describing rotations, and the way an imaginary split octonion is built from an imaginary quaternion and a quaternion. And don’t forget this:

• Andrei Agrachev, Rolling balls and octonions.

Have fun!


Follow

Get every new post delivered to your Inbox.

Join 3,095 other followers