UIUC Agents and Multi-Agents Group (AMAG)

eMediator, our electronic commerce server, demonstrates new ways in which AI, algorithmic support, and game theoretic incentive engineering can jointly improve the efficiency of ecommerce. The auction house component offers a variety of price determination mechanisms, novel bid types, and user support for choosing an auction type. It offers generalized combinatorial auctions that lead to more efficient allocations than traditional auctions because bidders can express complementarities and substitutabilities by bidding on bundles of items. Winner determination in combinatorial auctions is NP-complete, and, as we show, inapproximable. An optimal (anytime) algorithm is presented for making combinatorial auctions computationally feasible. By preprocessing and pruning the search space in several ways, it capitalizes on the fact that the space of bids is sparsely populated in practice. Our server also automatically programs mobile agents that bid optimally on the user's behalf.

In (automated) negotiation, contracts have traditionally been binding. They do not allow agents to efficiently accommodate future events. To address this, we developed a backtracking instrument for multiagent settings called a leveled commitment contract, where each party can unilaterally decommit by paying a predetermined penalty. We show that such contracts enable agreements and improve the expected payoffs of all contract parties even though each agent decommits using an inflated threshold on how good its outside offer must be before it decommits (because it would rather have another party decommit). The protocols differ based on whether agents have to declare their decommitting decisions sequentially or simultaneously, and whether or not agents have to pay the penalties if both decommit. We show that, surprisingly, each protocol leads to the same payoffs to the agents when the contract is optimized for each protocol separately. We then present eMediator's algorithms for optimizing the contract price and penalties, and the rational thresholds.

The third component of eMediator is a safe exchange planner. It avoids nondelivery by dividing the exchange into chunks - that are delivered in alternation - so that neither party is motivated to vanish before completing the exchange. Our algorithms for chunking and chunk sequencing find such a safe exchange plan if one exists.

Tuomas Sandholm is assistant professor of computer science at Washington University in St. Louis. He received the Ph.D. and M.S. degrees in computer science from the University of Massachusetts at Amherst in 1996 and 1994. He earned an M.S. (B.S. included) with distinction in Industrial Engineering and Management Science from the Helsinki University of Technology, Finland in 1991. His research interests include Internet commerce, artificial intelligence, game theory, multiagent systems, rational resource-bounded reasoning, auctions, automated negotiation and contracting, coalition formation, machine learning, constraint satisfaction, and combinatorial optimization. He has nine years of experience building multiagent systems for electronic commerce. He has also co-developed two fielded AI systems, and is co-founder and chief scientist of an electronic commerce startup company. He has published over 95 technical papers, and received several academic awards including the NSF CAREER Award.

Hosts: Les Gasser (GSLIS) and Gul Agha (CS),

Dr. Tuomas Sandholm
Assistant Professor
Director, Multiagent Systems Research Group
Washington University
Department of Computer Science
One Brookings Drive, Campus Box 1045
St. Louis, MO 63130
(314) 935-4749 (office)
(314) 935-7302 (fax)
sandholm@cs.wustl.edu
http://siesta.cs.wustl.edu/~sandholm/

This seminar is one of a series of talks hosted by the UIUC Agents and Mult-Agent Systems Group (AMAG).