David Blackwell’s Enduring Legacy

by Sophia Chen (science communicator in residence, Fall 2022)
 

In 1976, investment banker John C. Bogle introduced the first index fund available for the general public to purchase. As the story goes, when Bogle was an undergraduate at Princeton University in 1951, he conducted a study that found that stock market indexes, which track the collective price of a group of stocks, tended to grow more than most actively managed funds. Two and a half decades later, as the founder and CEO of Vanguard, Bogle introduced a fund that tracked the price of the S&P 500 index based on that insight. 

Investors distrusted Bogle’s first index fund, as Vanguard raised only $11 million for its initial public offering, around one-tenth of its goal. But they eventually came around. Today, index funds have a reputation for delivering reliable returns. People have invested trillions of dollars in index funds, which now make up more than 40% of the money invested in mutual funds and exchange-traded funds.

But this reputation isn’t a fluke. “There’s a theorem that backs up the use of index funds,” says mathematician Rakesh Vohra of the University of Pennsylvania. Assuming that buying an index fund is a zero-sum game — where the seller’s loss is the buyer’s gain, and vice versa — the theorem guarantees that “the average growth rate of your portfolio is going to match the average growth rate of the best stock,” he says.

The theorem goes by many names, as researchers have discovered and rediscovered it in different contexts. Some call it the experts’ theorem: for example, given two recommendations from two experts to buy two different stocks, the theorem lays out a method to combine the two recommendations that will perform almost as well as the best of these two experts. For this story, we will call it Blackwell’s approachability theorem — to highlight David Blackwell, the UC Berkeley mathematician who proved it and published it in 1956.

Stated more abstractly, Blackwell’s approachability theorem presents an algorithm to win a type of game. In a simplified version of the game, a player chooses numbers from the interval [-1,1] with the goal of nudging the average toward zero, while a second player tries to prevent the first player from doing so. In each round, Player 2 offers Player 1 a choice of two numbers, one negative and one positive from the interval. Player 1 chooses one of the numbers. A “toy” version of the theorem guarantees that if Player 1 always chooses the number whose sign is the opposite of the current average, then the average of Player 1’s numbers converges to zero. Thus, as the number of rounds increases, the theorem guarantees that Player 1 will always be able to win the game. 

“In other words, no matter what the second player does, the first player has a strategy for pushing the average point to the origin,” says Vohra. More generally, the game applies to any situation where one player aims to encourage the average to converge to any number, not just 0, provided Player 2 always provides options on both sides of that number. The number might correspond to the number of dollars the player seeks to pay for some product, for example. 

Blackwell’s approachability theorem applies beyond the domain of scalar numbers in this game and applies to higher dimensions, where both players are choosing vectors rather than single numbers. Player 2 offers Player 1 a choice of two vectors, one from above a hyperplane depending on the current average, and another from below. The theorem offers Player 1 a strategy for nudging the average vector toward zero. In this case, Player 1’s target average vector might correspond to a payoff in multiple currencies. “You can think of the vector as the payoff not being just a few dollars, but five oranges, two apples, 27 bananas,” says Vohra. More generally, the theorem prescribes an algorithm for the first player to choose a vector each round that guarantees that the average will converge to the first player’s desired vector.

In fact, many modern technologies make use of Blackwell’s approachability theorem to operate. The theorem, for example, underpins a form of machine learning known as reinforcement learning. Researchers often use reinforcement learning to train robots to learn how to move autonomously. In reinforcement learning, the robot receives rewards when it behaves in a desired way, and it receives punishments when it does not. The robot’s learning algorithm can be thought of as a Blackwell game.

“Blackwell’s approachability theorem gives us a framework for decision-making in dynamic settings with very low information,” says Vohra.

Researchers are still finding new applications of the theorem. Negin Golrezaei, who works in operations research at MIT, has recently cast a common problem in online marketplaces in terms of this type of game. 

Say you are looking for a plane ticket on Expedia or a thermometer on Amazon. These online marketplaces want to quickly display a ranked list of products, where your desired product is somewhere close to the top, so that you do not become frustrated and leave the site without purchasing anything. 

Golrezaei and her collaborators made the choice of product in each position in the list into a Blackwell game. You can think of this game as having two players. The first player is the seller behind the website, trying to produce a vector whose elements correspond to the probability that a user will click on the product that the element represents. Thus, the vector has the same number of elements as products to be ranked. You can think of the second player as an agency that has a model describing the distribution of users and their propensity to click on various products. The second player samples users from this model and has them click on the products to challenge the rankings that the first player has chosen. Ultimately, Blackwell’s theorem provides a strategy for the first player to rank the products according to the likelihood that a user will click on each product.

Golrezaei says that other problems in operations research — optimizing prices for products, selecting which products to display in a supermarket, known as assortment planning — can also be cast as Blackwell games. “The Blackwell game framework gives a unified solution for all these applications,” says Golrezaei.

What is old is new again
The theorem’s ongoing relevance may seem surprising, given that Blackwell published it more than half a century ago. UC Berkeley’s Department of Statistics had just formed the year before, in 1955, with Blackwell as one of its 10 founders. At the time, much of Blackwell’s research was inspired by military-driven questions in the wake of World War II. “World War II required the Allies to think more carefully and more scientifically about how to deploy resources,” says Vohra. “It’s really the first time scientists were used in large numbers in a host of areas.”

Vohra gives some examples of relevant questions at the time. “If I’m hunting for submarines, and I have a limited number of ships, where should I put them? If you are testing large numbers of soldiers for venereal disease, do you test them individually, or do you test them in groups?” 

Problems in economics also influenced Blackwell’s work. In a 1986 interview, he recalled a visit from an economist working with the Air Force when Blackwell was working at RAND Corporation, the research nonprofit. The economist was looking to recommend to the Air Force how much of its budget to devote to long-term research versus short-term research. The recommendation depended on the probability of a major war occurring in the next five years, and Blackwell was unable to make a prediction to his own satisfaction. The interaction would inspire some of his work on probability.

But the mathematical insights from these questions had much wider significance beyond their original setting. “From these concrete problems, Blackwell would formulate more fundamental versions,” says Vohra. “And these he would then tackle.” 

Blackwell’s gift was to understand how to strip away irrelevant context to reveal the fundamental mathematical structure of a problem, says mathematician Richard Lockhart of Simon Fraser University, one of Blackwell’s PhD students. “It can seem like the theory that you’ve developed is specific to the context,” says Lockhart. But Blackwell found the core mathematics of these problems, which would then recur in settings beyond military planning.

Blackwell himself spoke of the circuitous journey through which mathematics research becomes more broadly useful to society. “When I have looked at real problems, interesting theorems have sometimes come out of it,” he said in 1983. “But never anything that was helpful to the person who had the problem. … But there is no doubt in my mind that you do get interesting problems by looking at the real world.” 

Whether or not Blackwell’s theorems were useful when he conceived them, they have a deep impact across society today, from operating online commerce to training artificial intelligence systems. On August 26, 2022, for the end of the Simons Institute’s Data-Driven Decision Processes Boot Camp, the workshop organizers dedicated a day to honoring David Blackwell’s life and work. “We were thinking about all the topics we wanted to cover and looking at the news,” said Siddhartha Banerjee, an operations research professor at Cornell University, one of the symposium’s organizers. “In terms of the intellectual contribution and societal impact … everything we were doing seemed to tie back to David Blackwell.” 

One of few
Blackwell’s legacy looms large not just for his mathematical contributions, but as a Black mathematician. His race is still an anomaly in the field of mathematics. In 2021, U.S. institutions awarded 4,373 doctorates in mathematics, statistics, and computer science, according to the National Science Foundation. Sixty-four of those, or 1.5 percent, went to Black individuals. 

Born in 1919, Blackwell grew up in Centralia, Illinois, and attended a racially integrated secondary school, although the town also had two racially segregated schools. Blackwell’s grandfather was a storekeeper with some college education, while his father had attended school up to the fourth grade. Blackwell spoke of having a supportive family that assumed he would attend college. He attended what was then the University of Illinois, now renamed the University of Illinois Urbana-Champaign, and received his PhD at age 22.

In several interviews, Blackwell described feeling insulated from racism in his early life. “My parents protected me from it [racism], and I didn’t encounter enough of it in the schools to notice it,” he said. 

However, stories from that era lay bare the disparity in treatment that Blackwell received, both professionally and at large, due to his race. In 1942, the chair of UC Berkeley’s Department of Mathematics, Griffith Evans, rejected Blackwell as a faculty candidate on account of his race. Evans’s wife, a Southerner, did not want to invite Blackwell over to their house for dinner. 

Mathematician Jerzy Neyman, another founder of UC Berkeley’s Department of Statistics, would later recruit Blackwell from his position as a professor at Howard University in Washington, D.C., to Berkeley in 1955. “When Neyman went to recruit him, they talked some math, and Neyman suggested they go to the movies,” says mathematician Peter Bickel of UC Berkeley, who coauthored a paper with Blackwell in 1967. “Blackwell said, ‘We can’t go to the movies together,’ because the movies were segregated in Washington. Neyman said, ‘Fine, let’s go to the movies you can go to,’ and they cemented their friendship that way.” (After Berkeley later hired Blackwell in 1955, the Evanses eventually did invite Blackwell and his wife, Ann, for dinner for “a very pleasant evening,” a 1996 history of Berkeley’s Department of Statistics reported.)

Blackwell would go on to work at UC Berkeley for more than three decades and retire in 1988. In addition to his research, Blackwell relished teaching: “In transmitting [knowledge,] you get to appreciate its beauty all over again,” he said in 1983. In 1965, he became the first Black man to be elected to the National Academy of Sciences. 

He died in 2010, and in 2012, President Barack Obama posthumously awarded him the National Medal of Science. “His ability to do clean, tight, exact mathematics was unparalleled,” says Lockhart. “He wrote famously short papers. They were incompressible. You cannot take a paper by David and safely delete a word.”

His pursuit of a problem’s fundamentals has led to the long shelf life of his work. “I’m not interested in doing research, and I never have been,” Blackwell said in a 1983 interview. “I’m interested in understanding, which is quite a different thing.”