Universität zu Köln

Voss, Jan (2012). A system-theoretic approach to multi-agent models. PhD thesis, Universität zu Köln.

Preview

PDF Dissertation_Voss.pdf - Published Version Download (600kB)

Abstract

A system-theoretic model for cooperative settings is presented that unifies and ex- tends the models of classical cooperative games and coalition formation processes and their generalizations. The model is based on the notions of system, state and transi- tion graph. The latter describes changes of a system over time in terms of actions governed by individuals or groups of individuals. Contrary to classic models, the pre- sented model is not restricted to acyclic settings and allows the transition graph to have cycles. Time-dependent solutions to allocation problems are proposed and discussed. In par- ticular, Weber’s theory of randomized values is generalized as well as the notion of semi-values. Convergence assertions are made in some cases, and the concept of the Cesàro value of an allocation mechanism is introduced in order to achieve convergence for a wide range of allocation mechanisms. Quantum allocation mechanisms are de- fined, which are induced by quantum random walks on the transition graph and it is shown that they satisfy certain fairness criteria. A concept for Weber sets and two dif- ferent concepts of cores are proposed in the acyclic case, and it is shown under some mild assumptions that both cores are subsets of the Weber set. Moreover, the model of non-cooperative games in extensive form is generalized such that the presented model achieves a mutual framework for cooperative and non-co- operative games. A coherency to welfare economics is made and to each allocation mechanism a social welfare function is proposed.

Item Type:	Thesis (PhD thesis)
Translated title:	Title Language Ein systemtheorethischer Ansatz für Multiagentenmodelle German
Translated abstract:	Abstract Language Ein systemtheoretisches Modell für kooperative Situationen wird vorgestellt, welch- es die klassischen Modelle kooperativer Spiele und Koalitionsbildungsprozesse und deren Verallgemeinerungen vereinigt und erweitert. Das Modell basiert auf den Begrif- fen System, Zustand und Übergangsgraph. Letzterer beschreibt die Veränderung eines Systems in Form von Aktionen, welche von Individuen oder Gruppen von Individuen beherrscht werden. Im Gegensatz zu klassischen Modellen, ist das vorgestellte Mod- ell nicht auf azyklische Situationen beschränkt und erlaubt es dem Übergangsgraphen auch Kreise zu enthalten. Zeitabhängige Lösungen zu Allokationsproblemen werden vorgeschlagen und disku- tiert. Insbesondere wird Webers Theorie der randomisierten Werte, ebenso wie der Begriff des Halbwerts, verallgemeinert. In manchen Fällen werden Konvergenzaus- sagen getroffen und das Konzept des Cesàro-Werts eines Allokationsmechanismus wird eingeführt, um Konvergenz einer großen Menge von Allokationsmechanismen zu erreichen. Quantenallokationsmechanismen, welche von Quantenirrfahrten auf dem Übergangsgraphen induziert werden, werden definiert und es wird gezeigt, dass diese gewissen Fairnesskriterien genügen. Ein Konzept für Weber-Mengen und zwei ver- schiedene core-Konzepte werden im azyklischen Fall vorgeschlagen und es wird unter schwachen Voraussetzungen gezeigt, dass beide cores Teilmengen der Weber-Menge sind. Überdies wird das klassische Modell nicht-kooperativer Spiele in extensiver Form ver- allgemeinert, so dass das vorgestellte Modell einen gemeinsamen Rahmen für koopera- tive und nicht-kooperative Spiele bildet. Ein Zusammenhang zur Wohlfahrtsökonomie wird hergestellt und zu jedem Allokationsmechanismus wird eine gesellschaftliche Wohlfahrtsfunktion vorgeschlagen. German
Creators:	Creators Email ORCID ORCID Put Code Voss, Jan voss@zpr.uni-koeln.de UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-48170
Date:	1 August 2012
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Mathematical Institute
Subjects:	Mathematics
Uncontrolled Keywords:	Keywords Language game theory, cooperation, Shapley value, Banzhaf value, cooperative game, non-cooperative game, tensor-product of games, allocation mechanism, quantum random walk, quantum allocation English Spieltheorie, Kooperation, Shapleywert, Banzhafwert, kooperatives Spiel, nicht-kooperatives Spiel, Tensorprodukt von Spielen, Allokationsmechanismus, Quantenirrfahrt, Quantenallokationen. German
Date of oral exam:	15 June 2012
Referee:	Name Academic Title Faigle, Ulrich Prof. Dr. Schrader, Rainer Prof. Dr. Schönhuth, Alexander Prof. Dr.
References:	[1] D. Aharonov, A. Ambainis, J. Kempe and U. Vazirani (2001): Quantum Walks on Graphs. STOC ’01 Proceedings of the thirty-third annual ACM symposium on Theory of computing. [2] E. Algaba, J.M Bilbao, R. van den Brink and A. Jiménez-Losada (2004): Cooper- ative Games on Antimatroids. Discr. Mathematics 282, 1-15. [3] M. Aigner (1979): Combinatorial Theory. Springer-Verlag. [4] A. Ambainis (2003): Quantum walks and their algorithmic applications. Interna- tional Journal of Quantum Information 1 (4): 507–518. [5] K. J. Arrow (1963): Social Choice and Individual Values. John Wiley & Sons, Inc., New York. [6] R.J. Aumann and J.H. Drèze (1974): Cooperative Games with Cooperation Struc- ture. Int. J. of Game Theory 3, 217-237. [7] J.P. Aumann (1959): Acceptable Points in General Cooperative n-person Games. In: Tucker, A.W., Luce, R.D. (eds.) Contributions to the Theory of Games IV. Princeton: Princeton University Press. [8] J.F. Banzhaf (1965): Weighted Voting Doesn’t Work: A Mathematical Analysis. Rutgers Law Review 19:317–343. [9] M. Beck and S. Robins (2007): Counting the Continuous Discretely. Springer- Verlag. [10] W. R. Belding (1973): Incidence Rings of Pre-ordered Sets. Notre Dame J. Formal Logic Volume 14, Number 4, 481-509. [11] J.M. Bilbao, N. Jiménez Losada E. Lebrón and J.J López (2006): The Marginal operators for Games on Convex Geometries. Intern. Game Theory Review 8, 141-151. [12] Y. Chevaleyre, P. E. Dunne, U. Endriss, J. Lang, M. Lemaître, N. Maudet, J. Pad- get, S. Phelps, J. A. Rodríguez-Aguilar, and P. Sousa (2006): Issues in Multiagent Resource Allocation. Informatica, 30:3-31. [13] J.M. Bilbao (2000): Cooperative Games on Combinatorial Structures. Kluwer Academic Publishers. [14] J.M. Bilbao (2003): Cooperative Games under Augmenting Systems. SIAM Jour- nal on Discrete Mathematics, 24, 992-1010. [15] J.M. Bilbao, T.S.H. Driessen, N. Jiménez-Losada E. Lebrón (2001): The Shapley Value for Games on Matroids. Math. Meth. Oper. Res. 53, 333-348. [16] J.M. Bilbao, J.R. Fernández, N. Jiménez and J.J. López (2008): Biprobabilistic Values for Bicooperative Games. Discr. Appl. Math. 156, 14, 28, 2698-2711 [17] J.M. Bilbao, A. Jiménez-Losada and J.J. López (1998): The Banzhaf Power Index on Convex Geometries. Math. Social Sciences 36, 157-173. [18] P. Borm, H. Keiding, R.P. McLean, S. Oortwijn, S.H. Tijs (1992): The compro- mise value for NTU-games. International Journal of Game Theory 21:175-189 [19] R. v.d. Brink, I. Katsev and G. v.d. Laan (2011): Axiomatizations of Two Types of Shapley Values for Games on Union Closed Systems. to appear in Economic Theory. [20] F. Chung (2005): Laplacians and the Cheeger inequality for directed graphs. An- nals of Combinatorics, 9, 1-19. [21] Y. Chun (1991): On the Symmetric and Weighted Shapley Values. International Journal of Game Theory 20, 183-190. [22] J. Derks (1992): A Short Proof of the Inclusion of the Core in the Weber set. Int. J. Game Theory 21, 149-150. [23] J. Derks and H. Peters (1993): A Shapley Value for Games with Restricted Coali- tions. International Journal of Game Theory, 21, 351-366. [24] P.A.M. Dirac (1942): The Physical Interpretation of Quantum Mechanics. Proc. Royal Soc. London A 180, 1-39. [25] P. Dubey (1980): Asymptotic Semi-values and a Short Proof of Kannai’s Theorem. Math. Oper. res. 5, 267-270. [26] P. Dubey, A. Naham, R.J. Weber (1981): Value Theory without Efficiency. Math. of Op. Res. 6, 122-128. [27] J. Edmonds (1970): Submodular functions, matroids and certain polyhedra. Pro- ceedings of the Calgary International Conference on Combinatorial Structures and their Applications, 69-87. [28] U. Faigle (1989): Cores of Games with Restricted Cooperation. Zeitschrift für Operations Research 33, 405-422 [29] U. Faigle: Personal Communications. 2008-2012. [30] U. Faigle and B. Peis (2008): A Hierarchical Model for Cooperative Games. in: Algorithmic Game Theory, Proceedings SAGT 2008 Paderborn, Springer LNCS 4997, 230-241. [31] U. Faigle and M. Grabisch (2011): Values for Markovian Coalition Processes. Economic Theory, 1, 1-34. [32] U. Faigle, M. Grabisch and M. Heyne (2010): Monge Extensions of Cooperation and Communication Structures. European Journal of Operational Research, 206, 1, 104 - 110. [33] U. Faigle, M. Heyne, Th. Kleefisch and J. Voss (2009): Coalition Formation in Societies. Scientific Research Journal of South-West University 2, 13-18 [34] U. Faigle and W. Kern (1992): The Shapley Value for Cooperative Games under Precedence Constraints. Intern. J. Game Theory 21, 249-266. [35] U. Faigle and W. Kern (1991): Note on the Convergence of Simulated Annealing Algorithms. SIAM J. Control and Optimization, 29, 153-159. [36] U. Faigle, W. Kern and G. Still (2002): Algorithmic Principles of Mathematical Programming. Kluwer Academic Publishers [37] U. Faigle and J. Voss (2011): A System-theoretic Model for Cooperation, Interac- tion and Allocation. Discrete Applied Mathematics, 159, 16, 1736–1750. [38] U. Faigle and A. Schönhuth (2010): Discrete Quantum Markov Chains. Submit- ted manuscript. [39] U. Faigle and A. Schönhuth (2005): Note on Negative Probabilities and Ob- servable Processes. In: S. Albers, R. Moehring, C. Pflug, R. Schultz (eds.) Algo- rithms for Optimization with Incomplete Information Dagstuhl Seminar Proceed- ings 05031, 108:1-14. [40] J. Feigenbaum, J. Hershberger, A.A. Schäfer (1985): A Polynomial Time Algo- rithm for Finding the Prime Factors of Cartesian–Product Graphs. Discrete Appl. Math. 12 123-138. [41] R.P. Feynman (1987): Quantum Implications. Essays in Honour of David Bohm, B.J. Hiley and F.D. Peat eds., Routledge and Kegan Paul, London, 235-246. [42] G. Frobenius (1912): Über Matrizen aus nicht negativen Elementen. Berl. Ber. 1912, 456-477. [43] Y. Funaki and M. Grabisch (2008): A Coalition Formation Value for Games in Partition Function Form. CES Working Papers, 2008. [44] M. Grabisch and F. Lange (2007): Games on Lattices, Multichoice games and the Shapley Value: a New Approach. Math. Methods of Oper. Res., Vol. 65, 153-167. [45] M. Grabisch and L. Xie: The Restricted Core of Games on Distributive Lattices: How to Share Benefits in a Hierarchy. Working paper. [46] R.P. Gilles, G. Owen and R. van den Brink (1992): Games with Permission Struc- tures: the Conjunctive Approach. Intern. J. Game Theory 20 (1992), 277-293. [47] D.B. Gillies (1959): Solutions to General Non-zero-sum Games. Annals of Math- ematics Studies 40: Contributions to the Theory of Games IV, Princeton University Press, 47-85. [48] Harsanyi, J.C. (1959): A bargaining model for the cooperative n–person games. In: Contributions to the Theory of Games IV (A.W. Tucker and R.D. Luce, eds.), Princeton University Press, 325–356. [49] C.R. Hsiao and TES Raghavan (1993): Monotonicity and Dummy Free Property for Multi-Choice Cooperative Games. Int. J. of Game Theory 21, 301-312. [50] C.R. Hsiao and TES Raghavan (1993): Shapley Value for Multichoice Coopera- tive Games. Games and Economic Behavior 5, 240-256. [51] T.S. Han and K. Kobayashi (1994): Mathematics of Information and Coding. Amer. math. Soc.. [52] J. Hajdukova (2006): Coalition Formation Games: A survey. Int. Game Theory Review, 8, 613-641. [53] J.L. Hougaard and L.P. Østerdal (2010): Monotonicity of Social Welfare Optima. Games and Economic Behavior, vol. 70(2), 392-402. [54] B. Huppert (1990): Angewandte Lineare Algebra. Berlin, de Gruyter. [55] A. Irle (2005): Wahrscheinlichkeitstheorie und Statistik. 2. Auflage, Teubner Ver- lag. [56] B. Korte, L. Lovász and R. Schrader (1991): Greedoids. Springer Verlag. [57] E. Kalai and D. Samet (1987): On Weighted Shapley Values. International Journal of Game Theory, 16, 3, 205-222. [58] E. Kalai and M. Smorodinsky (1975): Other Solutions to Nash’s Bargaining Prob- lem. Econometrica 43 (3): 513–518. [59] E. Kalai and E. Zemel (1982): On Totally Balanced Games and Games of Flow. Mathematics of Operations Research, Vol. 7, 3. [60] J. Kempe (2003): Quantum random walks - an introductory overview. Contempo- rary Physics 44 (4): 307–327. [61] S. Lang (2002): Algebra. Graduate Texts in Mathematics 211 ((Rev. 3rd ed.) ed.). New York, Springer. [62] D.A. Levin, Y. Peres and E.L. Wilmer (2006): Markov Chains and Mixing Times. American Mathematical Society. [63] I. Macho-Stadler, D. Perez-Castillo and D. Wettstein (2007): Sharing the Sur- plus: An Extension of the Shapley Value for Environments with Externalities. J. of Economic Theory, 135, 339-356. [64] N. Megiddo (1975): Decomposition of Cooperative Games. SIAM Journal on Applied Mathematics, 29, 3, 388-405. [65] W. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller and E. Teller (1953): Equation of State Calculations by Fast Computing Machines. J. Chem. Phys., 21, 1087-1092. [66] D. Monderer and L.S. Shapley (1996): Potential Games. Games and Econ. Behav., 14, 124-143. [67] A. Montanaro (2007): Quantum Walks on Directed Graphs. Quantum Inf. Comp, 7, 93-102. [68] H. J. Moulin (2003): Fair Division and Collective Welfare. MIT Press, 2003. [69] J. Nash (1950): Equilibrium points in n-person games. Proceedings of the Na- tional Academy of Sciences 36(1), 48-49. [70] J. v. Neumann and O. Morgenstern (1944): Theory of Games and Economic Be- havior. Princeton University Press. [71] N. Nisan, T. Roughgarden, É. Tardos and V. V. Vazirani (2007): Algorithmic Game Theory. Camebridge University Press. [72] G. Owen (1975): Multilinear Extensions and the Banzhaf Value. Naval Research Logistics Quart 22:741–750. [73] G. Owen (1964): Tensor Composition of non-negative Games, Advances in Game Theory, M. Dresher,L. S. Shapley and A. W. Tucker, eds., Annals of Mathematics Studies, No. 52, Princeton University Press. Princeton, 307-327. [74] O. Perron: Zur Theorie der Matrices. Math. Ann. 64, 1907, 248-263. [75] J.L. Ramírez-Alfonsín (1996): Complexity of the Frobenius Problem. Combina- torica 16, 143-147. [76] R.W. Rosenthal (1973): A class of games possessing pure-strategy Nash equilib- ria. Int. J. of Game Theory, 2, 1, 65–67. [77] G.-C.Rota (1964): On the Foundations of Combinatorial Theory I: Theory of Möbius Functions. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebi- ete 2, 4, 1964, 340–368. [78] A.E. Roth (1977): The Shapley Value as a von Neumann-Morgenstern Utility, Econometrica 45, 657-664. [79] B. Russell (1912): Principia Mathematica. Cambridge University Press. vol. 2. [80] G.Sabidussi (1960): Graph Multiplication. Math.Z. 72, 446-457. [81] A. Schönhuth (2007): Diskretwertige stochastische Vektorräume, Dissertation Universität zu Köln. [82] L.S. Shapley (1953): A Value for n-Person Games. In: Contributions to the Theory of Games, H.W. Kuhn and A.W. Tucker eds., Ann. Math. Studies 28, Princeton University Press, 307-317. [83] L.S. Shapley (1953): Additive and Non-additive Set Functions. PhD Thesis, De- partment of Mathematics, Princeton University Press. [84] L. S. Shapley (1962): Compound Simple Games I & II, RAND Corp., RM-3192, RAND Corp., RM-3643. [85] L.S. Shapley (1971): Cores of Convex Games. International Journal of Game Theory, 1, 11-26. [86] L.S. Shapley and Martin Shubik (1969): On Market Games. Journal of Economic Theory, Volume 1, Issue 1, Pages 9-25. [87] R.M. Thrall and W.F. Lucas (1963): n-Person Games in Partition Function Form. Noval Research Logistics Quarterly 10, 281-298. [88] S.H. Tijs and G.-J. Otten (1993): Compromise Values in Cooperative Game The- ory. TOP 1, 1, 1-36. [89] V.G. Vizing (1963): The Cartesian Product of Graphs. Vycisl.Syst. 9, 30-43, [90] N.N. Vorob’ev (1975): Game Theory. 1st. Ed., Springer-Verlag. [91] R.J. Weber (1988): Probabilistic Values for Games. In: A.E. Roth (ed.), The Shapley Value, Cambrigde University Press, Cambridge, 101-120. [92] P.M. Winkler (1987): Factoring a Graph in Polynomial Time. European J.Combin. 8, 209-212.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/4817