Bargaining with limited computation: Deliberation equilibrium

We develop a normative theory of interaction-negotiation in particular-amon g self-interested computationally limited agents where computational action s are game theoretically treated as part of an agent's strategy. We focus o n a 2-agent setting where each agent has an intractable individual problem, and there is a potential gain from pooling the problems, giving rise to an intractable joint problem. At any time, an agent can compute to improve it s solution to its own problem, its opponent's problem, or the joint problem . At a deadline the agents then decide whether to implement the joint solut ion, and if so, how to divide its value (or cost). We present a fully norma tive model for controlling anytime algorithms where each agent has statisti cal performance profiles which are optimally conditioned on the problem ins tance as well as on the path of results of the algorithm run so far. Using this model, we introduce a solution concept, which we call deliberation equ ilibrium. It is the perfect Bayesian equilibrium of the game where delibera tion actions are part of each agent's strategy. The equilibria differ based on whether the performance profiles are deterministic or stochastic, wheth er the deadline is known or not, and whether the proposer is known in advan ce or not. We present algorithms for finding the equilibria. Finally, we sh ow that there exist instances of the deliberation-bargaining problem where no pure strategy equilibria exist and also instances where the unique equil ibrium outcome is not Pareto efficient. (C) 2001 Elsevier Science B.V. All rights reserved.