Bölüm 0: Hazırlık

0.1Giriş

Bu bölümde yeni bir oyun kuramı kavramı yoktur. Bölümün işi, oyun kuramının konuştuğu dili tanıtmaktır. Bu dil birkaç sembolden, birkaç hesap kuralından ve birkaç okuma alışkanlığından oluşur. Hepsi küçük bir oyun üzerinden somutlaşır: Taş-Kağıt-Makas.

0.1.1Bir oyunla başlangıç: Taş-Kağıt-Makas

İki oyuncu aynı anda Taş, Kağıt ya da Makas seçer. Taş Makas'ı, Makas Kağıt'ı, Kağıt da Taş'ı yener; aynı seçim berabere biter. Kazanan 1 puan alır, kaybeden 1 puan verir, beraberlikte kimse puan almaz. Şekil 0.1'de bu yenme ilişkisi bir döngü olarak çizilmiştir: her ok, okun çıktığı hamlenin okun gösterdiği hamleyi yendiğini söyler.

Döngünün önemli bir sonucu vardır: “en iyi hamle” diye tek bir hamle yoktur. Taş, Makas'a karşı iyidir ama Kağıt'a karşı kötüdür. Hangi hamlenin iyi olduğu tamamen rakibin ne oynadığına bağlıdır. Oyun kuramının bütün konusu bu bağımlılıktır: bir oyuncunun kazancı yalnız kendi seçimine değil, rakibin seçimine de bağlıdır.

Oyunu bir bilgisayara karşı oynadığımızı düşünelim. Bilgisayar iki türlü davranabilir. Birinci türde her turda rastgele bir hamle seçer. İkinci türde bizim hamlelerimizi izler: hangi hamleyi ne sıklıkla yaptığımızı ya da hangi hamleden sonra hangisini yapmaya eğilimli olduğumuzu öğrenir ve buna göre oynar. İkinci tür bilgisayar karşısında iki soru doğal olarak ortaya çıkar:

• Öğrenen bir bilgisayarın uzun vadede yenemeyeceği bir oynayış var mı?
• Hep Taş oynayan biri, rakibi bunu fark edince tur başına ortalama kaç puan kaybeder?

Bu iki soruyu cevaplamak için gereken araçlar şunlardır: hamleleri ve sonuçları yazmak için küme ve fonksiyon gösterimi; “ortalama kaç puan” sorusu için olasılık ve beklenen değer; “en iyi karşılık” sorusu için argmax ve en iyi tepki; “yenilmeyen oynayış” için kayıtsızlık denklemi. Bu not, bu araçları sırayla kurar ve sonunda iki soruyu tam olarak cevaplar (0.9.5).

0.1.2Oyun kuramında matematiğin rolü

Oyun kuramındaki matematik, büyük ölçüde bir yazım düzenidir. “Ayşe Taş, Bora Makas oynarsa Ayşe 1 puan alır” cümlesi uzun ve belirsizdir; aynı bilgi u₁(Taş, Makas) = 1 olarak kısa ve kesin yazılır. Oyun büyüdükçe bu kısalık bir zorunluluk olur: on oyunculu bir oyunun bütün sonuçlarını cümlelerle anlatmak mümkün değildir.

İkinci rol hesaplamaktır. Bir oyuncu “rakibim yarı yarıya Taş oynuyorsa ben ne yapmalıyım?” diye sorduğunda cevap bir sayı karşılaştırmasıdır: her hamlenin ortalama getirisi hesaplanır ve büyük olan seçilir. Bunun için olasılık, toplam ve en büyük değer bulma yeterlidir. Seçim sürekli olduğunda (bir firmanın kaç birim üreteceği gibi) en büyük değer türevle bulunur.

Üçüncü rol ölçmektir. Bir yöntemin bilgisayarda ne kadar süreceği, girdinin büyüklüğüne göre büyüme hızıyla anlatılır. Algoritmik oyun kuramının “algoritmik” kısmı buradan gelir: bir dengeyi bulmak mümkün mü, mümkünse ne kadar hızlı? Bu soruların dili O ve Θ gösterimidir (0.10.3).

Notun her kesimi aynı sırayı izler: önce kavramın sade bir anlatımı, sonra biçimsel tanımı, ardından neden önemli olduğu, çözülmüş bir örnek ve en sık yapılan hata. Örneklerdeki sayılar sunumdaki sayılarla aynıdır.

0.2Kümeler ve fonksiyonlar

Bir oyunu yazmak için üç şey gerekir: kim oynuyor, her oyuncunun seçenekleri neler ve her durumda kim ne kazanıyor. Seçenekler bir küme olarak, “her durum” Kartezyen çarpım olarak, “kim ne kazanıyor” da bir fonksiyon olarak yazılır. Bu kesimde bu üç yapı ve onlarla yakından ilgili sayma kuralları anlatılır.

0.2.1Küme ve Kartezyen çarpım

Küme, nesnelerin sırasız bir topluluğudur. Oyun kuramında en sık kullanılan küme, bir oyuncunun seçeneklerinin listesidir. Küme süslü parantezle yazılır: {Taş, Kağıt, Makas}. Kümede sıra önemsizdir; {Taş, Kağıt} ile {Kağıt, Taş} aynı kümedir. Bir eleman bir kümede iki kez yazılmaz.

Tanımdaki “sıralı” sözcüğü çok önemlidir. Bir kümede sıra önemsizdir ama bir çiftte sıra önemlidir: (a, b) çiftinde birinci yer A'ya, ikinci yer B'ye aittir. İki çift ancak iki yerdeki elemanlar da aynıysa eşittir.

Oyun kuramında oyuncuların seçeneklerine strateji, bir oyuncunun bütün seçeneklerinin kümesine strateji kümesi denir. Oyuncu 1'in strateji kümesi S₁, oyuncu 2'ninki S₂ ile gösterilir. Oyunun bir turunda her oyuncu bir strateji seçer. İki oyuncunun seçimlerinin birlikte oluşturduğu çifte strateji profili (strategy profile) denir. Bütün olası profillerin kümesi tam olarak Kartezyen çarpımdır: S₁ × S₂. Böylece Kartezyen çarpım, “oyunda neler olabilir?” sorusunun eksiksiz cevabı olur.

Tablo biçimi rastlantı değildir. İki oyunculu her oyunun profilleri böyle bir tabloya dizilir; hücrelere kazançlar yazıldığında bu tablo kazanç matrisi olur (0.7). Üç oyunculu bir oyunda profiller üç elemanlı listelerdir: (s₁, s₂, s₃) ∈ S₁ × S₂ × S₃. Bu tür listelere üçlü, genel olarak n-li denir. Sayma kuralı aynıdır: eleman sayıları çarpılır.

0.2.2Fonksiyon gösterimi

Fonksiyon bir makine gibi düşünülebilir: bir girdi alır ve tek bir çıktı verir. Aynı girdi her zaman aynı çıktıyı verir. Oyun kuramında en önemli fonksiyon kazanç fonksiyonudur (payoff function). Girdisi bir strateji profili, çıktısı bir sayıdır: o profil oynandığında bir oyuncunun aldığı puan.

Gösterimdeki alt indis, kimin kazancına bakıldığını söyler. Aynı profil için u₁ Ayşe'nin, u₂ Bora'nın kazancını verir. Bu iki sayı genellikle farklıdır. Parantez içindeki iki strateji ise profili, yani “kim ne oynadı?” sorusunun cevabını taşır; sırası Kartezyen çarpımdaki sırayla aynıdır.

Şekil 0.3 aynı girdinin iki ayrı makineye girdiğini gösterir. Bir oyunda her oyuncunun kendi kazanç fonksiyonu vardır. Oyunu tam olarak tanımlamak, her oyuncu için bu fonksiyonun bütün profillerdeki değerini vermek demektir. İki oyunculu Taş-Kağıt-Makas'ta bu, 2 · 9 = 18 sayı eder.

Fonksiyon gösterimi neden bu kadar önemlidir? Çünkü oyun kuramındaki tanımların hepsi bu gösterimle yazılır. Örneğin “Ayşe, Bora'nın Makas oynadığını bilirse Taş'ı Kağıt'a tercih eder” cümlesi u₁(Taş, Makas) > u₁(Kağıt, Makas) eşitsizliğiyle, yani 1 > −1 ile söylenir. Gösterim okunabildiğinde tanımlar da okunabilir.

0.2.3Sayma: çarpım kuralı, n! ve C(n, k)

Oyun kuramında sık sorulan bir soru “kaç tane?” sorusudur: kaç strateji profili var, bir oyuncunun kaç saf stratejisi var, bir ağaçta kaç yaprak var? Bu soruların cevabı üç basit sayma kuralıyla verilir. Olasılık hesaplarında da aynı kurallar kullanılır, çünkü eşit olası sonuçlarda olasılık bir sayma oranıdır (0.5.1).

Çarpım kuralı, Kartezyen çarpımın eleman sayısı kuralının genel hâlidir. Faktöriyel, çarpım kuralının özel bir uygulamasıdır: bir sıranın birinci yerine n nesneden biri, ikinci yerine kalan n − 1 nesneden biri konur ve böyle devam edilir. Kombinasyon ise sıranın önemsiz olduğu seçimleri sayar. Formülü şöyle anlaşılır: n nesneden k tanesini sırayla seçmenin yolu n · (n − 1) · … · (n − k + 1) = n!/(n − k)!'dir. Bu sayımda aynı k nesne k! farklı sırada ayrı ayrı sayılmıştır. Sıra önemsiz olduğunda her grup bir kez sayılmalıdır, bu yüzden k!'e bölünür.

Son örnekteki büyüme dikkat çekicidir. Hedef sayısı 4'ten 20'ye, korunan hedef sayısı 2'den 5'e çıkınca saf strateji sayısı 6'dan 15 504'e çıkar. Gerçek güvenlik uygulamalarında (havaalanı, liman, orman devriyesi) hedef sayısı yüzlerle ölçülür. Bu yüzden stratejileri tek tek listeleyen yöntemler çabuk yetersiz kalır. Strateji sayısının bu kadar hızlı büyümesi, algoritmik oyun kuramının temel sorularından birini doğurur: sayısı astronomik olan stratejiler arasından iyisini bilgisayar hızlıca bulabilir mi?

0.3Toplam ve en büyük

Oyun kuramındaki hesapların çoğu iki işlemden oluşur: bir şeyleri toplamak ve en büyüğünü seçmek. Beklenen kazanç bir toplamdır; en iyi tepki bir en büyük değer seçimidir; tekrarlanan oyunlarda toplam kazanç sonsuz bir toplamdır. Bu kesim bu iki işlemin gösterimini ve hesaplanmasını anlatır. Seçeneklerin sonsuz çok olduğu durumda en büyük değer türevle bulunur; kesimin son iki alt başlığı bu konudadır.

0.3.1Toplam sembolü Σ

Σ, Yunan alfabesinin büyük “sigma” harfidir ve “hepsini topla” demektir. Uzun toplamları kısa yazmaya yarar. Sembolün altındaki ifade toplamanın nereden başlayacağını, üstündeki sayı nerede duracağını söyler. Sağındaki ifade ise her adımda neyin ekleneceğidir.

Sayacın adı önemsizdir; i yerine j ya da k yazmak toplamı değiştirmez. Önemli olan sayacın hangi değerlerden geçtiği ve her değer için ne eklendiğidir. Bazı toplamlarda sınırlar yazılmaz ve toplama “bütün olası değerler üzerinden” yapılır. Örneğin Σ_x x · P(X = x) yazımı, X'in alabileceği her x değeri için bir terim ekler.

Σ ile çalışırken iki kural sık kullanılır. Birincisi, her terimde ortak olan sabit bir çarpan toplamın dışına alınabilir: Σ c · x_i = c · Σ x_i. İkincisi, iki toplamın toplamı tek toplam olarak yazılabilir: Σ (x_i + y_i) = Σ x_i + Σ y_i. Her iki kural da toplamanın sırasının ve gruplamasının sonucu değiştirmemesinden gelir.

Σ gösterimi programlamadaki bir döngünün matematik karşılığıdır. Σ_i=1³ x_i, “toplam = 0; i = 1'den 3'e kadar her i için toplam'a x[i] ekle” demektir. Bu benzerlik, piyangonun beklenen değerini hesaplayan kodda açıkça görülür (0.5.6).

0.3.2Geometrik seri ve iskonto faktörü δ

Bazı oyunlar bir kez oynanıp biter; bazıları aynı oyuncular arasında tekrar tekrar oynanır. İki firma her ay fiyat belirler, iki komşu her gün karşılaşır. Tekrarlanan oyunlarda bugünkü kazanç ile gelecekteki kazancın nasıl karşılaştırılacağı sorusu ortaya çıkar. İnsanlar genellikle bugünkü bir kazancı gelecekteki aynı kazanca tercih eder; ayrıca oyunun gelecek turda sürüp sürmeyeceği de kesin olmayabilir. Bu iki etki tek bir sayıyla, iskonto faktörüyle (discount factor) modellenir.

Bu formül ilk bakışta şaşırtıcıdır: sonsuz tane pozitif sayı toplanıyor ama sonuç sonlu bir sayı çıkıyor. Bunun nedeni terimlerin hızla küçülmesidir. δ = 1/2 için terimler 1, 1/2, 1/4, 1/8, … olarak her adımda yarıya iner (Şekil 0.6). Toplam her adımda 2'ye biraz daha yaklaşır ama onu hiç aşmaz.

Her turun kazancı 1 değil de a ise sabit çarpan kuralıyla toplam a/(1 − δ) olur. Toplam bugünden değil de bir tur sonradan başlıyorsa her terim fazladan bir δ taşır: δ + δ² + … = δ · (1 + δ + …) = δ/(1 − δ).

Bu formülün oyun kuramındaki önemi şudur: tekrarlanan bir oyunda iki oyuncu sürekli işbirliği yaparsa her tur belli bir kazanç alırlar; biri bir kez hile yaparsa o tur fazla kazanır ama sonraki turlarda cezalandırılabilir. Hilenin kârlı olup olmadığı, bir kerelik kazancın ileride kaybedilecek kazançların bugünkü değeriyle karşılaştırılmasıyla anlaşılır. O bugünkü değer tam olarak bir geometrik seridir. δ büyükse (oyuncular sabırlıysa ya da oyunun sürmesi olasıysa) gelecek ağır basar ve işbirliği sürdürülebilir.

0.3.3max ve argmax

Bir oyuncu karar verirken seçeneklerinin her birinin ne getireceğine bakar ve en çok getireni seçer. Bu düşüncede iki ayrı soru vardır: “en çok ne kadar kazanılabilir?” ve “en çoğu hangi seçenek getirir?” İlkinin cevabı bir sayıdır, ikincisinin cevabı bir seçenektir. İki soru iki ayrı gösterimle yazılır.

Oyun kuramında oyuncu bir değer değil, bir eylem seçer. Bu yüzden argmax daha sık kullanılır. Bir oyuncunun “en iyi tepkisi”, rakibin seçimine karşı kendi kazancının argmax'ıdır (0.8). Max ise o en iyi tepkinin getirdiği kazancı söyler.

Şekil 0.7 iki kavramı görsel olarak ayırır: max çubuğun yüksekliğidir, argmax çubuğun altındaki etikettir. Bu ayrım ilk bakışta önemsiz görünür; oysa oyun kuramının pek çok tanımında max ve argmax aynı satırda birlikte geçer. Birini ötekinin yerine yazmak, tanımı anlamsız kılar.

0.3.4Kod izleme: döngüyle argmax bulma

Bilgisayar argmax'ı bir döngüyle bulur. Aşağıdaki Python kodu, sunumdaki kodun aynısıdır. Bu kez ödüller 3, 7, 2, 7'dir; yani B ile D eşit en büyüktür. Kod eşitlikte nasıl davrandığını göstermek için özellikle böyle seçilmiştir.

eylem  = ["A", "B", "C", "D"]
kazanc = [3, 7, 2, 7]
en_iyi = 0             # en iyinin indisi
for i in range(1, 4):
    if kazanc[i] > kazanc[en_iyi]:
        en_iyi = i
print(kazanc[en_iyi], eylem[en_iyi])

Kodun satırları şöyle çalışır:

• eylem seçeneklerin adlarını, kazanc aynı sıradaki ödülleri tutar. İki liste aynı indisle eşleşir: indis 0 A'ya ve 3'e, indis 1 B'ye ve 7'ye karşılık gelir.
• en_iyi = 0: başlangıçta ilk kart (A, 3 jeton) şimdilik en iyi kabul edilir. Değişken bir değer değil, bir indis tutar; bu, argmax'ın bir seçenek olmasının koddaki karşılığıdır.
• Döngü i = 1, 2, 3 için çalışır. range(1, 4) 1'den başlar ve 4'ü içermez. 0 atlanır, çünkü ilk kart zaten başlangıç adayıdır.
• Her adımda bakılan kartın ödülü, şimdiye kadarki en iyinin ödülüyle karşılaştırılır. Kesin olarak büyükse en iyi güncellenir.
• Sonunda en iyinin ödülü (max) ve adı (argmax) yazdırılır.

Tablo 0.1 döngünün her adımını, Şekil 0.8 son durumu gösterir. İzleme tablosunun son satırı önemli bir ayrıntıyı gösterir. Üçüncü adımda D'nin ödülü 7, en iyinin ödülü de 7'dir. Karşılaştırma kesin “büyüktür” (>) olduğu için 7 > 7 yanlıştır ve en iyi değişmez. Kod eşitlikte ilk bulunanı tutar. Çıktı 7 B olur. Oysa matematik açısından argmax kümesi {B, D}'dir. Kod, kümenin yalnız bir elemanını vermiştir.

Karşılaştırma >= olsaydı son eşit eleman tutulurdu ve çıktı 7 D olurdu. Bütün en iyileri bulmak için iki geçiş yapılır: önce max bulunur, sonra ödülü max'a eşit olan bütün indisler bir listeye toplanır. Oyun kuramı kodlarında bu ayrıntı önemlidir. Örneğin bir matristeki bütün dengeleri bulan bir program, eşit en büyükleri atlarsa bazı dengeleri kaçırır.

Kodun iş miktarı da kolayca sayılır. n seçenek için döngü n − 1 kez çalışır ve her turda bir karşılaştırma yapar. İş, seçenek sayısıyla doğru orantılı büyür; bu, 0.10.3'teki gösterimle Θ(n)'dir. Her seçeneğe en az bir kez bakmadan en büyüğü bulmak mümkün olmadığı için daha hızlı bir yöntem yoktur.

0.3.5Fonksiyonun en büyüğü: türev sıfır

Seçenekler birkaç kartla sınırlı olduğunda argmax bir tablodan okunur. Ama bazı seçimler süreklidir. Bir firma 4 birim de üretebilir, 4,5 birim de, 4,37 birim de. Seçenek sayısı sonsuz olduğu için tablo yazılamaz. Bu durumda en büyük değer, fonksiyonun grafiğinin şekli kullanılarak bulunur.

Bir dağın tepesini düşünelim. Tepeye çıkarken yol yukarı eğimlidir; tepeden inerken aşağı eğimlidir. Tam tepede yol bir an için düzdür: eğim sıfırdır. Aynı şey düzgün bir kazanç eğrisi için de geçerlidir: tepenin solunda eğim artı, sağında eksidir; tepede sıfırdır. Bir fonksiyonun her noktadaki eğimini veren fonksiyona türev (derivative) denir ve f′(q) ile gösterilir.

Yöntem üç adımdan oluşur: türev alınır, sıfıra eşitlenir ve çıkan denklem çözülür. Bulunan noktaya aday denir, çünkü eğimin sıfır olduğu her nokta tepe değildir. Bir çukurun dibinde de eğim sıfırdır. Bu yüzden dördüncü bir adım gerekir: adayın gerçekten tepe olduğu denetlenir.

Şekil 0.9 türevin geometrik anlamını gösterir. q = 2'deki kırmızı doğru eğriye bu noktada teğettir ve eğimi 6'dır: q küçük bir miktar artınca f yaklaşık 6 katı kadar artar. Tepede teğet yataydır. Tepenin sağında, örneğin q = 8'de, eğim 10 − 16 = −6'dır: q arttıkça f azalır.

0.3.6Türevle en iyi miktar

Türev yönteminin oyun kuramındaki ilk büyük uygulaması üretim miktarı seçen firmalardır. İki firma aynı malı satar. Piyasa fiyatı toplam üretime bağlıdır: ne kadar çok üretilirse fiyat o kadar düşer. Bir firmanın kârı yalnız kendi miktarına değil, rakibin miktarına da bağlıdır. Bu, bir oyundur.

Modelin sayıları şunlardır: fiyat 12 − (q + r)'dir; burada q firmanın, r rakibin üretim miktarıdır. Üretim maliyeti yoktur. Kâr, miktar çarpı fiyattır:

u(q) = q · (12 − q − r)

Aynı hesap rakibin her miktarı için tekrarlanabilir. Bunun yerine r'yi bir sabit gibi tutarak hesap bir kez ve genel olarak yapılır. Kâr açılınca u(q) = 12q − q² − qr olur. r sabit olduğu için qr'nin q'ya göre türevi r'dir (sabit çarpan kuralı). Türev u′(q) = 12 − 2q − r'dir ve sıfıra eşitlenince

12 − 2q − r = 0 ⇒ q = (12 − r)/2

bulunur. r = 4 konunca q = 8/2 = 4 çıkar; bu, örnekteki sonuçtur. r = 2 için q = 5, r = 6 için q = 3'tür: rakip ne kadar çok üretirse firma o kadar az üretir.

Formülün bir sınırı vardır: miktar negatif olamaz. r ≥ 12 ise formül sıfır ya da eksi bir sayı verir. Bu durumda fiyat zaten sıfır ya da altındadır ve firmanın en iyisi hiç üretmemektir. Tam formül şöyledir:

q*(r) = max{0, (12 − r)/2}

Rakibin her miktarına en iyi cevabı veren bu formül, 0.8'de matriste işaretlenen en iyi tepkinin sürekli hâlidir. Matriste en iyi tepki her sütun için ayrı ayrı argmax alınarak bulunur; burada türev, sonsuz çok “sütunun” hepsi için argmax'ı tek bir formülde verir. İki firmanın birbirine aynı anda en iyi tepki verdiği miktarlar, 0.4.4'te kısmi türevle bulunur.

0.4Üs, logaritma ve türev kuralları

Oyun kuramında üslü ifadeler üç yerde karşımıza çıkar: tekrarlanan oyunlarda iskonto (δ^t), riskten kaçınan bir kişinin faydası (x^0,88 ya da ln x) ve olasılıklı seçim kuralları (e^λv). Bu ifadelerle çalışmak için üs ve logaritma kurallarına, bu ifadelerin en büyüğünü bulmak için de iki yeni türev kuralına gerek vardır: çarpım kuralı ve zincir kuralı. Kesimin sonunda birden çok değişkenli fonksiyonlarda türev, yani kısmi türev anlatılır.

0.4.1Üs kuralları ve kesirli üs

x^a ifadesinde x'e taban, a'ya üs denir. a pozitif bir tam sayıysa x^a, x'in a kez kendisiyle çarpımıdır: x³ = x · x · x. Üs kuralları bu tanımdan doğrudan çıkar ve sonra kesirli ve negatif üslere aynı biçimde genişletilir.

Kuralların nedeni sayarak görülür. x² · x³, iki tane x ile üç tane x'in çarpımıdır; toplam beş tane x çarpılır, yani x⁵. x⁰ = 1 kuralı da birinci kuraldan gelir: x^a · x⁰ = x^a+0 = x^a olmalıdır, bu yüzden x⁰ çarpımı değiştirmeyen sayı, yani 1 olmalıdır. Negatif üs aynı mantıkla gelir: x^a · x^−a = x⁰ = 1 olduğuna göre x^−a, x^a'nın tersidir. Son olarak x^1/2 · x^1/2 = x¹ = x'tir; kendisiyle çarpımı x veren pozitif sayı √x'tir.

Kesirli üsler (x^0,88 gibi) aynı kurallara uyar. Bunların anlamı tek bir cümleyle söylenebilir: üs 1'den küçük ve pozitifse x^a, x büyüdükçe artar ama gittikçe yavaşlayarak artar. Üs 1'den büyükse gittikçe hızlanarak artar. Şekil 0.11 bu üç durumu yan yana gösterir.

Son örneğin anlamı karar kuramında önemlidir. Üssü 1'den küçük bir fayda fonksiyonu, “ikinci yüz lira ilk yüz lira kadar sevindirmez” düşüncesini sayıyla ifade eder. Böyle bir kişi, kesin 100 lira ile yarı yarıya 0 ya da 200 lira arasında kesin olanı seçer: kesin seçenek 57,5 fayda verir, piyango ise ortalama (0 + 105,9)/2 ≈ 53 fayda verir. Bu davranışa riskten kaçınma denir.

0.4.2e sayısı ve doğal logaritma ln

Bazı tabanlar ötekilerden daha kullanışlıdır. Bunların en önemlisi e ≈ 2,718 sayısıdır. e'nin özel olmasının nedeni türevle ilgilidir: e^x fonksiyonunun her noktadaki eğimi kendi değerine eşittir. Bu özellik hesapları çok sadeleştirir. Oyun kuramında e, olasılıklı seçim kurallarında (0.6.3) ve öğrenme algoritmalarında karşımıza çıkar.

Logaritma kuralları üs kurallarının tersten okunmasıdır. a = e^m ve b = eⁿ yazılırsa a · b = e^m+n'dir; iki tarafın ln'i alınınca ln(a · b) = m + n = ln a + ln b çıkar. Logaritma çarpımı toplama çevirir. Bu özellik, çok sayıda olasılığın çarpımıyla çalışan algoritmaların neden logaritma kullandığını da açıklar: küçük sayıların çarpımı yerine logaritmalarının toplamıyla çalışmak hem kolay hem de sayısal olarak güvenlidir.

Şekil 0.12 ters fonksiyon ilişkisini gösterir. Bir fonksiyon ile tersi, y = x doğrusuna göre simetriktir: e⁰ = 1 olduğu için e^x eğrisi (0, 1) noktasından, ln 1 = 0 olduğu için ln x eğrisi (1, 0) noktasından geçer. e^x eğrisi her zaman x ekseninin üstündedir; ln x ise yalnız pozitif x için tanımlıdır.

0.4.3Çarpımın türevi ve zincir kuralı

0.3.5'teki kurallar, çarpımı önce açıp terimlerin toplamı olarak yazabildiğimiz fonksiyonlara yeter. Ama her fonksiyon böyle açılmaz. ln(1 + 2x) ya da e^−x gibi iç içe fonksiyonlarda ve uzun çarpımlarda iki kurala daha ihtiyaç vardır.

Çarpım kuralı şöyle düşünülebilir: f · g bir dikdörtgenin alanıdır; kenarlardan biri f, öteki g'dir. x biraz artınca iki kenar da biraz uzar. Alanın artışı iki şeritten gelir: f kenarının uzamasıyla eklenen şerit (f′ · g) ve g kenarının uzamasıyla eklenen şerit (f · g′). Köşedeki küçücük kare iki küçük artışın çarpımıdır ve ihmal edilir.

Zincir kuralı ise bir hız aktarımıdır. İçteki fonksiyon x ile g′ hızında değişir; dıştaki fonksiyon da kendi girdisiyle f′ hızında değişir. x değişince sonuç bu iki hızın çarpımıyla değişir. Şekil 0.13 bu aktarımı bir boru hattı olarak çizer.

Zincir kuralının denetlenmesi kolaydır: sonuç, fonksiyonu açıp bilinen kurallarla türev alarak bulunan sonuçla karşılaştırılır. Son örnekte bu denetim yapılmıştır. Açılamayan fonksiyonlarda (logaritma, üstel) ise sayısal bir denetim yapılabilir: x = 0'da ln(1 + 2x)'in türevi formüle göre 2'dir; x 0'dan 0,001'e çıkınca fonksiyon ln 1,002 ≈ 0,002 kadar artar, yani artış hızı yaklaşık 2'dir ✓.

0.4.4Kısmi türev

Bir oyunda kazanç yalnız bir oyuncunun seçimine değil, herkesin seçimine bağlıdır. Firmanın kârı u(q, r) hem kendi miktarı q'ya hem rakibin miktarı r'ye bağlıdır. Böyle iki değişkenli bir fonksiyonda “türev” sorusu belirsizdir: hangi değişken değişiyor? Oyunda her oyuncu yalnız kendi değişkenini seçebildiği için doğru soru şudur: “öteki değişken yerinde dururken, benim değişkenim değişince kazancım nasıl değişir?”

Kısmi türev yeni bir kural gerektirmez. ∂u/∂q alınırken r'nin bulunduğu her yere 4, 7 ya da başka bir sabit yazılmış gibi davranılır; bütün bildiğimiz kurallar aynen uygulanır. Oyun kuramında her oyuncu kendi değişkenine göre kısmi türevi sıfıra eşitler. Böylece her oyuncu için bir denklem, yani en iyi tepki formülü elde edilir. Bu denklemler birlikte çözülünce herkesin aynı anda en iyi tepki verdiği nokta bulunur.

Şekil 0.14 kısmi türevin geometrik anlamını gösterir. r'nin her değeri, q'ya bağlı ayrı bir eğri verir. ∂u/∂q, r'yi sabitleyerek seçilen eğrinin eğimidir. Rakip daha çok ürettikçe eğri hem aşağı iner hem de tepesi sola kayar: firma hem daha az kazanır hem de daha az üretmek ister. Örnekte bulunan q = r = 4 noktasında iki firmanın da kendi eğrisinin tepesinde olması, hiçbirinin miktarını tek başına değiştirmek istememesi demektir. Oyun kuramında bu özelliğe denge adı verilir.

0.5Olasılık ve beklenen değer

Oyunlarda belirsizlik iki kaynaktan gelir. Birincisi doğadır: zar, kart, hava durumu. İkincisi rakiptir: rakibin ne oynayacağı kesin bilinmez ve bazen rakip bilerek rastgele davranır. Her iki durumda da kararı belirleyen soru aynıdır: “ortalamada ne kazanırım?” Bu kesim, olasılığın sayarak nasıl bulunduğunu, bilgi gelince nasıl güncellendiğini ve ortalama kazancın, yani beklenen değerin nasıl hesaplandığını anlatır. Son alt başlıklar sürekli değerlerle (0 ile 1 arasındaki her sayı gibi) çalışmayı ve bunun için gereken integral fikrini tanıtır.

0.5.1Sayarak olasılık hesaplamak

Bir deneyin (zar atma, kart çekme) olası sonuçlarının hepsi eşit şanslıysa bir olayın olasılığı bir sayma oranıdır: istenen sonuçların sayısı, bütün sonuçların sayısına bölünür. Olasılık her zaman 0 ile 1 arasında bir sayıdır; 0 “asla”, 1 “kesin” demektir.

Bağımsızlık için çarpım kuralı, 0.2.3'teki sayma kuralının olasılık hâlidir. İki zar atıldığında birinci zarın 6 sonucu, ikinci zarın 6 sonucuyla eşleşerek 36 sonuçtan birini oluşturur. Bu yüzden iki zarın da 6 gelme olasılığı 1/36 = 1/6 · 1/6'dır. Tümleyen kuralı ise “en az bir” sorularında çok işe yarar: “en az bir 6” olayını doğrudan saymak yerine “hiç 6 gelmemesi” sayılır ve 1'den çıkarılır.

0.5.2Olasılık dağılımı

Bir deneyin sonucu bir sayıysa (zarın yüzü, iki zarın toplamı, bir piyangonun ödülü) bu sayıya rastgele değişken denir ve genellikle büyük harfle yazılır: X. X'in her olası değerine bir olasılık yazan tabloya olasılık dağılımı denir.

Bu iki koşul, karışık stratejilerin tanımında da aynen kullanılır (0.6.1). Bir oyuncunun hamlelerine verdiği olasılıklar bir dağılım oluşturmalıdır. Hesaplarda yapılan hatalar çoğu zaman ikinci koşul denetlenerek yakalanır: olasılıklar toplanır ve 1 çıkmazsa bir yerde yanlışlık vardır.

0.5.3Koşullu olasılık

Bir oyuncu oyun sırasında bilgi edinir: rakibin bir hamlesini görür, bir işaret alır, bir kartını açar. Bu bilgi olasılıkları değiştirir. Örneğin desteden çekilen kartın kırmızı olduğu öğrenilince onun kupa olma olasılığı 1/4'ten 1/2'ye çıkar. Yeni bilgiyle güncellenmiş olasılığa koşullu olasılık (conditional probability) denir.

Formülün anlamı şudur: B'nin gerçekleştiği öğrenilince B'nin dışındaki sonuçlar artık imkânsızdır. Geriye yalnız B'nin içindeki sonuçlar kalır ve bu daralmış dünyada A'nın payı aranır. Payda P(B), yeni dünyanın büyüklüğüdür; pay P(A ∩ B), bu dünyada A'nın kapladığı yerdir. Kart örneğinde kırmızı kartlar 26 tanedir ve bunların 13'ü kupadır: P(kupa | kırmızı) = (13/52)/(26/52) = 1/2.

Bu örnek oyun kuramında önemli bir fikrin temelidir. Işık, sürücülerin çarpışmasını önleyen bir koordinasyon aracıdır. Her sürücü ışığın önerisine uyup uymamaya kendisi karar verir. Ayşe “Dur” gördüğünde Bora'nın yarı yarıya geçtiğini bilir; bu bilgiyle durmanın onun için iyi bir seçim olup olmadığını hesaplayabilir. Önerilerin herkesin işine geldiği bu tür düzenlere korelasyonlu denge denir. Hesabın tamamı koşullu olasılığa dayanır.

0.5.4Bayes kuralı

Poker gibi oyunlarda oyuncular rakibin “tipini” bilmez: rakip agresif mi, sakin mi? Ama rakibin hamlelerini görür. Büyük bir bahis, rakibin agresif olduğuna dair bir işarettir; ne kadar güçlü bir işaret olduğu ise hesapla bulunur. Gözlemden sonra inancı güncellemenin kuralı Bayes kuralıdır (Bayes' rule).

Sonuç ilk bakışta şaşırtıcıdır: agresif oyuncular büyük bahsi %80 oranında yaptığı hâlde, büyük bahis yapan birinin agresif olma olasılığı yalnız %50'dir. Bunun nedeni ön olasılıktır. Sakin oyuncular dört kat kalabalıktır. Her biri seyrek büyük bahis yapsa da sayıları çok olduğu için büyük bahislerin yarısı onlardan gelir. Gözlem inancı 0,2'den 0,5'e çıkarmıştır; güçlü bir güncellemedir ama kesinlik değildir.

Sayı ağacı yöntemi Bayes hesaplarının en güvenli yoludur. Olasılıklar yerine 100 ya da 1000 kişilik bir grup düşünülür, her daldaki kişi sayısı çarpılarak bulunur ve sonunda yalnız gözlemle uyumlu dallar sayılır. Formüldeki her terim ağaçta bir dala karşılık gelir: pay, gözlemle uyumlu “agresif” dalı; payda, gözlemle uyumlu bütün dallardır.

0.5.5Beklenen değer

Belirsiz bir durumda karar vermenin en temel aracı beklenen değerdir. Bir oyun çok kez oynansaydı tur başına ortalama ne kazanılırdı? Bu sorunun cevabı, her olası sonucun kendi olasılığı oranında hesaba katıldığı ağırlıklı bir ortalamadır.

Beklenen değerin neden “uzun vadeli ortalama” olduğu şöyle görülür. Adil bir zar 600 kez atılsın. Her yüz yaklaşık 100 kez gelir. Bütün atışların toplamı yaklaşık 1 · 100 + 2 · 100 + … + 6 · 100 = 2100'dür; atış başına ortalama 2100/600 = 3,5'tir. Bu hesap, her değeri sıklığıyla, yani olasılığıyla çarpıp toplamaktan başka bir şey değildir.

Beklenen değerin iki kullanışlı özelliği vardır. Birincisi, bir sabitle çarpmak ve bir sabit eklemek beklenen değere aynen geçer: E[aX + b] = a · E[X] + b. Bir oyunun ödülleri iki katına çıkarsa beklenen ödül de iki katına çıkar; giriş ücreti düşülürse beklenen nette o kadar düşer. İkincisi, toplamın beklenen değeri beklenen değerlerin toplamıdır: iki zarın toplamının beklenen değeri 3,5 + 3,5 = 7'dir. Bu ikinci özellik, zarlar bağımsız olmasa bile geçerlidir.

Oyun kuramında beklenen değer her yerdedir. Bir oyuncu, rakibin olasılıklı davranışına karşı her hamlesinin beklenen kazancını hesaplar ve en büyüğünü seçer (0.6.2). Bir mekanizma tasarımcısı, katılımcıların beklenen ödemelerini hesaplar. Bu hesapların hepsi aynı formülün uygulamasıdır: değer çarpı olasılık, sonra topla.

0.5.6Kod izleme: piyangonun beklenen değeri

Bir piyango bileti 0,05 olasılıkla 100 TL, 0,25 olasılıkla 20 TL kazandırıyor; 0,70 olasılıkla hiçbir şey kazandırmıyor. Bilet 12 TL'dir. Aşağıdaki kod, sunumdaki kodun aynısıdır ve beklenen değer formülünü bir döngüyle uygular.

odul = [100, 20, 0]          # TL
olas = [0.05, 0.25, 0.70]
E = 0
for i in range(3):
    E = E + odul[i] * olas[i]
print("E =", E)
print("net =", E - 12)  # bilet 12 TL

Kodun yapısı Σ toplamının birebir karşılığıdır:

• odul ve olas listeleri aynı indisle eşleşir: indis 0 en büyük ödüldür (100 TL, 0,05).
• E = 0: toplayıcı sıfırdan başlar. Σ'nın “henüz hiçbir şey toplanmadı” durumudur.
• Döngünün her adımında bir terim, odul[i] * olas[i], toplayıcıya eklenir.
• Son iki satır beklenen ödülü ve bilet fiyatı düşülmüş net beklenen kazancı yazar.

Tablo 0.2 her adımda eklenen terimi ve toplayıcının yeni değerini, Şekil 0.20 son durumu gösterir. İzlemenin dikkat çeken adımı üçüncü terimdir. Boş biletin ödülü 0'dır ve 0 · 0,70 = 0 toplayıcıyı değiştirmez. Ama bu satır gereksiz değildir: olasılığı 0,70'tir ve dağılımın toplamının 1 olması için sayılması gerekir. Olasılıkların toplamını denetlemek, eksik bir sonucun unutulmadığını gösterir.

Bir biletin beklenen ödülü 10 TL'dir. Bilet 12 TL olduğuna göre net beklenen kazanç 10 − 12 = −2 TL'dir. Çok kez oynayan biri bilet başına ortalama 2 TL kaybeder. Bunu beklenen değerin doğrusallığıyla da görmek mümkündür: net kazanç X − 12'dir ve E[X − 12] = E[X] − 12 = −2'dir. Kod çalıştırılınca iki satır yazar: E = 10.0 ve net = -2.0. Python ondalık sayıları nokta ile ve kesirli biçimde (10.0) yazar. Bu örnekte sonuç tam çıkar; başka olasılıklarla kayan nokta yuvarlaması nedeniyle 9.999999999999998 gibi çok yakın bir sayı da görülebilir. Bu, hesabın yanlış olduğunu değil, bazı ondalık sayıların ikili sistemde tam gösterilemediğini gösterir.

0.5.7Bu zar oyunu oynanır mı?

Beklenen değerin en doğrudan kullanımı, bir oyuna girmeye değip değmeyeceğine karar vermektir. Bu alt başlıkta beklenen değer hesabı bir tabloyla düzenli olarak yapılır ve “adil fiyat” sorusu tek bilinmeyenli bir denklemle cevaplanır.

Oyun ne olsaydı adil olurdu? Bir oyuna, net beklenen kazancı sıfırsa adil denir. 6 için ödül bilinmeyen bir y olsun; öteki ödüller aynı kalsın. Beklenen ödül y/6 + 10/6 = (y + 10)/6'dır. Adillik için bu, giriş ücretine eşit olmalıdır:

(y + 10)/6 = 10 ⇒ y + 10 = 60 ⇒ y = 50

6 için ödül 50 TL olsaydı oyun adil olurdu. Aynı soru başka biçimde de sorulabilir: ödüller aynı kalırsa giriş ücreti ne olmalıydı? Cevap beklenen ödülün kendisidir, yani yaklaşık 8,33 TL. Bu, tek bilinmeyenli bir denklemdir; iki bilinmeyenli denklemler 0.9.2'de işlenir.

0.5.8Sürekli düzgün dağılım U[0, 1]

Şimdiye kadar rastgele değişkenler birkaç değerden birini alıyordu. Bazı büyüklükler ise bir aralıktaki herhangi bir sayı olabilir: bir alıcının bir mala biçtiği değer, bir teklif, bir bekleme süresi. Açık artırma modellerinde en sık kullanılan varsayım, rakiplerin değerlerinin 0 ile 1 arasında “eşit şanslı” dağıldığıdır. Bu dağılıma düzgün dağılım (uniform distribution) denir.

Sürekli dağılımda tek bir noktanın olasılığı sıfırdır. Bu ilk bakışta tuhaftır: 0,5 değeri pekâlâ gelebilir, olasılığı nasıl sıfır olur? Açıklama şudur: aralıkta sonsuz çok değer vardır. Her birine pozitif bir olasılık verilseydi toplam sonsuz olurdu. Bu yüzden olasılık noktalara değil aralıklara verilir; bir aralığın olasılığı onun uzunluğudur. Uzunluğu sıfır olan bir noktanın olasılığı da sıfırdır. Bunun bir sonucu, P(X ≤ 0,6) ile P(X < 0,6)'nın aynı olmasıdır.

İkinci adımdaki çarpım kuralı rakip sayısıyla birlikte hızla etkisini gösterir. n bağımsız rakibin hepsini 0,6 teklifle geçme olasılığı 0,6ⁿ'dir: 1 rakipte 0,6; 2'de 0,36; 5'te yaklaşık 0,078. Rakip sayısı arttıkça kazanmak için daha yüksek teklif gerekir. Açık artırma kuramındaki birçok hesap bu basit gözleme dayanır.

0.5.9İntegral: eğri altındaki alan

Düzgün dağılımda alanlar dikdörtgen olduğu için kolay hesaplanır. Ama beklenen değer gibi hesaplarda eğik ya da eğri çizgilerin altındaki alanlar gerekir. Bir eğrinin altındaki alanı bulma işlemine integral denir. İntegral, Σ toplamının sürekli hâlidir.

Tanımdaki fikir Σ ile doğrudan bağlantılıdır. Aralık n eşit parçaya bölünürse her parçanın genişliği (b − a)/n olur. Her parçanın üstüne, yüksekliği o parçadaki f değeri olan bir dikdörtgen konur. Dikdörtgenlerin alanlarının toplamı bir Σ'dır. n büyüdükçe dikdörtgenler eğriye daha iyi uyar ve toplam gerçek alana yaklaşır. Σ'daki toplama işareti integralde uzatılmış bir S'ye (∫) dönüşmüştür; “sum” sözcüğünün baş harfidir.

Bu notta integral yalnız alan fikri olarak gereklidir; integral hesaplama teknikleri gerekmez. Karşılaşılan alanlar dikdörtgen ve üçgen olacaktır. Önemli olan, olasılığın ve beklenen değerin sürekli durumda birer alan olduğunu görmektir.

0.5.10Beklenen değer ve kuyruk olasılığı

Beklenen değeri hesaplamanın ikinci bir yolu vardır. Bu yol, açık artırma kuramında gelir ve ödeme hesaplarında sık kullanılır. Fikir şudur: X'in değerine doğrudan bakmak yerine, X'in her eşiği aşma olasılığına bakılır.

Toplam hâlinin neden doğru olduğu sayarak görülür. X = 3 olan bir sonuç düşünelim. Bu sonuç “X ≥ 1”, “X ≥ 2” ve “X ≥ 3” olaylarının üçünde de vardır, “X ≥ 4”te yoktur. Kuyrukların toplamında bu sonuç tam üç kez sayılır, yani kendi değeri kadar. Genel olarak değeri x olan her sonuç kuyruk toplamında x kez sayılır. Bu yüzden kuyrukların toplamı Σ x · P(X = x)'e, yani beklenen değere eşittir. İntegral hâli aynı fikrin sürekli sürümüdür.

Kuyruk formülü neden gereklidir? Bazı problemlerde X'in dağılımı doğrudan değil, eşik olasılıkları biçiminde bilinir. Örneğin iki rakibin en yükseğini aşma olasılığı çarpım kuralıyla kolayca bulunur (0.5.8); bu olasılıktan beklenen değere geçmenin en kısa yolu kuyruk formülüdür.

0.6Karışık strateji

Taş-Kağıt-Makas'ta tahmin edilebilir olmak kaybettirir. Hep Taş oynayan biri, rakibi bunu fark edince her turda kaybeder. Bunun çaresi, hangi hamlenin oynanacağını şansa bırakmaktır. Bu fikir, olasılık ile oyun kuramını birleştirir: oyuncu artık bir hamle değil, hamleleri üzerinde bir olasılık dağılımı seçer. Bu kesim karışık stratejinin tanımını, ona karşı beklenen kazancın hesabını ve değerleri olasılıklara çeviren yumuşak bir kuralı (softmax) anlatır.

0.6.1Karışık strateji fikri

Bir oyuncu her turda tek bir hamle yapar. Ama bu hamleyi seçmeden önce bir zar atabilir ya da para fırlatabilir ve hamlesini sonuca göre belirleyebilir. Böylece rakip, oyuncunun hangi hamleyi yapacağını önceden bilemez; en fazla hangi olasılıklarla oynadığını öğrenebilir.

Karışık strateji yeni bir hamle eklemez; var olan hamleleri bir rastgelelik düzeneğiyle birleştirir. Her saf strateji, karışık stratejinin özel bir hâlidir: (1, 0, 0) “hep Taş” demektir. Böylece karışık stratejiler saf stratejileri de içeren daha geniş bir küme oluşturur.

Şekil 0.24'teki şerit gösterimi, karışık stratejiyi uygulamanın bir yolunu da verir. 0 ile 1 arasında düzgün rastgele bir sayı (0.5.8) çekilir ve sayının şeridin hangi parçasına düştüğüne bakılır. Yanlı karışımda sayı 0,5'ten küçükse Taş, 0,5 ile 0,75 arasındaysa Kağıt, 0,75'ten büyükse Makas oynanır. Parçaların uzunlukları olasılıklara eşit olduğundan her hamle doğru olasılıkla seçilir. Bilgisayar programları karışık stratejileri tam olarak bu yolla uygular.

0.6.2Karışık stratejiye karşı beklenen kazanç

Rakip karışık bir strateji oynuyorsa bir hamlenin getirisi kesin değildir; şansa bağlıdır. Bu yüzden her hamle, rakibin olasılıklarına göre beklenen kazancıyla değerlendirilir. Hesap, 0.5.5'teki beklenen değer formülünün doğrudan uygulamasıdır: kazanç matrisinde oyuncunun satırındaki her sayı, rakibin ilgili sütunu oynama olasılığıyla çarpılır ve toplanır.

Bu iki adımlı hesap, yani önce her satırın beklenen değeri, sonra bunların argmax'ı, oyun kuramının en temel hesabıdır. Sonuca en iyi tepki denir (0.8). Tablo 0.4 bu hesabın düzenli bir yazımıdır: son sütun her satırın beklenen değerini, yeşil hücre de en iyi tepkiyi gösterir.

Ayşe de karışık oynayabilir. Ayşe (x_T, x_K, x_M) oynarsa onun beklenen kazancı, satır beklentilerinin bu olasılıklarla tartılmış ortalamasıdır. Örneğin Ayşe (1/3, 1/3, 1/3) oynarsa kazancı 1/3 · 0 + 1/3 · 1/4 + 1/3 · (−1/4) = 0'dır; saf Kağıt'tan kötüdür. Bir karışımın getirisi, karıştırılan hamlelerin getirilerinin ortalamasıdır ve bu yüzden en iyi saf hamlenin getirisini aşamaz. Bu gözlem 0.7.3'te matris diliyle yeniden ele alınır.

0.6.3Üstel oranlar: logit ve softmax

Beklenen kazançlar hesaplandıktan sonra en iyiyi seçmek (argmax) keskin bir kuraldır: küçük bir fark bile seçimi tamamen değiştirir. Gerçek insanlar ve öğrenen algoritmalar çoğu zaman daha yumuşak davranır: iyi seçeneği daha sık, kötü seçeneği daha seyrek seçer, ama kötüyü hiç dışlamaz. Bu davranışı modelleyen kurala softmax denir.

Kuralın yapısı basittir. Her seçeneğin değeri önce λ ile çarpılır, sonra e'nin üssüne konur. Bu üslü sayılar her zaman pozitiftir. Son olarak her biri toplama bölünür; böylece sonuçlar 0 ile 1 arasında kalır ve toplamları 1 olur. Değeri büyük olan seçenek daha büyük bir üslü sayı, dolayısıyla daha büyük bir olasılık alır.

İki seçenekli hâlin softmax'tan nasıl çıktığı şöyle görülür: P(1) = e^λv₁/(e^λv₁ + e^λv₂)'dir. Pay ve payda e^λv₁'e bölünür. Pay 1 olur; paydada 1 + e^λv₂/e^λv₁ = 1 + e^{−λ(v₁ − v₂)} kalır (üs kuralı: e^a/e^b = e^a−b). Bu formül, olasılığın yalnız değer farkına bağlı olduğunu açıkça gösterir.

λ'nın iki uç durumu kuralın anlamını verir. λ = 0 iken bütün üsler e⁰ = 1 olur ve her seçenek eşit olasılık alır: değerler hiç önemsenmez. λ büyüdükçe en büyük değerin üslü sayısı ötekilere göre çok büyür ve olasılık argmax'ta toplanır. Softmax, rastgele seçim ile argmax arasında ayarlanabilir bir köprüdür.

Şekil 0.25 duyarlılığın etkisini gösterir. λ 4'ten 40'a çıkarılsaydı üsler 0, 10 ve −10 olurdu ve Kağıt'ın olasılığı yaklaşık 0,99995'e çıkardı: kural neredeyse argmax'a dönüşürdü. Softmax, davranışsal oyun kuramında “küçük hatalar yapan oyuncuları”, makine öğrenmesinde ise keşif ile sömürü arasındaki dengeyi modellemek için kullanılır. Oyuncuların birbirine softmax ile tepki verdiği durağan durumlara nicel tepki dengesi (quantal response equilibrium) denir (McKelvey ve Palfrey, 1995).

0.7Kazanç matrisi

İki oyunculu bir oyunun bütün bilgisi tek bir tabloya sığar: satırlar bir oyuncunun, sütunlar ötekinin seçenekleridir; her hücreye o profilde iki oyuncunun kazancı yazılır. Bu tabloya kazanç matrisi (payoff matrix) denir. Matrisi doğru okumak, oyun kuramının en sık kullanılan becerisidir. Bu kesimde bir örnek oyun üzerinden okuma kuralları, bir alıştırma ve karışık stratejilerle beklenen kazancın matris çarpımı olarak yazılışı anlatılır.

0.7.1Kazanç matrisini okumak

Tanımda iki ayrı bilgi vardır. Birincisi kimin neyi seçtiğidir: satır oyuncusu yalnız satırı, sütun oyuncusu yalnız sütunu seçer. Hiçbir oyuncu hücreyi tek başına seçemez. İkincisi hücredeki sayıların kime ait olduğudur: ilk sayı satır oyuncusunun, ikinci sayı sütun oyuncusunun. Bu sıra Kartezyen çarpımdaki sırayla (0.2.1) aynıdır: profil (satır seçimi, sütun seçimi), kazanç (satır kazancı, sütun kazancı).

Sıfır toplamlı oyunlarda ikinci sayı her zaman birincinin eksi işaretlisi olduğu için çoğu zaman yalnız satır oyuncusunun kazançları yazılır. Kart Gösterme'de bu, A = [[−3, 1], [1, −1]] matrisidir: ilk satır Kırmızı, ikinci satır Siyah; ilk sütun “Kırmızı”, ikinci sütun “Siyah” tahminidir. Bu kısa yazım 0.7.3'te kullanılır.

0.7.2Matrisi okuma alıştırması

Okuma kuralları birkaç soruyla pekiştirilir. Sorular Kart Gösterme matrisi üzerindedir (Şekil 0.26). Her sorunun cevabında hangi satıra ya da sütuna, hangi sayıya bakıldığı ayrıca belirtilmiştir.

Üçüncü sorunun yöntemi özellikle önemlidir: rakibin seçimi sabitlenir (bir sütun seçilir), oyuncu kendi sayılarını (ilk sayıları) karşılaştırır ve en büyüğünü seçer. Bu, en iyi tepkinin tanımıdır (0.8.1). Dördüncü soru ise Ayşe'nin oyunda neler yaşayabileceğinin sınırlarını verir; Ayşe'nin bu sınırlar arasında hangi sonucu alacağı Bora'nın seçimine bağlıdır.

0.7.3Beklenen kazanç bir matris–vektör çarpımıdır

İki oyuncu da karışık strateji oynadığında beklenen kazancı hesaplamak için her hücrenin kazancı, o hücreye düşülme olasılığıyla çarpılıp toplanır. Oyunlar büyüdükçe bu hesap kalabalıklaşır. Matris gösterimi hesabı iki düzenli adıma ayırır ve bilgisayarda tek bir işlemle yapılmasını sağlar.

Bu iki adım, 0.6.2'deki hesabın aynısıdır. Orada önce her satırın beklenen değeri bulunmuştu (Tablo 0.4'ün son sütunu); bu Ay'dir. Sonra Ayşe'nin karışımı bu sayıları tartmıştı; bu xᵀAy'dir. Matris gösterimi yeni bir şey öğretmez, yalnız aynı hesabı her boyuttaki oyun için aynı kısa yazımla ifade eder.

Örneğin son adımı genel bir kuralı gösterir: xᵀAy, Ay'nin elemanlarının ağırlıklı ortalamasıdır; ağırlıklı ortalama da en büyük elemanı aşamaz. Bu yüzden bir oyuncu, rakibin stratejisi biliniyorsa saf bir en iyi tepkiyle her karışım kadar iyi sonuç alabilir. Karışık oynamanın amacı rakibe karşı daha çok kazanmak değil, rakibin bizi sömürmesini önlemektir. Bu fark kayıtsızlık fikrinin özüdür (0.9.3).

0.8En iyi tepki

Önceki kesimlerin bütün araçları tek bir kavramda birleşir: en iyi tepki. Kazanç fonksiyonu, argmax, beklenen değer ve matris okuma bu kavramın parçalarıdır. En iyi tepki, oyun kuramının en temel kavramlarından biri olan dengenin de yapı taşıdır.

0.8.1En iyi tepki

“Rakibin ne yapacağını bilseydim ne yapardım?” sorusunun cevabı en iyi tepkidir. Soru bir varsayım içerir: rakibin seçimi bilinmektedir ve değişmeyecektir. Bu varsayım altında oyun, tek kişilik bir karar problemine dönüşür ve cevap bir argmax'tır.

Tanımın üç parçası vardır. Rakibin seçimini sabitle: matriste bir sütun seçilir. Kendi kazançlarına bak: o sütunda yalnız ilk sayılar okunur. Argmax'ı al: en büyük sayının satırı seçilir. Eşitlik varsa birden çok en iyi tepki vardır ve hepsi kümeye girer.

Son iki adım ilginç bir gözlem verir: Bora'nın karışımı değişince Ayşe'nin en iyi tepkisi de değişti. q = 1/2'de Siyah, q = 1/4'te Kırmızı en iyidir. Arada bir yerde iki hamlenin eşit getirdiği bir q olmalıdır. Bu değer 0.9.3'te bulunur ve karışık stratejilerin nasıl hesaplandığının anahtarıdır.

0.8.2İzleme: 2×2 matriste en iyi tepkiler

En iyi tepkiler bütün matris için bir kerede işaretlenebilir. Yöntem iki turdan oluşur: önce satır oyuncusunun her sütundaki en iyi tepkisi, sonra sütun oyuncusunun her satırdaki en iyi tepkisi işaretlenir. Tablo 0.5'teki oyunda Ayşe satırı (Yukarı/Aşağı), Bora sütunu (Sol/Sağ) seçer.

Bu izlemenin vardığı özellik, yani her oyuncunun ötekinin seçimine karşı en iyi tepkisini oynaması, Nash dengesi adını taşır. Denge, kimsenin tek başına sapmak istemediği bir durumdur. İşaretleme yöntemi, iki oyunculu matris oyunlarında bütün saf dengeleri bulmanın en kısa yoludur: her sütunda satır oyuncusunun, her satırda sütun oyuncusunun en büyük sayısı işaretlenir; iki işaretli hücreler dengedir.

Yöntemi Kart Gösterme'ye uygulamak öğreticidir. Bora “Kırmızı” derken Ayşe'nin en iyisi Siyah'tır; Ayşe Siyah tutarken Bora'nın en iyisi “Siyah” demektir; Bora “Siyah” derken Ayşe'nin en iyisi Kırmızı'dır; Ayşe Kırmızı tutarken Bora'nın en iyisi “Kırmızı”dır. En iyi tepkiler bir döngü kurar ve hiçbir hücrede iki işaret buluşmaz. Böyle oyunlarda saf strateji dengesi yoktur; oyuncular karıştırmalıdır. Karışımın olasılıkları kayıtsızlık denklemiyle bulunur.

0.9Denklemler ve kayıtsızlık

Oyun kuramında bilinmeyenler çoğu zaman olasılıklardır: bir oyuncu bir hamleyi hangi olasılıkla oynamalıdır? Bu sorular denklemlere dönüşür. Çoğu doğrusaldır (birinci derece), bazıları ikinci derecedir. Bu kesim iki denklem türünün çözümünü hatırlatır ve sonra oyun kuramının en çok kullanılan denklemini, kayıtsızlık denklemini kurar. Kesim, girişteki iki sorunun cevabıyla biter.

0.9.1İkinci derece denklem ve diskriminant

Bilinmeyenin karesinin geçtiği denkleme ikinci derece denklem denir. Grafiği bir paraboldür ve kökler, parabolün yatay ekseni kestiği noktalardır. Parabol ekseni iki noktada kesebilir, ekseni yalnız bir noktada teğet geçebilir ya da eksene hiç değmeyebilir. Hangisinin olduğunu tek bir sayı, diskriminant söyler.

Formüldeki “±” işareti iki ayrı hesabı kısaltır: biri +√Δ ile, öteki −√Δ ile yapılır. Δ = 0 iken iki hesap aynı sonucu verir; Δ < 0 iken negatif bir sayının karekökü gerçek sayı olmadığı için formül uygulanamaz.

Oyun kuramında bilinmeyen çoğu zaman bir olasılıktır. Bu durumda denklemin iki kökünden yalnız 0 ile 1 arasında olanı anlamlıdır. Öteki kök matematik olarak doğrudur ama olasılık olamaz. Her çözümün sonunda bu denetim yapılmalıdır.

Diskriminantın öteki iki durumu da birer örnekle görülebilir. p² − p + 1/4 = 0 için Δ = 1 − 4 · 1 · 1/4 = 0'dır; tek kök p = 1/(2 · 1) = 1/2'dir ve parabol ekseni bu noktada yalnız teğet geçer. p² + p + 1 = 0 için Δ = 1 − 4 = −3 < 0'dır; parabol eksene hiç değmez ve denklemin gerçek kökü yoktur.

0.9.2İki bilinmeyenli doğrusal denklem

İki bilinmeyeni bulmak için iki denklem gerekir. Tek bir denklem, sonsuz çok çözüm çifti verir; ikinci denklem bunlardan birini seçer. Çözümün fikri, bilinmeyenlerden birini yok etmektir: ya iki denklem birbirinden çıkarılır ya da birinden bir bilinmeyen çekilip ötekine konur. Kalan tek bilinmeyenli denklem çözülür ve bulunan değer geri yerine konur.

Oyun kuramında bu denklemlerin tipik biçimi şudur: iki olasılık x ve y için biri “olasılıkların toplamı 1'dir”, öteki de oyundan gelen bir koşuldur. Örneğin x + y = 1 ve x = 2y ise ikinci denklem birinciye konur (yerine koyma yöntemi): 2y + y = 1 ⇒ 3y = 1 ⇒ y = 1/3 ve x = 2/3. Denetim: 2/3 + 1/3 = 1 ✓ ve 2/3 = 2 · 1/3 ✓.

0.9.3Kayıtsızlık fikri

Karışık strateji oynayan bir oyuncunun karıştırdığı hamleler hakkında ne söylenebilir? Cevap basit bir akıl yürütmeden gelir. Oyuncu iki hamlesini gerçekten karıştırıyorsa, yani ikisine de pozitif olasılık veriyorsa, iki hamle ona eşit beklenen kazanç vermelidir. Biri daha iyi olsaydı oyuncu hep onu oynardı; daha kötü olana olasılık vermesi kazancını boşuna düşürürdü.

İlkenin şaşırtıcı bir sonucu vardır. Bir oyuncunun kayıtsız olması, rakibin olasılıklarına bağlıdır, kendi olasılıklarına değil. Ayşe'nin iki hamlesinin beklenen kazancı, Bora'nın ne sıklıkla ne oynadığıyla hesaplanır. Dolayısıyla “Ayşe kayıtsızdır” koşulu, Bora'nın olasılığı hakkında bir denklemdir. Ayşe'nin kendi olasılığı ise Bora'nın kayıtsızlık koşulundan bulunur.

Şekil 0.31 fikri görsel olarak özetler. Ayşe'nin en iyi tepkisi her q için üstteki doğrudur: q küçükken Kırmızı, büyükken Siyah. İki doğrunun kesişme noktası, Ayşe'nin karıştırmaya razı olabileceği tek q değeridir. 0.8.1'deki gözlem de burada açıklanır: q = 1/4 kesişmenin solundadır ve Kırmızı en iyidir; q = 1/2 sağındadır ve Siyah en iyidir.

0.9.4İzleme: kayıtsızlık denklemi

Kayıtsızlık denklemi her zaman aynı dört adımla kurulur ve çözülür. Aşağıdaki izlemede p, Ayşe'nin Kırmızı tutma olasılığı; q, Bora'nın “Kırmızı” deme olasılığıdır. Kullanılan matris Şekil 0.32'de yeniden verilmiştir.

Aynı dört adım Bora için tekrarlanınca Ayşe'nin olasılığı bulunur. Ayşe Kırmızı'yı p olasılıkla tutsun. Bora'nın kazançları Ayşe'ninkilerin eksi işaretlisidir. Bora “Kırmızı” derse 3 · p + (−1) · (1 − p) = 4p − 1, “Siyah” derse (−1) · p + 1 · (1 − p) = 1 − 2p kazanır. Eşitlik: 4p − 1 = 1 − 2p ⇒ 6p = 2 ⇒ p = 1/3. Denetim: iki taraf da 1/3'tür. Bu oyunda iki oyuncunun olasılığı rastlantıyla aynı çıkmıştır; genel olarak farklıdır.

Sonuçları bir araya getirelim. Ayşe p = 1/3 ile Kırmızı, Bora q = 1/3 ile “Kırmızı” oynarsa ikisi de ötekinin stratejisine karşı kayıtsızdır; hiçbiri stratejisini değiştirerek kazancını artıramaz. Ayşe tur başına −1/3, Bora +1/3 alır. Oyun Bora'nın lehinedir. Ayşe'nin Kırmızı'yı yalnız 1/3 olasılıkla tutması da anlamlıdır: Kırmızı yakalanırsa 3 jeton kaybettirir, bu yüzden Ayşe onu seyrek tutar. Bu, 0.8.2'de saf dengesi olmadığı görülen oyunun karışık strateji dengesidir.

0.9.5Oyuna dönüş: Taş-Kağıt-Makas

Girişteki iki soru artık cevaplanabilir. İkisi de beklenen kazanç ve en iyi tepki hesabıdır.

Yenilmeyen bir oynayış var mı? Evet: (1/3, 1/3, 1/3). Rakip ne oynarsa oynasın beklenen kazanç 0'dır. Örneğin rakip Kağıt oynarsa: Taş −1, Kağıt 0, Makas +1 getirir ve beklenen kazanç 1/3 · (−1) + 1/3 · 0 + 1/3 · (+1) = 0'dır. Rakip Taş ya da Makas oynadığında da aynı hesap 0 verir; rakip karıştırırsa sonuç bu sıfırların ortalaması, yine 0'dır. Kayıtsızlık açısından bakıldığında, eşit karışım rakibin üç hamlesini de ona eşit getirili yapar. Rakibin sömürebileceği bir taraf kalmaz.

Hep Taş oynayan ne kaybeder? Rakibin en iyi tepkisi hep Kağıt'tır ve her tur kazanır: tur başına −1. Daha hafif bir yanlılık da kaybettirir. (1/2, 1/4, 1/4) oynayana karşı rakibin her hamlesinin getirisi hesaplanır: Kağıt 1/2 · 1 + 1/4 · 0 + 1/4 · (−1) = 1/4, Taş 0 + 1/4 · (−1) + 1/4 · 1 = 0, Makas 1/2 · (−1) + 1/4 · 1 + 0 = −1/4. Rakip Kağıt oynar ve yanlı oyuncu tur başına −1/4 alır.

Tablo 0.6 tek bir ilkeyi gösterir: eşit karışımdan her sapma, onu fark eden bir rakibe karşı kaybettirir. Genel olarak (p_T, p_K, p_M) oynayana karşı rakibin Kağıt'ı p_T − p_M, Makas'ı p_K − p_T, Taş'ı p_M − p_K getirir. Bu üç sayının toplamı sıfırdır; bu yüzden ya hepsi sıfırdır (eşit karışım) ya da en az biri pozitiftir ve rakip onu seçer.

İnsanlar nasıl oynuyor? Laboratuvar deneylerinde üç hamlenin toplam sıklığı 1/3'e yakın çıksa da ardışık hamleler bağımsız değildir: kazanan aynı hamleyi tekrarlamaya, kaybeden hamlesini değiştirmeye eğilimlidir (Wang, Xu ve Zhou, 2014). Uzun vadeli sıklıklar eşit karışıma benzese de her tur öncekinden bağımsız seçilmediği için oynayış tahmin edilebilir hâle gelir. Örüntü öğrenen bir rakip tam olarak bunu sömürür: sıklıklara değil, “bir önceki turdan sonra ne geliyor?” sorusuna bakar. Kuramın önerdiği (1/3, 1/3, 1/3) karışımı, ancak her tur bağımsız bir rastgele seçimle uygulanırsa yenilmezdir.

0.10Oyun ağacı ve büyüme hızı

Matris, oyuncuların aynı anda seçim yaptığı oyunlar içindir. Satrançta, pazarlıkta ya da bir firmanın pazara girip girmemesinde ise oyuncular sırayla hamle yapar ve sonraki oyuncu öncekinin hamlesini görür. Böyle oyunlar bir ağaçla çizilir ve geriye doğru çıkarımla çözülür. Ağaçlar hızla büyüdüğü için kesim, büyüme hızını anlatan O ve Θ gösterimiyle biter.

0.10.1Oyun ağacını okumak

Ağaçta kökten bir yaprağa giden her yol, oyunun bir oynanışıdır. Yaprak sayısı, oyunun olası sonuçlarının sayısıdır. Matris ile ağaç arasındaki temel fark bilgidir: ağaçta sonraki oyuncu, önceki oyuncunun hangi dalı seçtiğini bilir ve buna göre karar verir. Bu yüzden aynı oyuncunun ağaçta birden çok düğümü olabilir; her düğüm farklı bir geçmişe karşılık gelir ve her birinde ayrı karar verilir.

0.10.2Geriye doğru çıkarım

Sıralı bir oyunu çözmek için kökten değil, yapraklardan başlanır. Fikir şudur: son hamleyi yapan oyuncunun kararı kolaydır, çünkü ondan sonra kimse hamle yapmaz; o yalnız kendi kazancını karşılaştırır. Onun kararı bilinince bir önceki oyuncu, her dalın sonunda ne olacağını bilerek karar verebilir. Bu, köke ulaşılana kadar tekrarlanır.

Sonuç ilk bakışta şaşırtıcı olabilir: (3, 0) yaprağı Ayşe için en büyük sayıdır, ama oyun oraya hiç varmaz. Ayşe Sakla derse Bora Çekil'i değil Devam'ı seçer, çünkü Devam ona 2, Çekil 0 verir. Ayşe bunu önceden hesaplar ve 1 yerine 2 aldığı Göster'i seçer. Geriye doğru çıkarımın özü budur: bir oyuncu kendi en iyi yaprağına değil, ötekilerin en iyi tepkileri altında ulaşılabilen en iyi sonuca bakar.

Çözümün tam yazımında Bora'nın her düğümdeki seçimi verilir, oynanmayan düğümünkü de. Bunun nedeni, Ayşe'nin kararının Bora'nın oynanmayan düğümdeki tepkisine dayanmasıdır: Ayşe'nin Sakla'yı reddetmesinin gerekçesi, Bora'nın Sakla'dan sonra Devam diyeceğidir. Bir stratejinin her durum için ne yapılacağını söyleyen eksiksiz bir plan olması, sıralı oyunlarda bu yüzden önemlidir.

0.10.3Büyüme hızı: O ve Θ

Geriye doğru çıkarım her düğümü bir kez ziyaret eder. Küçük ağaçlarda bu hızlıdır; ama satranç gibi bir oyunun ağacında düğüm sayısı evrendeki atom sayısını aşar. Bir yöntemin pratikte kullanılıp kullanılamayacağını anlamak için adım sayısının girdi büyüklüğüyle nasıl büyüdüğüne bakılır. Bunun dili O ve Θ gösterimidir.

Son örnek tanımla denetlenebilir. Alt sınır kolaydır: 3n² + 5n ≥ 3n², yani c₁ = 3. Üst sınır için n ≥ 5 iken 5n ≤ n · n = n² olduğu kullanılır: 3n² + 5n ≤ 3n² + n² = 4n², yani c₂ = 4 ve n₀ = 5. Böylece 3n² ≤ 3n² + 5n ≤ 4n² ve fonksiyon Θ(n²)'dir. 5n terimi büyük n'de n²'nin yanında önemsizleşir.

Tablo 0.7 üstel büyümenin neden bir engel olduğunu gösterir. Saniyede 10⁹ işlem yapan bir bilgisayar, d = 30 derinlikli ikili bir ağacı yaklaşık bir saniyede çözer; d = 60'ta ise yaklaşık 2⁶⁰/10⁹ ≈ 1,15 · 10⁹ saniye, yani 36 yıldan fazla gerekir. Derinliği iki katına çıkarmak süreyi iki katına değil, milyar katına çıkarır. Bu yüzden algoritmik oyun kuramında “çok terimli zamanda” (n², n³ gibi) çözülebilen problemler kolay, yalnız üstel zamanda çözülebildiği düşünülen problemler zor sayılır.

0.11Sık yapılan hatalar

Bölümdeki hataların çoğu birkaç ortak kaynaktan gelir: sırayı karıştırmak (profilde, matriste, ağaçta), bir sayıyı bir seçenekle karıştırmak (max ve argmax), olasılıkları gerekmeyen yerde toplamak ve bir oyuncunun neyi seçebildiğini unutmak. Tablo 0.8 her konunun en sık hatasını ve doğrusunu bir arada verir.

0.12Özet

• Gösterim. S₁ × S₂ bütün strateji profillerinin kümesidir; profilde sıra önemlidir. u_i, bir profile oyuncu i'nin kazancını (bir sayı) karşılık getirir. Profil sayısı çarpım kuralıyla, sırasız seçimler C(n, k) ile sayılır.
• Σ, seri, max ve argmax. Σ ile önce her terim hesaplanır, sonra toplanır. 0 ≤ δ < 1 için 1 + δ + δ² + … = 1/(1 − δ). max bir değerdir, argmax onu veren seçenek(ler)dir; eşitlikte argmax bir kümedir.
• Türev. Sürekli seçimde en büyük değer f′ = 0 ile bulunur ve f″ < 0 ile denetlenir. u(q) = q(12 − q − r) için en iyi miktar q*(r) = max{0, (12 − r)/2}'dir.
• Üs, e ve ln. x^a · x^b = x^a+b, x⁰ = 1. ln, e^x'in tersidir ve çarpımı toplamaya çevirir; (ln x)′ = 1/x, (e^x)′ = e^x.
• Türev kuralları. (fg)′ = f′g + fg′; zincir: dış türev × iç türev; ∂u/∂q: öteki değişkenler sabit tutulur. Her oyuncu kendi değişkenine göre kısmi türevi sıfıra eşitler; iki firma örneğinde q = r = 4.
• Olasılık. Eşit olası sonuçlarda sayılır ve bölünür; bağımsız olayların olasılıkları çarpılır, aynı anda olamayan olaylarınki toplanır; “en az bir” için tümleyen kullanılır. P(A | B) = P(A ∩ B)/P(B); Bayes: P(A | B) = P(B | A) · P(A)/P(B).
• Beklenen değer. E[X] = Σ x · P(x): uzun vadeli ortalamadır, tek denemenin sonucu değildir. Karar net beklenen değere göre verilir. X ≥ 0 ise E[X] = ∫ P(X > t) dt.
• Sürekli dağılım. U[0, 1]'de olasılık bir alandır: P(X ≤ x) = x, tek noktanın olasılığı 0, E[X] = 1/2. İntegral eğri altındaki alandır, Σ'nın sürekli hâlidir.
• Karışık strateji. Eylemler üzerinde bir olasılık dağılımıdır; her tur tek bir saf hamle rastgele seçilir. Softmax: P(i) ∝ e^λv_i; λ = 0'da eşit, λ büyüdükçe argmax.
• Kazanç matrisi. (a, b): a satır, b sütun oyuncusunun kazancı. Beklenen kazanç xᵀAy'dir; Ay her satırın beklentisidir.
• En iyi tepki. Rakibin seçimi sabitlenir; kendi kazancının argmax'ı alınır. İki sayısı da işaretli hücrede iki oyuncu da en iyi tepkisini oynar (Nash dengesi).
• Denklemler. x = (−b ± √Δ)/(2a); olasılık olan kök [0, 1]'dedir. Kayıtsızlık: karıştırılan eylemler eşit beklenen kazanç verir; bir oyuncunun kayıtsızlığı rakibin olasılığını belirler. Kart Gösterme'de p = q = 1/3, Ayşe'nin kazancı −1/3.
• Taş-Kağıt-Makas. (1/3, 1/3, 1/3) yenilmez (beklenen kazanç 0); hep Taş tur başına −1, (1/2, 1/4, 1/4) tur başına −1/4 kaybettirir.
• Geriye doğru çıkarım. Yapraktan köke; sırası gelen kendi kazancının en büyüğünü seçer. Kart oyununda sonuç Göster → Çekil, (2, 3).
• O ve Θ. log log n < log n < n < n log n < n² < 2ⁿ; sabitler ve küçük terimler atılır. İkili ağaçta geriye doğru çıkarım Θ(2^d) adımdır.

Tablo 0.9 her aracı, oyun kuramında en çok kullanıldığı yerle eşleştirir.

0.13Kavram listesi

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

• Kartezyen çarpım Cartesian product
• strateji profili strategy profile
• kazanç fonksiyonu payoff function
• çarpım kuralı product rule
• kombinasyon C(n, k) binomial coefficient
• geometrik seri geometric series
• iskonto faktörü discount factor
• argmax argmax
• türev derivative
• zincir kuralı chain rule
• kısmi türev partial derivative
• koşullu olasılık conditional probability
• Bayes kuralı Bayes' rule
• ön olasılık prior
• son olasılık posterior
• beklenen değer expected value
• beklenen kazanç expected payoff
• düzgün dağılım uniform distribution
• olasılık yoğunluğu probability density
• integral integral
• kuyruk olasılığı tail probability
• karışık strateji mixed strategy
• saf strateji pure strategy
• destek support
• olasılık vektörü probability vector
• logit fonksiyonu logit function
• softmax seçimi softmax choice
• kazanç matrisi payoff matrix
• sıfır toplamlı oyun zero-sum game
• en iyi tepki best response
• diskriminant discriminant
• kayıtsızlık ilkesi indifference principle
• sıralı oyun sequential game
• oyun ağacı game tree
• geriye doğru çıkarım backward induction
• büyük-O ve Θ gösterimi big-O and Θ notation

0.14Kendini Dene

1. Üç oyuncunun sırasıyla 3, 3 ve 2 stratejisi vardır. Kaç strateji profili vardır? Bir bekçi 5 hedeften 3'ünü koruyabiliyorsa kaç saf stratejisi vardır; hedefler “sırayla” seçilseydi kaç sıralı seçim sayılırdı?

   Cevap

   Çarpım kuralı: 3 · 3 · 2 = 18 profil. Bekçi: C(5, 3) = 5!/(3! · 2!) = 120/12 = 10 saf strateji. Sıralı seçim 5 · 4 · 3 = 60'tır; her üçlü 3! = 6 farklı sırada sayıldığı için 60/6 = 10.

2. Bir işbirliği her tur 4 kazandırıyor ve gelecek turlar δ = 0,75 ile tartılıyor. Bu turdan başlayan toplam iskontolu kazanç kaçtır? Kazanç ancak bir sonraki turdan itibaren gelseydi ne olurdu?

   Cevap

   Bugünden başlayan: 4/(1 − 0,75) = 4/0,25 = 16. Yarından başlayan: 4 · 0,75/(1 − 0,75) = 3/0,25 = 12. Fark bugünkü 4'tür: 16 − 12 = 4.

3. Bir torbada iki para var: biri adil, öteki iki yüzü de yazı olan hileli bir para. Torbadan rastgele bir para çekilip atılıyor ve yazı geliyor. Paranın hileli olma olasılığı nedir? Aynı para ikinci kez atılıp yine yazı gelirse bu olasılık ne olur?

   Cevap

   Ön olasılık P(hileli) = 1/2. P(yazı) = 1/2 · 1 + 1/2 · 1/2 = 3/4. Bayes: P(hileli | yazı) = (1 · 1/2)/(3/4) = 2/3. İki yazı için adil paranın olasılığı 1/4'tür: P(iki yazı) = 1/2 · 1 + 1/2 · 1/4 = 5/8 ve P(hileli | iki yazı) = (1/2)/(5/8) = 4/5. 100 deneyle sayarak: 50 hileli denemenin hepsi, 50 adil denemenin 12,5'i iki yazı verir; 50/62,5 = 0,8.

4. Bir çark 1/2 olasılıkla 0 TL, 1/3 olasılıkla 6 TL, 1/6 olasılıkla 18 TL ödüyor; çevirmek 6 TL. Net beklenen kazanç kaçtır? Diğer ödüller aynı kalırken 18 TL'lik ödül kaç TL olsaydı oyun adil olurdu?

   Cevap

   Olasılıklar toplamı 1/2 + 1/3 + 1/6 = 1 ✓. E = 0 · 1/2 + 6 · 1/3 + 18 · 1/6 = 0 + 2 + 3 = 5 TL; net 5 − 6 = −1 TL. Adil ödül y: 2 + y/6 = 6 ⇒ y/6 = 4 ⇒ y = 24 TL.

5. Sıfır toplamlı bir oyunda satır oyuncusunun (Ayşe) kazanç matrisi A = [[2, −1], [−1, 1]]'dir (satırlar Yukarı, Aşağı; sütunlar Sol, Sağ). Bora y = (1/2, 1/2) oynarsa Ay nedir ve Ayşe'nin en iyi tepkisi hangisidir? Bora Sol'u hangi q ile, Ayşe Yukarı'yı hangi p ile oynarsa iki oyuncu da kayıtsız kalır? Ayşe'nin beklenen kazancı kaçtır?

   Cevap

   Ay = (2 · 1/2 − 1 · 1/2, −1 · 1/2 + 1 · 1/2) = (1/2, 0); en iyi tepki Yukarı. Ayşe'nin kayıtsızlığı: 2q − (1 − q) = −q + (1 − q) ⇒ 3q − 1 = 1 − 2q ⇒ q = 2/5. Bora'nın kazançları −A'dır; kayıtsızlığı: Sol −2p + (1 − p) = 1 − 3p, Sağ p − (1 − p) = 2p − 1 ⇒ 1 − 3p = 2p − 1 ⇒ p = 2/5. Ayşe'nin kazancı 3 · 2/5 − 1 = 1/5 (denetim: 1 − 2 · 2/5 = 1/5 ✓).

6. Fiyat 20 − (q + r), maliyet sıfır; firmanın kârı u(q) = q(20 − q − r)'dir. Rakip r = 6 üretirse en iyi miktar ve kâr nedir? Bu noktanın tepe olduğu iki yolla nasıl gösterilir? Genel en iyi tepki formülü ve ∂u/∂r nedir?

   Cevap

   u(q) = q(14 − q) = 14q − q²; u′(q) = 14 − 2q = 0 ⇒ q = 7, u(7) = 49. u″ = −2 < 0; komşular u(6) = u(8) = 48 < 49. Genel: ∂u/∂q = 20 − 2q − r = 0 ⇒ q*(r) = max{0, (20 − r)/2}. ∂u/∂r = −q.

7. Ayşe önce Sol ya da Sağ der; Bora bunu görüp cevap verir. Sol'dan sonra Bora a derse (2, 1), b derse (0, 0); Sağ'dan sonra c derse (3, 0), d derse (1, 2) olur (Ayşe, Bora). Geriye doğru çıkarımın sonucu nedir? Her düğümde 3 dal olan d derinlikli bir ağaçta kaç yaprak vardır; d = 10 için kaç?

   Cevap

   Sol'dan sonra Bora a'yı seçer (1 > 0) ⇒ (2, 1). Sağ'dan sonra Bora d'yi seçer (2 > 0) ⇒ (1, 2). Ayşe kökte 2 ile 1'i karşılaştırır ve Sol der: sonuç (2, 1). (3, 0) Ayşe'nin en büyük sayısıdır ama Bora c'yi seçmez. Yaprak sayısı 3^d; d = 10 için 3¹⁰ = 59 049. Geriye doğru çıkarım Θ(3^d) adım sürer.

8. Üç hamlenin değerleri v = (ln 2, 0, 0) ve λ = 1'dir. Softmax olasılıkları nedir? İki seçenekte v₁ − v₂ = 1 ve λ = ln 4 ise logit olasılığı P(1) kaçtır? Bütün değerlere 5 eklenirse bu olasılıklar değişir mi?

   Cevap

   Üslü sayılar e^{ln 2} = 2, e⁰ = 1, e⁰ = 1; toplam 4. Olasılıklar (2/4, 1/4, 1/4) = (1/2, 1/4, 1/4): iki paralı yanlı karışımın aynısı. Logit: e^{−λ · 1} = e^{−ln 4} = 1/4, P(1) = 1/(1 + 1/4) = 4/5. Değerlere 5 eklemek her üssü e^5λ ile çarpar; pay ve paydada sadeleşir ve olasılıklar değişmez.

0.15İleri okuma

• M. J. Osborne, An Introduction to Game Theory (2004), Bölüm 17 (Matematik eki): sayılar, kümeler, fonksiyonlar, profiller, diziler ve olasılık konularını oyun kuramında kullanıldığı ölçüde, kısa ve örnekli bir özetle verir.
• J. K. Blitzstein ve J. Hwang, Introduction to Probability (2019), Bölüm 1–5: sayma, koşullu olasılık, Bayes kuralı, beklenen değer ve düzgün dağılımı çok sayıda örnek ve simülasyonla anlatır.
• E. Lehman, F. T. Leighton ve A. R. Meyer, Mathematics for Computer Science (2017): sayma, toplamlar ve asimptotik gösterim (O, Θ) için bilgisayar mühendisliği öğrencilerine yönelik ücretsiz bir ders kitabıdır.
• Z. Wang, B. Xu ve H.-J. Zhou, “Social cycling and conditional responses in the Rock-Paper-Scissors game” (2014): Taş-Kağıt-Makas'ta insanların kazanınca tekrarlayıp kaybedince değiştirdiğini gösteren laboratuvar deneyidir; kısa ve okunabilirdir.

0.16Kaynaklar

1. J. K. Blitzstein, J. Hwang, Introduction to Probability, 2. baskı, CRC Press (Chapman & Hall), 2019.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022 (Bölüm 3: asimptotik gösterim).
3. E. Lehman, F. T. Leighton, A. R. Meyer, Mathematics for Computer Science, MIT, 2017.
4. R. D. McKelvey, T. R. Palfrey, “Quantal response equilibria for normal form games”, Games and Economic Behavior 10(1), 6–38, 1995.
5. M. J. Osborne, An Introduction to Game Theory, Oxford University Press, 2004.
6. Z. Wang, B. Xu, H.-J. Zhou, “Social cycling and conditional responses in the Rock-Paper-Scissors game”, Scientific Reports 4, 5830, 2014.

Ön koşul özeti: Algoritmik Oyun Kuramı ön koşulları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.