Game-theoretic environments are those in which two or more agents interact, and agents' desires cannot be relied upon to coincide. Examples include the housing market, a game of poker, a morning commute, and the United Nations. Lately, computers have started to feature in such environments too: large-scale distributed systems like the internet are becoming ubiquitous, and in such systems users cannot simply be trusted to behave responsibly. At the same time, there is a recent trend for markets to move online and to become more complex, in the process encountering computational obstacles. For both of these reasons, game theory has moved in the last decade from being the province of theoretical microeconomists (along with a smattering of political scientists, psychologists, operations researchers and philosophers) to being a major research area in computer science.

Here's a very short summary video introducing my work to a broad audience.

Here's the video of an overview technical talk in which I discuss my research in this area.

My work in game theory can be grouped into two main lines of inquiry. First, I investigate the design of protocols with desirable properties. When applied to the problem of resource allocation, such protocols are termed auctions. With my collaborators, I was among the first to investigate the computational problem of determining the winners of combinatorial auctions—a complex auction type in which bidders can request indivisible bundles of goods, of substantial interest for the allocation of radio spectrum. We proposed two novel algorithms and designed a test suite that has become a de facto standard. Separately, we have shown how bidders can compensate for "hidden bids" in online markets such as eBay. In theoretical work, we have proven that virtually all dominant-strategy combinatorial auctions can improve revenue by denying participation to certain bidders, constructed a novel protocol for collusion in single-good auctions, and shown how bidders' uncertainty about their own valuations impacts their bidding behaviour. Beyond auctions, we have considered how incentives can be used to obtain good system behaviour in computer networks. Most significantly, we wrote what I believe was the first paper demonstrating the usefulness of game theory for analyzing P2P file-sharing systems.

Second, researchers have long been interested in answering game-theoretic questions computationally. However, naive representations of simultaneous-move games scale exponentially in the number of players, and previously-existing compact game representations do no better than the naive approach for many game theoretic settings of interest. We proposed a novel game representation and gave an algorithm that provides provably-exponential speedups to equilibrium finding algorithms. We also leveraged this representation to provide the first quantitative, equilibrium-based comparisons between Google and Yahoo's auction designs.

Despite substantial progress in game theory research over the last decade, significant gaps still exist between theory and practice. For example, game-theoretic models are typically very small and built on the assumptions that agents are omniscient and utility-maximizing. Even if such an agent did exist, most current theories would not tell her how to reason about more limited competitors. Approaches to resource allocation usually assume that goods for sale cannot be resold and are unique, that agents face no transaction costs or budgets, that markets can be redesigned without any constraints, and that agents know their valuations for the goods being allocated. My current research on multiagent systems focuses on developing new theoretical approaches to better model such practical settings. For example, I've recently initiated a research project that aims to build computational models of real human behaviour in strategic situations, starting with existing models from the "behavioural economics" literature in economics and cognitive psychology, and extending and evaluating them using techniques from machine learning and statistics.

Sophisticated computer systems are becoming integrated into almost every aspect of human life. Examples include the operation of the stock market, decisions about where to open new hospitals or where police should patrol, the design and testing of drugs and airplanes, the creation of movies and works of art, and the optimization of power usage in a smart building or a hybrid car. In each case, the quality of the results depends on complex algorithms created by computer scientists and engineers. It is therefore important to analyze algorithms' behaviour to understand how effective they will be in novel situations. The formal description of an algorithm and its practical realization are one and the same—i.e., algorithms are their own models. Hence, the main school of thought holds that they are most appropriately analyzed theoretically. However, when faced with large, real-world problems, it is often the case that cutting-edge algorithms' behaviour defies closed-form analysis beyond trivial, exponential worst-case running time bounds. Such algorithms nevertheless often exhibit excellent performance in applications, and hence are widely used. I therefore believe that theoretical analysis of algorithms should be supplemented using the same empirical and statistical approaches that are used to study natural phenomena.

To give one example, I've pioneered the idea of using machine learning techniques to model an algorithm's empirical runtime variation. My collaborators and I have focused on building empirical hardness models: statistical models that can predict the amount of time a given algorithm will take to solve a given problem instance. We've shown that such models can reliably make very accurate predictions of algorithm runtime on novel problem instances, and can be analyzed to explain runtime variability. These models can also be applied to the construction of algorithm portfolios by selecting the best among a set of algorithms on a per-instance basis. Notably, one such portfolio we designed ("SATzilla") performed outstandingly well at the past two International SAT Competitions, winning medals in five out of nine categories each time. The paper describing SATzilla was also recognized as the best paper published in the Journal of Artificial Intelligence Research over the previous five years.

SATzilla can be understood as a meta-algorithm—an algorithm that takes other algorithms, rather than just data, as its input. Meta-algorithms are an appealing idea because they offer the prospect of problem-independent, automatic methods for improving the performance of arbitrary algorithms; they are hence the focus of my current research. One fundamental problem is the configuration of algorithms with high-dimensional parameter spaces. Indeed, when this parameter space is specified broadly enough, algorithm configuration becomes another way of thinking about algorithm design. My collaborators and I have built the world's most effective algorithm configurator, a local search algorithm called ParamILS. We are now working to rival ParamILS' performance through an alternate approach based on response-surface models from statistics; this work has already yielded two best paper awards. We have also recently worked to combine algorithm configuration with algorithm portfolios, developing a method for automatically building a set of uncorrelated algorithms and a method for choosing between them, starting with just a single highly parameterized algorithm. What follows is an ICML tutorial on algorithm configuration, given with Frank Hutter (but not with Benjamin Recht, regardless of what the title slide generated by ICML may say :-)