Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması

Buğra ÇAŞKURLU (TOBB EKONOMİ VE TEKNOLOJİ ÜNİVERSİTESİ, MÜHENDİSLİK FAKÜLTESİ, BİLGİSAYAR MÜHENDİSLİĞİ BÖLÜMÜ)
Özgün EKİCİ (TOBB EKONOMİ VE TEKNOLOJİ ÜNİVERSİTESİ, MÜHENDİSLİK FAKÜLTESİ, BİLGİSAYAR MÜHENDİSLİĞİ BÖLÜMÜ)
5 2

Proje Grubu: EEEAG Sayfa Sayısı: 61 Proje No: 118E126 Proje Bitiş Tarihi: 15.12.2020 Metin Dili: Türkçe İndeks Tarihi: 10-01-2022

Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması

Öz:
Oyun kuramında, çözümlemeler için denge konseptleri büyük önem taşımaktadır. Oyun kuramının bir dalı olan koalisyonel oyun kuramı oyuncuların aralarında koalisyonlar kurabildiği varsayımı altında tanımlanan denge konseptlerini kullanır. Stratejik formda bir oyunda, kurulu olan hiçbir koalisyonun stratejilerini ortaklaşa değiştirerek refahını artıramadığı strateji profillerine (koalisyonel) denge denir. Daha zayıf veya güçlü denge konseptleri koalisyonların formasyonu üzerine yapılan çeşitli sınırlamalarla tanımlanabilir. Örneğin, bir Nash dengesinde, sadece tek bir oyuncudan oluşan koalisyonların kurulduğu varsayılmaktadır. Diğer zıt duruma karşılık gelen güçlü Nash dengesinde ise her koalisyonun (yani oyuncuların boş olmayan her alt kümesinin) kurulduğu kabul edilmektedir. Ancak, her koalisyonun kurulduğu varsayımı çalışmaya değer çoğu oyun için fazla zorlayıcıdır ve dolayısıyla çoğu oyunda güçlü Nash dengesi yoktur. Öte yandan, bir partisyon dengesinde, koalisyon formasyonu oyuncuların partisyonları ile sınırlanmaktadır. Bunun güçlü Nash dengesine göre çok daha az zorlayıcı olduğuna dikkat ediniz (zira bir partisyon dengesinde kurulu koalisyon sayısı O(n) iken güçlü Nash dengesinde oyuncu sayısı cinsinden üstseldir). Örneğin, bir partisyon dengesi kaynak seçme oyunlarında her zaman varken, bir güçlü Nash dengesi bu oyunların çok basit durumlarında bile yoktur. Koalisyon formasyonu üzerine daha sofistike sınırlamalar iletişime, koordinasyona ve kurumlaşmaya bağlı kısıtlar ile motive edilebilir. Bu projede, genelgeçer sosyal yapılaşmalardan ilhamla koalisyon formasyonu üzerine çeşitli sınırlamalar ve bu esasla tanımlanmış çeşitli denge konseptleri tanımlanmıştır. Bu denge konseptleri kaynak seçme oyunlarında çalışılmış ve bu oyunların hem genelinde hem de önemli özel durumlarında tanımladığımız denge konseptlerine göre denge strateji profillerinin varlık garantisinin olup olmadığı her denge konsepti için eksiksiz bir şekilde tespit edilmiştir. Ayrıca varlık garantisi olan durumlarda dengeyi bulmak için verimli algoritmalar sunulmuştur. Son olarak, oyuncuların bir partisyon oluşturmayı amaçladıkları hedonik oyunların önemli bir altsınıfında verimli denge profilinin olduğu ama hesaplamanın NP-zor olduğu gösterilmiştir. Bu proje kapsamında yapılan çalışmalar 4 adet akademik çalışmaya dönüştürülmüştür.
Anahtar Kelime: kaynak seçme oyunları partisyon dengesi koalisyonel denge konseptleri algoritmik oyun kuramı

Konular: Bilgisayar Bilimleri, Teori ve Metotlar
Erişim Türü: Erişime Açık
  • [1] Von Neumann, J., Morgenstren, O. 1944. Theory of Games and Economic Behavior, Princeton: Princeton University Presss.
  • 1- On efficient computation of equilibrium under social coalition structures (Makale - İndeksli Makale),
  • [2] Bernard, J. 1954. “The theory of games of strategy as a modern sociology of conflict”, American Journal of Sociology, 59(5), 411-424.
  • 2- On Hedonic Games with Common Ranking Property (Bildiri - Uluslararası Bildiri - Sözlü Sunum),
  • [3] Colman, A.M. 2003. “Cooperation, psychological game theory, and limitations of rationality in social interaction”, Behavioral and Brain Sciences, 26(02), 139-153.
  • 3- On Existence of Equilibrium Under Social Coalition Structures (Bildiri - Uluslararası Bildiri - Sözlü Sunum),
  • [4] Smith, J. 1982. Evolution and the Theory of Games, Cambridge: Cambridge University Press.
  • [5] Russell, S. J., Norvig, P. 2003. Artificial Intelligence: A Modern Approach. Upper Saddle River, New Jersey: Prentice Hall.
  • [6] Dijkstra, E. W. 1959. “A note on two problems in connexion with graphs”, Numerische Mathematik, 1, 269–271.
  • [7] Pettie, S., Ramachandran, V. 2002. “An optimal minimum spanning tree algorithm”, Journal of the Association for Computing Machinery, 49(1), 16-34.
  • [8] Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. 2009. Introduction to Algorithms, USA: The MIT Press.
  • [9] Kleinberg, J., Tardos, E. 2005. Algorithm Design, Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc.
  • [10] Hearn, R. A., Demaine, E. D. 2009. Games, Puzzles, and Computation, Natick, MA, USA: A. K. Peters, Ltd.
  • [11] Nisan, N., Roughgarden, T., Tardon, E., Vazirani, V.V. 2007. Algorithmic Game Theory, New York: Cambridge University Press.
  • [12] Roughgardan, T. 2016. Twenty Lectures on Algorithmic Game Theory, New York, NY, USA: Cambridge University Press.
  • [13] Shoham, Y. Brandt, F., Fischer, F., Harrenstein, Paul. 2007. “A game-theoretic analysis of strictly competitive multiagent scenarios”, Proceedings of the 20th international joint conference on Artifical intelligence. 1199-1206.
  • [14] Shoham, Y., Leyton-Brown, K. 2008. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, New York, NY, USA: Cambridge University Press.
  • [15] Nash, J. 1951. “Non-Cooperative games”, Annals of Mathematics, 54(2), 286–295.
  • [16] Aumann, R.J. 1959. “Acceptable points in general cooperative n-person games”, Contributions to the Theory of Games IV, Editörler: Luce, R. D., Tucker, A. W. Princeton: Princeton University Press.
  • [17] Feldman, M., Tennenholtz, M. 2010. “Structured coalitions in resource selection games”, ACM Trans. Intell. Syst. Technol., 1(1), 4.
  • [18] Anshelevich, E., Çaşkurlu, B., Hate, A. 2013. “Partition equilibrium always exists in resource selection games”, Theory of Computing Systems, 53(1), 73–85.
  • [19] Roughgardan, T., Tardos, E. 2002. “How bad is selfish routing?”, J. ACM, 49(2), 236–259.
  • [20] Anshelevich, E., et. al. 2004. “The price of stability for network design with fair cost allocation”, Proc. 45th Symp. Fdns. of Computer Science, 295–304.
  • [21] Caragiannis, I., et. al. 2006. “Tight bounds for selfish and greedy load balancing”, Proc. 33rd Intl. Colloq. on Automata, Languages, and Programming, 311–322.
  • [22] Rosenthal, R.W. 1973. “A class of games possessing pure-strategy Nash equilibria”, International Journal of Game Theory, 2, 65–67.
  • [23] Holzman, R., Law-Yone, N. 1997. “Strong equilibrium in congestion games”, Games and Economic Behavior, 21(1-2), 85–101.
  • [24] Bernheim, B.D., Peleg, B., Whinston, M.D. 1987. “Coalition-proof Nash equilibria concepts”, J. Econ. Theory, 42(1), 1–12.
  • [25] Konishi, H., Le Breton, N., Weber, S. 1997. “Equilibria in a model with partial rivalry”, J. Econ. Theory 72(1), 225–237.
  • [26] Konishi, H., Le Breton, M., Weber, S. 1999. “On coalition-proof Nash equilibria in common agency games”, J. Econ. Theory, 85(1), 122–139.
  • [27] Moreno, D., Wooders, J. 1996. “Coalition-proof equilibrium”, Games and Economic Behavior, 17(1), 80–112.
  • [28] Hayrapetyan, A., Tardos, E., Wexler, T. 2006. “The effect of collusion in congestion games”, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, 89–98.
  • [29] Roughgarden, T. 2005. “Selfish routing with atomic players”, ACM-SIAM Symposium on Discrete Algorithms, 1184–1185.
  • [30] Cominetti, R., Correa, J.R., Stier-Moses N.E. 2006. “Network games with atomic players”, ICALP 2006: Automate Languages and Programming, 525–536.
  • [31] Hoefer, M., Penn, M., Polukarov, M., Skopalik, A., Vöcking, B. 2011. “Considerate equilibrium”, Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, 1, 234–239.
  • [32] Harks, T., Klimm, M., Mohring, R.H., 2009. Strong nash equilibria in games with the lexicographical improvement property. Proceedings of the 5th International Workshop on Internet and Network Economics (WINE), 463–470.
  • [33] Dreze, J. H., Greenberg, J. 1980. “Hedonic coalitions: Optimality and stability”, Econometrica, 987–1003.
  • [34] Roth, A. E. 1984. “The evolution of the labor market for medical interns and residents: A case study in game theory”, Journal of Political Economy, 92(6), 991–1016.
  • [35] Roth, A. E., Peranson, E. 1999. “The redesign of the matching market for American physicians: Some engineering aspects of economic design”, American economic review, 89(4), 748–780.
  • [36] Maggs, B. M., Sitaraman, R. K. 2015. “Algorithmic nuggets in content delivery”, ACM SIGCOMM Computer Communication Review, 45(3), 52–66.
  • [37] Farrell, J., Scotchmer, S. 1988. “Partnerships”, “The Quarterly Journal of Economics, 103(2), 279–297.
  • [38] Woeginger, G. J. 2013. “Core stability in hedonic coalition formation”, In Procedings of 39th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM’13), 33–50.
  • [39] Dyer, M., Frieze, A. 1986. “Planar 3DM is NP-complete”, J. Algorithms 7(2), 174–184.
  • [40] Bazgan, C., Escoffier, B., Paschos, V.T. 2005. “Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness”, Theor. Comput. Sci. 339(2– 3), 272–292.
  • [41] Alimonti, P., Kann, V. 2000. “Some APX-completeness results for cubic graphs”, Theor. Comput. Sci. 237(1–2), 123–134.
APA Caskurlu B, Ekici O (2020). Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması. , 1 - 61.
Chicago Caskurlu Bugra,Ekici Ozgun Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması. (2020): 1 - 61.
MLA Caskurlu Bugra,Ekici Ozgun Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması. , 2020, ss.1 - 61.
AMA Caskurlu B,Ekici O Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması. . 2020; 1 - 61.
Vancouver Caskurlu B,Ekici O Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması. . 2020; 1 - 61.
IEEE Caskurlu B,Ekici O "Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması." , ss.1 - 61, 2020.
ISNAD Caskurlu, Bugra - Ekici, Ozgun. "Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması". (2020), 1-61.
APA Caskurlu B, Ekici O (2020). Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması. , 1 - 61.
Chicago Caskurlu Bugra,Ekici Ozgun Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması. (2020): 1 - 61.
MLA Caskurlu Bugra,Ekici Ozgun Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması. , 2020, ss.1 - 61.
AMA Caskurlu B,Ekici O Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması. . 2020; 1 - 61.
Vancouver Caskurlu B,Ekici O Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması. . 2020; 1 - 61.
IEEE Caskurlu B,Ekici O "Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması." , ss.1 - 61, 2020.
ISNAD Caskurlu, Bugra - Ekici, Ozgun. "Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması". (2020), 1-61.
Sayfa Oluşturulma Tarihi
18-04-2024 3:19

İLETİŞİM

TÜBİTAK ULAKBİM TR Dizin

Yüzüncüyıl, İşçi Blokları Mahallesi

Muhsin Yazıcıoğlu Caddesi No:51/C

06530 Çankaya / ANKARA +90 (312) 298 92 00

trdizin@tubitak.gov.tr

TÜBİTAK ULAKBİM Ulusal Akademik Ağ ve Bilgi Merkezi Cahit Arf Bilgi Merkezi © Tüm Hakları Saklıdır. Gizlilik Politikası Kullanım Şartları