A Stronger Foundation

In 1994, mathematician John Nash won a Nobel Prize for proving that certain types of games achieve equilibria, where no single player wants to shift strategies. Since the 1950s, Nash’s insight had defined how economists conceived of competing interests.

Thirteen years ago, computer scientist Professor Christos H. Papadimitriou (working at UC Berkeley with his then PhD student Constantinos Daskalakis and visiting scholar Paul W. Goldberg) proved that these equilibria are essentially unknowable: According to current understanding of computational complexity—how mathematicians predict computational difficulty, from simple to hard to impossible—some equilibria promised by Nash’s theorem cannot, in reality, be reached. Without knowing when Nash equilibria actually come into play, Papadimitriou says, “an important theorem that started modern economics is essentially an illusion.”

Ultimately, Nash’s equilibrium slipped the bounds of its original application, profoundly influencing ideas in political science, evolutionary biology, and computer science. In our age, artificial intelligence has done the same, showing huge promise across numerous areas: driving cars, detecting cancer, translating languages. But so too have some deep cracks emerged at its theoretical base. Beneath the impressive applications, researchers at work on the foundations of AI are not only building better and faster general-purpose algorithms but also carefully reassessing the ones we have. Such exploration can lead to the next generation of game-changing apps. It can also illuminate and correct pitfalls at the heart of how today’s AI does business.

For many, that means tackling algorithmic bias. Papadimitriou, in collaboration with fellow Columbia Engineering Professor Tim Roughgarden, is working to make algorithms fundamentally fairer, using methods that include training them with synthetic data and using them to automatically identify populations that face discrimination.

To do that, the two faculty members are coming at the challenge from angles of complementary expertise. Papadimitriou studies algorithmic game theory, analyzing the way players—people or programs—compete and cooperate in various situations.

Understanding complexity and leveraging interdisciplinary insights form the basis. “We’ve been trying to understand economics through computation, and through both, to understand the internet,” he says. “We see the internet as a huge jumble of intertwined interests that interact in complicated ways.”

Roughgarden, who designs systems to reorient self-interested agents toward the common good, has been reexamining how computer scientists go about picking the best algorithm for a given task. It’s a two-pronged issue: First, you need to confirm that your algorithm will work as predicted. Then, you need to determine whether you’ve done enough research to put your data into the right context.

Performance is often measured by testing the worst case or an average case. Roughgarden studies something called smoothed analysis, which takes problems, tweaks them slightly, and tests algorithms against them. This measure is more practical than the worst case and more reliable than an average case. He’s developed a new killer app for smoothed analysis: predicting the performance of machine learning models, like neural networks.

Meanwhile, by applying statistical learning theory to online auctions, like the ones Google and Facebook use to sell ads, his methods can home in on how many previous auctions need to be looked at to set a fair reserve price for a future auction. “The goal is to have a more nuanced way of talking about algorithms,” he says.

Together, Papadimitriou and Roughgarden are studying the interplay of AI and human behavior. One challenge is how to better define desirable behavior for an algorithm so that people won’t game it, such as by signing up for extra credit cards just to boost credit scores. They also plan to look at exchanges between users and platforms like Facebook and Gmail. In return for convenience or entertainment, users provide personal information, which such services autonomously mine to tailor ads. Roughgarden and Papadimitriou hope to elucidate exactly how those algorithms are indebted to users for their training.

If work in AI has seen one ever-growing trend across the board, it’s scale, as data and the processors to parse it expand exponentially—so much so that many problems can no longer be solved with one computer. Distributing them across a cluster comes with a unique set of challenges. “Basically, one has to rethink all the algorithms,” says Clifford S. Stein, professor of industrial engineering and operations research and computer science, who focuses on oversized problems using clusters.

One area of specialty is graphs, or data structures comprising nodes and links between the nodes. They can represent social networks, molecules, kidney exchanges, school-choice preferences, computer networks, or road maps. Say someone wants to find the distance from A to B using Google Maps. The entire road graph might be spread across many computers and hard to manipulate. Stein’s system might first create a sparse representation of the road graph to compute the approximate distance, and then refine it.

Given that algorithms are used to study and improve algorithms, improving AI’s foundations leads to a virtuous cycle: Better AI begets even better AI.