Tuomas Sandholm Professor Director, Agent-Mediated Electronic Marketplaces Laboratory Carnegie Mellon University Computer Science Department 5000 Forbes Avenue Pittsburgh, PA 15213 Affiliated Professor Machine Learning Department sandholm AT cs.cmu.edu (412) 268-8216 (office) Office: Gates Hillman Center room 9205 Executive assistant: Charlotte Yano yano AT cs.cmu.edu (412) 268-7656, Gates Hillman Center room 8118

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

---

Academic awards (some; full list on the CV below)

• 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).
• Alfred P. Sloan Research Fellow 2003-2005
• Inaugural ACM Autonomous Agents Research Award 2001
• National Science Foundation Career Award 1997
• Fellow of the ACM and AAAI, 2008.

Curriculum vitae, research statement, and teaching statement.

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

• CS 15-892 Foundations of Electronic Marketplaces (Fall 2011)
• CS 15-780 / RI 16-731 Advanced AI (cross-listed in the Robotics Institute as Fundamentals of AI for Robotics) (Spring 2011)
• CS 15-892 Foundations of Electronic Marketplaces (Fall 2009)
• MS in Ecommerce Mini-Course 20-853: Electronic Negotiation
• CS 15-381 Artificial Intelligence
• CS 15-780 / RI 16-731 Advanced AI (cross-listed in the Robotics Institute as Fundamentals of AI for Robotics) (Spring 2009)

Hiring PhD students as Graduate Research Assistants.

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)

• 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

• 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). on Advances on Preference Handling.)
• 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 (ACM-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). (Early version in IJCAI-03 Workshop on Distributed Constraint Reasoning.)
• 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.)

• Sandholm, T., Likhodedov, A., and Gilpin, A. Automated Design of Revenue-Maximizing Combinatorial Auctions. Operations Research, Special Issue on Computational Economics, to appear. (Subsumes and extends over a AAAI-05 paper and a AAAI-04 paper.)
• 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 National Conference on Artificial Intelligence (AAAI).
• 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 mechanism & 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)

Sequential games, poker

• Gilpin, A., Peña, J., and Sandholm, T. First-Order Algorithm with O(ln(1/epsilon)) Convergence for epsilon-Equilibrium in Two-Person Zero-Sum Games. Mathematical Programming, to appear. Subsumes our AAAI-08 paper.
• 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).
• Ganzfried, S., Sandholm, T., and Waugh, K. 2011. Strategy Purification. National Conference on Artificial Intelligence (AAAI) Workshop on Applied Adversarial Reasoning and Risk Modeling. 2-page abstract in Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• 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.
• 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 National Conference on Artificial Intelligence (AAAI).
• 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 Troels Bjerre Sørensen 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 Soerensen, 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 theNational Conference on Artificial Intelligence (AAAI).

Poker demonstrations (reviewed)

• 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.

Normal form games and repeated games

• 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 (ACM-EC).

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

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 (ACM-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

• Conitzer, V. and Sandholm, T. 2005. Common Voting Protocols as Maximum Likelihood Estimators. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI).

Expressive commerce, expressive bidding, combinatorial auctions, expressive negotiation

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; Ad auctions and exchanges; Display (banner) ads; Sponsored search

• 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 (ACM-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 National Conference on Artificial Intelligence (AAAI). 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 National Conference on Artificial Intelligence (AAAI).
• 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 National Conference on Artificial Intelligence (AAAI).
• 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 National Conference on Artificial Intelligence (AAAI).
• 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 National Conference on Artificial Intelligence (AAAI).
• 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

• 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

• 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., 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. 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. Automated Market-Making in the Large: The Gates Hillman Prediction Market. In Proceedings of the ACM Conference on Electronic Commerce (EC).
• Othman, A., Pennock, D., Reeves, D., and Sandholm, T. 2010. A Practical Liquidity-Sensitive Automated Market Maker. In Proceedings of the ACM Conference on Electronic Commerce (EC).
• 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 (ACM-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. Poster paper in Proceedings of the ACM Conference on Electronic Commerce (ACM-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 (ACM-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).

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 (ACM-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

• Sharma, A. and Sandholm, T. 2010. Asymmetric Spite in Auctions. In Proceedings of the National Joint Conference on Artificial Intelligence (AAAI).
• 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.)
• 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-92.)

Other

• Sandholm, T. and Vulkan, N. 2002. Bargaining with Deadlines. Early version appeared in Proceedings of the National Conference on Artificial Intelligence (AAAI), 1999.
• Andersson, M. and Sandholm, T. 1999. Time-Quality Tradeoffs in Reallocative Negotiation with Combinatorial Contract Types. National Conference on Artificial Intelligence (AAAI), pp. 3-10, Orlando, FL. (Acceptance rate 27%).
• 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.
• Sandholm, T. 2000. Approaches to Winner Determination in Combinatorial Auctions. Decision Support Systems, to appear.
• 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 Fourteenth 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 First 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. Twelfth National Conference on Artificial Intelligence (AAAI-94), Seattle, Washington, pp. 394-400. (Acceptance rate 31%)
• Neiman, D., Hildum, D., Lesser, V. and Sandholm, T. 1994. Exploiting Meta-Level Information in a Distributed Scheduling System. In Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI).

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. and Crites, R. 1995. Multiagent Reinforcement Learning in the Iterated Prisoner's Dilemma. Biosystems, 37, 147-166, Special Issue on the Prisoner's Dilemma.
• 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 (ACM-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.
• Sandholm, T. and Lesser, V. 1994. Utility-Based Termination of Anytime Algorithms. Extended version. University of Massachusetts at Amherst, Computer Science Technical Report TR 94-54.

Single-agent learning

• Sandholm, T. and Lesser, V. 1994. Utility-Based Termination of Anytime Algorithms. Extended version. University of Massachusetts at Amherst, Computer Science Technical Report TR 94-54.

• 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. and Crites, R. 1995. On Multiagent Q-Learning in a Semi-competitive Domain. 14th International Joint Conference on Artificial Intelligence (IJCAI-95), Workshop on Adaptation and Learning in Multiagent Systems, Montreal, Canada, pp. 71-77.

• 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 Thirteenth 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

---