TUOMAS SANDHOLM
Professor, Computer Science
www

My main research interests are in artificial intelligence, electronic commerce, game theory, multiagent systems, automated negotiation, contracting, auctions, exchanges, coalition formation, voting, algorithmic mechanism design, and computational models of bounded rationality. A key goal of this research is to construct electronic marketplaces that are efficient both in terms of the resulting economic allocations and the computational processes. We approach this by developing incentive-compatible market mechanisms and the algorithms that execute those mechanisms efficiently, as well as by designing software agents that act optimally on behalf of the real-world parties that they represent in such markets. A central subject of this research is the deep interaction between the game-theoretic incentive issues and the computational issues that stem from computational limits on the mechanism and the agents. Our research involves theoretical work such as models of limited computation, mechanism design, equilibrium analysis, and algorithm design as well as computational experiments and system building. Many of my systems have been commercially fielded.
The following are just some examples of my current projects:

Automated mechanism design. We are pioneering the idea of using optimization algorithms to automatically design the rules of a game (such as an auction) so that the designer's objective is maximized even though the participants play based on self-interest.

Online algorithms for exchanges. We design algorithms for market clearing that intelligently take into account possible future order flow, such as bids and asks arriving.

Auctions and exchanges. We design combinatorial and multi-attribute market mechanisms, systems that elicit minimal preference information from bidders, and software agents that bid and counterspeculate optimally in such markets.

Kidney exchange. We developed an algorithm that enables kidney exchanges to scale to a national level. It runs a kidney exchange network of 50 hospitals across 15 states.

Search and integer programming. For example, how should those algorithms branch?

Automated negotiation and contracting. For example, we design optimal backtracking instruments for multiagent systems, taking into account that the agents can act insincerely. This involves designing the instruments, analyzing their incentive properties, and developing algorithms for optimizing their parameters.

Mechanisms for computationally limited agents. If agents are computationally limited, what should good mechanisms (e.g., auctions) look like? It turns out that sometimes more can be done with computationally limited agents than unlimited ones!

Voting. We are circumventing classical impossibility results from game theory by designing (voting) mechanisms where manipulation is provably hard computationally.

Solving games. We design algorithms for solving for the equilibrium of a game, i.e., the best way to play a game. For example, we have developed an automated lossless abstraction technique that allowed us to solve poker games over 10,000 times larger than the largest solved previously. The work also includes complexity analysis and developing new solution concepts. Recently, we developed automated techniques for generating good strategies for sequential games of incomplete information, and the techniques yielded the world’s best software program for playing Heads-Up Limit Texas Hold’em poker.

You can check out my papers via my home page www.cs.cmu.edu/~sandholm.