A Little Learning (Game Theory, Part Deux)

Here, as promised, is the dangerous thing.

Suppose you're getting a sequence of playing cards, and you're trying to figure out some statistics for the playing cards. At first, the cards seem utterly random, but after a while, a pattern emerges: There are slightly more black face cards than red ones, and there are slightly more red low-rank cards than black ones. You're a statistician, so you can quantify the bias—measure the correlation coefficient between color and rank, estimate the standard error in the observed proportions, and so forth. There are rigorous rules for computing all these things, and they're quite straightforward to follow.

Except, you're playing gin rummy, and the reason you're receiving a biased sequence of cards is that you're trying to collect particular cards. If you change your collection strategy, you'll affect the bias. You may have followed all the statistical rules, but you've forgotten about the context.

It might seem entirely obvious to you, now that I've told you the whole story, what the mistake is, and how to avoid it, but I contend that a wholly parallel thing is happening in sports statistics. I'm going to talk about basketball again, because I'm most familiar with it, but the issue transcends that individual sport, yes?

I've previously touched upon this, but this time, with the first post on game theory as background, I'm actually going to go through some of the analysis. Again, we won't be able to entirely avoid the math, but I'll try to describe in words what's going on at the same time. If calculus makes you squeamish, feel free to skip the following and move down to the part in bold.

In our simple model, the offense has two basic options: have the perimeter player shoot the ball, or pass it into the post player, and have him shoot the ball. The defense, in turn, can vary its defensive pressure on the two players, and it can do that continuously: It can double team the perimeter player aggressively, double the post player off the ball, or anything in between. We'll use the principles of game theory to figure out where the Nash equilibrium for this situation is.

We'll denote the defensive strategy by b, for on-ball pressure: If b = 1, then all of the pressure is on the perimeter ball-handler; if b = 0, all of it's on the post player. An intermediate value, like b = 1/2, might mean that the defense is equally split between the two of them (man-to-man defense on each), but the exact numbers are not important; the important thing is that the defensive strategy varies smoothly, and its effects on the offensive efficiency also vary smoothly.

Each of the two offensive options has an associated efficiency, which represents how many points on average are scored when that player attempts a shot. We'll call the perimeter player's efficiency r, and the post player's efficiency s. As you might expect, both efficiencies depend on the defensive strategy, so we'll actually be referring to the efficiency functions r(b) and s(b). The perimeter player is less efficient when greater defensive pressure is placed on him, naturally, so r(b) is a decreasing function of b. On the other hand, the post player is more efficient when greater defensive pressure is placed on the perimeter player, so s(b) is an increasing function of b.

Now let's look at this situation from a game theory perspective. Will the Nash equilibrium of this system involve pure strategies, or mixed strategies? (A pure defensive strategy in this instance consisting of either b = 0 or b = 1.) Right away, we can eliminate the pure strategies as follows: If the offense funnelled all of its offense through one of those players, and the defense knew it, they would muster all their defensive pressure on that player. On the other hand, if the defense always pressured one of the players, and the offense knew it, they would always have the other player shoot it. Since those two scenarios are incompatible with one another, the Nash equilibrium must involve mixed strategies. Our objective, then, is to figure out what those mixed strategies are.

The offensive mix, or strategy, we'll represent by p, the fraction of time that the perimeter player shoots the ball. The rest of the time, 1-p, the post player shoots the ball. The overall efficiency function of the offense, as a function of defensive strategy b, is then

Q(b) = p r(b) + (1-p) s(b)

The objective of the defense, in setting its defensive strategy, will be to ensure that the offense cannot improve its outcome by varying its strategy p. That is, it will set the value b such that the partial derivative of Q with respect to p (not b) is equal to 0:

∂Q/∂p = r(b) - s(b) = 0

which happens when r(b) = s(b)—in other words, when the efficiencies of the two options are equal. The offense, in setting its strategy p, will aim to zero out the partial derivative of Q with respect to b:
∂Q/∂b = p r'(b) + (1-p) s'(b) = 0

which happens when

p = s'(b) / [s'(b) - r'(b)]

where b is taken to be the point where the two efficiency curves meet, since the offense knows the defense will play there.

But let's not worry about the offensive strategy; the important thing to take away is that at the Nash equilibrium, the defense will adjust its pressure until the efficiencies of the two offensive options are equal. Let's show what that looks like graphically.

We'll see here how game theory tells us what should be common sense: If the current defensive strategy were somewhere else than at the Nash equilibrium—say, if it were further to the left—the offense could improve its outcome by shifting more of its offensive load to the perimeter player, since he's the more efficient option on the left side of the graph. The reverse holds on the right side of the graph. Only at the point where they cross is the offense powerless to improve its situation by changing its offensive mix, which is exactly the outcome the defense wants.

As a corollary, the exact location of the Nash equilibrium depends vitally on the efficiency functions of the offensive components. If, for instance, one of the efficiency functions drops, the observed efficiency of the offense (that is, the efficiency measured by statistics) will also drop. Let's take a look at that graphically:


In this figure, the efficiency function of the post player, represented by s(b), has dropped. This has the effect of sliding the Nash equilibrium point down and to the right, which indicates increased ball pressure and a decrease in the observed efficiency of both the post player and the perimeter player. It's important to recognize that the efficiency function of a player refers to the entire curve, from b = 0 to b = 1, but when we gather basketball statistics, we merely get the observed efficiency, the value of that curve at a single point—the point where the team strategies actually reside (in this case, the Nash equilibrium).

Consider: Why might the efficiency function of the post player drop, as depicted above? It might be because the backup post player came in. It might be because a defensive specialist post player came in. In short, it might be because of a variety of things, none of which have to do with the perimeter player and his efficiency function—and yet the perimeter player's observed efficiency (whether we're talking about PER, or WP48, or whatever) drops as a result.

There's nothing special about the perimeter player in this regard; we would see the same effect on the post player if the perimeter player (or his defender) were swapped out. In general, the observed efficiency of a player goes up or down owing, in part, to the efficiency function of his teammates.

We see here an analogy to the distinction, drawn in economics, between demand and quantity demanded. Suppose we see that sales of a particular brand of cheese spread have dropped over the last quarter. That is to say, the quantity demanded has decreased. Does that necessarily mean that demand itself has dropped? Not necessarily. It could be that a new competing brand of cheese spread has arrived on the market. Or, it could be that production costs of the cheese spread have increased, leading to a corresponding increase in price. Both of these decrease the quantity demanded, but only the former represents a decrease in actual demand. Demand is a function of price; quantity demanded is just a number. If all we measure is quantity demanded, and we ignore the price, we haven't learned all we need to carry on our business. As economists, we would be roundly criticized (and rightly so) for neglecting this critical factor.

We are, in the basketball statistics world (and that of sports statistics in general), at a point where all we measure is the number. We don't, as a rule, measure the function. We apply our statistical rules with rigor and expect our results to acquire the patina of that rigor. But we mustn't be hypnotized by that patina and forget what we are measuring. If our aim is to describe the observed situation, then the number may be all we need. But if our aim is to describe some persistent quality of the situation—as must be the case if we are attempting to (say) compare players, or if we are hoping to optimize strategies—then we are obligated to measure the function. Doing so is very complex indeed for basketball; there are an array of variables to account for, and we have at present only the most rudimentary tools for capturing them. It is OK to punt that problem for now. But in the meantime, we must not delude ourselves into thinking that by measuring that one number, we have all we need to carry on our business.

Matching Up in Hyperspace (or, Thirty Dancing)

Maybe it's because I've been writing about basketball a lot, but I thought today I'd do something a little different before continuing on, as promised, with a second game theory post.

A while ago, I remember reading an analogy about why it is that oil and water don't mix. (I don't remember where I read it, though, so if you recognize it, please tell me.) Is it that water molecules only "like" water molecules, and oil molecules only "like" oil molecules? Not at all—they all like water molecules!

A water molecule is often drawn as H-O-H, but that drawing is a bit misleading. The hydrogen atoms are actually attached at an angle, as below.

This one looks a bit like a Japanese cartoon character, if you ask me. At any rate, this asymmetry, top to bottom (as drawn here), means that we can speak of an oxygen end (the bottom) and a hydrogen end (the top). What's more, because of the way that electrons are arranged in each atom, the oxygen atom tends to draw electrons away from the hydrogen atoms. The oxygen end, so to speak, has more electrons hanging around it than the hydrogen end. Since electrons are negatively charged, the water molecule has a positive pole (the hydrogen end) and a negative pole (the oxygen end), and we say that the water is a polar molecule.

Water molecules attract each other because they are polar. The positively charged hydrogen end of one attracts the negatively charged oxygen end of another. In steam, the gaseous form, this is almost impossible to make out, because the molecules are too far apart and energetic, bouncing around far too wildly to show any mutual attraction. However, in ice, the solid form, the attraction is much more obvious.



It's a bit hard to tell which hydrogen atoms are associated with each oxygen atoms, but that's because in ice, the bonds are a bit confused. Even so, however, it's clear that we don't have water molecules bonding together oxygen-to-oxygen, or hydrogen-to-hydrogen. They only attach oxygen-to-hydrogen (in the hexagonal arrangement that yields those lovely snowflakes), because the molecules are polar that way. That's the way water molecules "like" each other.

Liquid water is intermediate between ice and steam. The molecules aren't fixed in place to each other as they are in ice, but neither are they bouncing wildly as they are in steam. Instead, they wander amongst each other, like people milling about in a crowd. And as they wander around, they stick to each other a bit, on account of their polarity. They attach and cohere, which makes water bead up, among other things.

What about oil molecules? Oil molecules tend to be symmetric in such a way that there is no clear polar end as there is in water. As a result, they are much less polar than water molecules are. Nonetheless, being weakly polar (under appropriate circumstances), they "like" other polar molecules, too. So why don't they attach to the water molecules, too?

The reason is that there is only so much room for molecules to attract each other. And here's where the analogy I mentioned earlier comes into play. You often find, at a school, that the most popular kids date other most popular kids (when they date), and the least popular kids date other least popular kids (again, when they date). Why is that? Is it that the least popular kids aren't attracted to the most popular kids? Well, it might sometimes be because of that, but often, they are attracted to the most popular kids; that is, after all, part of what makes someone most popular.

What gets in the way, however, is that the most popular kids, like most others perhaps, are also attracted to the most popular kids, and since such pairings satisfy both attractions, they get paired first. Then the next most popular kids pair up with other next most popular kids, they get paired next. And so on down the line. Or so the story goes.

Of course, it isn't quite that neat and clean with kids, but it is a reasonable approximation with what happens when you combine oil and water. They don't mix because the most popular water molecules hook up with other most popular water molecules, while the least attractive oil molecules are left hooking up with each other.

So much for oil and water. But now let's go back to that analogy, which as it so happens is what I really wanted to talk about. (The rest of that science was just for show?!) It doesn't ring true because we all know couples where we think, "Wow, she paired up with him?" How does that happen? It happens because people aren't one-dimensional.

Suppose all people were one-dimensional. Then you could rate each person with a number x—say, from 0 to 100. (I hate it when things are rated from 1 to 100. What's middle-of-the-road on such ratings? 50.5?) In such a case, if you have two 100's, wouldn't they choose each other above all others? You couldn't easily see a 100 pairing with a 25, if there's another 100 to choose from. Under such circumstances, the nth highest-rated male would always match up with the nth highest-rated female. Just like the kids at our hypothetical school.

Note: For reasons I despise (expositional convenience, basically), I'm writing this out heterosexually. Let it be clear that this isn't mandated in any way, and I'm aware of that. This treatment unfortunately makes it easiest for me to separate out two groups and draw what amounts to a bipartite graph between them. Sorry!

We might say, callously, that only one pair of people would say they feel completely satisfied with the pairing; everyone else is "envious" in the sense that there's someone else with whom they would rather have paired up. That's inevitable with one-dimensional people.

So let's give people another dimension: Let them now be rated with two numbers (x, y). Now, there is no universal and complete ordering on people. We might agree that if someone has both numbers higher than someone else, they are more appealing, but there is no universally accepted way to compare two people with one number higher and one number lower. This is akin to the problem with PER. It's entirely possible that everyone could be envy-free.

Here's what I mean. Suppose you have three males and three females. The three males are (60, 30), (50, 50), and (30, 60). So are the three females. Now there's no way you can say that the (60, 30) male is inherently superior to the (50, 50) male, or vice versa. The same is true of any other two males, or any two females. To decide amongst the alternatives, one needs a discriminating function of some sort. Let's say your function is 2x+2y. Then you would rank your three choices 180, 200, and 180, and you would choose the (50, 50) over either the (60, 30) or the (30, 60). If, on the other hand, your function was 3x+y, you would rank your choices 210, 200, and 150, and you'd choose the (60, 30) over the other two. Finally, if your function was x+3y, you'd pick the (30, 60) first. So it's possible for each of the alternatives to be first in someone's eyes.

Of course, to be a completely satisfactory pairing, both sides of the pairing must feel they got the best catch. But consider the (60, 30) male. Being a high-x kind of guy, he naturally values x more than y, perhaps, and his discriminating function will reflect that. (Some people, all they care about is x.) He might be exactly the sort of guy with a function like 3x+y, and would therefore pick the (60, 30) female. She, thinking likewise, would pick the (60, 30) male back. Likewise, the (50, 50) people might pair up with each other as mutually optimal choices, and the (30, 60) people too. It doesn't have to match that way, of course; it just has to match one-to-one. Maybe the (60, 30)'s love the (30, 60)'s, for instance, and vice versa.

On the other hand, this matching leaves someone who's (40, 40) out in the cold, because no discriminating function will rate them ahead of everybody else. Whoever matched up with them would always be upset that they didn't at least match up with ol' (50, 50).

It boils down to who's on the Pareto front. The Pareto front is made up of everyone who isn't universally worse than some other option. An illustration of this in two dimensions should hopefully make it clear:

Everyone on the Pareto front could be someone's optimal choice; everyone else would be a consolation prize. It's possible that everyone would be on the front, but it's unlikely, given a random selection of people.

Let's not be too hasty, though. There's an interesting dependency between dimensionality and being on the hull. In one dimension, exactly one person is on the front (barring ties); everyone else is beneath him or her. In two dimensions, it's a bit more complex, but suppose you had a hundred people, evenly spread out between (0, 0) and (100, 100). On average, maybe five people would be on the front. (The actual average is the sum 1 + 1/2 + 1/3 + ... + 1/100.)

Now let's increase it to three dimensions. If you have a hundred people spread out between (0, 0, 0) and (100, 100, 100), on average about 14 people would be on the front. All 14 could be the optimal choice for some prospective mate. As the number of dimensions goes up (and the number of possible discriminating functions, too!), the percentage of people on the front also goes up. With four dimensions, the average number of people on the front is 28; with five, it's 44; with six, 59—more than half! Ten dimensions are sufficient to push it up to 94, and by the time you have, oh, let's say thirty dimensions, the odds are about ten million to one in favor of every last person being on the front. Remember, it isn't necessary to have a highest value in any of the dimensions to be on the front; all you need is to not be lower than anyone else in all of the dimensions. As the number of dimensions goes up, it becomes awfully unlikely that you'll be lower than anyone else in every single dimension. We can have an entirely envy-free matching, all with the help of increased dimensionality.

OK, this may seem completely crazy, and I wouldn't blame you for calling shenanigans. Who would actually go and rank people using a set of thirty numbers? But this is exactly what one of those on-line dating sites advertises it does. Well, not exactly; it actually claims to use 29 dimensions. Why 29? I would imagine because it sounds somewhat more scientific than thirty. But beyond that, I think that they use as many as 29 because it makes it almost inevitable that you'll be on the front, that there'll be someone who you find optimal (or very nearly so), for whom you will likewise be optimal (or very nearly so). And although I think that's partly a marketing gimmick, I think there's some truth to it, too; if there weren't, the human race would have died out long ago.

I mean, how else does Ric Ocasek land Paulina Porizkova? For real, I mean!

A (Kind of) Gentle Introduction to Game Theory

Prefatory to more basketball talk, I want to take a bit of time out to describe what I think is a rather elegant area of mathematics: game theory. Even the name is elegant—simple and to-the-point. As its name implies, game theory is the study of game strategies and tactics from a mathematical point of view. Rather than describe its foundations and move on from there, as a textbook would, I'm going to leap right in and use game theory in a couple of simple situations, which I hope will be a less obscure way of conveying what it's all about.

Suppose that David and Joshua are playing a friendly game of Global Thermonuclear War. At some point, both players have to decide whether to launch an attack or not. If David attacks and Joshua does not, then David wins and earns 5 points (this is a game, after all) and Joshua earns 1 point for being peaceable. Conversely, if Joshua attacks and David does not, Joshua earns 5 points and David earns just 1 point. If both attack, the Earth is rendered a wasteland and neither side earns any points; if both sides do not attack, everybody wins and both sides earn 6 points. The foregoing can be summarized in tabular form, as below.

David's payoffs are shown in blue, Joshua's in red. Let's run through a simple game-theoretical analysis of GTW. If we focus on just the blue numbers (David's payoffs), we see that if Joshua attacks, David's best strategy is to stand down (1 > 0). If Joshua stands down, David's best strategy is, again, to stand down (6 > 5). No matter what Joshua does, in short, David should stand down.

Moving over to the red numbers, we come to a similar conclusion for Joshua's strategy: No matter what David does, Joshua is better off standing down (either 1 > 0, or 6 > 5). As a result, both sides stand down; the only way to win is, indeed, not to play. Whew!

But maybe we shouldn't all relax quite yet. Suppose that we were to adjust the payoff matrix (which is what we call that table up there). Heads of state often get a little nationalistic, and they may well decide that a world without the enemy is better after all, even if we do have to suffer from a little radioactive fallout. At the same time, perhaps it is better to go out fighting and take out the enemy, even as we ourselves are getting wiped out. Then, possibly, the payoff matrix would look like this:

The numbers have changed only a little, but the conclusion is quite different: This time, no matter what Joshua does, David is better off attacking, and no matter what David does, Joshua is better off attacking. The upshot is that both sides end up attacking and wiping each other off the map. The rest of you, I hope you look forward to serving your cockroach overlords...

In the two examples above, the eventual solution has the property that the strategy for both sides was the best they could do, no matter what the opponent did. Such a solution is called a Nash equilibrium, after John Forbes Nash, who won a Nobel Prize in economics for his work in such games. (Yes, the Beautiful Mind guy.) In fact, in each case, the winning strategy was a single choice: either "always attack" or "always stand down."

That is not always the case. Consider a rather less violent game of football (well, somewhat less violent). On a crucial third down, the Steelers can choose to run the ball, or throw the ball; the Packers, on the other hand, can choose to defend the pass or defend the run.

Here's how we might model things. We'll let the payoff be simply the chance, the probability, that the Steelers make a first down. We'll also say that if the Steelers pass, they make a first down 60 percent of the time when the Packers defend the run, but only 20 percent of the time when they defend the pass. If the Steelers run, they make a first down 50 percent of the time when the Packers defend the pass, but only 30 percent of the time when they defend the run. Here's the payoff table:

(We've included the Packers' payoffs in red, although they can be derived from the Steelers' payoff by subtracting from 100 percent.) This time, matters are not as clear cut: For obvious reasons, the Steelers' best option depends on what the Packers do, and the Packers' best option depends on what the Steelers do. But, for our purposes, they both have to show their hands at the same time. What does game theory have to say about this kind of situation?

To figure that out, we'll have to consider a new kind of strategy, called a mixed strategy. A mixed strategy (as opposed to the pure strategies we considered above) is simply one that chooses each of the options with a certain probability. For instance, one possible mixed strategy the Steelers could employ is to run the ball half the time, and pass it the other half. Similarly, the Packers could defend the pass 60 percent of the time, and defend the run 40 percent of the time. There are an infinite number of different mixed strategies both teams could employ. How do we figure out what mixed strategies are actually the best for each side?

Here's where game theory gets a bit hairy (hence the "kind of" in the title). Essentially, what the Steelers want to do is to make their strategy "resistant" against the Packers, in the sense that no matter what the Packers do, they can't damage the Steelers' chances of making their first down. And the Packers want to set their strategy so that no matter what the Steelers do, they can't improve their chances of making the first down. Such a situation, where neither side can do any better without the other side changing what they do, is also a Nash equilibrium. The brilliant thing that Nash did, which earned him that Nobel Prize, was to show that in such games, there is always a set of mixed or pure strategies that yields a Nash equilibrium.

What follows is pretty heavy mathematical stuff. If you don't want me to go all calculus upside your head, feel free to skip it and go to the conclusion in bold, below. Here's what we do. We characterize the Steelers' strategy by p, the probability that the Steelers pass the ball, and the Packers' strategy by q, the probability that they defend the pass. From the Steelers' perspective, there are four distinct possibilities:

1. Steelers pass (p), Packers defend the pass (q): Payoff is 20 percent.
2. Steelers pass (p), Packers defend the run (1-q): Payoff is 60 percent.
3. Steelers run (1-p), Packers defend the pass (q): Payoff is 50 percent.
4. Steelers run (1-p), Packers defend the run (1-q): Payoff is 30 percent.

Putting it all together, we get an expression for the Steelers' payoff S:

S = 0.2 pq + 0.6 p(1-q) + 0.5 (1-p)q + 0.3 (1-p)(1-q)

S = 0.3 + 0.3 p + 0.2 q - 0.6 pq

We want to find the value of p that makes the partial derivative of S with respect to q equal to 0. That is, we need the value of p that makes it utterly irrelevant what the Packers do with their q (as it were).

∂S/∂q = 0.2 - 0.6 p = 0

which happens when p = 1/3. We can do a similar expression for the Packers' payoff P from their side of the payoff matrix:

P = 0.8 pq + 0.4 p(1-q) + 0.5 (1-p)q + 0.7 (1-p)(1-q)

P = 0.7 - 0.3 p - 0.2 q + 0.6 pq

and then the optimal strategy for the Packers is dictated by

∂P/∂p = -0.3 + 0.6 q = 0

which happens when q = 1/2. So the Nash equilibrium happens when the Steelers pass the ball 1/3 of the time and run the ball 2/3 of the time, and the Packers defend the run 1/2 of the time, and defend the pass 1/2 of the time. Under these strategies, the Steelers make their first down 40 percent of the time, and nothing the Steelers do on their own can increase it, and nothing the Packers do on their own can decrease it (given the payoff table). That's what makes it a Nash equilibrium.

Notice that none of the pure strategies work as well as the mixed strategies do. If the Steelers always ran the ball on third down, the Packers knew that, they would just defend the run and limit the Steelers to making first downs 30 percent of the time. It's even worse if the Steelers passed all the time; they'd make a first down only 20 percent of the time. Conversely, if the Packers always defended the run, and the Steelers knew that, they'd just pass all the time and make their first down with 60 percent efficiency. And so on.

The salient thing to take from all this, though, which I'll get into in my next post, is that although the Steelers' odds of making the first down don't depend on the Packers' strategy, at the Nash equilibrium, their best strategy does depend on how good the Packers are at defending the various options (which is represented by the payoff matrix). Although that is hardly earth-shattering in this particular case, we'll see that has interesting repercussions when trying to rate individual player achievement.