Kaynak Seçme Oyunlarında Sosyal YapılaşmalarAltında Denge Hesaplaması [Diğer]

Abstract

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.