ITR: Secure Automated Negotiation under Limited Computation: Deliberation in Equilibrium

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Multiple parties are increasingly using distributed information systems, especially the Internet, for automated negotiations. Game theory provides a basis for engineering incentives into the interaction mechanisms of these systems so that desirable social outcomes follow -- even though every party acts based on self-interest. However, there is a hazardous gap in game theory when it comes to incentives and computation, leaving such systems open to manipulation. Extensions to game theory that address computation are required for settings where the participants are self-interested, and there is an underlying intractable problem that limits the agents' rationality. In this project, a theory of interaction is being developed where computational actions are treated as part of each agent's strategy. The work involves model development, game-theoretic analysis, mechanism and algorithm design, and computational experiments. This research paves the way to building secure systems that are robust against manipulation, yet computationally feasible. The theories being developed allow the construction of optimal negotiating agents in settings where computation is an issue. This enables wider and fairer access to Internet commerce by putting novices, assisted by these software agents, on an equal playing field with expert market participants. The methodology being developed also enables the design of economically and computationally more efficient interaction mechanisms.