Mehta Earns NSF CAREER Award, Will Target Research on Equilibrium Computation

Illinois Computer Science Assistant Professor Ruta Mehta has won a National Science Foundation CAREER Award, which she plans to use to explore fundamental unresolved questions around equilibrium computation, problems that sit at the intersection of theory and practical applications in economics, cryptography, and other areas.

Mehta hopes to develop a stronger understanding of a class of problems that lie in NP intersect coNP. NP is the set of problems that have hard-to-find solutions and efficiently verifiable proofs, while coNP is the set of complements of the problems found in NP. Both NP and coNP are extensively studied and well-understood, but their intersection is not.

“There is a huge number of important problems within NP intersect coNP that are open for 50 or 60 years by now and they are not yet well understood,” she said. “These problems come from diverse fields like game theory, economics, cryptography, verification. We do not understand how hard these problems are relative to each other, or individually.”

The work, Mehta believes, will yield new tools for approximation algorithms and for beyond-worst-case analysis of equilibrium computation. And while her research is theoretical, equilibrium computation has a central role in everything from markets such as eBay to social networks and road systems.

“It goes with any system design. You set up the rules, then people are going to interact with those rules—then what happens?” she said.

With the five-year, $499,900 award, she plans to build on her already deep experience creating algorithms for a range of game and economic-market models, settling in some cases unanswered questions that had stood for years. In the process she plans to provide a large group of new game models and develop tools to find connections between problems from those disparate fields.

The tools she hopes to develop would be major improvements on currently available algorithms for, say, analyzing data from the users of social networks.

“Suppose you are a designer of a system, say a review system, or a social network, etc. It is important for you to understand what kind of rules/design will lead to an efficient system in a long run—when system would stabilize,” Mehta said.

With the award, Mehta also hopes to delve deeply into beyond-worst-cases analysis. Worst-case analysis measures the computational resources required to perform an operation in the worst case, but the realm beyond that threshold is both relatively unexplored, she said.

“Currently we are saying that you cannot solve these problems if the input is worst-case, but the real-life data is rarely worst-case if at all,” she said.

To complete the project, Mehta plans to train graduate and undergraduate students to help at various points over its life, and use mentoring workshops and other existing university initiatives to involve students from underrepresented groups.

Mehta came to Illinois Computer Science in 2016 after a postdoctoral fellowship at Georgia Tech and UC Berkeley. She completed her PhD at the Indian Institute of Technology, Bombay.

The NSF’s Faculty Early Career Development Program gives the CAREER Award to junior faculty who show the potential to be role models in research and education.