Algoritmik Oyun Kuramı İçin Ön Bilgiler

• Strateji profillerinin kümesi Kartezyen çarpımdır: S = S₁ × S₂ × ··· × Sₙ. Eleman sayısı |S₁|·|S₂|·…·|Sₙ| olur.
• s₋ᵢ, i oyuncusu dışındaki herkesin stratejisini gösterir. Böylece bir profil (sᵢ, s₋ᵢ) biçiminde yazılır.
• Niceleyicilerle Nash dengesi: her i oyuncusu ve her sᵢ′ ∈ Sᵢ için uᵢ(sᵢ*, s₋ᵢ*) ≥ uᵢ(sᵢ′, s₋ᵢ*).
• Değillemede niceleyiciler yer değiştirir: uᵢ(sᵢ′, s₋ᵢ*) > uᵢ(sᵢ*, s₋ᵢ*) koşulunu sağlayan bir i oyuncusu ve bir sᵢ′ stratejisi vardır. Bu, kârlı bir sapmadır.
• Bağıntılar: tercihler ikili bağıntılardır (≻, ≿). Oylama kuramı geçişlilik ve tamlık özelliklerine dayanır.

• Doğrudan ispat: hiçbir tek taraflı sapmanın hiçbir oyuncunun kazancını artırmadığı tek tek gösterilir.
• Tümevarım: geriye doğru çıkarım ve Zermelo teoremi sonlu oyun ağacının yapraklarından köke doğru ilerler. Nim stratejileri konum üzerinde tümevarımla kanıtlanır.
• Çelişki: strateji çalma argümanı, Hex oyununda ilk oyuncunun kaybedemeyeceğini gösterir.
• Karşı örnek: genel bir iddiayı çürütmek için küçük bir oyun yeter. Örneğin monotonluğu bozan bir oy profili.
• İmkânsızlık teoremleri (Arrow, Gibbard–Satterthwaite, Myerson–Satterthwaite) bir özellik listesini aynı anda sağlayan hiçbir kural olmadığını söyler.

• n nesnenin n! sıralaması (permütasyonu) vardır. n elemanlı bir kümenin 2ⁿ alt kümesi vardır. C(n, k) = n! / (k!(n − k)!).
• Shapley değeri, i oyuncusunun n! geliş sırası üzerinden marjinal katkılarının ortalamasıdır. Eşdeğer biçim: φᵢ = Σ (S ⊆ N∖{i}) |S|!(n − |S| − 1)!/n! · [v(S ∪ {i}) − v(S)]. Bu toplam 2ⁿ⁻¹ koalisyon üzerinden alınır.
• m aday için m! kesin sıralama vardır. Kemeny kuralının çok büyük bir uzayda arama yapması bundandır.
• n oyuncunun koalisyon yapılarının (küme bölüntülerinin) sayısı Bell sayısı Bₙ'dir: B₃ = 5, B₄ = 15, B₁₀ = 115.975.

• Geometrik seri: 0 ≤ δ < 1 için Σ_t≥0 δᵗ = 1/(1 − δ). Her turda c kazancının toplam değeri bu yüzden c/(1 − δ) olur.
• Harmonik sayı Hₙ = 1 + 1/2 + … + 1/n ≈ ln n + 0,577. Adil maliyet paylaşımı oyunlarında İstikrarın Bedeli (PoS) bu sayıyla sınırlıdır: PoS ≤ Hₙ.
• Logaritma kuralları: ln(ab) = ln a + ln b, ln(aᵏ) = k ln a. Logaritmik büyüme çok yavaştır (ln 10⁶ ≈ 13,8).
• Üstel fonksiyon: her x için e^x ≥ 1 + x; küçük ε için e^ε ≈ 1 + ε. Diferansiyel mahremiyet güvenceleri e^ε çarpanlarıyla ifade edilir.
• Çarpımsal ağırlıklar güncellemesi wᵢ ← wᵢ · e^η·gᵢ biçimindedir. Üsteki kazançları toplamak ağırlıkları çarpmak demektir.

• Birinci mertebe koşulu: türevlenebilir bir f'nin iç maksimumunda f′(x) = 0 olur. İkinci türeve (f″ < 0) ya da uç noktalara da bakılır, çünkü f′ = 0 bir minimumu da gösterebilir.
• Çarpım kuralı (fg)′ = f′g + fg′ ve kuvvet kuralı (xᵏ)′ = k xᵏ⁻¹ dersteki türetmeler için yeterlidir.
• Cournot: her firma qᵢ·P(q₁ + q₂) − maliyet kârını maksimize eder. Türev alınınca en iyi tepki fonksiyonu çıkar.
• Birikmiş maliyet olarak integral: Beckmann potansiyeli Φ(f) = Σₑ ∫₀^fₑ ℓₑ(t) dt. Bu potansiyelin fₑ'ye göre türevi ℓₑ(fₑ) gecikmesidir.

Örnek (Bölüm 5). n teklifçi var ve rakipler β·vⱼ teklif ediyor, vⱼ ~ U[0, 1]. Bu durumda b teklifi (b/β)ⁿ⁻¹ olasılıkla kazanır. (v − b)(b/β)ⁿ⁻¹ maksimize edilirken türev (n − 1)(v − b) = b olduğunda sıfırlanır. Sonuç b = (n − 1)v/n olur.

• Her λ ∈ [0, 1] için f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y) ise f dışbükeydir. İki kez türevlenebilir f için bu koşul f″ ≥ 0 demektir. −f dışbükeyse f içbükeydir.
• Dışbükey bir fonksiyonun yerel minimumu genel minimumdur. Dışbükey Beckmann potansiyelinin Wardrop dengesini iyi tanımlaması bu yüzdendir.
• Bir küme, herhangi iki noktası arasındaki doğru parçasını içeriyorsa dışbükeydir. Karışık stratejiler kümesi (simpleks) dışbükeydir. Kakutani teoremi bu özelliğe dayanır.
• Jensen eşitsizliği: f dışbükeyse f(E[X]) ≤ E[f(X)]; u içbükeyse E[u(X)] ≤ u(E[X]). Bu yüzden içbükey fayda riskten kaçınma anlamına gelir.

• İki matrisli oyun (A, B): i satırı j sütunuyla karşılaşınca satır oyuncusu Aᵢⱼ, sütun oyuncusu Bᵢⱼ kazanır. Sıfır toplamlı oyunda B = −A olur.
• Karışık strateji Δ = { x : xᵢ ≥ 0, Σxᵢ = 1 } simpleksindeki bir vektördür. Desteği, xᵢ > 0 olan eylemlerin kümesidir.
• Beklenen kazançlar: (Ay)ᵢ, satır oyuncusunun y'ye karşı saf i eyleminden aldığı kazançtır. xᵀAy ise x'in y'ye karşı kazancıdır.
• Destek sayımı küçük doğrusal denklem sistemleri çözer: destekteki kazançlar eşittir ve olasılıkların toplamı 1'dir.

• f'nin sabit noktası f(x) = x koşulunu sağlayan noktadır. Küme değerli bir F eşlemesi için bu koşul x ∈ F(x) olur.
• Brouwer: boş olmayan, kompakt (kapalı ve sınırlı) ve dışbükey bir K ⊂ ℝⁿ kümesini kendine götüren her sürekli f'nin bir sabit noktası vardır.
• Kakutani: F(x) değerleri boş olmayan ve dışbükey, grafiği kapalı olan bir F eşlemesi için de aynı sonuç geçerlidir. Nash bu teoremi karışık profiller üzerindeki en iyi tepki eşlemesine uygular: σ* ∈ BR(σ*).
• Bu teoremler varlığı kanıtlar ama verimli bir algoritma vermez. PPAD sınıfı tam olarak bu boşluğu ölçer.
• Bölüm 6'daki benimseme modeli ya da Bölüm 13'teki öğrenme kuralları gibi dinamikler, güncelleme dönüşümlerinin sabit noktalarında durur.

• Kesikli dağılım: pᵢ ≥ 0 olasılıkları ve Σpᵢ = 1. Sürekli dağılım: f ≥ 0 yoğunluğu ve F(x) = P(X ≤ x) dağılım fonksiyonu.
• Düzgün dağılım U[0, 1]: [0, 1] üzerinde F(x) = x ve f(x) = 1. E[X] = 1/2, Var(X) = 1/12.
• Bağımsızlık: P(A ∩ B) = P(A)·P(B). Bağımsız özel değerler (IPV), her teklifçinin değerinin bağımsız çekildiği anlamına gelir.
• Açık artırmalardaki temel adım: k bağımsız U[0, 1] değer için P(hepsi ≤ b) = bᵏ. Bu, değerini teklif eden k rakibi geçme olasılığıdır.

• E[X] = Σ x·P(X = x) (kesikli) ya da ∫ x f(x) dx (sürekli).
• Doğrusallık: E[aX + bY] = aE[X] + bE[Y]. X ile Y bağımlı olsa bile geçerlidir.
• f doğrusal değilse genelde E[f(X)] ≠ f(E[X]) olur (dışbükeylik kartındaki Jensen eşitsizliği).
• Var(X) = E[X²] − (E[X])² yayılımı ölçer. Ortalaması aynı iki piyangonun riski çok farklı olabilir.
• Beklenen kazanç en olası kazanç değildir: 0,3 olasılıkla 100 ödeyen bir piyango hiçbir zaman 30 ödemez.

• P(B) > 0 için P(A | B) = P(A ∩ B) / P(B).
• Bayes kuralı: P(H | E) = P(E | H)·P(H) / P(E). Payda toplam olasılık kuralıyla bulunur: P(E) = P(E | H)P(H) + P(E | ¬H)P(¬H).
• Adalet oranları koşullu olasılıklardır: doğru pozitif oranı TPR = P(Ŷ = 1 | Y = 1), yanlış pozitif oranı FPR = P(Ŷ = 1 | Y = 0), pozitif tahmin değeri PPV = P(Y = 1 | Ŷ = 1).
• Taban oranını göz ardı etmek: P(H) hesaba katılmazsa doğru bir testin pozitif sonucu olduğundan çok daha kesin görünür.
• Ardışık güncelleme: bugünün son olasılığı yarının ön olasılığıdır.

• n bağımsız U[0, 1] değer için k'ıncı en yüksek değerin beklentisi (n + 1 − k)/(n + 1) olur. En yüksek değerin beklentisi n/(n + 1), ikinci en yüksek değerinki (n − 1)/(n + 1)'dir.
• İkinci fiyat açık artırmasının geliri = E[ikinci en yüksek değer] = (n − 1)/(n + 1).
• b = (n − 1)v/n teklifiyle birinci fiyat açık artırmasının geliri = (n − 1)/n · n/(n + 1) = (n − 1)/(n + 1). Gelir eşdeğerliğinin öngördüğü gibi sonuç aynıdır.
• Kazananın laneti: tahmin hataları U[−a, a] dağılımındaysa n hatanın en büyüğünün beklentisi a(n − 1)/(n + 1)'dir. Kazanan, değeri en çok abartan teklifçidir.
• Sanal değer φ(v) = v − (1 − F(v))/f(v). U[0, 1] için φ(v) = 2v − 1 olur ve en iyi rezerv fiyat 1/2 çıkar.

• Büyük sayılar yasası: N bağımsız çekilişin örneklem ortalaması gerçek ortalamaya yaklaşır. Standart hatası σ/√N'dir.
• Karışıklık matrisi oranları: TPR = TP/(TP + FN), FPR = FP/(FP + TN), PPV = TP/(TP + FP), seçim oranı = (TP + FP)/toplam.
• Bir simülasyonda oyunların görülme sıklıkları karışık stratejileri tahmin eder. Küçük örneklerde bu sıklıklar çok dalgalanır.
• Örneklem karmaşıklığı, ε doğruluğunda tahmin için kaç örnek gerektiğini sorar. Örnek sayısı azsa aşırı uyum ortaya çıkar.

• Markov özelliği: sonraki durum geçmişin tamamına değil, yalnız şimdiki duruma (ve eyleme) bağlıdır.
• Markov karar süreci (Markov decision process, MDP) şu öğelerden oluşur: durumlar S, eylemler A, geçiş olasılıkları P(s′ | s, a), ödüller r ve iskonto γ ∈ [0, 1). Amaç E[Σ γᵗ rₜ] değerini maksimize etmektir.
• Politika durumları eylemlere eşler. Açgözlü politika argmaxₐ Q(s, a) eylemini seçer.
• Q-öğrenme güncellemesi: Q(s, a) ← Q(s, a) + α[r + γ·maxₐ′ Q(s′, a′) − Q(s, a)]. Burada α öğrenme oranıdır.

• Bir optimizasyon probleminde karar değişkenleri, maksimize ya da minimize edilecek bir amaç ve uygun kümeyi tanımlayan kısıtlar bulunur.
• max f bir değerdir. argmax f ise maksimum noktalarının kümesidir. Eşitlik durumunda argmax birden çok nokta içerebilir. Mekanizmaların bu yüzden bir eşitlik bozma kuralına ihtiyacı vardır.
• En iyi tepki: BRᵢ(s₋ᵢ) = argmax (sᵢ üzerinden) uᵢ(sᵢ, s₋ᵢ). VCG, x* = argmaxₓ Σᵢ bᵢ(x) tahsisini seçer.
• OPT en iyi amaç değerini gösterir. Anarşinin Bedeli bir dengenin maliyetini OPT ile karşılaştırır.

• Bir LP, doğrusal eşitsizlik kısıtları altında doğrusal bir amacı maksimize ya da minimize eder. Uygun küme dışbükey bir çokyüzlüdür. Optimum varsa bir köşede elde edilir.
• LP'ler polinom zamanda çözülür (elipsoit ve iç nokta yöntemleri). Simpleks yöntemi pratikte hızlıdır ama en kötü durumda üsteldir.
• Dualite: her maksimizasyon LP'sinin bir minimizasyon duali vardır. Zayıf dualite: birincil değer ≤ dual değer. Güçlü dualite: optimumda ikisi eşittir.
• Sıfır toplamlı oyunda satır oyuncusunun LP'si: her j sütunu için Σᵢ xᵢAᵢⱼ ≥ v, Σxᵢ = 1 ve x ≥ 0 kısıtları altında v maksimize edilir. Sütun oyuncusunun LP'si bunun dualidir. Dolayısıyla max min = min max olur (von Neumann'ın minimaks teoremi).
• Korelasyonlu ve kaba korelasyonlu dengeler de LP uygunluk problemleridir. Bu yüzden polinom zamanda hesaplanırlar.

• Yaygın büyüme hızları: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!). O bir üst sınırdır, Θ ise sıkı sınırdır.
• Polinom zaman (O(nᵏ)), “verimli” sözcüğünün çalışma tanımıdır.
• Dallanma çarpanı b ve derinliği d olan bir oyun ağacının yaklaşık bᵈ yaprağı vardır. Hamleler en iyi sırayla incelenirse alfa-beta budaması yaklaşık b^d/2 yaprağa bakar.
• Dersteki örnekler: Gale–Shapley O(n²), Macar algoritması O(n³), ikili yığınla Dijkstra O((V + E) log V).

• Özyineleme: minimaks bir düğümü çocuklarının değerlerinden hesaplar. Geriye doğru çıkarım da oyun ağacı üzerinde aynı fikirdir.
• Dinamik programlama çözülmüş alt problemleri saklar. Örneğin bir çıkarma oyununun kazanan ve kaybeden konumlarını.
• Açgözlü algoritmalar her adımda yerel olarak en iyi seçimi yapar. Hızlıdır ama her zaman optimum vermez. Macar algoritması ise optimum atamayı bulur.
• Gale–Shapley (ertelenmiş kabul): teklif edenler tercih sırasıyla teklif eder, alıcılar en iyi teklifi bekletir. Algoritma, teklif eden taraf için en iyi olan kararlı bir eşleştirmeyle biter.

• Ağaç terimleri: kök başlangıç konumudur, yapraklar oyun sonları ya da derinlik sınırındaki konumlardır. Bir düğümün derinliği kökten uzaklığıdır. Oyun ağacında katmanlar sırayla MAX ve MIN oyuncusuna aittir.
• Her iç düğümün b çocuğu varsa d derinlikte b^d yaprak, toplamda 1 + b + … + b^d = (b^d+1 − 1)/(b − 1) düğüm vardır. Düğümlerin büyük çoğunluğu son katmandadır: b = 10 için yaklaşık %90'ı.
• Özyinelemeli gezinmede bir düğümün değeri çocuklarının değerlerinden hesaplanır. Bellekte yalnızca kökten o anki düğüme giden yol durur. Bu yüzden süre O(b^d) iken bellek O(b·d) kadardır.
• Logaritma: N yapraklık bir bütçeyle inilebilecek derinlik d = log_b N = ln N / ln b olur. b^d/2 = (√b)^d olduğundan en iyi hamle sırasında alfa-beta aynı bütçeyle yaklaşık iki kat derine iner.
• Yinelemeli derinleştirme aramayı d = 1, 2, 3, … için tekrarlar. Önceki turların toplam maliyeti son turun yalnızca yaklaşık 1/(b − 1) katıdır.

• XOR (⊕) ikili basamakları eldesiz toplar: sonucun bir biti, o konumda 1 olan girdi sayısı tek ise 1 olur.
• x ⊕ x = 0 ve x ⊕ 0 = x. XOR değişmeli ve birleşmelidir.
• Nim (normal oyun): yığınların nim toplamı 0 ise hamle sırası gelen oyuncu, iki taraf da en iyi oynadığında kaybeder.

• P: polinom zamanda çözülebilen problemler. NP: önerilen bir çözümün polinom zamanda doğrulanabildiği problemler.
• NP-zor: her NP problemi polinom zamanda buna indirgenir. NP-tam = hem NP-zor hem NP'de. Dersteki örnekler: kombinatoryal açık artırmalarda VCG'nin argmax adımı, Kemeny sıralaması, bazı oylama kurallarını manipüle etmek.
• Nash dengesi bulmak neden NP-tam değildir? Denge her zaman vardır, bu yüzden evet/hayır sorusu önemsizdir. Zorluk dengeyi bulmaktadır.
• PPAD: çözümü bir parite (çizginin sonu) argümanıyla güvence altında olan arama problemleri. Brouwer, Sperner ve Nash bu sınıftadır. İki oyunculu Nash dengesi PPAD-tamdır (Chen–Deng, 2006; dergi sürümü Chen–Deng–Teng, 2009).
• PLS: yerel arama problemleri. Bir tıkanıklık oyununun saf dengesini bulmak PLS-tamdır.

• Çizgeler düğümlerden ve (yönlü ya da yönsüz) kenarlardan oluşur. Komşuluk listesi ya da komşuluk matrisiyle saklanır. Temel kavramlar: yol, döngü, bağlantılılık, iki parçalı çizge.
• En kısa yollar: Dijkstra negatif olmayan ağırlıklar ister. Bellman–Ford negatif ağırlıklara izin verir (negatif döngü olmamak koşuluyla).
• Akışlar: s'den t'ye r birimlik akış yollara bölünür. Bir kenarın yükü, o kenarı kullanan yolların akışlarının toplamıdır. Her iç düğümde akış korunur.
• Yönlendirme oyunlarında kenar maliyetleri sabit ağırlık değil, yüke bağlı ℓₑ(x) gecikme fonksiyonlarıdır. Tıkanıklığı ve Braess paradoksunu doğuran budur.
• Döngüler başka yerlerde de önemlidir: En İyi Takas Döngüleri (TTC) bir işaret çizgesinin döngülerini çıkarır. Döngü içeren bir çoğunluk çizgesi Condorcet paradoksudur.

• Bir piyangonun beklenen faydası Σ p(x)·u(x)'tir. Risk nötr oyuncuda u(x) = x olur. Riskten kaçınma içbükey u demektir.
• Kayıtsızlık ilkesi: karışık Nash dengesinde bir oyuncunun desteğindeki her eylem aynı beklenen kazancı getirir. Destek dışındaki eylemler daha fazlasını getirmez.
• Bu yüzden her oyuncunun karıştırma olasılıkları öteki oyuncuyu kayıtsız bırakacak biçimde seçilir. Bir oyuncunun kendi kazançları rakibin karışımını belirler.
• Açık artırma sonuçlarının çoğu teklifçilerin risk nötr olduğunu varsayar (Bölüm 5). Risk tutumları ise Bölüm 1'in konusudur.

• En iyi tepki: diğerlerinin eylemleri sabitken oyuncunun kazancını maksimize eden eylem ya da eylemler.
• Kesin baskınlık: sᵢ her durumda sᵢ′'den kesin olarak iyidir. Kesin baskılanan bir strateji hiçbir Nash dengesinde oynanmaz, pozitif olasılıkla bile.
• Zayıf baskınlık: hiçbir zaman daha kötü değil, bazen kesin olarak daha iyi. Zayıf baskılanan stratejiler yine de dengelerde görülebilir. Bunları elemenin sonucu eleme sırasına bağlı olabilir.
• Her oyuncu diğerlerine en iyi tepkiyi veriyorsa profil bir Nash dengesidir. Bireysel kararlılık sosyal optimumu garanti etmez (Mahkûmun İkilemi).

• Değerleme vᵢ: bir sonucun i ajanı için değeri. Yarı doğrusal fayda: uᵢ = vᵢ(x) − pᵢ, yani değer eksi ödeme.
• Sosyal refah: Σᵢ vᵢ(x). Ödemeler ajanlarla satıcı arasındaki transferlerdir. Bu yüzden refahta birbirini götürür.
• Gelir: Σᵢ pᵢ, satıcının topladığı tutar. Refah = ajanların toplam faydası + gelir.
• Bir piyasada artık (ticaretten kazanç), gerçekleşen alışverişlerde alıcı değeri ile satıcı maliyetinin farkıdır.
• Dışsallık, bir ajanın eyleminin diğerlerinin kazancına etkisidir. Ajan bu etkinin bedelini ödemez (tıkanıklık, ağ etkileri).

• T tur sonunda dışsal pişmanlık: R_T = maxₐ Σₜ gₜ(a) − Σₜ gₜ(aₜ). R_T / T → 0 ise algoritma pişmanlıksızdır.
• n eylem ve [0, 1] aralığındaki kazançlarla çarpımsal ağırlıklar (Hedge): R_T ≤ ln n/η + ηT. η = √(ln n / T) seçilirse R_T ≤ 2√(T ln n) olur.
• Lideri izle algoritması sürekli yer değiştirmeye zorlanabilir ve doğrusal pişmanlığa uğrar. Rastgeleleştirme bu sorunu giderir.
• Bütün oyuncular pişmanlıksız öğrenme kullanırsa oyunun zaman ortalaması kaba korelasyonlu dengeye yakınsar. Pürüzsüz oyunlardaki PoA sınırları da geçerli kalır.
• Haydut problemlerinde yalnız seçilen eylemin ödülü görülür. UCB, √(2 ln t / Nₐ) büyüklüğünde bir keşif payı ekler.
• Bölüm 1'deki minimaks pişmanlık (Savage) aynı sözcüğü taşır ama tek bir karar için kullanılan farklı bir ölçüttür.

• Dilin çekirdeği: değişkenler, döngüler, fonksiyonlar, özyineleme, listeler, demetler, sözlükler ve liste üreteçleri.
• İç içe listelerle kazanç matrisleri (A[i][j]), itertools.product ile strateji profilleri, itertools.permutations ile oyuncu sıraları.
• Rastgelelik: random.random(), random.choice ve tekrarlanabilir simülasyonlar için tohumlu üreteçler (random.Random(3)).
• Matematik fonksiyonları: math.exp, math.log, math.sqrt (çarpımsal ağırlıklar, UCB).
• Deneyler: bir simülasyon çok kez tekrarlanır, sonuçların ortalaması alınır ve kuramsal öngörüyle karşılaştırılır.