Tuomas Sandholm

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

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
(412) 268-8216 (office)
Office: Gates Hillman Center room 9205

Executive assistant: Charlotte Yano
yano AT
(412) 268-7656, Gates Hillman Center room 8118

Last updated 4/11/2014.


Tuomas Sandholm is Professor at Carnegie Mellon University in the Computer Science Department, with affiliate professor 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 is the Founder and Director of the Electronic Marketplaces Laboratory.  He has published over 450 papers.  He has over 20 years of experience building optimization-based electronic marketplaces, and has fielded several of his systems.  In parallel with his academic career, he was Founder, Chairman, 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 auctions, with over $60 billion in total spend and over $6 billion in generated savings.  Dr. Sandholm’s algorithms also run the US-wide UNOS kidney exchange.  He is Founder and CEO of Optimized Markets, Inc., a new startup that is bringing a new paradigm to advertising sales and scheduling - in TV, display, streaming, mobile, game, and cross-media advertising.  He also serves as the redesign consultant of Baidu’s sponsored search auctions and display advertising markets; within two years Baidu’s market cap increased 5x to $50 billion due to better monetization.  He has served as consultant, advisor, or board member for Yahoo!, Google, Granata Decision Systems, Netcycler, and others.  He has applied his game-solving algorithms to develop some of the world’s best poker-playing programs.  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 many honors are the NSF Career Award, inaugural ACM Autonomous Agents Research Award, Sloan Fellowship, Carnegie Science Center Award for Excellence, Edelman Laureateship, and Computers and Thought Award.  He is Fellow of the ACM and AAAI.

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

Curriculum vitae

Google Scholar profile

Video of me speaking about our advertising sales and scheduling/trafficking optimization system and Optimized Markets, Inc. on the National Science Foundation front page, 5/21/2013

Academic awards (some; full list in the CV above)

Some of the recent 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.

Some recommended publications by topic

A complete list of publications is available on my 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 mechanism & criticisms of the revelation principle

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

Solving sequential games, poker

Opponent exploitation (opponent modeling)

Poker demonstrations (reviewed)

Solving normal form games and repeated games

Security games

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

Preference elicitation in voting

Complexity of manipulating elections by insincere preference revelation


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


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


Peer-to-peer negotiation, bargaining & trading

Valuation calculation & normative models of bounded rationality


Leveled commitment contracts & breach (backtracking in multiagent systems)


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