Systems, especially for ecommerce, are increasingly being used by multiple parties with different preferences. Game theory helps design the interaction mechanism so that desirable system-wide outcomes follow even though every participant acts (or designs her agent to act) based on self-interest. I have shown that these prescriptions change in intricate ways once one takes into account limited computation. For example, in automated negotiation systems for self-interested agents, contracts have usually been binding. They do not allow agents to efficiently accommodate events that are uncertain due to incomplete information or limited computation in evaluating contracts and in looking ahead. 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. A rational agent will be reluctant to decommit because the other party might decommit, in which case the former agent gets freed from the contract, does not have to pay a penalty, and collects a penalty from the breacher. We proved that leveled commitment contracts enable agreements and improve the expected payoffs of all contract parties despite such strategic decommitting. The talk studies the properties of this contract family, compares different leveled commitment protocols, and presents algorithms for computing optimal decommitting strategies as well as for determining optimal contract parameters. I conclude by discussing other implications of limited computation on mechanism and agent design, by presenting the next generation ecommerce system prototypes that we have built, and by laying out a vision of future ecommerce technology.

BIO: Dr. Sandholm is faculty in the department of computer science at Washington University. 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 artificial intelligence, ecommerce, game theory, multiagent systems, auctions, automated negotiation and contracting, coalition formation, and normative models of bounded rationality. Several of his inventions have been fielded, and he has started two ecommerce companies. He has published over 100 technical papers and received several academic awards including the NSF CAREER award.