Common-Knowledge and Bayesian Equilibrium in Network Game

• Autorzy: Matsuhisa T.

Identyfikatory

DOI

10.14708/ma.v46i2.6346

Warianty tytułu

PL

Mądrość zespołowa a równowaga bayesowska w grach sieciowych

• Języki publikacji: EN

Abstrakty

EN

In this paper we investigate equilibriums in the Bayesian routing problem of the network game introduced by Koutsoupias and Papadimitriou (1999).We treat epistemic conditions for Nash equilibrium of social costs function in the network game. It highlights the role of common-knowledge on the users' individual conjectures on the others' selections of channels in the network game. Especially two notions of equilibria are presented in the Bayesian extension of the network game; expected delay equilibrium and rational expectations equilibrium. The former equilibrium is given such as each user minimizes own expectations of delay, and the latter is given as he/she maximizes own expectations of a social costs. We show that the equilibria have the properties: If all users commonly know them, then the former equilibrium yields a Nash equilibrium in the based KP-model and the latter equilibrium yields a Nash equilibrium for social costs in the network game. Further we introduce the extended notions of price of anarchy in the Bayesian network game for rational expectations equilibriums for social costs, named the expected price of anarchy and the common-knowledge price of anarchy. We will examine the relationship among the two extended price of anarchy and the classical notion of price of anarchy introduced by Koutsoupias and Papadimitriou(1999).

PL

Rozważane będą modele matematyczne, w których zmiana parametru jest przedmiotem badań statystycznych. Specjalizowanym narzędziem do tego celu są karty kontrolne. Celem pracy jest konstrukcja kart kontrolnych do badania zmian parametru rozkładu obserwowanej cechy w oparciu o dokładne rozkłady różnych estymatorów parametrów kontrolowanych wielkości i ich porównanie.

Słowa kluczowe

EN

Bayesian routing game; common-knowledge; conjecture; expected delay equilibrium; expected price of anarchy; information partition; Nash equilibrium; rational expectations equilibrium; social costs

PL

tworzenie partnerstwa; gra dynamiczna; równowaga Nasha; problem stopowania

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Mathematica Applicanda
• Rocznik: 2018
• Tom: Vol. 46, no. 2
• Strony: 211--243
• Opis fizyczny: Bibliogr. 16 poz., fot., tab.

Twórcy

autor

Matsuhisa T.

• Ibaraki Christian University, Ohmika 6-11-1, Hitachi-shi, Ibaraki 319-1295, Japan
• Karelia Research Centre, Russian Academy of Sciences, Institute of Applied Mathematical Research, Pushkinskaya ulitsa 11, Petrozavodsk, Karelia, 185910, Russia

Bibliografia

• [1] R. J. Aumann. Markets with a continuum of traders. Econometrica, 32 (1/2): 39-50, 1964. ISSN 00129682, 14680262. doi: 10.2307/1913732. URL http://www.jstor.org/stable/1913732. Cited on p. 235.
• [2] R. J. Aumann. Subjectivity and correlation in randomized strategies. J. Math. Econ., 1: 67-96, 1974. ISSN 0304-4068. doi: 10.1016/0304-4068(74)90037-8. Cited on p. 235.
• [3] R. J. Aumann. Agreeing to disagree. Ann. Statist., 4 (6): 1236-1239, 1976. ISSN 0090-5364. doi: 10.1214/aos/1176343654. URL http://links.jstor.org/sici?sici=0090-5364(197611)4:6<1236:ATD>2.0.CO;2-D&origin=MSN. MR 0433654, Zbl 0379.62003. Cited on pp. 212 and 235.
• [4] R. J. Aumann and A. Brandenburger. Epistemic conditions for Nash equilibrium. Econometrica, 63 (5): 1161-1180, 1995. ISSN 0012-9682; 1468-0262/e. doi: 10.2307/2171725. MR 1348517, Zbl 0841.90125. Cited on pp. 221 and 223.
• [5] R. Fagin, J. Y. Halphern, Y. Moses, and M. Y. Vardi. Reasoning about Knowledge. MIT Press, Cambridge, Massachusetts, London, England, 1995. ISBN 9780262061629. MR 1345612. Cited on pp. 212, 221, and 235.
• [6] M. Gairing, B. Monien, and K. Tiemann. Selfish routing with incomplete information. Theory of Computing Systems, 42 (1): 91-130, Jan 2008. ISSN 1433-0490. doi: 10.1007/s00224-007-9015-8. URL https://doi.org/10.1007/s00224-007-9015-8. Cited on pp. 211, 212, and 235.
• [7] J. C. Harsanyi. Games with incomplete information played by ”bayesian” players, i-iii part i. the basic model. Manag. Sci., 14 (3): 159-182, 1967. ISSN 0025-1909 (Print); 1526-5501 (Online). doi: 10.1287/mnsc.14.3.159. Cited on pp. 212 and 235.
• [8] J. C. Harsanyi. Games with incomplete information played by „bayesian” players, i-iii, part ii. bayesian equilibrium point. Manag. Sci., 14 (5): 320-332, 1968. ISSN 0025-1909 (Print); 1526-5501 (Online). doi: 10.1287/mnsc.14.5.320. Cited on pp. 212 and 235.
• [9] J. C. Harsanyi. Games with incomplete information played by „bayesian” players, i-iii, part iii. the basic probability distribution of the game. Manag. Sci., 14 (7): 468-502, 1968. ISSN 0025-1909 (Print); 1526-5501 (Online). doi: 10.1287/mnsc.14.7.486. Cited on pp. 212 and 235.
• [10] E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In STACS 99. 16th annual symposium on Theoretical aspects of computer science, Trier, Germany, March 4-6, 1999. Proceedings, pages 404-413. Berlin: Springer, 1999. ISBN 3-540-65691-X. Zbl 1099.91501. Cited on pp. 211, 212, and 213.
• [11] T. Matsuhisa. Communication and KP-Model. In N. T. Nguyen, S. Tojo, L. M. Nguyen, and B. Trawiński, editors, Intelligent Information and Database Systems, ACIIDS 2017. Lecture Notes in Computer Science, vol. 101922, pages 711-720. Springer, Berlin Heidelberg, 2017. ISBN 978-3-319-54429-8 (Print), 978-3-319-54430-4 (Online). doi: 10.1007/978-3-319-54430-4_68. Cited on p. 234.
• [12] V. Mazalov. Mathematical game theory and applications. John Wiley & Sons, Ltd., Chichester, 2014. ISBN 978-1-118-89962-5. MR 3309667. Cited on pp. 213 and 215.
• [13] J. F. Nash, Jr. Equilibrium points in n-person games. Proc. Natl. Acad. Sci. USA, 36: 48-49, 1950. ISSN 0027-8424; 1091-6490/e. doi: 10.1073/pnas.36.1.48. Zbl 0036.01104, MR 0031701. Cited on p. 215.
• [14] J. F. Nash, Jr. Non-cooperative games. ProQuest LLC, Ann Arbor, MI, 1950. URL http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/Nashfmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:0169578. Thesis (Ph.D.) - Princeton University. Cited on p. 215.
• [15] J. F. Nash, Jr. Non-cooperative games. Annals of Mathematics, 54 (2) :286-295, 1951. ISSN 0003486X. doi: 10.2307/1969529. URL http://www.jstor.org/stable/1969529. MR 0043432. Cited on p. 215.
• [16] R. Parikh and P. Krasucki. Communication, consensus, and knowledge. Journal of Economic Theory, 52 (1): 178-189, 1990. ISSN 0022-0531. doi: 10.1016/0022-0531(90)90073-S. MR 1073702. Cited on p. 234.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).