Bölüm 2: Oyunlar ve Temsiller

2.1Temel kavramlar

Bu bölümün ilk kısmı, bir oyunu oluşturan parçaları tek tek tanımlar. Parçalar basit görünür, ama sonraki bütün hesaplar bu tanımların üzerine kurulur. Bir kavram eksik ya da yanlış tanımlanırsa, örneğin strateji ile eylem karıştırılırsa, sonraki hesapların hepsi yanlış çıkar. Bu yüzden kavramlar önce küçük bir oyun üzerinden somutlaştırılır, sonra biçimsel olarak yazılır.

2.1.1Bir oyunla başlangıç: 2/3 ortalaması

Bir sınıftaki herkes 0 ile 90 arasında gizlice bir sayı yazar. Sayı tam ya da ondalıklı olabilir. Bütün tahminlerin ortalaması hesaplanır ve bu ortalamanın 2/3'ü hedef olarak alınır. Hedefe en yakın tahmini yazan kazanır; birden çok kişi aynı uzaklıktaysa ödül paylaşılır. Bu oyuna 2/3 ortalaması oyunu (guess 2/3 of the average) denir.

Oyunun ilginç yanı, doğru cevabın başkalarının ne yazacağına bağlı olmasıdır. Tek başına düşünen biri “sayılar 0 ile 90 arasında rastgele dağılırsa ortalama 45 olur, 45'in 2/3'ü 30'dur; o hâlde 30 yazarım” diyebilir. Ama aynı akıl yürütmeyi başkaları da yapıyorsa çoğu kişi 30 yazar; o zaman ortalama 30'a yakın, hedef 20'ye yakın olur. Bunu da öngören biri 20 yazar. Her adım, ötekilerin bir adım önceki düşüncesine verilen bir cevaptır.

Şekil 2.1'de sekiz oyuncunun tahminleri bir sayı doğrusu üzerinde gösterilir. Tahminlerin toplamı 360 olduğundan ortalama 360 / 8 = 45'tir. Hedef 45'in 2/3'ü, yani 30'dur. Tam 30 yazan oyuncu yeşil noktadır ve kazanır. Bu sekiz kişinin tahminleri farklı olsaydı ortalama ve hedef de değişirdi. Kazanan sayı oyunun kurallarından değil, oyuncuların birlikte yaptığı seçimlerden çıkar.

Bu küçük oyun, bölümün neredeyse bütün sorularını içinde taşır. Oyuncular kimdir? Her oyuncunun seçenekleri nelerdir? Her seçim kime ne kazandırır? Oyuncular birbirinin ne kadar akıllı olduğunu biliyor mu? “Herkes çok akıllıysa” hangi sayı kazanır? Gerçek bir sınıfta hangi sayı kazanır? Bu soruların ilk dördü oyunun tanımına, son ikisi oyunun çözümüne aittir. Bu oyunun çözümü 2.6'da ayrıntılı olarak yapılır; şimdilik soruları sormak yeterlidir.

2.1.2Oyun kuramı nedir?

Oyun kuramı (game theory), karar vericilerin stratejik etkileşim içinde olduğu durumları inceleyen matematiksel bir araçtır. Stratejik etkileşim kısaca şöyle özetlenir: benim en iyi kararım, senin ne yapacağına bağlıdır; seninki de benimkine. Tek kişilik karar probleminde karar verici yalnız doğaya ya da şansa karşı oynar. Oyunda ise karşıda, kendisi de düşünen ve kendi çıkarını gözeten başka karar vericiler vardır.

Karar vericilere oyuncu (player) ya da ajan (agent) denir. Oyuncu bir insan, bir şirket, bir ülke, bir yazılım ya da bir ağ cihazı olabilir. Oyun kuramı, oyuncuların nasıl davrandığını ve sonucun nasıl şekillendiğini açıklamaya çalışır. Bunu yaparken oyuncuların rasyonel olduğu ve kendi çıkarlarına göre hareket ettiği varsayılır. Bu varsayımın tam anlamı 2.1.5'te açılır.

Kuram ekonomi, siyaset bilimi, biyoloji, psikoloji ve bilgisayar biliminde yaygın kullanılır. Üç örnek alan, kuramın ne tür sorulara cevap verdiğini gösterir:

• Ekonomi: Şirketlerin fiyat rekabeti, açık artırmalar ve pazarlık. Bir şirketin fiyatı, rakibin fiyatına göre anlam kazanır.
• Bilgisayar ağları: Her paketin ya da her sürücünün kendi yolunu seçtiği bencil yönlendirme. Herkes en hızlı yolu seçerse o yol tıkanabilir.
• Yapay zekâ: Çoklu ajan sistemleri, oyun oynayan programlar ve öğrenen ajanlar. Bir satranç programı rakibin en iyi cevabını hesaba katmadan hamle seçemez.

Algoritmik oyun kuramı (algorithmic game theory), klasik oyun kuramına bilgisayar biliminden gelen iki soru ekler. Birincisi hesaplamayla ilgilidir: bir oyunun dengesini hesaplamak ne kadar zordur, hangi algoritma bunu yapar? İkincisi tasarımla ilgilidir: bencil ajanlar arasında iyi sonuç veren kurallar, yani algoritmalar, protokoller ve açık artırmalar nasıl tasarlanır? Bu iki soru bölümün sonunda, 2.9'da yeniden ele alınır.

2.1.3Kısa tarihçe

Oyun kuramı yirminci yüzyılın başında satranç gibi oyunlarla ilgili matematiksel sorularla başladı. Yüzyılın ortasında ekonominin temel araçlarından biri oldu. Yüzyılın sonunda bilgisayar bilimiyle buluşarak algoritmik oyun kuramına dönüştü. Tablo 2.1 bu yolculuğun önemli duraklarını gösterir.

Tablodaki tarihler üç dönemi ayırır. 1913–1944 arası, kuramın matematiksel temellerinin atıldığı dönemdir. Zermelo'nun satranç sonucu ve von Neumann'ın minimaks teoremi bu dönemin iki büyük sonucudur; ikisi de bu notta yeniden karşımıza çıkar (2.2.8 ve 2.7.1). 1950–1994 arası, kuramın genel oyunlara ve ekonomiye yayıldığı dönemdir. Nash'in denge kavramı bu dönemin merkezindedir. 1999'dan sonrası ise bilgisayar biliminin iki sorusunu, yani “dengeyi hesaplamak ne kadar zor?” ve “iyi kurallar nasıl tasarlanır?” sorularını kuramın merkezine taşır.

Mahkûmun İkilemi'nin doğuşu da bu tabloda görünür. 1950'de RAND şirketinde Merrill Flood ve Melvin Dresher, iki kişiye aynı oyunu art arda oynatarak oyuncuların kuramın öngördüğü gibi davranıp davranmadığını sınadı. Aynı yıl Albert Tucker, bu oyunun yapısını iki mahkûmun hikâyesiyle anlattı ve oyun bu adla tanındı. Hikâye 2.4.2'de ayrıntılı olarak anlatılır.

2.1.4Bir oyunun bileşenleri

Bir oyun, oyuncuların etkileşime girdiği ve her birinin seçiminin herkesin kazancını etkilediği bir durumdur. Bir durumu oyun olarak yazmak için altı soruya cevap vermek gerekir. Tablo 2.2 bu altı bileşeni ve gösterimlerini listeler.

Gösterimdeki i harfi “herhangi bir oyuncu” anlamına gelir. S_i, oyuncu i'nin seçebileceği stratejilerin kümesidir; u_i ise oyuncu i'nin kazancını hesaplayan fonksiyondur. Kazanç fonksiyonunun içine bütün oyuncuların seçimleri yazılır, yalnız oyuncu i'ninki değil. Stratejik etkileşim tam olarak budur: oyuncu kendi kazancını tek başına belirleyemez.

2.1.5Oyuncular, rasyonellik ve ortak bilgi

Oyun kuramının oyuncular hakkında yaptığı üç varsayım vardır. Üçü de sade bir dille söylenebilir, ama her birinin ince bir noktası vardır.

Rasyonellik tanımında iki önemli sözcük vardır. Birincisi “inançlarına göre” ifadesidir. Oyuncu ötekilerin ne yapacağını kesin olarak bilmez; onun hakkında bir tahmini, yani inancı vardır. Rasyonel oyuncu bu inanca göre en iyi seçimi yapar. İnanç yanlışsa sonuç kötü olabilir, ama seçim yine rasyoneldir. İkincisi “beklenen fayda” ifadesidir. Sonuç belirsizse oyuncu olası sonuçların faydalarını olasılıklarıyla tartıp toplar. Bu hesap 2.1.8'de ayrıntılı olarak yapılır.

Kendi çıkarı varsayımı çoğu zaman yanlış anlaşılır. Rasyonel, bencil demek değildir. Fayda fonksiyonu adalet, özgecilik ya da itibar kaygılarını da içerebilir. Kazancının bir kısmını gönüllü olarak bağışlayan biri, bağış yapmaktan fayda sağlıyorsa rasyoneldir. Kuram yalnızca şunu söyler: oyuncu neyi önemsiyorsa onu en iyi yapmaya çalışır. Neyin önemsendiği fayda fonksiyonuna yazılır. Sonuç ise hiçbir oyuncunun tek başına kontrol edemediği bir etkileşimin ürünüdür.

Ortak bilgi varsayımı en soyut olanıdır ve en çok 2/3 ortalaması oyununda işe yarar. Şekil 2.2, bu oyunda her bilgi düzeyinin hangi tahminleri elediğini gösterir.

Düzey 1'de yalnızca “herkes rasyonel” bilgisi vardır. Ortalama en fazla 90 olabileceğinden hedef en fazla 60'tır. 60'tan büyük bir sayı yazmak hiçbir durumda 60 yazmaktan daha iyi değildir; rasyonel oyuncu 60'ın üstünü yazmaz. Düzey 2'de herkes bunu bilir: kimsenin 60'ı aşmayacağını bilen biri ortalamanın en fazla 60, hedefin en fazla 40 olduğunu çıkarır. Düzey 3'te üst sınır 26,7'ye iner. Her düzey bir kat daha “herkes biliyor” ekler ve üst sınırı 2/3 ile çarpar. Ortak bilgi bu zincirin sonsuza dek sürmesidir ve sonunda yalnızca 0 kalır. Bu hesap 2.6.3'te kodla yapılır.

2.1.6Eylem ve strateji

Günlük dilde “eylem” ve “strateji” sözcükleri birbirinin yerine kullanılır. Oyun kuramında ikisi farklıdır ve bu fark özellikle sıralı oyunlarda önemlidir.

Eşzamanlı bir oyunda her oyuncu tek bir kez ve ötekini görmeden karar verir. Bu durumda strateji ile eylem aynı şeydir: Taş-Kağıt-Makas'ta “Taş” hem bir eylem hem de bir stratejidir. Fark, bir oyuncu ötekinin hamlesini gördükten sonra karar verdiğinde ortaya çıkar. O zaman oyuncunun planı, gördüğü her hamle için ayrı bir cevap içermelidir.

Şekil 2.3'te Ş2, Ş1'in fiyatını görüp yanıt verir. Ş2'nin iki karar düğümü vardır: biri Ş1'in 100 TL dediği, öteki 120 TL dediği durumdur. Her düğümde iki eylemden birini (100 ya da 120) seçer. Bir strateji, iki düğümün her biri için bir seçim yapmak demektir. Bu yüzden Ş2'nin strateji sayısı 2 · 2 = 4'tür: (100, 100), (100, 120), (120, 100) ve (120, 120). Oysa yalnız 2 eylemi vardır. Örneğin (120, 100) stratejisi şunu söyler: “Ş1 100 derse 120 derim, Ş1 120 derse 100 derim.”

Genel kural şöyledir: bir oyuncunun k karar düğümü varsa ve her düğümde m eylemden birini seçiyorsa, strateji sayısı m^k'dır. Ş2'nin 3 düğümü olsaydı strateji sayısı 2 · 2 · 2 = 8 olurdu. Bu sayı düğüm sayısıyla üstel olarak büyür. Bu yüzden büyük sıralı oyunları matris olarak yazmak pratik değildir; ağaç gösterimi (2.2.6) çok daha küçüktür.

Strateji, ötekilerin davranışına ilişkin beklentilere dayanır. Bir oyuncu bir planı seçerken ötekilerin ne yapacağını tahmin eder. Bu tahminin yanında, oyuncunun seçimini nasıl yaptığı da önemlidir. İki tür strateji vardır:

• Saf strateji (pure strategy): tek bir planı kesin olarak seçmek. Örnek: “her zaman Taş”.
• Karışık strateji (mixed strategy): saf stratejiler üzerinde bir olasılık dağılımı. Oyuncu hangi saf stratejiyi oynayacağını bir zar atarak belirler. Örnek: (Taş 1/3, Kağıt 1/3, Makas 1/3).

Karışık strateji ilk bakışta tuhaf görünebilir: rasyonel biri neden kararını zara bıraksın? Cevap, tahmin edilebilir olmanın bazı oyunlarda kaybettirmesidir. Taş-Kağıt-Makas'ta hep Taş diyen bir oyuncu, rakibi bunu fark edince hep kaybeder. Rastgele oynamak, rakibin sömürebileceği bir örüntü bırakmaz. Bu fikir 2.2.3'te sayılarla gösterilir.

2.1.7Kazanç ve fayda fonksiyonu

Kazanç (payoff), oyuncunun tüm oyuncuların seçtiği strateji profiline bağlı olarak elde ettiği değerdir. Kazancı ölçen fonksiyona fayda fonksiyonu (utility function) denir ve oyuncu i için u_i ile gösterilir. Oyuncular stratejilerini kazançlarını maksimize etmek için seçer.

Kazanç para, puan ya da memnuniyet düzeyi olabilir. Bazen kazanç kötü bir şeyin eksi işaretlisidir: hapis yılı ya da bekleme süresi gibi maliyetlerde az olan iyidir, bu yüzden kazanç olarak −(hapis yılı) yazılır. Böylece “büyük sayı iyidir” kuralı bütün oyunlarda geçerli kalır. Karışık stratejilerde ise sonuç belirsiz olduğu için oyuncu beklenen kazancını (expected payoff) hesaplar.

Şekil 2.4 kazancın neden bir profilin fonksiyonu olduğunu gösterir. Oyuncu 1 hep aynı eylemi, Kağıt'ı seçer. Ama kazancı rakibin seçimine göre +1, 0 ya da −1 olur. Bu yüzden kazanç yalnız Kağıt'a değil, (Kağıt, rakibin eylemi) çiftine bağlıdır. Gösterimle: u₁(Kağıt, Taş) = +1, u₁(Kağıt, Kağıt) = 0, u₁(Kağıt, Makas) = −1.

2.1.8Sıralı ve kardinal fayda

Fayda sayıları iki farklı anlamda kullanılabilir. Bu fark, hangi hesapların anlamlı olduğunu belirler.

Sıralı faydada sayıları sırayı bozmadan değiştirmek hiçbir şeyi değiştirmez. 3, 2, 0 yerine 30, 20, 0 yazılsa da Ayşe Opera'yı Futbol'a, Futbol'u Evde kalmaya tercih eder. Saf strateji analizi, baskınlık ve saf dengeler yalnızca “hangisi daha iyi?” sorusuna baktığı için bu değişiklikten etkilenmez.

Belirsizlik devreye girince durum değişir. Piyango (lottery), olası sonuçların olasılıklarıyla birlikte yazıldığı belirsiz bir seçenektir. “½ olasılıkla Opera, ½ olasılıkla Evde” bir piyangodur. Piyangonun değeri, sonuçların faydalarının olasılıklarla tartılmış toplamıdır ve bu toplam sayıların büyüklüğüne bağlıdır.

2.1.9Bilgi: kim neyi biliyor?

Her oyuncunun oyun, kazançlar ve yapılan hamleler hakkında sahip olduğu bilgi, stratejiyi ve sonucu doğrudan etkiler. Satrançta iki oyuncu da tahtanın tamamını görür. Pokerde ise rakibin kartları kapalıdır. Bu fark, iki oyunda iyi oynamanın neden çok farklı beceriler istediğini açıklar.

Oyun ağacında bilgi, bilgi kümesi (information set) ile gösterilir. Bilgi kümesi, sırası gelen oyuncunun birbirinden ayırt edemediği karar düğümlerinin kümesidir. Ağaçta bu düğümler kesikli bir çizgiyle birleştirilir. Oyuncu hangi düğümde olduğunu bilmediği için kümedeki bütün düğümlerde aynı eylemi seçmek zorundadır.

Şekil 2.5 üç durumu yan yana koyar. Solda her düğüm kendi başına bir bilgi kümesidir; oyuncu 2, oyuncu 1'in seçimini görür ve buna göre cevap verir. Ortada oyuncu 2'nin iki düğümü aynı bilgi kümesindedir. Oyuncu 1 bir seçim yapmıştır, ama oyuncu 2 bunu görmeden karar verir; bu, iki oyuncunun aynı anda karar vermesiyle aynı şeydir. Sağda ise ilk hamleyi Doğa (Nature) yapar: elin güçlü ya da zayıf olması bir şans olayıdır. Oyuncu 1 kendi elini görür, oyuncu 2 görmez. Oyuncu 2, oyuncu 1'in bahis yaptığını görür ama elin güçlü mü zayıf mı olduğunu bilmez.

Mükemmel bilgi, geçmişi görmek demektir; geleceği bilmek değil. Satranç oyuncusu rakibinin bir sonraki hamlesini bilmez, ama o ana kadar oynanan bütün hamleleri görür. Bu yüzden satranç mükemmel bilgili bir oyundur. Mükemmel bilgi ile tam bilgi (complete information) de farklıdır; tam bilgi, herkesin kazanç fonksiyonlarını bilmesidir. Bu ayrım 2.3.2'de açılır.

2.1.10Poker ve blöf

Texas Hold'em pokerinde her oyuncunun iki kapalı kartı vardır. Ortada herkesin görebildiği açık kartlar bulunur ve her oyuncu kendi kapalı kartlarıyla açık kartları birleştirerek en iyi eli oluşturmaya çalışır. Rakibin kapalı kartları görülmez: bilgi gizlidir. Güçlü bir eli olan oyuncu bile rakiplerin ellerini bahislerinden tahmin etmeye çalışır.

Bu oyunda rakibin davranışı, yani bahis yapması ya da beklemesi, eli hakkında bilgi taşır. Yalnızca güçlü elde bahis yapan bir oyuncu kolayca okunur: bahis yaptığında rakipler çekilir, beklediğinde rakipler saldırır. Blöf (bluff), elin gücünü gizlemek için yanıltıcı bir sinyal göndermektir: zayıf elde de bahis yapmak.

Oyun kuramı açısından blöf bir karışık stratejidir. Zayıf elde belirli bir olasılıkla bahis yapmak, rakibin oyuncuyu okumasını engeller. Olasılık çok düşükse oyuncu yine okunur; çok yüksekse rakip her bahsi görmeye başlar ve blöfler pahalıya patlar. Doğru olasılık, rakibin bahsi görmekle çekilmek arasında kararsız kalacağı noktadır. Bilgisayar poker programları bu dengeleri hesaplayarak oynar. Libratus adlı program 2017'de dört profesyonel oyuncuya karşı uzun bir maç serisini kazandı.

Poker örneği, bilginin oyunun yapısını nasıl değiştirdiğini gösterir. Satrançta “en iyi hamle” kavramı anlamlıdır, çünkü her şey açıktır. Pokerde ise tek bir en iyi hamle yoktur; en iyi davranış, hangi elde hangi olasılıkla ne yapılacağını söyleyen bir karışımdır.

2.2Oyunların temsili

Bir oyunu yazmanın iki temel yolu vardır. Normal form oyunu bir tablo, yani matris olarak yazar; oyuncuların aynı anda karar verdiği durumlar için doğaldır. Genişletilmiş form oyunu bir ağaç olarak çizer; hamlelerin sırasını ve her anda kimin neyi bildiğini gösterir. Bu kısım iki gösterimi tanımlar, örneklerle açıklar ve aynı oyunun iki gösterimde nasıl yazıldığını adım adım gösterir.

2.2.1Normal form

Tanımdaki “×” işareti Kartezyen çarpımdır: iki kümenin Kartezyen çarpımı, birinci kümeden bir eleman ile ikinci kümeden bir elemanın oluşturduğu bütün sıralı çiftlerin kümesidir. Örneğin S₁ = {Üst, Alt} ve S₂ = {Sol, Sağ} ise S₁ × S₂ = {(Üst, Sol), (Üst, Sağ), (Alt, Sol), (Alt, Sağ)} olur. Her çift bir strateji profilidir. Fayda fonksiyonunun tanımı u_i : S₁ × … × S_n → ℝ şunu söyler: u_i bir profili girdi olarak alır ve bir sayı verir. Girdi bütün oyuncuların seçimidir; yalnız oyuncu i'ninki değil.

İki oyunculu bir oyunda normal form bir kazanç matrisi (payoff matrix) ile yazılır. Satırlar oyuncu 1'in, sütunlar oyuncu 2'nin stratejileridir. Her hücrede iki sayı vardır: önce satır oyuncusunun, sonra sütun oyuncusunun kazancı, yani (u₁, u₂). Bu sıralama bütün not boyunca değişmez.

Şekil 2.6 bu okumayı somutlaştırır. Oyun G = (N, S₁, S₂, u₁, u₂), N = {1, 2} biçiminde yazılır. Dört profil vardır ve her biri bir hücredir. Vurgulu hücre (Üst, Sağ) = (1, 2) şu anlama gelir: oyuncu 1 Üst'ü, oyuncu 2 Sağ'ı seçtiğinde oyuncu 1 1 birim, oyuncu 2 2 birim kazanır. Oyuncu 1 yalnızca satırı seçebilir; hangi hücreye düşüleceğini oyuncu 2'nin sütunu belirler.

Normal form, oyuncuların eşzamanlı karar verdiği ya da birbirinin seçimini bilmeden karar verdiği durumları modeller. İki şirketin fiyatlarını aynı gün kapalı zarfla bildirmesi buna bir örnektir. Önemli olan zaman değil bilgidir: biri sabah, öteki akşam karar verse de, akşam karar veren sabahki kararı görmüyorsa oyun eşzamanlıdır.

2.2.2Taş-Kağıt-Makas normal formda

Taş-Kağıt-Makas'ta (TKM) iki oyuncu (n = 2) aynı anda Taş, Kağıt ya da Makas seçer. Taş makası, makas kağıdı, kağıt taşı yener. Kazanana +1, kaybedene −1, beraberlikte ikisine de 0 yazılır.

Şekil 2.7'deki matriste köşegen hücreler (Taş, Taş), (Kağıt, Kağıt), (Makas, Makas) beraberliktir: (0, 0). Öteki hücrelerde biri kazanır, öteki kaybeder. Örneğin (Kağıt, Taş) = (1, −1): satır oyuncusu Kağıt ile Taş'ı yener. Her hücrede iki sayının toplamı 0'dır.

Matrise dikkatle bakınca bir şey daha görülür: hiçbir hücrede iki oyuncu da seçiminden memnun kalmaz. Hep biri seçimini değiştirmek ister. (Taş, Makas) = (1, −1) hücresinde sütun oyuncusu Kağıt'a geçerse kazanır. (Kağıt, Kağıt) = (0, 0) hücresinde ikisi de Makas'a geçerek kazanabilir. Dokuz hücrenin hiçbiri bu “kimse değiştirmek istemez” testini geçmez. Bu gözlem, TKM'nin saf stratejilerde bir dengesi olmadığını söyler. Denge kavramı 2.4.1'de tanımlanır.

2.2.3Taş-Kağıt-Makas'ta strateji seçimi

TKM'yi tekrar tekrar oynayan bir oyuncu hangi kuralı izlemelidir? Üç olası kural karşılaştırılabilir.

1. Rastgele seçim. Her turda her sembol 1/3 olasılıkla seçilir. Bu strateji hiç sömürülemez: rakip ne yaparsa yapsın beklenen kazanç 0'dır. Örneğin rakip hep Taş derse oyuncunun kazancı 1/3 olasılıkla 0 (Taş), 1/3 olasılıkla +1 (Kağıt), 1/3 olasılıkla −1 (Makas) olur; ortalama 0'dır. Aynı hesap rakibin her seçimi için tekrarlanabilir.

2. Geçmişe göre seçim. “Rakip son turda Taş dediyse bu tur Kağıt de.” Bu kural, örüntülü oynayan bir rakibe karşı kazandırır. Ama kuralın kendisi de bir örüntüdür. Rakip bu kuralı fark ederse, son turda Taş deyip bu tur Makas diyerek oyuncuyu yener.

3. Dengesiz karışık strateji. Örneğin zamanın yarısında Kağıt, yarısında Makas.

Üç kuralın karşılaştırması bir ders içerir: basit bir oyunda bile strateji seçimi önemlidir. Tahmin edilemez olmak yetmez; doğru olasılıklarla tahmin edilemez olmak gerekir. TKM'de doğru olasılıklar 1/3'tür ve bu olasılıklar herhangi bir rakibe karşı 0 garanti eder.

2.2.4Sıfır toplamlı oyunlar

Sıfır toplamlı oyunda birinin kazancı, ötekinin kaybıdır. TKM, Yazı-Tura ve satranç (+1 / 0 / −1 puanlamasıyla) sıfır toplamlıdır. Bir puanın iki oyuncu arasında paylaşıldığı bir oyun da sabit toplamlıdır: biri 0,7 alırsa öteki 0,3 alır. Buna karşılık Mahkûmun İkilemi ve fiyat rekabeti sıfır toplamlı değildir; bu oyunlarda toplam kazanç sonuca göre değişir.

Sıfır toplamlı oyunda tek bir matris yeter, çünkü sütun oyuncusunun kazancı satır oyuncusununkinin eksi işaretlisidir. Satır oyuncusu kazancını büyütmek, sütun oyuncusu satır oyuncusunun kazancını küçültmek ister. Bu durumda iki doğal ölçüt ortaya çıkar. Maksimin (maximin): satır oyuncusu her satırın en kötü durumuna bakar ve en kötü durumu en iyi olan satırı seçer. Minimaks (minimax): sütun oyuncusu her sütunda satır oyuncusunun alabileceği en iyi sonuca bakar ve bunu en küçük yapan sütunu seçer. Oyun ağacındaki minimaks araması (2.7.2), aynı fikri sıralı oyunda yapraktan köke uygulayan algoritmadır.

Şekil 2.8 bu kısaltmayı gösterir. Üstteki tablo iki kazancı da yazar; alttaki A matrisi yalnızca satır oyuncusunun kazancını yazar. Sütun oyuncusunun kazancı her hücrede A'daki sayının eksi işaretlisidir. Bu kısaltma sıfır toplamlı olmayan oyunlarda yapılamaz, çünkü orada bir oyuncunun kazancı ötekininkinden çıkarılamaz.

Sıfır toplamlı oyunda ortak çıkar yoktur; oyun saf rekabettir. Sıfır toplamlı olmayan oyunlarda ise herkesin kazandığı ya da herkesin kaybettiği sonuçlar olabilir. İşbirliği ile rekabet bir aradadır; iletişim ve müzakere sonucu değiştirebilir. Ticaret müzakereleri ve iklim anlaşmaları bu tür oyunlardır: anlaşma sağlanırsa iki taraf da kazanır, sağlanamazsa iki taraf da kaybeder.

2.2.5Fiyat rekabeti oyunu

İki şirket aynı pazarda benzer bir ürün satar ve fiyatını aynı anda belirler: 100 TL ya da 120 TL. Ucuz olan müşteriyi kapar; ikisi de pahalı satarsa kâr marjı yüksek kalır. Tablo 2.4 kârları birim olarak verir.

İkisi de 100 TL derse 5'er, ikisi de 120 TL derse 6'şar birim kâr ederler. Biri 100, öteki 120 derse ucuz olan müşterilerin çoğunu alır ve 8 kazanır; pahalı olan yalnızca 1 kazanır.

Bu yapı, 2.4'te ayrıntılı incelenen Mahkûmun İkilemi'nin yapısıdır. Fiyat rekabeti oyunu sıfır toplamlı değildir: hücrelerdeki toplamlar 10, 9, 9 ve 12'dir. Toplamın en büyük olduğu hücre (120, 120)'dir, ama oyuncular oraya ulaşamaz.

2.2.6Genişletilmiş form

Normal form, kimin önce oynadığını göstermez. Sıralı etkileşimlerde (satranç, pazarlık, piyasaya giriş) sıra önemlidir: ikinci oynayan, birincinin hamlesini görerek karar verir. Bu durumları yazmanın doğal yolu oyun ağacıdır.

Şekil 2.9'da kök, Rakip'in karar düğümüdür. Rakip “Girme” derse oyun biter: Rakip 0 kazanır, Tekel pazarı tek başına tutar ve 2 kazanır. Rakip “Gir” derse sıra Tekel'e geçer. Tekel “Savaş” derse fiyat savaşı ikisine de zarar verir: (−1, −1). Tekel “Uzlaş” derse pazarı paylaşırlar: (1, 1). Ağaç, sırayı ve her karar anında kimin oynadığını açıkça gösterir. Bu oyunun çözümü 2.8.2'de yapılır.

2.2.7Normal formdan oyun ağacına

Eşzamanlı bir oyun da ağaç olarak çizilebilir. Bunun için ağaçta bilgi kümesi kullanılır. Fiyat rekabeti oyunu (Tablo 2.4) üzerinden dönüşüm adım adım şöyle yapılır:

1. Kök: Şirket 1'in kararı. Her dal bir eylemdir: 100 TL ya da 120 TL.
2. İkinci düzey: her dalın sonunda Şirket 2'nin bir karar düğümü vardır. O da 100 ya da 120 seçer.
3. Yapraklar: dört yol vardır ve her biri matrisin bir hücresine karşılık gelir. Örneğin 100–120 yolu (8, 1) hücresidir.
4. Bilgi kümesi: iki şirket fiyatı aynı anda belirlediği için Ş2, Ş1'in seçimini görmez. Ş2'nin iki düğümü kesikli bir çizgiyle aynı bilgi kümesine konur.

Şekil 2.10'daki ağaç, matrisle tam olarak aynı oyunu anlatır. Ağaç Ş1'i önce çizer, ama bu bir zaman sırası değildir; bilgi kümesi Ş2'nin Ş1'in seçimini bilmediğini söyler. Ş1'i yukarıya, Ş2'yi aşağıya koymak yerine tersini yapmak da aynı oyunu verirdi.

Bilgi kümesi kaldırılırsa oyun değişir. O zaman Ş2, Ş1'in fiyatını gördükten sonra karar verir: oyun artık sıralıdır.

Şekil 2.11'deki oyunda yapraklar aynıdır, ama Ş2'nin strateji sayısı değişmiştir. Eşzamanlı oyunda Ş2'nin iki stratejisi vardı (100 ya da 120), çünkü iki düğümünü ayırt edemiyordu ve ikisinde aynı şeyi seçmek zorundaydı. Sıralı oyunda iki düğüm ayrıdır ve Ş2'nin dört stratejisi vardır (Şekil 2.3). Bilgi, strateji kümesini doğrudan değiştirir.

2.2.8Satranç bir genişletilmiş form oyunudur

Satranç, genişletilmiş formun en tanınmış örneğidir. İki oyuncu sırayla hamle yapar; her hamle bir dal, her konum bir düğümdür. Oyun mükemmel bilgilidir: iki oyuncu da tahtayı ve bütün geçmiş hamleleri görür. Sonuç galibiyet, yenilgi ya da beraberliktir. Beraberlik pat, üç kez aynı konumun tekrarı ya da 50 hamle kuralıyla oluşabilir.

Ernst Zermelo 1913'te bu tür oyunlar için temel bir sonuç ispatladı.

Teorem, satrancın sonucunun “belirli” olduğunu söyler: iki taraf da hatasız oynarsa ya Beyaz kazanır, ya Siyah kazanır ya da oyun berabere biter. Ama hangisinin olduğu bilinmez, çünkü ağaç çok büyüktür. Şekil 2.12 bu büyüklüğü gösterir. İlk iki yarım hamlede 400 konum vardır. Her yarım hamlede ortalama 30 kadar seçenek olduğu ve oyunlar onlarca hamle sürdüğü için tüm ağaçtaki oyun sayısı yaklaşık 10¹²⁰'dir. Bu sayı, gözlemlenebilir evrendeki atom sayısından (yaklaşık 10⁸⁰) çok büyüktür.

Bu yüzden satranç programları ağacın yalnızca bir kısmını arar. Arama belirli bir derinlikte durur, oradaki konumlar bir değerlendirme fonksiyonuyla puanlanır ve gereksiz dallar budanır (minimaks ve budama). XOX, Nim ve “21'i Söyleme” gibi küçük oyunların ağacı ise tamamen çözülebilir. Bu oyunlar 2.7'de çözülür.

2.3Oyunların sınıflandırılması

Oyunlar çok çeşitlidir; her birini ayrı ayrı incelemek yerine ortak özelliklerine göre gruplamak işe yarar. Bir oyunun hangi gruba girdiği, hangi çözüm yönteminin kullanılacağını belirler. Örneğin sıralı ve mükemmel bilgili bir oyun geriye doğru çıkarımla çözülür; eşzamanlı bir oyun matris üzerinde en iyi tepkilerle çözülür.

2.3.1Altı boyut

Bir oyunu sınıflandırmak için altı soru sorulur. Her soru bir boyuttur ve her boyutun iki ucu vardır. Tablo 2.5 altı boyutu, her boyutta sorulan soruyu ve iki uca birer örneği verir.

Zamanlama. Eşzamanlı oyunda oyuncular birbirinin seçimini görmeden karar verir; kapalı zarfla teklif verilen bir ihale buna örnektir. Sıralı oyunda biri ötekinin hamlesini görerek oynar; piyasaya giriş oyununda Tekel, Rakip'in girdiğini gördükten sonra karar verir. 2.2.7'de görüldüğü gibi iki tür arasındaki fark bir bilgi kümesidir.

Anlaşma. İşbirlikçi oyunda (cooperative game) oyuncular bağlayıcı anlaşmalar yapabilir: verilen söz dışarıdan, örneğin bir sözleşme ve mahkeme ile uygulatılabilir. İşbirlikçi olmayan oyunda (non-cooperative game) böyle bir zorlama yoktur; oyuncular konuşabilir ama söz bağlayıcı değildir. İki tür oyunun analiz birimi de farklıdır. İşbirlikçi oyunda soru şudur: hangi grup, yani hangi koalisyon (coalition) birlikte hareket eder ve kazancı nasıl paylaşır? Shapley değeri ve çekirdek bu sorunun cevaplarıdır. İşbirlikçi olmayan oyunda analiz birimi tek oyuncudur ve temel kavram Nash dengesidir. “İşbirlikçi olmayan” adı oyuncuların hiç işbirliği yapmadığı anlamına gelmez: işbirliği ortaya çıkabilir, ama ancak her oyuncunun kendi çıkarına uygunsa.

Toplam kazanç. Sıfır toplamlı oyunda (2.2.4) birinin kazancı ötekinin kaybıdır; penaltı atışı buna örnektir: gol atıcıya kazanç, kaleciye kayıptır. İklim anlaşmasında ise herkesin kazandığı ya da herkesin kaybettiği sonuçlar vardır.

Simetri ve ufuk boyutları kısa bir biçimsel tanım ister; bunlar bir sonraki alt kısımda verilir. Bilgi boyutu 2.1.9'da tanımlandı: Connect Four'da iki oyuncu da tahtanın tamamını görür, pokerde rakibin kartları kapalıdır.

2.3.2Tam bilgi, simetri ve ufuk

Tam bilgi (complete information), mükemmel bilgiden ayrı bir kavramdır. Tam bilgide herkesin kazanç fonksiyonu herkesçe bilinir: her oyuncu, ötekilerin neyi ne kadar istediğini bilir. Bilinmiyorsa oyunda eksik bilgi (incomplete information) vardır. Açık artırmada her teklifçi, ötekilerin ürüne biçtiği değeri bilmez; bu bir eksik bilgi durumudur. Eksik bilgili oyunlar Bayesçi oyunlar (Bayesian games) olarak modellenir: her oyuncunun bilinmeyen özelliği bir olasılık dağılımından çekilmiş gibi düşünülür.

İki kavramın farkı şöyle özetlenebilir. Mükemmel bilgi, hamleler hakkındadır: geçmişte kim ne oynadı? Tam bilgi, oyunun kendisi hakkındadır: herkesin kazançları ne? Satranç hem mükemmel hem de tam bilgilidir. Taş-Kağıt-Makas tam bilgilidir (kazançlar herkesçe bilinir), ama mükemmel bilgili değildir (hamleler aynı anda yapılır).

Tanımdaki eşitlik dikkatle okunmalıdır: satır oyuncusu a'yı, sütun oyuncusu b'yi oynadığında satır oyuncusunun aldığı, roller değiştiğinde (satır b, sütun a) sütun oyuncusunun aldığına eşit olmalıdır. Matriste bu, (a, b) hücresindeki ilk sayının (b, a) hücresindeki ikinci sayıya eşit olması demektir.

Ufuk (horizon), oyunun kaç tur sürdüğüdür. Sonlu ufuklu oyunun belirli bir sonu vardır; kırkayak oyunu (2.8.5) dört hamlede biter. Sonsuz ufuklu oyunda ise oyunun ne zaman biteceği belli değildir; iki şirketin her ay yeniden fiyat belirlemesi böyledir. Sonsuz ufukta gelecek kazançlar bir iskonto faktörü (discount factor) δ ∈ (0, 1) ile tartılır ve oyuncunun toplam kazancı şöyle yazılır:

U = u₀ + δ u₁ + δ² u₂ + … = Σ_t δ^t u_t

Burada u_t, t. turun kazancıdır. δ küçükse gelecek az önemlidir: oyuncu sabırsızdır. δ 1'e yakınsa gelecek neredeyse bugün kadar önemlidir. δ'nın ikinci bir yorumu da vardır: her turdan sonra oyunun bir tur daha sürme olasılığı. Bu yorumda δ^t, oyunun t. tura ulaşma olasılığıdır.

2.3.3Bir oyunu sınıflandırmak

Altı boyut birbirinden bağımsızdır; bir oyun her boyutta ayrı ayrı konumlandırılır. Satranç örneğinde altı cevap şöyledir: sıralı (oyuncular sırayla oynar), işbirlikçi olmayan (bağlayıcı anlaşma yoktur), sıfır toplamlı (biri kazanırsa öteki kaybeder), simetrik değil (Beyaz önce oynar; ancak kurallar iki taraf için aynıdır), mükemmel bilgili (tahta açıktır) ve sonlu (beraberlik kuralları oyunun sonsuza dek sürmesini engeller).

2.4Denge ve Mahkûmun İkilemi

Bir oyunu yazmak, onu çözmek demek değildir. Oyunun “çözümü”, oyuncuların hangi stratejileri seçeceğine dair bir öngörüdür. Oyun kuramının en temel çözüm kavramı Nash dengesidir. Bu kısım kavramı sezgisel düzeyde tanıtır ve Mahkûmun İkilemi üzerinde denge ile verimlilik arasındaki farkı gösterir.

2.4.1En iyi tepki ve Nash dengesi

Tanım bir “pişmanlık testi” olarak okunabilir. Oyun oynandıktan sonra her oyuncuya şu soru sorulur: “Ötekilerin ne yaptığını bilseydin, kendi seçimini değiştirir miydin?” Herkesin cevabı “hayır” ise profil bir Nash dengesidir. Tek bir oyuncunun cevabı “evet” ise değildir.

İki oyunculu bir matriste en iyi tepkiler ve dengeler oklarla görselleştirilebilir. Her hücreden, oyunculardan birinin sapmak istediği yöne bir ok çizilir. Hiçbir okun çıkmadığı hücre dengedir.

Nash dengesinin söylediği şudur: ötekiler sabitken sapmak kazandırmaz; kimse pişman değildir. Denge kendi kendini sürdüren bir durumdur. Nash dengesinin söylemediği ise dengenin herkes için iyi olduğudur. Fiyat rekabetinde (120, 120) iki şirkete de 6 verirdi; denge ise 5'er verir. Mahkûmun İkilemi de aynı yapıdadır. Nash dengesinin biçimsel tanımı, varlığı ve hesaplanması ayrı bir konunun, Nash dengesi konusunun içeriğidir; burada kavramın sezgisi ve klasik örnekler üzerindeki kullanımı yeterlidir.

2.4.2Mahkûmun İkilemi: hikâye ve matris

İki şüpheli, Sam ve John, ayrı odalarda sorgulanır ve birbirleriyle konuşamazlar. Her birinin iki seçeneği vardır: sessiz kalmak ya da suç ortağını ele verip itiraf etmek. Tablo 2.7 dört durumdaki cezaları verir.

Terim birliği için iki adlandırma sabitlenir. İşbirliği, suç ortağıyla işbirliği yapmak, yani sessiz kalmaktır. İhanet ise itiraf etmektir (polisle işbirliği). Kısaca iki strateji “Sessiz” ve “İhanet” olarak yazılır.

Hapis yılı kötü bir şeydir; az olması iyidir. Kazanç olarak −(hapis yılı) yazılır: az ceza, büyük kazanç demektir. Tablo 2.8 oyunun kazanç matrisini verir. Her hücrede ilk sayı Sam'in (satır), ikinci sayı John'un (sütun) kazancıdır ve hücreler a, b, c, d olarak adlandırılmıştır.

Tablo şöyle okunur. İkisi de sessiz kalırsa (hücre a) ikisi de −1 alır. Sam sessiz kalıp John ihanet ederse (hücre b) Sam −3, John 0 alır: Sam 3 yıl yatar, John serbest kalır. Hücre c bunun tersidir. İkisi de ihanet ederse (hücre d) ikisi de −2 alır. Temel soru şudur: her mahkûm kendi cezasını en aza indirmek isterse ne olur?

2.4.3İhanet neden baskın?

Sam, John'un ne yapacağını bilmez. Bu yüzden iki durumu ayrı ayrı inceler. Bu yönteme durum analizi denir: rakibin her olası seçimi için en iyi cevap bulunur.

Baskın strateji varsa oyuncu ötekinin ne yapacağını tahmin etmek zorunda kalmaz. Sam'in John'un olasılıklarını bilmesi gerekmez; her durumda aynı cevap en iyidir. Bu, baskın stratejinin en güçlü yanıdır: rakip hakkında hiçbir inanç gerektirmez.

2.4.4İkilemin mesajı

Oyunun tek Nash dengesi (İhanet, İhanet) = (−2, −2)'dir. Bunu denetlemek kolaydır: d hücresinden Sam Sessiz'e geçerse −3 alır, John Sessiz'e geçerse −3 alır; ikisi de sapmaz. Öteki üç hücrede en az bir oyuncu ihanete geçerek kazanır. Buna karşılık (Sessiz, Sessiz) = (−1, −1) ikisi için de daha iyidir. Demek ki denge, ikisini birden daha iyi yapan bir sonuçtan kötüdür; 2.4.5'te tanımlanacak dille, denge Pareto optimal değildir.

Mahkûmlar sorgudan önce anlaşsa bile durum değişmez. Oyun işbirlikçi olmayan bir oyundur: anlaşma bağlayıcı değildir. “İkimiz de sessiz kalacağız” sözünden sonra John'un sessiz kalacağına inanan Sam, ihanet ederek 0 alır (−1 yerine). Her ikisi de sözünü bozmaya teşviklidir. Söz kazançları değiştirmediği için baskın stratejiyi de değiştirmez.

Oyunun mesajı şudur: herkesin kendi çıkarına rasyonel davranması, toplum için iyi sonucu garanti etmez. Bu, “görünmez el” fikrinin, yani bireysel çıkar peşindeki davranışların kendiliğinden toplumsal iyiliğe yol açtığı fikrinin her zaman geçerli olmadığını gösterir.

Mahkûmun İkilemi yapısı gündelik hayatta sık görülür:

• Fiyat savaşları: her şirket fiyat kırar, sonunda hepsinin kârı düşer (Tablo 2.4).
• Silahlanma yarışı: her ülke silahlanır, kimse daha güvende olmaz, hepsi daha yoksul olur.
• İklim anlaşmaları: her ülke emisyonu azaltmanın maliyetinden kaçınmak ister.
• Sporda doping: herkes doping yaparsa göreli sıra değişmez, ama herkesin sağlığı zarar görür.
• Ortak kaynakların aşırı kullanımı: balıkçılar stokun tükeneceğini bilse de daha çok avlanır.

İkilemden çıkış yolları da vardır. Birincisi tekrarlanan oyun ve itibardır: aynı oyuncular tekrar tekrar karşılaşırsa bugünkü ihanet yarın cezalandırılabilir. Tit-for-Tat (kısasa kısas) stratejisi ilk turda işbirliği yapar, sonra rakibin bir önceki hamlesini kopyalar. Sonsuz tekrarda işbirliğinin nasıl sürdüğü 2.8.8'de hesaplanır. İkincisi sözleşme ve teşvik tasarımıdır: kazançlar değiştirilirse, örneğin ihanete bir ceza eklenirse, ihanet baskın olmaktan çıkar. Oyunun kurallarını tasarlamak mekanizma tasarımının konusudur (2.9.3).

2.4.5Pareto optimallik

Nash dengesi bir kararlılık kavramıdır. Bir sonucun verimli olup olmadığını ölçmek için ayrı bir kavram gerekir. Bunun en zayıf ve en yaygın ölçütü Pareto optimalliktir.

Kazanç uzayında, yani her sonucun (u₁, u₂) noktası olarak çizildiği düzlemde, tanımın kolay bir görsel karşılığı vardır. Bir noktanın sağ üst çeyreği, iki oyuncuya da en az o kadar veren noktaların bölgesidir. Bu bölgede (noktanın kendisi dışında) başka bir sonuç yoksa nokta Pareto optimaldir.

Pareto optimallik adalet demek değildir. (S, İ) Pareto optimaldir, ama Sam 3 yıl yatarken John serbest kalır. Pareto optimallik yalnızca “boşa harcanan bir şey yok” der; kazancın nasıl dağıldığına bakmaz. Bir oyuncunun her şeyi aldığı, ötekinin hiçbir şey almadığı bir sonuç da Pareto optimal olabilir.

Denge (kararlılık) ile verimlilik ayrı sorulardır. Mahkûmun İkilemi bu iki sorunun farklı cevaplar verebileceğini gösterir: kararlı olan verimli değildir, verimli olan kararlı değildir. Aradaki kayıp, Anarşinin Bedeli (Price of Anarchy) ile ölçülür. Hapis yılları maliyet olarak sayılırsa dengede toplam maliyet 2 + 2 = 4 yıl, en iyi sonuçta (S, S) 1 + 1 = 2 yıldır; oran 4 / 2 = 2'dir. Bencil davranış, toplam maliyeti iki katına çıkarır.

2.5Klasik 2×2 oyunlar

İki oyuncunun ikişer stratejisi olan oyunlara 2×2 oyunlar denir. Matrisleri yalnızca dört hücreden oluşur, ama bu küçük oyunlar çok farklı stratejik durumları temsil eder: tam çatışma, güven sorunu, buluşma sorunu ve cesaret yarışı. Bu kısım altı klasik oyunu tanıtır, saf dengelerini bulur ve her birinin ne anlattığını yorumlar.

2.5.1Altı oyun ve saf dengeleri

Tablo 2.9 altı oyunu tek bir biçimde yazar. Her satırda bir oyun vardır. (1, 2) sütunu, satır oyuncusunun 1. eylemini, sütun oyuncusunun 2. eylemini oynadığı hücredir; hücrede önce satır oyuncusunun, sonra sütun oyuncusunun kazancı yazılır.

Saf dengeleri bulmanın düzenli bir yolu vardır: en iyi tepki işaretleme. Her sütunda satır oyuncusunun en büyük kazancı işaretlenir; bu, satır oyuncusunun o sütuna en iyi tepkisidir. Her satırda sütun oyuncusunun en büyük kazancı işaretlenir; bu da sütun oyuncusunun o satıra en iyi tepkisidir. İki işareti birden taşıyan hücre, iki oyuncunun da birbirine en iyi tepki verdiği hücredir, yani bir saf Nash dengesidir. Eşitlik varsa eşit en büyüklerin hepsi işaretlenir.

Geri kalan üç oyunun işaretlemesi aynı yolla yapılır. Cinsiyetler Savaşı'nda (Opera, Opera) = (3, 2) ve (Futbol, Futbol) = (2, 3) iki işaret taşır; köşegen dışı (0, 0) hücrelerinde ikisi de buluşma noktasına geçmek ister. Geyik Avı'nda (Geyik, Geyik) = (4, 4) ve (Tavşan, Tavşan) = (3, 3) dengedir: ötekinin Geyik avladığını bilen biri Geyik'ten 4, Tavşan'dan 3 alır; ötekinin Tavşan avladığını bilen biri Geyik'ten 0, Tavşan'dan 3 alır. Saf Koordinasyon'da (Parti, Parti) ve (Ev, Ev) dengedir.

2.5.2Çatışma mı, koordinasyon mu?

Altı oyun, iki oyuncunun çıkarlarının ne kadar örtüştüğüne göre bir yelpazeye dizilir. Bir uçta çıkarların tamamen zıt olduğu Yazı-Tura, öbür uçta hiç çatışma olmayan Saf Koordinasyon ve Bedava Para vardır.

Yazı-Tura Eşleştirme: tam çatışma. Çıkarlar tamamen zıttır ve oyun sıfır toplamlıdır. Her hücrede kaybeden sapar. Bir oyuncunun kestirilebilen her eğilimi sömürülür: eşleştiren biraz daha sık Yazı derse ayrıştıran Tura'ya kayar. Tek çıkış rastgele oynamaktır, yani karışık strateji (½–½). Penaltı atışı bu yapının gerçek hayattaki örneğidir: atıcı ve kaleci birbirini tahmin etmeye çalışır.

Tavuk: anti-koordinasyon. Oyuncular farklı eylemler seçmek ister: biri kırmalı, öteki düz gitmelidir. İki denge vardır ve her biri bir sürücüyü kayırır. Kim kazanır? Geri adım atamayacağını inandırıcı biçimde gösteren. Örneğin direksiyonunu pencereden atan bir sürücü, Düz git'ten başka seçeneği olmadığını gösterir; öteki sürücünün en iyi tepkisi kırmak olur. Bu tür bir davranışa taahhüt (commitment) denir. Taahhüt, seçenekleri azaltarak kazandırır; tek kişilik karar probleminde seçenek azalması hiç kazandırmazken oyunda kazandırabilir.

Cinsiyetler Savaşı: koordinasyon ve çatışma birlikte. İki kişi akşamı birlikte geçirmek ister; buluşmak ortak çıkardır. Ama biri Opera'yı (3 > 2), öteki Futbol'u (3 > 2) tercih eder; nerede buluşulacağı çatışmadır. Baskın strateji yoktur. Çözüm iletişim (“bu akşam operaya gidiyorum”), gelenek ya da sırayla seçmektir (bir hafta opera, bir hafta futbol).

Geyik Avı: güven ikilemi. İki avcı birlikte geyik avlarsa büyük ödül alır (4, 4). Biri tek başına tavşan avlarsa 3 alır; geyik peşindeki öteki eli boş kalır (0). (Geyik, Geyik) hem dengedir hem de Pareto optimaldir. Ama Tavşan her durumda 3 garanti eder: öteki ne yaparsa yapsın tavşan avcısı 3 alır. Geyik ise ötekine güvenmeyi gerektirir. Mahkûmun İkilemi'nden farkı şudur: Geyik Avı'nda işbirliği bir dengedir. Kimse işbirliğinden tek başına sapmak istemez; sorun sapma isteği değil, ötekinin sapacağı korkusudur (Skyrms, 2004).

Saf Koordinasyon: kötü denge de kalıcıdır. Çıkar çatışması yoktur: iki oyuncu da Parti'de buluşmayı tercih eder (10 > 5). Ama (Ev, Ev) de bir dengedir: ötekinin evde kalacağını bilen biri partiye gitmekle 0 alır, evde kalmakla 5. Kötü denge kendini sürdürür. Oyuncular çoğu zaman belirgin, “herkesin aklına gelecek” olana yönelir. Thomas Schelling bu tür seçimlere odak noktası (focal point) adını verdi (Schelling, 1960). Örneğin bir şehirde buluşma yeri söylenmemiş iki kişi, çoğu zaman şehrin en bilinen meydanına gider.

Bedava Para: zayıf denge. (Yazı, Yazı) kesin dengedir: sapan kaybeder. (Tura, Tura) zayıf dengedir: sapmak kazandırmaz, kaybettirmez de. Yazı zayıf baskındır; makul bir oyuncunun Tura'yı seçmesi için bir neden yoktur. Bu oyun, Nash dengesi tanımının “≥” işaretinin bazen akla yatkın olmayan dengeleri de içeri aldığını gösterir.

2.62/3 ortalaması oyunu

Bölümün başındaki oyun (2.1.1) artık çözülebilir. Oyunun iki farklı “cevabı” vardır. Biri kuramın cevabıdır: herkes tam rasyonel ve bu ortak bilgiyse ne olur? Öteki pratik cevaptır: gerçek bir sınıfta en iyi tahmin nedir? Bu kısım iki soruyu da cevaplar ve ikisinin neden farklı olduğunu açıklar.

2.6.1Seviye-k düşünme

Gerçek oyuncular sonsuz adım düşünmez; birkaç adımda dururlar. Bu davranışı modellemenin bir yolu seviye-k düşünmedir (level-k reasoning). Model, oyuncuları kaç adım düşündüklerine göre sınıflandırır.

“Ortalama 45 olur, 2/3'ü 30” akıl yürütmesi yalnızca seviye 1'dir. Başkalarının da 30 diyeceğini düşünen biri daha düşük bir sayı, örneğin 20 yazar. Herkesin fazla düşük yazacağını düşünen ise biraz yukarı kayabilir. Seviye k'nın tahmini genel olarak 45 · (2/3)^k'dır ve k büyüdükçe 0'a yaklaşır.

Önemli nokta şudur: en iyi tahmin, ötekilerin kaçıncı seviyede düşündüğüne dair inanca bağlıdır. Sınıfın çoğu seviye 1 ise en iyi cevap seviye 2'dir; daha fazla düşünmek kaybettirir. Seviye kavramı, ortak bilgideki “herkes biliyor” katlarını sayan bilgi düzeyiyle (Şekil 2.2) karıştırılmamalıdır. Seviye, bir oyuncunun kaç adım düşündüğüdür; bilgi düzeyi ise oyuncular hakkında neyin bilindiğidir.

2.6.2Kod izleme: seviye-k tahmini

Aşağıdaki Python kodu, sınıftaki seviyelerin dağılımına dair bir inanç verildiğinde her seviyenin hedefe ne kadar uzak kalacağını hesaplar.

def tahmin(k, L0=45):     # seviye-k
    g = L0
    for _ in range(k):
        g = g * 2 / 3
    return g
pay = {0: 0.3, 1: 0.4, 2: 0.3}   # inanç
ort = sum(p * tahmin(k) for k, p in pay.items())
hedef = ort * 2 / 3
for k in range(5):
    print(k, round(tahmin(k), 1),
          round(abs(tahmin(k) - hedef), 1))

Kod şöyle çalışır:

• tahmin(k, L0=45) seviye-k oyuncunun tahminini döndürür. g, 45 ile başlar ve döngü k kez çalışarak her seferinde g'yi 2/3 ile çarpar. k = 0 için döngü hiç çalışmaz ve 45 döner: seviye 0'ın ortalaması.
• pay sözlüğü inancı tutar: sınıfın %30'u seviye 0, %40'ı seviye 1, %30'u seviye 2.
• ort, beklenen ortalamadır: her seviyenin tahmini o seviyenin payıyla çarpılıp toplanır.
• hedef, ortalamanın 2/3'üdür; kazanan sayı budur.
• Son döngü seviye 0'dan 4'e kadar her seviyenin tahminini ve hedefe uzaklığını yazdırır.

Şekil 2.16 aynı sonucu sayı doğrusu üzerinde gösterir. Hedef (21), seviye 2'nin tahminine (20) çok yakındır. Seviye 3 ve 4 hedefin solunda, seviye 0 ve 1 sağında kalır. Hedefin yeri nüfusa bağlıdır: nüfusun daha büyük kısmı seviye 0 olsaydı hedef sağa kayardı.

2.6.3Yinelemeli eleme

Kuramın cevabı farklı bir yöntemle bulunur. Bu yöntem, hiçbir durumda iyi olamayacak tahminleri adım adım siler.

2/3 oyununda eleme şöyle işler. Başlangıçta her tahmin 0 ile 90 arasındadır ve hiçbir şey elenmemiştir.

1. Tur 1. Ortalama en fazla 90 olabilir, bu yüzden hedef en fazla 60'tır. 60'ın üstündeki her tahmin, hiçbir durumda 60 yazmaktan daha iyi değildir: hedef 60'ın altındaysa 60 ona daha yakındır. Bu tahminler elenir.
2. Tur 2. Herkes rasyonel ve bunu herkes biliyor: kimse 60'ı aşmaz. Ortalama ≤ 60 ⇒ hedef ≤ 40. 40'ın üstü elenir.
3. Tur 3. Ortalama ≤ 40 ⇒ hedef ≤ 26,7. Bu turu atmak için “herkesin, herkesin rasyonel olduğunu bildiğini” bilmek gerekir.
4. Tur 4–6. Ortalama ≤ 26,7 ⇒ hedef ≤ 17,8; ortalama ≤ 17,8 ⇒ hedef ≤ 11,9; ortalama ≤ 11,9 ⇒ hedef ≤ 7,9.

Her turda üst sınır 2/3 ile çarpılır; k tur sonra üst sınır 90 · (2/3)^k'dır. Aşağıdaki kod bu çarpımı altı tur yapar.

ust = 90                # olası en büyük tahmin
for tur in range(1, 7):
    # ortalama ≤ ust  ⇒  hedef ≤ (2/3)·ust
    ust = ust * 2 / 3
    print(tur, round(ust, 1))
# ust = 90·(2/3)^k → 0 : tek denge herkes 0

Kodda ust değişkeni, “anlamlı en büyük tahmin”i tutar. Döngünün her turunda yorum satırındaki çıkarım uygulanır: ortalama ust'u aşamıyorsa hedef (2/3)·ust'u aşamaz. Yeni ust bu değerdir. Döngü 6 turda durur, ama süreç kuramda sonsuza dek sürer.

Üst sınır geometrik olarak küçülür: her tur bir öncekinin 2/3'ü kadardır. Kaç tur sonra sınır 1'in altına iner? 90 · (2/3)^k < 1 eşitsizliği k = 12 için ilk kez sağlanır (90 · (2/3)¹² ≈ 0,70; k = 11 için ≈ 1,04). Ama hiçbir sonlu turda tam 0'a ulaşılmaz. Süreç sonsuza dek sürer ve üst sınır 0'a yakınsar: yinelemeli elemeden sağ çıkan tek profil, herkesin 0 söylemesidir (Şekil 2.17).

2.6.4Tek Nash dengesi: herkes 0

Yinelemeli eleme, herkesin 0 söylediği profili bırakır. Bu profilin bir Nash dengesi olduğu ayrıca denetlenir.

Başka hiçbir profil yinelemeli elemeden sağ çıkmaz; bu yüzden denge tektir. Bunun nedeni, kesin baskılanan stratejileri silmenin hiçbir Nash dengesini silmemesidir: bir dengede herkes en iyi tepkisini oynar, oysa baskılanan bir strateji hiçbir durumda en iyi tepki olamaz. Dolayısıyla her denge elemeden sağ çıkar; sağ çıkan tek profil herkesin 0 söylemesi olduğuna göre denge de tektir.

Bir ayrıntı, oyunun kurallarının dengeyi nasıl etkilediğini gösterir. Yalnız tam sayılara izin verilseydi n ≥ 4 oyuncuda “herkes 1” de bir denge olurdu. Ondalıklı tahmine izin vermek bu ikinci dengeyi ortadan kaldırır.

2.6.5Kuram ve deney

Kuramın cevabı 0'dır. Ama deneylerde kazanan sayı 0 çıkmaz. 1997'de Financial Times okurlarıyla yapılan 0–100 sürümünde kazanan tahmin 13'tü. Rosemarie Nagel'in 1995'te yayımlanan laboratuvar deneylerinde ilk tur tahminleri 1–2 düşünme adımının çevresinde yığıldı: tahminlerin çoğu seviye 1 ya da seviye 2'nin tahminlerine yakındı (Nagel, 1995). Oyun aynı grupla tekrarlandıkça tahminler 0'a doğru indi.

İki sütun farklı soruları cevaplar. Sol sütun, ortak bilginin her katının neyi elediğini gösterir: her adım bir kat daha “herkes rasyonel” varsayımı ekler ve sonsuz adımın sonu tek Nash dengesidir. Sağ sütun ise oyuncuların gerçekte ne yazdığını modeller. Kuram ile deney arasındaki fark, “herkes tam rasyonel ve bu ortak bilgi” varsayımının gerçekte tam tutmamasından kaynaklanır. Birkaç kişi bile yüksek sayılar yazarsa ortalama yükselir ve 0 yazan kaybeder.

Bu oyunda Nash dengesini belirlemek zor değildir: denge tek ve saf stratejilidir. Zor olan, gerçek oyuncular karşısında en iyi tepkiyi tahmin etmektir. Kazanmak için 0'ı değil, sınıfın kaç adım düşündüğünü bilmek gerekir. Sınıf seviye 1 oynar ve ortalama 30 çıkarsa hedef 20 olur; seviye 2 kazanır.

2.7Kombinatoryal oyunlar

Satranç, XOX ve Nim gibi oyunların ortak bir yapısı vardır: iki oyuncu sırayla oynar, her şey açıktır, zar ya da kart yoktur. Bu oyunlar oyun kuramının en “algoritmik” köşesidir: kuramsal olarak her biri, ağacı sondan başa taranarak çözülebilir. Bu kısım bu tarama fikrini üç algoritmayla, minimaks, geriye doğru etiketleme ve Nim'in XOR kuralıyla anlatır.

2.7.1Kombinatoryal oyun ve Zermelo teoremi

Nim normal oyun kuralıyla oynanır: son jetonu alan kazanır. 21'i Söyleme'de ise kural terstir: 21'i söyleyen, yani son hamleyi yapmak zorunda kalan kaybeder. XOX ve satrançta beraberlik de mümkündür. Zermelo teoremi (Teorem 2.1) bu oyunların hepsine uygulanır: böyle bir oyunda ya bir taraf kazanmayı ya da iki taraf beraberliği garanti eder.

Bazı oyunlarda kimin kazandığı, ağaç hiç taranmadan bulunabilir. Hex bunun ünlü örneğidir. Hex'te beraberlik yoktur: tahta dolduğunda oyunculardan biri mutlaka kendi kenarlarını birleştirmiştir. Strateji çalma argümanı (strategy-stealing argument) şöyle işler. İkinci oyuncunun kazanan bir stratejisi olduğunu varsayalım. İlk oyuncu rastgele bir taş koyar ve sonra kendini ikinci oyuncu yerine koyarak o kazanan stratejiyi oynar. Tahtadaki fazladan taş ona hiçbir zaman zarar vermez; stratejinin istediği kare zaten doluysa yine rastgele bir taş koyar. Böylece ilk oyuncu da kazanır. İki oyuncunun aynı anda kazanması imkânsız olduğu için varsayım yanlıştır: ikinci oyuncunun kazanan stratejisi yoktur. Beraberlik de olmadığı için ilk oyuncu kazanır. Argüman, ilk oyuncunun nasıl kazandığını söylemez; yalnızca kazandığını gösterir.

Kombinatoryal oyunlarda her konum iki türden birindedir:

Kuralların mantığı şudur. Sırası gelen oyuncu rakibini bir P-konumuna gönderebiliyorsa bunu yapar; rakip ne yaparsa yapsın ona tekrar bir N-konumu bırakır ve oyuncu her seferinde rakibi yeniden P'ye gönderir. Sonunda hamle yapamayan rakip olur. Oyuncunun bütün hamleleri N-konumlarına gidiyorsa ne yaparsa yapsın rakibe kazanan bir konum bırakır.

2.7.2Kod izleme: oyun ağacında minimaks

Kazanç değerleri yalnızca “kazan / kaybet” değil de sayılarsa aynı fikir minimaks algoritmasıyla uygulanır. İki oyuncu MAX ve MIN olarak adlandırılır. MAX büyük değer ister, MIN küçük değer ister. Yapraklardaki sayılar MAX'ın kazancıdır; oyun sıfır toplamlı olduğu için MIN'in kazancı bunun eksi işaretlisidir. Bir düğümün değeri şöyle tanımlanır: yaprakta oyun sonu kazancıdır; MAX düğümünde çocukların değerlerinin en büyüğü, MIN düğümünde en küçüğüdür.

T = {"A": ["B", "C", "D"], "B": [3, 12, 8],
     "C": [2, 4, 6], "D": [14, 5, 2]}
def minimax(n, maxi):
  if isinstance(n, int):         # yaprak
    return n
  best = -99 if maxi else 99
  for c in T[n]:
    v = minimax(c, not maxi)
    best = max(best, v) if maxi else min(best, v)
  return best
print(minimax("A", True))

Kodun parçaları şunlardır:

• T sözlüğü ağacı tutar. Kök A'nın çocukları B, C, D'dir. B, C, D'nin çocukları yapraklardır ve tam sayılarla (int) gösterilir.
• minimax(n, maxi) düğüm n'nin değerini döndürür. maxi doğruysa sıra MAX'tadır.
• isinstance(n, int) doğruysa n bir yapraktır ve değeri kendisidir; fonksiyon hemen döner.
• best, MAX için −99, MIN için 99 ile başlar. Bu sayılar “henüz hiçbir çocuk görülmedi” anlamındadır: MAX'ın ilk gördüğü değer −99'dan büyük, MIN'in ilk gördüğü 99'dan küçük olacaktır.
• Döngü her çocuğu sırayla değerlendirir. Çocuğun sırası öteki oyuncudadır; bu yüzden özyinelemeli çağrı not maxi ile yapılır. MAX max, MIN min ile best'i günceller.

İzlemede dikkat çeken nokta D düğümüdür. D'nin ilk yaprağı 14'tür ve MAX için cazip görünür. Ama D bir MIN düğümüdür: MIN, 14 yerine 2'yi seçer. MAX bunu bilerek D'ye gitmez. Oyunun değeri 3'tür: MAX B'yi seçer ve MIN ne yaparsa yapsın en az 3 garanti eder (Şekil 2.19). Kod 9 yaprağın hepsine bakar. Alfa-beta budaması bazı yaprakları hiç değerlendirmeden atlayabilir: örneğin C'nin ilk yaprağı 2 görüldüğünde C'nin değeri en fazla 2 olacaktır ve 3'ten küçüktür; C'nin öteki yapraklarına bakmaya gerek yoktur.

2.7.3XOX: tüm ağaç aranabilir

XOX'un (tic-tac-toe) ağacı küçüktür. Bütün oyunları sayan bir program 255.168 farklı oyun ve 5.478 erişilebilir konum bulur. Bu sayılar bir bilgisayar için çok küçüktür: tüm ağaç bir saniyeden kısa sürede taranır. Minimaks değerleri +1 (X kazanır), 0 (berabere) ve −1 (O kazanır) olarak alınır. Boş tahtada minimaks değeri 0'dır: iki taraf da hatasız oynarsa oyun berabere biter.

Şekil 2.20'deki konumda X yalnızca sol alt kareyle kazanır. Bu hamle iki iş yapar: O'nun çaprazını (sağ üst – orta – sol alt) keser ve aynı anda iki tehdit kurar. Sol sütunda (X, boş, X) ve alt satırda (X, boş, X) iki ayrı kazanma tehdidi oluşur. O yalnız birini kapatabilir; X ötekini tamamlar (+1). Diğer her karede O, kendi çaprazını tamamlayarak kazanır (−1).

Satrançta tam arama imkânsızdır; ağaçta yaklaşık 10¹²⁰ oyun vardır. Satranç programları üç teknikle çalışır: derinlik sınırı (ağaç belirli sayıda hamleden sonra kesilir), değerlendirme fonksiyonu (kesilen yerdeki konuma bir puan verilir: taş değerleri, şah güvenliği vb.) ve alfa-beta budaması (sonucu değiştiremeyecek dallar atlanır). Minimaks XOX rakibi ise değerleri tam olarak hesaplayarak oynar: onu yenmek mümkün değildir; en iyi ihtimalle berabere kalınır.

2.7.4Kod izleme: 21'i Söyleme

21'i Söyleme oyununun kuralı şöyledir: iki oyuncu sırayla, 1'den başlayarak 1, 2 ya da 3 ardışık sayı söyler. Örneğin ilk oyuncu “1, 2” der, ikinci “3, 4, 5” der, ilk oyuncu “6” der. 21'i söyleyen kaybeder. Oyunun durumu, son söylenen sayı c ile tanımlanır; başlangıçta c = 0'dır.

Her durum K (sırası gelen kazanır) ya da Y (sırası gelen yitirir, yani kaybeder) olarak etiketlenir. Taban durum c = 20'dir: sıradaki oyuncu 21'i söylemek zorundadır ve kaybeder (Y). Öteki durumlar sondan başa hesaplanır: bir durumdan rakibi bir Y durumuna itecek bir hamle varsa durum K'dir; yoksa Y'dir.

HEDEF = 21
kazanir = {HEDEF - 1: False}   # c=20: kayıp
for c in range(HEDEF - 2, -1, -1):
    kazanir[c] = any(not kazanir[c + k]
        for k in (1, 2, 3) if c + k < HEDEF)
kontrol = [c for c in kazanir if not kazanir[c]]
print(sorted(kontrol))

Kod şöyle çalışır:

• kazanir sözlüğü her c için “sırası gelen kazanır mı?” sorusunun cevabını tutar. kazanir[20] = False: taban durum.
• Döngü c'yi 19'dan 0'a kadar geriye doğru dolaşır. Her c için 1, 2 ya da 3 sayı söylemek c + k durumuna götürür (21'i aşmadan; c + k < HEDEF).
• any(not kazanir[c + k] …): en az bir hamle rakibi kaybeden bir duruma götürüyorsa c kazanan durumdur.
• kontrol listesi kaybeden durumları toplar. Bunlar, oyuncunun rakibine bırakmak istediği sayılardır: kontrol sayıları.

Kod [0, 4, 8, 12, 16, 20] yazdırır. Y durumları 4'ün katlarıdır (Şekil 2.21). Başlangıç durumu c = 0 Y'dir: ilk oyuncu kaybeder. İkinci oyuncunun stratejisi basittir: rakip x sayı söylerse kendisi 4 − x sayı söyler. Böylece her turun sonunda toplam 4 artar ve ikinci oyuncu hep 4, 8, 12, 16, 20'ye tamamlar. Sonunda ilk oyuncu 21'i söylemek zorunda kalır.

2.7.5Nim ve Bouton teoremi

Nim'de birkaç jeton yığını vardır. Sırası gelen oyuncu tek bir yığından en az bir jeton alır (isterse yığının hepsini). Son jetonu alan kazanır. Küçük konumlar Şekil 2.18'deki gibi elle etiketlenebilir; ama yığın sayısı ve boyu büyüdükçe konum sayısı hızla artar. Charles Bouton 1901'de bütün Nim konumlarını tek bir hesapla etiketleyen bir kural buldu.

Teorem bir strateji de verir. Nim toplamı 0 olmayan bir konumda sırası gelen oyuncu, toplamı 0 yapan hamleyi yapar. Rakip toplamı 0 olan konumda her hamlesiyle toplamı bozar; oyuncu her seferinde yeniden 0 yapar. Bütün yığınlar boşken toplam 0'dır ve bu konumu rakibe bırakan, yani son jetonu alan, oyuncudur. Birçok başka sıralı oyun da Nim'e çevrilerek çözülebilir; Sprague–Grundy kuramı bu çevirinin genel yoludur.

2.7.6Kod izleme: Nim'de kazandıran hamle

Aşağıdaki kod, bir Nim konumunda nim toplamını hesaplar ve toplamı 0 yapan hamleyi bulur.

yiginlar = [3, 4, 5]
x = 0
for h in yiginlar:
    x ^= h            # nim toplamı (XOR)
for i, h in enumerate(yiginlar):
    if h ^ x < h:     # küçültülebilir mi?
        yiginlar[i] = h ^ x
        print("yığın", i, ":", h, "->", h ^ x)
        break
print(yiginlar)

İlk döngü x'i 0'dan başlatır ve her yığını ^= (XOR atama) ile ekler. İkinci döngü yığınları sırayla dener: h ^ x < h ise yığın h ^ x'e küçültülebilir ve bu hamle toplamı 0 yapar. İlk uygun yığın bulununca hamle yapılır ve döngü break ile durur.

Kod “yığın 0 : 3 -> 1” ve [1, 4, 5] yazdırır: ilk yığından 2 jeton alınır. Bu yığının seçilmesi rastlantı değildir. x = 2'nin en soldaki 1 biti 2'ler bitidir ve 3'ün (011) de bu biti 1'dir. Öteki yığınlar denense ne olur? 4 ⊕ 2 = 6 ve 5 ⊕ 2 = 7 yığından büyüktür; jeton eklemek yasak olduğu için bu hamleler yapılamaz. Yeni konum [1, 4, 5]'te 1 ⊕ 4 ⊕ 5 = 0'dır (Şekil 2.23).

2.7.7Çözülmüş oyunlar

2/3 oyunu dışında bu bölümün etkileşimli oyunları iki kişilik, sıralı, mükemmel bilgili ve şans içermeyen oyunlardır. Zermelo teoremine göre hepsi kuramsal olarak geriye doğru çıkarımla çözülebilir; ama ağaç çoğu zaman çok büyüktür. Bir oyunun “çözülmesi”, mükemmel oyunda sonucun (ilk oyuncu kazanır, ikinci kazanır ya da berabere) bulunması demektir. Tablo 2.19 bilinen sonuçları özetler.

Mangala gibi oyunlarda hamle ağacında birkaç adım ileriye bakmak oyuncuya önemli bir üstünlük sağlar. Tilki ve Kazlar'da roller asimetriktir: bir tarafta tek tilki, öbür tarafta çok sayıda kaz vardır; yine de bilgi mükemmeldir. Dokuz Taş da mükemmel bilgili klasik bir strateji oyunudur. Bu oyunların hepsinde aynı ilke geçerlidir: oyun sonlu ve bilgi mükemmelse, sonuç kuramsal olarak bellidir; pratikteki zorluk ağacın büyüklüğüdür.

2.8Sıralı oyunlar ve geriye doğru çıkarım

Kombinatoryal oyunlarda kullanılan “sondan başa” fikri, kazançları sıfır toplamlı olmayan sıralı oyunlara da uygulanır. Bu oyunlarda yeni bir sorun ortaya çıkar: bazı Nash dengeleri, hiçbir zaman uygulanmayacak tehditlere dayanır. Bu kısım bu sorunu, onu çözen alt oyun mükemmel denge kavramını ve dengeyi bulan geriye doğru çıkarım algoritmasını anlatır.

2.8.1Alt oyun ve alt oyun mükemmel denge

Alt oyun tanımındaki “bilgi kümesini bölmeme” koşulu şunu söyler: bir düğümden başlayan parça, oyuncunun o noktada ne bildiğini bozmamalıdır. Bir bilgi kümesinin bir düğümü parçanın içinde, öteki dışında kalırsa parça bir alt oyun değildir. Mükemmel bilgili oyunlarda her bilgi kümesi tek düğüm olduğu için her karar düğümü bir alt oyun başlatır. Bütün oyun da kendi kendinin bir alt oyunudur.

Neden yeni bir denge kavramı gerekir? Sıradan Nash dengesi, oyunun hiç ulaşılmayan düğümlerinde ne olduğuna bakmaz. Bir oyuncu, gerçekte hiç uygulamayacağı bir tehditle ötekini korkutabilir; tehdit hiç sınanmadığı için Nash dengesi bunu yakalayamaz. Böyle bir tehdide inandırıcı olmayan tehdit (non-credible threat) denir. SPE, her alt oyunda, yani ulaşılmayanlar da dahil her düğümde, oyuncuların en iyi seçimi yapmasını ister. Bu yüzden inandırıcı olmayan tehditleri eler.

Sonlu ve mükemmel bilgili oyunlarda SPE, geriye doğru çıkarım (backward induction) ile bulunur (Kuhn/Zermelo). Algoritma dört adımdan oluşur:

1. Yalnızca yapraklara bağlı son karar düğümlerini bul.
2. Orada karar veren oyuncunun en iyi dalını seç: yalnız o oyuncunun kazancı karşılaştırılır.
3. Düğümü, seçilen yaprağın kazanç vektörüyle değiştir; düğüm artık bir yapraktır.
4. Köke ulaşana kadar tekrarla.

Algoritma her düğümü tam bir kez işler; bu yüzden çalışma süresi ağacın boyuyla doğru orantılıdır. Ağaç küçükse çözüm hızlıdır. Satrançtaki zorluk algoritmada değil, ağacın büyüklüğündedir.

2.8.2Piyasaya giriş: inandırıcı olmayan tehdit

Piyasaya giriş oyunu (Şekil 2.9) burada kısa adlarla yazılır: G (giren firma, Rakip) önce seçer; M (mevcut firma, Tekel) yalnızca G girerse karar verir.

Önce oyunun normal formu yazılır. G'nin iki stratejisi vardır: Gir, Girme. M'nin tek karar düğümü vardır ve iki stratejisi vardır: Savaş, Uzlaş (yani “G girerse savaşırım” ve “G girerse uzlaşırım”). G girmezse M'nin stratejisi sonucu etkilemez.

Geriye doğru çıkarım bu iki dengeden birini eler:

1. Son düğüm M: Savaş → −1, Uzlaş → 1. M Uzlaş'ı seçer. M'nin düğümünün değeri (1, 1) olur.
2. Kök G: Girme → 0, Gir → 1 (M'nin uzlaşacağını bilerek). G Gir'i seçer.
3. SPE: (Gir, Uzlaş); sonuç (1, 1).

(Girme, Savaş) bir Nash dengesidir, ama alt oyun mükemmel değildir. M'nin düğümünden başlayan alt oyunda, yani G girdikten sonra, savaşmak M'ye −1, uzlaşmak 1 verir. Bu alt oyunda Savaş bir en iyi tepki değildir. “Girersen savaşırım” tehdidi inandırıcı değildir: G girdiği anda M'nin çıkarı uzlaşmaktır. Rasyonel bir G bunu öngörür ve tehdide aldırmadan girer.

2.8.3Yatırım oyunu adım adım

Üç aşamalı bir oyun, geriye doğru çıkarımın birden çok adımda nasıl işlediğini gösterir. Ayşe (A) yatırım yapar ya da yapmaz. Yatırım yaparsa girişimci Bora (B) kârı paylaşır ya da parayla kaçar. Bora kaçarsa Ayşe dava açar ya da bırakır. Yapraklarda (Ayşe, Bora) kazançları yazılır: Yatırma (2, 0); Paylaş (3, 3); Kaç ve Dava aç (1, 1); Kaç ve Bırak (0, 4).

Şimdi dava pahalı olsun: dava açan Ayşe 1 yerine −1 alır. Ağaç aynıdır, yalnızca bir yaprak (1, 1)'den (−1, 1)'e değişmiştir. Geriye doğru çıkarım baştan yapılır.

Şekil 2.26 ince bir noktaya işaret eder. Ayşe “kaçarsan dava açarım” planını açıklarsa (Ayşe: Yatır, Dava aç; Bora: Paylaş) profili yine bir Nash dengesidir. Bu profilde Ayşe 3, Bora 3 alır. Bora kaçarsa dava yer ve 1 alır; sapmaz. Ayşe yatırmazsa 2 alır; sapmaz. Dava düğümüne hiç ulaşılmadığı için Ayşe'nin oradaki seçimi kazancını etkilemez. Ama tehdit inandırıcı değildir: Bora gerçekten kaçarsa Ayşe dava açarak −1, bırakarak 0 alır ve bırakır. Bora bunu bilir. Bu profil alt oyun mükemmel denge değildir.

Dersin özeti şudur: söz vermek yetmez; tehdidin uygulanması o anda kârlı olmalıdır. Ayşe'nin dava açmayı kârlı kılmasının yolları vardır: avukatla önceden sabit ücretli anlaşmak ya da Bora'dan teminat almak. Bu tür önlemler oyunun kazançlarını değiştirerek tehdidi inandırıcı yapar.

2.8.4Kod izleme: cozum()

Geriye doğru çıkarım kısa bir özyinelemeli fonksiyonla yazılabilir. Ağaç iç içe listelerle gösterilir: her karar düğümü [ad, oyuncu, dallar] biçimindedir; dallar, (hamle, çocuk) çiftlerinin listesidir. Yapraklar kazanç demetleridir (tuple). Oyuncular 0 ve 1 indisleriyle gösterilir: oyuncu 1 indis 0, oyuncu 2 indis 1'dir.

def cozum(d):
    if isinstance(d, tuple):         # yaprak: kazanç
        return d
    ad, oyuncu, dallar = d
    en_iyi = None
    for hamle, cocuk in dallar:
        v = cozum(cocuk)
        if en_iyi is None or v[oyuncu] > en_iyi[oyuncu]:
            en_iyi, secim = v, hamle
    print(ad, secim)
    return en_iyi
kok = ['kök', 0, [('Sol', ['x', 1, [('a', (3, 1)), ('b', (1, 2))]]),
                  ('Sağ', ['y', 1, [('c', (2, 1)), ('d', (0, 0))]])]]
print(cozum(kok))

Fonksiyon şöyle çalışır:

• Düğüm bir demetse yapraktır ve kazanç vektörü olduğu gibi döner.
• Değilse düğüm üç parçaya açılır: ad, karar veren oyuncu ve dallar.
• Her dal için çocuğun değeri özyinelemeli olarak hesaplanır: v = cozum(cocuk).
• Karşılaştırmada yalnızca karar veren oyuncunun kazancı kullanılır: v[oyuncu] > en_iyi[oyuncu]. Kesin büyüktür (>) kullanıldığı için eşitlikte ilk görülen dal korunur.
• Düğümün seçimi yazdırılır ve seçilen dalın kazanç vektörü döner; üst düğüm bu vektörü bir yaprak gibi kullanır.

Program sırasıyla “x b”, “y c”, “kök Sağ” ve (2, 1) yazdırır. Adım 2 önemlidir: x'te oyuncu 2 kendi kazancına bakar ve b'yi seçer (2 > 1). Böylece oyuncu 1'in en sevdiği yaprak (3, 1) ulaşılamaz olur. Kökte oyuncu 1, Sol'un gerçek değerini (1, 2) ve Sağ'ın gerçek değerini (2, 1) karşılaştırır ve Sağ'ı seçer. SPE: (Sağ; x'te b, y'de c). Ulaşılmayan x düğümündeki b de stratejinin parçasıdır; oyuncu 1'in Sol'u reddetmesinin nedeni odur.

2.8.5Kırkayak oyunu

Kırkayak oyunu (centipede game), Robert Rosenthal'ın 1981'de tanımladığı bir oyundur (Rosenthal, 1981). İki oyuncu sırayla karar verir. Her düğümde karar veren oyuncu ya “Bitir” der ve o anki paylaşım gerçekleşir, ya da “Devam” der ve toplam büyür. Toplam kazanç 1 → 2 → 4 → 6 diye büyür, sonda da 6'dır. Ama devam eden oyuncu, rakibi bir sonraki adımda bitirirse daha az alır.

Yaprakları sırayla okumak oyunun gerilimini gösterir. Oyuncu 1 ilk düğümde bitirirse (1, 0) olur. Devam ederse oyuncu 2 ikinci düğümde bitirerek (0, 2) alabilir: oyuncu 2 için 2 > 0. Oyuncu 2 devam ederse oyuncu 1 üçüncü düğümde (3, 1) ile bitirebilir. Dördüncü düğümde oyuncu 2 (2, 4) ile bitirebilir ya da devam edip (3, 3)'e gidebilir.

Geriye doğru çıkarım son düğümden başlar. Tablo 2.22 dört adımın sonucunu gösterir.

2.8.6Kırkayak: teori ve deney

Teori. SPE'de her oyuncu her düğümde Bitir der ve oyun ilk hamlede (1, 0) ile biter. Daha güçlü bir sonuç da vardır: oyunun herhangi bir Nash dengesinde sonuç aynıdır. Nedeni şudur. Oyunun 1. düğümden sonra bittiği bir Nash dengesi olsaydı, oyunun bittiği yerden bir önceki düğümde karar veren oyuncu sapmak isterdi. Örneğin oyun 3. düğümde (3, 1) ile bitseydi, 2. düğümdeki oyuncu 2 devam ederek 1 alırken bitirerek 2 alabilirdi. Oyun sonuna kadar sürüp (3, 3) olsaydı, 4. düğümdeki oyuncu 2 bitirerek 4 alabilirdi. Her durumda kârlı bir tek taraflı sapma vardır; demek ki her Nash dengesinde oyun ilk düğümde biter.

Verimsizlik. (3, 3) iki oyuncu için de (1, 0)'dan iyidir: SPE sonucu Pareto optimal değildir. Düğüm sayısı arttıkça kayıp büyür; yüz düğümlü bir kırkayakta oyuncular büyük bir toplamı ilk adımda feda eder.

Deney. Laboratuvarda oyuncuların çoğu ilk düğümde bitirmez; birkaç tur devam eder (McKelvey ve Palfrey, 1992). Bunun nedeni, geriye doğru çıkarımın rasyonelliğin ortak bilgi olmasını ve uzun bir akıl yürütme zincirini gerektirmesidir. Rakibin biraz “iyi niyetli” olma ihtimali bile devam etmeyi kârlı kılar: rakip bir tur daha devam ederse oyuncu daha büyük bir paydan bitirebilir.

Kırkayak, sonlu tekrarlanan Mahkûmun İkilemi ile aynı mantığı paylaşır: son turdan geriye bakınca işbirliği çözülür. Sonsuz ufukta ise işbirliği dengede kalabilir (2.8.8).

2.8.7Ültimatom oyunu

Ültimatom oyunu, pazarlığın en basit modelidir (Güth, Schmittberger ve Schwarze, 1982). Ayşe 10 TL'nin x TL'sini Bora'ya önerir; x tam TL'dir (0, 1, …, 10). Bora kabul ederse paylaşım (10 − x, x) olur. Reddederse ikisi de 0 alır.

Bu oyunda da inandırıcı olmayan bir tehdit vardır. Bora “4 TL'den azını reddederim” derse ve Ayşe buna inanırsa Ayşe 4 teklif eder. (Ayşe: 4 teklif et; Bora: 4 ve üstünü kabul, altını ret) profili bir Nash dengesidir: Ayşe daha az teklif ederse 0 alır, daha çok teklif ederse daha az kalır; Bora'nın ulaşılan düğümdeki seçimi (kabul) en iyisidir. Ama 1 TL önerildiğinde reddetmek Bora'ya 0 < 1 verir; tehdit inandırıcı değildir ve profil alt oyun mükemmel değildir.

Deney sonuçları kuramdan çok farklıdır. Teklif verenlerin çoğu toplamın %40–50'sini önerir; %20'nin altındaki tekliflerin yaklaşık yarısı reddedilir. Bu sonuç “oyuncular geriye doğru çıkarım yapamıyor” diye okunmamalıdır. Ret, adalet kaygısının fayda fonksiyonunda yer aldığını gösterir: haksız bir teklifi reddetmek, birine 1 TL'den daha değerli gelebilir. Teklif verenler de bunu öngörüp cömert davranır (Camerer, 2003). Bu, 2.1.5'teki ilkenin bir örneğidir: rasyonel, bencil demek değildir.

2.8.8Sonsuz tekrarlı Mahkûmun İkilemi

Mahkûmun İkilemi aynı iki oyuncu arasında tekrar tekrar oynanırsa işbirliği mümkün olur mu? Cevap, oyunun ne zaman biteceğinin bilinip bilinmediğine bağlıdır. Aynı tek atışlık oyun tekrarlanır; sonucu belirleyen ufuktur.

Sonlu ve bilinen ufuk. Oyun 10 tur sürsün ve bu bilinsin. Son turda gelecek yoktur, dolayısıyla ceza da yoktur: 10. tur tek atışlık bir Mahkûmun İkilemi'dir ve orada İhanet baskındır. 9. turda oyuncular 10. turda ne olacağını bilir: ne yaparlarsa yapsınlar 10. turda ikisi de ihanet edecektir. Bu yüzden 9. turdaki seçimin bir geleceği yoktur ve 9. tur da tek atışlık bir oyun gibidir: İhanet. Geriye doğru çıkarım bunu ilk tura kadar taşır. Her turda İhanet oynanır; kırkayaktaki gibi işbirliği sondan başa çözülür.

Sonsuz ufuk. Her turdan sonra oyun δ olasılıkla bir tur daha sürsün. Oyunun bilinen bir son turu yoktur. Bugünkü ihanetin kazancı, gelecekteki kalıcı cezanın kaybıyla tartılır. δ yeterince büyükse, yani oyuncular sabırlıysa ya da oyunun sürme olasılığı yüksekse, sapmak kârlı değildir ve işbirliği dengede kalır.

Ceza inandırıcıdır, çünkü (İhanet, İhanet) tek atışlık oyunun bir dengesidir. Ceza aşamasında hiçbir oyuncu tek başına sessiz kalarak kazanamaz: rakip ihanet ederken sessiz kalmak −3, ihanet −2 verir. Bu yüzden iki kinci tetik stratejisi birlikte alt oyun mükemmel dengedir: hem işbirliği aşamasında (δ ≥ 1/2 iken) hem de ceza aşamasında kimse sapmak istemez.

2.8.9Sıralı oyunlarda sık hatalar

2.9Algoritmik bakış ve mekanizma tasarımı

Bu bölümde görülen kavramların çoğu klasik oyun kuramına aittir. Ama bölüm boyunca bir çizgi de belirdi: minimaks, geriye doğru çıkarım ve Nim'in XOR kuralı birer algoritmadır; 2/3 oyununda eleme bir döngüdür. Bu kısım, oyun kuramının bilgisayar bilimiyle buluştuğu yeri, yani algoritmik oyun kuramının sorularını özetler.

2.9.1Algoritmik oyun kuramı neden “algoritmik”?

Üç gözlem algoritmik bakışı gerekli kılar.

Büyüklük. Oyunun tanımı bile üstel olarak büyür. n oyuncunun her birinin 2 stratejisi varsa strateji profili sayısı 2ⁿ'dir. Her profil için her oyuncunun kazancını yazmak gerektiğinden matris n · 2ⁿ sayı içerir. 30 oyunculu bir oyunda profil sayısı 2³⁰ ≈ 1,07 · 10⁹'dur. Bütün profilleri tek tek denetleyen kaba kuvvet yöntemi ölçeklenmez.

Şekil 2.31'deki çubukların her biri bir öncekinden kat kat büyüktür. Güvenlik örneğinde 20 hedeften 5'inin korunacağı her seçim bir stratejidir; seçim sayısı C(20, 5) = 20! / (5! · 15!) = 15.504'tür. Bu sayılar, oyunların çoğunun ancak yapılarından yararlanan algoritmalarla çözülebileceğini gösterir.

Karmaşıklık. Nash'in teoremine göre her sonlu oyunda karışık stratejilerde bir denge vardır. Ama dengenin varlığını bilmek onu bulmak demek değildir. İki oyunculu oyunlarda bile dengeyi hızlı bulan bir yöntem bilinmez: problem PPAD-tam denen zor problemler sınıfındadır (Daskalakis, Goldberg ve Papadimitriou; iki oyuncu için Chen ve Deng).

Yapı ve tasarım. Özel yapı verimlilik getirir. Sıfır toplamlı oyunlar doğrusal programlamayla hızlı çözülür; Nim'de XOR, üstel sayıda konumu tek bir hesapla etiketler. Kurallar da algoritmadır: bir açık artırmanın kazananı ve ödemesi belirleyen kuralı bir programdır ve doğru tasarlanması gerekir.

2.9.2Dört soru

Algoritmik oyun kuramının dört ana sorusu vardır. Bu bölümün kavramları, yani oyunların sınıflandırılması, klasik oyunların dengeleri ve sıralı oyunlarda geriye doğru çıkarım, dört sorunun da ortak dilidir.

1. Hesaplama: denge bulunabilir mi? Sıfır toplamlı oyunlar doğrusal programlamayla hızlı çözülür. Genel oyunlarda Nash dengesini hızlı bulan bir yöntem bilinmez; problem PPAD-tamdır. Kombinatoryal oyunlar da zor olabilir: Hex'i büyük tahtalarda çözmek PSPACE-tamdır (Reisch, 1981).
2. Verimlilik: bencillik ne kaybettirir? Anarşinin Bedeli, en kötü dengenin maliyetinin en iyi sonucun maliyetine oranıdır. Mahkûmun İkilemi'nde hapis yılı maliyet sayılırsa denge toplam 4 yıl, (Sessiz, Sessiz) 2 yıldır; oran 4 / 2 = 2'dir.
3. Tasarım: hangi kurallar? Mekanizma tasarımı, oyuncuların özel bilgisini dürüstçe bildirmesini sağlayan, yani teşvik uyumlu (incentive compatible) kuralları arar: açık artırmalar, eşleştirme, oylama.
4. Dinamik: oyuncular dengeye nasıl ulaşır? Tekrarlanan ve çevrimiçi oyunlarda bilgi zamanla gelir; oyuncular geçmişten öğrenerek stratejilerini uyarlar. 2/3 oyununda tekrarlanan turlarda tahminlerin 0'a inmesi bunun bir örneğidir.

2.9.3Mekanizma tasarımı: tersine oyun kuramı

Oyun kuramı verilen bir oyunun sonucunu tahmin eder: kurallar bellidir, soru ne olacağıdır. Mekanizma tasarımı (mechanism design) soruyu tersine çevirir: istenen sonuç bellidir, soru o sonucu verecek kuralların ve teşviklerin ne olduğudur. Bu yüzden mekanizma tasarımına “tersine oyun kuramı” da denir.

Tasarımın zorluğu şudur: ajanların özel bilgisi, örneğin bir ürüne biçtikleri değer, konumları ya da tercihleri, tasarımcıya kapalıdır. Ajanlar bu bilgiyi bildirirken yalan söyleyebilir. İyi bir mekanizma, yalan söylemeyi kârsız kılar. Vickrey'nin 1961'de gösterdiği gibi ikinci fiyat açık artırmasında dürüst teklif baskın stratejidir: kazanan, kendi teklifini değil ikinci en yüksek teklifi öder; bu yüzden teklifi şişirmek ya da kısmak kazanca bir şey eklemez.

Mekanizmalar iki gruba ayrılır:

• Para ile: tasarımcı ödeme alabilir ya da yapabilir; ödemeler doğru söylemeyi teşvik eder. Örnekler: açık artırmalar, reklam yerleşimi.
• Para olmadan: teşvikler yalnızca kuralla sağlanır; genellikle hedeften biraz ödün verilir. Örnekler: seçimler, oda takası, tesis yeri seçimi.

2.9.4Gerçek dünya uygulamaları

Mekanizma tasarımı ve algoritmik oyun kuramı birçok gerçek sistemin içinde çalışır:

• Arama reklamları: reklam alanları her aramada genelleştirilmiş ikinci fiyat (GSP) açık artırmasıyla dağıtılır. Tek alanlı ikinci fiyat açık artırmasının aksine, çok alanlı GSP'de dürüst teklif baskın değildir.
• Spektrum açık artırmaları: devletler frekans lisanslarını tasarlanmış açık artırmalarla satar; ABD'de bu uygulama 1994'ten beri sürer.
• Okul yerleştirme: öğrenci önerili Gale–Shapley algoritmasında öğrencinin gerçek tercihlerini yazması en iyisidir; sonuç kararlı bir eşleştirmedir.
• Oda ve vardiya takası: herkes elindekini getirir; takas döngüleriyle kimse eskisinden kötü bir şey almaz ve para kullanılmaz.
• Trafik ve yönlendirme: her sürücü kendi en hızlı yolunu seçer; bencil seçimlerin toplam gecikmeye maliyeti Anarşinin Bedeli ile ölçülür.
• Platformlar ve teşvikler: yoğunluk fiyatlandırması sürücüleri yoğun saatlere çeker; Bitcoin madencileri işlemleri ödül için doğrular.

Bu uygulamaların ortak fikri şudur: kurallar öyle tasarlanır ki herkes kendi çıkarına davransa bile sistem iyi çalışır. Mahkûmun İkilemi'nde bireysel çıkar ortak kötü sonuca götürüyordu; iyi tasarlanmış bir mekanizmada ise bireysel çıkar istenen sonuca götürür.

2.10Çözümlü problemler

Aşağıdaki problemler bölümün ana yöntemlerini bir araya getirir. Her birinin çözümü ara adımlarıyla verilir.

2.11Özet

• Bir oyun; oyuncular, stratejiler, kazançlar, bilgi ve kurallardan oluşur. Rasyonel oyuncu inancına göre beklenen faydasını maksimize eder; rasyonel, bencil demek değildir. Ortak bilgi, “herkes biliyor” zincirinin sonsuza dek sürmesidir.
• Strateji, her karar düğümünde ne yapılacağını söyleyen tam plandır; k düğümde m'şer eylem m^k strateji verir. Karışık strateji, saf stratejiler üzerinde olasılık dağılımıdır.
• Sıralı fayda yalnız sırayı, kardinal fayda farkların büyüklüğünü de taşır. Piyango ve karışık strateji hesapları kardinal fayda ister; a · u + b (a > 0) dönüşümü kararları korur.
• Normal form G = (N, (S_i), (u_i)) eşzamanlı oyunları matrisle; genişletilmiş form sıralı oyunları ağaçla yazar. Bilgi kümesi, eşzamanlı oyunu ağaçta gösterir.
• Oyunlar altı boyutta sınıflandırılır: zamanlama, anlaşma, toplam kazanç, simetri, bilgi ve ufuk. Mükemmel bilgi geçmiş hamlelerle, tam bilgi kazanç fonksiyonlarıyla ilgilidir.
• Nash dengesi, kimsenin tek taraflı sapmak istemediği profildir. Mahkûmun İkilemi'nde ihanet baskındır ve tek denge (−2, −2) Pareto optimal değildir: kararlılık verimlilik değildir.
• Altı klasik 2×2 oyun çatışmadan koordinasyona uzanır: Yazı-Tura'da saf denge yoktur; Tavuk, Cinsiyetler Savaşı, Geyik Avı ve Saf Koordinasyon'da iki saf denge vardır; Bedava Para'da biri zayıftır.
• 2/3 oyununda yinelemeli eleme 90 → 60 → 40 → … → 0 ile tek dengeyi (herkes 0) verir; gerçek oyuncular 1–2 adım düşünür ve en iyi tahmin inanca bağlıdır (seviye-k).
• Minimaks değerleri yapraktan köke hesaplar; XOX berabere, örnek ağacın değeri 3'tür. Nim'de konum, nim toplamı 0 ise kaybedendir (Bouton); 21'i Söyleme'de kontrol sayıları 4'ün katlarıdır.
• Alt oyun mükemmel denge her alt oyunda Nash dengesidir ve geriye doğru çıkarımla bulunur; inandırıcı olmayan tehditleri eler (piyasaya giriş, yatırım, ültimatom). Kırkayakta SPE (1, 0)'dır.
• Kinci tetik stratejisi sonsuz tekrarda ihaneti kalıcı cezayla caydırır; Sam–John kazançlarıyla δ ≥ 1/2 iken işbirliği dengededir. Sonlu ve bilinen ufukta işbirliği çözülür.
• Algoritmik oyun kuramı dört soru sorar: hesaplama, verimlilik (Anarşinin Bedeli), tasarım (mekanizma tasarımı) ve dinamik.

2.12Kavram listesi

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

• oyun kuramı game theory
• oyuncu player
• rasyonellik rationality
• ortak bilgi common knowledge
• strateji strategy
• strateji profili strategy profile
• saf strateji pure strategy
• karışık strateji mixed strategy
• kazanç payoff
• fayda fonksiyonu utility function
• beklenen fayda expected utility
• sıralı fayda ordinal utility
• kardinal fayda cardinal utility
• piyango lottery
• bilgi kümesi information set
• mükemmel bilgi perfect information
• tam bilgi complete information
• eksik bilgi incomplete information
• Bayesçi oyun Bayesian game
• normal form normal form
• kazanç matrisi payoff matrix
• genişletilmiş form extensive form
• oyun ağacı game tree
• yaprak leaf
• sıfır toplamlı oyun zero-sum game
• sabit toplamlı oyun constant-sum game
• maksimin maximin
• minimaks minimax
• simetrik oyun symmetric game
• koalisyon coalition
• iskonto faktörü discount factor
• en iyi tepki best response
• Nash dengesi Nash equilibrium
• baskın strateji dominant strategy
• Mahkûmun İkilemi Prisoner's Dilemma
• Pareto optimal Pareto optimal
• Pareto baskınlık Pareto dominance
• Anarşinin Bedeli Price of Anarchy
• taahhüt commitment
• odak noktası focal point
• seviye-k düşünme level-k reasoning
• yinelemeli (baskın strateji) eleme iterated elimination of dominated strategies
• kombinatoryal oyun combinatorial game
• Zermelo teoremi Zermelo's theorem
• strateji çalma argümanı strategy-stealing argument
• nim toplamı nim-sum
• alt oyun subgame
• alt oyun mükemmel denge subgame perfect equilibrium
• geriye doğru çıkarım backward induction
• inandırıcı olmayan tehdit non-credible threat
• kırkayak oyunu centipede game
• Ültimatom oyunu ultimatum game
• kinci tetik stratejisi grim trigger
• mekanizma tasarımı mechanism design
• teşvik uyumlu incentive compatible

2.13Kendini Dene

1. Şirket 1 dört fiyattan birini seçer (80, 90, 100, 120 TL). Şirket 2 bu fiyatı görüp 90, 100 ya da 120 TL der. İki şirketin kaçar saf stratejisi vardır?

   Cevap

   Şirket 1'in tek karar düğümü ve 4 eylemi vardır: 4 strateji. Şirket 2'nin 4 karar düğümü vardır (Şirket 1'in her fiyatı için bir tane) ve her birinde 3 eylem seçer: 3⁴ = 81 strateji. Eylem sayısı (3) ya da düğüm × eylem (12) strateji sayısı değildir.

2. Hücrelerde (u₁, u₂): (Üst, Sol) = (2, 2), (Üst, Sağ) = (0, 3), (Alt, Sol) = (3, 0), (Alt, Sağ) = (1, 1). Baskın stratejiler, Nash dengesi ve Pareto optimal sonuçlar nelerdir?

   Cevap

   Satır oyuncusu için Alt baskındır: Sol'a karşı 3 > 2, Sağ'a karşı 1 > 0. Sütun oyuncusu için Sağ baskındır: Üst'e karşı 3 > 2, Alt'a karşı 1 > 0. Tek Nash dengesi (Alt, Sağ) = (1, 1)'dir. (Üst, Sol) = (2, 2) dengeyi Pareto baskılar. Pareto optimal sonuçlar (2, 2), (0, 3) ve (3, 0)'dır. Oyun bir Mahkûmun İkilemi'dir.

3. 2/3 oyununda (0–90) sınıfın %60'ı seviye 0, %40'ı seviye 1 düşünüyorsa hedef kaçtır? Seviye 1 mi, seviye 2 mi daha iyi yapar?

   Cevap

   Beklenen ortalama 0,6 · 45 + 0,4 · 30 = 27 + 12 = 39, hedef 2/3 · 39 = 26'dır. Seviye 1 (30) hedefe 4, seviye 2 (20) hedefe 6 uzaktadır. Bu nüfusta seviye 1 daha iyi yapar: ötekilerin az düşündüğü bir sınıfta fazla düşünmek kaybettirir.

4. MAX kökünün üç MIN çocuğu var: B = [5, 9], C = [6, 1, 8], D = [7, 4]. Oyunun minimaks değeri ve MAX'ın seçimi nedir? Ağaçtaki en büyük yaprak neden seçilemez?

   Cevap

   MIN değerleri: B = min(5, 9) = 5, C = min(6, 1, 8) = 1, D = min(7, 4) = 4. Kök MAX = max(5, 1, 4) = 5; MAX B'yi seçer. En büyük yaprak 9 B'dedir, ama B'de seçimi MIN yapar ve 5'i seçer.

5. Nim konumu [1, 3, 6]. Sırası gelen oyuncu kazanan bir konumda mıdır? Kazandıran hamle hangisidir?

   Cevap

   1 ⊕ 3 = 001 ⊕ 011 = 010 = 2; 2 ⊕ 6 = 010 ⊕ 110 = 100 = 4. Nim toplamı 4 ≠ 0: kazanan konumdur. Yığınlar denenir: 1 ⊕ 4 = 5 (1'den büyük), 3 ⊕ 4 = 7 (3'ten büyük), 6 ⊕ 4 = 2 (6'dan küçük). Tek kazandıran hamle üçüncü yığından 4 jeton alıp [1, 3, 2] bırakmaktır: 1 ⊕ 3 ⊕ 2 = 0.

6. “25'i Söyleme”de oyuncular sırayla 1'den 4'e kadar ardışık sayı söyler; 25'i söyleyen kaybeder. Kaybeden durumlar (son söylenen sayı) hangileridir ve kim kazanır?

   Cevap

   Taban durum 24'tür: sıradaki 25'i söylemek zorundadır (Y). 23, 22, 21, 20 durumlarından 24'e ulaşılır (K). 19'dan ulaşılabilen 20–23 hepsi K'dir: 19 Y. Örüntü 5'lik adımlarla sürer: Y durumları 24, 19, 14, 9, 4'tür. Başlangıç 0'dan 4'e ulaşılabildiği için ilk oyuncu kazanır: “1, 2, 3, 4” der, sonra rakip x sayı söylerse kendisi 5 − x sayı söyler.

7. Piyasaya giriş oyununda Tekel'in savaşmaktan itibar kazandığını varsayalım: Gir–Savaş yaprağı (−1, −1) yerine (−1, 3) olsun; öteki yapraklar aynıdır (Girme (0, 2), Gir–Uzlaş (1, 1)). Alt oyun mükemmel denge nedir? “Girersen savaşırım” tehdidi artık inandırıcı mıdır?

   Cevap

   M'nin düğümünde Savaş 3, Uzlaş 1 verir; M savaşır ve düğümün değeri (−1, 3) olur. Kökte G için Gir −1, Girme 0 verir; G girmez. SPE (Girme, Savaş), sonuç (0, 2). Tehdit artık inandırıcıdır, çünkü G girdiğinde savaşmak gerçekten M'nin çıkarınadır.

8. Tekrarlanan bir oyunda her tur kazançlar şöyledir: ikisi de işbirliği yaparsa 3'er; biri sapıp öteki işbirliği yaparsa sapan 6, öteki 0; ikisi de saparsa 1'er. İki oyuncu kinci tetik oynuyor. Oyunun bir tur daha sürme olasılığı δ en az kaç olmalıdır ki sapmak kârsız olsun?

   Cevap

   Uymak: 3 / (1 − δ). Sapmak: bu tur 6, sonra her tur 1: 6 + δ / (1 − δ). Koşul 3 / (1 − δ) ≥ 6 + δ / (1 − δ). İki taraf (1 − δ) ile çarpılır: 3 ≥ 6(1 − δ) + δ = 6 − 5δ, yani δ ≥ 3/5. Sapmanın cazibesi büyüdükçe (6 yerine daha büyük) eşik de büyür.

2.14İleri okuma

• M. J. Osborne, An Introduction to Game Theory (2004), Bölüm 2–5: normal form oyunları, Nash dengesini, genişletilmiş form oyunları ve geriye doğru çıkarımı az matematikle ve çok sayıda örnekle anlatır.
• A. R. Karlin ve Y. Peres, Game Theory, Alive (2017): kombinatoryal oyunları, Nim'i ve strateji çalma argümanını öğrenci düzeyinde ayrıntılı ispatlarla verir.
• C. F. Camerer, Behavioral Game Theory (2003): 2/3 oyunu, kırkayak ve ültimatom gibi oyunlarda gerçek oyuncuların davranışını deney sonuçlarıyla inceler.
• N. Nisan, T. Roughgarden, É. Tardos ve V. Vazirani (ed.), Algorithmic Game Theory (2007), Bölüm 1: oyun kuramının temel kavramlarını algoritmik oyun kuramının soruları açısından tanıtır.

2.15Kaynaklar

1. C. L. Bouton, “Nim, a game with a complete mathematical theory”, Annals of Mathematics 3, 1901–1902.
2. C. F. Camerer, Behavioral Game Theory, Princeton University Press, 2003.
3. D. Easley, J. Kleinberg, Networks, Crowds, and Markets, Cambridge University Press, 2010.
4. W. Güth, R. Schmittberger, B. Schwarze, “An experimental analysis of ultimatum bargaining”, Journal of Economic Behavior & Organization 3(4), 1982.
5. R. A. Hearn, E. D. Demaine, Games, Puzzles, and Computation, A K Peters, 2009.
6. A. R. Karlin, Y. Peres, Game Theory, Alive, American Mathematical Society, 2017.
7. R. D. McKelvey, T. R. Palfrey, “An experimental study of the centipede game”, Econometrica 60(4), 1992.
8. R. Nagel, “Unraveling in guessing games: An experimental study”, American Economic Review 85(5), 1995.
9. J. F. Nash, “Equilibrium points in n-person games”, PNAS 36(1), 1950.
10. N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani (ed.), Algorithmic Game Theory, Cambridge University Press, 2007 (Bölüm 1).
11. M. J. Osborne, An Introduction to Game Theory, Oxford University Press, 2004 (Bölüm 2–5).
12. S. Reisch, “Hex ist PSPACE-vollständig”, Acta Informatica 15, 1981.
13. R. W. Rosenthal, “Games of perfect information, predatory pricing and the chain-store paradox”, Journal of Economic Theory 25, 1981.
14. T. Roughgarden, Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016.
15. J. Schaeffer vd., “Checkers is solved”, Science 317(5844), 2007.
16. T. C. Schelling, The Strategy of Conflict, Harvard University Press, 1960.
17. R. Selten, “Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit”, Zeitschrift für die gesamte Staatswissenschaft 121, 301–324 ve 667–689, 1965.
18. Y. Shoham, K. Leyton-Brown, Multiagent Systems, Cambridge University Press, 2009 (Bölüm 3 ve 5).
19. B. Skyrms, The Stag Hunt and the Evolution of Social Structure, Cambridge University Press, 2004.
20. J. von Neumann, “Zur Theorie der Gesellschaftsspiele”, Mathematische Annalen 100, 1928.
21. E. Zermelo, “Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels”, Proceedings of the Fifth International Congress of Mathematicians, cilt 2, 501–504, Cambridge University Press, 1913.

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