Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
3.9CiteScore
1.3Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2008 Volume 23
Article Contents
Next Previous
RESEARCH ARTICLE   Open Access    

Fairness in multi-agent systems

More Information
  • Abstract: Multi-agent systems are complex systems in which multiple autonomous entities, called agents, cooperate in order to achieve a common or personal goal. These entities may be computer software, robots, and also humans. In fact, many multi-agent systems are intended to operate in cooperation with or as a service for humans. Typically, multi-agent systems are designed assuming perfectly rational, self-interested agents, according to the principles of classical game theory. Recently, such strong assumptions have been relaxed in various ways. One such way is explicitly including principles derived from human behavior. For instance, research in the field of behavioral economics shows that humans are not purely self-interested. In addition, they strongly care about fairness. Therefore, multi-agent systems that fail to take fairness into account, may not be sufficiently aligned with human expectations and may not reach intended goals. In this paper, we present an overview of work in the area of fairness in multi-agent systems. More precisely, we first look at the classical agent model, that is, rational decision making. We then provide an outline of descriptive models of fairness, that is, models that explain how and why humans reach fair decisions. Then, we look at prescriptive, computational models for achieving fairness in adaptive multi-agent systems. We show that results obtained by these models are compatible with experimental and analytical results obtained in the field of behavioral economics.
  • 加载中
  • Aldewereld H.2007 Autonomy vs. conformity: an institutional perspective on norms and protocols. PhD thesis, Universiteit Utrecht.

    Google Scholar

    Aristotle. Politics, Book II, Chapter III, 1261b; translated by Benjamin Jowett as The Politics of Aristotle: Translated into English with Introduction, Marginal Analysis, Essays, Notes and Indices, volume 1 of 2. Oxford: Clarendon Press, 1885.

    Google Scholar

    Barabasi A.-L. and Albert R.1999Emergence of scaling in random networks. Science286, 509–512.

    Google Scholar

    Basu K.1994. The traveler’s dilemma: paradoxes of rationality in game theory. American Economic Review84(2), 391–395.

    Google Scholar

    Basu K.2007The traveler’s dilemma. Scientific American296(6), 68–73.

    Google Scholar

    Bowles S., Boyd R., Fehr E. and Gintis H.1997Homo reciprocans: a research initiative on the origins, dimensions, and policy implications of reciprocal fairness. Advances in Complex Systems4, 1–30.

    Google Scholar

    Bowling M. H. and Veloso M. M.2002Multiagent learning using a variable learning rate. Artificial Intelligence136, 215–250.

    Google Scholar

    Boyd R., Gintis H., Bowles S. and Richerson P.2003The evolution of altruistic punishment. Proceedings of the National Academy of Sciences of the United States of America100, 3531–3535.

    Google Scholar

    Boyd R. and Mathew S.2007A narrow road to cooperation. Science316, 1858–1859.

    Google Scholar

    Charness G. and Rabin M.2002Understanding social preferences with simple tests. Quarterly Journal of Economics117, 817–869.

    Google Scholar

    Chevaleyre Y., Dunne P. E., Endriss U., Lang J., Lema^ıtre M., Maudet N., Padget J., Phelps S., Rodriguez-Aguilar J. A. and Sousa P.2006Issues in multiagent resource allocation. Informatica30, 3–31.

    Google Scholar

    Chevaleyre Y., Endriss U., Lang J. and Maudet N.2007 A short introduction to computational social choice. In Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM-2007), vol. 4362 of LNCS, Berlin, Heidelberg, Germany: Springer-Verlag, pp. 51–69.

    Google Scholar

    Dannenberg A., Riechmann T., Sturm B. and Vogt C.2007Inequity aversion and individual behavior in public good games: an experimental investigation. SSRN eLibrary.

    Google Scholar

    Dawkins R.1976The Selfish Gene. Oxford: Oxford University Press.

    Google Scholar

    De Jong S., Tuyls K. and Sprinkhuizen-Kuyper I.2006 Robust and scalable coordination of potential-field driven agents. In Proceedings of IAWTIC/CIMCA2006, Sydney.

    Google Scholar

    De Jong S., Tuyls K. and Verbeeck K.2008a Artificial agents learning human fairness. In Accepted at the International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’08).

    Google Scholar

    De Jong S., Tuyls K., Verbeeck K. and Roos N.2008b Priority awareness: towards a computational model of human fairness for multi-agent systems. Adaptive Agents and Multi-Agent Systems III—Lecture Notes in Artificial Intelligence, 4865.

    Google Scholar

    Denning D.1982Cryptography and Data Security. Boston, USA: Addison-Wesley.

    Google Scholar

    Erev I. and Roth A. E.1998Predicting how people play games with unique, mixed strategy equilibria. American Economic Review88, 848–881.

    Google Scholar

    Falk A. and Fischbacher U.2006A theory of reciprocity. Games and Economic Behavior54, 293–315.

    Google Scholar

    Fehr E.2004Don’t lose your reputation. Nature432, 499–500.

    Google Scholar

    Fehr E. and Gaechter S.2000Fairness and retaliation: the economics of reciprocity. Journal of Economic Perspectives14, 159–181.

    Google Scholar

    Fehr E. and Gaechter S.2002Altruistic punishment in humans. Nature415, 137–140.

    Google Scholar

    Fehr E. and Schmidt K.1999A theory of fairness, competition and cooperation. Quarterly Journal of Economics114, 817–868.

    Google Scholar

    Ferber J.1999Multi-Agent Systems. An Introduction to Distributed Artificial Intelligence. Boston, USA: Addison-Wesley.

    Google Scholar

    Gintis H.2001Game Theory Evolving: A Problem-Centered Introduction to Modeling Strategic Interaction. Princeton, USA: Princeton University Press.

    Google Scholar

    Gueth W., Schmittberger R. and Schwarze B.1982An Experimental Analysis of Ultimatum Bargaining. Journal of Economic Behavior and Organization3(4), 367–388.

    Google Scholar

    Hamilton W.1964The genetical evolution of social behaviour I and II. Journal of Theoretical Biology7, 1–16, 17–52.

    Google Scholar

    Hardin G.1968The tragedy of the commons. Science162, 1243–1248.

    Google Scholar

    Hauert C., Monte S. D., Hofbauer J. and Sigmund K.2002Volunteering as red queen mechanism for cooperation in public goods games. Science296, 1129–1132.

    Google Scholar

    Hauert C., Traulsen A., Brandt H., Nowak M. and Sigmund K.2007Via freedom to coercion: the emergence of costly punishment. Science316, 1905–1907.

    Google Scholar

    Henrich J.2004Cultural group selection, coevolutionary processes and large-scale cooperation. Journal of Economic Behavior and Organization53, 3–35.

    Google Scholar

    Henrich J. and Boyd R.2001Why people punish defectors. Journal of Theoretical Biology208, 79–89.

    Google Scholar

    Henrich J., Boyd R., Bowles S., Camerer C., Fehr E. and Gintis H.2004Foundations of Human Sociality: Economic Experiments and Ethnographic Evidence from Fifteen Small-Scale Societies. Oxford: Oxford University Press.

    Google Scholar

    Henrich J., McElreath R., Barr A., Ensimger J., Barrett C., Bolyanatz A., Cardenas J. C., Gurven M., Gwako E., Henrich N.2006Costly punishment across human societies. Science312, 1767–1770.

    Google Scholar

    Jackson M.2000Mechanism Theory. Humanities and Social Sciences October, 228–277.

    Google Scholar

    Jennings N., Sycara K. and Wooldridge. M.1998A roadmap of agent research and development. Autonomous agents and Multi-Agent Systems1, 275–306.

    Google Scholar

    Kalagnanam J. and Parkes D.C.2004 Auctions, bidding and exchange design. In Simchi-Levi D., Wu S. D. and Shen M. (eds.), Handbook of Quantitative Supply Chain Analysis: Modeling in the E-Business Era, International Series in Operations Research and Management Science, ch. 5. Dordrecht, Netherlands: Kluwer Academic Publishers, pp. 1–84.

    Google Scholar

    Kalisch G., Milnor J., Nash J. and Nering E.1952 Some experimental n-person games. Technical report, The Rand Corporation U.S. Air Force.

    Google Scholar

    Keller L. and Ross K. G.1998Selfish genes: a green beard in the red fire ant. Nature394 (6693), 573–575.

    Google Scholar

    Knoch D., Pascual-Leone A., Meyer K., Treyer V. and Fehr E.2006Diminishing reciprocal fairness by disrupting the right prefrontal cortex. Science314, 829–832.

    Google Scholar

    Leimar O. and Hammerstein P.2001Evolution of Cooperation through Indirect Reciprocity. Proceedings: Biological Sciences268(1468), 745–753.

    Google Scholar

    Lotem A., Fishman M. and Stone L.1999Evolution of Cooperation between individuals. Nature400, 226–227.

    Google Scholar

    Mao X., ter Mors A., Roos N. and Witteveen C. Agent-based scheduling for aircraft deicing. In Schobbens P.-Y., Vanhoof W. and Schwanen G. (eds.) Proceedings of the 18th Belgium–Netherlands Conference on Artificial Intelligence, BNVKI, October 2006. pp. 229–236.

    Google Scholar

    Maynard-Smith J.1982Evolution and the Theory of Games. Cambridge University Press.

    Google Scholar

    Milinski M., Semmann D. and Krambeck H.2002Reputation helps solve the tragedy of the commons. Nature415, 424–426.

    Google Scholar

    Narendra K. and Thathachar M.1989Learning Automata: An introduction. Boston, USA: Prentice-Hall International.

    Google Scholar

    Nash J.1950a Equilibrium points in N-person games. Proceedings of the National Academy of Sciences of the United States of America36, 48–49.

    Google Scholar

    Nash J.1950b The bargaining problem. Econometrica18, 155–162.

    Google Scholar

    North D.1990Institutions, Institutional Change and Economic Performance. 1st edn., Cambridge: Cambridge University Press.

    Google Scholar

    Nowak M., Page K. and Sigmund K.2000Fairness versus reason in the Ultimatum Game. Science289, 1773–1775.

    Google Scholar

    Nowak M., Sasaki A., Taylor C. and Fudenberg D.2004Emergence of cooperation and evolutionary stability in finite populations. Nature428, 646–650.

    Google Scholar

    Nowak M. A. and Sigmund K.1998Evolution of indirect reciprocity by image scoring. Nature393(6685), 573–577.

    Google Scholar

    Nowak M. A. and Sigmund K.2005Evolution of indirect reciprocity. Nature437(7063),1291–1298.

    Google Scholar

    Nydegger R. and Owen H.1974Two-person bargaining, an experimental test of the Nash axioms. International Journal of Game Theory3, 239–250.

    Google Scholar

    Oosterbeek H., Sloof R. and van de Kuilen G.2004Cultural differences in ultimatum game experiments: evidence from a meta-analysis. Experimental Economics7, 171–188.

    Google Scholar

    Osborne J. and Rubinstein A.1994A Course in Game Theory. Boston, USA: MIT Press.

    Google Scholar

    Panchanathan K. and Boyd R.2004Indirect reciprocity can stabilize cooperation without the second-order free rider problem. Nature432, 499–502.

    Google Scholar

    Parkes D. C.2008 Computational Mechanism Design. In Lecture notes of Tutorials at 10th Conference. on Theoretical Aspects of Rationality and Knowledge (TARK-05). Institute of Mathematical Sciences, University of Singapore.

    Google Scholar

    Preist C. and van Tol M.1998 Adaptive agents in a persistent shout double auction. In ICE ’98: Proceedings of the First International Conference on Information and Computation Economies, New York: ACM Press, pp. 11–18.

    Google Scholar

    Rabin M.1993Incorporating Fairness into Game Theory and Economics. American Economic Review83, 1281–1302.

    Google Scholar

    Rodriguez-Aguilar J. A.2003 On the design and construction of agent-mediated electronic institutions. PhD thesis, Monografies de l’Institut d’Investigaci´o en Intellig`encia Artificial.

    Google Scholar

    Roth A. and Malouf M.1979Game theoretic models and the role of information in bargaining. Psychological Review86, 574–594.

    Google Scholar

    Sanfey A. G., Rilling J. K., Aronson J. A., Nystrom L. E. and Cohen J. D.2003The neural basis of economic decision-making in the ultimatum game. Science300, 1755–1758.

    Google Scholar

    Santos F. and Pacheco J.2005Scale-free networks provide a unifying framework for the emergence of cooperation. Physical Review Letters95, 98–104.

    Google Scholar

    Santos F., Pacheco J. and Lenaerts T.2006a Emergence of cooperation in heterogeneous structured populations. Proceedings of the 10th International Conference on the Simulation and Synthesis of Living Systems (Alife X). 432–437.

    Google Scholar

    Santos F., Pacheco J. and Lenaerts T.2006b Evolutionary dynamics of social dilemmas in structured heterogeneous populations. Proceedings of the National Academy of Sciences of the United States of America103, 3490–3494.

    Google Scholar

    Santos F., Pacheco J. and Lenaerts T.2006c Cooperation prevails when individuals adjust their social ties. PLoS Computational Biology2(10),1284–1291.

    Google Scholar

    Scott W.2001Institutions and Organizations, 2 edn. Thousand Oaks, USA: Sage.

    Google Scholar

    Sen S. and Airiau S.2007 Emergence of norms through social learning. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence pp. 1507–1512.

    Google Scholar

    Shoham Y., Powers R. and Grenager T.2007If multi-agent learning is the answer, what is the question?. Artificial Intelligence171(7),365–377.

    Google Scholar

    Sigmund K., Hauert C. and Nowak M.2001Reward and punishment. Proceedings of the National Academy of Sciences of the United States of America98(19), 10757–10762.

    Google Scholar

    Simon H.1957Models of Man. London, UK: John Wiley.

    Google Scholar

    Simon H.1972Theories of Bounded Rationality. Decision and Organization1, 161–176.

    Google Scholar

    Simon H. and Newell A.1972Human Problem Solving. Englewood Cliffs, USA: Prentice Hall.

    Google Scholar

    Sugden R.1986The Economics of Rights, Co-operation and Welfare. Oxford: Basil Blackwell.

    Google Scholar

    Thathachar M. and Sastry P.2004Networks of Learning Automata: Techniques for Online Stochastic Optimization. Dordrecht, Netherlands: Kluwer Academic Publishers.

    Google Scholar

    Tuyls K. and Nowe A.2005Evolutionary game theory and multi-agent reinforcement learning. The Knowledge Engineering Review20(01), 63–90.

    Google Scholar

    Van Huyck J., Battalio R., Mathur S. and Ortmann A.1995On the origin of convention: evidence from symmetric bargaining games. International Journal of Game Theory34, 187–212.

    Google Scholar

    Vaughn K. L.1987The New Palgrave: A Dictionary of Economics, vol. 2. ch. Invisible Hand. London, UK: Macmillan.

    Google Scholar

    Vazquez-Salceda J., Aldewereld H. and Dignum F.2005Norms in multiagent systems: from theory to practice. Computer Systems Science and Engineering20(4),225–236.

    Google Scholar

    Verbeeck K., Now´e A., Parent J. and Tuyls K.2007Exploring selfish reinforcement learning in repeated games with stochastic rewards. Journal of Autonomous Agents and Multi-Agent Systems14, 239–269.

    Google Scholar

    von Neumann J. and Morgenstern O.1944Theory of Games and Economic Behaviour. Princeton, USA: Princeton University Press.

    Google Scholar

    Wedekind C. and Milinski M.Cooperation through image scoring in humans. Science288(5467), 850–852.

    Google Scholar

    Weiss G.1999Multiagent Systems. A Modern Approach to Distributed Artificial Intelligence. Boston, USA: MIT Press.

    Google Scholar

    Weyns D., Boucke N., Holvoet T. and Schols W.2005Gradient field-based task assignment in an AGV transportation system. In Proceedings of EUMASpp. 447–458.

    Google Scholar

    Yaari M. and Bar-Hillel M.1981On dividing justly. Social Choice and Welfare1, 1–24.

    Google Scholar

    Yamagishi T.1986The provision of a sanctioning system as a public good. Journal of Personality and Social Psychology51(1),110–116.

    Google Scholar

    Zollman K. J.2008Explaining fairness in complex environments. Politics, Philosophy, and Economics7(1),81–97.

    Google Scholar

  • Cite this article

    STEVEN DE JONG, KARL TUYLS, KATJA VERBEECK. 2008. Fairness in multi-agent systems. The Knowledge Engineering Review. 23: doi: 10.1017/S026988890800132X
    STEVEN DE JONG, KARL TUYLS, KATJA VERBEECK. 2008. Fairness in multi-agent systems. The Knowledge Engineering Review. 23: doi: 10.1017/S026988890800132X
    shu
Download PDF

Article Metrics

Article views(27) PDF downloads(193)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Fairness in multi-agent systems

  • Published online: 01 June 2008
The Knowledge Engineering Review  23,  Article number: 10.1017/S026988890800132X  (2008)  |  Cite this article

Abstract: Abstract: Multi-agent systems are complex systems in which multiple autonomous entities, called agents, cooperate in order to achieve a common or personal goal. These entities may be computer software, robots, and also humans. In fact, many multi-agent systems are intended to operate in cooperation with or as a service for humans. Typically, multi-agent systems are designed assuming perfectly rational, self-interested agents, according to the principles of classical game theory. Recently, such strong assumptions have been relaxed in various ways. One such way is explicitly including principles derived from human behavior. For instance, research in the field of behavioral economics shows that humans are not purely self-interested. In addition, they strongly care about fairness. Therefore, multi-agent systems that fail to take fairness into account, may not be sufficiently aligned with human expectations and may not reach intended goals. In this paper, we present an overview of work in the area of fairness in multi-agent systems. More precisely, we first look at the classical agent model, that is, rational decision making. We then provide an outline of descriptive models of fairness, that is, models that explain how and why humans reach fair decisions. Then, we look at prescriptive, computational models for achieving fairness in adaptive multi-agent systems. We show that results obtained by these models are compatible with experimental and analytical results obtained in the field of behavioral economics.

    HTML

    Rights and permissions
    • Copyright © Cambridge University Press 20082008Cambridge University Press
References (89)
  • About this article
    Cite this article
    STEVEN DE JONG, KARL TUYLS, KATJA VERBEECK. 2008. Fairness in multi-agent systems. The Knowledge Engineering Review. 23: doi: 10.1017/S026988890800132X
    STEVEN DE JONG, KARL TUYLS, KATJA VERBEECK. 2008. Fairness in multi-agent systems. The Knowledge Engineering Review. 23: doi: 10.1017/S026988890800132X
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return