Tuomas Sandholm

Tuomas Sandholm

Angel Jordan University Professor
Carnegie Mellon University
Computer Science Department
5000 Forbes Avenue
Pittsburgh, PA 15213

Co-Director, CMU AI

Director, Electronic Marketplaces Laboratory

Affiliated Professor
Machine Learning Department
Ph.D. Program in Algorithms, Combinatorics, and Optimization (ACO)
Carnegie Mellon/University of Pittsburgh Joint Ph.D. Program in Computational Biology

sandholm AT cs.cmu.edu
(412) 268-8216 (office)
Office: Gates Hillman Center room 9205

Executive Assistant: Pat Loring
sawako AT andrew.cmu.edu, (412) 268-5628, Gates Hillman Center room 7025

Biography

Tuomas Sandholm is Angel Jordan University Professor of Computer Science at Carnegie Mellon University and a serial entrepreneur. His research focuses on the convergence of artificial intelligence, economics, and operations research. He is Co-Director of CMU AI. He is the Founder and Director of the Electronic Marketplaces Laboratory. He has published over 500 peer-reviewed papers, holds 29 US patents, and his h-index is 96. In addition to his main appointment in the Computer Science Department, he holds appointments in the Machine Learning Department, Ph.D. Program in Algorithms, Combinatorics, and Optimization (ACO), and CMU/UPitt Joint Ph.D. Program in Computational Biology.

He has built optimization-powered electronic marketplaces since 1989, and has fielded several of his systems. In parallel with his academic career, he was Founder, Chairman, first CEO, and CTO/Chief Scientist of CombineNet, Inc. from 1997 until its acquisition in 2010. During this period the company commercialized over 800 of the world's largest-scale generalized combinatorial multi-attribute auctions, with over $60 billion in total spend and over $6 billion in generated savings.

Sandholm has developed the leading algorithms for several general classes of game with his students. The team that he leads is the multi-time world champion in computer heads-up no-limit Texas hold’em, which is the main benchmark and decades-open challenge problem for testing application-independent algorithms for solving imperfect-information games. Their AI Libratus became the first and only AI to beat top humans at that game. Then their AI Pluribus became the first and only AI to beat top humans at the multi-player game. That is the first superhuman milestone in any game beyond two-player zero-sum games. He is Founder and CEO of Strategy Robot, Inc., which focuses on defense, intelligence, and other government applications. He is also Founder and CEO of Strategic Machine, Inc., which provides solutions for strategic reasoning under imperfect information in a broad set of applications ranging from poker to other recreational games to business strategy, negotiation, strategic pricing, finance, cybersecurity, physical security, auctions, political campaigns, and medical treatment planning.

Since 2010, his algorithms have been running the national kidney exchange for the United Network for Organ Sharing, where they autonomously make the kidney exchange transplant plan for 80% of U.S. transplant centers together each week. He also co-invented never-ending altruist-donor-initiated chains and his algorithms created the first such chain. Such chains have become the main modality of kidney exchange worldwide and have led to around 10,000 life-saving transplants. He invented liver lobe and multi-organ exchanges, and the first liver-kidney swap took place in 2019.

He is Founder and CEO of Optimized Markets, Inc., which is bringing a new optimization-powered paradigm to advertising campaign sales, pricing, and scheduling - in TV (linear and nonlinear), Internet display, streaming (video and audio), mobile, game, and cross-media advertising. He served as the redesign consultant of Baidu’s sponsored search auctions and display advertising markets 2009-2011; within two years Baidu’s market cap increased 5x to $50 billion due to doubled monetization per user. He has served as consultant, advisor, or board member for Yahoo!, Google, Chicago Board Options Exchange, swap.com, Granata Decision Systems (now part of Google), Rare Crowds (now part of Media Math), and others.

He holds a Ph.D. and M.S. in computer science and a Dipl. Eng. (M.S. with B.S. included) with distinction in Industrial Engineering and Management Science. Among his honors are the Vannevar Bush Faculty Fellowship, AAAI Award for AI for the Benefit of Humanity, IJCAI John McCarthy Award, Robert S. Engelmore Award, Minsky Medal, Computers and Thought Award, inaugural ACM Autonomous Agents Research Award, CMU’s Allen Newell Award for Research Excellence, Sloan Fellowship, NSF Career Award, Carnegie Science Center Award for Excellence, and Edelman Laureateship. He is Fellow of the ACM, AAAI, INFORMS, and AAAS. He holds an honorary doctorate from the University of Zurich.

Research interests: Artificial intelligence; optimization (search and integer programming, combinatorial optimization, stochastic optimization, and convex optimization); game theory; equilibrium finding; algorithms for solving games; opponent modeling and exploitation; automated algorithm configuration; market design; mechanism design; electronic commerce; multiagent systems; auctions and exchanges; automated negotiation and contracting; advertising markets; computational advertising; kidney exchange; prediction markets; (automated) market making; voting; coalition formation; safe exchange; preference elicitation; normative models of bounded rationality; resource-bounded reasoning; fairness, privacy; multiagent learning; and machine learning.

Curriculum vitae (including full list of publications)

List of publications on DBLP

Google Scholar profile

Awards (some; full list, including best paper and classic paper awards, is on the CV)

 

Recent placement of PhD students into tenured or tenure-track positions:
MIT EECS (Gabriele Farina), Stanford (Ellen Vitercik), CMU CSD (Vincent Conitzer)

 

News


Courses taught (full list here):

Information for candidates interested in applying to become my PhD students

Advice for my research group

CMU AI seminar series


Selected pre-2018 publications by topic (complete list of publications is on the CV)

Broad overview articles (more specific review articles are listed under their respective topics below)

Automated mechanism design (AMD)

Overview (somewhat dated by now)

Research on the general problem

Revenue maximization, auctions, other selling mechanisms, and online mechanisms. (See also AMD work listed in section “Safe Exchange” below.)

Manipulation-optimal mechanisms and criticisms of the revelation principle

Algorithms and complexity of solving games (coalitional games and multiagent learning are discussed in their own sections later)

Solving extensive-form games, e.g., poker

Overviews
Abstraction and equilibrium finding
Opponent exploitation (opponent modeling)
Poker demonstrations (reviewed)

Applications of game solving to medical domains and healthcare

Security games and cybersecurity games

Solving normal form games and repeated games

Voting (privacy in voting is discussed in a separate section later on)

Are teams smarter than smart individuals? General theory, and experiments in computer Go

Preference elicitation in voting

Complexity of manipulating elections by insincere preference revelation

Other

Expressiveness in mechanisms, expressive bidding, combinatorial auctions, expressive negotiation, bundling, reserve pricing

Brief overview of our recent work on expressiveness

Theory; Case studies; Large fielded systems; Bidding languages; Markets with side constraints & non-price attributes; Generalizations; Spectrum auctions; Ad auctions and exchanges; Display (banner) ads; Sponsored search

Multi-item markets (combinatorial auctions and generalizations)

Winner determination (= market clearing), search, integer programming, mixed integer programming

Market anomalies

Multi-unit markets

Kidney exchange, matching markets, barter exchanges

(Automated) market making and prediction markets

Online algorithms for exchanges

Preference elicitation, “ascending” auctions & coherent pricing

Overview

The original paper on preference elicitation in combinatorial auctions

Effectiveness of preference elicitation in general combinatorial auctions

Preferences for which elicitation can (not) be done in a polynomial worst-case number of queries

Preference elicitation in combinatorial exchanges (& multi-robot systems)

Coherent pricing

Eliciting bid taker non-price preferences in (combinatorial) auctions: Automated scenario navigation

Auction design for spiteful bidders

Bidding agents (for auctions, exchanges, general equilibrium markets, and bargaining)

Valuation calculation, normative models of bounded rationality, and information acquisitionin auctions and bargaining

Other

Peer-to-peer negotiation, bargaining & trading

Valuation calculation & normative models of bounded rationality

Other

Leveled commitment contracts & breach (backtracking in multiagent systems)

Overview

Single leveled commitment contract

Sequences of leveled commitment contracts

Safe exchange & deviation-proof multiagent plans

A general framework

Methods based on dividing the exchange into chunks

Motivating the participants to reveal their trustworthiness (trust & reputation)

Stability (deviation-proofness) of multiagent plans

Coalition formation

Machine learning

Multiagent learning

Single-agent learning

Resource-bounded reasoning (multiagent resource-bounded reasoning covered in other sections)

Privacy in social choice (voting and auctions), cryptography

Satisfiability & constraint satisfaction

Networks


Hobbies

Adventures

Family