Oyun Teorisi
Stratejik etkileşim, Nash dengesi, algoritmik denge hesaplama, pişmanlık minimizasyonu ve mekanizma tasarımını bilgisayar bilimi açısından inceleyen akademik ders.
Oyun teorisi, birbirlerinin kararlarından etkilenen birden fazla karar vericinin stratejilerini matematiksel olarak inceler. Bu derste stratejik etkileşimin bilgisayar bilimindeki hesaplama problemleri; saf ve karma denge, denge bulma algoritmaları, öğrenme, ağ oyunları ve teşvik tasarımı üzerinden geliştirilir. Bireysel rasyonellik ile sistem düzeyindeki verimlilik farklı ölçütlerdir.
Ünite 1: Oyunların Matematiksel Gösterimi ve Stratejik Kararlar
1.1. Oyuncular, Stratejiler ve Fayda Fonksiyonları
Stratejik oyunda oyuncular kümesi, her oyuncunun strateji kümesi ve strateji profiline bağlı fayda fonksiyonları tanımlanır. Bir oyuncunun seçimi, diğer oyuncuların seçiminden bağımsız bir optimizasyon değildir. Normal biçimli ve geniş biçimli gösterimler aynı etkileşimin farklı bilgi yapıları altında incelenmesini sağlar.
1.2. Dağıtık Kaynak Paylaşımı Modelleri
Dağıtık kaynak paylaşımında eylem bir sunucu veya kanal seçimi, fayda ise gecikme ve kaynak maliyetinin fonksiyonu olabilir. Faydanın ölçümden nasıl türetildiği açık olmalıdır. Strateji kümeleri sonsuz ise sonlu matrisle temsil her durumda mümkün değildir.
G = (N, (Sᵢ)ᵢ∈N, (uᵢ)ᵢ∈N); uᵢ : ∏[j] Sⱼ → ℝ1.3. Fayda Tablolarının Tutarlılığı
Denge analizi yapılmadan önce her strateji profilinin fayda değeri ve uygunluk koşulları doğrulanır. Fayda dönüşümlerinin dengeyi koruyup korumadığı; oyuncu başına pozitif afin dönüşümlerle diğer dönüşümler arasında ayrım yapılarak incelenir.
1.4. Sayısal ve Algoritmik Örnek
İki oyunculu basit paylaşım oyununda stratejiler A ve B kaynakları olsun. Her iki oyuncu A seçerse yük artışından dolayı fayda azalabilir; biri B ye geçtiğinde denge değişebilir. Bu davranış bir görev atama optimumundan farklıdır, çünkü oyuncuların amaçları birbirine eşit olmak zorunda değildir.
1.5. Stratejik Modelin Bileşenleri
Sonlu normal biçimli oyunda oyuncu kümesi, her oyuncunun eylem uzayı ve ortak eylem profiline bağlı faydalar açıkça belirtilir. Fayda, yalnız parasal gelir değildir; gecikme, hesaplama maliyeti ve erişim kalitesi gibi büyüklükler dönüştürülerek kullanılabilir. Ancak fayda ölçeği ve dönüşümün tercih sırasını koruyup korumadığı denge yorumunu etkiler. Bir ağda her kullanıcı bağımsız yol seçiyorsa genel sistem maliyeti oyuncu faydalarının basit toplamına eşit olmayabilir.
G = (N, (Sᵢ)ᵢ∈N, (uᵢ)ᵢ∈N)1.6. Merkezî Optimizasyon ve Stratejik Etkileşim
Tek karar vericili optimizasyonda tek bir amaç fonksiyonunun en iyi değeri aranır. Stratejik modelde her oyuncu kendi faydasını artırmaya çalışırken diğerlerinin eylemleri ortamı değiştirir. Ortak sistem hedefi, oyuncuların tercihleriyle uyumsuz olabilir. Bu nedenle merkezi en iyi kaynak paylaşımının neden kendiliğinden gerçekleşmeyebileceği, kullanıcıların bağımsız karar verdiği iki alternatifli küçük modeller üzerinde açıklanmalıdır.
1.7. Ödeme Matrislerinde Doğruluk Denetimi
İki oyunculu sonlu bir oyunda ödeme tablosunun her hücresi sıralı bir fayda çiftidir. Matrisin satır ve sütun sıralaması sabit tutulmazsa en iyi tepki hesapları yanlış oyuncuya uygulanabilir. Rastgele oluşturulan oyunlar için her eylem profilinde fayda fonksiyonuyla matris hücresinin eşleştiği test edilir. Çok oyunculu oyunlarda tam normal biçim tablo boyutu eylem kümelerinin çarpımı oranında büyüdüğünden sıkıştırılmış temsil gerekebilir.
1.8. Hesaplamalı Örnek ve Çözüm
İki kullanıcı A ve B kaynaklarından birini seçsin. Kaynağın maliyeti onu kullanan kullanıcı sayısına eşit olsun. İkisi de A seçerse maliyetleri 2, ayrı kaynaklara geçerlerse her birinin maliyeti 1 olur. Bu, bireysel karar ile toplam maliyet ilişkisini açıkça gösterir.
C(A,A)=4; C(A,B)=21.9. Bağımsız Doğrulama ve Gerçekleme Sınırları
Ödemelerde maliyet küçültme ile fayda büyütme işaret farkı korunmalıdır; aksi hâlde en iyi tepki yönü tersine döner.
Ünite 2: Normal Biçimli Oyunlar ve En İyi Tepki Analizi
2.1. En İyi Tepki Bağıntısı
En iyi tepki kümesi, diğer oyuncuların stratejileri sabitken faydayı ençoklayan eylemlerden oluşur. Kesin baskınlık ile zayıf baskınlık aynı değildir: zayıf baskın stratejilerin elenmesi sıralamaya duyarlı olabilir. Rasyonellik varsayımı, oyun matrisinden otomatik olarak elde edilen deneysel bir özellik değildir.
2.2. Baskınlık ve Strateji Eleme Algoritmaları
Sonlu oyunlarda her oyuncunun eylemi taranarak en iyi tepki hesaplanabilir. Strateji profili sayısı oyuncu sayısıyla çarpımsal büyür; dolayısıyla tam tablo enumerasyonu üstel ölçekte olabilir. Seyrek fayda gösterimleri daha büyük oyunlarda bellek tüketimini azaltır.
BRᵢ(s₋ᵢ) = arg max[a∈Sᵢ] uᵢ(a, s₋ᵢ)2.3. Sonlu Oyunların Hesaplama Maliyeti
Baskın strateji elemesi uygulanırken elenen stratejiler ve kullanılan karşılaştırma ölçütleri kayıt altına alınır. Karma stratejiler dahil edilmediğinde bulunan en iyi tepkiler yalnız saf strateji uzayına aittir.
2.4. Sayısal ve Algoritmik Örnek
İki oyuncunun her biri için iki eylem olduğunda dört saf profil taranır. Her profilde her oyuncunun diğer eyleme geçerek kazancını artırıp artırmadığı test edilir. Sadece bütün sapma kazançları sıfır veya negatif olan profiller saf Nash dengesidir.
2.4.1. Açıklayıcı Sözde Kod
for profile in cartesian_product(strategy_sets):
deviations = []
for player in players:
deviations += profitable_unilateral_deviations(player, profile)
if deviations == []: report_pure_equilibrium(profile)2.5. Katı ve Zayıf Baskınlık
Bir eylem her karşı taraf stratejisinde diğerinden kesin daha düşük fayda veriyorsa katı biçimde baskılanmıştır. Böyle eylemler sonlu oyunda rasyonel en iyi tepki olamaz. Zayıf baskınlıkta ise bazı durumlarda eşitlik bulunduğundan eleme sırası ve varsayımlar önem kazanır. Eylemlerin iteratif elenmesi Nash denge hesaplamasına yardımcı olabilir; ancak zayıf baskın eylemleri gelişigüzel silmek olası dengeleri ortadan kaldırabilir.
uᵢ(aᵢ,s₋ᵢ) > uᵢ(bᵢ,s₋ᵢ) ∀s₋ᵢ2.6. En İyi Tepki Hesaplama
En iyi tepki, diğer oyuncuların stratejileri sabitken oyuncunun faydasını maksimize eden eylemlerin kümesidir. Birden fazla eylem eşit fayda sağlıyorsa tek bir eylem yerine çok değerli tepki kümesi elde edilir. Saf Nash dengesi, bütün oyuncular için bu kümelerin ortak tutarlılığını gerektirir. Küçük matrislerde her profil taranabilir; çok oyunculu veya örtük fayda fonksiyonlu modellerde bu işlemin maliyeti hızla büyür.
2.7. Saf Denge Bulma ve Doğrulama
Bir strateji profilinin saf Nash dengesi olup olmadığı, her oyuncu için bütün tek taraflı sapmalar kontrol edilerek doğrulanabilir. Saf dengenin hiç bulunmaması, oyunun matematiksel olarak çözümsüz olduğu anlamına gelmez; sonlu oyunlarda karma strateji dengesi mevcuttur. Tüm profilleri numaralandıran test bir doğrulama referansıdır fakat çok büyük oyunlar için ölçeklenebilir bir arama yöntemi değildir.
2.8. Hesaplamalı Örnek ve Çözüm
İki oyuncunun eş eylem seçtiğinde ikişer, farklı eylem seçtiğinde sıfır fayda aldığı bir koordinasyon oyunu kurulsun. (A,A) ve (B,B) saf Nash dengeleridir; farklı eylem profillerinde oyunculardan biri kazançlı sapma yapabilir.
uᵢ(A,A)=uᵢ(B,B)=2; uᵢ(A,B)=uᵢ(B,A)=02.9. Bağımsız Doğrulama ve Gerçekleme Sınırları
İki saf dengenin bulunması, denge sonucunun tek olmadığına ilişkin doğrulama örneğidir. Başka stratejiler tanımlanırsa bütün sapmalar yeniden sınanmalıdır.
Ünite 3: Sıfır Toplamlı Oyunlar ve Minimax Teoremi
3.1. Sıfır Toplamlı Fayda Matrisleri
İki oyunculu sıfır toplamlı oyunda bir oyuncunun kazancı diğerinin kaybına eşittir. Karma strateji olasılık dağılımı olduğundan her dağılımın bileşenleri negatif olmayan ve toplamı bir olan sayılardır. Sonlu iki oyunculu sıfır toplamlı oyunlarda minimax değeri mevcuttur.
3.2. Doğrusal Programlama ile Minimax Çözümü
Maksimum en kötü durum kazancı doğrusal program olarak kurulabilir. Dual problem rakibin en iyi karma stratejisini temsil eder. Bu özel sınıfta doğrusal programlamayla denge hesaplamak mümkünken genel toplamlı oyunlarda aynı kolaylık geçerli değildir.
max[p∈Δₘ] min[j] ∑[i] pᵢAᵢⱼ = min[q∈Δₙ] max[i] ∑[j] Aᵢⱼqⱼ3.3. Primal-Dual Strateji Doğrulaması
Örnek ödeme matrisi için primal ve dual strateji dağılımları hesaplanıp beklenen faydalar karşılaştırılır. En kötü durum güvencesi ve olasılık toplamı ayrı test edilmelidir.
3.4. Sayısal ve Algoritmik Örnek
Yazı-tura eşleştirme oyununda bir oyuncu aynı sonucu, diğeri farklı sonucu ister. Saf strateji dengesi bulunmaz; iki oyuncunun da her iki eyleme ½ olasılık vermesi minimax dengesini oluşturur. Bu karışımın beklenen değeri uygun sıfır-toplam ölçeklemesinde sıfırdır.
3.5. Sıfır Toplamlı Oyunun Doğrusal Programı
Sonlu sıfır toplamlı iki oyunculu oyunda satır oyuncusu en düşük olası beklenen getiriyi en yükseğe çıkarır. Karma strateji olasılıkları negatif değildir ve toplamları birdir. Her sütun stratejisine karşı beklenen getiri, garanti edilen değerle sınırlandırılır; rakibin problemi dual doğrusal programa karşılık gelir. Minimax eşitliği nedeniyle bu iki programın optimumu aynı oyun değerini üretir. Bu özellik genel toplamlı oyunlara doğrudan genişletilemez.
max v; Aᵀp ≥ v·1; ∑ᵢpᵢ=1; pᵢ≥03.6. Eyer Noktası ve Karma Denge Ayrımı
Satır minimumlarının en büyüğü ile sütun maksimumlarının en küçüğü eşitse saf stratejili eyer noktası bulunur. Bu değerler farklıysa saf denge bulunmadığında karma strateji olasılıklarına geçilir. İki eylemli örneklerde karışım olasılıkları, rakibi destek eylemleri arasında kayıtsız bırakan doğrusal eşitliklerden hesaplanabilir. Çözümden sonra olasılıkların [0,1] aralığında olduğu ve rakibin kullanılmayan eylemlere sapmasının kazanç sağlamadığı kontrol edilir.
3.7. Karmaşıklık ve Sayısal Hassasiyet
Sıfır toplamlı oyunun doğrusal programlanabilirliği, genel toplamlı Nash dengesi hesaplamasından önemli ölçüde ayrılır. Çok büyük matrislerde tüm stratejileri açık üretmek pahalı olabilir; en iyi tepki oracle'ı kullanan yöntemler düşünülür. Fayda girdilerindeki küçük değişimler denge desteklerini değiştirebilir; yaklaşık çözümlerde beklenen fayda artıkları sayısal toleransla test edilmelidir.
3.8. Hesaplamalı Örnek ve Çözüm
Yazı-tura oyununda satır oyuncusunun getiri matrisi [[1,−1],[−1,1]] olsun. Her iki oyuncunun iki eylemi eşit olasılıkla seçmesi rakibini kayıtsız bırakır; oyunun beklenen değeri sıfırdır.
p=(½,½); q=(½,½); value=03.9. Bağımsız Doğrulama ve Gerçekleme Sınırları
Minimax doğrulaması her saf rakip eylemine karşı garantili beklenen getiriyi ve dual optimumu ayrı hesaplamalıdır.
Ünite 4: Nash Dengesi ve Karma Stratejiler
4.1. Tek Taraflı Sapmalar ve Denge Koşulu
Nash dengesi, hiçbir oyuncunun diğer stratejiler değişmeden tek taraflı sapmayla faydasını artıramadığı profildir. Saf denge her oyunda bulunmaz; sonlu oyunlarda karma strateji dengesi vardır. Bir karma stratejinin desteğinde bulunan her eylem, denge koşulunda aynı en yüksek beklenen faydayı vermelidir.
4.2. Karma Strateji Desteklerinin Hesaplanması
İki oyunculu küçük oyunlarda desteklerin enumerasyonu olası denge adaylarını üretir. Destek dışındaki eylemlerin daha iyi sonuç verip vermediği sonradan sınanır. Yaklaşık dengede pişmanlık üst sınırı hesaplanır; yalnız eşit pay-off tablosu denge kanıtı değildir.
uᵢ(sᵢ*, s₋ᵢ*) ≥ uᵢ(sᵢ, s₋ᵢ*) ∀i, sᵢ ∈ Sᵢ4.3. Yaklaşık Denge ve Sapma Kazancı
Denge sonucu birden fazla olabileceğinden algoritmanın tek çözüm üretmesi tüm denge kümesini bulduğu anlamına gelmez. Sayısal olasılıkların sıfıra yakın değerleri için tolerans tutarlı uygulanmalıdır.
4.4. Sayısal ve Algoritmik Örnek
İki eylemli bir oyunda oyuncunun karma stratejisi p olsun. Rakibin iki saf eylem karşısındaki beklenen faydaları eşitlenerek iç destekli çözüm aranır. Elde edilen p değeri [0,1] dışında ise varsayılan destek geçersizdir; uç stratejiler ayrıca denenir.
4.4.1. Açıklayıcı Sözde Kod
for support_1 in nonempty_subsets(Actions1):
for support_2 in nonempty_subsets(Actions2):
candidate = solve_indifference_equations(support_1, support_2)
if valid_probabilities(candidate) and no_profitable_deviation(candidate):
report_equilibrium(candidate)4.5. Destek Kümelerine Dayalı Denge Araması
Karma Nash dengesinde pozitif olasılıkla oynanan bütün eylemler oyuncuya aynı beklenen faydayı sağlamalıdır. Destek dışında kalan eylemler daha iyi getiri veremez. Destek numaralandırma algoritması olası pozitif eylem kümelerini seçer, kayıtsızlık denklemlerini çözer ve bütün sapma eşitsizliklerini test eder. Destek sayısı eylem sayısıyla üstel büyüdüğünden bu yöntem büyük oyunlarda hesaplama garantisi sağlamaz.
uᵢ(a,s₋ᵢ*) = vᵢ (a ∈ supp(sᵢ*)); uᵢ(b,s₋ᵢ*) ≤ vᵢ4.6. Denge Yaklaşıklığı ve Sapma Kazancı
Hesaplanan strateji profilinin dengeye uzaklığı, oyuncuların en iyi tek taraflı sapmayla kazanabileceği en büyük ek faydayla ölçülebilir. Bu ε-pişmanlık değeri küçükse ε-Nash dengesi elde edilir. Farklı oyunları kıyaslamak için fayda ölçeğinin normalize edilmesi gerekir; aksi hâlde aynı sayısal epsilon farklı önem taşır. Numune tabanlı beklenen fayda kestirimlerinde istatistiksel belirsizlik ayrıca raporlanmalıdır.
4.7. Birden Çok Dengenin Seçim Sorunu
Nash dengesi tek bir sonuç seçmeyi zorunlu kılmaz; aynı oyunda birden fazla denge bulunabilir. Dengeler verimlilik, adalet ve dayanıklılık bakımından farklı olabilir. Algoritmanın ilk bulduğu dengeyi “toplumsal optimum” diye sunmak yanlıştır. Çıktıda kullanılan denge seçimi ölçütü, sapma artığı ve sistem düzeyi amaç değeri ayrı alanlar olarak tutulmalıdır.
4.8. Hesaplamalı Örnek ve Çözüm
Koordinasyon oyununda eş eylemler ikişer, farklı eylemler sıfır fayda versin. İki saf dengeye ek olarak iki oyuncunun A ve B eylemlerini ½ olasılıkla karıştırdığı bir karma denge vardır.
P(A)=P(B)=½; E[u(A)]=E[u(B)]=14.9. Bağımsız Doğrulama ve Gerçekleme Sınırları
Karma denge doğrulamasında destek dışı eylemler bulunmadığı ve beklenen faydaların eşitliği ayrıca denetlenmelidir.
Ünite 5: Denge Hesaplama Algoritmaları ve Hesaplama Karmaşıklığı
5.1. PPAD ve Denge Probleminin Zorluğu
İki oyunculu genel toplamlı oyunlarda denge hesaplama, sıfır toplamlı oyunlardan farklı bir hesaplama problemidir. Lemke–Howson etiketli politoplar üzerinden tamamlayıcı pivot dizisi izler; bütün oyun sınıflarında polinom zamanda sonlanma garantisi sağlamaz. Denge hesaplama problemi PPAD karmaşıklık sınıfıyla ilişkilidir.
5.2. Lemke–Howson ve Grafiksel Oyunlar
Büyük oyunlarda tam ödeme matrisi tutmak yerine grafiksel oyunlar veya faktörize fayda temsilleri tercih edilebilir. Yapısal varsayımlar bulunmadığında bu gösterimler genel hesaplama zorluğunu ortadan kaldırmaz. Yaklaşık çözümler için sapma kazancı açık raporlanır.
ε(s) = max[i] max[a∈Sᵢ] [uᵢ(a, s₋ᵢ) − uᵢ(s)]5.3. Yaklaşım Hatası ve Sayısal Dejenerasyon
Algoritma sonuçları farklı başlangıç etiketlerinde ve dejenerasyon koşullarında test edilmelidir. Bütçe sınırında biten çözüm süreci, dengenin yokluğunu ispatlamaz.
5.4. Sayısal ve Algoritmik Örnek
Lemke–Howson iki matrisli oyunun dengesini tamamlayıcı etiketler üzerinden arar. Aynı oyun farklı başlangıç etiketleriyle farklı dengelere ulaşabilir. Her bulunan çözümde olasılıkların toplamı ve tek taraflı sapma kazançları bağımsız olarak kontrol edilmelidir.
5.5. PPAD ve Denge Hesaplama Sınırları
Genel toplamlı sonlu iki oyunculu oyunlarda karma Nash dengesinin varlığı, bu dengeyi polinom zamanda hesaplayan genel bir yöntem bulunduğu anlamına gelmez. İlgili denge bulma problemi PPAD-tamlık sonuçlarıyla ilişkilidir. Bu kuramsal durum, belirli oyun ailelerinde özel algoritmaların verimli olmasını dışlamaz. Kuramsal en kötü durum sınıfı, deneysel çözüm süresi ve yaklaşık çözümlerin hatası ayrı boyutlar olarak açıklanmalıdır.
ε(s) = maxᵢ maxₐ [uᵢ(a,s₋ᵢ) − uᵢ(s)]5.6. Lemke–Howson ve Etiketli Çokyüzlüler
İki oyunculu bimatriks oyununda Nash dengesi tamamlayıcı etiket koşullarıyla geometrik olarak temsil edilebilir. Lemke–Howson yöntemi bir etiketi geçici olarak bırakarak bitişik köşeler arasında pivot yapar. Yöntemin belirli başlangıç etiketleri ve dejenere durumlara duyarlılığı vardır; bütün dengeleri üretme veya polinom süre garantisi vermez. Küçük oyunlarda bağımsız destek numaralandırmayla çapraz doğrulama yapılabilir.
5.7. Yaklaşık Çözücülerde Hata Bütçesi
Sayısal doğrusal cebir toleransları, sonlu iterasyon ve örnekleme hatası aynı denge artığına katkıda bulunabilir. Tahmin edilmiş fayda değerleri kullanılırken sapma kazançlarının hatasını sınırlandırmadan kesin ε değerine güvenilemez. Çıktı olarak strateji olasılıkları, beklenen faydalar, oyuncu bazında en iyi sapmalar ve maksimum ε değeri sunulmalıdır. Dengenin hesaplanamaması ile ε eşiğinin karşılanamaması farklı durumdur.
5.8. Hesaplamalı Örnek ve Çözüm
Bir denge çözümünde oyuncuların en büyük tek taraflı kazançları sırasıyla 0,03 ve 0,05 olsun. Bu profil en çok ε=0,05 düzeyinde yaklaşık Nash dengesidir. Sayı, fayda normalizasyonuyla birlikte yorumlanmalıdır.
ε = max(0.03,0.05)=0.055.9. Bağımsız Doğrulama ve Gerçekleme Sınırları
Yakınsama ölçütü yalnız strateji olasılıklarının az değişmesi değildir; sapma faydaları da hesaplanmalıdır.
Ünite 6: Sıralı Oyunlar ve Alt Oyun Mükemmel Dengesi
6.1. Oyun Ağaçları ve Bilgi Kümeleri
Sıralı oyunlar karar noktaları, eylemler, bilgi kümeleri ve sonuçlardan oluşan oyun ağaçlarıyla gösterilir. Bilgi kümeleri hangi düğümlerin oyuncu tarafından ayırt edilemediğini belirtir. Tam bilgili sonlu oyunlarda geriye doğru indüksiyon alt oyun mükemmel dengeyi hesaplamak için kullanılabilir.
6.2. Geriye Doğru İndüksiyon ve Sequence Form
Büyük oyun ağaçlarında stratejik form her koşulda uygulanabilir değildir; strateji sayısı karar noktalarına göre üstel büyüyebilir. Sequence form, gerçekleşme planlarını ve akış kısıtlarını kullanarak iki oyunculu belirli oyunlarda daha kompakt gösterim sağlar.
a*(v) ∈ arg max[a∈A(v)] u[player(v)](a | v)6.3. Alt Oyun Doğrulaması
Alt oyun mükemmel denge hesabında eşit faydalı seçeneklerin çokluğu ve bilgi kümesinin alt oyun tanımına etkisi ayrıca incelenir. Sıralı gözlem yapısının yanlış kurulması geçersiz denge üretebilir.
6.4. Sayısal ve Algoritmik Örnek
Sıralı bir oyun ağacında son karar düğümünden başlayarak geçerli oyuncu en yüksek faydalı dalı seçer. Aynı düğümde iki oyuncunun amaçlarını tek skora toplamak stratejik modeli bozabilir. Alt oyun mükemmel denge her uygun alt oyunda rasyonel devam kararları gerektirir.
6.5. Oyun Ağaçları ve Bilgi Kümeleri
Sıralı oyunlarda düğümler karar zamanlarını, kenarlar eylemleri ve yapraklar faydaları gösterir. Bir oyuncunun ayırt edemediği karar düğümleri bilgi kümesinde birleştirilir; bu durumda strateji her bilgi kümesi için eylem seçimini belirtmelidir. Bütün düğümler gözleniyormuş gibi geriye doğru çözümleme yapmak, eksik bilgi içeren oyunlarda geçersiz sonuç üretebilir. Bilgi kümelerinde aynı oyuncuya ve aynı eylem seçeneklerine ilişkin tutarlılık denetlenmelidir.
V(h) = maxₐ V(h·a) (tek oyunculu karar düğümü)6.6. Geriye Doğru Çözümleme ve Alt Oyunlar
Tam bilgili sonlu oyunlarda geriye doğru çözümleme, son kararların en iyi tepkilerini hesaplayarak köke ilerler. Alt oyun mükemmel Nash dengesi, her uygun alt oyunda Nash dengesi olmayı gerektirir ve güvenilir olmayan tehditleri eler. Ancak bilgi kümesini kesen bir düğümden yeni alt oyun başlatılamaz. Hesaplama maliyeti ağacın açık düğüm sayısıyla ilişkili olduğundan ardışık uzun ufuklarda sıkıştırılmış durum gösterimi gereklidir.
6.7. Strateji Gösterimi ve Hafıza
Davranışsal strateji, her bilgi kümesinde eylemler üzerinde olasılık dağılımı tanımlar. Karma stratejiyse tam saf stratejiler üzerinde dağılımdır; bunların eşdeğerliği kusursuz hatırlama gibi koşullara bağlıdır. Yazılım gerçekleştiriminde bilgi kümesi anahtarlarının çakışmaması, terminal faydaların sabit sıralı oyuncu vektörüyle tutulması ve çözüm ağacının deterministik biçimde dolaşılması gerekir.
6.8. Hesaplamalı Örnek ve Çözüm
İlk oyuncu “giriş” veya “vazgeçme”, ikinci oyuncu girişten sonra “karşılık” seçsin. İkinci oyuncunun giriş sonrası tehdidi kendisine daha kötü sonuç veriyorsa geriye doğru çözümleme tehdidi dışlar.
SPNE: optimal action at every proper subgame6.9. Bağımsız Doğrulama ve Gerçekleme Sınırları
Oyun ağacı çözümünde karar düğümlerinin sahibi ve bilgi kümeleri doğru tutulmadan alt oyun tespiti yapılamaz.
Ünite 7: Bayesçi Oyunlar ve Eksik Bilgi
7.1. Tip Uzayları ve İnanç Dağılımları
Bayesçi oyunlarda oyuncuların özel tipleri ve bu tipler hakkında ortak veya oyuncuya özgü öncül inançlar bulunur. Strateji, yalnız gerçekleşen tipe değil o tip için seçilecek eyleme ilişkin bir fonksiyondur. Bayes–Nash dengesi, her tipin koşullu beklenen faydasını ençoklayan stratejiler kümesidir.
7.2. Koşullu Beklenen Fayda
Beklenen fayda, rakip tiplerin koşullu olasılıklarına göre ağırlıklandırılarak hesaplanır. Bağımsız tipler varsayımı belirtilmeden dağılımlar çarpılamaz. Öğrenilen inanç dağılımı veri yanlılığı veya eksik gözlem nedeniyle hatalı olabilir.
E[uᵢ | tᵢ,aᵢ] = ∑[t₋ᵢ] P(t₋ᵢ | tᵢ)uᵢ(aᵢ, s₋ᵢ(t₋ᵢ), t)7.3. Öncül Dağılımlara Duyarlılık
Duyarlılık testinde farklı öncül dağılımlar altında stratejiler ve olası denge değişimleri karşılaştırılır. Yanlış model bilgisi ile oyunun gerçek oyuncu davranışı arasında nedensel eşitlik kurulmaz.
7.4. Sayısal ve Algoritmik Örnek
İki olası özel tipe sahip oyuncuda karşı tarafın t₁ tipine olasılık 0.7, t₂ tipine 0.3 verilsin. Her eylemin beklenen faydası 0.7u(a,t₁)+0.3u(a,t₂) ile hesaplanır. Bu değerler tipler arasında bağımsızlık varsayılıyorsa ona göre koşullandırılmalıdır.
7.5. Türler, Önsel İnançlar ve Fayda Fonksiyonları
Bayesçi oyunda oyuncunun türü, tercihlerini veya özel bilgisini belirler; diğer oyuncular bu türü doğrudan gözlemlemeyebilir. Harsanyi dönüşümü başlangıçta doğanın türleri bir ortak olasılık modeline göre seçtiği gösterimi kullanır. Ortak önsel varsayımı her uygulamada geçerli değildir ve kullanıldığında açık belirtilmelidir. Tür, gözlem ve eylem alanlarını karıştırmak posterior hesaplarının yanlış koşullandırılmasına neden olur.
P(t₋ᵢ | tᵢ) = P(t₋ᵢ,tᵢ) / P(tᵢ)7.6. Bayes–Nash Dengesi
Strateji, her tür için bir eylem veya eylem dağılımı üretir. Bayes–Nash dengesinde oyuncunun her pozitif olasılıklı türü, diğer stratejiler ve kendi bilgi durumu altında beklenen faydasını ençoklar. Dengenin kontrolünde yalnız genel ortalama faydaya bakmak yeterli değildir; her tür için sapma analizi yapılır. Sıfır olasılıklı türlerde koşullu beklenti özel dikkat gerektirir.
7.7. Bayesçi Hesaplamada Senaryo Sayısı
Tür kümeleri çoğaldığında olası tür profillerinin kartezyen çarpımı hızla büyür. Tam numaralandırma yerine faktörleşmiş olasılık modelleri veya örnekleme kullanılabilir; fakat örnekleme tahmini kullanıldığında güven aralıkları gerekir. Tür dağılımını gözlenen veriyle tahmin etmek, stratejik denge modelinden ayrı istatistiksel bir problemdir. Veri sızıntısı veya yanlış prior, çok hassas denge tahminlerine yol açabilir.
7.8. Hesaplamalı Örnek ve Çözüm
Özel tür t₁ olasılığı 0,7, t₂ olasılığı 0,3 olsun. a eyleminin bu türlerde faydası 4 ve −2 ise beklenen fayda 2,2 olur. Alternatif eylem aynı bilgi koşullarında değerlendirilmelidir.
E[u(a)] = 0.7·4 + 0.3·(−2) = 2.27.9. Bağımsız Doğrulama ve Gerçekleme Sınırları
Posterior gerektiren durumlarda önsel beklentiyle koşullu beklenti karıştırılmamalıdır.
Ünite 8: Pişmanlık Minimizasyonu ve Strateji Öğrenme
8.1. Dış ve İç Pişmanlık
Çevrimiçi strateji seçiminde eylemler sıralı olarak uygulanır ve kayıp daha sonra gözlenebilir. Dış pişmanlık, geriye dönük en iyi sabit stratejiye göre birikimli kayıp farkıdır. Pişmanlık minimizasyonu tek başına her adımın Nash dengesi oluşturduğunu garanti etmez.
8.2. Çoklu Ağırlık Güncelleme Algoritmaları
Çoklu ağırlık güncelleme ve olasılık dağılımı güncelleme yöntemleri belirli kayıp sınırları altında alt doğrusal pişmanlık sağlayabilir. Tüm oyuncuların dış pişmanlığı azalırsa ampirik strateji dağılımının kaba korelasyonlu dengeye yakınsaması mümkündür; korelasyonlu denge için daha güçlü iç pişmanlık koşulları gerekir.
R(T) = ∑[t=1..T] ℓₜ(aₜ) − min[a] ∑[t=1..T] ℓₜ(a)8.3. Kümülatif Kayıp ve Yakınsama
Deneyde kümülatif kayıp, referans stratejinin kaybı ve normalize pişmanlık ayrı raporlanır. Rakibin uyarlanabilir davranışı, sabit çevre varsayımıyla karıştırılmaz.
8.4. Sayısal ve Algoritmik Örnek
Kayıp dizisi üzerinde en iyi sabit eylemin toplam kaybı 20, algoritmanın toplam kaybı 24 ise dış pişmanlık 4 tür. Ufuk uzunluğu 100 olduğunda ortalama pişmanlık 0.04 olur. Bu gözlem tek başına stratejilerin her turda Nash dengesine karşılık geldiğini göstermez.
8.4.1. Açıklayıcı Sözde Kod
weights = uniform_distribution(actions)
for round in horizon:
action = sample(weights)
observe_loss_vector_when_available()
weights = normalize(weights * exp(-eta * losses))
report_cumulative_regret()8.5. Dışsal Pişmanlık ve Rekabetçi Öğrenme
Tekrarlı karar vermede dışsal pişmanlık, öğrenicinin bir dizi eylemi seçmek yerine geriye dönük olarak en iyi tek sabit eylemi seçseydi elde edeceği farktır. Alt doğrusal toplam pişmanlık, ortalama pişmanlığın zamanla sıfıra yaklaşmasını sağlar. Buna rağmen tek tek her iterasyondaki stratejinin Nash dengesine yakın olduğu sonucu çıkmaz. Toplam kayıp ve per-round öğrenme hızı açıkça tanımlanmalıdır.
Rₜ = ∑ₜ ℓₜ(aₜ) − minₐ ∑ₜ ℓₜ(a)8.6. Ağırlıklı Çoğunluk ve Üstel Ağırlıklar
Hedge algoritması her eylemin ağırlığını gözlenen kayıplarla üstel olarak günceller. Tam bilgi durumunda bütün eylemlerin kayıpları gözlenirken çok kollu bandit probleminde yalnız seçilen eylemin kaybı elde edilir. Bandit geri bildirimi için önem ağırlıklı tahmin veya özel keşif politikası gerekir; tam bilgi güncellemesini eksik gözlemle doğrudan uygulamak yanlıştır. Öğrenme hızının büyük seçilmesi oynaklığı artırabilir.
8.7. Pişmanlık ve Korelasyonlu Denge
Oyuncuların deneysel oyun profillerinin zaman ortalaması, uygun pişmanlık özellikleri altında korelasyonlu veya kaba korelasyonlu denge kümesine yaklaşabilir. Dışsal pişmanlığın kaybolması genel olarak kaba korelasyonlu dengeyi, daha güçlü içsel veya swap pişmanlığı denetimi korelasyonlu dengeyi destekler. Bu ayrım Nash dengesiyle aynı değildir. Deneyde kullanılan ortalama profil, tek tur stratejileriyle karıştırılmamalıdır.
8.8. Hesaplamalı Örnek ve Çözüm
Yüz tur sonunda öğrenicinin toplam kaybı 70, geriye dönük en iyi sabit eylemin kaybı 60 olsun. Toplam dışsal pişmanlık 10, tur başına ortalama pişmanlık 0,1 olur.
R₁₀₀=70−60=10; R₁₀₀/100=0.18.9. Bağımsız Doğrulama ve Gerçekleme Sınırları
Bu ölçüm tek bir turun Nash dengesi olduğunu kanıtlamaz. Rastgele stratejilerde tekrarlar ve kayıp geri bildiriminin türü kaydedilmelidir.
Ünite 9: Grafiksel ve Potansiyel Oyunlar
9.1. Yerel Etkileşim ve Çizge Gösterimi
Grafiksel oyunlarda bir oyuncunun faydası yalnız komşu oyuncuların stratejilerine bağlı olabilir. Bu bağımlılık grafı veri boyutunu azaltır; fakat çizge yoğunluğu ve ağaç genişliği hesaplama maliyetini etkiler. Potansiyel oyunlarda tek taraflı fayda değişimleri bir potansiyel fonksiyon değişimiyle ilişkilendirilir.
9.2. Potansiyel Fonksiyonla En İyi Tepkiler
Sonlu tam potansiyel oyunlarında sıkı iyileştirme adımları sonlu sayıda aşamadan sonra saf dengeye ulaşır; bu özellik bütün genel toplamlı oyunlarda bulunmaz. Grafiksel oyunların ağaç yapısı belirli dinamik programlama yöntemlerine imkân verebilir.
Φ(aᵢ, s₋ᵢ) − Φ(s) = uᵢ(aᵢ, s₋ᵢ) − uᵢ(s)9.3. Sonlu İyileştirme Özelliği
Yerel fayda bağımlılıkları ve potansiyel değişimi örnek strateji geçişlerinde kontrol edilir. Uygulamada asenkron güncelleme ile eşzamanlı güncelleme aynı yakınsama garantilerine sahip değildir.
9.4. Sayısal ve Algoritmik Örnek
İki oyuncunun aynı bağlantıya yığılması halinde maliyet artıyor ve başka bağlantıya geçme kararı toplam maliyeti aynı miktarda azaltıyorsa bir potansiyel fonksiyon kurulabilir. Sonlu tam potansiyel oyununda asenkron sıkı iyileştirmeler sonlanır.
9.5. Potansiyel Fonksiyonu ve Sonlu İyileştirme Özelliği
Tam potansiyel oyunda tek taraflı strateji değişiminin oyuncu faydasına etkisi, skaler bir potansiyel fonksiyonunun değişimiyle aynıdır. Sonlu strateji uzayında her adımda kesin iyileştirme yapan dinamik potansiyeli tek yönlü değiştirdiğinden döngüye girmeden durur. Bununla birlikte kaç adımda duracağı üstel büyüklükte olabilir. Yaklaşık potansiyel oyunlarıyla tam potansiyel oyunları eşitlemek doğru değildir.
Φ(aᵢ,s₋ᵢ) − Φ(s) = uᵢ(aᵢ,s₋ᵢ) − uᵢ(s)9.6. Grafiksel Oyunlarda Yerel Bağımlılık
Grafiksel oyunlarda her oyuncunun faydası komşu oyuncuların eylemlerine bağlıdır. Bu gösterim tam ortak eylem uzayını saklamadan yerel faktörlerle hesaplama yapmayı sağlayabilir. Ancak yerel grafik yapısının bulunması, Nash dengesi bulmanın her ağda kolay olduğu anlamına gelmez. Ağın ağaç genişliği ve oyuncu eylem sayıları, mesaj geçirme veya dinamik programlamanın pratik maliyetini belirler.
9.7. Asenkron En İyi Tepki Güncellemeleri
Yük paylaşımında oyuncuların sırayla stratejilerini yenilemesiyle hepsinin eşzamanlı güncellenmesi farklı dinamikler üretir. Potansiyel fonksiyonu garantileri genellikle tek oyunculu iyileştirme adımına dayanır; aynı anda güncelleme bu yapıyı korumayabilir. Deneysel kıyaslamada güncelleme sırası, eşit faydalı eylemler için bağlama kuralı ve sonlandırma koşulu sabit tutulmalıdır. Durdurulan simülasyonun son profili ayrıca sapma testiyle değerlendirilmelidir.
9.8. Hesaplamalı Örnek ve Çözüm
Üç kullanıcı iki eş kaynak arasında bölünsün; kaynak maliyeti kullanıcı sayısıdır. (2,1) dağılımında kalabalık kaynaktaki bir kullanıcı diğerine geçtiğinde (1,2) olur ve kendi maliyeti yine 2 kalır; kesin iyileştirme gerçekleşmez.
load=(2,1); moving cost: 2→29.9. Bağımsız Doğrulama ve Gerçekleme Sınırları
Güncelleme kuralında yalnız kesin iyileştirme kabul ediliyorsa bağlama durumları döngü yaratmamalıdır.
Ünite 10: Ağ Oyunları ve Anarşinin Bedeli
10.1. Tıkanıklık Maliyetleri ve Toplumsal Amaç
Tıkanıklık oyununda kaynak maliyeti, kaynağı kullanan oyuncu sayısına veya toplam yüke bağlıdır. Bireysel en iyi seçim sistemin toplam gecikmesini en aza indirmeyebilir. Anarşinin bedeli, dengedeki toplumsal maliyetin en iyi mümkün maliyete oranıdır.
10.2. Wardrop Dengesi ve Ağ Akışları
Akış yönlendirmede Wardrop dengesi, kullanılan yolların marjinal kullanıcı açısından daha ucuz kullanılmayan bir alternatif sunmamasıyla karakterize edilir. Kullanıcı atomikliği ve gecikme fonksiyonunun biçimi PoA sınırlarını değiştirir.
PoA = max[s∈NE] C(s) / min[s∈ℱ] C(s)10.3. Anarşinin Bedeli Ölçütü
Ağ akışının toplam maliyeti, her kenarda yük çarpı gecikme toplamıyla hesaplanır. Sistem optimumu ile özçıkarcı denge aynı veri üzerinde bağımsız çözdürülür; oran en az bir olmalıdır.
10.4. Sayısal ve Algoritmik Örnek
İki paralel bağlantının gecikmeleri ℓ₁(x)=x ve ℓ₂(x)=1 olsun; toplam akış 1 olsun. Bireysel yönlendirme dengesi ile toplam xℓ₁(x)+(1−x)ℓ₂(1−x) maliyetini en aza indiren yönlendirme farklı olabilir. Denge ve optimum ayrı hesaplanmalıdır.
10.5. Tıkanıklık Oyunlarının Gecikme Modelleri
Ağ tıkanıklık oyununda bir kaynağın gecikmesi onu kullanan oyuncu sayısına veya sürekli akış miktarına bağlıdır. Oyuncular kendi yol gecikmesini en aza indirirken toplam ağ gecikmesi aynı tercihleri izlemeyebilir. Kaynak gecikmesinin azalmayan olması gibi varsayımlar belirli varlık ve verimlilik sonuçlarında önemlidir. Yol tabanlı bir oyuncu stratejisiyle kenar tabanlı maliyet hesabının tutarlılığı açıkça korunmalıdır.
C(f) = ∑ₑ fₑℓₑ(fₑ)10.6. Anarşinin Bedeli ve En Kötü Denge
Anarşinin bedeli, ilgili oyun ailesinde en kötü dengenin sosyal maliyetiyle merkezi optimum maliyetin oranını karşılaştırır. Maliyet minimizasyonunda oran genellikle en az birdir; sıfır optimum maliyet gibi ayrık durumlar özel tanım gerektirir. En iyi dengenin maliyetini karşılaştıran istikrar bedeli farklı bir ölçüttür. Doğrusal gecikmeli ağlara ilişkin özel sınırlar tüm gecikme fonksiyonlarına genellenmemelidir.
10.7. Wardrop Dengesi ve Sürekli Kullanıcı Akışı
Atomik oyunda her oyuncu kendi rotasını seçer; atomik olmayan akışta tek kullanıcının toplam akış üzerindeki etkisi ihmal edilir. Wardrop dengesinde kullanılan tüm yollar en küçük mevcut yol maliyetine sahiptir. Potansiyel optimizasyon biçimi belirli ayrışabilir gecikme modellerinde dengeyi bulabilir. Ancak denge koşullarıyla sistem optimumunun ilk mertebe koşulları farklıdır; marjinal dışsallık maliyetinin dahil edilmesi bu farkı açıklar.
10.8. Hesaplamalı Örnek ve Çözüm
Pigou ağında bir yolun gecikmesi x, diğer yolunki 1 ve toplam akış 1 olsun. Wardrop dengesinde bütün akış x gecikmeli yolu seçebilir; toplam maliyet 1 olur. Sistem optimumunda x=½ ile maliyet ¾ elde edilir.
PoA = 1/(¾) = 4/310.9. Bağımsız Doğrulama ve Gerçekleme Sınırları
Anarşinin bedeli hesabında maliyetler, aynı toplam talep ve aynı uygulanabilir yol kümesi üzerinde karşılaştırılmalıdır.
Ünite 11: Mekanizma Tasarımı ve Açık Artırma Algoritmaları
11.1. Teşvik Uyumluluğu ve Tahsis Kuralları
Mekanizma tasarımı, oyuncuların özel bilgilerini ve teşviklerini dikkate alarak sonuç ve ödeme kurallarını belirler. Doğru bildirim teşvik uyumluluğu, oyuncunun gerçek değerini açıklamasının uygun karşılaştırma stratejilerine göre en iyi tercih olmasını gerektirir.
11.2. VCG ve Hesaplamalı Açık Artırmalar
Tek parametreli ortamlarda monoton tahsis kuralları ve uygun ödeme formülleri önemli yapı taşlarıdır. VCG mekanizması belirli yarı-doğrusal fayda ve transfer varsayımları altında etkinliği ve doğruluğu sağlayabilir; hesaplama maliyeti ve bütçe dengesi kendiliğinden sağlanmaz.
uᵢ = vᵢ(x) − pᵢ; x ∈ arg max[x∈ℱ] ∑[j] v̂ⱼ(x)11.3. Doğru Bildirimin Denetlenmesi
Her teklif profili için tahsis uygulanabilirliği kontrol edilir. Teklif değiştiren oyuncunun kazancındaki farkla doğruluk koşulu sınanır; ödeme işareti ve para transferlerinin yönü açık tanımlanır.
11.4. Sayısal ve Algoritmik Örnek
Tek bir kaynak iki adaydan birine verildiğinde ödeme kuralı adayın bildirdiği değerden bağımsız rekabet etkisiyle ilişkilendirilebilir. Tahsis ve ödeme kuralının birlikte tanımlanması gerekir; yalnız en yüksek teklifin kazanması doğruluk garantisi vermez.
11.5. Doğrudan Açıklama ve Teşvik Uyumluluğu
Mekanizma tasarımı, oyuncuların özel değer veya tercihlerini bildirdikleri kuralları ve bu bildirimlerden doğan sonuçları inceler. Doğru bildirmenin baskın strateji olması, oyuncunun diğer bildiriler ne olursa olsun yanlış bildirimle daha iyi sonuç elde edememesi demektir. Bu koşul sosyal fayda ençoklama koşulundan ayrıdır. Ödeme fonksiyonu, tahsis fonksiyonu ve oyuncuların rezervasyon değerleri birlikte modellenmelidir.
uᵢ(vᵢ; bᵢ,b₋ᵢ) ≥ uᵢ(vᵢ; b′ᵢ,b₋ᵢ)11.6. VCG Ödemeleri ve Dışsallık
Vickrey–Clarke–Groves mekanizmalarında tahsis bildirilen toplam değeri ençoklar; ödeme kuralı oyuncunun diğer oyuncular üzerindeki dışsallığını temel alır. Uygun varsayımlarda doğru bildirim baskın stratejidir. Ancak VCG otomatik olarak bütçe dengesi, danışıklılığa dayanıklılık veya pratik çözüm kolaylığı garanti etmez. Dağıtık kaynak atamada tahsis optimizasyonunun hesaplama zorluğu, ödeme hesapları için ek çözüm çağrıları gerektirebilir.
11.7. Tek Parametreli Açık Artırmalarda Monotonluk
Tek parametreli tahsis problemlerinde bir oyuncunun beyanını artırması kendisine verilen miktarı azaltmıyorsa monotonluk koşulu sağlanabilir. Uygun eşik ödeme tasarımıyla teşvik uyumluluğu elde edilebilir. Bu sonuç çok parametreli mekanizmalara doğrudan taşınmaz. Sayısal simülasyonda oyuncu beyanı değiştirilerek hem tahsis monotonluğu hem fayda sapmaları bağımsız test edilmelidir.
11.8. Hesaplamalı Örnek ve Çözüm
Tek nesneli ikinci fiyat açık artırmada teklifler 9, 6 ve 4 olsun. En yüksek teklif sahibi nesneyi alır ve ikinci en yüksek teklif 6 kadar ödeme yapar. Kazananın gerçek değeri 9 ise faydası 3 olur.
payment=6; utility=9−6=311.9. Bağımsız Doğrulama ve Gerçekleme Sınırları
Doğru bildirim baskın strateji sonucunun risk nötrlüğü, tek parametreli değer ve uygun teklif kurallarıyla ilişkisi belirtilmelidir.
Ünite 12: Çok Etmenli Karar Algoritmaları ve Denge Doğrulaması
12.1. Stokastik Oyunlar ve Ortak Durumlar
Çok etmenli sistemler ortak kaynakları kullanan veya birbirinin kararından etkilenen yazılım ajanlarından oluşabilir. Sadece tek etmenli Markov karar süreci çözücüsünü her ajan için çalıştırmak etkileşimin stratejik niteliğini ortadan kaldırmaz. Durum, eşzamanlı eylemler ve geçiş dağılımı birlikte tanımlanır.
12.2. Çok Etmenli Öğrenme Mimarileri
Stokastik oyunlarda her ajan için ödül fonksiyonu ile geçiş modeli ayrıdır. Öğrenen ajanların birbirlerinin politikasını değiştirmesi durağan çevre varsayımını bozabilir. Koordinasyon için merkezi öğrenme ve dağıtık karar verme ayrımı yöntemsel olarak önemlidir.
Qᵢ⁽π⁾(s,a) = rᵢ(s,a) + γ∑[s′] P(s′ | s,a)Vᵢ⁽π⁾(s′)12.3. Politika Değerlendirmesi ve Denge Hatası
Denge doğrulaması için örneklemeden tahmin edilen sapma kazançları belirsizlik aralıklarıyla sunulur. Eğitim ödülü artışı, Nash veya Pareto optimalite kanıtı olarak yorumlanmaz.
12.4. Sayısal ve Algoritmik Örnek
İki öğrenen ajan aynı anda politika güncelliyorsa her ajan açısından çevre dağılımı değişir. Tek etmenli yakınsama ispatı doğrudan geçerli olmayabilir. Öğrenilen politikalarda belirli karşıt eylemlerin getirisi ölçülerek sapma kazancı kestirilir.
12.5. Stokastik Oyunlarda Durum ve Ortak Eylem
Stokastik oyunda birden fazla oyuncu aynı anda veya sıralı karar verir; durum geçiş olasılıkları ortak eylemlere bağlıdır. Her oyuncunun ödül fonksiyonu farklı olabilir. Tek etmenli Markov karar sürecindeki Bellman optimizasyonu doğrudan çok oyunculu Nash koşullarının yerini tutmaz. Durum uzayının büyümesi ve ortak eylem çarpımı çok etmenli hesaplamayı pahalı hâle getirir.
Qᵢ(s,a) = rᵢ(s,a) + γ∑ₛ′P(s′|s,a)Vᵢ(s′)12.6. Çok Etmenli Öğrenmede Durağan Olmama
Bağımsız öğrenen ajanlar aynı çevrede politika güncellediğinde her ajan için görülen çevre dağılımı zamanla değişir. Bu nedenle tek etmenli kararlı geçiş varsayımı bozulabilir. Merkezi eğitim ve dağıtık yürütme, ortak durum bilgisinin eğitimde kullanılabildiği fakat uygulamada ajanların yerel gözlemlerle hareket ettiği yapılardan biridir. Eğitim getirisi yüksek olsa bile kararlı strateji veya Nash denge garantisi ayrıca kanıtlanmalıdır.
12.7. Strateji Dayanıklılığı ve Karşı Oyuncu Değişimi
Bir politikanın tek bir rakip stratejisine karşı başarılı olması, farklı rakiplere karşı sağlam olduğu anlamına gelmez. Değerlendirme, sabit karşı oyuncu havuzu, dağılım dışı stratejiler, en iyi tepki ile sömürülebilirlik testi ve rastgele tohumlar üzerinden yürütülebilir. Ortalama ödül, en kötü durum faydası ve sapma kazancı ayrı raporlanmalıdır. Simülasyondaki gözlem gecikmesi ile gerçek sistemdeki eşzamanlı eylem modeli de uyuşmalıdır.
12.8. Hesaplamalı Örnek ve Çözüm
İki durumlu bir stokastik oyunda eylem çifti hem anlık faydayı hem sonraki duruma geçiş olasılığını belirlesin. Tek oyuncunun seçtiği eylem sabit rakip politikasına göre uygun görünürken rakip politikasını değiştirdiğinde değer hesabı farklılaşır.
Vᵢ(s) = E[∑ₜ≥0 γᵗrᵢ,t | s]12.9. Bağımsız Doğrulama ve Gerçekleme Sınırları
Denetimde rakip politika sürümü, iskonto katsayısı ve durum geçiş örneklem büyüklüğü korunur.
Kaynakça
- Nisan, Noam; Roughgarden, Tim; Tardos, Éva; Vazirani, Vijay V. (eds.). Algorithmic Game Theory. Cambridge University Press, 2007. ISBN 9780521872829.
