Oyun teorisi sözlüğü - Glossary of game theory

Bu makale için ek alıntılara ihtiyaç var doğrulama. Lütfen yardım et bu makaleyi geliştir tarafından güvenilir kaynaklara alıntılar eklemek. Kaynaksız materyale itiraz edilebilir ve kaldırılabilir. Kaynakları bulun: "Oyun teorisi sözlüğü"  – Haberler  · gazeteler  · kitabın  · akademisyen  · JSTOR (Aralık 2009) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

Oyun Teorisi şubesi matematik içinde oyunlar incelenir: yani, insan davranışını tanımlayan modeller. Bu, konuyla ilgili bazı terimlerin bir sözlüğüdür.

Bir oyunun tanımları

Gösterim kuralları

Gerçek sayılar

${ displaystyle mathbb {R}}$.

Kümesi oyuncular

${ displaystyle mathrm {N}}$.

Strateji alanı

${ displaystyle Sigma = prod _ {i in mathrm {N}} Sigma ^ {i}}$, nerede

Oyuncu i'nin strateji alanı

${ displaystyle Sigma ^ {i}}$ oyuncunun tüm olası yollarının alanıdır ben oyunu oynayabilir.

Oyuncu için bir strateji ben

${ displaystyle sigma _ {i}}$ bir unsurdur ${ displaystyle Sigma ^ {i}}$.

Tamamlayıcılar

${ displaystyle sigma _ {- i}}$ bir unsuru ${ displaystyle Sigma ^ {- i} = prod _ {j in mathrm {N}, j neq i} Sigma ^ {j}}$, dışındaki tüm oyuncular için bir dizi strateji ben.

Sonuç alanı

${ displaystyle Gama}$ çoğu ders kitabında aynıdır -

Kazançlar

${ displaystyle mathbb {R} ^ { mathrm {N}}}$, ne kadar olduğunu açıklayan kazanç (para, zevk vb.) oyuncular oyunun sonunda tahsis edilir.

Normal form oyunu

Normal formdaki bir oyun bir işlevdir:

${ displaystyle pi : prod _ {i in mathrm {N}} Sigma ^ {i} - mathbb {R} ^ { mathrm {N}}}$

Verilen demet nın-nin stratejiler oyuncular tarafından seçilirse, birine ödemeler (gerçek sayılar olarak verilir).

Daha ileri bir genelleme, oyun iki işlevden oluşan bir bileşime:

${ displaystyle pi : prod _ {i içinde mathrm {N}} Sigma ^ {i} ila Gama}$

sonuç fonksiyonu oyunun (bazı yazarlar bu işlevi "oyun formu" olarak adlandırır) ve:

${ displaystyle nu : Gama ila mathbb {R} ^ { mathrm {N}}}$

tahsisi getiriler (veya tercihler) oyunun her sonucu için oyunculara.

Kapsamlı form oyunu

Bu, bir ağaç her birinde nerede tepe of ağaç farklı bir oyuncunun bir kenar. sonuç Kapsamlı bir oyun kümesi genellikle ağaç yaprakları kümesidir.

Kooperatif oyun

Oyuncuların koalisyon kurmalarına (ve koalisyon disiplini uygulamalarına) izin verilen bir oyun. İşbirlikçi oyun, bir belirtilerek verilir. değer her koalisyon için:

${ displaystyle nu : 2 ^ { mathbb {P} (N)} - mathbb {R}}$

Her zaman boş koalisyonun sıfır kazandığı varsayılır. Çözüm kavramları kooperatif oyunlar için genellikle oyuncuların büyük koalisyon ${ displaystyle N}$, kimin değeri ${ displaystyle nu (N)}$ daha sonra bir tahsis vermek için oyuncular arasında bölünür.

Basit oyun

Basit bir oyun, olası kazancın '0' veya '1' olduğu varsayıldığı bir işbirlikli oyunun basitleştirilmiş bir şeklidir. Basit bir oyun çifttir (N, W), nerede W "kazananların" listesi koalisyonlar, ganimet kazanabilen ('1') ve N oyuncular kümesidir.

Sözlük

Kabul edilebilir oyun

bir oyun formu öyle ki mümkün olan her şey için tercih profilleri, oyun var saf nash dengesihepsi pareto verimli.

Malların tahsisi

bir işlev ${ displaystyle nu : Gama ila mathbb {R} ^ { mathrm {N}}}$. Tahsis, bir kardinal iyi (örneğin para) belirleme yaklaşımı oyunculara oyunun farklı sonuçlarına göre verilir.

En iyi yanıt

belirli bir tamamlayıcıya en iyi cevap ${ displaystyle sigma _ {- i}}$ bir stratejidir ${ displaystyle tau _ {i}}$ oyuncuyu maksimize eden ben's ödemesi. Resmi olarak şunu istiyoruz:
${ displaystyle forall sigma _ {i} Sigma ^ {i} quad quad pi ( sigma _ {i}, sigma _ {- i}) leq pi ( tau _ {i}, sigma _ {- i})}$.

Koalisyon

oyuncu grubunun herhangi bir alt kümesidir: ${ displaystyle mathrm {S} subseteq mathrm {N}}$.

Condorcet kazananı

Verilen bir tercih ν üzerinde sonuç alanı, bir sonuç a kukla olmayan tüm oyuncular tercih ederse akbaba kazananıdır a diğer tüm sonuçlara.

Karar Verilebilirlik

Oyun teorisi ile ilgili olarak, bir oyunun çözülüp çözülemeyeceği konusunda bir cevap verebilecek ve döndürecek bir algoritmanın varlığı sorusunu ifade eder.^[1]

Kararlılık

Bir oyunun bir veya diğer oyuncusunun kazanma stratejisine sahip olduğu koşulları ve bu tür stratejilerin varlığının sonuçlarını inceleyen bir küme teorisi alt alanı. Küme teorisinde incelenen oyunlar Gale – Stewart oyunlarıdır - oyuncuların sonsuz sayıda hamle dizisi yaptıkları ve beraberliğin olmadığı iki oyunculu mükemmel bilgi oyunları.

Kararlı oyun (veya Kesinlikle belirlenmiş oyun)

Oyun teorisinde, kesin olarak belirlenmiş bir oyun iki oyuncudur sıfır toplam en az bir tane olan oyun Nash dengesi her iki oyuncu da kullanıyor saf stratejiler.^[2][3]

Diktatör

Oyuncu bir güçlü diktatör Diğer oyunculardan bağımsız olarak herhangi bir sonucu garanti edebiliyorsa. ${ displaystyle m in mathbb {N}}$ bir zayıf diktatör herhangi bir sonucu garanti edebiliyorsa, ancak bunu yapma stratejileri tamamlayıcı strateji vektörüne bağlı olabilir. Doğal olarak, her güçlü diktatör zayıf bir diktatördür. Resmen:
m bir Güçlü diktatör Eğer:
${ displaystyle forall a in mathrm {A}, ; sigma _ {n} Sigma ^ {n} ; st ; forall sigma _ {- n} Sigma ^ {- n}: ; Gama ( sigma _ {- n}, sigma _ {n}) = a}$
m bir Zayıf diktatör Eğer:
${ displaystyle forall a in mathrm {A}, ; forall sigma _ {- n} in Sigma ^ {- n} ; var sigma _ {n} Sigma ^ {n} ; st ; Gama ( sigma _ {- n}, sigma _ {n}) = a}$

Başka bir ifade şekli şudur:

a zayıf diktatör dır-dir ${ displaystyle alpha}$- Olası her sonuç için etkilidir.

Bir güçlü diktatör dır-dir ${ displaystyle beta}$- Olası her sonuç için etkilidir.

Bir oyunda birden fazla olamaz güçlü diktatör. Bazı oyunlarda birden fazla zayıf diktatörler (içinde Taş kağıt makas her iki oyuncu da zayıf diktatörler ama hiçbiri bir güçlü diktatör).

Ayrıca bakın Etkililik. Antonym: kukla.

Hakim sonuç

Verilen bir tercih ν üzerinde sonuç alanıbir sonuç olduğunu söylüyoruz a sonuca hakimdir b (dolayısıyla, b ... baskın strateji) tüm oyuncular tarafından tercih edilirse. Ek olarak, bazı oyuncular kesinlikle b bitmiş a, sonra şunu söyleriz a dır-dir kesinlikle hakim. Resmen:
${ displaystyle forall j in mathrm {N} ; quad nu _ {j} (a) leq nu _ {j} (b)}$ hakimiyet için ve
${ displaystyle var mathrm {N} ; s.t. ; nu _ {i} (a) < nu _ {i} (b)}$ sıkı hakimiyet için.
Bir sonuç a (kesinlikle) hakim eğer öyleyse (kesinlikle) hakim başka biri tarafından sonuç.
Bir sonuç a bir için hakimdir koalisyon S eğer tüm oyuncular S başka bir sonucu tercih etmek a. Ayrıca bakınız Condorcet kazananı.

Hakim strateji

stratejinin (güçlü bir şekilde) strateji tarafından yönetildiğini söylüyoruz ${ displaystyle tau _ {i}}$ herhangi bir tamamlayıcı strateji dizisi için ${ displaystyle sigma _ {- i}}$, oyuncu ben oynayarak faydalar ${ displaystyle tau _ {i}}$. Resmi olarak konuşursak:
${ displaystyle forall sigma _ {- i} içinde Sigma ^ {- i} quad quad pi ( sigma _ {i}, sigma _ {- i}) leq pi ( tau _ {i}, sigma _ {- i})}$ ve
${ Displaystyle var sigma _ {- i} Sigma ^ {- i} quad st quad pi ( sigma _ {i}, sigma _ {- i}) < pi ( tau _ {i}, sigma _ {- i})}$.
Bir strateji σ (kesinlikle) hakim eğer öyleyse (kesinlikle) hakim başka biri tarafından strateji.

Kukla

Oyuncu ben oyunun sonucu üzerinde hiçbir etkisi yoksa bir kukla. Yani oyunun sonucu oyuncuya duyarsızsa ben'stratejisi.

Zıtlıklar: söyle, veto, diktatör.

Etkililik

Bir koalisyon (veya tek bir oyuncu) S dır-dir etkili a eğer zorlayabilirse a oyunun sonucu olmak. S üyeleri ise α-etkilidir S stratejileri var s.t. tamamlayıcısı ne olursa olsun S yapar, sonuç olacak a.

S tamamlayıcı herhangi bir strateji için β etkilidir Süyeleri S sonucu garantileyen stratejilerle cevap verebilir a.

Sonlu oyun

her biri sonlu bir dizi içeren sonlu sayıda oyuncunun olduğu bir oyundur. stratejiler.

Büyük koalisyon

tüm oyuncuları içeren koalisyonu ifade eder. İşbirlikçi oyunlarda genellikle büyük koalisyonun oluştuğu ve oyunun amacının istikrarlı ithamlar bulmak olduğu varsayılır.

Karışık strateji

oyuncu için ben bir olasılık dağılımı P açık ${ displaystyle Sigma ^ {i}}$. O oyuncunun ben şuna göre rastgele bir strateji seçer P.

Karışık Nash Dengesi

İle aynı Saf Nash Dengesi, uzayda tanımlanmıştır karışık stratejiler. Her sonlu oyunda Karışık Nash Dengesi.

Pareto verimliliği

Bir sonuç a nın-nin oyun formu π (şiddetle) pareto verimli Öyleyse haksız her şeyin altında tercih profilleri.

Tercih profili

bir işlev ${ displaystyle nu : Gama ila mathbb {R} ^ { mathrm {N}}}$. Bu sıra oyunun sonucunu açıklama yaklaşımı. Tercih, oyuncuların oyunun olası sonuçlarından ne kadar 'memnun' olduklarını açıklar. Görmek malların tahsisi.

Saf Nash Dengesi

Bir element ${ displaystyle sigma = ( sigma _ {i}) _ {i içinde mathrm {N}}}$ bir oyunun strateji alanı saf nash denge noktası oyuncu yoksa ben stratejisinden saparak faydalanabilir ${ displaystyle sigma _ {i}}$, diğer oyuncuların oynadığı göz önüne alındığında ${ displaystyle sigma}$. Resmen:
${ displaystyle forall i in mathrm {N} quad forall tau _ {i} Sigma ^ {i} quad pi ( tau , sigma _ {- i}) leq pi ( sigma )}$.
Hiçbir denge noktası baskın değildir.

Söyle

Oyuncu ben var Söyle eğer o değilse Kukla, yani bazı tamamlama stratejileri dizisi varsa π (σ_i) sabit bir fonksiyon değildir.

Antonym: Kukla.

Shannon numarası

Muhafazakar bir alt sınırı oyun ağacı karmaşıklığı nın-nin satranç (10¹²⁰).

Çözülmüş oyun

Sonucu (kazanma, kaybetme veya beraberlik) tüm oyunculardan mükemmel bir oyun olduğu varsayılarak doğru tahmin edilebilen bir oyun.

Değer

Bir değer rasyonel olarak beklenen bir oyunun sonuç. Birkaç taneden daha fazlası var değer, oyuna bir çözüm elde etmenin farklı yöntemlerini açıklıyor.

Veto

Bir veto, bazı oyuncunun belirli bir alternatifin oyunun sonucu olmasını engelleme yeteneğini (veya hakkını) belirtir. Bu yeteneğe sahip bir oyuncuya denir veto oyuncusu.

Antonym: Kukla.

Zayıf kabul edilebilir oyun

sahip olan bir oyundur saf nash dengesi bazıları pareto verimli.

Sıfır toplam oyun

tahsisinin farklı üzerinde sabit olduğu bir oyundur sonuçlar. Resmen:
${ displaystyle forall gamma in Gamma sum _ {i in mathrm {N}} nu _ {i} ( gamma ) = const.}$
w.l.g. sabitin sıfır olduğunu varsayabiliriz. Sıfır toplamlı bir oyunda, bir oyuncunun kazancı, diğer oyuncunun kaybıdır. Çoğu klasik masa oyunu (ör. satranç, dama ) sıfır toplam.

Referanslar