Tuomas Sandholm
Office 9205 Gates and Hillman Centers
Email sandholm@cs.cmu.edu
Phone (412) 268-8216
Department
Computer Science Department
Administrative Support Person
Patricia Loring
Research Interests
Algorithms and Complexity
Artificial Intelligence
Game Theory
Machine Learning
Theory
Advisees
Ioannis Anagnostides
Siddharth Prasad
Brian Zhang
CSD Courses Taught
15281 - Spring, 2024
Research/Teaching Statement
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 normative 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 our systems have been commercially fielded.
The following are just some examples of my current projects:
Solving Games, Poker. We design algorithms for abstracting games and algorithms for solving for the equilibrium of a game, i.e., the best way to play it. For example, we have developed a lossless abstraction algorithm that enabled us to exactly solve poker games over 10,000 times larger than the largest solved previously. Our algorithms have also yielded some of the best poker playing programs for Texas Hold’em. We are also developing opponent modeling and exploitation techniques. Our work also involves complexity analysis and developing new game-theoretic solution concepts.
Expressive Auctions and Exchanges. We are developing the theory and methodology of how one should design markets when the participants have rich preferences over outcomes.
Advertising Markets and Electricity Markets. We are developing techniques, and founded a new startup company, in the space of expressive advertising markets, such as for TV advertising. We are also working in electricity markets.
Kidney Exchange. We have developed the market designs and algorithms that run the nationwide kidney exchange at UNOS. Our current research focuses on developing better models and algorithms for the dynamic problem.
Search and Integer Programming. For example, how should those tree search algorithms branch? Also, we are developing techniques for automated and recursive decompositions.
Revenue Maximization and 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. An example application is revenue-maximizing combinatorial auctions. Another example is channel abstraction (bundling, automated item definition), such as in TV and Internet display advertising.
Mechanisms for Computationally Limited Agents. If agents are computationally limited, how should they allocate their deliberation? What should good mechanisms (e.g., auctions) look like for such agents? It turns out that sometimes mechanisms that lead to greater systemwide good can be designed for computationally limited agents than unlimited ones!