Dinamik oyunlar ve geriye doğru çözüm

Öğrenme çıktıları

• Hatırlama — Kapsamlı biçimli oyunu, bilgi kümesini, tam bilgili oyunu, eksiksiz eylem planını, kırkayak oyununu ve Zermelo teoremini tanımlar.
• Uygulama — Bir oyun ağacını geriye doğru çözer, oyuncuların strateji sayılarını hesaplar ve sıralı bir pazarlık oyununun dengesini bulur.
• Analiz — Kırkayak oyununda ve sıralı pazarlıkta gözlenen davranışın geriye doğru çözümden neden saptığını, hesaplama sınırları ve karşı tarafa dair inançlar üzerinden çözümler.
• Değerlendirme — Satranççılarla yapılan iki deneyin çelişen bulgularını karşılaştırarak geriye doğru çözümün gerçek davranışı ne zaman öngördüğünü değerlendirir.

Sezgi

Açılış

İki kişi sırayla bir sayıya ekleme yapıyor. Sıfırdan başlıyorlar; her hamlede 1 ile 10 arasında bir sayı ekleniyor. Toplamı tam 100'e ulaştıran kazanıyor. İlk hamleyi yapan oyuncu, rakibi ne yaparsa yapsın kazanmayı garanti edebilir mi?

Evet, edebilir; ama bunu görmek için oyunun sonundan başa doğru düşünmek gerekir. 89'a ulaşan oyuncu kazanır, çünkü rakip ne eklerse eklesin toplam 90 ile 99 arasında kalır ve 100'e tamamlamak mümkündür. 89'a ulaşmak için 78'e ulaşmak, 78 için 67'ye ulaşmak yeter. Bu zincir 1'e kadar iner. İlk oyuncu 1 ile başlar ve her seferinde rakibinin eklediğini 11'e tamamlarsa kazanır.

Oyun teorisine giriş dersinde sıralı oyunları ve geriye doğru çıkarımı bir piyasa giriş örneğiyle tanıdık. Bu ders aynı yöntemi daha sistemli biçimde kuruyor: oyunların ağaç biçiminde nasıl yazıldığını, geriye doğru çözümün neden her zaman bir sonuç verdiğini ve en önemlisi, insanların bu çözümü gerçekte ne kadar uyguladığını.

Hikâye — satranççılar ve kırkayak

Geriye doğru çözümün en ünlü sınavlarından biri kırkayak oyunudur. İki oyuncu sırayla ya oyunu durdurur ya da devam eder. Her devam kararında ortadaki ödül büyür; ama durduran, ödülün büyük kısmını alır. Geriye doğru düşünüldüğünde, son hamleyi yapacak oyuncu durdurmayı seçer; bunu bilen bir önceki oyuncu bir adım önce durdurur; zincir ilk hamleye kadar iner. Teori, ilk oyuncunun oyunu hemen durdurmasını öngörür. Laboratuvar deneylerinde ise öğrenciler bunu nadiren yaptı; çoğu birkaç tur devam edip ödülü büyüttü.

Ignacio Palacios-Huerta ve Oscar Volij, belki de deneklerin yeterince derin düşünmediğini düşündü ve oyunu, derin geriye doğru düşünmeyi meslek edinmiş insanlara oynattı: satranççılara.

Bu bulgu, teorinin «yeterince akıllı» oyuncular için işlediğini düşündürüyordu. Ama iki yıl sonra yayımlanan bir başka çalışma, aynı soruya farklı bir cevap verdi.

Kavram — oyunu ağaç olarak yazmak

Bir önceki derslerde oyunları tablolarla yazdık. Ama oyuncuların sırayla hareket ettiği ve öncekilerin ne yaptığını gördüğü oyunlarda tablo, önemli bir bilgiyi gizler: kimin, ne zaman, neyi bilerek karar verdiğini.

Bazen bir oyuncu, rakibinin önceki hamlesini görmeden karar verir. Böyle durumlar, ağaçta oyuncunun birbirinden ayırt edemediği düğümlerin bir araya getirilmesiyle gösterilir.

Sıralı bir oyunda strateji, tek bir eylemden fazlasıdır. Oyuncu, karşılaşabileceği her durumda ne yapacağını önceden belirlemelidir; o duruma oyun hiç ulaşmayacak olsa bile.

Veri ve kanıt — hesaplamak mı, adil olmak mı?

Sıralı pazarlık oyunları, geriye doğru çözümün bir başka sınavıdır. Eric Johnson, Colin Camerer, Sankar Sen ve Talia Rymon, katılımcıların karar verirken bilgisayar ekranında neye baktığını izleyerek, sapmanın nedenini anlamaya çalıştı.

Bu deney, sapmanın iki kaynağını ayırmayı başardı. İnsan rakiplere 2,11 dolar teklif edilmesi, hem adalet kaygısını hem de hesaplama eksikliğini yansıtabilir. Robotlara karşı adalet kaygısı ortadan kalkar; ama teklif yine de 1,84 dolar oldu. Eğitimden sonra teklif dengeye, 1,22 dolara indi. Fark, büyük ölçüde insanların oyunun sonundan başa doğru bakmamasından kaynaklanıyordu.

Neden önemli? — geleceği bugüne taşımak

Geriye doğru çözüm, ekonomideki birçok kararın temelidir. Bir şirket bir yatırımı yapıp yapmayacağına karar verirken rakibinin sonraki tepkisini, bir sendika bir grev kararı alırken işverenin sonraki adımını, bir hükümet bir vergi düzenlemesi yaparken mükelleflerin ve şirketlerin uyum biçimini hesaba katmak zorundadır. Her birinde bugünün en iyi kararı, yarının tepkilerinin doğru öngörülmesine bağlıdır.

Bu dersin kanıtları iki önemli ders içeriyor. Birincisi, geriye doğru çözüm güçlü bir araçtır, ama insanlar onu kendiliğinden uygulamaz; eğitim, deneyim ve oyunun basitliği uygulamayı kolaylaştırır. İkincisi, geriye doğru çözümün öngördüğü sonuç, karşı tarafın da aynı biçimde düşündüğü varsayımına dayanır. Bu varsayım şüpheliyse, örneğin rakibin işbirliğine yatkın olduğuna inanmak için bir neden varsa, teoriden sapmak hata değil, akıllıca bir seçim olabilir.

Model

Bu bölümde oyun ağaçlarını çözüyor, strateji sayılarını hesaplıyor ve sıralı pazarlık ile kırkayak oyunlarını sayılarla inceliyoruz. Deney sonuçları dışındaki bütün getiriler ve tutarlar kurgusaldır.

Çözümlü örnek — 100'e yarışın kazanma noktaları

Her hamlede 1 ile 10 arasında bir sayı eklenen ve 100'e ulaştıranın kazandığı oyunu sondan çözelim. Toplam 100'e ulaştıran kazanır. 90 ile 99 arasındaki bir toplama sıra gelen oyuncu 100'e tamamlayıp kazanır; bu toplamlar kazanan konumlardır. 89'a sıra gelen oyuncu ise ne eklerse eklesin rakibine 90 ile 99 arasında bir toplam bırakır; 89 kaybeden bir konumdur. Bu yüzden 89'a ulaştıran oyuncu kazanır.

Aynı mantıkla 78'e ulaştıran oyuncu, rakibini 79 ile 88 arasına iter; rakip ne yaparsa yapsın, oyuncu toplamı 89'a tamamlayabilir. Kaybeden konumlar 100'den 11'in katları kadar aşağıdadır: 89, 78, 67, 56, 45, 34, 23, 12 ve 1. İlk oyuncu 1 ekleyerek başlar ve her turda rakibinin eklediği sayıyı 11'e tamamlar. Rakip 4 eklerse oyuncu 7, rakip 9 eklerse oyuncu 2 ekler. Bu strateji kazanmayı kesin olarak garanti eder.

Çözümlü örnek — Ağaçtan tabloya

İki aşamalı bir oyun düşünelim. Önce bir yayıncı bir kitabı ciltli ya da cep boyu basmaya karar veriyor. Ardından bir kitapçı zinciri, yayıncının seçimini görerek kitabı vitrine koymaya ya da rafta tutmaya karar veriyor.

Yayıncının tek bir karar düğümü ve iki eylemi vardır; iki stratejisi vardır. Kitapçının iki karar düğümü vardır: ciltli basıldıysa ve cep boyu basıldıysa. Her düğümde iki eylemi vardır. Eksiksiz eylem planı, iki düğümün her biri için bir eylem belirtmelidir: «ciltliyse vitrin, cep boyuysa raf» gibi. Kitapçının 2 × 2 = 4 stratejisi vardır.

Bu oyunu stratejik biçimde yazmak için 2 × 4'lük bir tablo gerekir. Tablo, kitapçının ciltli kitabı gördüğünde ne yapacağı ile cep boyu kitabı gördüğünde ne yapacağını aynı satırda birleştirir. Ağaç ise bu iki kararı ayrı tutar ve kitapçının yayıncının seçimini bildiğini açıkça gösterir. Tablo, oyunun zaman yapısını kaybeder; bu yüzden bir sonraki derste göreceğimiz gibi, tablodan bulunan bazı Nash dengeleri ağaçta inandırıcı olmayan kararlara dayanabilir.

Çözümlü örnek — Dört hamleli kırkayak

İki oyuncu, A ve B, sırayla durdurmaya ya da devam etmeye karar veriyor. Başlangıçta ortada 4 lira var. Bir oyuncu durdurursa ortadakinin yüzde 80'ini kendisi alır, yüzde 20'si rakibine kalır. Devam ederse ortadaki para iki katına çıkar ve sıra rakibe geçer. Dört hamleden sonra oyun kendiliğinden biter ve son pot, son hamlede devam eden oyuncunun rakibine yüzde 80, kendisine yüzde 20 olarak bölüşülür.

Pot sırasıyla 4, 8, 16 ve 32 liradır; dördüncü hamlede de devam edilirse 64 liraya çıkar. Son hamleyi B yapar. Durdurursa 32'nin yüzde 80'i olan 25,6 lirayı alır; devam ederse 64'ün yüzde 20'si olan 12,8 lirayı alır. B durdurur. Üçüncü hamlede A, B'nin durduracağını bilir. Durdurursa 16'nın yüzde 80'i olan 12,8 lirayı alır; devam ederse B durdurur ve A 32'nin yüzde 20'si olan 6,4 lirayı alır. A durdurur. Aynı mantıkla ikinci hamlede B durdurur ve ilk hamlede A durdurur. Geriye doğru çözüm, A'nın oyunu hemen durdurup 3,2 lira almasını, B'nin 0,8 lira almasını öngörür.

Oysa iki oyuncu da sonuna kadar devam etseydi, A 64'ün yüzde 80'i olan 51,2 lirayı, B 12,8 lirayı alırdı. İkisi için de bu, dengedeki sonuçtan çok daha iyidir. Kırkayak oyununun gerilimi buradadır: geriye doğru çözüm, ikisinin de çok daha iyi olabileceği bir sonucu ilk hamlede ortadan kaldırır.

Çözümlü örnek — İşbirlikçi bir rakip olasılığı

A'nın, B'nin her hamlede devam eden «işbirlikçi» bir oyuncu olma olasılığını r olarak düşündüğünü varsayalım; B işbirlikçi değilse, geriye doğru çözümü uygular. A ilk hamlede bu inançla devam etmeli mi?

Basit bir karşılaştırma yapalım. A hemen durdurursa 3,2 lira alır. A ilk hamlede devam eder ve üçüncü hamlede durdurmayı planlarsa: B işbirlikçiyse üçüncü hamleye gelinir ve A 12,8 lira alır; B işbirlikçi değilse ikinci hamlede durdurur ve A 8'in yüzde 20'si olan 1,6 lirayı alır. Beklenen getiri r × 12,8 + (1 − r) × 1,6'dır. Bu, r × 11,2 > 1,6, yani r > yaklaşık 0,143 olduğunda 3,2'yi aşar.

Rakibinin yedide bir olasılıkla işbirlikçi olduğuna inanan bir oyuncu için devam etmek, hemen durdurmaktan daha iyidir. Levitt ve arkadaşlarının yorumu bu hesapla uyumludur: kırkayakta devam etmek, geriye doğru düşünememekten değil, rakibin de devam edebileceğine dair makul bir inançtan kaynaklanabilir. Palacios-Huerta ve Volij'in bulgusu da bu çerçevede okunabilir: büyükustalar, rakiplerinin de geriye doğru düşüneceğinden emin oldukları için hemen durdurmuş olabilir.

Çözümlü örnek — Üç turlu pazarlık

İki oyuncu bir parayı bölüşmek için pazarlık ediyor. Birinci turda 5 lira var; A bir bölüşüm önerir, B kabul ederse anlaşma olur. B reddederse para 2,50 liraya iner ve B bir bölüşüm önerir. A reddederse para 1,25 liraya iner ve A son bir öneri yapar; B bu son öneriyi ya kabul eder ya da ikisi de hiçbir şey almaz.

Son turdan başlayalım. Üçüncü turda B, reddettiğinde hiçbir şey almayacağı için sıfıra yakın her öneriyi kabul eder; A 1,25 liranın tamamını alır. İkinci turda B, A'nın reddederse üçüncü turda 1,25 lira alacağını bilir; A'ya 1,25 lira önerir ve kalan 1,25 lirayı kendisi alır. Birinci turda A, B'nin reddederse ikinci turda 1,25 lira alacağını bilir; B'ye 1,25 lira önerir ve 3,75 lirayı kendisi alır. Dengede birinci turda anlaşılır; A 3,75, B 1,25 lira alır.

Bu örnekte denge teklifi, Johnson ve arkadaşlarının deneyindeki gibi 1,25 liradır. Bir katılımcının yalnızca birinci turdaki 5 liraya bakması, eşit bölüşüme, yani 2,50 liraya yakın bir öneri yapmasına yol açabilir. Dengeyi bulmak, üçüncü turdaki 1,25 liraya bakmayı gerektirir; deneydeki bilgi arama kayıtları, birçok katılımcının bunu yapmadığını gösteriyordu.

Çözümlü örnek — Tur sayısı ve ilk teklif

Aynı pazarlığın yalnızca iki turlu olduğunu düşünelim: birinci turda 5 lira, ikinci ve son turda 2,50 lira var ve son öneriyi B yapıyor. İkinci turda B, 2,50 liranın tamamını alır. Birinci turda A, B'ye 2,50 lira önermek zorundadır ve kendisi 2,50 lira alır.

Üç turlu oyunda A 3,75 lira alıyordu; iki turlu oyunda 2,50 lira alır. Son öneriyi kimin yaptığı ve paranın her turda ne kadar küçüldüğü, bölüşümü belirler. Pazarlık gücü, yalnızca sabırdan ya da inatçılıktan değil, oyunun kurallarından, yani kimin ne zaman öneri yapabildiğinden gelir.

Çözümlü örnek — Görmek ile görmemek arasındaki fark

Yayıncı ve kitapçı örneğine sayılar ekleyelim. Getiriler, önce yayıncının sonra kitapçının olmak üzere şöyledir: ciltli basılır ve vitrine konursa 5 ve 4; ciltli basılır ve rafta kalırsa 2 ve 1; cep boyu basılır ve vitrine konursa 6 ve 1; cep boyu basılır ve rafta kalırsa 3 ve 3.

Kitapçı yayıncının seçimini görüyorsa, oyunu geriye doğru çözeriz. Ciltli kitap için vitrin 4, raf 1 verir; kitapçı vitrini seçer. Cep boyu kitap için vitrin 1, raf 3 verir; kitapçı rafı seçer. Yayıncı bunu bilir: ciltli basarsa 5, cep boyu basarsa 3 alacaktır. Ciltli basar. Sonuç 5 ve 4'tür.

Şimdi kitapçının, kararını yayıncının seçimini görmeden vermek zorunda olduğunu varsayalım; iki karar düğümü aynı bilgi kümesine girer. Oyun eşanlı hâle gelir. Yayıncı için cep boyu, kitapçı vitrini seçerse 6 > 5, rafı seçerse 3 > 2 verir; cep boyu kesin baskındır. Kitapçı bunu bilir ve rafı seçer. Sonuç 3 ve 3'tür.

Kitapçının yayıncıyı görmesi, ikisini de daha iyi duruma getirdi. Görülebilir bir ilk hamle, ilk oyuncunun kendini bağlamasını sağlar: yayıncı ciltli basarak kitapçıyı vitrine yönlendirir. Bilgi kümelerinin nasıl çizildiği, yani kimin neyi bildiği, oyunun sonucunu kökten değiştirebilir.

Çözümlü örnek — Sabrın pazarlıktaki değeri

İki turlu bir pazarlıkta 100 lira bölüşülüyor. A birinci turda bir öneri yapar; B reddederse ikinci turda B son öneriyi yapar ve 100 liranın tamamını alabilir. Ama ikinci tur bir dönem sonra gelir ve oyuncular gelecekteki parayı farklı biçimde iskonto eder: A için bir dönem sonraki 1 lira bugün 0,9, B için 0,6 lira değerindedir.

B ikinci turda 100 lirayı alacaktır; bu, B için bugün 60 lira değerindedir. A, B'nin reddetmemesi için ona en az 60 lira önermelidir. A 40, B 60 lira alır. B'nin iskonto katsayısı 0,9 olsaydı, ikinci turdaki 100 lira B için bugün 90 lira ederdi; A 10, B 90 lira alırdı. Sabırlı oyuncu, beklemenin kendisine daha az maliyetli olması sayesinde daha büyük pay elde eder. Model bölümündeki tur sayısı örneğiyle birlikte bu hesap, pazarlık gücünün kaynaklarını gösterir: son öneriyi kimin yaptığı ve kimin beklemeye daha dayanıklı olduğu.

Çözümlü örnek — Oyun uzadıkça

Aynı kuralları koruyarak kırkayağı altı hamleye uzatalım. Pot sırasıyla 4, 8, 16, 32, 64 ve 128 liradır; altıncı hamlede de devam edilirse 256 liraya çıkar. Geriye doğru çözüm değişmez: son hamlede B durdurur, beşinci hamlede A durdurur ve zincir yine ilk hamleye kadar iner. A 3,2, B 0,8 lira alır.

Ama işbirliğinin kazancı büyür. İki oyuncu da sonuna kadar devam etseydi A 256'nın yüzde 80'i olan 204,8 lirayı, B 51,2 lirayı alırdı. İşbirlikçi bir rakip olasılığına dair hesap da değişir. A, ilk hamlede devam edip beşinci hamlede durdurmayı planlarsa, B işbirlikçiyse 64'ün yüzde 80'i olan 51,2 lirayı, değilse 1,6 lirayı alır. Beklenen getiri r × 51,2 + (1 − r) × 1,6'dır ve bu, r yaklaşık 0,032'yi aştığında 3,2'den büyük olur.

Dört hamleli oyunda devam etmek için rakibin yedide bir olasılıkla işbirlikçi olduğuna inanmak gerekiyordu; altı hamleli oyunda otuzda bire yakın bir olasılık yetiyor. Oyun uzadıkça, rakibin rasyonelliğine dair çok küçük bir şüphe bile devam etmeyi akıllıca kılar. Laboratuvar deneylerinde kırkayak oyunlarında gözlenen devam kararları bu açıdan şaşırtıcı değildir.

Modelin sınırları

Geriye doğru çözüm, her oyuncunun oyunun bütün ağacını bildiğini, sonraki her düğümde herkesin rasyonel davranacağını ve bunun ortak bilgi olduğunu varsayar. Ağaç büyüdükçe bu varsayım gerçekçiliğini yitirir: satrançta geriye doğru çözüm kuramsal olarak mümkündür, ama hiçbir insan ya da bilgisayar bütün ağacı hesaplayamaz. Ayrıca kırkayak örneğinin gösterdiği gibi, rakibin rasyonelliğine dair küçük bir şüphe bile, en iyi kararı geriye doğru çözümün öngördüğünden uzaklaştırabilir. Bu yüzden geriye doğru çözüm, kısa ve basit oyunlarda güçlü bir öngörü, uzun ve karmaşık oyunlarda ise bir referans noktasıdır.

Teknik

Kapsamlı biçimin tanımı

Sonlu bir kapsamlı biçimli oyun şu unsurlardan oluşur: bir T ağacı, yani bir kök düğümden başlayan ve döngü içermeyen sonlu bir düğüm kümesi; uç olmayan her düğüme o düğümde karar verecek oyuncuyu atayan bir ι fonksiyonu; her oyuncunun karar düğümlerini bilgi kümelerine bölen bir bölüntü; her bilgi kümesindeki eylemler kümesi ve her uç düğümde her oyuncunun getirisi. Aynı bilgi kümesindeki düğümlerde aynı eylemler bulunmalıdır; aksi hâlde oyuncu, hangi düğümde olduğunu mevcut eylemlerden çıkarabilirdi.

Bir oyuncunun saf stratejisi, her bilgi kümesine o kümede mevcut eylemlerden birini atayan bir fonksiyondur. Oyuncunun k tane bilgi kümesi varsa ve j'inci kümede m_j eylem bulunuyorsa, saf strateji sayısı m_1 × m_2 × … × m_k'dır. Bu sayı, oyunun uzunluğuyla birlikte üstel olarak büyür. Dört hamleli kırkayakta her oyuncunun iki karar düğümü ve her düğümde iki eylemi vardır; her oyuncunun 4 stratejisi vardır. On hamleli bir kırkayakta her oyuncunun beş düğümü ve 2^5 = 32 stratejisi olur.

Geriye doğru çözüm ve Zermelo teoremi

Tam bilgili sonlu bir oyunda geriye doğru çözüm şöyle tanımlanır. Ağacın en derin karar düğümlerinden başlanır: bu düğümlerin her birinde, karar veren oyuncu getirisini en yükseğe çıkaran eylemi seçer ve düğüm, bu eylemin götürdüğü uç düğümün getirileriyle değiştirilir. Bu işlem, kök düğüme ulaşılana kadar sürdürülür.

Zermelo teoremi olarak bilinen sonuç, Ernst Zermelo'nun 1913'te satranç üzerine yaptığı çalışmaya dayanır ve sonradan Harold Kuhn tarafından genel biçimde ifade edilmiştir: tam bilgili her sonlu oyunun saf stratejilerde, geriye doğru çözümle bulunan bir Nash dengesi vardır. İspat, ağacın derinliği üzerine tümevarımdır. Derinliği bir olan bir ağaçta tek bir karar vardır ve karar veren oyuncunun en iyi eylemi sonlu bir kümede her zaman bulunur. Derinliği n olan bir ağaçta, kök düğümün her dalı derinliği n − 1'den küçük bir alt ağaç başlatır; tümevarım varsayımına göre her alt ağacın geriye doğru çözümü vardır. Kökteki oyuncu, bu çözümlerin getirileri arasından en iyisini seçer.

Hiçbir oyuncu hiçbir düğümde iki eylem arasında kayıtsız değilse, geriye doğru çözüm tektir. Kayıtsızlık varsa birden fazla çözüm olabilir; her biri bir dengedir. Satranç gibi iki kişilik sıfır toplamlı ve beraberliğe izin veren bir oyuna bu sonuç uygulandığında, oyunun belirli bir sonucu olduğu çıkar: ya beyaz kazanmayı garanti edebilir, ya siyah garanti edebilir, ya da iki taraf da en az beraberliği garanti edebilir. Hangisinin doğru olduğu bilinmemektedir; ağacın büyüklüğü hesaplamayı olanaksız kılar.

Sıralı pazarlığın genel çözümü

Model bölümündeki pazarlığı genelleştirelim. Bölüşülecek miktar başlangıçta 1 olsun ve her ret sonrasında δ katsayısıyla küçülsün; 0 < δ < 1. Oyuncular sırayla öneri yapsın ve oyun T turdan sonra bitsin. Son turda öneri yapan oyuncu, o turdaki miktarın tamamını alır. Bir önceki turda öneri yapan oyuncu, karşı tarafa onun bir sonraki turda alacağı miktarı önerir ve kalanı kendisi alır.

T turlu oyunda birinci turda öneri yapan oyuncunun payı x_T olsun. Tek turlu oyunda x_1 = 1'dir. T turlu oyunda birinci oyuncu, karşı tarafa onun T − 1 turlu oyunda birinci önerici olarak alacağı payın δ katını önermek zorundadır: x_T = 1 − δ × x_(T−1). δ = 0,5 için x_1 = 1, x_2 = 0,5, x_3 = 0,75, x_4 = 0,625 ve dizi 2/3'e yakınsar. Genel olarak tur sayısı sonsuza giderken birinci önericinin payı 1 ÷ (1 + δ)'ya yakınsar. Bu sınır, Ariel Rubinstein'ın sonsuz turlu pazarlık modelinin tek alt oyun yetkin dengesindeki paydır; bir sonraki derste bu kavramı ayrıntılı ele alacağız.

Mükemmel hatırlama ve davranışsal stratejiler

Kapsamlı biçimli oyunlarda karma stratejinin iki farklı tanımı vardır. Birincisi, oyuncunun bütün saf stratejileri, yani bütün eksiksiz eylem planları üzerinde bir olasılık dağılımıdır. İkincisi, davranışsal stratejidir: oyuncu her bilgi kümesinde, o kümedeki eylemler üzerinde ayrı ve bağımsız bir olasılık dağılımı seçer. Davranışsal stratejiler çok daha az sayıda parametreyle tanımlanır; dört bilgi kümesinde ikişer eylemi olan bir oyuncu için karma strateji on altı saf strateji üzerinde bir dağılım, davranışsal strateji ise dört olasılıktır.

Harold Kuhn'un 1953'te gösterdiği sonuca göre, oyuncu kendi geçmiş eylemlerini ve önceden bildiklerini hiç unutmuyorsa, yani mükemmel hatırlamaya sahipse, her karma stratejiyle aynı sonuç dağılımını üreten bir davranışsal strateji vardır ve tersi de geçerlidir. Bu yüzden mükemmel hatırlamalı oyunlarda iki tanım arasında seçim yapmak gerekmez; daha kullanışlı olan davranışsal stratejiler tercih edilir. Satranç, kırkayak ve sıralı pazarlık mükemmel hatırlamalı oyunlardır. Mükemmel hatırlamanın bozulduğu oyunlarda ise, örneğin bir oyuncunun daha önce hangi yoldan geldiğini unuttuğu durumlarda, iki tanım farklı sonuçlar verebilir; bu tür oyunlar, oyun teorisinin dikkat gerektiren özel bir alanıdır.

Ortak bilgi ve geriye doğru çözüm

Robert Aumann 1995'te, tam bilgili sonlu oyunlarda rasyonelliğin ortak bilgisinin geriye doğru çözümün sonucunu doğurduğunu gösterdi. Bu, kırkayak oyununda ilk oyuncunun durdurmasının, oyuncuların rasyonel olduğu ve bunun ortak bilgi olduğu varsayımının mantıksal bir sonucu olduğu anlamına gelir.

Ama bu sonuç ince bir soruyu gündeme getirir. Geriye doğru çözüm, oyunun hiç ulaşılmaması gereken düğümlerinde de oyuncuların rasyonel davranacağını varsayar. Kırkayakta B, ikinci hamleye gelindiğini görürse, A'nın ilk hamlede devam ettiğini, yani geriye doğru çözüme uymadığını öğrenmiş olur. Bu durumda B'nin A'nın üçüncü hamlede rasyonel davranacağına inanmaya devam etmesi için bir neden kalır mı? Bu soru, oyun teorisinde «denge dışı inançlar» tartışmasının çekirdeğidir. Model bölümündeki işbirlikçi rakip hesabı, bu inançlar değiştiğinde en iyi kararın da değiştiğini gösteriyordu.

Hesaplama yükü

Geriye doğru çözüm algoritması ağacın her düğümünü bir kez ziyaret eder; işlem sayısı düğüm sayısıyla orantılıdır. Sorun, düğüm sayısının oyunun uzunluğuyla birlikte üstel büyümesidir. Her hamlede b eylemin bulunduğu ve d hamle süren bir oyunda yaklaşık b^d uç düğüm vardır. 100'e yarışta oyunun yapısı bu büyümeyi önler: oyuncunun durumunu yalnızca toplam belirler, geçmişin ayrıntısı önemsizdir ve 100 konumluk bir tablo yeterlidir. Satrançta ise konumların sayısı o kadar büyüktür ki, oyunun geriye doğru çözümü bugün bilinmemektedir. Levitt ve arkadaşlarının bulgusu bu açıdan da okunabilir: satranççılar, durumu birkaç sayıyla özetlenebilen 100'e yarışta geriye doğru düşünebildi.

Geriye doğru çözüm ile Nash dengesi arasındaki ilişki

Geriye doğru çözümle bulunan her profil bir Nash dengesidir: her düğümde en iyi eylem seçildiği için, hiçbir oyuncu kendi planının herhangi bir parçasını değiştirerek kazanamaz. Ters yön ise genellikle geçerli olmaz. Kapsamlı biçimli bir oyunun stratejik biçiminde, bazı Nash dengeleri, oyunun hiç ulaşılmayan düğümlerinde oyuncunun kendi aleyhine olan eylemler içerir. Bu eylemler dengede hiçbir zaman uygulanmadığı için, oyuncunun getirisini etkilemez; ama rakibin kararını etkiler. Böyle dengeler, inandırıcı olmayan tehditlere dayanır. Geriye doğru çözüm, her düğümde, ulaşılmasa bile, en iyi eylemi zorunlu kılarak bu dengeleri eler. Bu fikrin bilgi kümeleri tek düğümlü olmayan oyunlara genişletilmesi, bir sonraki dersin konusudur.

Uygulama

Özet kartı

1. Kapsamlı biçimli oyun, kimin ne zaman ve neyi bilerek hareket ettiğini bir ağaçla gösterir; bir oyuncunun stratejisi, her bilgi kümesinde ne yapacağını belirten eksiksiz bir eylem planıdır.
2. Zermelo teoremine göre tam bilgili her sonlu oyunun, geriye doğru çözümle bulunan saf stratejili bir Nash dengesi vardır.
3. Palacios-Huerta ve Volij, üst sıralardaki satranççıların yüzde 69'unun, büyükustaların ise yüzde 100'ünün kırkayak oyununu hemen durdurduğunu buldu.
4. Levitt, List ve Sadoff, satranççıların kırkayakta dengeyi neredeyse hiç oynamadığını, ama birçoğunun 100'e yarış oyununda doğru biçimde geriye doğru düşündüğünü buldu.
5. Johnson ve arkadaşlarının pazarlık deneyinde teklifler insanlara 2,11, robotlara 1,84, eğitim sonrası robotlara 1,22 dolardı; sapmanın büyük kısmı sınırlı hesaplamadan geliyordu.

Kavram sözlüğü

Kendini sına

1. (Çıktı 1) Tam bilgili oyun ile bilgi kümeleri tek düğümlü olmayan oyun arasındaki fark nedir? Birer örnek verin.
2. (Çıktı 2) 1 ile 6 arasında ekleme yapılan ve 60'a ulaştıranın kazandığı bir yarış oyununda kaybeden konumlar hangileridir? İlk oyuncu kazanmayı garanti edebilir mi?
3. (Çıktı 2) Bir oyunda A önce iki eylemden birini seçiyor; B, A'nın seçimini görerek üç eylemden birini seçiyor; ardından A, B'nin seçimini görerek iki eylemden birini seçiyor. A'nın ve B'nin kaç saf stratejisi vardır?
4. (Çıktı 3) Bu dersteki dört hamleli kırkayakta A, B'nin işbirlikçi olma olasılığını 0,1 olarak düşünüyorsa ilk hamlede devam etmeli mi? Olasılık 0,2 olsaydı ne değişirdi?
5. (Çıktı 3) Johnson ve arkadaşlarının deneyinde insanlara ve robotlara yapılan tekliflerin farkı neyi gösterir? Eğitimden sonra robotlara yapılan teklifin dengeye yaklaşması ne anlatır?
6. (Çıktı 4) Palacios-Huerta ve Volij ile Levitt, List ve Sadoff'un çalışmaları satranççılar hakkında farklı sonuçlara ulaştı. İki sonuç birlikte nasıl açıklanabilir? Geriye doğru çözümün gerçek davranışı ne zaman öngördüğüne dair ne söylerler?

Cevaplar

1. Tam bilgili oyunda her bilgi kümesi tek bir düğümden oluşur; her oyuncu karar anında oyunun o ana kadarki bütün geçmişini bilir. Satranç ve 100'e yarış bunun örnekleridir. Bilgi kümeleri tek düğümlü olmayan oyunlarda ise bir oyuncu, rakibinin önceki hamlesini görmeden karar verebilir; örneğin iki firmanın teklifleri kapalı zarfla verildiği bir ihalede ikinci firma, birinci firmanın teklifini bilmeden karar verir ve onun olası tekliflerine karşılık gelen düğümler aynı bilgi kümesindedir.
2. Her hamlede 1 ile 6 arasında ekleme yapıldığı için, kaybeden konumlar 60'tan 7'nin katları kadar aşağıdadır: 53, 46, 39, 32, 25, 18, 11 ve 4. Bu toplamlara ulaştıran oyuncu, rakibini bir sonraki kaybeden konumun 1 ile 6 aşağısına iter ve her turda rakibin eklediğini 7'ye tamamlayarak kazanır. İlk oyuncu 4 ekleyerek başlarsa kazanmayı garanti eder.
3. A'nın iki karar aşaması vardır. İlk aşamada tek bir düğümü ve iki eylemi vardır. Üçüncü aşamada, kendi ilk seçimi ve B'nin seçimine göre 2 × 3 = 6 farklı düğümü vardır ve her birinde iki eylemi vardır. A'nın saf strateji sayısı 2 × 2^6 = 128'dir. B'nin, A'nın iki olası seçimine karşılık gelen iki düğümü ve her birinde üç eylemi vardır; saf strateji sayısı 3 × 3 = 9'dur.
4. Hemen durdurmak 3,2 lira verir. İlk hamlede devam edip üçüncü hamlede durdurmanın beklenen getirisi r × 12,8 + (1 − r) × 1,6'dır. r = 0,1 için bu 1,28 + 1,44 = 2,72 liradır; 3,2'den az olduğu için A hemen durdurmalıdır. r = 0,2 için 2,56 + 1,28 = 3,84 liradır; 3,2'yi aştığı için A ilk hamlede devam etmelidir. Eşik yaklaşık 0,143'tür.
5. İnsanlara yapılan 2,11 dolarlık teklif hem adalet kaygısını hem de hesaplama sınırlarını yansıtabilir. Robotlara karşı adalet kaygısı ortadan kalktığı hâlde teklif 1,84 dolarda kaldı; bu fark, sapmanın bir kısmının adalet kaygısından geldiğini gösterir. Eğitimden sonra robotlara yapılan teklifin 1,22 dolara, yani dengeye inmesi, kalan sapmanın büyük ölçüde katılımcıların oyunu sondan başa doğru çözmemesinden kaynaklandığını gösterir; bilgi arama kayıtları da bunu destekliyordu.
6. Palacios-Huerta ve Volij, satranççıların büyük çoğunluğunun ve büyükustaların hepsinin kırkayakta hemen durdurduğunu buldu. Levitt, List ve Sadoff ise satranççıların kırkayakta dengeyi neredeyse hiç oynamadığını, ama 100'e yarış gibi saf geriye doğru çıkarım oyunlarında birçoğunun doğru düşündüğünü buldu. İki bulgu, kırkayakta devam etmenin geriye doğru düşünememekten değil, rakibin de devam edeceğine dair inançtan kaynaklanabileceği yorumuyla bağdaştırılabilir: rakibin geriye doğru düşüneceğinden emin olan oyuncu durdurur, rakibinin devam edebileceğini düşünen oyuncu devam eder. Geriye doğru çözüm, oyuncuların hem kendileri hem de rakipleri hakkında aynı biçimde düşündüğü kısa ve basit oyunlarda iyi öngörür; rakibin rasyonelliğine dair belirsizliğin önemli olduğu oyunlarda ise öngörü gücü azalır.

İleri okuma

• Ignacio Palacios-Huerta, Oscar Volij (2009). «Field Centipedes». American Economic Review 99(4). Satranççılarla kırkayak oyunu deneyleri.
• Steven D. Levitt, John A. List, Sally E. Sadoff (2011). «Checkmate: Exploring Backward Induction among Chess Players». American Economic Review 101(2). Kırkayak oyunu ile saf geriye doğru çıkarım oyunlarının karşılaştırılması.
• Eric J. Johnson, Colin Camerer, Sankar Sen, Talia Rymon (2002). «Detecting Failures of Backward Induction: Monitoring Information Search in Sequential Bargaining». Journal of Economic Theory 104(1). Sıralı pazarlıkta bilgi aramanın izlenmesi.
• Richard D. McKelvey, Thomas R. Palfrey (1992). «An Experimental Study of the Centipede Game». Econometrica 60(4). Kırkayak oyununun ilk büyük laboratuvar çalışması.

Sonraki derse köprü

Bu derste geriye doğru çözümü, her oyuncunun bütün geçmişi bildiği oyunlarda kullandık ve bu çözümün inandırıcı olmayan tehditlere dayanan bazı Nash dengelerini elediğini gördük. Ama oyunların çoğunda oyuncular her şeyi görmez; bir ihalede rakibin teklifini, bir pazarlıkta karşı tarafın bütün seçeneklerini bilmeden karar verirler. Bilgi kümeleri tek düğümlü olmadığında geriye doğru çözüm nasıl genelleştirilir ve bir dengenin oyunun her parçasında tutarlı olması ne demektir? Sıradaki ders alt oyun yetkin dengeyi ele alıyor.