nach oben

Group Decision and Negotiation

Erschienen in:

01.03.2015

Learning from the Metaheuristics: Protocols for Automated Negotiations

verfasst von: Fabian Lang, Andreas Fink

Erschienen in: Group Decision and Negotiation | Ausgabe 2/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Nowadays, enterprises are more and more interconnected such that operational planning has to consider the different interests of the involved organizations. This may be a challenging and complex task as it is subject to strategic interactions and incomplete information. Automated negotiation by software agents is a powerful tool which can handle these issues and facilitate intercompany planning. Nevertheless, sophisticated negotiation protocols that govern the rules of the negotiation are needed. In this study, we present and evaluate two configurable protocols for multi-issue negotiations, which are inspired by general heuristic optimization algorithms for centralized problems, so-called metaheuristics. The protocols consist of several policy building blocks; these are evaluated with regard to their impact on the negotiation outcome. The evaluation shows that both protocols can efficiently achieve beneficial solutions—even for complex, nonlinear contract spaces—given the parameterization and the configuration of building blocks are chosen appropriately. Furthermore, we elaborate on requirements for appropriate protocol design and find that both protocols adequately comply with the requirements.

Vorheriger Artikel Leveraging ICT Capabilities in Potentially Deceptive Interactions: An Integrated Theoretical Model to Improve Detectability

Nächster Artikel A Foresight Support System Using MCDM Methods

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

There is also a multi-bilateral case with more than two agents, but only bilateral connections (one-to-many).

With the origin as disagreement point.

For instance, the other companies can adjust their advertising activity by using information deduced from rather unimportant operations management actions, i.e., the information can be linked to a more important context outside of the negotiation.

See Sect. 2.2.2 for definitions of \(c^p,c^n,\) and \(c^k\); furthermore, \(c_j^{best} = \arg \max _c U_j(c)\) (claim point) and \(c^p = \arg \min _{c^p \in \mathcal {P}} EuclideanDistance(c,c^p)\) (closest Pareto point).

Aarts E, Eikelder HT (2002) Simulated annealing. In: Pardalos P, Resende MGC (eds) Handbook of applied optimization. Oxford University Press, New York, pp 209–221

Axelrod R, Hamilton W (1981) The evolution of cooperation. Science 211(4489):1390–1396CrossRef

Baarslag T, Fujita K, Gerding E, Hindriks K, Ito T, Jennings NR, Jonker CM, Kraus S, Lin R, Robu V, Williams CR (2013) Evaluating practical negotiating agents: results and analysis of the 2011 international competition. Artif Intell 198:73–103CrossRef

Bergstrom TC, Varian HR (1985) When do market games have transferable utility? J Econ Theory 35(2):222–233CrossRef

Bichler M, Kersten G, Strecker S (2003) Towards a structured design of electronic negotiations. Group Decis Negot 12(4):311–335CrossRef

Bichler M, Gupta A, Ketter W (2010) Designing smart markets. Inf Syst Res 21(4):688–699CrossRef

Binmore K, Vulkan N (1999) Applying game theory to automated negotiation. Netnomics 1(1):1–9CrossRef

Blum C, Roli A (2003) Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput Surv 35(3):268–308CrossRef

Boutilier C, Shoham Y, Wellmanc MP (1997) Economic principles of multi-agent systems. Artif Intell 94(1–2):1–6CrossRef

Bouyssou D, Vincke P (2010) Binary relations and preference modeling. In: Bouyssou D, Dubois D, Pirlot M, Prade H (eds) Decis Mak Process Concepts Methods. Wiley-ISTE, London, pp 49–84

Cerný V (1985) Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J Optim Theory Appl 45(1):41–51CrossRef

Collins J, Gini M, Mobasher B (2002) Multi-agent negotiation using combinatorial auctions with precedence constraints. Technical Report 02–009, University of Minnesota, Minneapolis, MN, USA

Conitzer V (2010) Making decisions based on the preferences of multiple agents. Commun ACM 53(3): 84–94

Conitzer V, Sandholm T (2004) Self-interested automated mechanism design and implications for optimal combinatorial auctions. In: Breese JS, Feigenbaum J, Seltzer MI (eds) Proceedings of the 5th ACM conference on electronic commerce (ACM-EC 2004), pp 132–141

Fink A (2006) Supply chain coordination by means of automated negotiations between autonomous agents. In: Chaib-draa B, Müller J (eds) Multiagent based supply chain management (Studies in Computational Intelligence, Vol. 28). Springer, Berlin, pp 351–372CrossRef

Fogel D (2006) Evolutionary computation: toward a new philosophy of machine intelligence, 3rd edn. Wiley-IEEE Press, Piscataway

French S (1986) Decision theory: an introduction to the mathematics of rationality. Horword, Chichester

Fujita K, Ito T, Klein M (2010) Representative based multi-round protocol based on revealed private information for multi-issue negotiations. Multiagent Grid Syst 6(5–6):459–476

Fujita K, Ito T, Klein M (2010) Secure and efficient protocols for multiple interdependent issues negotiation. J Intell Fuzzy Syst 21(3):175–185

Fujita K, Ito T, Klein M (2014) Efficient issue-grouping approach for multiple interdependent issues negotiation between exaggerator agents. Decis Support Syst 60:10–17

Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley Professional, Boston

Granville V, Krivanek M, Rasson JP (1994) Simulated annealing: a proof of convergence. IEEE Trans Pattern Anal Mach Intell 16(6):652–656CrossRef

Harsanyi J (1955) Cardinal welfare, individualistic ethics, and interpersonal comparisons of utility. J Polit Econ 63(4):309–321CrossRef

Hattori H, Klein M, Ito T (2007) Using iterative narrowing to enable multi-party negotiations with multiple interdependent issues. In: Durfee EH, Yokoo M, Huhns MN, Shehory O (eds) Proceedings of the sixth international joint conference on autonomous agents and multiagent systems (AAMAS 2007)

Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor

Homberger J (2010) Decentralized multi-level uncapacitated lot-sizing by automated negotiation. 4OR 8(2):155–180CrossRef

Homberger J (2011) A generic coordination mechanism for lot-sizing in supply chains. Electron Commer Res 11(2):123–149CrossRef

Homberger J (2012) A (\(\mu,\, \lambda \))-coordination mechanism for agent-based multi-project scheduling. OR Spectr 34(1):107–132CrossRef

Hurwicz L (1945) The theory of economic behavior. Am Econ Rev 35(5):909–925

Hurwicz L (1973) The design of mechanisms for resource allocation. Am Econ Rev 63(2)

Imai H (1983) Individual monotonicity and lexicographic maxmin solution. Econometrica 51(2):389–401CrossRef

Ito T, Klein M, Hattori H (2008) A multi-issue negotiation protocol among agents with nonlinear utility functions. Multiagent Grid Syst 4(1):67–83

Jennings NR, Sycara K, Wooldridge M (1998) A roadmap of agent research and development. Auton Agents Multi-Agent Syst 1(1):7–38CrossRef

Jennings NR, Faratin P, Lomuscio AR, Parsons S, Sierra C, Wooldridge M (2001) Automated negotiation: prospects, methods and challenges. Group Decis Negot 10(2):199–215CrossRef

Kalai E (1977) Proportional solutions to bargaining situations: interpersonal utility comparisons. Econometrica 45(7):1623–1630CrossRef

Kalai E, Smorodinsky M (1975) Other solutions to Nash’s bargaining problem. Econometrica 43(3):513–518CrossRef

Kallrath J (2002) Planning and scheduling in the process industry. OR Spectr 24(3):219–250CrossRef

Kaneko M (1976) Note on transferable utility. Int J Game Theory 5(4):183–185CrossRef

Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680CrossRef

Klein M, Faratin P, Sayama H, Bar-Yam Y (2003) Negotiating complex contracts. Group Decis Negot 12(2):111–125CrossRef

Klein M, Faratin P, Sayama H, Bar-Yam Y (2007) Negotiating complex contracts. MIT Sloan School of Management Working Paper No. 4196–01, Massachusetts Institute of Technology, Cambridge, http://ssrn.com/paper=290147

Kraus S (1996) An overview of incentive contracting. Artif Intell 83(2):297–346CrossRef

Kraus S (1997) Negotiation and cooperation in multi-agent environments. Artif Intell 94(1–2):79–97CrossRef

Kraus S (2001) Automated negotiation and decision making in multiagent environments. In: Luck M, Marik V, Stepankova O, Trappl R (eds) Multi-agents Syst Appl, vol 104. Springer, New York, pp 150–172CrossRef

Kraus S, Wilkenfeld J, Zlotkin G (1995) Multiagent negotiation under time constraints. Artif Intell 75(2):297–345CrossRef

van Laarhoven P, Aarts E (1987) Simulated annealing: theory and applications. D. Reidel Publishing, DordrechtCrossRef

Lai G, Li C, Sycara K, Giampapa J (2004) Literature review on multi-attribute negotiations. Technical Report CMU-RI-TR-04-66, Carnegie Mellon University, Pittsburgh, PA, USA

Lai G, Li C, Sycara K (2006) Efficient multi-attribute negotiation with incomplete information. Group Decis Negot 15(5):511–528CrossRef

Lai G, Sycara K (2008) A generic framework for automated multi-attribute negotiation. Group Decis Negot 18(2):169–187CrossRef

Lai G, Sycara K, Li C (2008) A decentralized model for automated multi-attribute negotiations with incomplete information and general utility functions. Multiagent Grid Syst 4(1):45–65

Lang F, Fink A (2012) A quota-based multi-agent negotiation protocol for complex contracts. In: Filipe J, Fred ALN (eds) ICAART 2012—Proceedings of the 4th international conference on agents and artificial intelligence, volume 2—agents, SciTePress, pp 113–118

Lang F, Fink A (2012) Collaborative job processing on a single machine: a multi-agent weighted tardiness problem. In: van der Hoek W, Padgham L, Conitzer V, Winikoff M (eds) Proceedings of the 11th international conference on autonomous agents and multiagent aystems (AAMAS 2011), vol 3, pp 1417–1418

Lang F, Fink A (2012) Collaborative single and parallel machine scheduling by autonomous agents. In: Smari WW, Fox GC (eds) 2012 International conference on collaboration technologies and systems (CTS 2012), IEEE, pp 76–83

Lang F, Fink A (2012) Negotiating in dynamic environments: time-efficient automated negotiations by means of combinatorial auctions. Evol Syst 3(3):189–201CrossRef

Lang F, Fink A (2013) Information sharing in interorganizational systems—a story about falsehood, greed, and privacy. In: Martinovski, B (ed) Proceedings of the 13th meeting on Group Decision and Negotiation (GDN 2013), pp 319–323

Lomuscio A, Wooldridge M, Jennings NR (2003) A classification scheme for negotiation in electronic commerce. Group Decis Negot 12(1):31–56CrossRef

Metropolis N, Rosenbluth A, Rosenbluth M, Teller A, Teller E (1953) Equation of state calculations by fast computing machines. J Chem Phys 21(6):1087–1092CrossRef

Michalewicz Z (1996) Genetic algorithms + data structures = evolution programs, 3rd edn. Springer, BerlinCrossRef

Miller BL, Goldberg DE (1995) Genetic algorithms, tournament selection, and the effects of noise. Complex Syst 9(3):193–212

Nash JF (1950) The bargaining problem. Econometrica 18(2):155–162CrossRef

Neumann D (2007) Market engineering: a structured design process for electronic markets. Universitätsverlag Karlsruhe, Karlsruhe

von Neumann J, Morgenstern O (1944) Theory of games and economic behavior. Princeton University Press, Princeton

Ockenfels A, Roth A (2002) The timing of bids in internet auctions: market design, bidder behavior, and artificial agents. AI Mag 23(3):79–87

Raiffa H (1982) The art and science negotiation. Harvard University Press, Cambridge

Raiffa H, Richardson J, Metcalfe D (2002) Negotiation analysis: the science and art of collaborative decision making. Harvard University Press, Cambridge

Rief D, Dinther C (2010) Negotiation for cooperation in logistics networks: an experimental study. Group Decis Negot 19(3):211–226CrossRef

Rosenschein JS, Zlotkin G (1994) Designing conventions for automated negotiation. AI Mag 15(3):29–46

Roth A (1979) An impossibility result concerning n-person bargaining games. Int J Game Theory 8(3):129–132CrossRef

Rothkopf M, Teisberg T, Kahn E (1990) Why are Vickrey auctions rare? J Polit Econ 98(1):94–109CrossRef

Roughgarden T, Tardos É (2007) Introduction to the inefficiency of equilibria. In: Nissan N, Roughgarden T, Tardos É (eds) Algorithmic game theory. Cambridge University Press, Cambridge, pp 443–458CrossRef

Sandholm T (1999) Distributed rational decision making. In: Weiß G (ed) Multiagent systems: a modern introduction to distributed artificial intelligence. MIT Press, Cambridge, pp 201–258

Satterthwaite MA (1975) Strategy-proofness and arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions. J Econ Theory 10(2):187–217CrossRef

Shoham Y, Leyton-Brown K (2009) Multiagent systems: algorithmic, game-theoretic, and logical foundations. Cambridge University Press, Cambridge

Ströbel M, Weinhardt C (2003) The Montreal taxonomy for electronic negotiations. Group Decis Negot 12(2):143–164CrossRef

Sycara K (1998) Multiagent systems. Artif Intell 19(2):79–92

Tucker AW (1983) The mathematics of Tucker: a sampler. Two-Year Coll Math J 14(3):228–232CrossRef

Tung HW, Lin RJ (2005) Automated contract negotiation using a mediation service. In: Müller G, Lin KJ (eds) Seventh IEEE international conference on E-commerce technology (CEC 2005), IEEE, pp 374–377

Varian HR (2010) Intermediate microeconomics: a modern approach, 8th edn. W. W. Norton & Company, New York

Vetschera R (2013) Negotiation processes: an integrated perspective. EURO J Decis Process 1(1–2):135–164CrossRef

Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J Financ 16(1):8–37CrossRef

Vulkan N (1999) Economic implications of agent technology and e-commerce. Econ J 109(453):67–90CrossRef

Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3(4):257–271CrossRef

Zlotkin G, Rosenschein JS (1996) Mechanism design for automated negotiation, and its application to task oriented domains. Artif Intell 86(2):195–244CrossRef

Titel: Learning from the Metaheuristics: Protocols for Automated Negotiations
verfasst von: Fabian Lang
Andreas Fink
Publikationsdatum: 01.03.2015
Verlag: Springer Netherlands
Erschienen in: Group Decision and Negotiation / Ausgabe 2/2015
Print ISSN: 0926-2644
Elektronische ISSN: 1572-9907
DOI: https://doi.org/10.1007/s10726-014-9390-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2015

A Foresight Support System Using MCDM Methods

Consensus-Based Group Decision Making Under Multi-granular Unbalanced 2-Tuple Linguistic Preference Relations

Group Decision Making with Incomplete Interval-Valued Intuitionistic Preference Relations

The Condorcet Efficiency Advantage that Voter Indifference Gives to Approval Voting Over Some Other Voting Rules

Mind the Medium: A Qualitative Analysis of Email Negotiation

Leveraging ICT Capabilities in Potentially Deceptive Interactions: An Integrated Theoretical Model to Improve Detectability

Premium Partner