An alternating offers bargaining model for computationally limited agents

ABSTRACT

An alternating offers bargaining model for computationally limited agents is presented. The gents compute to determine plans, but deadlines restrict them from determining an optimal solution. As the agents compute, they also negotiate over whether to perform a joint plan or whether to act independently and how, if implemented, the value of the joint plan would be divided. Their computing actions and bargaining actions are interrelated and both incorporated into each agent's strategy. We analyze the model for equilibrium strategies for agents under different conditions. It is shown that the equilibrium strategies for the alternating offers model where agents take turns making offers and counter-offers, even with its extremely large action space, are equivalent to those of a much simpler single shot, take--it--or--leave--it bargaining model. In particular, agents will compute and make no offers until the first agent's deadline.

REFERENCES

• 1: Mark Boddy , Thomas L. Dean, Deliberation scheduling for problem solving in time-constrained environments, Artificial Intelligence, v.67 n.2, p.245-285, June 1994 [doi>10.1016/0004-3702(94)90054-X]
• 2: Eric A. Hansen , Shlomo Zilberstein, Monitoring and control of anytime algorithms: a dynamic programming approach, Artificial Intelligence, v.126 n.1-2, p.139-157, Feb., 2001 [doi>10.1016/S0004-3702(00)00068-0]
• 3: about beliefs and actions under computational resource constraints. In 3rd Workshop on Uncertainty in AI, pages 429--444, Seattle, 1987.
• 4: P. Jehiel. Limited horizon forecast in repeated alternate games. Journal of Economic Theory, 67:497--519, 1995.
• 5: D. Koller, N. Megiddo, and B. Stengel. Efficient computation of equilibria for extensive two-person games. Games and Economic Behavior, 14(2):247--259, 1996.
• 6: Sarit Kraus , Jonathan Wilkenfeld , Gilad Zlotkin, Multiagent negotiation under time constraints, Artificial Intelligence, v.75 n.2, p.297-345, June 1995 [doi>10.1016/0004-3702(94)00021-R]
• 7: Kate Larson , Tuomas Sandholm, Bargaining with limited computation: deliberation equilibrium, Artificial Intelligence, v.132 n.2, p.183-217, November 2001 [doi>10.1016/S0004-3702(01)00132-1]
• 8: Kate Larson , Tuomas Sandholm, Costly valuation computation in auctions, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
• 9: A. Mas-Colell, M. Whinston, and J. R. Green. Microeconomic Theory. Oxford University Press, 1995.
• 10: M. J. Osborne and A. Rubinstein. Bargaining and Markets. Academic Press, Inc., 1990.
• 11: Jeffrey S. Rosenschein , Gilad Zlotkin, Rules of encounter: designing conventions for automated negotiation among computers, MIT Press, Cambridge, MA, 1994
• 12: A. Rubinstein. Perfect equilibrium in a bargaining model. Econometrica, 50:97--109, 1982.
• 13: A. Rubinstein. Modeling Bounded Rationality. MIT Press, 1998.
• 14: Stuart J. Russell, Rationality and intelligence, Artificial Intelligence, v.94 n.1-2, p.57-77, July 1997 [doi>10.1016/S0004-3702(97)00026-X]
• 15: Stuart Russell , Eric Wefald, Do the right thing: studies in limited rationality, MIT Press, Cambridge, MA, 1991
• 16: T. Sandholm. Issues in computational Vickrey auctions. International Journal of Electronic Commerce, 4(3):107--129, 2000.
• 17: Tuomas W. Sandholm , Victor R. Lesser, Coalitions among computationally bounded agents, Artificial Intelligence, v.94 n.1-2, p.99-137, July 1997 [doi>10.1016/S0004-3702(97)00030-1]
• 18: Tuomas Sandholm , Nir Vulkan, Bargaining with deadlines, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.44-51, July 18-22, 1999, Orlando, Florida, United States
• 19: H. Simon. Models of bounded rationality, vol. 2. MIT Press, 1982.
• 20: Shlomo Zilberstein , Stuart Russell, Optimal composition of real-time systems, Artificial Intelligence, v.82 n.1-2, p.181-213, April 1996 [doi>10.1016/0004-3702(94)00074-3]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Economics, Theory