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: Jessica Packer jpacker AT cs.cmu.edu, (412) 268-7660, Gates Hillman Center room 9006

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 22 US patents, and his h-index is 85. 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.

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.

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.

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 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. He is also Founder and CEO of Strategy Robot, Inc., which focuses on defense, intelligence, and other government applications.

He served 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 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 many honors are the 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, and INFORMS. He holds an honorary doctorate from the University of Zurich.

Research interests: Artificial intelligence; market design; optimization (search and integer programming, combinatorial optimization, stochastic optimization, and convex optimization); game theory; mechanism design; electronic commerce; multiagent systems; auctions and exchanges; automated negotiation and contracting; equilibrium finding; algorithms for solving games; opponent modeling and exploitation; automated algorithm configuration; 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

Google Scholar profile

News

• Pluribus was selected Science Breakthrough of the Year Runner-Up by Science, 2019.
• Our AI Pluribus became the first and only AI to beat professional players in 6-player no-limit Texas hold’em poker in 2019. This is the first superhuman AI gaming milestone in any game that is not a two-player zero-sum game.
• My student Noam Brown and I received a AAAI-19 Distinguished Paper honorable mention.
• My student Noam Brown and I received the NIPS-17 best paper award.
• Our AI called Libratus (built by my PhD student Noam Brown and me) became the first and only AI to beat top Heads-Up No-Limit Texas Hold'em professionals in January 2017.
• Lengpudashi, our different version of Libratus, beat a team of six Chinese professional poker players, including China's only WSOP bracelet winner, in April 2017.
• I was ranked in the Top 10 Most Influential Scholars of all time in the field of Artificial Intelligence by AMiner in December 2016.
• I received an honorary doctorate from the University of Zurich, and met the President of Switzerland - 4/30/2016.
• We won the world championships of computer poker again. My PhD student Noam Brown and I won the AAAI 2016 Annual Computer Poker Competition Heads-Up No-Limit Texas Hold'em competition in both categories (total banroll and elimination). We beat every opponent with statistical significance. No-Limit Texas Hold'em is the game that the leading teams have focused on over the last couple of years. There was no competition in 2015.
• We won the world championships of computer poker. My team (my PhD students Sam Ganzfried, Noam Brown, and I) won the AAAI (Association for the Advancement of Artificial Intelligence) 2014 Annual Computer Poker Competition, Heads-Up No-Limit Texas Hold'em, in both categories (total bankroll and elimination). We beat each opponent with statistical significance.
• Video of me speaking about our advertising sales, allocation, and scheduling optimization system and Optimized Markets, Inc. on the National Science Foundation front page.

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

• Minsky Medal, 2019.
• CMU’s Allen Newell Award for Research Excellence, 2018.
• Honorary Doctorate, University of Zurich, 2016
• Fellow of the ACM (2008), AAAI (2008), and INFORMS (2014)
• IJCAI Computers and Thought Award, 2003 (Award talk writeup: “Making Markets and Democracy Work: A Story of Incentives and Computing” in Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-03), p. 1649-1671. Award talk (.ppt, 87MB with audio).
• Inaugural ACM Autonomous Agents Research Award, 2001
• Edelman Laureate, 2005
• Alfred P. Sloan Research Fellow, 2003-2005
• Carnegie Science Center Award for Excellence, 2004
• Outstanding Achievement in Research, UMass Outstanding Achievement and Advocacy Awards, 2009
• One of the three most influential academics in the business world, The Brilliant Issue: 73 Biggest Brains in Business, Conde Nast Portfolio Magazine, 2008
• Ernst & Young Entrepreneur of the Year Award finalist, Western PA, 2003
• National Science Foundation Career Award, 1997

---

Some of the recent courses taught (full list here):

• CS 15-381 / 681 Artificial Intelligence: Representation and Problem Solving (Fall 2017, with Tai Sing Lee) = undergraduate and MS-level introduction to AI
• CS 15-780 Graduate Artificial Intelligence (cross-listed in the Robotics Institute as RI 16-731 Fundamentals of AI for Robotics) (Spring 2016, with Zico Kolter)
• CS 15-892 Foundations of Electronic Marketplaces (Fall 2015)
• CS 15-780 Graduate Artificial Intelligence (cross-listed in the Robotics Institute as RI 16-731 Fundamentals of AI for Robotics) (Spring 2013, with Manuela Veloso)
• CS 15-780 Graduate Artificial Intelligence (cross-listed in the Robotics Institute as RI 16-731 Fundamentals of AI for Robotics) (Spring 2011, with Geoff Gordon)
• MS in Ecommerce Mini-Course 20-853: Electronic Negotiation

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 (may be out of date)

A complete list of publications is available on my CV.

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

• Sandholm, T. 2008. Computing in Mechanism Design. In the New Palgrave Dictionary of Economics.
• Sandholm, T. 1999. Distributed Rational Decision Making. In the textbook Multiagent Systems: A Modern Introduction to Distributed Artificial Intelligence, Weiß, G., ed., MIT Press. Pp. 201-258.

Automated mechanism design (AMD)

Overview (somewhat dated by now)

• Sandholm, T. 2003. Automated mechanism design: A New Application Area for Search Algorithms. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP). Paper corresponding to an invited talk. (The review part is about joint research with Vincent Conitzer.)

Research on the general problem

• Nath, S. and Sandholm, T. 2016. Efficiency and Budget Balance. In Proceedings of the Conference on Web and Internet Economics (WINE). Extended version on ArXiv.
• Sui, X, Boutilier, C, and Sandholm, T. 2013. Analysis and Optimization of Multi-dimensional Percentile Mechanisms. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Sandholm, T., Conitzer, V., and Boutilier, C. 2007. Automated Design of Multistage Mechanisms. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). (Early longer version in IBC workshop 2005.)
• Conitzer, V. and Sandholm, T. 2007. Incremental Mechanism Design. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Conitzer, V. and Sandholm, T. 2004. Self-Interested Automated Mechanism Design and Implications for Optimal Combinatorial Auctions. In Proceedings of the ACM Conference on Electronic Commerce (EC).
• Conitzer, V. and Sandholm, T. 2004. An Algorithm for Automatically Designing Deterministic Mechanisms without Payments. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Conitzer, V. and Sandholm, T. 2003. Applications of automated mechanism design. In Proceedings of the UAI Bayesian Modeling Applications Workshop. Extended version.
• Conitzer, V. and Sandholm, T. 2003. Automated mechanism design with a structured outcome space. Draft.
• Conitzer, V. and Sandholm, T. 2002. Complexity of Mechanism Design. In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI).
• Conitzer, V. and Sandholm, T. 2003. Automated Mechanism Design: Complexity Results Stemming from the Single-Agent Setting. In Proceedings of the International Conference on Electronic Commerce (ICEC).

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

• Balcan, N., Sandholm, T., and Vitercik, E. 2017. Sample Complexity of Multi-Item Profit Maximization. On arXiv. Version that was later accepted to the Workshop on Algorithmic Game Theory and Data Science at the ACM Conference on Economics and Computation (EC).
• Balcan, N., Sandholm, T., and Vitercik, E. 2016. Sample Complexity of Automated Mechanism Design. In Proceedings of the Conference on Neural Information Processing Systems (NIPS). Supplementary material. Earlier version on arXiv.
• Sandholm, T. and Likhodedov, A. 2015. Automated Design of Revenue-Maximizing Combinatorial Auctions. Operations Research 63(5), 1000-1025. (Subsumes and extends over a AAAI-05 paper and a AAAI-04 paper.)
• Tang, P. and Sandholm, T. 2012. Mixed-bundling auctions with reserve prices. In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).
• Tang, P. and Sandholm, T. 2011. Approximating Optimal Combinatorial Auctions for Complements Using Restricted Welfare Maximization. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Othman, A. and Sandholm, T. 2009. How Pervasive is the Myerson-Satterthwaite Impossibility? In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Hajiaghayi, M., Kleinberg, R., and Sandholm, T. 2007. Automated Online Mechanism Design and Prophet Inequalities. In Proceedings of the AAAI Conference on Artificial Intelligence.
• Sandholm, T. and Gilpin, A. 2006. Sequences of Take-It-or-Leave-It Offers: Near-Optimal Auctions without Full Valuation Revelation. In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS). (Early version in AMEC-03
• Likhodedov, A. and Sandholm, T. 2004. Mechanism for Optimally Trading Off Revenue and Efficiency in Multi-unit Auctions. 2-page poster abstract in ACM Conference on Electronic Commerce.

Manipulation-optimal mechanisms and criticisms of the revelation principle

• Othman, A. and Sandholm, T. 2009. Better with Byzantine: Manipulation-Optimal Mechanisms. In Proceedings of the Symposium on Algorithmic Game Theory (SAGT). (Early versions in COMSOC-08 and GAMES-08.)
• Conitzer, V. and Sandholm, T. 2003. Computational Criticisms of the Revelation Principle. In Proceedings of the Workshop on Agent Mediated Electronic Commerce (AMEC V). Also orally presented at LOFT-04. Newer draft.

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

• Sandholm, T. 2015. Solving Imperfect-Information Games. Science 347(6218), 122-123.
• Sandholm, T. 2015. Abstraction for Solving Large Incomplete-Information Games. In Proceedings of the AAAI Conference on Artificial Intelligence, Senior Member Track, Summary Paper Subtrack.
• Sandholm, T. 2010. The State of Solving Large Incomplete-Information Games, and Application to Poker. AI Magazine, special issue on Algorithmic Game Theory, Winter, 13-32.

Abstraction and equilibrium finding

• Farina, G., Kroer, C., Sandholm, T. 2017. Regret Minimization in Behaviorally-Constrained Zero-Sum Games. In Proceedings of the International Conference on Machine Learning (ICML).
• Brown, N. and Sandholm, T. 2017. Reduced Space and Faster Convergence in Imperfect-Information Games via Pruning. In Proceedings of the International Conference on Machine Learning (ICML). Early version "Reduced Space and Faster Convergence in Imperfect-Information Games via Regret-Based Pruning" in Proceedings of the AAAI workshop on Computer Poker and Imperfect Information Games. Even earlier version on arXiv.
• Kroer, C., Farina, G., Sandholm, T. 2017. Smoothing Method for Approximate Extensive-Form Perfect Equilibrium. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). ArXiv version.
• Kroer, C., Waugh, K., Kilinc-Karzan, F., and Sandholm, T. 2017. Theoretical and Practical Advances on Smoothing for Extensive-Form Games. Abstract in Proceedings of the ACM Conference on Economics and Computation (EC). Full version on arXiv.
• Brown, N., Kroer, C., and Sandholm, T. 2017. Dynamic Thresholding and Pruning for Regret Minimization. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). Early version in IJCAI-16 AGT workshop.
• Kroer, C. and Sandholm, T. 2016. Imperfect-Recall Abstractions with Bounds in Games. In Proceedings of the ACM Conference on Economics and Computation (EC). Early version: Extensive-Form Game Imperfect-Recall Abstractions with Bounds in IJCAI-15 workshop on Algorithmic Game Theory.
• Noam Brown and Tuomas Sandholm. 2016. Strategy-Based Warm Starting for Regret Minimization in Games. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). Extended version with appendix and a typo fix.
• Noam Brown and Tuomas Sandholm. 2015. Regret-Based Pruning in Extensive-Form Games. In Proceedings of the Neural Information Processing Systems: Natural and Synthetic (NIPS) conference. Extended version.
• Brown, N. and Sandholm, T. 2015. Simultaneous Abstraction and Equilibrium Finding in Games. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Kroer, C. and Sandholm, T. 2015. Limited Lookahead in Imperfect-Information Games. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Kroer, C., Waugh, K., Kilinc-Karzan, F., and Sandholm, T. 2015. Faster First-Order Methods for Extensive-Form Game Solving. In Proceedings of the ACM Conference on Economics and Computation (EC).
• Brown, N., Ganzfried, S., and Sandholm, T. 2015. Hierarchical Abstraction, Distributed Equilibrium Computation, and Post-Processing, with Application to a Champion No-Limit Texas Hold’em Agent. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Kroer, C. and Sandholm, T. 2015. Discretization of Continuous Action Spaces in Extensive-Form Games. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Ganzfried, S. and Sandholm, T. 2015. Endgame Solving in Large Imperfect-Information Games. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS). Early version in AAAI-15 Workshop on Computer Poker and Imperfect Information. Early version in AAAI-13 Workshop on Computer Poker and Incomplete Information.
• Kroer, C. and Sandholm, T. 2014. Extensive-Form Game Abstraction With Bounds. In Proceedings of the ACM Conference on Economics and Computation (EC). Extended version that includes the appendices.
• Brown, N. and Sandholm, T. 2014. Regret Transfer and Parameter Optimization. In Proceedings of the AAAI Conference on Artificial Intelligence. (Extended version)
• Ganzfried, S. and Sandholm, T. 2014. Potential-Aware Imperfect-Recall Abstraction with Earth Mover’s Distance in Imperfect-Information Games. In Proceedings of the AAAI Conference on Artificial Intelligence.
• Ganzfried, S. and Sandholm, T. 2013. Action Translation in Extensive-Form Games with Large Action Spaces: Axioms, Paradoxes, and the Pseudo-Harmonic Mapping. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Sandholm, T. and Singh, S. 2012. Lossy Stochastic Game Abstraction with Bounds. In Proceedings of the ACM Conference on Electronic Commerce (EC).
• Gilpin, A., Peña, J., and Sandholm, T. 2012. First-Order Algorithm with O(ln(1/epsilon)) Convergence for epsilon-Equilibrium in Two-Person Zero-Sum Games. Mathematical Programming 133(1-2), 279-298. Subsumes our AAAI-08 paper.
• Ganzfried, S., Sandholm, T., and Waugh, K. 2012. Strategy Purification and Thresholding: Effective Non-Equilibrium Approaches for Playing Large Games. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS). (Early version in AAAI-11Workshop on Applied Adversarial Reasoning and Risk Modeling, and 2-page abstract in AAMAS-11.)
• Ganzfried, S. and Sandholm, T. 2012. Tartanian5: A Heads-Up No-Limit Texas Hold'em Poker-Playing Program. Computer Poker Symposium at the AAAI Conference on Artificial Intelligence.
• Hoda, S., Gilpin, A., Peña, J., and Sandholm, T. 2010. Smoothing techniques for computing Nash equilibria of sequential games. Mathematics of Operations Research 35(2), 494-512. Subsumes our WINE-07 paper.
• Ganzfried, S. and Sandholm, T. 2010 Computing Equilibria by Incorporating Qualitative Models. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS). Extended version appeared as CMU technical report CMU-CS-10-105.
• Gilpin, A.. and Sandholm, T. 2010. Speeding Up Gradient-Based Algorithms for Sequential Games (Extended Abstract). In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Ganzfried, S. and Sandholm, T. 2009. Computing Equilibria in Multiplayer Stochastic Games of Imperfect Information.In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Gilpin, A. and Sandholm, T. 2008. Expectation-Based Versus Potential-Aware Automated Abstraction in Imperfect Information Games: An Experimental Comparison Using Poker. In Proceedings of the AAAI Conference on Artificial Intelligence.
• Ganzfried, S. and Sandholm, T. 2008. Computing an Approximate Jam/Fold Equilibrium for 3-Agent No-Limit Texas Hold'em Tournaments. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Gilpin, A., Sandholm, T., and Sørensen, T. 2008. A heads-up no-limit Texas Hold'em poker player: Discretized betting models and automatically generated equilibrium-finding programs. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Gilpin, A. and Sandholm, T. 2007. Lossless abstraction of imperfect information games. Journal of the ACM, 54 (5), October. Early versions: Finding Equilibria in Large Sequential Games of Imperfect Information, EC-06, and CMU-CS-05-158, 2005.
• Gilpin, A., Sandholm, T., and Sørensen, T. 2007. Potential-Aware Automated Abstraction of Sequential Games, and Holistic Equilibrium Analysis of Texas Hold'em Poker. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
• Gilpin, A. and Sandholm, T. 2007. Better automated abstraction techniques for imperfect information games, with application to Texas Hold'em poker. In Proceedings of the International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).
• Gilpin, A. and Sandholm, T. 2006. A competitive Texas Hold'em Poker player via automated abstraction and real-time equilibrium computation. In Proceedings of the National Conference on Artificial Intelligence (AAAI).

Opponent exploitation (opponent modeling)

• Ganzfried, S. and Sandholm, T. 2015. Safe Opponent Exploitation. In the Best of EC-12 special issue of ACM Transactions of Economics and Computation (TEAC), 3(2), Article 8, 1-28.
• Ganzfried, S. and Sandholm, T. 2011. Game Theory-Based Opponent Modeling in Large Imperfect-Information Games. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).

Poker demonstrations (reviewed)

• Brown, N. and Sandholm, T. 2016. Baby Tartanian8: Winning Agent from the 2016 Annual Computer Poker Competition. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Demonstration Track.
• Brown, N. and Sandholm, T. 2015. Claudico: The World's Strongest No-Limit Texas Hold'em Poker AI. In Proceedings of the Neural Information Processing Systems: Natural and Synthetic (NIPS) conference, Demonstration Track.
• Brown, N., Ganzfried, S., and Sandholm, T. 2015. Tartanian7: A Champion Two-Player No-Limit Texas Hold’em Poker-Playing Program. In Proceedings of the AAAI Conference on Artificial Intelligence, Demonstration Track Paper.
• Gilpin, A. and Sandholm, T. 2008. A heads-up no-limit Texas Hold'em poker player: Discretized betting models and automatically generated equilibrium-finding programs. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), Demonstration Track.
• Gilpin, A. and Sandholm, T. 2006. A Texas Hold'em poker player based on automated abstraction and real-time equilibrium computation. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), Demonstration Track.
• Gilpin, A. and Sandholm, T. 2005. Optimal Rhode Island Hold'em Poker. In Proceedings of the National Conference on Artificial Intelligence (AAAI), Intelligent Systems Demonstration Program (refereed demonstration). Here is a version with screen shots.

Applications of game solving to medical domains and healthcare

• Kroer, C. and Sandholm, T. 2016. Sequential Planning for Steering Immune System Adaptation. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Sandholm, T. 2015. Steering Evolution and Biological Adaptation Strategically: Computational Game Theory and Opponent Exploitation for Treatment Planning, Drug Design, and Synthetic Biology. Vision paper in the CSD50 commemorative volume to celebrate the 50th birthday of the Computer Science Department at Carnegie Mellon University. I presented it at the CMU Computer Science Department's 50th birthday (video; my talk start at time 1:00:20 within the video; slides).
• Sandholm, T. 2015. Steering Evolution Strategically: Computational Game Theory and Opponent Exploitation for Treatment Planning, Drug Design, and Synthetic Biology. In Proceedings of the AAAI Conference on Artificial Intelligence, Senior Member Track, Blue Skies Subtrack.

Security games and cybersecurity games

• DeBruhl, B., Kroer, C., Datta, A., Sandholm, T., and Tague, P. 2014. Power napping with loud neighbors: optimal energy-constrained jamming and anti-jamming. In Proceedings of the ACM Conference on Security & Privacy in Wireless and Mobile Networks (WiSec).
• Yin, Z., Jiang, A., Tambe, M., Kietkintveld, C., Leyton-Brown, K, Sandholm, T., Sullivan, J. 2012. TRUSTS: Scheduling Randomized Patrols for Fare Inspection in Transit Systems using Game Theory. AI Magazine, 33(4), 59-72. Conference version TRUSTS: Scheduling Randomized Patrols for Fare Inspection in Transit Systems in Proceedings of the Innovative Applications of Artificial Intelligence (IAAI) Conference, 2012.
• Jiang, A., Yin, Z., Johnson, M., Tambe, M., Kietkintveld, C., Leyton-Brown, K, and Sandholm, T. 2012. Towards Optimal Patrol Strategies for Fare Inspection in Transit Systems. In Proceedings of the AAAI Spring Symposium on Game Theory for Security, Sustainability and Health.

Solving normal form games and repeated games

• Berg, K. and Sandholm, T. 2017. Exclusion Method for Finding Nash Equilibrium in Multiplayer Games. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI).
• Gatti, N. and Sandholm, T. 2014. Finding the Pareto Curve in Bimatrix Games is Easy. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Gatti, N., Rocco, M., and Sandholm, T. 2013. Algorithms for strong Nash equilibrium with more than two agents. In Proceedings of the AAAI Conference on Artificial Intelligence.
• Gatti, N., Rocco, M., and Sandholm, T. 2013. Strong Nash equilibrium is in smoothed P. In Proceedings of the AAAI Conference on Artificial Intelligence, late-breaking paper track.
• Gatti, N., Rocco, M., and Sandholm, T. 2013. On the verification and computation of strong Nash equilibrium. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Gatti, N., Patrini, G., Rocco, M., and Sandholm, T. 2012. Combining local search techniques and path following for bimatrix games. Conference on Uncertainty in Artificial Intelligence (UAI).
• Benisch, M., Davis, G., and Sandholm, T. 2010. Algorithms for Closed Under Rational Behavior (CURB) Sets. Journal of Artificial Intelligence Research (JAIR) 38: 513-534. Early versions in AAAI-06 and EC-06 workshop on Alternative Solution Concepts.
• Conitzer, V. and Sandholm, T. 2008. New Complexity Results about Nash Equilibria. Games and Economic Behavior, 63(2), 621-641. Early version in IJCAI-03.
• Gilpin, A. and Sandholm, T. 2008. Solving two-person zero-sum repeated games of incomplete information. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Conitzer, V. and Sandholm, T. 2006. Computing the Optimal Strategy to Commit to. In Proceedings of the ACM Conference on Electronic Commerce (EC).
• Conitzer, V. and Sandholm, T. 2006. A Technique for Reducing Normal Form Games to Compute a Nash Equilibrium. In Proceedings of the International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS). (Early version in 7th Workshop on Game Theoretic and Decision Theoretic Agents, GTDT-05.)
• Sandholm, T., Gilpin, A., and Conitzer, V. 2005. Mixed-Integer Programming Methods for Finding Nash Equilibria. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
• Conitzer, V. and Sandholm, T. 2005. A Generalized Strategy Eliminability Criterion and Computational Methods for Applying It. In Proceedings of the National Conference on Artificial Intelligence (AAAI). Slightly updated version in EC-06 workshop on Alternative Solution Concepts.
• Conitzer, V. and Sandholm, T. 2005. Complexity of (Iterated) Dominance. In Proceedings of the ACM Conference on Electronic Commerce (EC).

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

• Jiang, A., Marcolino, L., Procaccia, A., Sandholm, T., Shah, N., Tambe, M. 2014. Diverse Randomized Agents Vote to Win. In Proceedings of the Neural Information Processing Systems: Natural and Synthetic (NIPS) conference.

Preference elicitation in voting

• Conitzer, V. and Sandholm, T. 2005. Communication Complexity of Common Voting Rules. In Proceedings of the ACM Conference on Electronic Commerce (EC).
• Conitzer, V. and Sandholm, T. 2002. Vote Elicitation: Complexity and Strategy-Proofness. In Proceedings of the National Conference on Artificial Intelligence (AAAI). Extended version.

Complexity of manipulating elections by insincere preference revelation

• Conitzer, V., Sandholm, T., and Lang, J. 2007. When Are Elections with Few Candidates Hard to Manipulate? Journal of the ACM, 54(3), June. This paper combines and extends upon a AAAI-02 paper and a TARK-03 paper.
• Conitzer, V. and Sandholm, T. 2006. Nonexistence of Voting Rules That Are Usually Hard to Manipulate. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
• Conitzer, V. and Sandholm, T. 2003. Universal Voting Protocol Tweaks to Make Manipulation Hard. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).

Other

• Tang, P. and Sandholm, T. 2012. Coalitional Structure of the Muller-Satterthwaite Theorem. In Proceedings of the Workshop on Cooperative Games in Multiagent Systems (CoopMAS) at the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Conitzer, V. and Sandholm, T. 2005. Common Voting Protocols as Maximum Likelihood Estimators. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI).

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

Brief overview of our recent work on expressiveness

• Sandholm, T. 2008. Expressiveness in mechanisms and its relation to efficiency: Our experience from $40 billion of combinatorial multi-attribute auctions, and recent theory. Extended abstract of an invited plenary talk given at the International Workshop on Computational Social Choice (COMSOC) and at the DIMACS-LAMSADE conference on Algorithmic Decision Theory.

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

• Peng, F. and Sandholm, T. 2016. Scalable Segment Abstraction Method for Advertising Campaign Admission and Inventory Allocation Optimization. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Nguyen, T.and Sandholm, T. 2016. Multi-Option Descending Clock Auction. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), extended abstract.
• Kroer, C. and Sandholm, T. 2015. Computational Bundling for Auctions. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS). Early long version: CMU Computer Science Department Technical Report CMU-CS-13-111.
• Nguyen, T.and Sandholm, T. 2014. Optimizing Prices in Descending Clock Auctions. In Proceedings of the ACM Conference on Economics and Computation (EC). Online appendices. Also submitted into the Federal Communications Commission (FCC) Docket No. 12-268, that is, the incentive auction design docket.
• Dickerson, J., Goldman, J., Karp, J., Procaccia, A., and Sandholm, T. 2014. The Computational Rise and Fall of Fairness. In Proceedings of the AAAI Conference on Artificial Intelligence.
• Sandholm, T. 2013. Very-Large-Scale Generalized Combinatorial Multi-Attribute Auctions: Lessons from Conducting $60 Billion of Sourcing. Chapter 16 in The Handbook of Market Design, edited by Nir Vulkan, Alvin E. Roth, and Zvika Neeman, Oxford University Press.
• Conitzer, V. and Sandholm, T. 2012. Computing Optimal Outcomes under an Expressive Representation of Settings with Externalities. Journal of Computer and System Sciences (JCSS), special issue on Knowledge Representation and Reasoning, 78(1), 2-14. Early version in AAAI-05.
• Benisch, M., and Sandholm, T. 2011. A Framework for Automated Bundling and Pricing Using Purchase Data. In Proceedings of the Conference on Auctions, Market Mechanisms and Their Applications (AMMA).
• Conitzer, V. and Sandholm, T. 2011. Expressive Markets for Donating to Charities. Artificial Intelligence, 175(7-8), 1251-1271, special issue on Representing, Processing, and Learning Preferences: Theoretical and Practical Challenges. Early version "Expressive Negotiation over Donations to Charities" in Proceedings of the ACM Conference on Electronic Commerce (EC), 2004.
• Walsh, W., Boutilier, C., Sandholm, T., Shields, R., Nemhauser, G., and Parkes, D. 2010. Automated Channel Abstraction for Advertising Auctions. In Proceedings of the AAAI Conference on Artificial Intelligence. Earlier, longer version appeared in the Proceedings of the Ad Auctions Workshop, 2009.
• Othman, A. and Sandholm, T. 2010. Envy Quotes and the Iterated Core-Selecting Combinatorial Auction. In Proceedings of the AAAI Conference on Artificial Intelligence.
• Krysta, P., Michalak, T., Sandholm, T., and Wooldridge, M. 2010. Combinatorial Auctions with Externalities (Extended Abstract). In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), short paper.
• Othman, A., Sandholm, T., Budish, E. 2010. Finding Approximate Competitive Equilibria: Efficient and Fair Course Allocation. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Benisch, M., Sadeh, N., and Sandholm, T. 2009. Methodology for Designing Reasonably Expressive Mechanisms with Application to Ad Auctions. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). Earlier version: The Cost of Inexpressiveness in Advertisement Auctions. In Proceedings of the Fourth Workshop on Ad Auctions, 2008.
• Benisch, M., Sadeh, N., and Sandholm, T. 2008. A Theory of Expressiveness in Mechanisms. In Proceedings of the AAAI Conference on Artificial Intelligence.
• Boutilier, C., Parkes, D., Sandholm, T., and Walsh, W. 2008. Expressive Banner Ad Auctions and Model-Based Online Optimization for Clearing. In Proceedings of the AAAI Conference on Artificial Intelligence.
• Walsh, W., Parkes, D., Sandholm, T., and Boutilier, C. 2008. Computing Reserve Prices and Identifying the Value Distribution in Real-World Auctions with Market Disruptions. In Proceedings of the AAAI Conference on Artificial Intelligence.
• Benisch, M., Kelley, P., Sadeh, N., Sandholm, T., Cranor, L., Drielsma, P., and Tsai, J. 2008. The Impact of Expressiveness on the Effectiveness of Privacy Mechanisms for Location Sharing. CMU Technical Report CMU-ISR-08-141, December.
• Sandholm, T. 2007. Expressive Commerce and Its Application to Sourcing: How We Conducted $35 Billion of Generalized Combinatorial Auctions. AI Magazine, 28(3), 45-58, Fall. Conference version in IAAI-06, Deployed Application Award.
• Sandholm, T., Levine, D., Concordia, M., Martyn, P., Hughes, R., Jacobs, J., and Begg, D. 2006. Changing the Game in Strategic Sourcing at Procter Gamble: Expressive Competition Enabled by Optimization. (For the Franz Edelman Award submission by P&G and CombineNet.) Interfaces 36(1), 55-68. Special issue on the 2005 Edelman award competition.
• Sandholm, T. and Suri, S. 2006. Side Constraints and Non-Price Attributes in Markets. Games and Economic Behavior 55: 321-330, Note. Longer earlier version in IJCAI-01 Workshop on Distributed Constraint Reasoning.
• Parkes, D. and Sandholm, T. 2005. Optimize-and-Dispatch Architecture for Expressive Ad Auctions. In Proceedings of the First Workshop on Sponsored Search Auctions, at the ACM Conference on Electronic Commerce.
• Sandholm, T. 2002. eMediator: A Next Generation Electronic Commerce Server. Computational Intelligence 18(4): 656-676, Special issue on Agent Technology for Electronic Commerce. Early versions: In Proceedings of the International Conference on Autonomous Agents (AGENTS), Barcelona, Spain, June 3-8, 2000; In Proceedings of the AAAI-99 Workshop on AI in Electronic Commerce, p. 46-55; Washington University CS tech report January 1999. (First combinatorial auction on the Internet? Running since 1998.)
• Sandholm, T. 1999. eMediator: A Next Generation Electronic Commerce Server. At the National Conference on Artificial Intelligence (AAAI), Intelligent Systems Demonstration Program (refereed demonstration), AAAI proceedings pp. 923-924.

Multi-item markets (combinatorial auctions and generalizations)

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

• Dickerson, J. and Sandholm, T. 2013. Throwing darts: Random sampling helps tree search when the number of short certificates is moderate. Annual Symposium on Combinatorial Search (SoCS). (Also, 2-page version in AAAI-13 late-breaking paper track.)
• Gilpin, A. and Sandholm, T. 2011. Information-Theoretic Approaches to Branching in Search. Discrete Optimization, 8, 147-159. Significantly extends the IJCAI-07 version.
• Sandholm, T. and Shields, R. 2006. Nogood Learning for Mixed Integer Programming. CMU Computer Science Department technical report CMU-CS-06-155. (Short version presented at the workshop on “Hybrid methods and branching rules in combinatorial optimization”, Centre de recherches mathématiques, Concordia University, Montreal, 2006.
• Sandholm, T. 2006. Optimal Winner Determination Algorithms. Chapter 14 of the book Combinatorial Auctions, Cramton, Shoham, and Steinberg, eds., MIT Press.
• Lehmann, D., Mueller, R., and Sandholm, T. 2006. The Winner Determination Problem. Chapter 12 of the book Combinatorial Auctions, Cramton, Shoham, and Steinberg, eds., MIT Press.
• Conitzer, V., Derryberry, J., and Sandholm, T. 2004. Combinatorial Auctions with Structured Item Graphs. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
• Kothari, A., Sandholm, T., and Suri, S. 2002. Solving Combinatorial Exchanges: Optimality via a Few Partial Bids. In Proceedings of the AAAI-02 workshop on AI for Intelligent Business. Also: Proceedings of the ACM Conference on Electronic Commerce 2003, short paper.
• Sandholm, T., Suri, S., Gilpin, A., and Levine, D. 2002. Winner Determination in Combinatorial Auction Generalizations. In Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS). Early version: In Proceedings of the AGENTS-01 Workshop on Agent-based Approaches to B2B.
• Sandholm, T., Suri, S., Gilpin, A., and Levine, D. 2005. CABOB: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions. Management Science 51(3), 374-390, special issue on Electronic Markets. (Earlier version in IJCAI-01.)
• Sandholm, T. and Suri, S. 2003. BOB: Improved Winner Determination in Combinatorial Auctions and Generalizations. Artificial Intelligence, 145, 33-58. Early version: Improved Algorithms for Optimal Winner Determination in Combinatorial Auctions and Generalizations. In Proceedings of the National Conference on Artificial Intelligence (AAAI), 2000.
• Sandholm, T. 2002. Algorithm for Optimal Winner Determination in Combinatorial Auctions. Artificial Intelligence, 135, 1-54. World’s 24^th most cited 2001 paper in computer science. (Early version appeared as an invited talk at ICE-98, as a tech report 1/99, and as a paper in the Proceedings of IJCAI-99 =world’s 35^th most cited 1999 paper in computer science).

Market anomalies

• Conitzer, V. and Sandholm, T. 2006. Failures of the VCG mechanism in combinatorial auctions and exchanges. In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS). (Early version in AMEC-04.)
• Gilpin, A. and Sandholm, T. 2004. Arbitrage in combinatorial exchanges. Agent-Mediated Electronic Commerce (AMEC) workshop.

Multi-unit markets

• Sandholm, T. and Suri, S. 2002. Optimal Clearing of Supply/Demand Curves. In Proceedings of the 13^th Annual International Symposium on Algorithms and Computation (ISAAC), Vancouver, Canada. Also: AAAI-02 workshop on Agent-Based B2B Electronic Commerce Technologies.
• Sandholm, T. and Suri, S. 2001. Market Clearability. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).

Kidney exchange, matching markets, barter exchanges

• Blum, A., Dickerson, J., Haghtalab, N., Procaccia, A., Sandholm, T., and Sharma, A. 2020. Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries. Operations Research 68(1): 16-34.
• Dickerson, J., Procaccia, A., and Sandholm, T. 2019. Failure-Aware Kidney Exchange. Management Science 65(4):1768-1791.
• Dickerson, J. and Sandholm, T. 2017. Multi-Organ Exchange. Journal of Artificial Intelligence Research 60: 639-679.
• Farina, G., Dickerson, J., and Sandholm, T. 2017. Operation Frames and Clubs in Kidney Exchange. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). ArXiv version. Early version, Inter-Club Kidney Exchange, in AAAI-17 Workshop on AI and OR for Social Good (AIORSocGood-17).
• Farina, G., Dickerson, J., and Sandholm, T. 2017. Multiple Willing Donors and Organ Clubs in Kidney Exchange. Algorithmic Game Theory (AGT) workshop at the International Joint Conference on Artificial Intelligence (IJCAI).
• Sandholm, T., Farina, G., Dickerson, J., Leishman, R., Stewart, D., Formica, R., Thiessen, C., and Kulkarni, S. 2017. A Novel KPD Mechanism to Increase Transplants When Some Candidates Have Multiple Willing Donors. American Transplant Congress (ATC), poster.
• Leishman, R., Aeder, M., Leffell, S., Murphey, C., Reinsmoen, N., Saidman, S., Sandholm, T., Toll, A., Harper, A., and Turgeon, N. 2017. Effects of New KPD Histocompatibility Policy on Refusal Rate and Transplants. American Transplant Congress (ATC), oral and poster.
• Dickerson, J., Kazachkov, A., Procaccia, A., and Sandholm, T. 2017. Small Representations of Big Kidney Exchange Graphs. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). Extended version on arXiv.
• Dickerson, J., Manlove, D., Plaut, B., Sandholm, T., and Trimble J. 2016. Position-Indexed Formulations for Kidney Exchange. In Proceedings of the ACM Conference on Economics and Computation (EC). Extended version.
• Plaut, B., Dickerson, J., and Sandholm, T. 2016. Hardness of the Pricing Problem for Chains in Barter Exchanges. arXiv
• Plaut, B., Dickerson, J., and Sandholm, T. 2016. Fast Optimal Clearing of Capped-Chain Barter Exchanges. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI).
• Dickerson, J. and Sandholm, T. 2015. FutureMatch: Combining Human Value Judgments and Machine Learning to Match in Dynamic Environments. In Proceedings of the AAAI Conference on Artificial Intelligence. Extended version with appendix.
• Hajaj, C., Dickerson, J., Hassidim, A., Sandholm, T., and Sarne, D. 2015. Strategy-Proof and Efficient Kidney Exchange Using a Credit Mechanism. In Proceedings of the AAAI Conference on Artificial Intelligence.
• Leishman, R., Stewart, D., Kucheryavaya, A., Callahan, L., Sandholm, T., Aeder, M. 2015. Reasons for Match Offer Refusals and Efforts to Reduce them in the OPTN/UNOS Kidney Paired Donation Pilot Program (KPDPP). American Transplant Congress (ATC). Slides.
• Aeder, M., Stewart, D., Leishman, R., Callahan, L., Kucheryavaya, A., Sandholm, T., Formica, R. 2015. Impact of Cold Ischemic Time (CIT) and Distance Traveled on Shipped Kidneys in the OPTN/UNOS Kidney Paired Donation (KPD) Pilot Program (PP). American Transplant Congress (ATC).
• Das, S., Dickerson, J., Li, Z., and Sandholm, T. 2015. Competing Dynamic Matching Markets. In Proceedings of the Conference on Auctions, Market Mechanisms and Their Applications (AMMA).
• Dickerson, J., Procaccia, A., and Sandholm, T. 2014. Price of Fairness in Kidney Exchange. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Dickerson, J. and Sandholm, T. 2014. Balancing Efficiency and Fairness in Dynamic Kidney Exchange. In Proceedings of the Modern Artificial Intelligence for Health Analytics (MAIHA) workshop at AAAI-14.
• Dickerson, J., Procaccia, A., and Sandholm, T. 2014. Empirical Price of Fairness in Failure-Aware Kidney Exchange. Towards Better and more Affordable Healthcare: Incentives, Game Theory, and Artificial Intelligence (HCAGT) workshop at AAMAS-14.
• Leishman, R., Stewart, D., Monstello, C., Cherikh, W., Sandholm, T., Formica, R., Aeder, M. 2014. The OPTN Kidney Paired Donation Pilot Program (KPDPP): Reaching the Tipping Point in 2013. World Transplant Congress (WTC). Abstract, presentation.
• Aeder, M., Stewart, D., Leishman, R., Sandholm, T., Formica, R. 2014. Early Outcomes of Transplant Recipients in the OPTN Kidney Paired Donation Pilot Program. World Transplant Congress (WTC). Abstract, presentation.
• Stewart, D., Leishman, R., Kucheryavaya, A., Formica, R., Aeder, M., Bingaman, A., Gentry, S., Sandholm, T., and Ashlagi, I. 2014. Exploring the Candidate/Donor Compatibility Matrix to Identify Opportunities to Improve the OPTN KPD Pilot Program's Priority Point Schedule. World Transplant Congress (WTC). Abstract, poster.
• Leishman, R., Formica, R., Andreoni, K., Friedewald, J., Sleeman, E., Monstello, C., Stewart, D., and Sandholm, T. 2013. The Organ Procurement and Transplantation Network (OPTN) Kidney Paired Donation Pilot Program (KPDPP): Review of Current Results. American Transplant Congress (ATC). Abstract of talk.
• Leishman, R., Formica, R., Andreoni, K., Friedewald, J., Sleeman, E., Monstello, C., Stewart, D., and Sandholm, T. 2013. An Early Look at Transplant Outcomes from the OPTN KPD Pilot Program: Comparing Cold Times and DGF Rates with Other Living and Deceased Donor Transplants. American Transplant Congress (ATC). Abstract of talk.
• Stewart, D., Leishman, R., Sleeman, E., Monstello, C., Lunsford, G., Maghirang, J., Sandholm, T., Gentry, S., Formica, R., Friedewald, J., and Andreoni, K. 2013. Tuning the OPTN's KPD Optimization Algorithm to Incentivize Centers to Enter Their "Easy-to-Match" Pairs. American Transplant Congress (ATC). Abstract of talk.
• Dickerson, J., Procaccia, A., and Sandholm, T. 2012. Dynamic Matching via Weighted Myopia with Application to Kidney Exchange. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
• Dickerson, J., Procaccia, A., and Sandholm, T. 2012. Optimizing Kidney Exchange with Transplant Chains: Theory and Reality. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Woodle, S., Daller, J., Aeder M., Shapiro, R., Sandholm, T., Casingal, V., Goldfarb, D., Lewis, R., Goebel, J., and Siegler, M. 2010. Ethical Considerations for Participation of Nondirected Living Donors in Kidney Exchange Programs. American Journal of Transplantation 10: 1460-1467.
• Awasthi, P. and Sandholm, T. 2009. Online Stochastic Optimization in the Large: Application to Kidney Exchange. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Rees, M., Kopke, J., Pelletier, R., Segev, D., Fabrega, A., Rogers, J., Pankewycz, O., Hiller, J., Roth, A., Sandholm, T., Ünver, U., Nibhanubpudy, R., Bowers, V., VanBuren, C., and Montgomery, R. 2009. Six Nonsimultaneous Extended Altruistic Donor (NEAD) Chains. American Transplant Congress (ATC).
• Rees, M., Kopke, J., Pelletier, R., Segev, D., Rutter, M., Fabrega, A., Rogers, J., Pankewycz, O., Hiller, J., Roth, A., Sandholm, T., Ünver, U., and Montgomery, R. 2009. A Nonsimultaneous, Extended, Altruistic-Donor Chain. New England Journal of Medicine 360(11), 1096-1101.
• Abraham, D., Blum, A., and Sandholm, T. 2007. Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. In Proceedings of the ACM Conference on Electronic Commerce (EC).

(Automated) market making and prediction markets

• Othman, A., Pennock, D., Reeves, D., and Sandholm, T. 2013. A Practical Liquidity-Sensitive Automated Market Maker. ACM Transaction on Economics and Computation (TEAC), 1(3), Article 14, 25 pages. (Conference version in EC-10.)
• Othman, A. and Sandholm, T. 2013. The Gates Hillman prediction market. Review of Economic Design, 17(2), 95-128. (Conference version "Automated Market-Making in the Large: The Gates Hillman Prediction Market" in EC-10.)
• Othman, A. and Sandholm, T. 2012. Profit-Charging Market Makers with Bounded Loss, Vanishing Bid/Ask Spreads, and Unlimited Market Depth. In Proceedings of the ACM Conference on Electronic Commerce (EC).
• Othman, A. and Sandholm, T. 2012. Rational Market Making with Probabilistic Knowledge. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Othman, A. and Sandholm, T. 2011. Inventory-based versus Prior-based Options Trading Agents. Algorithmic Finance 1:95-121.
• Othman, A. and Sandholm, T. 2011. Liquidity-Sensitive Automated Market Makers via Homogeneous Risk Measures. Workshop on Internet And Network Economics (WINE).
• Othman, A. and Sandholm, T. 2011. Automated Market Makers That Enable New Settings: Extending Constant-Utility Cost Functions. In Proceedings of the Conference on Auctions, Market Mechanisms and Their Applications (AMMA).
• Othman, A. and Sandholm, T. 2010. Decision Rules and Decision Markets. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Othman, A. and Sandholm, T. 2010. When Do Markets with Simple Agents Fail? In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).

Online algorithms for exchanges

• Blum, A., Sandholm, T., and Zinkevich, M. 2006. Online Algorithms for Market Clearing. Journal of the ACM, Vol. 53, No. 5, pp. 845-879. (Conference version in SODA-02.)

Preference elicitation, “ascending” auctions & coherent pricing

Overview

• Sandholm, T. and Boutilier, C. 2006. Preference Elicitation in Combinatorial Auctions. Chapter 10 of the book Combinatorial Auctions, Cramton, Shoham, and Steinberg, eds., MIT Press.

The original paper on preference elicitation in combinatorial auctions

• Conen, W. and Sandholm, T. 2001. Preference Elicitation in Combinatorial Auctions: Extended Abstract. In Proceedings of the ACM Conference on Electronic Commerce (EC).
• Conen, W. and Sandholm, T. 2001. Minimal Preference Elicitation in Combinatorial Auctions. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Workshop on Economic Agents, Models, and Mechanisms.

Effectiveness of preference elicitation in general combinatorial auctions

• Hudson, B. and Sandholm, T. 2004. Effectiveness of Query Types and Policies for Preference Elicitation in Combinatorial Auctions. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS). Partly subsumes the papers:
1. Effectiveness of Preference Elicitation in Combinatorial Auctions. In Proceedings of the Agent-Mediated Electronic Commerce (AMEC) workshop at AAMAS-02 (also: Carnegie Mellon University, Computer Science Department technical report CMU-CS-02-124, and Stanford Institute of Theoretical Economics (SITE-02) summer school).
2. Using Value Queries in Combinatorial Auctions. Poster paper in Proceedings of the ACM Conference on Electronic Commerce (EC-03). Extended draft.
3. Generalizing Preference Elicitation in Combinatorial Auctions. Poster paper in Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-03). Extended draft.
• Conen, W. and Sandholm, T. 2002. Partial-Revelation VCG Mechanism for Combinatorial Auctions. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
• Conen, W. and Sandholm, T. 2002. Differential-Revelation VCG Mechanisms for Combinatorial Auctions. In Proceedings of theAgent-Mediated Electronic Commerce (AMEC) workshop.

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

• Conitzer, V. and Sandholm, T., and Santi, P. 2005. Combinatorial Auctions with k-wise Dependent Valuations. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
• Santi, P., Conitzer, V., and Sandholm, T. 2004. Towards a Characterization of Polynomial Preference Elicitation with Value Queries in Combinatorial Auctions. In Proceedings of the Conference on Computational Learning Theory (COLT).
• Blum, A., Jackson, J., Sandholm, T. and Zinkevich, M. 2004. Preference Elicitation and Query Learning. Journal of Machine Learning Research (JMLR), 5: 649-667. (Early version in COLT-03.)
• Zinkevich, M., Blum, A. and Sandholm, T. 2003. On Polynomial-Time Preference Elicitation with Value Queries. In Proceedings of the ACM Conference on Electronic Commerce (EC).

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

• Smith, T., and Sandholm, T. and Simmons, R. 2002. Constructing and Clearing Combinatorial Exchanges Using Preference Elicitation. In Proceedings of the AAAI-02 workshop on Preferences in AI and CP: Symbolic Approaches.

Coherent pricing

• Conen, W. and Sandholm, T. 2004. Coherent Pricing of Efficient Allocations in Combinatorial Economies. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 254-260, New York, July 19-23. Earlier version in Proceedings of the AAAI-02 workshop on Game-Theoretic and Decision-Theoretic Agents.

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

• Boutilier, C., Sandholm, T., and Shields, R. 2004. Eliciting bid taker non-price preferences in (Combinatorial) Auctions. In Proceedings of the National Conference on Artificial Intelligence (AAAI).

Auction design for spiteful bidders

• Tang, P. and Sandholm, T. 2012. Optimal Auctions for Spiteful Bidders. In Proceedings of the AAAI Conference on Artificial Intelligence.
• Sharma, A. and Sandholm, T. 2010. Asymmetric Spite in Auctions. In Proceedings of the AAAI Conference on Artificial Intelligence.
• Brandt, F., Sandholm, T., and Shoham, Y. 2007. Spiteful Bidding in Sealed-Bid Auctions. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). (Early version in GTDT-05.)

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

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

• Larson, K. and Sandholm, T. 2005. Mechanism Design and Deliberative Agents. Proceedings of the International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS). Early versions: Designing Auctions for Deliberative Agents in the AAMAS-04 workshop on Agent Mediated Electronic Commerce (AMEC-04), Springer LNCS 3435; Strategic Deliberation and Truthful Revelation: An Impossibility Result in Proceedings of the ACM Conference on Electronic Commerce (EC-04).
• Larson, K. and Sandholm, T. 2004. Experiments on Deliberation Equilibria in Auctions. In Proceedings of the International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).
• Larson, K. and Sandholm, T. 2003. Miscomputing Ratio: The Social Cost of Selfish Computing. In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS). Early version: In Proceedings of the AAAI-02 workshop on Game-Theoretic and Decision-Theoretic Agents.
• Larson, K. and Sandholm, T. 2001. Costly Valuation Computation in Auctions. In Proceedings of the Theoretical Aspects of Reasoning about Knowledge (TARK).
• Larson, K. and Sandholm, T. 2001. Computationally Limited Agents in Auctions. In Proceedings of the International Conference on Autonomous Agents, Workshop on Agent-based Approaches to B2B.
• Sandholm, T. 2000. Issues in Computational Vickrey Auctions. International Journal of Electronic Commerce, 4(3), 107-129. Special issue on Intelligent Agents for Electronic Commerce. invited reviewed submission. (Early version in Proceedings of ICMAS-96.)

Other

• Sandholm, T. and Ygge, F. 1999. Constructing Speculative Demand Functions in Equilibrium Markets. Washington University, Department of Computer Science, WUCS-99-26. October 14th (Early version in IJCAI-97)
• Brainov, S. and Sandholm, T. 2000. Reasoning About Others: Representing and Processing Infinite Belief Hierarchies. In Proceedings of the International Conference on Multi-Agent Systems (ICMAS).(Auctions without common knowledge)
• Sandholm, T. and Huai, Q. 2000. Nomad: Mobile Agent System for an Internet-Based Auction House. IEEE Internet Computing, 4(2), 80-86, Mar/Apr, Special issue on Agent Technology and the Internet.

Peer-to-peer negotiation, bargaining & trading

Valuation calculation & normative models of bounded rationality

• Larson, K. and Sandholm, T. 2002. An Alternating Offers Bargaining Model for Computationally Limited Agents. In Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Larson, K. and Sandholm, T. 2001. Bargaining with Limited Computation: Deliberation Equilibrium. Artificial Intelligence, 132(2), 183-217.
• Sandholm, T. 1993. An Implementation of the Contract Net Protocol Based on Marginal Cost Calculations. In Proceedings of the Eleventh National Conference on Artificial Intelligence (AAAI). (World’s first use of combinatorial bidding to allocate trucking tasks; built 1990-91.)

Other

• Sandholm, T. and Vulkan, N. 2002. Bargaining with Deadlines. Early version appeared in Proceedings of the National Conference on Artificial Intelligence (AAAI), 1999.
• Sandholm, T. 2000. Agents in Electronic Commerce: Component Technologies for Automated Negotiation and Coalition Formation. Autonomous Agents and Multi-Agent Systems, 3(1), 73-96. Special Issue on Best of ICMAS-98, invited submission, reviewed.
• Andersson, M. and Sandholm, T. 2000. Contract Type Sequencing for Reallocative Negotiation. In Proceedings of the International Conference on Distributed Computing Systems (ICDCS).
• Andersson, M. and Sandholm, T. 1999. Time-Quality Tradeoffs in Reallocative Negotiation with Combinatorial Contract Types. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
• Sandholm, T. 1998. Contract Types for Satisficing Task Allocation: I Theoretical Results. In Proceedings of the AAAI Spring Symposium.
• Sandholm, T. 1997. Necessary and Sufficient Contract Types for Optimal Task Allocation. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). Poster presentation.
• Sandholm, T. and Lesser, V. 1995. Issues in Automated Negotiation and Electronic Commerce: Extending the Contract Net Framework. In Proceedings of the International Conference on Multiagent Systems (ICMAS).
• Neiman, D., Hildum, D., Lesser, V. and Sandholm, T. 1994. Exploiting Meta-Level Information in a Distributed Scheduling System. In Proceedings of the National Conference on Artificial Intelligence (AAAI-94).

Leveled commitment contracts & breach (backtracking in multiagent systems)

Overview

• Sandholm, T. and Lesser, V. 2002. Leveled Commitment Contracting: A Backtracking Instrument for Multiagent Systems. AI Magazine 23 (3): 89-100.

Single leveled commitment contract

• Sandholm, T. and Lesser, V. 2001. Leveled Commitment Contracts and Strategic Breach. Games and Economic Behavior, 35, 212-270. Special issue on AI and Economics. (Early version in AAAI-96)
• Sandholm, T. and Zhou, Y. 2002. Surplus Equivalence of Leveled Commitment Contracts. Artificial Intelligence 142, 239-264. (Early version in ICMAS-00.)
• Sandholm, T., Sikka, S. and Norden, S. 1999. Algorithms for Optimizing Leveled Commitment Contracts. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).

Sequences of leveled commitment contracts

• Andersson, M. and Sandholm, T. 2001. Leveled Commitment Contracts with Myopic and Strategic Agents. Journal of Economic Dynamics and Control, 25, 615-640. Special issue on Agent-Based Computational Economics. (Early version in AAAI-98)
• Andersson, M. and Sandholm, T. 1998. Leveled Commitment Contracting among Myopic Individually Rational Agents. In Proceedings of the Proceedings of the Third International Conference on Multiagent Systems (ICMAS).

Safe exchange & deviation-proof multiagent plans

A general framework

• Sandholm, T. and Wang, X. 2002. (Im)possibility of Safe Exchange Mechanism Design. In Proceedings of the National Conference on Artificial Intelligence (AAAI).

Methods based on dividing the exchange into chunks

• Sandholm, T. and Ferrandon, V. 2000. Safe Exchange Planner. (ps) (pdf) In Proceedings of the International Conference on Multi-Agent Systems (ICMAS).
• Sandholm, T. 1997. Unenforced Ecommerce Transactions. IEEE Internet Computing, 1(6), 47-54, Nov-Dec, Special issue on Electronic Commerce.
• Sandholm, T. 1996. Negotiation among Self-Interested Computationally Limited Agents. Ph.D. Dissertation. University of Massachusetts at Amherst, Department of Computer Science. Chapter 5.
• Sandholm, T. and Lesser, V. 1995. Equilibrium Analysis of the Possibilities of Unenforced Exchange in Multiagent Systems. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).

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

• Brainov, S. and Sandholm, T. 2002. Contracting with Uncertain Level of Trust. Computational Intelligence 18(4):501-514, Special issue on Agent Technology for Electronic Commerce. (Early version in ACM Conference on Electronic Commerce (EC), 1999.)
• Brainov, S. and Sandholm, T. 2003. Auctions with Untrustworthy Bidders. In Proceedings of the IEEE Conference on Electronic Commerce. Extended version.

Stability (deviation-proofness) of multiagent plans

• Brainov, S. and Sandholm, T. 1999. Power, Dependence and Stability in Multiagent Plans. In Proceedings of the National Conference on Artificial Intelligence (AAAI).

Coalition formation

• Ohta, N., Iwasaki, A., Yokoo, M., Maruono, K., Conitzer, V., and Sandholm, T. 2006. A Compact Representation Scheme for Coalitional Games in Open Anonymous Environments. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
• Conitzer, V. and Sandholm, T. 2006. Complexity of Constructing Solutions in the Core Based on Synergies Among Coalitions. Artificial Intelligence, 170: 607-619(Early versions in IJCAI-03, DCR-02, and CMU-CS-02-137.)
• Yokoo, M., Conitzer, V., Sandholm, T., Ohta., N., and Iwasaki, A. 2005. Coalitional Games in Open Anonymous Environments. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
• Conitzer, V. and Sandholm, T. 2004. Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
• Sandholm, T., Larson, K., Andersson, M., Shehory, O., and Tohmé, F. 1999. Coalition Structure Generation with Worst Case Guarantees. Artificial Intelligence, 111(1-2), 209-238.
• Sandholm, T. and Lesser, V. 1997. Coalitions among Computationally Bounded Agents. Artificial Intelligence, 94(1), 99-137, Special issue on Economic Principles of Multiagent Systems.
• Tohmé, F. and Sandholm, T. 1999. Coalition Formation Processes with Belief Revision among Bounded Rational Self-Interested Agents. Journal of Logic and Computation, 9(6), 793-815.
• Larson, K. and Sandholm, T. 2000. Anytime Coalition Structure Generation: An Average Case Study. Journal of Experimental and Theoretical AI, 12, 23-42.

Machine learning

Multiagent learning

• Sandholm, T. 2007. Perspectives on Multiagent Learning. Artificial Intelligence, 171, 382-391. Special issue on multiagent learning.
• Conitzer, V. and Sandholm, T. 2007. AWESOME: A General Multiagent Learning Algorithm that Converges in Self-Play and Learns a Best Response Against Stationary Opponents. Machine Learning, 67, 23-43, special issue on Learning and Computational Game Theory. (Short version in ICML-03.)
• Conitzer, V. and Sandholm, T. 2004. Communication Complexity as a Lower Bound for Learning in Games. In Proceedings of the International Conference on Machine Learning (ICML).
• Wang, X. and Sandholm, T. 2003. Learning Near-Pareto-Optimal Conventions in Polynomial Time. In Proceedings of the Neural Information Processing Systems: Natural and Synthetic (NIPS) conference.
• Conitzer, V. and Sandholm, T. 2003. BL-WoLF: A Framework For Loss-Bounded Learnability In Zero-Sum Games. In Proceedings of the International Conference on Machine Learning (ICML).
• Wang, X. and Sandholm, T. 2002. Reinforcement Learning to Play An Optimal Nash Equilibrium in Team Markov Games. In Proceedings of the Neural Information Processing Systems: Natural and Synthetic (NIPS) conference. Extended version.
• Sandholm, T. and Crites, R. 1995. Multiagent Reinforcement Learning in the Iterated Prisoner's Dilemma. Biosystems, 37, 147-166, Special Issue on the Prisoner's Dilemma.

Single-agent learning

• Berkman, N. and Sandholm, T. 1995. What should be minimized in a decision tree: A re-examination. University of Massachusetts at Amherst, Computer Science Technical Report TR 95-20.
• Sandholm. T., Brodley, C., Vidovic, A. and Sandholm, M. 1996. Comparison of Regression Methods, Symbolic Induction Methods and Neural Networks in Morbidity Diagnosis and Mortality Prediction in Equine Gastrointestinal Colic. Working Notes of the AAAI Spring Symposium Series, Artificial Intelligence in Medicine: Applications of Current Technologies.
• Honkela, T. and Sandholm, T. 1993. Machine Learning. In the Finnish Encyclopedia of Artificial Intelligence, Eero Hyvönen, ed., pp. 244-255.
• Sandholm, T. 1991. Solving the 1-Dimensional Fractal Inverse Problem with a Genetic Algorithm. In Genetic Algorithms, Jarmo T. Alander, ed., pp. 126-132, Publications of the Helsinki University of Technology.

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

• Larson, K. and Sandholm, T. 2004. Using Performance Profile Trees to Improve Deliberation Control. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
• Conitzer, V. and Sandholm, T. 2003. Definition and Complexity of Some Basic Metareasoning Problems. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Sandholm, T. 2003. Terminating Decision Algorithms Optimally. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), poster paper, Springer LNCS 2833. Extended version. Rough early versions: Sandholm, T. and Lesser, V. 1994. Utility-Based Termination of Anytime Algorithms. In Proceedings of the European Conference on Artificial Intelligence (ECAI) Workshop on Decision Theory for DAI Applications; University of Massachusetts at Amherst, Computer Science TR 94-54.

Privacy in social choice (voting and auctions), cryptography

• Brandt, F. and Sandholm, T. 2008. On the Existence of Unconditionally Privacy-Preserving Auction Protocols. ACM Transactions on Information and System Security, 11(2), Article 10, 21 pages. Conference version in AAMAS-04.
• Brandt, F. and Sandholm, T. 2005. Unconditional Privacy in Social Choice. In Proceedings of the Theoretical Aspects of Reasoning about Knowledge (TARK) conference.
• Brandt, F. and Sandholm, T. 2005. Efficient Privacy-Preserving Protocols for Multi-Unit Auctions. In Proceedings of the International Conference on Financial Cryptography and Data Security (FC), published in Springer Lecture Notes in Computer Science LNCS 3570.
• Brandt, F. and Sandholm, T. 2005. Decentralized Voting with Unconditional Privacy. In Proceedings of the International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).
• Brandt, F. and Sandholm, T. 2004. On Correctness and Privacy in Distributed Mechanisms In Proceedings of the Agent-Mediated Electronic Commerce (AMEC) workshop, Springer LNAI 3937.

Satisfiability & constraint satisfaction

• Sandholm, T. 1996. A Second Order Parameter for 3SAT. In Proceedings of the National Conference on Artificial Intelligence (AAAI).

Networks

• Suri, S., Sandholm, T. and Warkhede, P. 2003. Compressing 2-Dimensional Routing Tables. Algorithmica 35(4): 287-300. (Early version “Optimal Flow Aggregation” in SWAT-00.)

---

Hobbies

Adventures

Family

---