|
|
|
Research interests: Electronic commerce; game theory; mechanism design; artificial intelligence; multiagent systems; auctions and exchanges; automated negotiation and contracting; voting; coalition formation; safe exchange; search, integer programming and combinatorial optimization; preference elicitation; normative models of bounded rationality; resource-bounded reasoning; privacy; multiagent reinforcement learning.
Academic awards
·
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.
Recent courses
taught:
·
CS 15-892
Foundations of Electronic Marketplaces (Fall 2009)
·
CS 15-780 / RI
16-731 Advanced AI, aka Fundamentals of AI for Robotics (Spring 2009)
·
MS in Ecommerce
Mini-Course 20-853: Electronic Negotiation
· CS 15-381 Artificial Intelligence
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
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 version in IBC-05.)
- Conitzer, V. and Sandholm, T. 2007. Incremental Mechanism Design. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). (Early version in ECAI-06 workshop 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).
AMD for auctions, other selling mechanisms,
and online mechanisms. (See also AMD work listed in section “Safe
Exchange” below.)
- 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).
- Likhodedov, A. and Sandholm, T. 2005. Approximating Revenue-Maximizing Combinatorial Auctions. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
- Likhodedov, A. and Sandholm, T. 2004. Methods for Boosting Revenue in Combinatorial Auctions. 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. Short paper in proceedings of the ACM Conference on Electronic Commerce. Extended version. (Early version in AMEC-03.)
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
- 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., Peña, J., and Sandholm, T. 2008. First-Order Algorithm with O(ln(1/epsilon)) Convergence for epsilon-Equilibrium in Two-Person Zero-Sum Games. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
- 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., Hoda, S., Peña, J., and Sandholm, T. 2007. Gradient-based algorithms for finding Nash equilibria in extensive form games. In Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE).
- 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 the National 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
- 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).
- Benisch, M., Davis, G., and Sandholm, T. 2006. Algorithms for rationalizability and CURB sets. In Proceedings of the National Conference on Artificial Intelligence (AAAI). Extended version in EC-06 workshop on Alternative Solution Concepts.
- 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
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
o 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
o Walsh, W., Boutilier, C., Sandholm, T., Shields, R., Nemhauser, G., and Parkes, D. 2009. Automated Channel Abstraction for Advertising Auctions. In Proceedings of the Ad Auctions Workshop.
o 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).
o Benisch, M., Sadeh, N., and Sandholm, T. 2008. A Theory of Expressiveness in Mechanisms. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
o 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).
o Benisch, M., Sadeh, N., Sandholm, T. 2008. The Cost of Inexpressiveness in Advertisement Auctions. In Proceedings of the Fourth Workshop on Ad Auctions.
o 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).
o 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.
o 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.
o 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.
o 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.
o 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.
o Conitzer,
V. and Sandholm, T. 2005. Expressive Negotiation in Settings with
Externalities. In Proceedings of
the National Conference on Artificial
Intelligence (AAAI),
o Conitzer, V. and Sandholm, T. 2004. Expressive Negotiation over Donations to Charities. In Proceedings of the ACM Conference on Electronic Commerce (ACM-EC).
o 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.)
o 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
o Gilpin, A. and Sandholm, T. 2007. Information-Theoretic Approaches to Branching in Search. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
o 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,
o Sandholm, T. 2006. Optimal Winner Determination Algorithms. Chapter 14 of the book Combinatorial Auctions, Cramton, Shoham, and Steinberg, eds., MIT Press.
o 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.
o Conitzer, V., Derryberry, J., and Sandholm, T. 2004. Combinatorial Auctions with Structured Item Graphs. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
o 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.
o 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.
o 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.)
o 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.
o Sandholm, T. 2002. Algorithm for Optimal Winner Determination in Combinatorial Auctions. Artificial Intelligence, 135, 1-54. World’s 24th 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 35th most cited 1999 paper in computer science).
Market anomalies
o 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.)
o Gilpin, A. and Sandholm, T. 2004. Arbitrage in combinatorial exchanges. Agent-Mediated Electronic Commerce (AMEC) workshop.
Multi-unit markets
o Sandholm,
T. and Suri, S. 2002. Optimal Clearing of Supply/Demand Curves. In
Proceedings of the 13th Annual International Symposium on
Algorithms and Computation (ISAAC),
o Sandholm, T. and Suri, S. 2001. Market Clearability. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
Matching markets, barter exchanges, kidney
exchange
o 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).
o 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.
o 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).
Online algorithms for exchanges
o
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
o 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
o Conen, W. and Sandholm, T. 2001. Preference Elicitation in Combinatorial Auctions: Extended Abstract. In Proceedings of the ACM Conference on Electronic Commerce (ACM-EC).
o 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
o 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 (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.
o Conen, W. and Sandholm, T. 2002. Partial-Revelation VCG Mechanism for Combinatorial Auctions. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
o Conen, W. and Sandholm, T. 2002. Differential-Revelation VCG Mechanisms for Combinatorial Auctions. In Proceedings of the Agent-Mediated Electronic Commerce (AMEC) workshop.
Preferences for which elicitation can (not) be
done in a polynomial worst-case number of queries
o 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).
o 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).
o 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.)
o 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)
o 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
o
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,
Eliciting bid taker non-price preferences in
(combinatorial) auctions: Automated scenario navigation
o 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)
Valuation calculation, and normative models of
bounded rationality and information acquisition
· 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. (Early version in Proceedings of ICMAS-96.)
Other
- 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.
· 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:
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.
·
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 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. 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. 1996. Negotiation
among Self-Interested Computationally Limited Agents. Ph.D.
Dissertation.
· 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
o 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).
o 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.)
o 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).
o 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).
o 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.
o 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.
o 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.
o 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
o Sandholm, T. 2007. Perspectives on Multiagent Learning. Artificial Intelligence, 171, 382-391. Special issue on multiagent learning.
o 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.)
o 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).
o 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.
o 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).
o 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.
o
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.
· 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
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;
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.)