I study two broad areas: competitive multiagent systems and empirical algorithmics. Both can be described as subareas of artificial intelligence, though both make interdisciplinary connections to other fields. Although there are overlaps between them, they are studied in essentially distinct communities and deal with substantially different subject matter.

 

Competitive Multiagent Systems

Competitive multiagent systems are environments in which two or more self-interested agents interact. It is this ingredient of self-interest that makes a multiagent system "competitive": agents' desires cannot be relied upon to coincide. These systems are studied by an interdisciplinary coalition of researchers drawing heavily on computer science and theoretical microeconomics. The topic has interested economists since their discipline began, because self-interested interaction is fundamental to markets and other economic settings. Computer scientists are motivated by the importance of large-scale distributed systems in which users cannot be trusted to behave responsibly, and by the recent trend for markets to move online and to become more complex, in the process encountering computational obstacles. The primary formalism used to describe competitive multiagent systems is game theory.

My main contributions to the area concern computational game theory, incentives in networks, and auctions. (All discussion of specific papers is written in the first person plural, in order to emphasize contributions made by my coauthors. For details about coauthorship, please see my publications page.) A summary of each of these contributions follows.

 

First, I study computational game theory, focusing on the design and analysis of algorithms for computing equilibria in large games. Notably, we proposed a novel, compact representation for large game-theoretic interactions. Technically, it emphasizes context-specific independence over strict independence; the latter is the typical structural feature exploited by compact representations in game theory and beyond. We have given representation theorems showing that our representation subsumes most existing game representations, and algorithms that can allow important quantities (e.g., Nash equilibria) to be computed exponentially more quickly than the previous state of the art.

Second, I have helped to show how incentives can be used to obtain good system behavior in computer networks. Most significantly, I coauthored what I believe was the first paper demonstrating the usefulness of game theory for analyzing P2P file-sharing systems. This has now become a popular area of study; see, e.g., the series of Workshops on the Economics of Peer-to-Peer Systems, now merged into NetEcon.


Auctions are perhaps the most broadly-fielded application of mechanism design, and indeed of game theory. They are widely used by governments, corporations and individuals, the last especially because of the recent rise of electronic commerce. We proposed two novel algorithms for determining the winners of combinatorial auctions—a complex auction type in which bidders can request indivisible bundles of goods—and designed a widely-used test suite.


Finally, in theoretical work on auctions, 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 the impact of bidders' uncertainty about their own valuations on their bidding behavior. In experimental work on auctions, we have shown how bidders can compensate for "hidden bids'' in online markets such as eBay, and identified novel equilibria of the advertising auctions run by search engine companies.

My current research on multiagent systems focuses on developing new theoretical approaches to address significant gaps that 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 (i.e., they are available only in the one-shot market being designed), that agents face no transaction costs or budgets, that markets can be redesigned without any constraints, and that agents know their own valuations for the goods being allocated. In practical settings of interest, many or even all of these assumptions can fail to hold.

Empirical Algorithmics

Despite the fact that algorithms are human artifacts, I believe that their theoretical analysis should be supplemented using the same approaches that are used to study natural phenomena. This is justified by the tremendous complexity of cutting-edge algorithms' behavior when faced with large combinatorial problems, which almost always defies closed-form analysis. Nevertheless, algorithms often exhibit excellent typical-case performance, and are widely used in cutting-edge computing applications. My research adopts an empirical approach, conducting very large, carefully-controlled computational experiments to investigate the empirical behavior of state-of-the-art algorithms for solving hard combinatorial problems. One interesting phenomenon is that, while state-of-the-art algorithms dramatically outperform worst-case bounds, they also exhibit enormous variability in runtime, even on fixed-size problem instances.

One big idea I've pursued is that machine learning techniques can be used to explain an algorithm's empirical runtime variation, based on huge bodies of experimental data. We have focused on building what I call empirical hardness models: statistical models that can predict the amount of time a given algorithm will take to solve a given problem instance. We have showed how to build models that reliably make very accurate predictions of algorithm runtime on novel problem instances, and how to analyze these models to explain runtime variability. Empirical hardness 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 I helped to design ("SATzilla'') achieved outstanding performance in the 2007 International SAT Competition, placing first in three categories, second in another, and third in still another.

In more recent work, we have begun to develop other automatic methods for improving algorithm performance, in part by leveraging this past work. The overall goal is to automate many parts of the algorithm design process that are currently performed by human experts. A prominent example is the configuration of algorithms with high-dimensional parameter spaces. We have proposed novel methods based both on local search ("ParamILS") and on building response-surface models ("SPO+"; "ActiveConfigurator"). We have applied these tools to the design of new algorithms by starting with extremely-highly-parameterized algorithms and then tuning them for domains of interest. Notable in this vein is our "Satenstein" algorithm framework, which we (automatically) configured with ParamILS to instantiate new, state-of-the-art local search SAT solvers for a variety of widely-studied domains.