Alt oyun mükemmel dengesi - Subgame perfect equilibrium

Alt Oyun Mükemmel Denge
Bir çözüm konsepti içinde oyun teorisi
ilişki
Alt kümesi Nash dengesi
ile kesişir Evrimsel olarak kararlı strateji
Önemi
tarafından önerilen Reinhard Selten
İçin kullanılır Kapsamlı form oyunları
Misal ültimatom oyunu

In oyun teorisi , bir alt-oyun mükemmel denge (veya alt-oyun mükemmel Nash dengesi ) bir olan arıtma a Nash dengesi kullanılan dinamik oyunlar . Bir strateji profili , orijinal oyunun her alt oyununun bir Nash dengesini temsil ediyorsa, bir alt oyun mükemmel dengesidir . Gayri resmi olarak bu, oyunun herhangi bir noktasında, oyuncuların o noktadan sonraki davranışlarının, daha önce ne olursa olsun, devam oyununun (yani alt oyunun) bir Nash dengesini temsil etmesi gerektiği anlamına gelir. Her sonlu kapsamlı oyun ile mükemmel hatırlama bir alt-oyun mükemmel dengesi vardır. Mükemmel hatırlama, 1953'te Harold W. Kuhn tarafından ortaya atılan bir terimdir ve "oyun kurallarının her oyuncunun önceki hamlelerde bildiği her şeyi ve bu hamlelerdeki tüm seçimlerini hatırlamasına izin verildiği iddiasına eşdeğerdir" .

Sonlu bir oyun durumunda alt-oyun mükemmel dengesini belirlemek için yaygın bir yöntem geriye dönük çıkarımdır . Burada ilk önce oyunun son hareketlerini göz önünde bulundurur ve son hareket ettiricinin faydasını en üst düzeye çıkarmak için olası her durumda hangi eylemleri yapması gerektiğini belirler . Daha sonra, son aktörün bu eylemleri yapacağını varsayar ve ikinciden sondan eylemlere, yine o aktörün faydasını maksimize edenleri seçerek değerlendirir. Bu işlem, oyunun ilk hamlesine ulaşana kadar devam eder. Geriye kalan stratejiler, sonlu-ufuk kapsamlı mükemmel bilgi oyunları için tüm alt-oyun mükemmel dengelerinin kümesidir. Ancak geriye dönük çıkarım kusurlu veya eksik bilgi oyunlarına uygulanamaz çünkü bu tekil olmayan bilgi kümelerini kesmeyi gerektirir .

Bir alt-oyun mükemmel dengesi zorunlu olarak tek seferlik sapma ilkesini karşılar .

Belirli bir oyun için alt-oyun mükemmel dengeleri kümesi her zaman o oyun için Nash dengeleri kümesinin bir alt kümesidir. Bazı durumlarda kümeler aynı olabilir.

Ultimatom oyunu Nash dengeleri daha az alt-oyun mükemmel dengeleri ile bir oyunun sezgisel örnek sağlar.

Misal

Alt-oyun mükemmel dengesinin geriye doğru tümevarım kullanılarak belirlenmesi aşağıda Şekil 1'de gösterilmiştir. Oyuncu 1 için stratejiler {Up, Uq, Dp, Dq} ile verilirken, Oyuncu 2 {TL, TR, BL, BR} arasında stratejilere sahiptir. Bu örnekte 3 uygun alt oyunla birlikte 4 alt oyun vardır.

Şekil 1

Geriye dönük çıkarımı kullanarak, oyuncular her bir alt oyun için aşağıdaki işlemleri yapacaklardır:

  • p ve q eylemleri için alt oyun: Oyuncu 1, Oyuncu 1'in getirisini en üst düzeye çıkarmak için ödeme (3, 3) ile p eylemini yapacak, böylece L eyleminin getirisi (3,3) olur.
  • L ve R eylemleri için alt oyun: Oyuncu 2, 3 > 2 için L eylemini yapacak, böylece D eyleminin getirisi (3, 3) olur.
  • T ve B eylemleri için alt oyun: Oyuncu 2, Oyuncu 2'nin getirisini en üst düzeye çıkarmak için T eylemini yapacak, böylece U eyleminin getirisi (1, 4) olur.
  • U ve D eylemleri için alt oyun: Oyuncu 1, Oyuncu 1'in getirisini en üst düzeye çıkarmak için D eylemini yapacaktır.

Böylece, alt-oyun mükemmel dengesi, getirisi (3, 3) ile {Dp, TL}'dir.

Eksik bilgi içeren geniş biçimli bir oyun aşağıda Şekil 2'de sunulmaktadır. A ve B eylemlerine sahip Oyuncu 1 düğümünün ve sonraki tüm eylemlerin bir alt oyun olduğunu unutmayın. Oyuncu 2'nin düğümleri, aynı bilgi setinin parçası oldukları için bir alt oyun değildir.

şekil 2

İlk normal biçimli oyun, tüm kapsamlı biçimli oyunun normal biçimli temsilidir. Sağlanan bilgilere dayanarak, (UA, X), (DA, Y) ve (DB, Y) tüm oyun için Nash dengeleridir.

İkinci normal biçimli oyun, Oyuncu 1'in A ve B eylemleriyle ikinci düğümünden başlayan alt oyunun normal biçimli temsilidir. İkinci normal biçimli oyun için, alt oyunun Nash dengesi (A, X)'dir.

Tüm oyun için Nash dengesi (DA, Y) ve (DB, Y) alt-oyun mükemmel dengesi değildir çünkü Oyuncu 2'nin hareketi bir Nash Dengesi oluşturmaz. Nash dengesi (UA, X) alt oyun mükemmeldir çünkü stratejisinin bir parçası olarak Nash dengesini (A, X) alt oyunu içerir.

Bu oyunu çözmek için önce Alt Oyun 1'in karşılıklı en iyi tepkisine göre Nash Dengesini bulun. Sonra geriye dönük çıkarımı kullanın ve (A,X) → (3,4)'ü takın, böylece (3,4) Alt Oyun 2'nin getirisi olsun.

Kesikli çizgi, 2. oyuncunun, 1. oyuncunun aynı anda bir oyunda A mı yoksa B mi oynayacağını bilmediğini gösterir.

Alt Oyun 1 çözüldü ve (3,4) Alt Oyun 1'in tamamının yerini alıyor ve birinci oyuncu Alt Oyun 1 için U -> (3,4)Çözüm seçecek

Oyuncu 1, D yerine U'yu seçer çünkü Oyuncu 1'in getirisi için 3 > 2'dir. Ortaya çıkan denge (A, X) → (3,4).

Alt Oyun Mükemmel Dengesinin Çözümü

Böylece, geriye dönük çıkarım yoluyla alt-oyun mükemmel dengesi (UA, X) ve getirisi (3, 4) olur.

Tekrarlanan oyunlar

Sonlu olarak tekrarlanan oyunlar için, eğer bir sahne oyununda yalnızca bir benzersiz Nash dengesi varsa, alt oyun mükemmel dengesi, geçmiş eylemleri dikkate almadan oynamak ve mevcut alt oyunu tek seferlik bir oyun olarak ele almaktır. Bunun bir örneği, son derece tekrarlanan bir Mahkum ikilemi oyunudur. Mahkumun ikilemi, adını iki suçlunun bulunduğu bir durumdan alır. Sorgulandıklarında, sessiz kalma ya da kaçma seçeneklerine sahipler. Her iki suçlu da sessiz kalırsa, ikisi de kısa bir cezaya çarptırılır. Her ikisi de kusurluysa, ikisi de makul bir ceza verir. Zıt seçenekleri seçerlerse, kusurlu suçlu serbesttir ve sessiz kalan suçlu uzun bir cezaya çarptırılır. Son olarak, geriye dönük çıkarımı kullanarak, sonlu olarak tekrarlanan Mahkum ikilemindeki son alt oyun, oyuncuların benzersiz Nash dengesini oynamasını gerektirir (her iki oyuncu da kaçar). Bu nedenle, son alt oyundan önceki tüm oyunlar, tek periyotlu getirilerini maksimize etmek için Nash dengesini oynayacaktır. Sonlu olarak tekrarlanan bir oyunda bir sahne oyununun birden fazla Nash dengesi varsa, alt-oyun mükemmel dengesi, bir "havuç ve çubuk" yapısı aracılığıyla, sahne oyunu olmayan Nash dengesi eylemlerini oynamak için oluşturulabilir. Bir oyuncu, Nash dışı denge hareketini oynamayı teşvik etmek için tek aşamalı oyun Nash dengesini kullanabilirken, diğer oyuncu kusur etmeyi seçerse daha düşük getirisi olan bir sahne oyunu Nash dengesini kullanabilir.

Alt-oyun-mükemmel dengeleri bulma

Geriye dönük çıkarım çözümünün iyi bilindiği bir oyun tic-tac-toe'dur.

Reinhard Selten ana oyunda mevcut tüm seçenekler alt kümesi içeren "alt-oyun" ayrılabilir herhangi bir oyun bir şekilde muhtemelen (bir alt-oyun mükemmel Nash dengesi stratejisi olacağını kanıtladı karışık strateji olmayan deterministik alt- vererek oyun kararları). Alt oyun mükemmelliği yalnızca eksiksiz bilgi içeren oyunlarda kullanılır . Alt-oyun mükemmelliği, eksiksiz fakat kusurlu bilgiler içeren kapsamlı biçimli oyunlarla kullanılabilir .

Alt-oyun-mükemmel Nash dengesi, normal olarak oyunun çeşitli nihai sonuçlarından " geriye dönük çıkarım" ile çıkarılır ve herhangi bir oyuncunun o düğümden inandırıcı olmayan (çünkü optimal olmadığı için) bir hamle yapmasını içeren dalları ortadan kaldırır . Geriye dönük çıkarım çözümünün iyi bilindiği bir oyun tic-tac-toe'dur , ancak teoride Go'nun bile tüm oyuncular için böyle bir optimum stratejisi vardır. Alt-oyun mükemmelliği ve geriye dönük çıkarım arasındaki ilişki sorunu, genelleştirilmiş bir geri tümevarım prosedürünün sonsuz uzunluğa, her bilgi kümesi olarak sonsuz eylemlere ve kusurlu olabilecek oyunlarda tüm alt oyun mükemmel dengelerini ürettiğini kanıtlayan Kaminski (2019) tarafından çözüldü. nihai destek koşulunun yerine getirilip getirilmediği bilgisi.

Bir önceki paragrafta geçen "inanılır" kelimesinin ilginç yanı, bir bütün olarak alındığında (alt oyunlara ulaşmanın geri döndürülemezliği göz ardı edilerek) alt-oyun mükemmel stratejilerinden daha üstün, ancak bir tehdit oluşturma anlamında inandırıcı olmayan stratejilerin mevcut olmasıdır. bunları gerçekleştirmek, tehdit oluşturan oyuncuya zarar verecek ve bu strateji kombinasyonunu önleyecektir. Örneğin " tavuk " oyununda, eğer bir oyuncunun direksiyon simidini arabasından koparma seçeneği varsa, bunu her zaman almalıdır çünkü bu, rasyonel rakibinin aynı şeyi yapmasının engellendiği bir "alt oyun"a yol açar ( ve ikisini de öldürmek). Çark sökücü her zaman oyunu kazanır (rakibini yoldan çıkarır) ve rakibin intihara meyilli bir şekilde davayı takip etme tehdidi inandırıcı değildir.

Ayrıca bakınız

Referanslar

Dış bağlantılar