Implementation of a Value for Generalized Characteristic Function Games

• Autorzy: Michalak T. P. , Rahwan T.
• Języki publikacji: EN

Abstrakty

EN

Generalized characteristic function games are a variation of characteristic function games, in which the value of a coalition depends not only on the identities of its members, but also on the order in which the coalition is formed. This class of games is a useful abstraction for a number of realistic settings and economic situations, such as modeling relationships in social networks. To date, two main extensions of the Shapley value have been proposed for generalized characteristic function games: the Nowak-Radzik value and the S´anchez-Berganti˜nos value. In this context, the present article studies generalized characteristic function games from the point of view of implementation and computation. Specifically, the article presents a non-cooperative mechanism that implements the Nowak-Radzik value in Subgame-Perfect Nash Equilibria in expectation.

Słowa kluczowe

EN

generalized characteristic function games; Shapley value implementation

• Wydawca: Warszawska Wyższa Szkoła Informatyki
• Czasopismo: Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki
• Rocznik: 2014
• Tom: nr 11
• Strony: 7--27
• Opis fizyczny: Bibliogr. 27 poz.

Twórcy

autor

Michalak T. P.

• Department of Computer Science, University of Oxford, UK
• Institute of Informatics, University of Warsaw, Poland

autor

Rahwan T.

• Masdar Institute of Science and Technology, UAE
• Warsaw School of Computer Science, Poland

Bibliografia

• [1] G. Chalkiadakis, E. Elkind, and M. Wooldridge. Computational Aspects of Cooperative Game Theory. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2011.
• [2] A. Nowak and T. Radzik. The Shapley value for n-person games in generalized characteristic function form. Games and Economic Behavior, 6(1):150–161, 1994.
• [3] A. Rutherford, M. Cebrian, I. Rahwan, S. Dsouza, J. McInerney, V. Naroditskiy, M. Venanzi, N. R Jennings, E. Wahlstedt, S. U Miller, et al. Targeted social mobilization in a global manhunt. PLOS One, 8(9):e74628, 2013.
• [4] I. Rahwan, S. Dsouza, A. Rutherford, V. Naroditskiy, J. McInerney, M. Venanzi, N. R Jennings, and M. Cebrian. Global manhunt pushes the limits of social mobilization. IEEE Computer, 46(4):68–75, 2013.
• [5] E. S´anchez and G. Bergantin˜nos. Coalitional values and generalized characteristic functions. Mathematical Methods of Operations Research, 49(3):413–433, 1999.
• [6] L. S. Shapley. A value for n-person games. In H.W. Kuhn and A.W. Tucker, editors, In Contributions to the Theory of Games, volume II, pages 307–317. 1953.
• [7] E. S´anchez and G. Berganti˜nos. On values for generalized characteristic functions. OR Spektrum, 19(3):229–234, 1997.
• [8] M. del Pozo, C. Manuel, E. Gonz´alez-Arang¨uena, and G. Owen. Centrality in directed social networks. a game theoretic approach. Social Networks, 33(3):191–200, 2011.
• [9] R. Amer, Jos´e M. Gim´enez, and A. Mag˜ana. A ranking for the nodes of directed graphs based on game theory. Proceedings in Applied Mathematics and Mechanics, 7(1), 2007.
• [10] R. Amer, J. M. Gim´enez Pradales, and A. Maga˜na Nieto. Nodes of directed graphs ranked by solutions defined on cooperative games. In XXXII Congreso Nacional de Estad´ıstica e Investigaci´on Operativa”, pages 1–20, 2010.
• [11] S. J. Brams, H. Mutlu, and S. L. Ramirez. Influence in terrorist networks: From undirected to directed graphs. In Studies in Conflict and Terrorism 29(7), 2006.
• [12] H. K. Lentz, T. Selhorst, and I. M. Sokolov. Spread of infectious diseases in directed and modular metapopulation networks. Physical Review E, 85:066111, Jun 2012.
• [13] A. Dasgupta and Y. S. Chiu. On implementation via demand commitment games. International Journal of Game Theory, 27(2):161–189, 1998.
• [14] F. Gul. Bargaining foundations of Shapley value. Econometrica, 57(1):81–95, 1989.
• [15] S. Hart and Z. Levy. Efficiency does not imply immediate agreement. Econometrica, 67(4):909–912, 1999.
• [16] R. A. Evans. Value, consistency, and random coalition formation. Games and Economic Behavior, 12(1):68–80, 1996.
• [17] D. P´erez-Castrillo and D.Wettstein. Bidding for the surplus: A non-cooperative approach to the Shapley value. Journal of Economic Theory, 100(2):274–294, 2001.
• [18] D. P´erez-Castrillo and D. Wettstein. Implementation of the ordinal Shapley value for a three–agent economy. Economics Bulletin, 3(48):1–8, 2005.
• [19] J. Vidal-Puga and G. Berganti˜nos. An implementation of the owen value. Games and Economic Behavior, 44(2):412–427, 2003.
• [20] Y. Ju and D. Wettstein. Bidding with coalitional externalities: A strategic approach to partition function form games. European Meeting of the Econometric Society in Budapest, Hungary, pages 1–17, 2007.
• [21] K. Hang P. Do and H. Norde. The Shapley value for partition function form games. International Game Theory Review, 09(02):353–360, 2007.
• [22] I. Macho-Stadler, D. P´erez-Castrillo, and D.Wettstein. Efficient bidding with externalities. Games and Economic Behavior, 57(2):304–320, 2006.
• [23] I. Macho-Stadler, D. P´erez-Castrillo, and D. Wettstein. Dividends and weighted values in games with externalities. International Journal of Game Theory, 39(1):177–184, March 2010.
• [24] R. van den Brink and Y. Funaki. Axiomatization and implementation of discounted Shapley values. Tinbergen institute discussion papers, Tinbergen Institute, July 2010.
• [25] G. Bergantin˜nos and E. S´anchez. Weighted Shapley values for games in generalized characteristic function form. TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 9(1):55–67, 2001.
• [26] R. Serrano. Fifty Years of the Nash Program, 1953-2003. Technical Report 2004-20, Brown University, 2004.
• [27] Y. Shoham and K. Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2009.