Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2016 | OriginalPaper | Chapter

4. Social Optimality in Cooperative Multiagent Systems

Authors : Jianye Hao, Ho-fung Leung

Published in: Interactions in Multiagent Systems: Fairness, Social Optimality and Individual Rationality

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this chapter, we turn to look at another important solution concept called social optimality which targets at maximizing the sum of all agents’ payoffs involved. A socially optimal outcome is desirable in that it is not only optimal from the system-level’s perspective but also Pareto optimal. To achieve socially optimal outcomes in cooperative environments, the major challenge is how each agent can coordinate effectively with others given limited information, since the behaviors of other agents coexisting in the system may significantly impede the coordination process among them. The coordination problem becomes more difficult when the environment is uncertain (or stochastic) and each agent can only interact with its local partners if we consider a topology-based interaction environment [1, 6].

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

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!

inform now
previous chapter Fairness in Cooperative Multiagent Systems
next chapter Individual Rationality in Competitive Multiagent Systems
Footnotes
1
In the current implementation, we only take each agent’s payoff during the second-half period into consideration in order to get a more accurate evaluation of the actual performance of the period.
 
2
In the current implementation, we only take each agent’s payoff during the second-half period into consideration in order to get a more accurate evaluation of the actual performance of the period.
 
3
Notice that socially optimal outcomes here correspond to Pareto-optimal Nash equilibria in the transformed game \(G^{{\prime}}\) under the social learning update scheme.
 
4
Note that these two examples are the most commonly adopted test beds in previous work [4, 5, 20, 22].
 
5
Note that the minimum unit of the agents’ utilities is 1 here, since the utility function is defined in integers.
 
6
Note that the gray nodes 3 and 15 do not belong to the negotiation tree itself and for explanation only.
 
7
Note that each agent only knows its own best possible utility over each node in the negotiation tree. Here we show both agents’ information in the same negotiation tree for illustration purpose only.
 
8
Recall that we assume that the agent’s utilities are integers only and the utility’s minimum unit is 1. Since the agents are altruistic-individually rational, and also u 1(A 0(1)) = u i (A 13(1)), agent 1 will ask for a payment of p(1) = 1 to have the incentive to propose the allocation A 13.
 
9
Note that this is based on the assumption that the agents are altruistic-individually rational. This assumption is important to prevent that the socially optimal allocation may be discarded during negotiation. For example, consider a deal (A t , A t+1) in which A t+1 is the socially rational allocation, and \(u_{1}(A_{t}(1)) = 10,u_{2}(A_{t}(2)) = 6,u_{1}(A_{t+1}(1)) = 15\), and \(u_{2}(A_{t+1}(2)) = 2\). Without this assumption, agent 1 may propose the deal (A t , A t+1) with p(1) = 3, and accordingly, agent 2 will reject this offer since its utility is decreased.
 
Literature
1.
Hoen PJ, Tuyls Kl, Panait L, Luke S, Poutre JAL (2005) An overview of cooperative and competitive multiagent learning. In: Proceedings of first international workshop on learning and adaption in multi-agent systems, Utrecht, pp 1–46
2.
Hao JY, Leung HF (2013) Reinforcement social learning of coordination in cooperative multi-agent systems(extended abstract). In: Proceedings of AAMAS’13, Saint Paul, pp 1321–1322
3.
Hao JY, Leung HF (2013) The dynamics of reinforcement social learning in cooperative multiagent systems. In: Proceedings of IJCAI 13, Beijing, pp 184–190
4.
Matlock M, Sen S (2007) Effective tag mechanisms for evolving coordination. In: Proceedings of AAMAS’07, Toronto, p 251
5.
Hao JY, Leung HF (2011) Learning to achieve social rationality using tag mechanism in repeated interactions. In: Proceedings of ICTAI’11, Washington, DC, pp 148–155
6.
Panait L, Luke S (2005) Cooperative multi-agent learning: the state of the art. Auton Agents Multi-Agent Syst 11(3):387–434CrossRef
7.
Fulda N, Ventura D (2007) Predicting and preventing coordination problems in cooperative learning systems. In: Proceedings of IJCAI’07, Hyderabad
8.
Matignon L, Laurent GJ, Le For-Piat N (2012) Independent reinforcement learners in cooperative Markov games: a survey regarding coordination problems. Knowl Eng Rev 27:1–31CrossRef
9.
Claus C, Boutilier C (1998) The dynamics of reinforcement learning in cooperative multiagent systems. In: Proceedings of AAAI’98, Madison, pp 746–752
10.
Lauer M, Rienmiller M (2000) An algorithm for distributed reinforcement learning in cooperative multi-agent systems. In: Proceedings of ICML’00, Stanford, pp 535–542
11.
Kapetanakis S, Kudenko D (2002) Reinforcement learning of coordination in cooperative multiagent systems. In: Proceedings of AAAI’02, Edmonton, pp 326–331
12.
Matignon L, Laurent GJ, Le For-Piat N (2008) A study of FMQ heuristic in cooperative multi-agent games. In: AAMAS’08 workshop: MSDM, Estoril, pp 77–91
13.
Panait L, Sullivan K, Luke S (2006) Lenient learners in cooperative multiagent systems. In: Proceedings of AAMAS’06, Utrecht, pp 801–803
14.
Wang X, Sandholm T (2002) Reinforcement learning to play an optimal nash equilibrium in team Markov games. In: Proceedings of NIPS’02, Vancouver, pp 1571–1578
15.
16.
Watkins CJCH, Dayan PD (1992) Q-learning. Mach Learn 8:279–292MATH
17.
Melo FS, Veloso M (2009) Learning of coordination: exploiting sparse interactions in multiagent systems. In: Proceedings of AAMAS’09, Budapest, pp 7730–780
18.
Sen S, Airiau S (2007) Emergence of norms through social learning. In: Proceedings of IJCAI’07, Hyderabad, pp 1507–1512
19.
Fudenberg D, Levine DK (1998) The theory of learning in games. MIT, CambridgeMATH
20.
Hales D, Edmonds B (2003) Evolving social rationality for mas using “tags”. In: Proceedings of AAMAS’03. ACM, New York, pp 497–503
21.
Sen S, Arora N, Roychowdhury S (1998) Using limited information to enhance group stability. Int J Hum-Comput Stud 48:69–82CrossRef
22.
Matlock M, Sen S (2009) Effective tag mechanisms for evolving coperation. In: Proceedings of AAMAS’09, Budapest, pp 489–496
23.
Hogg LM, Jennings NR (1997) Socially rational agents. In: Proceedings of AAAI fall symposium on socially intelligent agents, Providence, pp 61–63
24.
Hogg LMJ, Jennings NR (2001) Socially intelligent reasoning for autonomous agents. IEEE Trans SMC Part A Syst Hum 31:381–393CrossRef
25.
Chao I, Ardaiz O, Sanguesa R (2008) Tag mechanisms evaluated for coordination in open multi-agent systems. In: Proceedings of 8th international workshop on engineering societies in the agents world, Athens, pp 254–269
26.
Chevaleyre Y, Dunne PE et al (2006) Issues in multiagent resource allocation. Informatica 30:3–31MATH
27.
Chevaleyre Y, Endriss U, Maudet N (2006) Tractable negotiation in tree-structured domains. In: Proceedings of AAMAS’06, Hakodate, pp 362–369
28.
Endriss U, Maudet N (2005) On the communication complexity of multilateral trading: extended report. Auton Agents Multi-Agent Syst 11:91–107
29.
Saha S, Sen S (2007) An efficient protocol for negotiation over multiple indivisible resources. In: Proceedings of IJCAI’07, Hyderabad, pp 1494–1499
30.
Maly K, Overstreet C, Qiu X, Tang D (1988) Dynamic bandwidth allocation in a network. In: Proceedings of the ACM symposium on communications architectures and protocols, StanfordCrossRef
31.
Gomoluch J, Schroeder M (2003) Market-based resource allocation for grid computing: a model and simulation. In: Proceedings of MGC’03, Rio de Janeiro, pp 211–218
32.
Endriss U, Maudet N, Sadri F, Toni F (2003) On optimal outcomes of negotiation over resources. In: Proceedings of AAMAS’03, Melbourne
33.
Chevaleyre Y, Endriss U, Maudet N (2010) Simple negotiation schemes for agents with simple preferences: sufficiency, necessity and maximality. Auton Agents Multi-Agent Syst 20(2):234–259CrossRef
34.
Rosenschein JS, Zlotkin G (1994) Rules of encounter. MIT, CambridgeMATH
35.
Brams SJ, Taylor AD (2000) The win-win solution: guaranteeing fair shares to everybody. W.W.Norton and Company, New York
36.
Endriss U, Maudet N (2003) Welfare engineering in multiagent systems. In: Engineering societies in the agents world IV. Springer, Berlin, pp 93–106
37.
Arrow KJ, Sen AK, Suzumura K (2002) Handbook of social choice and welfare. North-Holland, AmsterdamMATH
38.
Brams SJ, Taylor AD (1996) Fair division: from cake-cutting to dispute resolution. Cambridge University Press, CambridgeCrossRefMATH
39.
Metadata
Title
Social Optimality in Cooperative Multiagent Systems
Authors
Jianye Hao
Ho-fung Leung
Copyright Year
2016
Publisher
Springer Berlin Heidelberg
Book
Interactions in Multiagent Systems: Fairness, Social Optimality and Individual Rationality

Print ISBN: 978-3-662-49468-4

Electronic ISBN: 978-3-662-49470-7

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-662-49470-7_4

Premium Partner

    Image Credits