Abstract
In negotiations among autonomous agents over resource allocation, beliefs about opponents, and about opponents’ beliefs, become particularly important when there is incomplete information. This paper considers interactions among self‐motivated, rational, and autonomous agents, each with its own utility function, and each seeking to maximize its expected utility. The paper expands upon previous work and focuses on incomplete information and multiple encounters among the agents. It presents a strategic model that takes into consideration the passage of time during the negotiation and also includes belief systems. The paper provides strategies for a wide range of situations. The framework satisfies the following criteria: symmetrical distribution, simplicity, instantaneously, efficiency and stability.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
R.J. Aumann, Subjectivity and correlation in randomized strategies, Journal of Mathematical Economics 1(1) (1974) 67–96.
L.M. Ausubel and R.J. Deneckere, Stationary sequential equilibria in bargaining with two sided incomplete information, Discussion Paper 784, Center for Mathematical Studies in Economics and Management Science, Northwestern University (1988).
F. Bacchus, A. Grove, J. Halpern and D. Koller, From statistics to beliefs, in: Proc. of AAAI-92 (California, 1992) pp. 602–608.
A.H. Bond and L. Gasser, An analysis of problems and research in DAI, in: Readings in Distributed Artificial Intelligence, eds. A.H. Bond and L. Gasser (Morgan-Kaufmann Publishers, Inc., San Mateo, California, 1988) pp. 3–35.
E. Bond and L. Samuelson, Durable good monopolies with rational expectation and replacement sales, Rand Journal of Economics 15 (1984) 336–345.
E. Bond and L. Samuelson, The Coase conjecture need not hold for durable good monopolies with depreciation, Economics Letters 24 (1987) 93–97.
N. Carver, Z. Cvetanovic and V. Lesser, Sophisticated cooperation in FA/C distributed problem solving systems, in: Proc. of AAAI-91 (California, 1991) pp. 191–198.
K. Chatterjee and L. Samuelson, Bargaining with two-sided incomplete information: An infinite horizon model with alternating offers, Review of Economic Studies 54 (1987) 175–192.
I.K. Cho, Characterization of stationary equilibria in bargaining models with incomplete information, Unpublished paper, Department of Economics, University of Chicago (1989).
P. Cohen and H. Levesque, Teamwork, Noûs (1991) 487–512.
S.E. Conry, R.A. Meyer and V.R. Lesser, Multi-stage negotiation in distributed planning, in: Readings in Distributed Artificial Intelligence, eds. A.H. Bond and L. Gasser (Morgan-Kaufmann Publishers, Inc., San Mateo, California, 1988) pp. 367–384.
S.E. Conry, K. Kuwabara, V.R. Lesser and R.A. Meyer, Multi-stage negotiation for distributed satisfaction, IEEE Transactions on Systems, Man, and Cybernetics, Special Issue on Distributed Artificial Intelligence 21(6) (December 1991) 1462–1477.
K. Decker and V. Lesser, A one-shot dynamic coordination algorithm for distributed sensor networks, in: Proc. of AAAI-93 (1993) pp. 210–216.
J. Doyle, Some theories of reasoned assumptions: an essay in rational psychology, Technical Report 83-125, Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA (1983).
J. Doyle, Rational belief revision, Technical Report, MIT, Artificial Intelligence Laboratory, Cambridge, Massachusettes (1990). Unpublished paper.
D. Dubois and H. Prade, A survey of belief revision and updating rules in various uncertainty models, International Journal of Intelligent Systems 9 (1994) 61–100.
E.H. Durfee, Coordination of Distributed Problem Solvers (Kluwer Academic Publishers, Boston, 1988).
E. Ephrati and J.S. Rosenschein, The Clarke Tax as a consensus mechanism among automated agents, in: Proc. of AAAI-91 (California, 1991) pp. 173–178.
E. Ephrati and J.S. Rosenschein, Reaching agreement through partial revelation of preferences, in: Proceedings of the Tenth European Conference on Artificial Intelligence, Vienna, Austria (August 1992) pp. 229–233.
R. Fagin, G. Kuper, J. Ullman and M. Vardi, Updating logical databases, in: Advances in Computing Research, Vol. 3 (1986) pp. 1–18.
D. Fudenberg and J. Tirole, Game Theory, Chapter 8 (MIT Press, Cambridge, MA, 1991).
P. Gardenfors, Knowledge in Flux: Modeling the Dynamics of Epistemic States (MIT Press, 1988).
J.Y. Halpern and Y. Moses, Knowledge and common knowledge in a distributed environment, Journal of the Association for Computing Machinery 37(3) (1990).
G. Harman, Change in View (MIT Press, Cambridge, MA, 1986).
W.L. Harper, Rational belief change, popper functions, and counterfactuals, in: Foundations of Probability Theory, Statistical Inference, and Statistical Theories of Science, Vol. 1, eds. W.L. Harper and C.A. Hooker (Reidel, Dordrecht, 1976) pp. 73–115.
O.D. Hart and J. Tirole, Contract renegotiation and Coasian dynamics, Review of Economic Studies (1988) pp. 509–540.
H. Katsuno and A. Mendelzon, Knowledge base revision and minimal change, Artificial Intelligence 52 (1991) 263–294.
H. Katsuno and A. Mendelzon, On the difference between updating a knowledge base and revising it, in: Proc. of KR91 (1991) pp. 387–394.
S. Kraus and D. Lehmann, Knowledge, belief and time, Theoretical Computer Science 58 (1988) 155–174.
S. Kraus and D. Lehmann, Designing and building a negotiating automated agent, Computational Intelligence 11(1) (1995) 132–171.
S. Kraus and J. Wilkenfeld, The function of time in cooperative negotiations, in: Proc. of AAAI-91 (California, 1991) pp. 179–184.
S. Kraus and J. Wilkenfeld, Negotiations over time in a multi-agent environment: Preliminary report, in: Proc. of IJCAI-91 (Australia, 1991) pp. 56–61.
S. Kraus and J. Wilkenfeld, A strategic negotiations model with applications to an international crisis, IEEE Transaction on Systems Man and Cybernetics 23(1) (1993) 313–323.
S. Kraus, J. Wilkenfeld and G. Zlotkin, Multi-agent negotiation under time constraints, Artificial Intelligence 75(2) (1995) 297–345.
D. Kreps and R. Wilson, Reputation and imperfect information, Journal of Economic Theory 27 (1982) 253–279.
D. Kreps and R. Wilson, Sequential equilibria, Econometrica 50 (1982) 863–894.
K. Kuwabara and V. Lesser, Extended protocol for multi-stage negotiation, in: Proc. of the Ninth Workshop on Distributed Artificiall Intelligence (1989) pp. 129–161.
B. Laasri, H. Laasri and V. Lesser, A generic model for intelligent negotiating agents, International Journal on Intelligent Cooperative Information Systems 1(2) (1992) 291–317.
G. Lemel, A strategic model for negotiation among autonomous agents, M.Sc. Thesis, Dept. of Mathematics and Computer Science, Bar-Ilan University, Ramat Gan (written largely in Hebrew) (1995).
V.R. Lesser, J. Pavlin and E.H. Durfee, Approximate processing in real time problem solving, AI Magazine 9(1) (1988) 49–61.
V.R. Lesser, A retrospective view of FA/C distributed problem solving, IEEE Transactions on Systems, Man, and Cybernetics 21(6) (1991) 1347–1362.
D. Lewis, Counterfactuals (Blackwell, Oxford, 1973).
R.D. Luce and H. Raiffa, Games and Decisions (John Wiley and Sons, 1957).
V. Madrigal, T. Tan and R. Werlang, Support restrictions and sequential equililibria, Journal of Economic Theory 43 (1987) 329–334.
T.W. Malone, R.E. Fikes, K.R. Grant and M.T. Howard, Enterprise: A market-like task schedule for distributed computing environments, in: The Ecology of Computation, ed. B.A. Huberman (North-Holland, 1988) pp. 177–205.
P. Milgrom and J. Roberts, Predation, reputation, and entry deterrence, Journal of Economic Theory 27 (1982) 280–312.
T. Moehlman, V. Lesser and B. Buteau, Decentralized negotiation: An approach to the distributed planning problem, Group Decision and Negotiation 2 (1992) 161–191.
M.J. Osborne and A. Rubinstein, Bargaining and Markets (Academic Press Inc., San Diego, California, 1990).
W.V. Quine and J.S. Ullian, The Web of Belief, 2nd edn. (Random House, New York, 1978).
A.S. Rao and N.Y. Foo, Formal theories of belief revision, in: Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning (Morgan-Kaufmann, May 1989) pp. 369–380.
E. Rasmusen, Games and Information (Basil Blackwell Ltd., Cambridge, MA, 1989).
J.S. Rosenschein, Rational interaction: cooperation among intelligent agents, PhD Thesis, Stanford University (1986).
J.S. Rosenschein and G. Zlotkin, Rules of Encounter: Designing Conventions for Automated Negotiation Among Computers (MIT Press, Boston, 1994).
A. Rubinstein, Perfect equilibrium in a bargaining model, Econometrica 50(1) (1982) 97–109.
A. Rubinstein, A bargaining model with incomplete information about preferences, Econometrica 53(5) (1985) 1151–1172.
T. Sandholm, An implementation of the contract net protocol based on marginal cost calculations, in: Proc. of AAAI-93 (1993) pp. 256–262.
L.J. Savage, The Foundations of Statistics, 2nd edn. (Dover Publications, New York, 1972).
R.G. Smith and R. Davis, Negotiation as a metaphor for distributed problem solving, Artificial Intelligence 20 (1983) 63–109.
W. Spivey and R. Thrall, Linear Optimization (Holt, Rinehart and Winston, 1970).
R.C. Stalnaker, Inquiry (MIT Press, Cambridge, MA, 1984).
K.P. Sycara, Persuasive argumentation in negotiation, Theory and Decision 28 (1990) 203–242.
K.P. Sycara, Resolving adversarial conflicts: an approach to integrating case-based and analytic methods, PhD Thesis, School of Information and Computer Science, Georgia Institute of Technology (1987).
M. Wellman, A general-equilibrium approach to distributed transportation planning, in: Proc. of AAAI-92 (San Jose, California, 1992) pp. 282–289.
M. Winslett, Is belief revision harder than you thought?, in: Proceedings of AAAI-86 (Philadelphia, 1986) pp. 421–427.
G. Zlotkin and J.S. Rosenschein, Cooperation and conflict resolution via negotiation among autonomous agents in noncooperative domains, IEEE Transactions on Systems, Man, and Cybernetics, Special Issue on Distributed Artificial Intelligence 21(6) (December 1991) 1317–1324.
G. Zlotkin and J.S. Rosenschein, Incomplete information and deception in multi-agent negotiation, in: Proc. IJCAI-91 (Australia, 1991) pp. 225–231.
G. Zlotkin and J.S. Rosenschein, A domain theory for task oriented negotiation, in: Proceedings of IJCAI-93 (Chambery, France, August 1993) pp. 416–422.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kraus, S. Beliefs, time and incomplete information in multiple encounter negotiations among autonomous agents. Annals of Mathematics and Artificial Intelligence 20, 111–159 (1997). https://doi.org/10.1023/A:1018928310720
Issue Date:
DOI: https://doi.org/10.1023/A:1018928310720