Systems, especially for e-commerce, 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. Sandholm has 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, Sandholm has 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. Sandholm proved that leveled commitment contracts enable agreements and improve the expected payoffs of all contract parties despite such strategic decommitting.

This 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. Sandholm will conclude by discussing other implications of limited computation on mechanism and agent design, by presenting the next generation ecommerce system prototypes that he has built, and by laying out a vision of future ecommerce technology.