Daedalus of Crete — who, according to Greek myth, designed the labyrinth that trapped the Minotaur — is one of the oldest symbols of human ingenuity, credited with the invention of the saw, the ax, glue, and the ship’s sail, among other things.
Constantinos Daskalakis, a recently tenured associate professor of computer science and engineering at MIT, comes from a Cretan family, and while it’s fanciful to suggest that the ingenuity of his work in theoretical computer science owes anything to the example of Daedalus, the problems he explores are undoubtedly labyrinthine.
Much of Daskalakis’ work concentrates on the application of computer science techniques to game theory, a discipline that attempts to get a quantitative handle on human strategic reasoning. Game theory models human interactions as a series of moves in a clearly defined game; each move represents an instance of a particular strategy and may elicit a different response from the other players, leading to different rewards. Even a simple game with only a handful of players can take vastly more twists and turns than the largest physical labyrinth.
Daskalakis’ parents are both from Crete, but they met in Athens, where they had come for college — his father to study mathematics, and his mother to study Ancient Greek literature and philosophy. Until he came to the U.S. for graduate school, Daskalakis lived in the greater Athens area — like one-third of the country’s population. “When you ask the question ‘Where are you from?’ in Greece, it has a different meaning than when you ask it in the States,” Daskalakis says. “In the States it means where you grew up. In Greece it means where your family originated from.”
Both of Daskalakis’ parents were teachers, and as a child, he showed an interest in and an aptitude for both of their disciplines. In junior high, however, he competed in the math Olympiad and finished second in the country. Though literature remains important to him — his MIT Web page features the complete text of a poem by the great Greek modernist poet Constantine Cavafy — from then on, he was marked as a student with exceptional mathematical promise.
Game theory
In Greece, every high school senior opts to take one of three sets of standardized tests, which determines his or her university placement. Daskalakis’ score on the technical exam was the fifth highest in the country, earning him a spot at the prestigious National Technical University of Athens. He enrolled in the five-year electrical engineering and computer science curriculum, the first half of which is spent canvassing a huge range of topics, from the physics of individual electrical components to the most esoteric questions in theoretical computer science.
“Sampling this big spectrum satiated my desire in the applied domain,” Daskalakis says. “I understood I could write a complicated program and then decided, ‘OK, now I know how to write a program. Let’s do math.’”
Daskalakis applied to and was accepted by graduate programs at several U.S. universities, and during his fifth year, he came to the United States to visit them. At the University of California at Berkeley, he was captivated by the computer scientist Christos Papadimitriou, a recipient of both of the Association for Computing Machinery’s major awards for theoretical computer science. Papadimitriou’s larger-than-life personality was celebrated in the bestselling 2009 comic book “Logicomix.”
“He’s a very inspiring person,” Daskalakis says, “and a founding father of the interaction between computer science and economics.”
After returning to Greece, Daskalakis chose to focus on that interaction for his undergraduate thesis. Game theory has been a staple of economics research since 1950, when John Nash, who taught at MIT from 1951 to 1959 and is the subject of the movie “A Beautiful Mind,” published the seminal paper that would ultimately win him the Nobel Prize in economics.
Every game has what’s called a Nash equilibrium, which describes a balance of strategies that no player has an incentive to change unilaterally. Daskalakis’ thesis investigated Nash equilibria for games that can be represented as highly regular networks of interactions. The paper was accepted to the 13th Annual European Symposium on Algorithms. “I still find it a very elegant piece of work,” Daskalakis says.
Intractability
In 2004, after graduating, Daskalakis moved to Berkeley, to continue his study of algorithmic game theory with Papadimitriou. Four years later, his doctoral dissertation won the Association for Computing Machinery’s thesis award.
In it, Daskalakis proves that computing the Nash equilibrium for a three-person game is computationally intractable. That means that, for any but the simplest of games, all the computers in the world couldn’t calculate its Nash equilibrium in the lifetime of the universe. Consequently, Daskalakis argues, it’s unlikely that the real-world markets modeled by game theorists have converged on Nash equilibria either.
“I have been blessed throughout my career with the most brilliant graduate students and collaborators, but Costis [Daskalakis] is different from all,” Papadimitriou says. “I had been working on what ended up being his thesis problem — the complexity of Nash equilibria — for more than two decades. In the fall of 2004, conversations with Costis, who, remarkably, had just started his first year of graduate studies at Berkeley, inspired me to give it another good push, and this ultimately led to an important result.”
During his last year at Berkeley, Daskalakis got a job offer from MIT, but he deferred it for a year to do a postdoc at Microsoft Research New England. “It was really a year for me to step back and think about what I want to do next before coming to MIT and being very busy,” Daskalakis says.
When computer scientists run up against an intractable problem, their first recourse is to investigate the tractability of approximate solutions to it. After his doctoral thesis, Daskalakis focused on importing notions of approximation from computer science into economics. First, he published several papers examining the computation of approximate Nash equilibria. Some of those results were disheartening: For general games, even relatively coarse approximations are still intractably hard to find.
Ideal auctions
Other problems in game theory, however, have proven more susceptible to analysis from a computational perspective. In 2012, after coming to MIT, Daskalakis and his students solved a30-year-old problem in economics, a generalization of work that helped earn the University of Chicago’s Roger Myerson the Nobel Prize in economics. That problem was how to structure auctions for multiple items so that, even if all the bidders adopt strategies that maximize their own returns, the auctioneer can still extract the greatest profit.
Since then, Daskalakis’ group has taken on topics in computational genetics, probability theory, and machine learning. They’ve also been working to generalize their results on auction design. “The computer science aesthetic is, ‘Given a problem, I am looking for an algorithm that solves instances of this problem,’” Daskalakis says. “The economics aesthetic is, ‘Given a problem, I want to understand the structure of the solutions to different instances of this problem. I want to be able to make universal statements about the structure of these solutions.’ Working at this interface of economics and computation, you have to balance the two aesthetics. Now we’re trying to import more of that economics aesthetic into our work.”
“To do that,” Daskalakis adds, “it turned out we had to develop new tools in the field of mathematics called optimal transport theory,” which examines the most efficient way to move objects — or data — between multiple origins and destinations. The labyrinthine path that Daskalakis started down as a senior in college continues to branch in unexpected ways.
