A Beautiful Math

by Tom Siegfried

  Much of Buckle's philosophy echoes Quetelet, including similar slams against the idea of unfettered free will. Occasionally someone makes what appears to be a free and even surprising choice, but only because you don't know enough about the person's circumstances, Buckle observed. "If, however, I were capable of correct reasoning, and if, at the same time, I had a complete knowledge both of his disposition and of all the events by which he was surrounded, I should be able to foresee the line of conduct which, in consequence of those events, he would adopt," Buckle pointed out.18 Read retrospectively, Buckle's comment sounds very much like what a game theorist would say today. Game theory is, in fact, all about understanding what choice would (or should) be made if all the relevant information influencing the outcome of the decision is known.

  Buckle realized that choices emerge not merely from external factors, though, but from the inner workings of the mind as well. Since sorting out the nuances of all the influences exceeds science's powers, the nature of human behavior must be described instead by the mathematics of statistics. "All the changes of which history is full, all the vicissitudes of the human race, their progress or their decay, their happiness or their misery, must be the fruit of a double action; an action of external phenomena upon the mind, and another action of the mind upon the phenomena," wrote Buckle. "The most comprehensive inferences respecting the actions of men are derived from this or from analogous sources: they rest on statistical evidence, and are expressed in mathematical language."19

  It's not hard to imagine Maxwell reading these words and seeing in them a solution to the complexities confounding the description of gases. Though Maxwell found Buckle's book "bumptious," he recognized it as a source of original ideas, and the statistical reasoning that Buckle applied to society seemed just the thing that Maxwell needed to deal with molecular motion. "The smallest portion of matter which we can subject to experiment consists of millions of molecules," Maxwell later noted. "We cannot, therefore, ascertain the actual motion of any one of these molecules; so that we are obliged to … adopt the statistical method of dealing with large groups of molecules."20 That statistical method, he showed, could indeed reveal "uniformities" in molecular behavior. "Those uniformities which we observe in our experiments with quantities of matter containing millions of millions of molecules are uniformities of the same kind as those explained by Laplace and wondered at by Buckle," Maxwell declared.21

  The essential feature of Maxwell's work was showing that the properties of gases made sense not if gas molecules all flew around at a similar "average" velocity, as Clausius had surmised, but only if they moved at all sorts of speeds, most near the average, but some substantially faster or slower, and a few very fast or slow. As the molecules bounced off one another, some gained velocity; others slowed down. In subsequent collisions, a fast molecule might be either slowed down or speeded up. A few would enjoy consecutive runs of very good (or very bad) luck and end up moving extremely rapidly (or slowly), while most would get a mix of bounces and tend toward the overall average velocity of all the molecules in the box.

  Just as Quetelet's average man was fictitious, and key insights into society came from analyzing the spread of features around the average, understanding gases meant figuring out the range and distribution of molecular velocities around the average. And that distribution, Maxwell calculated, matched the bell-shaped curve describing the range of measurement errors.

  As Maxwell refined his ideas during the 1860s, he showed that when the velocities reached the bell-shaped distribution, no further net change was likely. (The Austrian physicist Ludwig Boltzmann further elaborated on and strengthened Maxwell's results.) Any specific molecule might speed up or slow down, but the odds were strong that other molecules would change in speed to compensate. Thus the overall range and distribution of velocities would stay the same. When a gas reached that state—in which further collisions would cause no net change in its overall condition—the gas was at equilibrium.

  Of course, this notion of equilibrium is precisely analogous to the Nash equilibrium in game theory. And it's an analogy that has more than merely lexical significance. In a Nash equilibrium, the sets of strategies used by the participants in a game attain a stable set of payoffs, with no incentive for any player to change strategies. And just as the Nash equilibrium is typically a mixed set of strategies, a gas seeks an equilibrium state with a mixed distribution of molecular velocities.

  PROBABILITY DISTRIBUTIONS

  Nash's mixed strategies, and Maxwell's mixed-up molecules, are both examples of what mathematicians call probability distributions. It's such an important concept for game theory (and for science generally) that it's worth a brief interlude to mercilessly pound the idea into your brain (possibly with a silver hammer). Consider Maxwell's problem. How do the molecules in a gas share the total amount of energy that the gas possesses? One possibility is that all the molecules move at something close to the average, as Clausius suspected. Or the velocities could be distributed broadly, some molecules leisurely floating about, others zipping around at superspeed. Clearly, there are lots of possible combinations. And all of these allocations of molecular velocities are in principle possible. It's just that some combinations of velocities are more likely than others.

  For a simpler example, imagine what happens when you repeatedly flip a coin 10 times and record the number of heads. It's easy to calculate the probability distribution for pennies, because you know that the odds of heads versus tails are 50-50. (More technically, the probability of heads for any toss is 0.5, or one-half. That's because there are two possibilities—equally likely, and the sum of all the probabilities must equal 1—1 signifying 100 percent of the cases.) In the long run, therefore, you'll find that the average number of heads per trial is something close to 5 (if you're using a fair coin). But there are many conceivable combinations of totals that would give that average. Half the trials could turn up 10 heads, for instance, while the other half turned up zero every time. Or you could imagine getting precisely 5 heads in every 10-flip trial.

  What actually happens is that the number of trials with different numbers of heads is distributed all across the board, but with differing probabilities—about 25 percent of the time you'll get 5 heads, 20 percent of the time 4 (same for 6), 12 percent of the time 3 (also for 7). You would expect to get 1 head 1 percent of the time (and no heads at all out of a 10-flip run about 0.1 percent of the time, or once in a thousand). Coin tossing, in other words, produces a probability distribution of outcomes, not merely some average outcome. Maxwell's insight was that the same kind of probability distribution governs the possible allocations of energy among a mess of molecules. And game theory's triumph was in showing that a probability distribution of pure strategies—a mixed strategy—is usually the way to maximize your payoff (or minimize your losses) when your opponents are playing wisely (which means they, too, are using mixed strategies).

  Imagine you are repeatedly playing a simple game like matching pennies, in which you guess whether your opponent's penny shows heads or tails. Your best mixed strategy is to choose heads half the time (and tails half the time), but it's not good enough just to average out at 50-50. Your choices need to be made randomly, so that they will reflect the proper probability distribution for equally likely alternatives. If you merely alternate the choice of heads or tails, your opponent will soon see a pattern and exploit it; your 50-50 split of the two choices does you no good. If you are choosing with true randomness, 1 percent of the time you'll choose heads 9 times out of 10, for instance.

  In his book on behavioral game theory, Colin Camerer discusses studies of this principle in a real game—tennis—where a similar 50-50 choice arises: whether to serve to your opponent's right or left side. To keep your opponent guessing, you should serve one way or the other at random.22 Amateur players tend to alternate serve directions too often, and consequently do not achieve the proper probability distribution. Professionals, on the other hand, do approach the ideal
distribution more nearly, suggesting that game theory does indeed capture something about optimal behavior, and that humans do have the capability of learning how to play games with game-theoretic rationality.

  And that, in turn, makes a point that I think is relevant to the prospects of game theory as a mathematical method of quantifying human behavior. In many situations, over time, people do learn how to play games in a way so that the results coincide with Nash equilibrium. There are lots of nuances and complications to cope with, but at least there's hope.

  STATISTICS RETURNS TO SOCIETY

  Of course, real-life situations, the rise of civilization, and the evolution of culture and society are much more complicated than flipping coins and playing tennis. But that is also true of the inanimate world. In most realms of physics and chemistry, the phenomena in need of explanation are rarely split between two equally likely outcomes, so computing probability distributions is much more complicated than the simple 50-50 version you can use with pennies. Maxwell, and then Boltzmann, and then the American physicist J. Willard Gibbs consequently expended enormous intellectual effort in devising the more elaborate formulas that today are known as statistical mechanics, or sometimes simply statistical physics. The uses of statistical mechanics extend far beyond gases, encompassing all the various states of matter and its behavior in all possible circumstances, describing electric and magnetic interactions, chemical reactions, phase transitions (such as melting, boiling, freezing), and all other manner of exchanges of matter and energy.

  The success of statistical mechanics in physics has driven the belief among many physicists that it could be applied with similar success to society. Nowadays, using statistical physics to study human social interactions has become a favorite pastime of a whole cadre of scientists seeking new worlds for physics to conquer. Everything from the flow of funds in the stock market to the flow of traffic on interstate highways has been the subject of statistical-physics study.

  So the use of statistical physics to describe society is not an entirely new endeavor. But the closing years of the 20th century saw an explosion of new research in that arena, and as the 21st century opened, that trend turned into a tidal wave. Behind it all was a surprising burst of new insight into the mathematics describing complex networks. The use of statistical physics to describe such networks has propelled an obscure branch of math called "graph theory" into the forefront of social physics research. And it has all come about because of a game, starring an actor named Kevin Bacon.

  * * *

  8

  Bacon's Links Networks, society, and games

  Unlike the physics of subatomic particles or the largescale structure of the universe, the science of networks is the science of the real world—the world of people, friendships, rumors, disease, fads, firms, and financial crises.

  —Duncan Watts, Six Degrees

  Modern science owes a lot to a guy named Bacon.

  If you had said so four centuries ago, you would have meant Francis Bacon, the English philosopher who stressed the importance of the experimental method for investigating nature. Bacon's influence was so substantial that modern science's birth is sometimes referred to as the Baconian revolution.

  Nowadays, though, when you mention Bacon and science in the same breath you're probably talking not about Francis, but Kevin, the Hollywood actor. Some observers might even say that a second Baconian revolution is now in progress.

  After all, everybody has heard by now that Kevin Bacon is the most connected actor in the movie business. He has been in so many films that you can link almost any two actors via the network of movies that he has appeared in. John Belushi and Demi Moore, for instance, are linked via Bacon through his roles in Animal House (with Belushi) and A Few Good Men (with Moore). Actors who never appeared with Bacon can be linked indirectly: Penelope Cruz has no common films with Bacon, but she was in Vanilla Sky with Tom Cruise, who appeared with Bacon in A Few Good Men. By mid-2005, Bacon had appeared in films with nearly 2,000 other actors, and he could be linked in six steps or fewer to more than 99.9 percent of all the linked actors in a database dating back to 1892. Bacon's notoriety in this regard has become legendary, even earning him a starring role in a TV commercial shown during the Super Bowl.

  Bacon's fame inspired the renaissance of a branch of mathematics known as graph theory—in common parlance, the math of networks. Bacon's role in the network of actors motivated mathematicians to discover new properties about all sorts of networks that could be described with the tools of statistical physics. In particular, modern Baconian science has turned the attention of statistical physicists to social networks, providing a new mode of attack on the problem of forecasting collective human behavior.

  In fact, the new network math has begun to resemble a blueprint for a science of human social interaction, a Code of Nature. So far, though, the statistical physics approach to quantifying social networks has mostly paid little attention to game theory. Many researchers believe, however, that there is—or will be—a connection. For game theory is not merely the math for analyzing individual behavior, as you'll recall—it also proscribes the rules by which many complex networks form. What started out as a game about Kevin Bacon's network may end up as a convergence of the science of networks and game theory.

  SIX DEGREES

  In the early 1990s, Kevin Bacon's ubiquity in popular films caught the attention of some college students in Pennsylvania. They devised a party game in which players tried to find the shortest path of movies linking Bacon to some other actor. When a TV talk show publicized the game in 1994, some clever computer science students at the University of Virginia were watching. They soon launched a research project that spawned a Web page providing instant calculations of how closely Bacon was linked to any other actor. (You should try it—go to oracleofbacon.org.) The 1,952 actors directly linked by a common film appearance with Bacon each have a "Bacon number" of 1. Another 169,274 can be linked to Bacon through one intermediary, giving them a Bacon number of 2. More than 470,000 actors have a Bacon number of 3. On average, Bacon can be linked to the 770,269 linkable actors in the movie database1 in about 2.95 steps. And out of those 770,269 in the database, 770,187 (almost 99.99 percent) are linked to Bacon in six steps or fewer—nearly all, in other words, are less than six degrees of separation from Bacon.

  So studies of the Kevin Bacon game seemed to verify an old sociological finding from the 1960s, when social psychologist Stanley Milgram conducted a famous mail experiment. Some people in Nebraska were instructed to send a parcel to someone they knew personally who in turn could forward it to another acquaintance with the eventual goal of reaching a Boston-area stockbroker. On average, it took a little more than five mailings to reach the stockbroker, suggesting the notion that any two people could be connected, via acquaintances, by less than "six degrees of separation." That idea received considerable publicity in the early 1990s from a play (and later a movie) of that title by John Guare.

  From a scientific standpoint, the Bacon game and Guare's play came along at a propitious time for the study of networks. The six-degrees notion generated an awareness that networks could be interesting things to study, just when the tools for studying networks fell into scientists' laps, in the form of powerful computers that, it just so happened, were themselves linked into a network of planetary proportions—the Internet.

  NETWORKS ARE US

  When I was growing up, "network" meant NBC, ABC, or CBS. Later came PBS, CNN, and ESPN, among others, but the basic idea stayed the same. As the world's cultural focus shifted from TV to computers, though, the notion of network expanded far beyond its origins. Nowadays it seems that networks are everywhere, and everything is a network. Networks permeate government, the environment, and the economy. Society depends on energy networks, communication networks, and transportation networks. Businesses engage networks of buyers and sellers, producers and consumers, and even networks of insider traders. You can find networks of good ol' boys—in poli
tics, industry, and academia. Atlases depict networks of rivers and roads. Food chains have become food webs, just another word for networks. Bodies contain networks of organs, blood vessels, muscles, and nerves. Networks are us.

  Of all these networks, though, one stands out from the crowd—the Internet and the World Wide Web. (OK, that's actually two networks; the Internet comprising the physical network of computers and routers, while the World Wide Web is technically the software part, consisting of information on "pages" connected by URL hyperlinks.) During the early 1990s, awareness of the Internet and Web spread rapidly through the population, bringing nearly everybody in contact with a real live example of a network in action. People in various walks of life began thinking about their world in network terms. True, the word "network" already had its informal uses, for such things as groups of friends or business associates. But during the closing years of the 20th century, the notion of network became more precise and came to be applied to all sorts of systems of interest in biology, technology, and society.

  Throughout the scientific world, networks inspired a new viewpoint for assessing some of society's most perplexing problems. Understanding how networks grow and evolve, survive or fail, may help prevent e-mail crashes, improve cell phone coverage, and even provide clues to curing cancer. Discovering the laws governing networks could provide critical clues for how to protect— or attack—everything from power grids and ecosystems to Web sites and terrorist organizations. Physicists specializing in network math have infiltrated disciplines studying computer systems, international trade, protein chemistry, airline routes, and the spread of disease.