A Poet of Computation Who Uncovers Distant Truths

Rejecting the Satrapy

Athenians never say they’re from Athens unless their family has been there for many generations, said Daskalakis, who was born there. Instead, they say where their grandparents are from. For Daskalakis, that was Crete.

Constantinos (or “Costis,” as most people call him) spent his childhood summers there, soaking up the island’s distinct culture. Cretans have always been “troublemakers” when their freedom was taken away, Daskalakis said — they fought back vigorously against occupation by the Ottoman Empire and later the Nazis.

These heroic stories deeply influenced the young Daskalakis. “It’s not just the tales of the culture but also, like, feeling it in the atmosphere,” he said. “The proud mountains of Crete … this beautiful color and sea and landscape.”

Daskalakis is something of a proud mountain himself, with imposing features and an unruly mane of black hair atop a powerfully built 6-foot-1 frame. But his face is softened by his mild, dark eyes. He and his younger brother, Nikolaos, both consider him to be the “calm” one. “He’s a very sweet person… a very peaceful type of character,” Nikolaos Daskalakis said.

But that serene nature didn’t stop him from defending Nikolaos with his fists on more than one occasion when they were beset by bullies on the streets of Athens as teenagers. “He was very protective of me,” Nikolaos said.

At home, the two brothers would embark on one project after another — delving into their father’s math texts, creating comic books, or trying to derive Kepler’s laws of planetary motion. Daskalakis’ gentle disposition coexisted with an intense desire to understand the world around him. When he was in third grade, his father brought home an early Amstrad computer, and Daskalakis stayed up all night trying to figure out how it worked. “I told my parents, ‘I know I have to go to bed, but this is very important,’” he said. “They let me stay up.”

As Daskalakis made his way through high school and then undergraduate studies in electrical and computer engineering at the National Technical University of Athens, it quickly became clear that he was an extreme outlier. He earned perfect scores in all but one of his undergraduate classes, a feat never before achieved in the university’s nearly 200-year history. “Every teacher you will ask about Costis will remember him, even 20 years afterwards,” said Alexandros Dimakis of the University of Texas, Austin, who was Daskalakis’ schoolmate in both undergraduate and graduate school.

Daskalakis could easily have landed a well-paying job after college, as most of his classmates did. It was 2004, and the Greek economy was booming: The nation had adopted the euro a few years earlier and was now gearing up to host the summer Olympics. But Daskalakis never considered seeking such a job. “I was looking for opportunities to do something creative,” he said.

He had found his undergraduate studies mostly uninspiring, but a 2003 summer program organized by the Onassis Foundation had given him a glimpse of a very different approach to learning. The program centered on the relationship between computer science and economics, and the foundation had attracted several luminaries to deliver lectures. “I didn’t have access to this kind of people,” Daskalakis said. “It was an eye-opening experience.”

One lecture by the theoretical computer scientist Christos Papadimitriou made an especially deep impression on him. It discussed, among other things, the problem of computing a Nash equilibrium, one of the central concepts in game theory and economics. “Little did I know that this would be my Ph.D. dissertation,” Daskalakis said.

Originated by the mathematician John Nash, the subject of the best-selling book and feature film A Beautiful Mind, the Nash equilibrium represents the most stable (and in some ways the most sensible) behavior players in a strategic game can choose. Players are at a Nash equilibrium if they’ve each chosen a strategy and none of them could have improved their lot by switching to some other strategy, given what the other players chose to do. In 1950, Nash proved that every game has a Nash equilibrium.

Nash’s theorem launched the modern field of microeconomics “by allowing any economist, when contemplating some institution or market or mechanism, to sit back and think, ‘OK, let’s see what happens at equilibrium,’” said Papadimitriou, now a professor at Columbia University.

But while Nash could prove that an equilibrium always exists, his proof gave no way to find it. For complicated games, finding a Nash equilibrium might be an enormous computational challenge — and if a Nash equilibrium is impossible to compute for all practical purposes, does it even make sense to envision players finding and using its strategies? “If [a Nash equilibrium] requires the lifetime of the universe to solve, you cannot claim that you have it,” Papadimitriou said.

In the decades after Nash’s proof, researchers tried but failed to find an efficient algorithm that would compute Nash equilibria for all possible games. By the time Papadimitriou gave his lecture at the Onassis Foundation, he was convinced that the reason for this failure was that no efficient algorithm exists.

Papadimitriou had been studying the problem of computing Nash equilibria for two decades, but he couldn’t prove this conjecture. “Frankly, deep down, I didn’t expect to solve it,” he said.

“Many people viewed it as the biggest open question in algorithmic game theory,” said Tim Roughgarden, a computer scientist at Stanford University.

Fascinated by Papadimitriou’s lecture, Daskalakis ultimately decided to apply for graduate school at the University of California, Berkeley, Papadimitriou’s institution at the time. A few hours after he dropped his application in the mailbox, he ran into Papadimitriou on the street in Athens — the first time they had seen each other since the summer lectures half a year earlier. “It was very crazy,” Daskalakis said. “What’s the chance of that?”

The pair exchanged little more than a nod of greeting, but it felt like a “fateful moment,” Papadimitriou said. “We looked at each other, and I think we both knew that he would be admitted [to Berkeley] and he would be my advisee.”

“I’m not sure I believe in signs,” Daskalakis said. “But it was a very important encounter.”

The Inestimable Well Done

Daskalakis moved to Berkeley in the fall of 2004. With its olive trees and Mediterranean climate, it offered perhaps as smooth a transition from Greek life as any American city could have afforded, as well as the intellectual stimulation he had been craving. “The sense of possibility that I got was inspiring and mind-blowing,” he said.

Daskalakis and his old friend Dimakis moved into a one-bedroom apartment — the most they could afford in Berkeley’s overheated housing market — and used a fair division algorithm to decide who should get the bedroom and who the living room, and at what price. Daskalakis won the bedroom but often ended up in the living room anyway, pulling all-nighters doing problem sets with Dimakis while his then-girlfriend slept in the bedroom.

Daskalakis had an indefatigable intellectual energy, Dimakis said. Once, Dimakis recalled, the pair went skiing at Lake Tahoe, and afterward Dimakis was so tired he could hardly move. But Daskalakis started thinking about some problem, and soon he was eager to discuss it — even though it was midnight. “I’m like, ‘Man, I’m exhausted,’” Dimakis said.

Over the years, Papadimitriou had tried the Nash equilibrium problem on several of his most talented students, but to no avail. Daskalakis, however, embraced it eagerly. “I was looking for something challenging,” he said.

Soon, Papadimitriou felt a sense of motion on the problem that he hadn’t felt in years. “It was as impossible as ever, but I had the feeling that we were hitting new walls, not the old walls.”

Daskalakis had a key insight just weeks into thinking about the problem. One evening, he thought he had figured out how to solve the entire thing. Elated, he went out to a bar in San Francisco with his friends “to live this happiness before I realize if there are any bugs.” The next morning, however, he woke to the realization not only that his proof was wrong, but that no proof along the lines he’d been attempting could work. But the error morphed into an important advance, for Daskalakis simultaneously realized what kind of proof architecture should work: one that had a similar kind of circular structure to the one Nash himself had used in proving his theorem.

It would be months before Daskalakis and Papadimitriou figured out how to combine this insight with another line of work by Papadimitriou and Paul Goldberg, now at Oxford University, to arrive at a complete proof. By the summer of Daskalakis’ first year of graduate school, however, they had managed to crack the problem for all games with four or more players. Their work “shows that under very reasonable complexity assumptions, you need an insane amount of computation to compute a Nash equilibrium,” Roughgarden said.

The three researchers hoped it might be possible to extend their result to three-player games, and Daskalakis tackled the problem with his customary enthusiasm. But it proved a struggle, and one day, after thinking about it hard, Daskalakis felt ready to give up, at least for the time being. He turned on his laptop to check some emails, but the laptop crashed. As Daskalakis waited out a lengthy scan of the hard drive, he turned his attention back to the three-player problem — and in an instant he knew how to solve it. In retrospect, he realizes that he must have already solved the problem in some inaccessible part of his mind. “It was right in my brain, but yet I was not aware of it.”

Many of Daskalakis’ insights seem to come in these liminal moments — as he wakes up in the morning or waits for a laptop to reboot, or when he’s in the shower or ill with a fever. “Usually I have good ideas when jetlagged,” he said.

Pencil-and-paper calculations have their role, he said, but only after the initial insight. They’re useful, he said, for when “you want to see whether some intuition that you have in the subconscious can be actually formalized and taken out of your soul and, you know, expressed in mathematics.”

Daskalakis’ solution to the Nash equilibrium problem brought him instant fame within the theoretical computer science community. And in 2008, when he was awarded the Association for Computing Machinery’s Doctoral Dissertation Award, that fame percolated out to the general Greek public. After a blog post about his award went viral, the president of Greece invited him for a visit, and documentaries about him aired on Greek television again and again.

“He’s basically a rock star in Greece,” Roughgarden said. He remembers once accompanying Daskalakis to a Greek restaurant in Boston that featured live musicians. When Daskalakis went over to compliment them after their set, one of the musicians replied that he’d had trouble concentrating with Daskalakis in the audience. As Roughgarden recalled, the musician said, “I’m trying to play the song and I look to my left, and I say, ‘Oh my God, that’s Costis Daskalakis.’”

Daskalakis attributes his celebrity status in Greece to the national frame of mind at the time he received his award. The global recession had just hit Greece with devastating impact, and Greek society was trying to come to terms with the value system that had brought the country to its knees — the corruption, the seeking after satrapies. “I feel like they latched upon myself, upon my success, to say, look, Greece is not just this corrupt construct that is about to collapse,” he said. “There is also a very healthy and very talented part of Greek society who is really trying to find escapes, to be creative and to be successful.”

Fine and Great Works

After his triumph in graduate school, Daskalakis wondered if he would ever do work of the same caliber again. “You feel like, a lot of people that are scientists have one big result in their career,” he said. “Was this mine?” But he felt no impulse to chase after fame. “I still had interesting problems,” he said. “Sometimes, you just keep working on the problems that are important for you.”

Daskalakis soon became a professor at MIT and started advising graduate students of his own. Weinberg, one of his first students, recalls coming to Daskalakis’ office proposing to work on improving the numerical factors in a paper he had just read. “I remember he politely said, ‘OK, that’s good, but I think we should be a little bit more ambitious,’” Weinberg said.

In this case, that meant tackling a problem that had seen essentially no progress in 30 years. In 1981, Roger Myerson, an economist now at the University of Chicago, had solved the problem of how to design a single-item auction to maximize the seller’s revenue, an achievement that helped earn him a Nobel Prize in economics.

But many transactions involve multiple items — food choices on a restaurant menu, for example, or slices of the electromagnetic spectrum to be auctioned off to cell phone providers. In these settings, there are many more potential auction structures than in the single-item case, since the items may be sold separately or in a vast array of different possible bundles. In terms of the difficulty of understanding their structure, there’s a huge chasm between single-item auctions and multi-item auctions, Roughgarden said. “Things get much, much harder.” For decades, no one could come up with the optimal design in this broader setting.

Then in 2012, Daskalakis and Weinberg, together with another of Daskalakis’ students, Yang Cai, developed an algorithm that can efficiently find the optimal auction design regardless of the number of items being sold. And over the next couple of years, Daskalakis and two more of his graduate students, Alan Deckelbaum and Christos Tzamos, pushed this analysis further in the case where there’s only one buyer (for instance, an individual choosing among different cell phone packages). In that setting, Daskalakis and his students were able to characterize, for any selling mechanism, the exact settings in which that mechanism will be optimal.

“Many economists were working on that problem,” said Dirk Bergemann, an economist at Yale University. “They all were quite impressed by these results.”

More recently, Daskalakis has been using high-dimensional statistics to study the theoretical foundations of machine learning. In particular, he has been pursuing an approach to machine learning called generative adversarial networks, which uses game theory to train a neural network by setting it in competition with a second neural network with which it is playing a game. And, coming full circle, he has launched a research project with his brother, who is now a neuroscientist.

Last year, Nikolaos Daskalakis obtained a faculty position at Harvard Medical School, fulfilling the brothers’ long-cherished goal of living in the same city. Their Boston colony includes Nikolaos’ two-year-old daughter, to whom Costis is a doting uncle and godfather. “He takes it very seriously,” Nikolaos said.

Lately, the brothers have started exploring the use of mathematical models to identify the causative genes for various neuropsychiatric disorders. “I use mathematics because I want to solve problems,” Nikolaos said. “He’s thinking about what are the boundaries of the capabilities of mathematics — very theoretical concepts. But then if we find a problem that is interesting for both of us, maybe it’s a very important problem.”

The brothers have different bodies of knowledge, Costis said. What makes the collaboration work, he said, “is that we both care very deeply about putting together our two fields.”

Between tending to his students, traveling to conferences, and visiting his extended family in Greece, Daskalakis scarcely has a moment to call his own. During a Quanta Magazine interview at Northwestern University, where he was attending a two-month workshop, whenever there was a break he whipped out his cell phone to call one of his graduate students. Daskalakis and his students were getting seven papers ready for a conference deadline later that week, and his fiancée, Alexandra Courcoulas — an art history graduate student at MIT — predicted that another all-nighter was in the offing.

It’s an intense life, but Daskalakis wouldn’t trade it for anything. “It ultimately boils down to being genuinely interested in stuff, and not feeling it as a burden to think about it,” he said.

And “The Satrapy” is always there to remind him of “the noble reasons why I started pursuing my interests,” he said. “You have to not forget where you started, and what brought you here.”

Correction: This article was revised on August 9, 2018, to reflect that Daskalakis’ father brought home an early Amstrad computer when Daskalakis was in third grade, not eighth grade.