by Caitlin Hayes for Cornell Research
We’re familiar with the most dramatic version of the chicken game—where two cars hurtle toward each other on a collision course, and the driver who swerves loses. What is the best strategy in this situation, when both drivers want to avoid collision yet prefer not to steer away?
This kind of game models the situations Éva Tardos, Computer Science, is thinking of in her research in the field of game theory. “When I say game, I don’t mean something like chess, with many complicated moves,” she says. “The moves we consider are simpler, but like players in chess, you want to find a solution that’s good for you, and I want a solution that’s good for me, and those solutions are in conflict.”
Modeling Self-Interest Interactions as Games
These types of games, where the users’ self-interest results in conflicts, have been used to model many real-life situations. Political scientists use them to model conflicts in politics. Economists use them to model economic interactions—how people choose jobs or buy or sell products based on their needs.
“The interest in these games in computer science arose from modeling the modern, interconnected world, where my computer interacts with the internet and your computer does, too, and we need to think of computers making these kinds of selfish decisions,” Tardos says. “When we want to get information from the web, we want it as fast as possible, and we don’t pay attention to how this may impact others.
“We model these interactions as games,” Tardos continues, “and we try to understand how the system will perform given that we (or our computers) are all optimizing for ourselves. An important question to ask is this: can we modify how the system is set up to make it perform better, despite the selfish actions of the users?”
Routing Traffic—Car or Data—and a Global Approach
One area Tardos models is systems of traffic routing—the traffic of actual cars or data on the internet that travels (in packets) from websites to your computer. In the example of car traffic, the aim of the driver is to get to the destination in the quickest way possible, without regard for how the driver’s actions affect others.
Classical algorithms for traffic routing would optimize traffic by telling drivers (or packets) what route to take. However, there is no centralized or global agency in these situations that controls the decisions of each driver or the routers that send data to your computer. “So classically, with algorithms, you have a bunch of input and some machine processes that input and tells you how to optimize,” Tardos says. “In this case, there is a bunch of separate humans or routers making decisions, but they all affect each other as part of a global system.”
Tardos works on understanding outcomes in these types of systems. One of her primary questions is to what extent selfish choices actually slow a system down. “When we are all optimizing for our own objective, that may or may not be the right thing to do from the global perspective,” she says. “There may be solutions that are better for each one of us.”
This issue is exemplified in the prisoner’s dilemma, a foundational model in game theory. In the prisoner’s dilemma, two criminal accomplices in separate cells are given the option to either cooperate with police by giving incriminating information about the other prisoner or cooperate with their fellow criminal by staying silent. The possible outcomes are set up so that a criminal, acting in his own self-interest, is better off helping the police no matter what the other prisoner does. By doing so, the criminals both end up in prison longer.
“There are similar traffic-related examples,” Tardos says. “If it benefits me to drive on one road, it may do some damage to many others by causing congestion and vice versa. We can both be better off if we don’t do what appears to be the best thing for ourselves and instead avoid that route.” This idea could lead to structural improvements in our traffic routing systems. Along these lines, Tardos has connected her research to Braess’ Paradox, developed by German mathematician Dietrich Braess, which presents an example where, if you close a main road, everyone gets to their destination faster.
How Does a System Evolve Due to Learning?
Recently, Tardos has been interested in a question that complicates the already difficult problem of traffic routing: what happens day after day, as people or machines learn and evolve to change their behavior?
“Some set of people are doing this commute every day, or on the internet, every 10 seconds, and the system tries to learn from past performance what might be good to do next,” Tardos says. “Understanding how the system evolves due to this learning is something many researchers in my field are thinking about.”
Finding better algorithms for the machine learning that goes on in the background—as routers or GPS try to find the best route—is one goal. Then another challenge is developing a model that can incorporate new data and predict the evolution of the entire system. “Do we have better algorithms that might give us better ways to learn? And what happens to the system if most people are participants who are learning?” Tardos asks.
To improve machine learning algorithms, Tardos is currently working on how to deal with a classic trade-off—between knowing information about a past route and having information about alternative routes. “There is always this trade-off of taking advantage of what you’ve learned in the past versus making sure you’re exploring and learning enough for the future,” Tardos says. “We are trying to find the right way to do this in evolving situations.”
Tardos says incorporating the idea of learning is necessary to model anything that resembles the real world. Especially in the case of packets on the internet, the system is incredibly dynamic, with new or different users and current events constantly impacting the traffic patterns. For many years, game theorists were focused on stability: finding and understanding the Nash equilibrium, where every user is content with their decision or strategy, given everyone else’s decision. “But life isn’t stable,” Tardos says. “Learning is better at adapting to the changing world. In a changing world, we cannot have a system that is stable but can have something that adapts.”
Computer Science at Cornell—Theoretical and Applied, Collaborative and Diverse
Tardos’ degrees are all in mathematics, but when she came from Hungary to the United States for her postdoctoral work, she was drawn to the expansive possibilities and applications in computer science. “The breadth of interest this community has and the breadth of applications they’re thinking about was and is really appetizing,” she says.
Cornell’s computer science department appealed to her because of its friendliness and collaboration as well as the integration of theoretical and applied approaches. “Before I came to Cornell, I’d always lived in big cities, so Ithaca was not entirely natural,” Tardos laughs. “But the computer science community was so attractive. It’s not like silos where everyone works on their own things and never talks to their neighbor, but a department where quite often we have lunch together informally, and you hear about what’s going on in others’ research.”
Tardos also values the department’s commitment to increasing diversity in computer science. She serves as faculty adviser for Women in Computing at Cornell (WICC), an undergraduate support group for women majoring in computer science, as well as a newer student group, Underrepresented Minorities in Computing (URMC). With the help of WICC and the department’s efforts, the number of women majoring in computer science at Cornell has risen from barely above 10 percent in the early 2000s to above 30 percent today, making Cornell one of the leaders nationally.
“The fact that we’re above 30 percent women is a big change, and it feels so much better,” Tardos says. “We’ve worked very hard, and we want to be even more welcoming both for women and minorities, because there are so many cool opportunities in computer science, so many fun things you can do.”