Bölüm 3: Nash Dengesi

3.1Temeller

Bu bölümün bütün kavramları tek bir sorunun etrafında döner: birden çok karar vericinin kararları birbirine bağlıysa, “makul” bir sonuç nedir? Önce küçük bir oyunla soruyu somutlaştırıyoruz, sonra kavramı günlük bir durum üzerinden sezdirip biçimsel tanıma geçiyoruz.

3.1.1Bir oyunla başlangıç: Mahkûmun İkilemi

Sam ve John adlı iki zanlı ayrı odalarda sorgulanır. Her biri, ötekinin ne yaptığını bilmeden iki seçenekten birini seçer: Sessiz kalmak ya da ötekine İhanet etmek. İkisi de sessiz kalırsa yetersiz delil yüzünden birer yıl yatarlar. İkisi de ihanet ederse ikişer yıl yatarlar. Biri ihanet edip öteki sessiz kalırsa ihanet eden serbest kalır, sessiz kalan üç yıl yatar.

Oyun kuramında bir oyunun sonuçları kazanç (payoff) olarak yazılır ve her oyuncu kendi kazancını büyütmek ister. Hapis yılı ise kötü bir şeydir: az olması iyidir. Bu iki bakışı uzlaştırmak için kazanç, hapis yılının eksi işaretlisi olarak tanımlanır: 1 yıl hapis −1 kazanç, 3 yıl hapis −3 kazanç demektir. Böylece “büyük sayı iyidir” kuralı her yerde geçerli kalır; −1, −3'ten büyüktür.

Oyunu bir kazanç matrisi (payoff matrix) ile yazmak gelenektir. Satırlar bir oyuncunun (burada Sam'in), sütunlar ötekinin (John'un) seçenekleridir. Her hücrede iki sayı vardır: önce satır oyuncusunun, sonra sütun oyuncusunun kazancı. Bu sıralama bütün not boyunca değişmez.

Tabloyu okumak bu bölümün en temel becerisidir. Örneğin sağ üst hücre (Sessiz, İhanet) = (−3, 0) şunu söyler: Sam sessiz kaldı, John ihanet etti; Sam 3 yıl yatar (kazancı −3), John serbest kalır (kazancı 0). Sam yalnızca satırı seçebilir, hangi hücreye düşüleceğini John'un sütunu belirler. Bu, oyunu tek kişilik bir karar probleminden ayıran şeydir.

Sam'in yerine geçip düşünelim. John'un ne yapacağı bilinmiyor. John sessiz kalırsa Sam'in seçeneği −1 (sessiz) ile 0 (ihanet) arasındadır; ihanet daha iyidir. John ihanet ederse seçenek −3 (sessiz) ile −2 (ihanet) arasındadır; yine ihanet daha iyidir. Demek ki John ne yaparsa yapsın Sam için ihanet daha iyidir. Aynı akıl yürütme John için de geçerlidir, çünkü oyun simetriktir. Sonuçta ikisi de ihanet eder ve ikişer yıl yatarlar. Oysa ikisi de sessiz kalsaydı yalnız birer yıl yatacaklardı. Bireysel olarak akıllıca olan seçimlerin herkes için kötü bir sonuç doğurması, oyunun “ikilem” adını almasının nedenidir.

Aynı oyun tekrarlandığında tablo değişir. Bilgisayara karşı oynanan sürümde bilgisayar Tit-for-Tat stratejisini kullanabilir: ilk turda sessiz kalır, sonraki her turda karşısındakinin bir önceki turdaki seçimini kopyalar. Böyle bir rakibe karşı on turda en az kaç yıl birikebileceği sorusu, ihanetin “sonraki turda cezalandırılması” fikrine dayanır; bu soru 3.3.2'de hesaplanır.

3.1.2John Nash ve kavramın kökeni

Kavram adını Amerikalı matematikçi John Forbes Nash Jr.'dan (1928–2015) alır. Nash, 1950'de Princeton'da Non-Cooperative Games (İşbirliksiz Oyunlar) adlı kısa bir doktora tezi yazdı. Aynı yıl PNAS dergisinde iki sayfalık bir not yayımladı; bu notta her sonlu oyunun bir denge noktası olduğunu ispatladı (Nash, 1950). Tezin genişletilmiş hâli ertesi yıl Annals of Mathematics'te çıktı (Nash, 1951).

Nash'ten önce oyun kuramının en güçlü sonucu, John von Neumann'ın 1928'de iki kişilik sıfır toplamlı oyunlar (zero-sum game) için kurduğu minimaks kuramıydı (von Neumann, 1928). Sıfır toplamlı oyunda birinin kazancı ötekinin kaybıdır; çıkarlar tam olarak zıttır. Gerçek hayattaki etkileşimlerin çoğu böyle değildir: Mahkûmun İkilemi'nde iki oyuncu da (Sessiz, Sessiz) sonucunu (İhanet, İhanet) sonucuna tercih eder, yani çıkarlar kısmen ortaktır. Nash'in katkısı, denge fikrini n kişilik genel (sıfır toplamlı olmayan) oyunlara taşımasıdır.

Nash bu çalışmalarıyla 1994'te John Harsanyi ve Reinhard Selten ile birlikte Nobel Ekonomi Ödülü'nü aldı. 2015'te kısmi diferansiyel denklemlere katkıları için Abel Ödülü'ne layık görüldü. Hayatı A Beautiful Mind (2001) filmine konu oldu.

3.1.3Stratejik davranış ve uygulama alanları

Oyun kuramının temel varsayımı, oyuncuların kendi kazançlarını maksimize etmeye çalıştığıdır. Bu tek başına yeni bir şey değildir; tek kişilik karar kuramı da aynı varsayımla çalışır. Yeni olan, herkesin kazancının ötekilerin seçimine de bağlı olmasıdır. Bir oyuncu en iyi seçimini yapmak için ötekilerin ne yapacağını tahmin etmelidir; ötekiler de onun ne yapacağını tahmin eder. Buna stratejik davranış denir.

Stratejik bağımlılık çok farklı alanlarda karşımıza çıkar. Aşağıdaki tablo bu bölümde ve sonraki konularda sık geçen örnekleri ve yapılarını özetler.

Bu örneklerin ortak noktası şudur: hiçbirinde “en iyi seçim” rakipten bağımsız olarak söylenemez. Penaltıda kaleci hep sola atlarsa atıcı sağa vurur; atıcı hep sağa vurursa kaleci sağa atlar. Standart seçiminde doğru teknoloji, ötekilerin seçtiği teknolojidir. Bilgisayar ağlarında bir cihazın paket göndermesinin iyi olup olmadığı, ötekilerin aynı anda gönderip göndermediğine bağlıdır. Bu yüzden tek tek oyuncuların en iyi seçimi yerine, seçimlerin bir arada tutarlı olduğu durumları aramak gerekir.

3.1.4Kimsenin pişman olmadığı durum

Biçimsel tanımdan önce kavramı gündelik bir örnekle düşünelim. Yemekhanede iki kasa vardır ve öğrenciler kuyruklara dağılmıştır. Herkes daha kısa beklemek ister ve kuyruk değiştirmek serbesttir. Şekil 3.1'de iki durum görülür.

Kuyruklar 7 ve 3 kişiyse uzun kuyruğun sonundaki öğrenci öteki kasaya geçerek 7. sıra yerine 4. sıraya gelir. Geçmesi kârlıdır, dolayısıyla bu durum kalıcı değildir: biri mutlaka yer değiştirir. Kuyruklar 5 ve 5 kişiyse kim geçerse geçsin öteki kuyruğun 6. sırasına düşer, yani daha geriye gider. Kimsenin yer değiştirmek için nedeni yoktur; durum kendi kendini sürdürür.

Bu gözlem bir test olarak yazılabilir. Buna pişmanlık testi diyelim: “Ötekilerin ne yaptığını görseydim, kendi seçimimi değiştirir miydim?” Bu soruya herkesin cevabı “hayır” ise durum bir Nash dengesidir. Testin iki önemli özelliği vardır. Birincisi, her oyuncu yalnız kendi seçimini değiştirmeyi düşünür; ötekilerin seçimi sabit kabul edilir. İkincisi, test her oyuncu için ayrı ayrı yapılır; bir kişinin bile cevabı “evet” ise durum denge değildir.

Denge kendi kendini sürdüren bir durumdur: herkes ötekilerin davranışını doğru bekler ve buna göre elinden gelenin en iyisini yapar. Ancak denge “en iyi sonuç” ya da “adil sonuç” anlamına gelmez. Mahkûmun İkilemi'nde (İhanet, İhanet) pişmanlık testini geçer, ama iki oyuncu da (Sessiz, Sessiz) sonucunu tercih ederdi. Denge bir kararlılık kavramıdır, bir değerlendirme kavramı değildir.

3.1.5Biçimsel tanım

Pişmanlık testini kesin bir dille yazmak için önce oyunun kendisini kesin bir dille yazmak gerekir. Aşağıdaki gösterim bütün bölüm boyunca kullanılır.

Mahkûmun İkilemi'nde N = {Sam, John}, her iki oyuncu için S_i = {Sessiz, İhanet}'tir. Dört strateji profili vardır ve her biri tablonun bir hücresidir. Örneğin s = (Sessiz, İhanet) için u_Sam(s) = −3 ve u_John(s) = 0'dır. Sam açısından bakınca s_−Sam yalnızca John'un stratejisidir.

s_−i gösterimi ilk bakışta garip gelebilir. Sebebi şudur: oyuncu i bir karar verirken ötekilerin seçimini tek bir paket olarak düşünür. İki kişilik oyunda bu paket tek bir stratejidir; üç kişilik oyunda iki stratejiden oluşan bir listedir. Gösterim, oyuncu sayısı ne olursa olsun aynı kalır.

Eşitsizliğin sol tarafı, oyuncunun dengedeki kazancıdır. Sağ taraf, oyuncu kendi stratejisini s_i'ye değiştirdiğinde ve ötekiler yerinde kaldığında alacağı kazançtır. Bu tür bir değişikliğe tek taraflı sapma (unilateral deviation) denir. Tanım, hiçbir tek taraflı sapmanın kârlı olmadığını söyler. “≥” işaretine dikkat edilmelidir: sapma kazancı eşit bırakabilir, yalnız artıramaz.

Tanımın üç yorumu vardır ve üçü de aynı şeyi farklı açıdan anlatır:

• Tek taraflı sapma: Diğerleri sabitken hiçbir oyuncu stratejisini değiştirerek kazancını artıramaz.
• Kendini doğrulayan anlaşma: Oyuncular önceden bir profilde anlaştıysa ve herkes ötekilerin anlaşmaya uyacağına inanıyorsa, kendisi de uyar. Anlaşmanın uygulanması için dışarıdan bir zorlama gerekmez.
• Kararlılık verimlilik değildir: Denge, adalet ya da verimlilik garantisi vermez. Özellikle bir denge Pareto optimal olmak zorunda değildir. Bir sonuç, herkesi en az onun kadar iyi ve en az birini kesin daha iyi yapan başka bir sonuç yoksa Pareto optimaldir.

Dört hücreyi tek tek denetlemek küçük bir oyunda kolaydır. Oyun büyüdükçe bu yöntem yorucu hâle gelir. 3.2'deki en iyi tepki işaretlemesi aynı denetimi düzenli bir biçimde yapar.

3.1.6Tanımla ilgili yanılgılar

Nash dengesinin tanımı kısa olduğu için yanlış okunmaya açıktır. Aşağıdaki yanılgılar öğrencilerin en sık düştüğü tuzaklardır. Her birinin neden yanlış olduğu, tanımdaki bir sözcüğe dayanır.

3.2En iyi tepki

Nash dengesinin tanımı her profil için “sapma kârlı mı?” sorusunu sorar. Bu soruyu düzenli biçimde cevaplamanın yolu, her oyuncunun ötekilerin her olası seçimine karşı en iyi cevabını önceden bulmaktır. Bu cevaba en iyi tepki denir. Dengeyi bulmak, en iyi tepkilerin çakıştığı yeri bulmaya dönüşür.

3.2.1En iyi tepki ve karşılıklı en iyi tepki

En iyi tepkinin arkasındaki soru basittir: “Rakibin ne yapacağını bilseydim ne yapardım?” Rakibin seçimi sabitlenir, oyuncu yalnız kendi kazançlarına bakar ve en büyüğünü veren seçeneği alır.

Bunu yazmak için argmax gösterimi kullanılır. max bir listedeki en büyük değeri verir; argmax ise bu en büyük değeri veren seçeneği (ya da seçenekleri) verir. Örneğin dört seçeneğin kazançları A: 3, B: 7, C: 2, D: 7 ise max = 7'dir, ama argmax = {B, D}'dir. En büyük değer birden çok seçenekte görülüyorsa argmax bir kümedir; bu ayrıntı eşitlikli oyunlarda önem kazanır.

En iyi tepki bir sabit değildir; rakibin seçimine bağlı bir kuraldır. Rakip değişince en iyi tepki de değişebilir. BR_i'yi “rakibin her seçimine karşı ne yapacağımı söyleyen tablo” olarak düşünmek yararlıdır. Bu kurala en iyi tepki eşlemesi (best-response correspondence) de denir. “Eşleme” sözcüğü, bir girdiye birden çok çıktı (eşitlik durumunda bir küme) atanabildiğini vurgular.

Nash dengesinin tanımındaki eşitsizlik, s_i*'ın s_−i*'a karşı en büyük kazancı verdiğini söyler. Bu, s_i*'ın bir en iyi tepki olması demektir. Aşağıdaki teorem bu gözlemi kesinleştirir.

Teorem, dengeyi bulmak için pratik bir yöntem verir. İki kişilik bir matris oyununda üç adım yeterlidir:

1. Satır oyuncusu: Her sütunda, satır oyuncusunun en büyük kazancı (hücredeki ilk sayı, u₁) işaretlenir. Sütun sabit tutulduğu için bu, sütun oyuncusunun o seçimine karşı satır oyuncusunun en iyi tepkisidir.
2. Sütun oyuncusu: Her satırda, sütun oyuncusunun en büyük kazancı (ikinci sayı, u₂) işaretlenir.
3. Kesişim: İki kazancı da işaretli hücreler saf strateji Nash dengeleridir.

Yöntemin maliyeti küçüktür. m × n bir matriste her hücre bir sütun maksimumu ve bir satır maksimumuyla karşılaştırılır. Sütun maksimumları ve satır maksimumları bir kez hesaplanırsa toplam iş O(mn) olur; yani matristeki hücre sayısıyla orantılıdır. Matris zaten verildiyse bundan daha hızlı bir yöntem olamaz, çünkü her hücreye en az bir kez bakmak gerekir.

3.2.2İşaretleme yöntemi: Mahkûmun İkilemi

Yöntemi önce tanıdık oyunda deneyelim. Kazançlar hapis yılının eksi işaretlisidir (−1 = 1 yıl) ve her oyuncu kendi sayısını büyütmek ister. Hücrelere a, b, c, d harfleri verelim: a = (Sessiz, Sessiz), b = (Sessiz, İhanet), c = (İhanet, Sessiz), d = (İhanet, İhanet).

Şekil 3.2'de işaretlemenin son hâli görülür. Her oyuncunun iki işareti de İhanet satırında ya da sütunundadır. Bu, İhanet'in iki oyuncu için de baskın strateji olduğunu gösterir. Baskın stratejisi olan bir oyuncunun rakibini tahmin etmesine gerek yoktur; bu durum oyunu özellikle kolay çözülür kılar.

3.2.3Üçe üç bir örnek

Baskın strateji her oyunda bulunmaz. Aşağıdaki oyunda satır oyuncusu A, B, C; sütun oyuncusu X, Y, Z stratejilerinden birini seçer. Hücrede (u₁, u₂) yazılıdır: önce satır, sonra sütun oyuncusunun kazancı.

Bu örnekte iki önemli gözlem vardır. Birincisi, (C, Z) hücresinde satır oyuncusunun 3'ü işaretlidir ama sütun oyuncusu Z yerine X'e geçerek 2 yerine 4 alır. Tek işaret yetmez. İkincisi, “en büyük sayılar” dengeyi belirlemez: (C, X)'teki 4 de sütun oyuncusu için tablodaki en büyük kazançlardan biridir, ama satır oyuncusu orada A'ya geçmek ister. Denge, sayıları büyük olan hücre değil, karşılıklı en iyi tepki olan hücredir.

Oyunun iki dengesi olması da dikkat çekicidir. Kuram hangi dengenin oynanacağını tek başına söylemez. Satır oyuncusu (A, X)'i (4 alır), sütun oyuncusu ise iki dengede de 3 alır. Birden çok denge olduğunda hangisinin seçileceği sorusu 3.5'te ayrıca ele alınır.

3.2.4Eşitlik olduğunda: dil seçimi oyunu

İşaretleme yöntemi eşitlik olduğunda bir incelik gerektirir. Ayşe ve Bora ortak bir proje için programlama dili seçiyor: Python, Java ya da C. Hücrede (Ayşe, Bora) kazancı vardır; Ayşe satır, Bora sütun oyuncusudur. Kural aynıdır: Ayşe için her sütunda ilk sayıların, Bora için her satırda ikinci sayıların en büyüğünün altı çizilir. Bu yüzden yönteme altını çizme yöntemi de denir.

Eşitlik durumunda yalnız birini işaretlemek sık yapılan bir hatadır. Bu örnekte o hata zararsız görünebilir; ama başka bir oyunda eşit kazançlı hücrelerden biri tam olarak dengenin bulunduğu hücre olabilir ve tek işaret o dengeyi gözden kaçırır. Kural nettir: en büyük değer birden çok kez görülüyorsa hepsi işaretlenir.

Bu oyun, 3.3'te anlatılan baskın strateji elemesiyle de incelenebilir. Bora için Java, C'yi her satırda kesin olarak yener (1 > 0, 4 > 2, 2 > 1), bu yüzden C sütunu silinebilir. Geriye kalan iki sütunda Ayşe için Python, C'yi yener (4 > 1, 1 > 0) ve C satırı da silinir. Kalan 2 × 2 oyunda hiçbir strateji baskılanmaz; iki denge birlikte kalır. Yani eleme oyunu küçültür ama çözmez; altını çizme ise iki dengeyi doğrudan bulur. Oyunun ayrıca bir karışık dengesi de vardır (Ayşe Python'u 3/4, Bora Python'u 1/5 olasılıkla seçer); bu tür dengeler 3.4'te hesaplanır.

3.2.5İşaretlemede sık hatalar

İşaretleme mekanik bir yöntemdir, ama hangi sayının hangi yönde karşılaştırılacağı karıştırılabilir. Şekil 3.5'te doğru yönler gösterilmiştir: satır oyuncusu yalnız satırını değiştirebildiği için kendi seçeneklerini aynı sütun içinde karşılaştırır; sütun oyuncusu ise aynı satır içinde karşılaştırır.

3.2.6Üç oyuncu: grup ödevi oyunu

Tanım iki oyuncuyla sınırlı değildir. Üç öğrenci bir grup ödevi için aynı anda Katıl ya da Katılma der. En az iki kişi katılırsa ödev başarılı olur ve herkes (katılan da katılmayan da) 3 puan alır. Katılmanın kişisel maliyeti 1'dir. Üç oyuncu ve ikişer strateji olduğu için 2 × 2 × 2 = 8 profil vardır. Oyun simetrik olduğu için profilleri katılan sayısına (k) göre gruplamak yeterlidir.

Oyunun dört saf dengesi vardır: tam iki kişinin katıldığı üç profil ve kimsenin katılmadığı profil. Test, n oyunculu oyunda da aynıdır: her oyuncu için, ötekiler sabitken. Üç oyunculu bir oyunda bile tek bir “matris” çizilemez; ama tanım hiç değişmez.

“Kimse katılmaz” dengesi ilginçtir. Herkes 0 alır, oysa iki kişi katılsa katılanlar 2, katılmayan 3 alırdı. Kimse bu dengeyi tek başına bozamaz, çünkü tek başına katılan ödevi kurtaramaz ve −1 alır. Bu duruma koordinasyon başarısızlığı denir. İki öğrencinin birlikte katılmaya karar vermesi durumu düzeltirdi; ama birlikte sapmak Nash tanımının dışındadır. Bu yüzden Nash dengesi bazen kötü bir durumda “sıkışıp kalmayı” da açıklar.

3.2.7Kod izleme: saf_nash()

İşaretleme yöntemi kısa bir Python fonksiyonuyla yazılabilir. Fonksiyon, satır oyuncusunun kazanç matrisi U1 ile sütun oyuncusunun kazanç matrisi U2'yi alır ve saf dengelerin (satır, sütun) indislerini döndürür.

def saf_nash(U1, U2):
    m, n, denge = len(U1), len(U1[0]), []
    for i in range(m):
        for j in range(n):
            br1 = max(U1[k][j] for k in range(m))
            br2 = max(U2[i][l] for l in range(n))
            if U1[i][j] == br1 and U2[i][j] == br2:
                denge.append((i, j))
    return denge

Kod satır satır şöyle çalışır:

• m satır sayısı, n sütun sayısıdır; denge boş bir listedir.
• İki iç içe döngü bütün hücreleri dolaşır: i satır, j sütun indisidir.
• br1, j sütunundaki en büyük U1 değeridir. Satır oyuncusunun bu sütuna karşı alabileceği en iyi kazanç budur.
• br2, i satırındaki en büyük U2 değeridir. Sütun oyuncusunun bu satıra karşı alabileceği en iyi kazanç budur.
• Hücredeki iki kazanç da kendi maksimumuna eşitse (iki işaret de varsa) hücre listeye eklenir. Eşitlik (==) kullanıldığı için eşit en büyük değerlerin hepsi kabul edilir; eşitlik sorunu kendiliğinden çözülür.

Tablo 3.3'teki oyun için U1 = [[4, 0, 1], [2, 3, 0], [1, 2, 3]] ve U2 = [[3, 2, 1], [1, 3, 2], [4, 0, 2]]'dir; indis 0, 1, 2 sırasıyla A, B, C (ya da X, Y, Z) demektir. Sütun maksimumları X: 4, Y: 3, Z: 3; satır maksimumları A: 3, B: 3, C: 4'tür. İzleme tablosu dokuz hücreyi sırayla gösterir.

Dokuz hücre tarandıktan sonra fonksiyon [(0, 0), (1, 1)] döndürür, yani (A, X) ve (B, Y). Dikkat edilirse (C, X)'te yalnız ikinci koşul, (C, Z)'de yalnız birinci koşul doğrudur; and ikisini birden istediği için bu hücreler elenir. Bu, “tek işaret yetmez” kuralının koddaki karşılığıdır.

Karmaşıklık açısından bu sürüm her hücrede bir sütun maksimumu (m karşılaştırma) ve bir satır maksimumu (n karşılaştırma) hesaplar. Toplam iş O(mn · (m + n))'dir. Maksimumlar döngüden önce bir kez hesaplanıp bir listede saklanırsa iş O(mn)'ye düşer. Küçük matrislerde fark önemsizdir; 1000 × 1000 bir matriste ise yaklaşık 2000 kat fark eder.

3.2.8Sürekli stratejiler: Cournot duopolü

Şimdiye kadar her oyuncunun birkaç seçeneği vardı. Bazı oyunlarda strateji bir sayıdır ve sonsuz çok değer alabilir. En eski örnek Antoine Augustin Cournot'nun 1838'de incelediği iki firmalı piyasadır; iki firmalı piyasaya duopol denir.

İki firma aynı malı üretir ve aynı anda üretim miktarı y₁, y₂ ≥ 0 seçer. Piyasa fiyatı toplam üretime bağlıdır: P = 12 − (y₁ + y₂). Ne kadar çok üretilirse fiyat o kadar düşer. Üretim maliyeti sıfırdır. Firma 1'in kârı miktar çarpı fiyattır:

u₁(y₁, y₂) = y₁ · (12 − y₁ − y₂)

Burada matris çizilemez, çünkü satır sayısı sonsuzdur. Ama en iyi tepki fikri aynen geçerlidir: firma 2'nin y₂ miktarı sabitken firma 1'in kârını en büyük yapan y₁ aranır. Seçim sürekli olduğunda argmax tablodan okunmaz; türev ile bulunur.

Türev, bir eğrinin her noktadaki eğimidir. Kâr eğrisinin tepesinde eğim sıfırdır: tepenin solunda eğim artı (kâr artıyor), sağında eksidir (kâr azalıyor). Burada gereken üç kural şunlardır: y²'nin türevi 2y'dir; c · y'nin türevi c'dir; sabitin türevi 0'dır. Toplamın türevi türevlerin toplamıdır.

Şekil 3.6'da iki en iyi tepki doğrusu çizilmiştir. Yatay eksen firma 1'in, dikey eksen firma 2'nin miktarıdır. BR₁ doğrusu, firma 2'nin her miktarı için firma 1'in en iyi miktarını gösterir; y₂ = 0'da 6'dan başlar, y₂ = 12'de 0'a iner. Denge iki doğrunun kesiştiği tek noktadır. Rakip daha çok ürettikçe benim en iyi miktarım azalır: doğrunun eğimi negatiftir.

Kartel neden dengede değildir? İki firma anlaşıp toplam kârı en büyük yapmak isteseydi, toplam miktar Y için Y(12 − Y)'yi en büyük yapardı. Türev 12 − 2Y = 0'dan Y = 6 çıkar; her firma 3 üretir, fiyat 6 olur ve her firma 3 · 6 = 18 kazanır. Bu, dengedeki 16'dan fazladır. Ancak anlaşma kendini doğrulamaz. Rakip 3 üretirken firma 1'in en iyi tepkisi BR₁(3) = (12 − 3)/2 = 4,5'tir. Sapan firma 4,5 · (12 − 4,5 − 3) = 4,5 · 4,5 = 20,25 kazanır; anlaşmaya sadık kalan firmanın kârı ise 3 · 4,5 = 13,5'e düşer. Her firmanın sapma isteği vardır. Bu, Mahkûmun İkilemi'nin sürekli stratejili bir sürümüdür.

Denge nasıl bulunabilir? Firmaların dengeyi hesapladığını varsaymak zorunda değiliz. Firmalar sırayla birbirine en iyi tepki verirse üretimler dengeye yaklaşır. Başlangıçta firma 1 tek başına 6 üretsin (rakip 0 üretirken en iyi tepki). Firma 2 buna (12 − 6)/2 = 3 ile cevap verir. Firma 1 de 3'e 4,5 ile cevap verir, ve böyle devam eder.

Her adımda, güncellenen miktarın dengeye uzaklığı yarıya iner: 6 için 2, 3 için 1, 4,5 için 0,5, 3,75 için 0,25, 4,125 için 0,125. Bunun nedeni en iyi tepki doğrusunun eğiminin −1/2 olmasıdır. Bu tür bir “öğrenme süreci” her oyunda dengeye varmaz; ama burada vardığı için Cournot dengesi davranışsal olarak da makul bir tahmindir.

3.2.9Bertrand: fiyatla rekabet

Firmalar miktar yerine fiyat seçerse sonuç şaşırtıcı biçimde değişir. Bu model Joseph Bertrand'ın adını taşır. İki firma aynı malı satar; birim maliyet c = 2 TL, pazar 100 birimdir. Firmalar aynı anda fiyat seçer. Ucuz olan pazarın hepsini alır; fiyatlar eşitse pazar yarı yarıya bölünür. Bir firmanın kârı (fiyat − maliyet) × satılan miktardır.

İki model arasındaki fark, sapmanın ne getirdiğinden kaynaklanır. Cournot'da bir firma miktarını artırınca fiyat düşer ve bu düşüş kendi kârını da azaltır; sapma kendi kendini frenler. Bertrand'da ise küçük bir fiyat indirimi pazarın tamamını getirir; sapmanın ödülü çok büyüktür. Bu yüzden iki firma bile fiyatı maliyete kadar indirir. Bu sonuca Bertrand paradoksu denir: “iki firma varsa kâr yüksek kalır” sezgisi fiyat rekabetinde yanlıştır. Gerçek piyasalarda kâr, ancak ürün farkı, kapasite sınırı ya da tekrarlanan etkileşim gibi etkenlerle korunur.

3.3Baskın strateji eleme

En iyi tepki işaretlemesi dengeyi doğrudan arar. Baskın strateji elemesi ise ters yönden çalışır: önce “hiçbir rasyonel oyuncunun oynamayacağı” stratejileri bulup oyundan çıkarır, oyunu küçültür. Bazen geriye tek bir hücre kalır ve oyun bu yolla tamamen çözülür.

3.3.1Baskın ve baskılanan strateji

İki stratejiyi karşılaştırmanın en güçlü yolu, rakibin her olası seçimine karşı karşılaştırmaktır. Bir strateji ötekinden rakip ne yaparsa yapsın daha iyiyse, ikinci stratejiyi oynamak için hiçbir neden kalmaz.

Tanımdaki “her” sözcüğü kritiktir. Kesin baskılama için karşılaştırma rakibin her seçimi için ayrı ayrı yapılır ve her birinde kesin büyüklük gerekir. “Ortalamada daha iyi” ya da “çoğu durumda daha iyi” yetmez.

Rasyonel oyuncu kesin baskılanan stratejiyi asla oynamaz. Nedeni açıktır: hangi inanca sahip olursa olsun, baskılayan strateji ona daha çok kazandırır. Kesin baskılanan bir strateji hiçbir rakip seçimine en iyi tepki değildir.

Baskın stratejisi olan oyuncu için oyun kolaydır: rakibini tahmin etmek zorunda değildir. Herkesin baskın stratejisi varsa, herkesin baskın stratejisini oynadığı profil bir Nash dengesidir; buna baskın strateji dengesi (dominant-strategy equilibrium) denir. Mahkûmun İkilemi'nde İhanet iki oyuncu için de baskın stratejidir ve (İhanet, İhanet) bir baskın strateji dengesidir. Ancak baskın strateji her oyunda bulunmaz. Taş-Kağıt-Makas'ta (TKM) her hamle bir başka hamleye yenilir; hiçbir hamle ötekileri her durumda yenmez.

Baskın strateji olmasa bile tek tek baskılanan stratejiler olabilir. Bunları silmek ve küçülen oyunda yeniden aramak bir yöntem verir.

Yöntemin dayandığı varsayım, yalnız oyuncuların rasyonel olması değil, herkesin rasyonel olduğunun herkesçe bilinmesi, bunun da herkesçe bilinmesi ve bu zincirin sonsuza kadar sürmesidir. Bu varsayıma ortak bilgi (common knowledge) denir. İlk turda silinen strateji, yalnız oyuncunun kendisinin rasyonel olmasından gelir. İkinci turda silinen strateji, oyuncunun rakibinin rasyonel olduğunu bilmesini gerektirir: “rakibim o baskılanan stratejiyi oynamaz, o hâlde o sütunu hesaba katmam”. Her yeni tur, bir kat daha derin bilgiye dayanır.

Zayıf baskılama için bu güvence yoktur. Zayıf baskılanan bir strateji, bazı durumlarda baskılayanla eşit kazanç verir; o durumlarda bir en iyi tepki olabilir ve bir dengede yer alabilir. Silindiğinde bazı dengeler kaybolabilir ve sonuç silme sırasına bağlı olabilir (3.3.7).

Önceki bölümlerden tanıdık bir örnek bu farkı gösterir. 2/3 ortalaması oyununda herkes 0 ile 90 arasında bir sayı yazar; ortalamanın 2/3'üne en yakın sayı kazanır. Ortalama en fazla 90 olabileceği için hedef en fazla 60'tır. 60'ın üstündeki bir tahmin, hiçbir durumda 60 yazmaktan iyi değildir; ama bazı durumlarda (örneğin iki tahmin de hedeften uzak kalıp ikisi de kaybettiğinde) eşit sonuç verir. Bu yüzden 60'ın üstündeki sayıları silmek zayıf baskılamaya dayanır, kesin baskılamaya değil.

3.3.2Mahkûmun İkilemi'ne dönüş

Sam sessiz mi kalmalı, ihanet mi etmeli? Kuramın cevabı nettir: İhanet baskın stratejidir, çünkü John sessizse 0 > −1, ihanet ederse −2 > −3'tür. Tek Nash dengesi (İhanet, İhanet) = (−2, −2), yani ikişer yıldır (Şekil 3.9).

Gerçek davranış kuramdan farklıdır. Tek seferlik oyunda insanlar kuramın öngördüğünden çok daha sık işbirliği yapar. 1958–1992 arasındaki deneyleri birleştiren bir meta-analize göre katılımcıların kabaca yarısı işbirliği yapar ve oyun öncesinde konuşma izni verilmesi bu oranı belirgin biçimde artırır (Sally, 1995). Güven, adalet ve karşılıklılık duyguları da seçimi etkiler. Bu, kuramın yanlış olduğu anlamına gelmez; kazanç olarak yalnız hapis yılı yazıldığında insanların önemsediği başka şeyler (suçluluk duygusu, itibar) tablonun dışında kalır. Kuram, bu etkenler olmasaydı ne olacağını gösteren açık bir karşılaştırma noktasıdır.

Tekrarlanan oyun. Oyun aynı rakiple tekrar tekrar oynanınca durum değişir. Bilgisayar Tit-for-Tat oynasın: ilk tur sessiz kalır, sonra karşısındakinin bir önceki seçimini kopyalar. Sam'in 10 turluk farklı planlarının toplam maliyeti şöyledir.

Tek seferlik oyunda baskın olan İhanet, Tit-for-Tat'a karşı pahalıdır: her ihanet bir sonraki turda cezalandırılır. Yalnız son turda ceza gelemez, çünkü sonraki tur yoktur. Bu yüzden en iyi plan dokuz tur sessiz kalıp son turda ihanet etmektir. 2¹⁰ = 1024 planın hepsi bilgisayarla denendiğinde de en küçük toplamın 9 yıl olduğu görülür. Bu “son tur etkisi”, oyun ağacında sondan başa doğru akıl yürüten geriye doğru çıkarımın (backward induction) konusudur.

3.3.3Yinelemeli eleme: üçe üç örnek

Aşağıdaki oyunda hiçbir oyuncunun baskın stratejisi yoktur, ama yinelemeli eleme oyunu tek hücreye indirir.

3.3.4Bir eleme ötekinin yolunu açar

Yinelemeli elemenin gücü, her silmenin yeni silmelere kapı açmasındadır. Aşağıdaki oyunda başta yalnız tek bir kesin baskılama vardır; geri kalanların hepsi ondan sonra ortaya çıkar. Satırlar yalnız ilk sayılarla, sütunlar yalnız ikinci sayılarla karşılaştırılır.

Bu örneğin öğrettiği iki şey vardır. Birincisi, silme sırası mantıksal bir zincirdir: Üst'ün silinmesi Sağ'ın, Sağ'ın silinmesi de Alt'ın silinmesine bağlıdır. Her adım, bir öncekinin varsaydığı rasyonellik bilgisine bir kat daha ekler. İkincisi, denge herkes için en iyi sonuç değildir. (Üst, Merkez) = (5, 6) iki oyuncuya da (3, 5)'ten daha iyidir. Ama dengede değildir: sütun oyuncusu Merkez oynarken satır oyuncusu Orta'ya geçip 5 yerine 6 alır.

3.3.5Kod izleme: ele()

Yinelemeli eleme de kısa bir fonksiyonla yazılır. Fonksiyon, kalan satır indislerini R'de, kalan sütun indislerini S'de tutar.

def ele(U1, U2):
    R, S = [0, 1, 2], [0, 1, 2]   # kalanlar
    while True:
        x = [r for r in R for k in R if
             all(U1[k][c] > U1[r][c] for c in S)]
        y = [c for c in S for d in S if
             all(U2[r][d] > U2[r][c] for r in R)]
        if x: R.remove(x[0])      # satır elenir
        elif y: S.remove(y[0])    # sütun elenir
        else: return R, S

Kodun mantığı şöyledir:

• x, kalan satırlar içinde başka bir kalan satır k tarafından kesin baskılanan satırların listesidir. all(U1[k][c] > U1[r][c] for c in S), k satırının r satırını kalan her sütunda kesin yendiğini denetler. Silinmiş sütunlar S'de olmadığı için karşılaştırmaya girmez.
• y, aynı denetimi sütunlar için U2 ile yapar: d sütunu c sütununu kalan her satırda yeniyor mu?
• Önce satır silmeye bakılır: x boş değilse ilk baskılanan satır silinir. Yoksa sütuna bakılır. İkisi de boşsa kalanlar döndürülür.
• while True döngüsü her silmeden sonra baştan başlar; böylece bir silmenin açtığı yeni baskılamalar bir sonraki turda bulunur.

Üçe üç eleme örneğinin matrisleriyle çağrıldığında izleme şöyledir:

Fonksiyon ([2], [2]) döndürür, yani yalnız (C, Z) kalır. Dört elemede sırayla X, B, Y, A silinmiştir. 2. turda y'nin boş çıkması önemlidir: o anda kalan üç satırda Z, Y'yi yenemez, çünkü B satırında Y 4, Z 3 verir. B silindikten sonra (3. tur) Z, Y'yi yener. Bu, 3.3.4'teki “bir eleme ötekinin yolunu açar” gözleminin koddaki karşılığıdır.

Her turda x en çok m² · n, y en çok n² · m karşılaştırma yapar ve en çok m + n tur vardır. Toplam iş polinomdur; küçük oyunlar için anında biter.

3.3.6Karışık stratejiyle baskılama

Bir stratejiyi yenen tek bir saf strateji olmayabilir, ama iki stratejinin bir karışımı onu yenebilir. Aşağıdaki tabloda yalnız satır oyuncusunun kazançları (u₁) verilmiştir, çünkü satırlar yalnız bu sayılarla karşılaştırılır.

Orta'yı hiçbir saf satır baskılamaz: Sağ sütununda Üst'ten (1 > 0), Sol sütununda Alt'tan (1 > 0) iyidir. Ama satır oyuncusu yazı-tura atıp yarı olasılıkla Üst, yarı olasılıkla Alt oynarsa, her sütunda beklenen kazancı şöyle olur:

• Sol'a karşı: ½ · 4 + ½ · 0 = 2.
• Sağ'a karşı: ½ · 0 + ½ · 4 = 2.

İki sütunda da 2 > 1'dir. Demek ki Orta, ½–½ karışımı tarafından kesin baskılanır ve silinebilir. Beklenen kazanç kavramı 3.4.1'de ayrıntılı açıklanır; burada “çok sayıda tekrarda tur başına ortalama kazanç” anlamı yeterlidir.

Şekil 3.12 aynı sonucu bir adım daha ileri taşır. Satır oyuncusu, sütun oyuncusunun Sol'u q olasılıkla oynayacağına inanıyor olsun. Üst'ün beklenen kazancı 4q, Alt'ınki 4(1 − q)'dur. Bu iki doğrunun büyük olanı (üst zarf) en az 2'dir; en düşük noktası q = ½'deki kesişimdir. Orta'nın doğrusu ise her yerde 1'dir ve üst zarfın tamamen altında kalır. Sonuç: Orta, sütun oyuncusu hakkındaki hiçbir inanca karşı en iyi tepki değildir. Karışık stratejiyle kesin baskılanmak ile “hiçbir inanca karşı en iyi tepki olmamak” iki kişilik oyunlarda aynı şeydir.

3.3.7Zayıf baskılamanın tuzağı

Zayıf baskılananları silmenin neden tehlikeli olduğunu küçük bir oyun gösterir.

Ders şudur: kesin baskılama güvenlidir, zayıf baskılama denge kaybettirebilir. Ayrıca birden çok zayıf baskılama olduğunda, hangisinin önce silindiğine göre farklı hücreler kalabilir. Bu nedenle denge ararken yalnız kesin baskılananlar silinir.

Kesin eleme her oyunda tek hücreye de inmez. Cinsiyetler Savaşı'nda (Battle of the Sexes) iki kişi akşam Opera'ya mı Futbol'a mı gideceklerine ayrı ayrı karar verir; biri Opera'yı, öteki Futbol'u daha çok sever, ama ikisi de ayrı yerlere gitmektense birlikte olmayı tercih eder. Bu oyunda hiçbir strateji baskılanmaz; eleme hiçbir şey silmez. O zaman en iyi tepki işaretlemesine ve karışık stratejilere başvurulur.

3.3.8Elemede sık hatalar

3.4Karışık strateji

Bazı oyunlarda hiçbir hücre karşılıklı en iyi tepki değildir. Yazı-Tura Eşleştirme'de iki oyuncu aynı anda bir madeni paranın yüzünü seçer; yüzler aynıysa satır oyuncusu, farklıysa sütun oyuncusu kazanır. Satır oyuncusu Yazı derse sütun oyuncusu Tura demek ister; o Tura derse satır oyuncusu Tura'ya geçmek ister; ve döngü böyle sürer. Böyle oyunlarda oyuncular tahmin edilemez olmak ister. Bu bölüm, “tahmin edilemez olmak” fikrini olasılıkla kesinleştirir.

3.4.1Karışık strateji ve kayıtsızlık ilkesi

Önce iki temel olasılık kavramına kısaca bakalım. Bir olasılık dağılımı, olası sonuçların her birine 0 ile 1 arasında bir sayı atar ve bu sayıların toplamı 1'dir. Adil bir zarda her yüzün olasılığı 1/6'dır. Değeri şansa bağlı bir X sayısının beklenen değeri (expected value), her olası değerin olasılığıyla çarpılıp toplanmasıyla bulunur:

E[X] = Σ_x x · P(X = x)

Adil zarda E[X] = (1 + 2 + 3 + 4 + 5 + 6) · 1/6 = 21/6 = 3,5'tir. Beklenen değer “en olası sonuç” değildir; zarda 3,5 hiç gelmez. Beklenen değer, aynı deney çok kez tekrarlansaydı tur başına ortalamanın ne olacağını söyler.

Örneğin Taş-Kağıt-Makas'ta (1/3, 1/3, 1/3), “bir zar at; 1–2 gelirse Taş, 3–4 gelirse Kağıt, 5–6 gelirse Makas oyna” demektir. 2 × 2 oyunlarda gösterim kısalır: p satır oyuncusunun ilk satırı, q sütun oyuncusunun ilk sütunu oynama olasılığıdır; öteki seçeneklerin olasılığı 1 − p ve 1 − q'dur.

Bir saf stratejinin karışık bir rakibe karşı beklenen kazancı, o satırın kazançlarının rakibin olasılıklarıyla tartılmasıdır. Rakip Taş-Kağıt-Makas'ta (1/2 Taş, 1/4 Kağıt, 1/4 Makas) oynasın. Kazanınca +1, kaybedince −1, berabere 0 olsun:

• Taş: ½ · 0 + ¼ · (−1) + ¼ · (+1) = 0.
• Kağıt: ½ · (+1) + ¼ · 0 + ¼ · (−1) = ¼.
• Makas: ½ · (−1) + ¼ · (+1) + ¼ · 0 = −¼.

Bu rakibe karşı en iyi tepki Kağıt'tır ve tur başına ortalama ¼ puan kazandırır. Beklenen değer ile argmax birlikte, karışık bir rakibe karşı en iyi tepkiyi verir. Rakip (1/3, 1/3, 1/3) oynasaydı her hamle 0 getirirdi; hiçbir hamle ötekinden iyi olmazdı. TKM'nin dengesi tam olarak budur: iki oyuncu da (1/3, 1/3, 1/3) oynar ve her eylem 0 getirir. 1/3–1/3–1/3 dışındaki her karışımı rakip sömürebilir; az önceki hesap, Taş'a hafif yatkın bir oyuncunun Kağıt'la nasıl sömürüldüğünü gösterir.

Tanım saf durumdakiyle aynıdır; yalnızca stratejiler ve kazançlar genişlemiştir. Karışık dengeyi hesaplamanın anahtarı aşağıdaki ilkedir.

İlkenin şaşırtıcı bir sonucu vardır. Satır oyuncusunun karışık stratejisini oynamaya razı olması için iki seçeneği arasında kayıtsız olması gerekir; bu kayıtsızlık ise sütun oyuncusunun q'suna bağlıdır. Dolayısıyla satır oyuncusunun kayıtsızlık denklemi sütun oyuncusunun q'sunu belirler. Tersine, sütun oyuncusunun kayıtsızlık denklemi satır oyuncusunun p'sini belirler. Kısacası: satır oyuncusunun karışımı, sütun oyuncusunun kazançlarından hesaplanır (ve tersi).

Karışık stratejinin iki yorumu vardır. Birincisi gerçekten zar atmaktır: penaltıda atıcı tarafını kafasından rastgele seçer. İkincisi nüfus yorumudur: çok sayıda oyuncunun bulunduğu bir nüfusta olasılıklar davranış oranlarıdır; örneğin bütün penaltıların yüzde kaçının sola atıldığı. Tek bir oyuncu zar atmasa bile, rakibin bakış açısından onun hamlesi belirsizdir ve olasılık bu belirsizliği ölçer.

3.4.2Denetim oyunu adım adım

Denetim oyunu (inspection game), saf dengesi olmayan oyunların tipik örneğidir. Satır oyuncusu bir işçidir ve Çalış ya da Kaytar seçer. Sütun oyuncusu müdürdür ve Denetle ya da Denetleme seçer. Sayılar şöyledir: ücret 4, işçinin çaba maliyeti 2, çalışan işçinin üretimi 6, denetimin müdüre maliyeti 1. Kaytaran işçi denetimde yakalanırsa ücret alamaz.

Her hücre bu sayılardan türetilir. Çalış–Denetle hücresinde işçi ücretten çaba maliyetini çıkarır: 4 − 2 = 2. Müdür üretimden ücreti ve denetim maliyetini çıkarır: 6 − 4 − 1 = 1. Çalış–Denetleme'de işçi yine 2, müdür 6 − 4 = 2 alır. Kaytar–Denetle'de işçi yakalanır: ücret yok, çaba yok, 0 alır; müdür üretim almaz, ücret ödemez, yalnız denetim maliyetini öder: −1. Kaytar–Denetleme'de işçi çalışmadan ücreti alır: 4; müdür üretim almadan ücret öder: −4.

Şekil 3.14'teki okları takip edelim. İşçi çalışıyorsa müdür denetlemeyi bırakır (2 > 1). Müdür denetlemiyorsa işçi kaytarır (4 > 2). İşçi kaytarıyorsa müdür denetler (−1 > −4). Müdür denetliyorsa işçi çalışır (2 > 0). Her hücrede biri sapmak ister; en iyi tepkiler bir döngü oluşturur. Karışık denge aranır.

Şekil 3.15 müdürün durumunu gösterir. p < 3/4 iken mavi doğru üstte kalır: işçi sık kaytarıyorsa denetlemek iyidir. p > 3/4 iken kırmızı doğru üsttedir: işçi çoğunlukla çalışıyorsa denetim gereksizdir. Yalnız p = 3/4'te müdür iki seçenek arasında kayıtsızdır ve karıştırmaya razıdır.

3.4.3Ceza değişince kimin olasılığı değişir?

Kaytaran işçiye yakalandığında daha sert bir ceza verilsin: yakalanan kaytarıcının kazancı 0 yerine −2 olsun. Hangi olasılık değişir? Sezgisel cevap “işçi daha çok çalışır” olur. Kayıtsızlık ilkesi başka bir şey söyler.

Ceza yalnız işçinin kazancını değiştirir. İşçinin kazançları ise müdürün q'sunu belirler. Yeni hâliyle işçinin kayıtsızlığı 2 = −2q + 4(1 − q) = 4 − 6q'dur ve q* = 1/3 çıkar. Müdürün kazançları değişmediği için müdürün kayıtsızlık denklemi aynı kalır ve p* = 3/4 değişmez. Daha sert ceza, işçiyi daha çalışkan yapmaz; müdürün daha az denetlemesine izin verir.

Genel olarak yakalanan kaytarıcının kazancı c ise işçinin kayıtsızlığı 2 = c · q + 4(1 − q)'dur. Bu denklem (4 − c) q = 2 biçimine getirilir ve

q* = 2/(4 − c),   p* = 3/4

bulunur. c = 0'da q* = 1/2, c = −2'de q* = 1/3, c = −6'da q* = 1/5'tir.

Bu sonuç, “her oyuncunun denge olasılığını rakibinin kazançları belirler” ilkesinin somut bir hâlidir. Politika açısından da önemlidir: cezaları artırmak, denetim olasılığını azaltarak denetim maliyetinden tasarruf sağlar, ama kuralı çiğneme oranını değiştirmez. Kuralı çiğneme oranını değiştirmek için müdürün (denetleyenin) kazançlarını değiştirmek gerekir.

3.4.4Saklambaç: yöntemin tekrarı

Kayıtsızlık yöntemini bir kez daha, her adımı ayrı yazarak uygulayalım. Ayşe saklanır (satır), Bora arar (sütun). Seçenekler Bahçe ve Ev'dir. Hücrede keyif puanı (Ayşe, Bora) yazılıdır. Bora Ayşe'yi bahçede bulursa 3, evde bulursa 1 puan alır. Ayşe bahçede bulunmazsa 2, evde bulunmazsa 1 puan alır. Bulunan Ayşe 0, bulamayan Bora 0 alır.

Sonuç ilk bakışta çelişkili görünür: bahçeyi daha çok seven Ayşe (orada bulunmazsa 2 puan) orada yalnız %25 olasılıkla saklanır. Nedeni, Bora'nın da bahçede bulmayı daha çok sevmesidir (3 puan). Bora'nın bahçeye bakma isteği, Ayşe'yi oradan uzaklaştırır. Ayşe'nin bahçe sevgisi ise Bora'nın davranışını belirler: Bora bahçeye 2/3 olasılıkla bakar.

3.4.5Kod izleme: karisik_2x2()

Kayıtsızlık denklemleri her 2 × 2 oyun için genel olarak çözülebilir. Satır oyuncusunun kazançları A, sütun oyuncusununkiler B olsun (indis 0 ilk seçenek, 1 ikinci seçenek). Satır oyuncusunun kayıtsızlığı

A₀₀ q + A₀₁(1 − q) = A₁₀ q + A₁₁(1 − q)

eşitliğidir. q'lu terimler bir tarafa toplanınca q (A₀₀ − A₀₁ − A₁₀ + A₁₁) = A₁₁ − A₀₁ çıkar. Parantezdeki sayıya d_a denirse q = (A₁₁ − A₀₁) / d_a'dır. Aynı işlem sütun oyuncusunun kayıtsızlığı B₀₀ p + B₁₀(1 − p) = B₀₁ p + B₁₁(1 − p) için yapılınca p = (B₁₁ − B₁₀) / d_b, d_b = B₀₀ − B₀₁ − B₁₀ + B₁₁ bulunur. Aşağıdaki fonksiyon bu formülleri kesirlerle (Fraction) hesaplar; böylece 2/5 gibi sonuçlar ondalık yuvarlama hatası olmadan çıkar.

from fractions import Fraction as F
def karisik_2x2(A, B):
    da = A[0][0] - A[0][1] - A[1][0] + A[1][1]
    if da == 0: return None     # denklem yok
    q = F(A[1][1] - A[0][1], da)  # satır kayıtsız
    db = B[0][0] - B[0][1] - B[1][0] + B[1][1]
    if db == 0: return None
    p = F(B[1][1] - B[1][0], db)  # sütun kayıtsız
    if not (0 < p < 1 and 0 < q < 1):
        return None               # iç denge yok
    u1 = A[0][0] * q + A[0][1] * (1 - q)
    return p, q, u1

Fonksiyon üç durumda None döndürür: d_a = 0 ise satır oyuncusunun kayıtsızlık denkleminde q yok olur (iki seçeneğin farkı q'ya bağlı değildir); d_b = 0 ise aynısı sütun oyuncusu için olur; olasılıklardan biri 0 ile 1 arasında değilse iç karışık denge yoktur. Son satırdaki u1, satır oyuncusunun ilk satırı oynadığındaki beklenen kazancıdır. Kayıtsızlık ilkesi gereği ikinci satır da aynı değeri verir, bu yüzden bu sayı satır oyuncusunun denge kazancıdır.

Fonksiyonu Cinsiyetler Savaşı ile çalıştıralım. 0 = Opera, 1 = Futbol; A = [[3, 0], [0, 2]] satır, B = [[2, 0], [0, 3]] sütun oyuncusunun kazançlarıdır. Satır oyuncusu Opera'yı, sütun oyuncusu Futbol'u daha çok sever; ikisi de ayrı düşmekten (0) kaçınır.

Sütun oyuncusunun beklenen kazancı da u₂ = 2 · (3/5) = 6/5'tir. Bu sayı dikkat çekicidir: iki saf dengede (Opera, Opera) ve (Futbol, Futbol) oyuncular 2 ya da 3 alır. Karışık dengede ise ikisi de yalnız 6/5 alır, çünkü sık sık ayrı yerlere düşerler. Buluşamama, satır oyuncusu Opera'ya ve sütun oyuncusu Futbol'a gittiğinde ya da tersinde olur. Sütun oyuncusunun Futbol olasılığı 1 − 2/5 = 3/5, satır oyuncusununki 1 − 3/5 = 2/5 olduğundan buluşamama olasılığı (3/5)(3/5) + (2/5)(2/5) = 9/25 + 4/25 = 13/25 = %52'dir.

Fonksiyonun None dalları da örneklerle anlaşılır. Bedava Para oyununda yalnız (Yazı, Yazı) hücresi (1, 1), öteki hücreler 0'dır. A = [[1, 0], [0, 0]] için d_a = 1, q = (0 − 0)/1 = 0 çıkar; q 0 ile 1 arasında olmadığı için fonksiyon None döndürür. Mahkûmun İkilemi'nde A = [[-1, -3], [0, -2]] için d_a = −1 + 3 − 0 − 2 = 0'dır ve ilk denetim None döndürür: İhanet, Sessiz'den her durumda tam 1 fazla verdiği için satır oyuncusu hiçbir q'da kayıtsız olmaz.

3.4.6Altı klasik oyunun karışık dengeleri

Aşağıdaki tablo altı klasik 2 × 2 oyunun dengelerini karşılaştırır. p* ve q*, ilk stratejinin (Yazı, Kır, Opera, Geyik, Parti, Yazı) oynanma olasılığıdır.

Tablodaki sayıların ikisini ayrıntılı türetelim.

Tablonun son satırı bir uyarıdır. Bedava Para'da sütun oyuncusu Yazı'yı q > 0 olasılıkla seçtiği sürece satır oyuncusu için Yazı (kazanç q) Tura'dan (kazanç 0) kesin daha iyidir. Kayıtsızlık yalnız q = 0'da olur; bu da bir “karışım” değil, saf (Tura, Tura) dengesidir. Kazançlarında eşitlik bulunan böyle oyunlarda iç karışık denge olmayabilir.

3.4.7Karışık dengede sık hatalar

3.5Varlık ve denge seçimi

Şimdiye kadar incelenen oyunların bazılarında tek denge, bazılarında birden çok denge vardı; saf dengesi olmayan oyunlarda ise karışık bir denge bulundu. İki soru doğal olarak ortaya çıkar. Her oyunun bir dengesi var mıdır? Birden çok denge varsa hangisi oynanır? Bu bölüm iki soruyu sırayla ele alır.

3.5.1Nash'in varlık teoremi

Teoremin tam ispatı bu dersin kapsamı dışındadır; ama fikri anlaşılabilir. Fikir, sabit nokta kavramına dayanır. Bir fonksiyonun sabit noktası, fonksiyonun değiştirmediği noktadır: f(x) = x. En basit hâli şöyledir: [0, 1] aralığını yine [0, 1]'e götüren ve grafiği kopuksuz çizilebilen (sürekli) her fonksiyonun bir sabit noktası vardır. Grafik x = 0'da köşegenin üstünde ya da üzerinde başlar, x = 1'de köşegenin altında ya da üzerinde biter; kalemi kaldırmadan çizildiği için köşegeni bir yerde keser. O kesişim noktası sabit noktadır. Bu, Brouwer sabit nokta teoreminin bir boyutlu hâlidir.

Nash'in ispatında “nokta” bir karışık strateji profilidir. Fonksiyonun yerinde en iyi tepki eşlemesi vardır: her profile, herkesin ötekilere en iyi tepki verdiği profilleri atar. Eşlemenin sabit noktası, herkesin zaten ötekilere en iyi tepki verdiği bir profildir; Teorem 3.1'e göre bu bir Nash dengesidir. Kakutani'nin sabit nokta teoremi (Brouwer'in tek değer yerine küme döndüren eşlemelere genellemesi) bu eşlemenin bir sabit noktası olduğunu garanti eder.

Karışık stratejilerin burada neden gerekli olduğu da bu fikirden anlaşılır. Sabit nokta teoremleri “kopuksuzluk” ister: olasılıklar sürekli değişebilir (0,30'dan 0,31'e), saf stratejiler ise atlayarak değişir (Yazı'dan Tura'ya). Saf stratejilerle sınırlı kalınca kopukluk oluşur ve denge kaybolabilir. Nitekim Yazı-Tura'da saf denge yoktur. Bu yüzden teoremin garantisi karışık stratejiler içindir.

Sonluluk koşulu da gereklidir. Strateji kümesi sonsuzsa denge olmayabilir. Örneğin iki oyuncu aynı anda bir doğal sayı söylesin ve büyük sayıyı söyleyen kazansın. Her sayıdan daha büyüğü vardır; hangi profil seçilirse seçilsin, kaybeden daha büyük bir sayı söyleyerek kazanır. Hiçbir profil denge değildir. Cournot oyununda strateji kümesi sonsuz olduğu hâlde denge vardı; çünkü orada kazançlar düzgündü ve en iyi tepkiler sınırlı bir aralıkta kalıyordu. Sonsuz kümelerde varlık, ek koşullara bağlıdır.

Şekil 3.18 bu fikri denetim oyununda somutlaştırır. Yatay eksen işçinin Çalış olasılığı p, dikey eksen müdürün Denetle olasılığı q'dur. İşçinin en iyi tepkisi şöyledir: q < 1/2 iken Kaytar (p = 0), q > 1/2 iken Çalış (p = 1), q = 1/2'de ise kayıtsızdır ve her p en iyi tepkidir. Bu yüzden mavi eğri bir “basamak” biçimindedir ve q = 1/2'de yatay bir parça içerir. Müdürün en iyi tepkisi de benzer bir basamaktır: p < 3/4 iken Denetle (q = 1), p > 3/4 iken Denetleme (q = 0). İki basamak tek bir noktada kesişir. Kesişim noktasında iki oyuncu da birbirine en iyi tepki verir; bu nokta dengedir. Eğrilerin kesişmek zorunda olması, sabit nokta teoreminin bu basit oyundaki görüntüsüdür.

3.5.2Kanal paylaşımında üç denge

İki kablosuz cihaz aynı kanala paket göndermek ister. İkisi aynı anda gönderirse paketler çarpışır ve her biri −2 alır. Yalnız biri gönderirse gönderen 3, bekleyen 1 alır (bekleyen de kanalın düzgün çalışmasından yararlanır). İkisi de beklerse kanal boşa gider ve ikisi de 0 alır. Bu yapı, Tavuk oyunu ile aynıdır: her oyuncu karşısındakinin tersini yapmak ister.

En iyi tepki eğrileri (Şekil 3.19) üç noktada kesişir: iki köşe saf dengeler, orta nokta karışık dengedir. Karışık denge simetrik olduğu için “adil”dir, ama verimsizdir. Zamanın dörtte birinde paketler çarpışır, dörtte birinde kanal boş kalır ve her cihaz ortalama yalnız ½ alır. Saf dengelerde ise her cihaz 3 ya da 1 alır. Ağ protokollerindeki rastgele bekleme (backoff) bu rastgeleleştirmenin uygulamadaki karşılığıdır: çarpışan cihazlar rastgele bir süre bekleyip yeniden dener, böylece “kim önce gönderecek” sorusu koordinasyon olmadan çözülür.

3.5.3Kaç denge olur? Tek sayı kuralı

Bu bölümde incelenen oyunların denge sayıları ilginç bir örüntü gösterir.

Teoremin ispatı ileri düzeydedir (Wilson, 1971); ama pratik bir kural verir. İki saf denge bulunduysa büyük olasılıkla bir karışık denge daha vardır ve kayıtsızlık yöntemiyle aranmalıdır. Dil seçimi oyunu bunun güzel bir örneğidir. İki saf dengenin yanında, C seçeneklerinin hiç oynanmadığı bir karışık denge vardır. Ayşe Python'u 3/4, Bora Python'u 1/5 olasılıkla seçer. Bu karışıma karşı Ayşe'nin Python ve Java satırları 8/5, C satırı yalnız 1/5 verir; Bora'nın Python ve Java sütunları 7/4, C sütunu 1/2 verir. C'ye geçmek kimseye kazandırmaz, yani 2 × 2'de bulunan karışım 3 × 3 oyunda da dengedir.

Eşitlikli oyunlarda kural bozulabilir. Zayıf Baskılamanın Tuzağı'nda sütun oyuncusu her hücrede 1 aldığı için her karışıma razıdır; örneğin satır oyuncusu Alt oynarken sütun oyuncusunun her karışımı bir dengedir. Sonsuz çok denge vardır. Bedava Para'da ise denge sayısı 2'dir, yani çifttir. Bu oyunlar “dejenere”dir: kazançlardaki eşitlikler kuralın varsayımını bozar. Kazançlar biraz değiştirilirse (örneğin bir eşitlik 1 yerine 1,01 yapılırsa) tek sayı kuralı geri gelir.

3.5.4Çoklu denge: Geyik Avı

Filozof Jean-Jacques Rousseau'nun anlattığı bir öyküye dayanan Geyik Avı (Stag Hunt), çoklu dengenin en bilinen örneğidir. İki avcı aynı anda Geyik ya da Tavşan avlamaya karar verir. Geyik ancak iki avcı birlikte avlanırsa yakalanır ve her biri 4 alır. Tavşan tek başına yakalanabilir ve ortak ne yaparsa yapsın 3 garanti eder. Geyiğe yalnız giden avcı eli boş döner (0).

En iyi tepkiler iki hücrede çakışır: (Geyik, Geyik) ve (Tavşan, Tavşan). Ortak geyiğe giderse geyiğe gitmek (4 > 3), ortak tavşana giderse tavşana gitmek (3 > 0) en iyisidir. Üçüncü denge karışıktır: karşı taraf Geyik'i q olasılıkla seçiyorsa Geyik'in beklenen kazancı 4q, Tavşan'ınki her durumda 3'tür. 4q = 3 ⇒ q = 3/4. Geyik, ancak ortağın en az %75 olasılıkla geleceğine inanılırsa en iyi tepkidir. Hangi denge oynanacak?

İki ölçüt farklı cevaplar verir.

Pareto baskınlık (Pareto dominance): Bir denge, öteki dengeye göre herkese en az onun kadar, en az birine daha çok veriyorsa onu Pareto baskılar. (Geyik, Geyik) iki avcıya da daha çok verir (4 > 3). Verimlilik ölçütü (Geyik, Geyik)'i seçer.

Risk baskınlık (risk dominance): Harsanyi ve Selten'in (1988) önerdiği bu ölçüt, ortağın ne yapacağından emin olunmadığında hangi dengenin daha “güvenli” olduğuna bakar. Her dengede, her oyuncunun tek taraflı sapma kaybı hesaplanır ve bu kayıplar çarpılır. Çarpımı büyük olan denge risk baskındır.

• (G, G)'de bir avcı Tavşan'a sapsa 4 yerine 3 alır: kaybı 4 − 3 = 1. İki avcı için çarpım 1 · 1 = 1.
• (T, T)'de bir avcı Geyik'e sapsa 3 yerine 0 alır: kaybı 3 − 0 = 3. Çarpım 3 · 3 = 9.

9 > 1 olduğu için (Tavşan, Tavşan) risk baskındır. Sezgisel anlamı şudur: (T, T)'de yanılmanın bedeli düşüktür (tavşan zaten garanti), (G, G)'de ise ortağa yanlış güvenmenin bedeli ağırdır (eli boş dönmek). 2 × 2 simetrik oyunlarda risk baskın denge, ortağın ne yapacağı hakkında yarı yarıya bir inançla en iyi tepki olan dengedir: ortak ½ olasılıkla geyiğe gelirse Geyik 4 · ½ = 2, Tavşan 3 verir.

3.5.5Denge seçimi ölçütleri

Kuram birden çok dengeden hangisinin oynanacağını tek başına söylemez. Bu soruya denge seçimi (equilibrium selection) sorunu denir. Literatürde öne çıkan ölçütler şunlardır:

Odak noktası (focal point) özellikle ilginçtir. İki arkadaş İstanbul'da buluşacak ama yer ve saati konuşamamışlar. Her ortak yer ve saat bir dengedir; kazançlar eşittir, bu yüzden Pareto ya da risk ölçütü yardımcı olmaz. Yine de pek çok kişi “saat 12'de Taksim” cevabını verir. Seçimi belirleyen sayılar değil, ortak kültür ve belirginliktir. Thomas Schelling bu gözlemi 1960'ta ortaya koydu.

Denge seçiminde bir de adalet sorunu vardır. Cinsiyetler Savaşı'nda saf dengelerin biri bir oyuncuyu (Opera: 3'e 2), diğeri öbürünü (Futbol: 2'ye 3) kayırır. “Adil” görünen simetrik karışık denge ise ikisine de yalnız 6/5 verir, yani iki saf dengenin her ikisinden de kötüdür. Adalet ile verimlilik burada çatışır. Gerçek hayatta bu tür çatışmalar sıra ile (bir hafta opera, bir hafta futbol) ya da yazı-tura gibi bir dış sinyalle çözülür. Dış sinyal fikri, 3.5.7'deki korelasyonlu dengenin çekirdeğidir.

3.5.6Hata yapan rakip

Denge kavramı, herkesin ötekilerin davranışını doğru bildiğini varsayar. Bu varsayım biraz gevşetilsin: rakip küçük bir ε olasılıkla niyet etmediği hamleyi yapsın (eli kaysın, yanlış tuşa bassın). En iyi tepki değişir mi?

Mahkûmun İkilemi: değişmez. Rakip p olasılıkla Sessiz kalsın. Sam'in Sessiz kalmasının beklenen kazancı −1 · p − 3 · (1 − p) = 2p − 3, İhanet'inki 0 · p − 2 · (1 − p) = 2p − 2'dir. Fark her p için (2p − 2) − (2p − 3) = 1'dir. İhanet her p için tam 1 yıl daha iyidir; rakibin hata payı ne olursa olsun karar değişmez.

Geyik Avı: hata payına bağlıdır. Rakip q olasılıkla Tavşan'a kaçsın. Geyik'in beklenen kazancı 4 · (1 − q), Tavşan'ınki her durumda 3'tür. Geyik, ancak 4(1 − q) ≥ 3, yani q ≤ 1/4 iken en iyi tepkidir. Ortağın tavşana kaçma olasılığı %25'i aşarsa güvenli seçim, risk baskın Tavşan'dır.

Genel ders şudur: baskın strateji dengesi hatalara dayanıklıdır, koordinasyon dengeleri değildir. Baskın strateji, rakibin ne yapacağına hiç bağlı olmadığı için rakibin hataları onu etkilemez. Koordinasyon dengesi ise karşı tarafın doğru oynayacağına duyulan güvene dayanır; güven azaldıkça denge sarsılır.

3.5.7Korelasyonlu denge

Işıksız bir kavşağa iki sürücü aynı anda gelir. Her biri yol verir (Kır) ya da geçer (Düz git). Bu bir Tavuk oyunudur: (Kır, Kır) = (0, 0), (Kır, Düz) = (−1, 1), (Düz, Kır) = (1, −1), (Düz, Düz) = (−10, −10). İki saf denge birer sürücüyü kayırır; koordinasyon yoksa simetrik karışık dengede her sürücü 9/10 olasılıkla kırar, %1 olasılıkla çarpışma olur ve beklenen kazanç −1/10'dur (Tavuk örneği).

Şimdi kavşağa bir trafik ışığı konsun. Işık bir aracı gibi çalışır: önceden ilan edilmiş bir olasılık dağılımı μ'den bir hücre çeker ve her sürücüye yalnız kendi önerisini fısıldar. Burada μ, (Kır, Kır), (Kır, Düz) ve (Düz, Kır) hücrelerine 1/3'er olasılık, (Düz, Düz)'e 0 olasılık verir.

Uyma kısıtlarını denetlemek için koşullu olasılık gerekir. Bir olayın, başka bir olayın gerçekleştiği bilindiğinde olasılığı P(A | B) = P(A ve B) / P(B)'dir. Bu formüle Bayes kuralı da denir; sürücü kendi önerisini görünce rakibin önerisi hakkındaki inancını bu kuralla günceller.

Işığın gücü, sürücülerin kendi önerileri dışında bir şey bilmemesinden gelir. Kır önerisi alan sürücü, rakibin de Kır önerisi almış olabileceğini bilir; bu belirsizlik ona sapmayı pahalı kılar. Aracı hiçbir zorlama yapmaz; uymak herkesin kendi çıkarınadır.

Korelasyonlu denge iki özelliğiyle önemlidir. Birincisi, kapsamı geniştir: her Nash dengesi bir korelasyonlu dengedir (aracı, oyuncuların bağımsız karışımlarını aynen önerirse uyma kısıtları Nash koşuluna dönüşür), ama tersi doğru değildir. Bu örnekteki ışık hiçbir Nash dengesine karşılık gelmez. İkincisi, hesaplaması kolaydır: uyma kısıtlarının hepsi μ'nün olasılıklarında doğrusaldır. Bu yüzden bir korelasyonlu denge doğrusal programlama (linear programming, LP) ile polinom zamanda bulunur; Nash dengesi için böyle bir yöntem bilinmez (3.6.6). Işık sürelerini trafik yoğunluğuna göre ayarlamak ise ayrı bir tasarım kararıdır: hangi korelasyonlu dengenin seçileceği, kuralları koyanın elindedir.

3.6Minimaks ve karmaşıklık

Bu bölüm iki konuyu birleştirir. Önce çıkarların tam olarak zıt olduğu sıfır toplamlı oyunlara bakılır; bu oyunlarda denge kavramı özellikle güçlüdür ve verimli biçimde hesaplanabilir. Sonra genel oyunlara dönülür ve dengeyi bulmanın bilgisayar açısından ne kadar zor olduğu sorulur.

3.6.1Sıfır toplamlı oyun ve eyer noktası

Sıfır toplamlı oyunda her hücrede iki oyuncunun kazançlarının toplamı sıfırdır: u₂ = −u₁. Bu yüzden hücreye yalnız satır oyuncusunun kazancı yazılır; sütun oyuncusu aynı miktarı kaybeder. Satır oyuncusu bu sayıyı büyütmek, sütun oyuncusu küçültmek ister.

Böyle bir oyunda doğal bir akıl yürütme kötümser düşünmektir. Satır oyuncusu der ki: “Hangi satırı seçersem seçeyim, rakibim bana en kötüsünü yapacak. O hâlde her satırın en kötü değerine bakıp en iyisini seçeyim.” Sütun oyuncusu da benzer düşünür.

Eyer noktasının Nash dengesi olduğu kolayca görülür. Satır oyuncusu Y sütununda başka bir satıra geçerse 3'ten fazla alamaz, çünkü 3 o sütunun en büyüğüdür. Sütun oyuncusu A satırında başka bir sütuna geçerse 3'ten az veremez, çünkü 3 o satırın en küçüğüdür. Adı da buradan gelir: at eyeri bir yönde (sütun boyunca) tepe, öteki yönde (satır boyunca) çukurdur.

Maksimin ile minimaks her zaman eşit değildir; ama maksimin hiçbir zaman minimakstan büyük olamaz. Nedeni şudur: maksimin satırı r*, minimaks sütunu c* olsun. r* satırının en küçüğü, bu satırdaki A[r*][c*]'dan büyük olamaz; c* sütununun en büyüğü de bu sütundaki A[r*][c*]'dan küçük olamaz. Dolayısıyla maksimin ≤ A[r*][c*] ≤ minimaks'tır. Eşitlik yoksa eyer noktası yoktur ve oyuncuların garantileri arasında bir boşluk kalır.

3.6.2Eyer noktası yoksa: penaltı atışı

Penaltıda atıcı ve kaleci aynı anda Sol ya da Sağ seçer (Sol ve Sağ atıcıya göredir). Hücrede gol yüzdesi yazılıdır; atıcı bu sayıyı büyütmek, kaleci küçültmek ister. Sayılar örnek değerlerdir; gerçek verideki yapı benzerdir (Palacios-Huerta, 2003).

İlginç bir ayrıntı: atıcının güçlü tarafı Sol'dur (kaleci yanlış tarafa atlarsa %95), ama dengede Sol'a yalnız 4/11 olasılıkla vurur. Kaleci de bu güçlü tarafı bildiği için oraya daha sık atlamaya hazırdır. Kayıtsızlık ilkesinin her yerde gördüğümüz sonucu burada da geçerlidir.

3.6.3Güvenlik oyunları

Güvenlik oyunları (security games), sınırlı kaynakla çok sayıda hedefin korunduğu durumları modeller: havalimanları, limanlar, orman devriyeleri. Savunucu n hedeften k'sını koruyabilir. Hangi k hedefin seçileceği bir saf stratejidir ve bunların sayısı C(n, k)'dir. C(n, k) = n! / (k! (n − k)!), n nesneden sırasız k tane seçmenin yolu sayısıdır. n = 20, k = 5 için 15.504 saf strateji vardır.

Saldırgan devriye düzenini gözlemleyebilir. Sabit bir düzen, saldırgan tarafından kolayca atlatılır; bu yüzden savunucu rastgeleleştirir. Los Angeles Havalimanı'nda kullanılan ARMOR sistemi (2007), kontrol noktalarını ve köpekli devriyeleri bu modelle planladı (Tambe, 2011).

3.6.4von Neumann'ın minimaks teoremi

Penaltı ve güvenlik örneklerinde karışık stratejilerle iki oyuncunun garantisi eşit çıktı. Bu bir rastlantı değildir. Teoremi yazmak için beklenen kazancın matris gösterimi gerekir. Satır oyuncusunun karışık stratejisi bir olasılık vektörü x = (x₁, …, x_m), sütun oyuncusununki y olsun. Ay vektörünün her öğesi bir satırın y'ye karşı beklenen kazancıdır; x^TAy ise bu satır beklentilerinin x'in olasılıklarıyla tartılmış toplamıdır, yani satır oyuncusunun beklenen kazancıdır. (x^T, x'in satır vektörü olarak yazıldığını gösterir.)

Sol taraf, satır oyuncusunun karışık stratejilerle garanti edebileceği en büyük kazançtır; sağ taraf, sütun oyuncusunun garanti edebileceği en küçük kayıptır. Saf stratejilerde aralarında boşluk olabiliyordu (penaltıda 70 ile 90); karışık stratejilerde boşluk her zaman kapanır. Teoremin sonuçları şunlardır:

• Denge = minimaks stratejileri. (x*, y*) bir Nash dengesidir ancak ve ancak x* bir maksimin, y* bir minimaks stratejisidir. Tüm dengelerde satır oyuncusunun kazancı aynıdır: v.
• Değiştirilebilirlik (interchangeability). (x, y) ve (x′, y′) iki dengeyse (x, y′) de dengedir. Çünkü x bir maksimin, y′ bir minimaks stratejisidir ve birinci sonuca göre böyle her çift bir dengedir. Oyuncuların hangi dengeyi oynayacaklarını koordine etmeleri gerekmez; sıfır toplamlı oyunda denge seçimi sorunu yoktur.
• Doğrusal programlama. Satır oyuncusu, her sütuna karşı en az v alacağı bir x karışımını ve olabilecek en büyük v'yi arar: v'yi en büyük yap; koşullar: her sütun j için Σ_i x_i A[i][j] ≥ v, Σ_i x_i = 1, her x_i ≥ 0. Bütün koşullar doğrusal olduğu için bu bir doğrusal programdır ve bilgisayar onu polinom zamanda çözer.
• Öğrenme bağlantısı. Oyuncular oyunu tekrar tekrar oynayıp geçmişte iyi giden stratejilerin ağırlığını artırarak öğrenirse, ortalama stratejileri minimaks stratejilerine yaklaşır.

Nash'in teoremi, minimaks teoreminin sıfır toplamlı olmayan n kişilik oyunlara genellemesi olarak görülebilir. Ancak genelleme bedelsiz değildir. Genel oyunda “değer” tek değildir (Cinsiyetler Savaşı'nda dengeler farklı kazançlar verir), değiştirilebilirlik bozulur (bir oyuncu bir dengenin, öteki başka bir dengenin stratejisini oynarsa sonuç denge olmayabilir) ve denge doğrusal programla bulunamaz.

3.6.5Kod izleme: maksimin()

Satır oyuncusunun yalnız iki satırı varsa (2 × n oyun), maksimin stratejisi grafik yöntemiyle kolayca bulunur. Satır oyuncusu ilk satırı p olasılıkla oynasın. Her sütun j, p'ye bağlı bir doğru verir: p · A[0][j] + (1 − p) · A[1][j]. Sütun oyuncusu her p'ye en kötü sütunla cevap verir; bu yüzden satır oyuncusunun garantisi bu doğruların alt zarfıdır: g(p) = min_j [p · A[0][j] + (1 − p) · A[1][j]]. Alt zarf parça parça doğrusal olduğu için en yüksek noktası ya uçlarda (p = 0, p = 1) ya da iki doğrunun kesişiminde bulunur. Fonksiyon bu adayları toplar ve en iyisini seçer.

from fractions import Fraction as F
def maksimin(A):                  # A: 2 x n
    n, aday = len(A[0]), [F(0), F(1)]
    for j in range(n):
        for k in range(j + 1, n):
            d = A[0][j] - A[1][j] - A[0][k] + A[1][k]
            if d != 0:
                aday.append(F(A[1][k] - A[1][j], d))
    g = lambda p: min(p*a+(1-p)*b for a, b in zip(*A))
    p = max((c for c in aday if 0 <= c <= 1), key=g)
    return p, g(p)

İki doğrunun kesişimi şöyle bulunur. j ve k sütunlarının doğruları eşitlenir: p A[0][j] + (1 − p) A[1][j] = p A[0][k] + (1 − p) A[1][k]. Terimler düzenlenince p · d = A[1][k] − A[1][j] çıkar; burada d = A[0][j] − A[1][j] − A[0][k] + A[1][k]'dır. d = 0 ise doğrular paraleldir ve kesişmez. zip(*A) ifadesi, matrisin sütunlarını (a, b) çiftleri olarak verir: a ilk satırdaki, b ikinci satırdaki sayıdır.

Örnek matris A = [[4, 1, 3], [0, 3, 2]] olsun; sütunlar X, Y, Z'dir. Doğrular X: 4p, Y: p + 3(1 − p) = 3 − 2p, Z: 3p + 2(1 − p) = 2 + p'dir. Saf maksimin 1, minimaks 3'tür; eyer noktası yoktur.

En büyük garanti p = 1/2'de v = 2'dir. Z sütununun doğrusu bu noktada 2,5 verir ve zarfın üstünde kalır; sütun oyuncusu Z'yi hiç oynamaz. Minimaks tarafı da denetlenir: sütun oyuncusu X'i 1/3, Y'yi 2/3 olasılıkla oynarsa satır oyuncusunun ilk satırı 4/3 + 2/3 = 2, ikinci satırı 0 + 2 = 2 verir. Satır oyuncusu en fazla 2 alabilir. Maks-min = min-maks = 2'dir.

3.6.6Dengeyi hesaplamak ne kadar zor?

Bilgisayar biliminde bir problemin “verimli çözülebilir” sayılması, girdi büyüdükçe çalışma süresinin girdi boyutunun bir polinomu (örneğin n² ya da n³) kadar büyümesi demektir. Süre 2ⁿ gibi üstel büyüyorsa küçük bir büyüme bile hesaplamayı imkânsız kılar. Nash dengesi için tablo şöyledir:

Tablonun ilk iki satırı bu bölümde gördüğümüz yöntemlerdir ve verimlidir. Genel oyunlarda karışık denge bulmak için pratikte iki yöntem kullanılır. Destek sayımı (support enumeration), her oyuncu için olası bir destek kümesi tahmin eder ve kayıtsızlık denklemlerini çözer; bu, 3.4.5'teki yöntemin bütün destek çiftleri üzerinde denenmesidir. Lemke–Howson algoritması, bir başlangıç noktasından bir dengeye giden bir yolu izler. İki yöntem de pratikte çoğu zaman iyi çalışır, ama en kötü durumda üstel süre alır: destek kümelerinin sayısı stratejilerle birlikte üstel büyür.

Üç ve daha çok oyunculu oyunlarda bir sorun daha vardır: denge olasılıkları irrasyonel sayılar (örneğin √2 içeren sayılar) olabilir ve bilgisayarda tam olarak yazılamaz. İki kişilik oyunlarda kayıtsızlık denklemleri doğrusal olduğu için dengeler rasyoneldir (kesirlerle yazılır); üç oyuncuda denklemlerde olasılık çarpımları görülür ve kökler irrasyonel çıkabilir. Bu yüzden çok oyunculu oyunlarda ε-yaklaşık denge (ε-approximate equilibrium), yani hiçbir sapmanın en çok ε kazandırdığı bir profil aranır.

Tablonun son satırı, “herhangi bir” denge yerine “özel bir” dengeyi aramanın zorluğudur: en yüksek sosyal refahlı dengeyi bulmak ya da oyunun tek dengesi olup olmadığına karar vermek NP-zordur. İleri okuma için: sabit bir ε (örneğin 0,1) için iki kişilik oyunlarda yarı-polinom süreli bir algoritma vardır (Lipton, Markakis ve Mehta, 2003); çok oyunculu oyunlarda ise sabit ε için bile problem PPAD-zor kalır (Rubinstein, 2015).

3.6.7PPAD

Zor problemler denince akla genellikle NP-tamlık gelir. NP-tam problemler “çözüm var mı?” biçimindeki sorulardır (örneğin “bu çizgede tüm düğümleri bir kez dolaşan bir yol var mı?”). Nash dengesi için bu soru önemsizdir: Nash'in teoremi dengenin her zaman var olduğunu söyler, cevap her zaman “evet”tir. Bu yüzden NP-tamlık, çözümü garanti olan bu tür problemler için uygun bir ölçü değildir.

PPAD sınıfı (Papadimitriou, 1994) tam olarak bu durum için tanımlanmıştır. PPAD, çözümün var olduğu kesin bilinen, ama bulmak için çok uzun bir yolu adım adım izlemek gerekebilen problemlerin sınıfıdır. Adı da bu yapıdan gelir: Polynomial Parity Arguments on Directed graphs (yönlü çizgelerde polinom eşlik argümanları).

Şekil 3.26'daki benzetmeyi şöyle okuyabiliriz. Bir yolun başı bilinmektedir. Her düğümden bir sonrakine nasıl gidileceği kolayca hesaplanır. Yol sonsuz olamaz, çünkü düğüm sayısı sonludur; demek ki yolun bir sonu kesin vardır. Ama yol üstel uzunlukta olabilir ve sonuna yürümek astronomik zaman alabilir. Lemke–Howson algoritması tam olarak böyle bir yolu izler. Nash dengesi bulmak bu sınıfta tamdır, yani sınıfın en zor problemlerindendir. Sonuç olarak genel oyunlarda dengenin verimli bulunamayabileceği düşünülür. Bu durum kavramsal bir soru da doğurur: bir bilgisayar bile dengeyi hızlıca bulamıyorsa, gerçek oyuncular dengeyi “bulur” mu? Denge kavramının bir tahmin aracı olarak gücü, bu soruyla sınanır.

3.6.8Yaklaşık denge ve hesaplama araçları

Ölçekleme önemlidir: kazançlar 1000 ile çarpılırsa her sapma kazancı da 1000 ile çarpılır ve aynı profil için ε anlamsızlaşır. [0, 1] aralığında ε = 0,01, “hiçbir oyuncu sapmakla en büyük olası kazanç farkının %1'inden fazlasını kazanamaz” demektir. Gerçek zamanlı sistemler (reklam açık artırmaları, piyasalar) çoğu zaman bu kadarıyla yetinir.

Tam dengeyi bulmak zor olabilir, ama “neredeyse kimsenin sapmak istemediği” bir profil çoğu zaman hızlıca bulunur. Az sayıda stratejiyi eşit olasılıkla karıştıran basit profiller bile iyi yaklaşıklık verir (Lipton, Markakis ve Mehta, 2003). İki kişilik oyunlarda çok basit bir profil ½-yaklaşık dengedir (Daskalakis, Mehta ve Papadimitriou, 2006): satır oyuncusunun rastgele bir i satırı seçilir; sütun oyuncusu i'ye en iyi tepki olan j sütununu oynar; k, j'ye en iyi tepki olan satırdır; satır oyuncusu i ile k'yi yarı yarıya karıştırır.

Pratikte denge hesaplamak için hazır araçlar kullanılır. Python kütüphanesi Nashpy, iki kişilik oyunlar için destek sayımı ve Lemke–Howson algoritmasını sunar. Denetim oyunu Nashpy ile şöyle çözülür:

import nashpy as nash
A = [[2, 2], [0, 4]]    # işçi: Çalış / Kaytar
B = [[1, 2], [-1, -4]]  # müdür: Denetle / Denetleme
oyun = nash.Game(A, B)
for x, y in oyun.support_enumeration():
    print(x, y)  # [0.75 0.25] [0.5 0.5]

A işçinin, B müdürün kazanç matrisidir; satırlar Çalış/Kaytar, sütunlar Denetle/Denetleme'dir. nash.Game(A, B) oyunu kurar. support_enumeration() bütün destek çiftlerini dener ve bulduğu her dengeyi bir (x, y) çifti olarak verir. Çıktıdaki [0.75 0.25] işçinin (Çalış, Kaytar) olasılıklarıdır, yani p* = 3/4; [0.5 0.5] müdürün (Denetle, Denetleme) olasılıklarıdır, yani q* = 1/2. Oyunun saf dengesi olmadığı için başka çıktı yoktur. Sonuç, elle yapılan hesapla aynıdır. Gambit adlı araç da aynı işi (destek sayımı, Lemke–Howson, doğrusal programlama) bir arayüzle ve çok oyunculu oyunlar için yapar.

Nash dengesinin başka türleri de vardır. Korelasyonlu denge (3.5.7) bunlardan biriydi. Hamlelerin sırayla yapıldığı oyunlarda ise alt oyun mükemmel denge (subgame perfect equilibrium) kullanılır: oyun ağacında geriye doğru çıkarımla bulunur ve inandırıcı olmayan tehditleri dışarıda bırakır. Her alt oyun mükemmel denge bir Nash dengesidir; tersi doğru değildir.

3.7Tartışma ve kontrol listesi

Bölümün son kısmı, kavramın sınırlarını tartışır ve bir oyunu çözerken izlenecek adımları bir araya getirir.

Denge adil mi? Hayır, gerekmez. Denge yalnızca karşılıklı en iyi tepkidir. Cinsiyetler Savaşı'nda saf dengelerin kazançları eşit değildir; Mahkûmun İkilemi'nde ise herkes için daha iyi bir sonuç vardır. Adalet ile denge farklı kavramlardır. Bir sonucun denge olması, onun iyi ya da istenir olduğunu göstermez; yalnızca kendi kendini sürdürdüğünü gösterir.

İnsanlar rasyonel mi? Gerçek kararlar bilgi eksikliği, zaman baskısı, duygular ve sosyal normlardan etkilenir. Herbert Simon bu duruma sınırlı rasyonellik (bounded rationality) adını verdi. Tek seferlik Mahkûmun İkilemi deneylerinde katılımcıların yaklaşık yarısının işbirliği yapması bunun bir göstergesidir. Ancak model yine de değerlidir: stratejik bağımlılığı incelemek için açık ve kesin bir karşılaştırma noktası sunar. Gerçek davranış modelden saptığında, sapmanın nedeni (güven, itibar, adalet duygusu) ayrıca incelenebilir.

Etik sınırlar. Aldatma, manipülasyon, adil olmayan avantaj… “Kazanmak için her yol mubah mı?” sorusunun cevabını oyun kuramı vermez. Stratejik davranışın sınırlarını kurallar ve kurumlar çizer. Kuralları, istenen sonucun bir denge olacağı biçimde tasarlamak ise mekanizma tasarımının (mechanism design) konusudur. Bu bölümdeki örnekler bu fikrin ilk izlerini taşır: denetim oyununda cezayı artırmak denetim olasılığını değiştirdi, trafik ışığı ise çarpışmasız bir korelasyonlu denge kurdu.

Kontrol listesi. Bir oyunu adım adım çözmek için aşağıdaki sıra izlenir (Şekil 3.27).

1. Önce okuma. Kim satır, kim sütun? Hücrede ilk sayı kimin? Sayılar kazanç mı, maliyet mi (yıl, dakika)? Maliyetse eksi işaretle kazanca çevrilir.
2. Ele. Kesin baskılanan stratejiler yinelemeli olarak silinir. Karışımlar da denenir.
3. Altını çiz. Kalan oyunda en iyi tepkiler işaretlenir; iki işaretli hücreler saf dengelerdir.
4. Kayıtsızlık. Karışık denge kayıtsızlık denklemleriyle aranır; olasılıkların 0 ile 1 arasında olduğu denetlenir.
5. Doğrula. Her aday için sapma testi yapılır.
6. Say. Eşitliksiz oyunlarda denge sayısı genellikle tek sayıdır; çift sayıda denge bulunduysa bir denge atlanmış olabilir.
7. Sonra yazma. Her denge profil olarak yazılır: örneğin (Orta, Sol) = (3, 5). Karışık dengede iki oyuncunun olasılıkları ve beklenen kazançları verilir.

3.8Özet

• Nash dengesi, hiçbir oyuncunun ötekiler sabitken tek başına sapmakla kazancını artıramadığı strateji profilidir: u_i(s_i*, s_−i*) ≥ u_i(s_i, s_−i*). Denge kararlılık söyler; verimlilik ya da adalet söylemez (Mahkûmun İkilemi).
• En iyi tepki, ötekilerin seçimine karşı kazancı en büyük yapan stratejiler kümesidir. Denge, karşılıklı en iyi tepkidir. Matris oyunlarında saf dengeler, her sütunda satır oyuncusunun ve her satırda sütun oyuncusunun en büyük kazancı işaretlenerek O(mn) sürede bulunur; eşitlikte bütün en büyükler işaretlenir.
• Sürekli stratejilerde en iyi tepki türevle bulunur. Cournot (P = 12 − Y) dengesi 4'er birim ve 16'şar kârdır; kartel (3'er, 18'er) dengede değildir. Bertrand'da fiyat maliyete iner ve kâr sıfırdır.
• Kesin baskılanan strateji hiçbir inanca karşı en iyi tepki değildir. Yinelemeli kesin eleme hiçbir dengeyi silmez ve sıradan bağımsızdır; zayıf baskılananları silmek denge kaybettirebilir. Karışımlar da baskılayabilir.
• Karışık dengede desteğindeki her saf strateji eşit beklenen kazanç verir (kayıtsızlık ilkesi). Bu yüzden bir oyuncunun denge olasılığı rakibinin kazançlarından hesaplanır. Denetim oyununda (p*, q*) = (3/4, 1/2)'dir ve ceza değişince yalnız q* değişir.
• Nash'in varlık teoremi: sonlu her oyunun en az bir karışık dengesi vardır (Kakutani / Brouwer sabit noktası). Dejenere olmayan oyunlarda denge sayısı tektir (Wilson).
• Çoklu dengede kuram tek sonucu seçmeyebilir. Pareto baskınlık, risk baskınlık, odak noktası ve öğrenme farklı seçimler önerebilir (Geyik Avı'nda (G, G) Pareto baskın, (T, T) risk baskın). Baskın strateji dengeleri hatalara dayanıklıdır, koordinasyon dengeleri değildir.
• Korelasyonlu dengede bir aracının önerisine uymak herkesin çıkarınadır. Uyma kısıtları doğrusal olduğu için doğrusal programlamayla bulunur; trafik ışığı örneğinde kazanç 0'dır, karışık Nash dengesinde −1/10'dur.
• Sıfır toplamlı oyunlarda maks-min = min-maks = v'dir (von Neumann). Eyer noktası yoksa karışık stratejiler gerekir (penaltıda p* = 4/11, v ≈ %79,1); denge doğrusal programla bulunur ve dengeler değiştirilebilirdir.
• Karmaşıklık: iki kişilik genel oyunda karışık denge bulmak PPAD-tamdır; pratikte destek sayımı, Lemke–Howson ve ε-yaklaşık dengeler kullanılır.

3.9Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• Nash dengesi Nash equilibrium
• saf Nash dengesi pure Nash equilibrium
• strateji profili strategy profile
• strateji kümesi strategy set
• kazanç fonksiyonu payoff function
• normal form normal form
• tek taraflı sapma unilateral deviation
• Pareto optimal Pareto optimal
• en iyi tepki best response
• en iyi tepki eşlemesi best-response correspondence
• Cournot duopolü Cournot duopoly
• kartel cartel
• Bertrand paradoksu Bertrand paradox
• kesin baskılama strict dominance
• zayıf baskılama weak dominance
• baskın strateji dominant strategy
• baskın strateji dengesi dominant-strategy equilibrium
• yinelemeli eleme IESDS
• ortak bilgi common knowledge
• karışık strateji mixed strategy
• destek support
• beklenen kazanç expected payoff
• kayıtsızlık ilkesi indifference principle
• denetim oyunu inspection game
• Nash'in varlık teoremi Nash's existence theorem
• sabit nokta teoremi fixed-point theorem
• tek sayılılık teoremi oddness theorem
• dejenere oyun degenerate game
• çoklu denge multiple equilibria
• denge seçimi equilibrium selection
• Pareto baskınlık Pareto dominance
• risk baskınlık risk dominance
• odak noktası focal point
• korelasyonlu denge correlated equilibrium
• sıfır toplamlı oyun zero-sum game
• maksimin maximin
• minimaks minimax
• eyer noktası saddle point
• oyunun değeri value of the game
• minimaks teoremi minimax theorem
• değiştirilebilirlik interchangeability
• güvenlik oyunu security game
• doğrusal programlama linear programming
• destek sayımı support enumeration
• Lemke–Howson algoritması Lemke–Howson algorithm
• PPAD-tam PPAD-complete
• ε-yaklaşık denge ε-approximate equilibrium

3.10Kendini Dene

1. Hücrelerde (u₁, u₂): (Üst, Sol) = (3, 2), (Üst, Sağ) = (1, 1), (Alt, Sol) = (0, 0), (Alt, Sağ) = (2, 3). Oyunun bütün Nash dengeleri nelerdir? Karışık dengede iki oyuncunun beklenen kazancı kaçtır?

   Cevap

   Satır en iyileri: Sol → Üst (3 > 0), Sağ → Alt (2 > 1). Sütun en iyileri: Üst → Sol (2 > 1), Alt → Sağ (3 > 0). Saf dengeler (Üst, Sol) ve (Alt, Sağ)'dır. Karışık denge: satır oyuncusunun kayıtsızlığı 3q + 1(1 − q) = 0 · q + 2(1 − q), yani 1 + 2q = 2 − 2q ve q = P(Sol) = 1/4. Sütun oyuncusunun kayıtsızlığı 2p + 0 = 1 · p + 3(1 − p), yani p = P(Üst) = 3/4. Beklenen kazançlar: satır 3 · ¼ + 1 · ¾ = 3/2, sütun 2 · ¾ = 3/2. Toplam üç denge vardır (tek sayı kuralına uygun).

2. Satırlar Üst, Orta, Alt; sütunlar Sol, Sağ. (Üst, Sol) = (2, 1), (Üst, Sağ) = (1, 3), (Orta, Sol) = (3, 0), (Orta, Sağ) = (2, 1), (Alt, Sol) = (1, 2), (Alt, Sağ) = (0, 0). Kesin baskılanan stratejiler yinelemeli olarak silinince ne kalır?

   Cevap

   Orta, Üst'ü her sütunda yener (3 > 2, 2 > 1): Üst silinir. Orta, Alt'ı da yener (3 > 1, 2 > 0): Alt silinir. Yalnız Orta satırı kalınca sütun oyuncusu Sol'da 0, Sağ'da 1 alır: Sol silinir. Kalan (Orta, Sağ) = (2, 1) oyunun tek Nash dengesidir. Dikkat: başta sütunlar arasında baskılama yoktur (Üst satırında Sağ 3 > 1, ama Alt satırında Sol 2 > 0).

3. Satır oyuncusunun kazançları: Üst (Sol 5, Sağ 0), Orta (2, 2), Alt (0, 5). Orta'yı bir saf strateji baskılar mı? Üst'ü p, Alt'ı 1 − p olasılıkla karıştıran strateji hangi p değerlerinde Orta'yı kesin baskılar?

   Cevap

   Saf strateji baskılamaz: Orta, Sol'da Alt'tan (2 > 0), Sağ'da Üst'ten (2 > 0) iyidir. Karışım Sol'a karşı 5p, Sağ'a karşı 5(1 − p) verir. Kesin baskılama için 5p > 2 ve 5(1 − p) > 2 gerekir, yani 2/5 < p < 3/5. Örneğin ½–½ karışımı her sütunda 2,5 verir.

4. Cournot duopolünde fiyat P = 18 − (y₁ + y₂), maliyet 0'dır. Nash dengesindeki miktarlar, fiyat ve kârlar nedir? Firmalar üretimi eşit bölen bir kartel kursa her biri ne kazanır ve kartelden sapan firma ne kazanır?

   Cevap

   Kâr y₁(18 − y₁ − y₂); türev 18 − 2y₁ − y₂ = 0 ⇒ BR₁(y₂) = (18 − y₂)/2. Simetrik denge: 2y = 18 − y ⇒ y* = 6, fiyat 6, kâr 36'şar. Kartel toplam Y(18 − Y)'yi Y = 9'da en büyük yapar: 4,5'er üretim, fiyat 9, kâr 40,5'er. Rakip 4,5 üretirken en iyi tepki (18 − 4,5)/2 = 6,75'tir ve sapan firma 6,75 · 6,75 = 45,5625 kazanır. Kartel dengede değildir.

5. Sıfır toplamlı oyunda satır oyuncusunun kazanç matrisi A = [[5, 1], [2, 4]]'tür. Saf maksimin ve minimaks nedir? Eyer noktası yoksa iki oyuncunun minimaks stratejileri ve oyunun değeri nedir?

   Cevap

   Satır en küçükleri 1, 2 ⇒ maksimin 2; sütun en büyükleri 5, 4 ⇒ minimaks 4. 2 < 4, eyer noktası yoktur. Satır oyuncusu ilk satırı p ile oynarsa sütunlara karşı 5p + 2(1 − p) = 2 + 3p ve p + 4(1 − p) = 4 − 3p alır; eşitlik p = 1/3, v = 3. Sütun oyuncusu ilk sütunu q ile oynarsa 5q + 1(1 − q) = 2q + 4(1 − q) ⇒ q = 1/2 ve yine 3 verir.

6. Tek bekçi iki hedeften birini korur. Hedef H'nin değeri 5, hedef L'nin değeri 3'tür; korunmayan hedefe saldıran değerini kazanır, korunana saldıran 0 alır. Bekçi H'yi hangi olasılıkla korumalıdır ve saldırgan ne kazanır? Bekçi hep H'yi korusaydı ne olurdu?

   Cevap

   Saldırganı kayıtsız bırakmak için 5(1 − p) = 3p ⇒ p = 5/8. Saldırganın kazancı 3 · 5/8 = 15/8 ≈ 1,9'dur. Bekçi hep H'yi korusaydı saldırgan L'ye saldırıp 3 alırdı.

7. Geyik Avı'nın bir sürümünde birlikte geyik 5'er kazandırır, tavşan her durumda 2 kazandırır, geyiğe yalnız giden 0 alır. Karışık dengede geyik olasılığı nedir? Hangi denge Pareto baskın, hangisi risk baskındır?

   Cevap

   Ortak Geyik'i q ile seçiyorsa Geyik 5q, Tavşan 2 verir: q = 2/5. (G, G) Pareto baskındır (5 > 2). Sapma kayıpları çarpımı (G, G)'de (5 − 2)² = 9, (T, T)'de (2 − 0)² = 4'tür; (G, G) risk baskın da olur. Bu sürümde iki ölçüt aynı dengeyi seçer; ortağın yalnız %40 olasılıkla gelmesi geyiği seçmeye yeter.

8. Kavşaktaki Tavuk oyununda ((Kır, Kır) = (0, 0), (Kır, Düz) = (−1, 1), (Düz, Kır) = (1, −1), (Düz, Düz) = (−10, −10)) bir ışık yarı yarıya (Kır, Düz) ya da (Düz, Kır) önerir. Bu bir korelasyonlu denge midir? Işık bunun yerine yarı yarıya (Kır, Kır) ya da (Düz, Düz) önerseydi ne olurdu?

   Cevap

   İlk ışık bir korelasyonlu dengedir. “Kır” önerisi alan sürücü rakibe kesin “Düz” denildiğini bilir: uyarsa −1, saparsa −10 alır. “Düz” önerisi alan rakibe kesin “Kır” denildiğini bilir: uyarsa 1, saparsa 0 alır. Beklenen kazanç 0'dır. İkinci ışık korelasyonlu denge değildir: “Düz” önerisi alan sürücü rakibin de düz gideceğini bilir; uyarsa −10, Kır'a saparsa −1 alır ve sapar.

3.11İleri okuma

• M. J. Osborne, An Introduction to Game Theory (2004), Bölüm 2–4: Nash dengesi, karışık strateji ve baskılama konularını çok sayıda çözülmüş örnekle, az matematikle anlatır.
• T. Roughgarden, Twenty Lectures on Algorithmic Game Theory (2016), Ders 13, 18 ve 20: denge kavramlarının hiyerarşisini, minimaks teoreminin öğrenmeyle ispatını ve PPAD'i bilgisayar bilimi bakışıyla sunar.
• A. R. Karlin ve Y. Peres, Game Theory, Alive (2017): sıfır toplamlı oyunları ve Nash teoreminin sabit nokta ispatını öğrenci düzeyinde ayrıntılı verir.
• C. Daskalakis, P. Goldberg ve C. Papadimitriou, “The complexity of computing a Nash equilibrium” (2009): Nash dengesi bulmanın PPAD-tamlığını gösteren makalenin dergi sürümüdür; girişi teknik ayrıntıya girmeden okunabilir.

3.12Kaynaklar

1. R. J. Aumann, “Subjectivity and correlation in randomized strategies”, Journal of Mathematical Economics 1(1), 67–96, 1974.
2. X. Chen, X. Deng, “Settling the complexity of two-player Nash equilibrium”, IEEE FOCS, 2006.
3. V. Conitzer, T. Sandholm, “New complexity results about Nash equilibria”, Games and Economic Behavior 63(2), 621–641, 2008.
4. C. Daskalakis, P. Goldberg, C. Papadimitriou, “The complexity of computing a Nash equilibrium”, SIAM J. Computing 39(1), 2009 (konferans sürümü ACM STOC, 2006).
5. C. Daskalakis, A. Mehta, C. Papadimitriou, “A note on approximate Nash equilibria”, WINE, LNCS 4286, 297–306, 2006.
6. D. Easley, J. Kleinberg, Networks, Crowds, and Markets, Cambridge, 2010 (Bölüm 6: Oyunlar).
7. K. Etessami, M. Yannakakis, “On the complexity of Nash equilibria and other fixed points”, SIAM J. Computing 39(6), 2010 (konferans sürümü IEEE FOCS, 2007).
8. I. Gilboa, E. Zemel, “Nash and correlated equilibria: Some complexity considerations”, Games and Economic Behavior 1(1), 80–93, 1989.
9. J. C. Harsanyi, R. Selten, A General Theory of Equilibrium Selection in Games, MIT Press, 1988.
10. A. R. Karlin, Y. Peres, Game Theory, Alive, AMS, 2017.
11. R. J. Lipton, E. Markakis, A. Mehta, “Playing large games using simple strategies”, ACM EC, 2003.
12. J. F. Nash, “Equilibrium points in n-person games”, PNAS 36(1), 1950.
13. J. F. Nash, “Non-cooperative games”, Annals of Mathematics 54(2), 1951.
14. N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani (ed.), Algorithmic Game Theory, Cambridge, 2007 (Bölüm 1–3).
15. M. J. Osborne, An Introduction to Game Theory, Oxford University Press, 2004 (Bölüm 2–4).
16. I. Palacios-Huerta, “Professionals play minimax”, Review of Economic Studies 70(2), 395–415, 2003.
17. C. H. Papadimitriou, “On the complexity of the parity argument and other inefficient proofs of existence”, Journal of Computer and System Sciences 48(3), 498–532, 1994.
18. T. Roughgarden, Twenty Lectures on Algorithmic Game Theory, Cambridge, 2016 (Ders 13, 18 ve 20).
19. A. Rubinstein, “Inapproximability of Nash equilibrium”, ACM STOC, 2015.
20. D. Sally, “Conversation and cooperation in social dilemmas: a meta-analysis of experiments from 1958 to 1992”, Rationality and Society 7(1), 1995.
21. T. C. Schelling, The Strategy of Conflict, Harvard University Press, 1960.
22. M. Tambe, Security and Game Theory, Cambridge University Press, 2011.
23. J. von Neumann, “Zur Theorie der Gesellschaftsspiele”, Mathematische Annalen 100, 1928.
24. R. Wilson, “Computing equilibria of n-person games”, SIAM J. Applied Mathematics 21, 1971.

Ders sayfaları: Roughgarden CS364A · Shah CSC304 · Araçlar: Gambit, Nashpy · © Sercan Külcü. Tüm hakları saklıdır.