Abstract
This paper presents some of the key techniques for reaching agreements in multi-agent environments. It discusses game-theory and economics based techniques: strategic negotiation, auctions, coalition formation, market-oriented programming and contracting. It also presents logical based mechanisms for argumentations. The focus of the survey is on negotiation of self-interested agents, but several mechanisms for cooperative agents who need to resolve conflicts that arise from conflicting beliefs about different aspects of their environment are also mentioned. For space reasons, we couldn#x2019;t cover all the relevant works, and the papers that are mentioned only demonstrate the possible approaches. We present some of the properties of the approaches using our own previous work.
This work is supported in part by NSF under grant No.IIS-9820657.This paper isbased on hapters in S.Kraus.Strategic Negotiation in Multi-Agent Environments,MIT Press,Cambridge,USA,2001 and on S.Kraus,K.Sy ara and A.Even hik.Reaching agreements through argumentation:a logical model and implementation,Artificial Intelligence Journal 104(1-2):1-69,1998.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M.R. Andersson and T.W. Sandholm. Contract Types for Optimal Task Allocation: II Experimental Results. In AAAI 1998 Spring Symposium: Satisficing Models, Stanford University, California, 1998.
K.J. Arrow.The economics of agency. In J. Pratt and R. Zeckhauser, editors, Principals and Agents: The Structure of Business, pages 37–51. Harvard Business School Press, Cambridge, MA, 1985.
R. Azoulay-Schwartz and S. Kraus. Negotiation on data allocation in multi-agent environments. Autonomous Agents and Multi-Agent Systems journal, 2001. To appear.
S. Baiman and J. Demski. Economically optimal performance evaluation and control systems. Journal of Accounting Research, 18:184–220, 1980.
A. Banerjee and A. Beggs. Efficiency in hierarchies: implementing the first-best solution by sequential actions. The Rand Journal of Economics, 20(4):637–645, 1989.
M. Ben-Or and N. Linial. Collective coin flipping, robust voting games and minima of banzhaf values. In Proc. 26th IEEE Symposium on the Foundations of Computer Science, pages 408–416, Portland, 1985.
F.J. Boster and P. Mongeau. Fear-arousing persuasive messages. In R.N. Bostrom, editor, Communication yearbook 8. SAGE Publications, 1984.
M.E. Bratman. Shared cooperative activity. The Philosophical Review, 101:327–341, 1992.
B. Caillaud, R. Guesnerie, P. Rey, and J. Tirole. Government intervention in production and incentives theory: a review of recent contributions. Rand Journal of Economics, 19(1):1–26, 1988.
S.E. Conry, K. Kuwabara, V.R. Lesser, and R.A. Meyer. Multistage negotiation for distributed satisfaction. IEEE Transactions on Systems, Man, and Cybernetics, Special Issue on Distributed Artificial Intelligence, 21(6):1462–1477, December 1991.
D. Druckman. Negotiations. Sage Publications, London, 1977.
eBay. eBay-Your Personal Trading Community. http://www.ebay.com/aw/ 2001.
R. Fisher and W. Ury. Getting To Yes: Negotiating Agreement Without Giving In. Houghton Miffin, Boston, 1981.
E. Freitsis. Negotiations in the pollution sharing problem. Master’s thesis, BarIlan University, 2000.
Y. Fujishima, K. Leyton-Brown, and Y. Shoham. Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches. In Dean Thomas, editor, Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI-99-Vol1), pages 548–553, S.F., July 31-August 6 1999. Morgan Kaufmann Publishers.
C. Gerber, C. Russ, and G. Vierke. On the suitability of market-based mechanisms for telematics applications. In Proc. of Agents99, pages 408–409, 1999.
E. Gimenez-Funes, L. Godo, and J. A. Rodriguez-Aguilar. Designing bidding strategies for trading agents in electronic commerce. In ICMAS98, pages 136–143, Paris, 1998.
S. Grossman and O. Hart. An analysis of the principal-agent problem. Econometrica, 51(1):7–45, 1983.
B.J. Grosz and S. Kraus. Collaborative plans for complex group activities. Artificial Intelligence Journal, 86(2):269–357, 1996.
B.J. Grosz and S. Kraus. The evolution of sharedplans. In A. Rao and M. Wooldridge, editors, Foundations and Theories of Rational Agency, pages 227–262. Kluwer Academic Publishers, 1999.
R.H. Guttman and P. Maes. Cooperative vs. competitive multi-agent negotiations in retail electronic commerce. In The Second International Workshop on Cooperative Information agents (CIA98), pages 135–147, Paris, 1998.
Lavinia Hall, editor. Negotiation: Strategies for Mutual Gain. Sage, Beverly Hills, 1993.
R. Hamill, T.D. Wilson, and R.E. Nisbett. Insensitivity to sample bias: Generalizing from atypical cases. Journal of Personality and Social Psychology, 39:579–589, 1980.
M. Harris and A. Raviv. Some results on incentive contracts with applications to education and employment, health insurance, and law enforcement. The American Economic Review, 68(1):20–30, 1978.
J. Hirshleifer and J. Riley. The Analytics of Uncertainty and Information. Cambridge University Press, Cambridge, 1992.
B. Huberman and S.H. Clearwater.A multi-agent system for controlling building environments. In Proceedings of ICMAS-95, pages 171–176, San Fransisco, 1995.
L. Hunsberger and B. Grosz.A combinatorial auction for collaborative planning. In ICMAS-2000, Boston, USA, 2000.
N.R. Jennings, P. Faratin, A.R. Lomuscio, S. Parsons, C. Sierra, and M. Wooldridge. Automated haggling: Building artificial negotiators. In Pacific Rim International Conference on Artificial Intelligence, page 1, 2000.
R. Johnson. Negotiation basics. Sage, Newbury Park, 1993.
J.P. Kahan and A. Rapoport. Theories of coalition formation. Lawrence Erlbaum Associates, Hillsdale, New Jersey, 1984.
M. Karlins and H.I. Abelson. Persuasion: How opinions and attitudes are changed. Springer Publishing Company, Inc., second edition, 1970.
C.L Karrass. The Negotiating Game: How to Get What You Want. Thomas Crowell Company, NY, 1970.
S.P. Ketchpel. Forming coalitions in the face of uncertain rewards. In Proc. of AAAI94, pages 414–419, Seattle, Washington, 1994.
P. Klemperer. Auction theory: A guide to literature. Journal of Economic Surveys, 13(3), 1999.
M. Klusch and O. Shehory. A polynomial kernel-oriented coalition formation algorithm for rational information agents. In Proc. of ICMAS-96, pages 157–164, Kyoto, Japan, 1996.
R.R. Jr. Koballa. Persuading teachers to reexamine the innovative elementary science programs of yesterday: The effect of anecdotal versus data-summary communications. Journal of Research in Science Teaching, 23:437–449, 1986.
S. Kraus. An overview of incentive contracting. Artificial Intelligence Journal, 83(2):297–346, 1996.
S. Kraus. Strategic Negotiation in Multiagent Environments. MIT Press, Cambridge, USA, 2001.
S. Kraus and D. Lehmann. Designing and building a negotiating automated agent. Computational Intelligence, 11(1):132–171, 1995.
S. Kraus, K. Sycara, and A. Evenchik. Reaching agreements through argumentation: a logical model and implementation. Artificial Intelligence, 104(1–2):1–69, 1998.
S. Kraus and J. Wilkenfeld. A strategic negotiations model with applications to an international crisis. IEEE Transaction on Systems Man and Cybernetics, 23(1):313–323, 1993.
D. Kreps and R. Wilson. Sequential equilibria. Econometrica, 50:863–894, 1982.
J. Laffont and J. Tirole. A Theory Of Incentives in Procurement and Regulation. The MIT Press, Cambridge, Massachusetts, 1993.
Susan E. Lander and Victor R. Lesser. Customizing distributed search among agents with heterogeneous knowledge. In Proc. first int. conf. on Information Knowledge Management, pages 335–344, Baltimore, 1992.
M. Landsberger and I. Meilijson.Monopoly insurance under adverse selection when agents differ in risk aversion. Journal of Economic Theory, 63:392–407, 1994.
Daniel Lehmann, Liadan Ita O’Callaghan, and Yoav Shoham. Truth revelation in rapid, approximately efficient combinatorial auctions. In Proceedings of the ACM Conference on Electronic Commerce (EC#x2019;99), pages 96–102, N.Y., November 3-5 1999. ACM Press.
R.D. Luce and H. Raiffa. Games and Decisions. John Wiley and Sons, New York, 1957.
I. Macho-Stadler and J. Péastrillo. Moral hazard and cooperation. Economics Letters, 35:17–20, 1991.
T.W. Malone, R.E. Fikes, K.R. Grant, and M.T. Howard. Enterprise:Amarketlike task schedule for distributed computing environments. In B.A. Huberman, editor, The Ecology of Computation, pages 177–205. North Holland, 1988.
S. Matthews. Selling to risk averse buyers with unobservable tastes. Journal of Economy Theory, 30:370–400, 1983.
R.P. McAfee and J. McMillan. Bidding for contracts: a principal-agent analysis The Rand Journal of Economics, 17(3):326–338, 1986.
T. Moehlman, V. Lesser, and B. Buteau. Decentralized negotiation: An approach to the distributed planning problem. Group Decision and Negotiation, 2:161–191, 1992.
D. Monderer and M. Tennenholtz. Optimal auctions revisited. Artificial Intelligence Journal, 120:29–42, 2000.
R. Myerson. Mechanism design by an informed principal. Econometrica, 51:1767–1798, 1983.
B. Nalebu. and J. Stiglitz. Information, competition, and markets. American Economic Review, 73(2):278–283, 1983.
NASA. EOSDIS Home Page. http://www-v0ims.gsfc.nasa.gov/v0ims/index.html. 1996.
J.F. Nash. Two-person cooperative games. Econometrica, 21:128–140, 1953.
Noam Nisan. Bidding and allocation in combinatorial auctions. In ACM Conference on Electronic Commerce, pages 1–12, 2000.
R.E. Nisbett, E. Borgida, R. Crandall, and H. Reed. Popular induction: information is not necessarily informative. In J.S. Carroll and J.W. Payne, editors, Cognition and social behavior. Lawrence Erlbaum, 1976.
T. Ohko, K. Hiraki, and Y. Anzai. Reducing communication load on contract net by case-based reasoning:extension with directed contract and forgetting. In Proceedings of the First International Conference on Multi-Agent Systems, Cambridge, MA, 1995. MIT Press.
Daniel J. O’Keefe. Persuasion: Theory and Research. SAGE Publications, 1990.
M.J. Osborne and A. Rubinstein. Bargaining and Markets. Academic Press Inc., San Diego, California, 1990.
M.J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, Cambridge, Massachusetts, 1994.
S. Parsons, C. Sierra, and N.R. Jennings. Agents that reason and negotiate by arguing. Journal of Logic and Computation, 8(3):261–292, 1998.
H. van Dyke Parunak. Manufacturing experience with the contract net. In Proceedings of the 1995 Distributed Artificial Intelligence Workshop, pages 67–91, December 1995.
D.G. Pruitt. Negotiation Behavior. Academic Press, New York, N.Y., 1981.
Z. Qiu and M. Tambe. Flexible negotiations in teamwork: Extended abstract. In Proceedings of the AAAI Fall Symposium on Distributed Continual Planning, 1998.
H. Raiffa. The Art and Science of Negotiation. Harvard University Press, Cambridge, MA, 1982.
A. Rapoport. N-Person Game Theory. University of Michigan, Michigan, 1970.
E. Rasmusen. Games and Information. Basil Blackwell Ltd., Cambridge, MA, 1989.
Amir Ronen. Algorithms for rational agents. In Conference on Current Trends in Theory and Practice of Informatics, pages 56–70, 2000.
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.
S. Ross. The economic theory of agency: The principal’s problem. The American Economic Review, 63(2):134–139, 1973.
A.E. Roth. Axiomatic Models of Bargaining. Lecture Notes in Economics and Mathematical Systems No. 170. Springer-Verlag, Berlin, 1979.
M.H. Rothkopf, A. Pekec, and R.M. Harstad. Computationally manageable combinatorial auctions. Technical Report 95-09, DIMACS, April 19 1995.
A. Rubinstein. Perfect equilibrium in a bargaining model. Econometrica, 50(1):97–109, 1982.
A. Rubinstein and M. Yaari. Repeated insurance contracts and moral hazard. Journal of Economic Theory, 30:74–97, 1983.
T. Sandholm. An implementation of the contract net protocol based on marginal cost calculations. In Proc. of AAAI-93, pages 256–262, Washington D.C., July 1993.
T. Sandholm, K. Larson, M.R. Andersson, O. Shehory, and F. Tohm. Coalition structure generation with worst case guarantees. Artificial Intelligence Journal, 111:209–238, 1999.
T. Sandholm, S. Sikka, and S. Norden. Algorithms for optimizing leveled commitment contracts. In Proc. of IJCAI99, pages 535–540, Stockholm, Sweden, 1999.
T. Sandholm and Y. Zhou. Surplus equivalence of leveled commitment contracts. In Prof. of ICMAS-2000, pages 247–254, Boston, MA, 2000. IEEE Computer Society.
T.W. Sandholm. Limitations of the vickrey auction in computational multiagent systems. In International Conference on Multiagent Systems (ICMAS-96), pages 299–306, Kyoto, Japan, 1996.
T.W. Sandholm and V.R. Lesser. Coalition formation among bounded rational agents. In Proc. of IJCAI-95, pages 662–669, Montr#x00E9;al, 1995.
T.W. Sandholm and V.R. Lesser. Issues in automated negotiation and electronic commerce: Extending the contract net framework. In First International Conference on Multiagent Systems (ICMAS-95), pages 328–335, San Fransisco, 1995.
T.W. Sandholm and V.R. Lesser. Coalition formation among bounded rational agents. Artificial Intelligence, 94(1–2):99–137, 1997. Special issue on Principles of Multi-Agent Systems.
R. Schwartz and S. Kraus. Negotiation on data allocation in multi-agent environments. In Proc. of AAAI-97, pages 29–35, Providence, Rhode Island, 1997.
R. Schwartz and S. Kraus. Bidding mechanisms for data allocation in multiagen environments. In Munindar P. Singh, Anand S. Rao, and Michael J. Wooldridge, editors, Intelligent Agents IV: Agent Theories, Architectures, and Languages, pages 61–75. Springer-Verlag, 1998.
Sandip Sen and Edmund Durfee. A contracting model for flexible distributed scheduling. Annals of Operations Research, 65:195–222, 1996.
S. Shavell. Risk sharing and incentives in the principal and agent relationship. Bell Journal of Economics, 10:55–79, 1979.
O. Shehory and S. Kraus. Methods for task allocation via agent coalition formation. Artificial Intelligentce, 15(3):218–251, 1998.
O. Shehory and S. Kraus. Feasible formation of stable coalitions among autonomous agents in non-super-additive environments. Computational Intelligence, 15(3):218–251, 1999.
K.I. Shimomura. The bargaining set and coalition formation. Technical Report 95-11, Brown University, Dept. of Economics, 1995.
C. Sierra, P. Faratin, and N. Jennings. A service-oriented negotiation model between autonomous agents. In Proc. 8th European Workshop on Modeling Autonomous Agents in a Multi-Agent World (MAAMAW-97), pages 17–35, Ronneby, Sweden, 1997.
R. Smith and R. Davis. Framework for cooperation in distributed problem solvers. IEEE Transactions on Systems, Man and Cybernetic, C-29(12):61–70, 1981.
R.G. Smith. The contract net protocol: High-level communication and control in a distributed problem soler. IEEE Transactions on Computers, 29:1104–1113, 1980.
R.G. Smith and R. Davis. Negotiation as a metaphor for distributed problem solving. Artificial Intelligence, 20:63–109, 1983.
M. Spence and R. Zeckhauser. Insurance, information and individual action. The American Economic Review, 61(1):380–391, 1971.
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.
K.P. Sycara. Persuasive argumentation in negotiation. Theory and Decision, 28:203–242, 1990.
S.E. Taylor and S.C. Thompsons. Staking the elusive vividness effect. Psychological Review, 89:155–181, 1982.
Jean Tirole. The Theory of Industrial Organization. The MIT Press, Cambridge, MA, 1988.
S. Toulmin, R. Rieke, and A. Janik. An introduction to reasoning. Macmillan Publishing Co., Inc., 1979.
M. Tsvetovatyy, M. Gini, B. Mobasher, and Z. Wieckowski. Magma: An agentbased virtual market for electronic commerce. Applied Artificial Intelligence, special issue on Intelligent Agents, 6:501–523, 1997.
M.B. Tsvetovatyy and M. Gini. Toward a virtual marketplace: Architectures and strategis. In The first International Conference on the Practical Application of Intelligent Agents and Multi Agents Technology, pages 597–614, London, 1996.
B. Vermazen. Objects of intention. Philosophical Studies, 71:223–265, 1993.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. J. of Finance, 16:8–37, March 1961.
R. Vohra. Coalitional non-cooperative approaches to cooperation. Technical Report 95-6, Brown University, Dept. of Economics, 1995.
M. Wellman. A market-oriented programming environment and its application to distributed multicommodity flow problems. Journal of Artificial Intelligence Research, 1:1–23, 1993.
M. Wellman. Market-oriented programming: Some early lessons. In S. Clearwater, editor, Market-Based Control: A Paradigm for Distributed Resource Allocation. World Scientific, Singapore, 1996.
M. Wellman and M. Wurman. TAC: Trading agent competition. http://auction2.eecs.umich.edu/game.html. 2001.
M.P. Wellman and P.R. Wurman. Market-aware agents for a multiagent world. Robotics and Autonomous Systems, 24:115–125, 1998.
J. Wilkenfeld, S. Kraus, K. Holley, and M. Harris. Genie: A decision support system for crisis negotiations. Decision Support Systems, 14:369–391, 1995.
R. Wilson. Incentive effeciency of double auctions. Econometrica, 53(5): 1101–1116, 1985.
P.R. Wurman, W.E. Walsh, and M.P. Wellman. Flexible double auctions for electronic commerce: Theory and implementation. Decision Support Systems, 24:17–27, 1998.
Dajun Zeng and Katia Sycara. Bayesian learning in negotiation. International Journal of Human-Computer Studies, 48:125–141, 1998.
L. Zhou. A new bargaining set of an n-person game and endogenous coalition formation. Games and Economic Behavior, 6:512–526, 1994.
G. Zlotkin and J.S. Rosenschein. Coalition, cryptography, and stability: Mechanisms for coalition formation in task oriented domains. In Proc. of AAAI94, pages 432–437, Seattle, Washington, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Kraus, S. (2001). Automated Negotiation and Decision Making in Multiagent Environments. In: Luck, M., Mařík, V., Štěpánková, O., Trappl, R. (eds) Multi-Agent Systems and Applications. ACAI 2001. Lecture Notes in Computer Science(), vol 2086. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47745-4_7
Download citation
DOI: https://doi.org/10.1007/3-540-47745-4_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42312-6
Online ISBN: 978-3-540-47745-7
eBook Packages: Springer Book Archive