AVRIM BLUM Professor, Computer Science www

My main research interests are in machine learning theory, algorithmic game theory, mechanism design, and approximation algorithms, as well as topics that combine several of these areas.

Machine Learning Theory . The goals of machine learning theory are to provide a mathematical understanding of the issues involved in getting programs to learn from experience. This involves designing models that capture fundamental tradeoffs, as well as producing new analyzable algorithms. One of my recent interests has been in developing an analog of the standard PAC learning model for the problem of clustering. In clustering, you have a set of data (say, documents) that you want to cluster according to some criterion (say, by topic). To aid in this task, you assume you have a pairwise similarity measure among data objects (perhaps measuring the fraction of important words that two documents have in common) that you hope is related to your criterion for clustering. The question we are interested in is: what properties of this similarity measure (in terms of how it relates to the clustering criterion) are sufficient to allow one to cluster well, and by what algorithms? One of the interesting things we have found is that if you allow the algorithm to produce a hierarchical clustering (splitting the documents into high-level categories at the top, then recursively splitting each category) and call this successful if the user's desired clustering is close to some pruning of this tree (i.e., we make it the user's responsibility to decide how specific a clustering she wants) then one can develop a fairly general theory of natural properties that are sufficient for clustering via different kinds of algorithms.

Algorithmic game theory and mechanism design . Many large systems involve multiple entities, interacting with each other but with their own interests in mind. The area of algorithmic game theory has developed around understanding the behavior of systems of this type: for example, analyzing the efficiency loss caused by individuals acting in their own interests rather than acting in the best interests of the overall system. Usually, this work focuses on analyzing equilibrium behavior. One of my main research interests has been in replacing the assumption that users are in a Nash equilibrium (which sometimes can even be computationally hard to find) with the much weaker assumption that individuals are adapting their behavior in ways that minimize their own regret (something for which there are many efficient algorithms). We find that results based on this assumption are often just as good as those using stronger equilibrium assumptions, plus are often resilient to the presence of Byzantine players who act in an unpredictable and even adversarial manner.

In the area of algorithmic mechanism design, I am interested in the design of auctions and other pricing mechanisms for optimizing various quantities such as revenue and efficiency. Some of these problems can be converted into hard but deceptively simple-looking graph problems.