Kooperatif oyun teorisi - Cooperative game theory

In oyun teorisi , bir kooperatif oyun (ya da koalisyonlu oyun ) bir olan oyun ile rekabet grupları arasındaki oyuncuları nedeniyle kooperatif davranış dış uygulanması (örn aracılığıyla olasılığına ( "koalisyonlar") sözleşme hukuku ). Bunlar, ittifak kurma olasılığının olmadığı veya tüm anlaşmaların kendi kendini uygulayacağı (örneğin, inandırıcı tehditler yoluyla ) gerektiği işbirlikçi olmayan oyunlara karşıdır .

İşbirlikli oyunlar genellikle hangi koalisyonların oluşacağını, grupların gerçekleştireceği ortak eylemleri ve sonuçta ortaya çıkan toplu getirileri tahmin etmeye odaklanan işbirlikli oyun teorisi çerçevesinde analiz edilir . Bireysel oyuncuların eylemlerini ve getirilerini tahmin etmeye ve Nash dengelerini analiz etmeye odaklanan geleneksel işbirlikçi olmayan oyun teorisine karşıdır .

İşbirlikçi oyun teorisi, yalnızca koalisyonların yapısını, stratejilerini ve getirilerini tanımladığı için üst düzey bir yaklaşım sağlarken, işbirlikçi olmayan oyun teorisi de pazarlık prosedürlerinin her bir koalisyon içindeki getirilerin dağılımını nasıl etkileyeceğine bakar. İşbirlikçi olmayan oyun teorisi daha genel olduğundan, işbirlikçi oyunlar, olasılık nedeniyle oyuncular için mevcut olan tüm olası stratejileri kapsayacak yeterli varsayımların yapılması koşuluyla, işbirlikçi olmayan oyun teorisi yaklaşımı ile analiz edilebilir (tersi geçerli değildir). dış işbirliği uygulaması. Böylelikle tüm oyunların işbirlikçi olmayan bir çerçeve altında ifade edilmesi mümkün olsa da, çoğu durumda stratejik pazarlık sürecinde oyunculara sunulan resmi prosedürleri doğru bir şekilde modellemek için yeterli bilgi mevcut değildir veya ortaya çıkan model çok yüksek olacaktır. gerçek dünyada pratik bir araç sunmak için karmaşıklık. Bu gibi durumlarda, işbirlikçi oyun teorisi, pazarlık yetkileri hakkında herhangi bir varsayımda bulunmak zorunda kalmadan oyunun genel olarak analizine izin veren basitleştirilmiş bir yaklaşım sağlar.

Matematiksel tanım

Her koalisyon için bir değer belirlenerek ortak bir oyun verilir. Resmi olarak koalisyonlu oyun oyuncuların sonlu kümesi oluşur denilen, büyük koalisyon ve karakteristik fonksiyonu olduğunu karşılayan ödemeler bir dizi oyuncuların tüm olası koalisyonlar kümesinden . İşlev, bir grup oyuncunun bir koalisyon oluşturarak ne kadar toplu kazanç elde edebileceğini açıklar ve oyuna bazen bir değer oyunu veya kar oyunu denir . ${\ displaystyle N}$ ${\ displaystyle v: 2 ^ {N} \ - \ mathbb {R}}$${\ displaystyle v (\ boş küme) = 0}$

Tersine, işbirlikçi bir oyun, tatmin edici bir karakteristik maliyet fonksiyonu ile de tanımlanabilir . Bu ortamda, oyuncular bazı görevleri yerine getirmelidir ve karakteristik işlev , görevi birlikte gerçekleştiren bir dizi oyuncunun maliyetini temsil eder. Bu tür bir oyun, maliyet oyunu olarak bilinir . Çoğu işbirlikçi oyun teorisi kar oyunlarıyla ilgilense de, tüm kavramlar kolayca maliyet ayarına çevrilebilir. ${\ displaystyle c: 2 ^ {N} \ - \ mathbb {R}}$${\ displaystyle c (\ boş küme) = 0}$${\ displaystyle c}$

Harsanyi temettü

Harsanyi temettü (adını John Harsanyi genelleme için kullandı, Shapley değeri 1963 yılında) bir kooperatif oyunda oyuncuların koalisyonu tarafından oluşturulan fazlalığı tanımlar. Bu fazlalığı belirtmek için, bu koalisyonun değeri, alt koalisyonlar tarafından zaten yaratılan fazlalıkla düzeltilir. Bu amaçla, oyundaki koalisyonun temettü oranı tekrarlı olarak şu şekilde belirlenir: ${\ displaystyle d_ {v} (S)}$${\ displaystyle S}$${\ displaystyle v}$

${\ displaystyle {\ başlar {hizalı} d_ {v} (\ {i \}) & = v (\ {i \}) \\ d_ {v} (\ {i, j \}) & = v (\ {i, j \}) - d_ {v} (\ {i \}) - d_ {v} (\ {j \}) \\ d_ {v} (\ {i, j, k \}) & = v (\ {i, j, k \}) - d_ {v} (\ {i, j \}) - d_ {v} (\ {i, k \}) - d_ {x} (\ {j, k \}) - d_ {v} (\ {i \}) - d_ {v} (\ {j \}) - d_ {v} (\ {k \}) \\ & \ vdots \\ d_ {v } (S) & = v (S) - \ sum _ {T \ subsetneq S} d_ {v} (T) \ end {hizalı}}}$

Temettü için açık bir formül ile verilmiştir . Fonksiyon olarak da bilinen Möbiüs ters arasında . Nitekim, biz kurtarabilirsiniz gelen formül yardımıyla . ${\ textstyle d_ {v} (S) = \ toplam _ {T \ subseteq S} (- 1) ^ {| S \ setminus T |} v (T)}$${\ displaystyle d_ {v}: 2 ^ {N} \ - \ mathbb {R}}$${\ displaystyle v: 2 ^ {N} \ - \ mathbb {R}}$${\ displaystyle v}$${\ displaystyle d_ {v}}$${\ textstyle v (S) = d_ {v} (S) + \ toplamı _ {T \ subsetneq S} d_ {v} (T)}$

Harsanyi temettüleri hem oyunları hem de çözüm konseptlerini analiz etmek için kullanışlıdır, örneğin Shapley değeri , her bir koalisyonun temettülerinin üyeleri arasında dağıtılmasıyla elde edilir, yani oyuncunun oyundaki Shapley değeri , bir oyuncunun temettülerindeki payının toplanmasıyla verilir. ait olduğu tüm koalisyonlar . ${\ displaystyle \ phi _ {i} (v)}$${\ displaystyle i}$${\ displaystyle v}$${\ textstyle \ phi _ {i} (v) = \ toplam _ {S \ alt küme N: i \ içinde S} {d_ {v} (S)} / {| S |}}$

Dualite

Bir kar oyunu olalım . İkili oyun ait maliyet oyunu olarak tanımlanmaktadır ${\ displaystyle v}$${\ displaystyle v}$${\ displaystyle v ^ {*}}$

${\ displaystyle v ^ {*} (S) = v (N) -v (N \ setminus S), \ forall ~ S \ subseteq N.}$

Sezgisel olarak, ikili oyun , büyük koalisyona katılmama koalisyonu için fırsat maliyetini temsil ediyor . İkili kar oyunu , bir maliyet oyunu için aynı şekilde tanımlanabilir . Bir kooperatif oyun ve ikilisi bir anlamda eşdeğerdir ve birçok özelliği paylaşırlar. Örneğin, bir oyunun çekirdeği ve ikilisi eşittir. İşbirlikçi oyun ikiliği hakkında daha fazla ayrıntı için, örneğin bakınız ( Bilbao 2000 ). ${\ displaystyle S}$${\ displaystyle N}$${\ displaystyle c ^ {*}}$${\ displaystyle c}$

Alt oyunlar

Boş olmayan bir oyuncu koalisyonu olalım . Alt-oyun ile doğal olarak tanımlanır ${\ displaystyle S \ subsetneq N}$ ${\ displaystyle v_ {S}: 2 ^ {S} \ - \ mathbb {R}}$${\ displaystyle S}$

${\ displaystyle v_ {S} (T) = v (T), \ forall ~ T \ subseteq S.}$

Başka bir deyişle, dikkatimizi sadece içerdiği koalisyonlarla sınırlıyoruz . Alt oyunlar , büyük koalisyon için tanımlanan çözüm kavramlarını daha küçük koalisyonlarda uygulamamıza izin verdiği için kullanışlıdır . ${\ displaystyle S}$

Karakterizasyon için özellikler

Süperadditivite

Karakteristik fonksiyonların genellikle süper eklemeli olduğu varsayılır ( Owen 1995 , s. 213). Bu, ayrık koalisyonlar birliğinin değerinin , koalisyonların ayrı değerlerinin toplamından daha az olmadığı anlamına gelir :

${\ Displaystyle v (S \ fincan T) \ geq v (S) + v (T)}$ ne zaman tatmin olursa . ${\ displaystyle S, T \ subseteq N}$${\ displaystyle S \ cap T = \ emptyset}$

Monotonluk

Daha büyük koalisyonlar daha çok kazanır:

${\ Displaystyle S \ subseteq T \ Rightarrow v (S) \ leq v (T)}$ .

Bu, süperadditiviteden kaynaklanır . yani kazançlar normalleştirilirse, tekil koalisyonların değeri sıfır olur.

Basit oyunlar için özellikler

Bir koalisyon oyunu v , getiriler 1 veya 0 ise, yani koalisyonlar ya "kazanıyor" ya da "kaybediyorsa" basit kabul edilir .

Eşdeğer bir basit bir oyun koleksiyonu olarak tanımlanabilir W üyeleri koalisyon, W denir kazanan koalisyonlar ve diğerleri kaybediyor koalisyonlar. Bazen basit bir oyunun boş olmadığı veya boş bir set içermediği varsayılır. Bununla birlikte, matematiğin diğer alanlarında, basit oyunlara hiper grafikler veya Boole işlevleri (mantık işlevleri) de denir .

• Basit bir W oyunu , kazanan bir koalisyon içeren herhangi bir koalisyon da kazanıyorsa, yani, eğer ve ima ediyorsa , monotondur . ${\ displaystyle S \ W olarak}$${\ displaystyle S \ subseteq T}$${\ displaystyle T \ W olarak}$
• Basit bir oyun W ise uygun olmadığını kazanan tüm koalisyonun tamamlayıcısı (muhalefet) olduğunu, kaybettiği takdirde ima . ${\ displaystyle S \ W olarak}$${\ displaystyle N \ setminus S \ notin W}$
• Basit bir W oyunu , kaybeden herhangi bir koalisyonun tamamlayıcısı kazanıyorsa, yani ima ediyorsa güçlüdür . ${\ displaystyle S \ notin W}$${\ displaystyle N \ setminus S \ W olarak}$
  • Basit bir W oyunu uygun ve güçlüyse, bir koalisyon ancak ve ancak tamamlayıcısı kaybediyorsa, yani iff kaybediyorsa kazanır . (Eğer v , herhangi bir S. için uygun ve güçlü bir koalisyonel basit oyunsa .) ${\ displaystyle S \ W olarak}$${\ displaystyle N \ setminus S \ notin W}$${\ displaystyle v (S) = 1-v (N \ setminus S)}$
• Bir veto oyuncu basit bir oyunda (vetoer) Tüm kazanan koalisyonlar ait bir oyuncudur. Bir veto oyuncusu olduğunu varsayarsak, veto oyuncusu içermeyen herhangi bir koalisyon kaybediyor. Basit bir W oyunu , bir veto oyuncusu varsa, yani tüm kazanan koalisyonların kesişme noktası boş değilse , zayıftır ( meslektaş ) . ${\ displaystyle \ bigcap W: = \ bigcap _ {S \ W} S}$
  • Basit bir oyundaki bir diktatör , bu oyuncuyu içeren herhangi bir koalisyonun kazanması için bir veto oyuncusudur. Diktatör, kaybedilen herhangi bir koalisyona ait değil. ( Deneysel ekonomideki diktatör oyunları bununla ilgisizdir.)
• Bir taşıyıcı basit bir oyun ait W kümesidir herhangi koalisyon için böyle S , elimizdeki IFF . Basit bir oyunun bir taşıyıcısı olduğunda, ona ait olmayan herhangi bir oyuncu göz ardı edilir. Sonlu bir taşıyıcıya sahipse ( N sonsuz olsa bile ) basit bir oyuna bazen sonlu denir . ${\ displaystyle T \ subseteq N}$${\ displaystyle S \ W olarak}$${\ displaystyle S \ cap T \ W olarak}$
• Nakamura numarası basit bir oyun minimal sayıdır koalisyonlar kazanan boş kesişme ile. Nakamura'nın teoremine göre, sayı rasyonalite derecesini ölçer; bir toplama kuralının ne ölçüde iyi tanımlanmış seçimler sağlayabileceğinin bir göstergesidir.

Yukarıdaki aksiyomlar arasında, aşağıdakiler gibi birkaç ilişki yaygın olarak kabul edilmiştir (örneğin, Peleg, 2002, Kısım 2.1):

• Basit bir oyun zayıfsa, doğrudur.
• Basit bir oyun, ancak ve ancak güçlü ve zayıfsa diktatörlüktür.

Daha genel olarak, sonuçları Tabloda özetlenen dört geleneksel aksiyom (monotonluk, uygunluk, sağlamlık ve zayıf olmama), sonluluk ve algoritmik hesaplanabilirlik arasındaki ilişkinin tam bir araştırması yapılmıştır (Kumabe ve Mihara, 2011). Aşağıdaki "Basit Oyunların Varlığı".

Basit Oyunların Varlığı

Tür	Sonlu Uyumsuz	Sonlu Hesaplanabilir	Infinite Non-comp	Sonsuz Hesaplanabilir
1111	Hayır	Evet	Evet	Evet
1110	Hayır	Evet	Hayır	Hayır
1101	Hayır	Evet	Evet	Evet
1100	Hayır	Evet	Evet	Evet
1011	Hayır	Evet	Evet	Evet
1010	Hayır	Hayır	Hayır	Hayır
1001	Hayır	Evet	Evet	Evet
1000	Hayır	Hayır	Hayır	Hayır
0111	Hayır	Evet	Evet	Evet
0110	Hayır	Hayır	Hayır	Hayır
0101	Hayır	Evet	Evet	Evet
0100	Hayır	Evet	Evet	Evet
0011	Hayır	Evet	Evet	Evet
0010	Hayır	Hayır	Hayır	Hayır
0001	Hayır	Evet	Evet	Evet
0000	Hayır	Hayır	Hayır	Hayır

Basit oyunlar için çeşitli aksiyomların Nakamura sayılarına dayattığı kısıtlamalar da kapsamlı bir şekilde çalışıldı. Özellikle, veto oyuncusu olmayan hesaplanabilir basit bir oyunun Nakamura sayısı, yalnızca uygun ve güçlü olmayan bir oyunsa 3'ten büyüktür .

İşbirlikçi olmayan teori ile ilişki

Let G stratejik (non-kooperatif) oyunu olması. Daha sonra, koalisyonların koordineli davranışı uygulama yeteneğine sahip olduğunu varsayarsak, G ile ilişkili birkaç ortak oyun vardır . Bu oyunlar genellikle G'nin temsili olarak adlandırılır . İki standart temsil şöyledir:

• Α-etkili oyun, her bir koalisyonla, üyelerinin kazanımlarının toplamının güçlerini birleştirerek 'garanti edebileceği' bir ilişki kurar. 'Garanti etme' ile, değerin maks-min olduğu, örneğin muhalefetin stratejileri üzerinden alınan minimumun maksimal değeri olduğu kastedilmektedir.
• Β-etkili oyun, her koalisyonla, üyelerinin kazanımlarının toplamını, güçlerini birleştirerek 'stratejik olarak garanti edebilir'. "Stratejik olarak garanti etme" ile, değerin min-max olduğu kastedilmektedir, örneğin muhalefetin stratejileri üzerinden alınan maksimumun minimum değeri.

Çözüm kavramları

İşbirlikçi oyun teorisindeki ana varsayım, büyük koalisyonun oluşacağıdır. O zaman zorluk, kazancı oyuncular arasında adil bir şekilde paylaştırmaktır. (Oyuncular ayrılarak küçük koalisyonlar oluşturmak bile, biz aslında oluşturacak her ne koalisyonlar tarafından tanımlanan subgames çözüm kavramları uygulayabilirsiniz çünkü bu varsayım, kısıtlayıcı değildir.) Bir çözüm konsepti bir vektör olduğu (ya da bir vektör seti) olduğunu gösterir her oyuncuya tahsis. Araştırmacılar, farklı adalet kavramlarına dayanan farklı çözüm konseptleri önermişlerdir. Bir çözüm konseptinde aranacak bazı özellikler şunları içerir: ${\ displaystyle N}$${\ displaystyle v (N)}$${\ displaystyle x \ in \ mathbb {R} ^ {N}}$

• Verim: ödeme vektör tam olarak toplam değeri böler: . ${\ displaystyle \ toplamı _ {i \ in N} x_ {i} = v (N)}$
• Bireysel rasyonellik: Hiçbir oyuncu kendi başına alabilir olandan daha az alır: . ${\ displaystyle x_ {i} \ geq v (\ {i \}), \ forall ~ i \ N'de}$
• Varoluş: Herhangi bir oyun için çözüm konsepti mevcuttur . ${\ displaystyle v}$
• Benzersizlik: Çözüm konsepti her oyun için benzersizdir . ${\ displaystyle v}$
• Marjinallik: Bir oyuncunun getirisi sadece bu oyuncunun marjinal katkısına bağlıdır, yani bu marjinal katkılar iki farklı oyunda aynı ise, o zaman kazanç aynıdır: içeri ve içinde aynı olduğu anlamına gelir . ${\ displaystyle v (S \ fincan \ {i \}) = w (S \ fincan \ {i \}), \ forall ~ S \ subseteq N \ setminus \ {i \}}$${\ displaystyle x_ {i}}$${\ displaystyle v}$${\ displaystyle w}$
• Monotonluk: Bir oyuncu artar ödeme bu oyuncunun artışın marjinal katkısı ise: ima içinde zayıf büyüktür daha . ${\ displaystyle v (S \ fincan \ {i \}) \ leq w (S \ fincan \ {i \}), \ forall ~ S \ subseteq N \ setminus \ {i \}}$${\ displaystyle x_ {i}}$${\ displaystyle w}$${\ displaystyle v}$
• Hesaplama kolaylığı: Çözüm kavramı verimli bir şekilde hesaplanabilir (yani, oyuncu sayısına göre polinom zamanında ). ${\ displaystyle | N |}$
• Simetri: konsept çözümü ayırır ödemeleri eşit simetrik oyunculara , . İki oyuncu , olan simetrik ise ; yani, oyunculardan sadece birini içeren herhangi bir koalisyonda bir oyuncuyu diğeriyle değiştirebiliriz ve getiriyi değiştirmeyiz. ${\ displaystyle x}$${\ displaystyle x_ {i} = x_ {j}}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle v (S \ fincan \ {i \}) = v (S \ fincan \ {j \}), \ forall ~ S \ subseteq N \ setminus \ {i, j \}}$
• Eklenebilirlik: Bir oyuncuya toplam iki oyunda tahsis, her bir oyunda oyuncuya yapılan tahsislerin toplamıdır. Matematiksel olarak, eğer ve oyunlar, oyunu payoffs toplamı koalisyon iki ayrı oyunlarda alacağı herhangi koalisyona basitçe atar. Her oyuncuya Ek bir solüsyon kavramı atar içeri ne alacağı toplamı ve . ${\ displaystyle v}$${\ displaystyle \ omega}$${\ displaystyle (v + \ omega)}$${\ displaystyle (v + \ omega)}$${\ displaystyle v}$${\ displaystyle \ omega}$
• Null Oyunculara Sıfır Tahsis: Boş oyuncuya tahsis sıfırdır. Bir boş oyuncu karşılar . Ekonomik açıdan, boş bir oyuncunun, onu içermeyen herhangi bir koalisyon için marjinal değeri sıfırdır. ${\ displaystyle i}$${\ displaystyle v (S \ fincan \ {i \}) = v (S), \ forall ~ S \ subseteq N \ setminus \ {i \}}$

Etkili bir ödeme vektörü denen önceden isnat ve bireysel olarak akılcı ön isnat bir adlandırılır isnat . Çoğu çözüm kavramı, isnatlardır.

Ahır seti

Bir oyunun kararlı seti ( von Neumann-Morgenstern çözümü ( von Neumann & Morgenstern 1944 ) olarak da bilinir ), 2'den fazla oyunculu oyunlar için önerilen ilk çözümdü. Izin bir oyun olacak ve izin , iki olmak ithamlarda arasında . Sonra bazı koalisyon tatmin ederse hakim olur ve . Başka bir deyişle, oyuncular kazançları kendilerinden gelenlere tercih ederler ve kullanılıyorsa büyük koalisyondan ayrılma tehdidinde bulunabilirler çünkü kendi başlarına elde ettikleri getiri en az altında aldıkları tahsisat kadar büyüktür . ${\ displaystyle v}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle v}$${\ displaystyle x}$ ${\ displaystyle y}$${\ displaystyle S \ neq \ emptyset}$${\ displaystyle x_ {i}> y_ {i}, \ forall ~ i \ S’de}$${\ displaystyle \ toplamı _ {i \ içinde S} x_ {i} \ leq v (S)}$${\ displaystyle S}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle y}$${\ displaystyle x}$

Bir stabil bir grubu bir dizi yerine atama ye uyan iki özellikleri:

• İç kararlılık: Kararlı kümedeki hiçbir getiri vektörüne kümedeki başka bir vektör hakim değildir.
• Dış kararlılık: Küme dışındaki tüm getiri vektörlerine kümedeki en az bir vektör hakimdir.

Von Neumann ve Morgenstern ahır kümesini bir toplumdaki kabul edilebilir davranışların toplamı olarak gördüler: Hiçbiri diğerine açıkça tercih edilmez, ancak her kabul edilemez davranış için tercih edilen bir alternatif vardır. Tanım çok geneldir ve konseptin çok çeşitli oyun formatlarında kullanılmasına izin verir.

Özellikleri

• Bir kararlı küme var olabilir veya olmayabilir ( Lucas 1969 ) ve eğer varsa, tipik olarak benzersiz değildir ( Lucas 1992 ). Kararlı kümeleri bulmak genellikle zordur. Bu ve diğer zorluklar, diğer birçok çözüm konseptinin geliştirilmesine yol açmıştır.
• İşbirlikçi oyunların pozitif bir bölümü, çekirdekten oluşan benzersiz kararlı setlere sahiptir ( Owen 1995 , s. 240).
• İşbirlikçi oyunların olumlu bir kısmı, oyuncuları ayırt eden sabit setlere sahiptir . Bu tür setlerde en azından ayrımcılığa uğrayan oyuncular hariç tutulur ( Owen 1995 , s. 240). ${\ displaystyle n-2}$${\ displaystyle n-3}$

Çekirdek

Oyun olalım . Çekirdek ve sonuç vektörleri kümesi ${\ displaystyle v}$${\ displaystyle v}$

${\ displaystyle C (v) = \ sol \ {x \ in \ mathbb {R} ^ {N}: \ toplamı _ {i \ N} x_ {i} = v (N); \ dört \ toplamı _ { i \ in S} x_ {i} \ geq v (S), \ forall ~ S \ subseteq N \ right \}.}$

Kısacası, çekirdek, hiçbir koalisyonun üyelerinin getirilerinin toplamından daha büyük bir değere sahip olmadığı isnatlar dizisidir . Bu nedenle, hiçbir koalisyonun büyük koalisyondan ayrılma ve daha büyük bir getiri alma teşviki yoktur.

Özellikleri

• Çekirdek , bir oyunun (bakınız boş olabilir Bondareva-Shapley'in teoremini ). Çekirdeği boş olmayan oyunlara dengeli denir .
• Boş değilse, çekirdek mutlaka benzersiz bir vektör içermez.
• Çekirdek herhangi bir stabil grubu içinde yer alır ve temel olarak stabil ise benzersiz kararlı grubu olmaktadır; kanıt için bkz. ( Driessen 1988 ).

Tercihlere göre basit bir oyunun özü

Basit oyunlar için, her oyuncunun bir dizi alternatif üzerinde tercihleri ​​olduğu varsayıldığında, başka bir çekirdek kavramı vardır . Bir profil listesidir bireysel tercihlerin üzerinde . İşte o kişi demektir alternatif tercih etmek profiline . Basit bir oyun Verilen ve bir profil , bir baskınlık ilişkisi tanımlanır tarafından kazanan bir koalisyon vardır ancak ve ancak (yani ) tatmin herkes için . Çekirdek basit oyunun profile göre tercihlere göre undominated alternatiflerin dizi (maksimal öğeleri kümesinin saygı ile ): ${\ displaystyle X}$${\ displaystyle p = (\ succ _ {i} ^ {p}) _ {i \ N'de}}$${\ displaystyle \ succ _ {i} ^ {p}}$${\ displaystyle X}$${\ displaystyle x \ succ _ {i} ^ {p} y}$${\ displaystyle i}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle p}$${\ displaystyle v}$${\ displaystyle p}$${\ displaystyle \ succ _ {v} ^ {p}}$${\ displaystyle X}$${\ displaystyle x \ succ _ {v} ^ {p} y}$${\ displaystyle S}$${\ displaystyle v (S) = 1}$${\ displaystyle x \ succ _ {i} ^ {p} y}$${\ displaystyle i \ S’de}$ ${\ displaystyle C (v, p)}$${\ displaystyle v}$${\ displaystyle p}$${\ displaystyle \ succ _ {v} ^ {p}}$${\ displaystyle X}$${\ displaystyle \ succ _ {v} ^ {p}}$

${\ displaystyle x \ in C (v, p)}$ ancak ve ancak böyle bir şey yoksa . $X'te {\ displaystyle y \}$${\ displaystyle y \ succ _ {v} ^ {p} x}$

Nakamura numarası basit bir oyunun boş kesişme ile koalisyonlar kazanan minimal sayıdır. Nakamura teoremi göbeği durumları tüm profiller için boş olmayan bir bir asiklik (alternatif olarak, geçişli ancak ve ancak) tercihleri sonlu ve ana numarası (elemanların sayısı) daha az Nakamura sayısı daha . Kumabe ve Mihara'nın bir varyantı, çekirdeğin , yalnızca ve ancak kardinal sayısı Nakamura sayısından küçükse, maksimal öğesi olan tüm tercih profilleri için boş olmadığını belirtir . (Ayrıntılar için Nakamura numarasına bakın.) ${\ displaystyle C (v, p)}$${\ displaystyle p}$${\ displaystyle X}$${\ displaystyle X}$${\ displaystyle v}$${\ displaystyle C (v, p)}$${\ displaystyle p}$${\ displaystyle X}$${\ displaystyle v}$

Güçlü epsilon çekirdeği

Çünkü ana boş olabilir, bir genelleme (tanıtıldı Shapley'i ve Shubik 1966 ). Güçlü -çekirdek ${\ displaystyle \ varepsilon}$ bir sayı için ödeme vektörlerinin kümesidir ${\ displaystyle \ varepsilon \ in \ mathbb {R}}$

${\ displaystyle C _ {\ varepsilon} (v) = \ sol \ {x \ in \ mathbb {R} ^ {N}: \ toplamı _ {i \ N} x_ {i} = v (N); \ dörtlü \ sum _ {i \ in S} x_ {i} \ geq v (S) - \ varepsilon, \ forall ~ S \ subseteq N \ right \}.}$

Ekonomik açıdan, güçlü çekirdek, hiçbir koalisyonun, ayrılmanın bir cezasını ödemesi gerekiyorsa, büyük koalisyondan ayrılmak suretiyle getirisini iyileştiremeyeceği bir dizi ön-ithamdır . Bunun olumsuz olabileceğini unutmayın, bu durumda büyük koalisyondan ayrılma bonusu anlamına gelir. Açıkça, çekirdeğin boş olup olmadığına bakılmaksızın , güçlü- çekirdek yeterince büyük bir değer için boş olmayacak ve yeterince küçük (muhtemelen negatif) bir değer için boş olacaktır . Bu akıl yürütme çizgisini takiben , ( Maschler, Peleg & Shapley 1979 ) ortaya konan en küçük çekirdek , boş olmayan tüm güçlü çekirdeklerin kesişimidir. En küçük değeri için seti boş olmayan yapan güçlü çekirdek olarak da görülebilir ( Bilbao 2000 ). ${\ displaystyle \ varepsilon}$${\ displaystyle \ varepsilon}$${\ displaystyle \ varepsilon}$${\ displaystyle \ varepsilon}$${\ displaystyle \ varepsilon}$${\ displaystyle \ varepsilon}$${\ displaystyle \ varepsilon}$${\ displaystyle \ varepsilon}$${\ displaystyle \ varepsilon}$

Shapley değeri

Shapley'in değeri , etkili bir simetrik ve tatmin monotonicity benzersiz ödeme vektörüdür. Etkin, simetrik, katkı sağlayan ve kukla oyunculara sıfır getiri atayan benzersiz getiri vektörü olduğunu gösteren Lloyd Shapley ( Shapley 1953 ) tarafından tanıtıldı . Süper eklemeli bir oyunun Shapley değeri bireysel olarak rasyoneldir, ancak bu genel olarak doğru değildir. ( Driessen 1988 )

Çekirdek

Oyun olalım ve verimli bir kazanç vektörü olalım . Maksimum artı oyuncunun i oyuncu üzerinde j göre , x ise ${\ displaystyle v: 2 ^ {N} \ - \ mathbb {R}}$${\ displaystyle x \ in \ mathbb {R} ^ {N}}$

${\ displaystyle s_ {ij} ^ {v} (x) = \ max \ sol \ {v (S) - \ toplamı _ {k \ in S} x_ {k}: S \ subseteq N \ setminus \ {j \ }, i \ sağda \},}$

maksimum miktar, cihazın i oyuncu işbirliği olmadan kazanabilir j büyük koalisyonundan çekilerek N ödeme vektörü altında X diğer oyuncu varsayarak i s çekme koalisyonu altında payoffs ile karşılanır x . Maksimum fazlalık, bir oyuncunun diğerine karşı pazarlık gücünü ölçmenin bir yoludur. Çekirdek ait setidir ithamlarda x o tatmin ${\ displaystyle v}$

• ${\ displaystyle (s_ {ij} ^ {v} (x) -s_ {ji} ^ {v} (x)) \ kere (x_ {j} -v (j)) \ leq 0}$ , ve
• ${\ displaystyle (s_ {ji} ^ {v} (x) -s_ {ij} ^ {v} (x)) \ kere (x_ {i} -v (i)) \ leq 0}$

her oyuncu çifti için i ve j . Sezgisel olarak, i oyuncusu , x if ithafına göre j oyuncusundan daha fazla pazarlık gücüne sahiptir , ancak j oyuncusu , bu ödülü kendi başına elde edebildiği için, i oyuncusunun tehditlerine karşı bağışıktır . Çekirdek, hiçbir oyuncunun bir başkası üzerinde bu pazarlık gücüne sahip olmadığı tüm ithamları içerir . Bu çözüm kavramı ilk olarak ( Davis & Maschler 1965 ) 'de tanıtıldı . ${\ displaystyle s_ {ij} ^ {v} (x)> s_ {ji} ^ {v} (x)}$${\ displaystyle x_ {j} = v (j)}$

Çekirdekçik

Izin bir oyun ve izin bir ödeme vektör olsun. Fazla arasında koalisyon miktar ; diğer bir deyişle, koalisyondaki oyuncuların büyük koalisyondan geri ödeme altında çekilir ve bunun yerine karşılığını alırlarsa elde edecekleri kazançtır . ${\ displaystyle v: 2 ^ {N} \ - \ mathbb {R}}$${\ displaystyle x \ in \ mathbb {R} ^ {N}}$${\ displaystyle x}$${\ displaystyle S \ subseteq N}$${\ displaystyle v (S) - \ toplamı _ {i \ S} x_ {i}}$${\ displaystyle S}$${\ displaystyle N}$${\ displaystyle x}$${\ displaystyle v (S)}$

Şimdi , artmayan düzende düzenlenmiş fazlalıkların vektörü olalım . Başka bir deyişle ,. Uyarı olan iç kısım arasında bir ön-isnat ve, ancak ve ancak, eğer . Nükleolü tanımlamak için, vektörlerin sözlükbilimsel sıralanmasını şu şekilde ele alıyoruz : İki getiri vektörü için, bir indeks için ve sahip olduğumuzdan sözlükbilimsel olarak daha küçük diyoruz . (Bu taklit Sıralamanın bir sözlükte kelime düzenlemek için kullanılan, çünkü sipariş lexicographic denir.) Nükleolus ait sözlük sırasında minimal töhmet bu siparişlerin sebep. Bu çözüm kavramı ilk olarak ( Schmeidler 1969 ) 'da tanıtıldı . ${\ displaystyle \ theta (x) \ içinde \ mathbb {R} ^ {2 ^ {N}}}$${\ displaystyle x}$${\ displaystyle \ theta _ {i} (x) \ geq \ theta _ {j} (x), \ forall ~ i <j}$${\ displaystyle x}$${\ displaystyle v}$${\ displaystyle \ theta _ {1} (x) \ leq 0}$${\ displaystyle \ mathbb {R} ^ {2 ^ {N}}}$${\ displaystyle x, y}$${\ displaystyle \ theta (x)}$${\ displaystyle \ theta (y)}$${\ displaystyle k}$${\ displaystyle \ theta _ {i} (x) = \ theta _ {i} (y), \ forall ~ i <k}$${\ displaystyle \ theta _ {k} (x) <\ theta _ {k} (y)}$${\ displaystyle v}$

Nükleolusun tanımı soyut görünse de ( Maschler, Peleg & Shapley 1979 ) daha sezgisel bir tanım verdi: En az çekirdek ile başlayarak, eşitsizliğin sağ tarafının tanımında daha fazla olamayacağı koalisyonları kaydedin. seti boşaltmadan küçültülür. Kalan koalisyonlar için sağ tarafı, seti boşaltmadan azaltılamayana kadar azaltmaya devam edin. Eşitsizliklerin eşit olduğu yeni koalisyonları kaydedin; kalan koalisyonların sağ tarafını azaltmaya devam edin ve bu süreci tüm koalisyonlar kaydedilene kadar gerektiği kadar tekrarlayın. Ortaya çıkan getiri vektörü çekirdekçiktir. ${\ displaystyle C _ {\ varepsilon} (v)}$

Özellikleri

• Tanım açıkça belirtmese de, nükleolus her zaman benzersizdir. ( Kanıt için ( Driessen 1988 ) Bölüm II.7'ye bakınız .)
• Çekirdek boş değilse, çekirdek çekirdek içindedir.
• Nükleolus her zaman çekirdekte bulunur ve çekirdek pazarlık setinde yer aldığından, her zaman pazarlık setindedir ( ayrıntılar için bkz. ( Driessen 1988 ).)

Konveks işbirlikçi oyunlar

Shapley tarafından ( Shapley 1971 ) tanıtılan , konveks işbirlikli oyunlar, bazı oyunların "kartopu" sezgisel özelliğini yakalar. Spesifik olarak, bir oyun konveks karakteristik fonksiyonu halinde olan supermodular : ${\ displaystyle v}$

${\ Displaystyle v (S \ fincan T) + v (S \ cap T) \ geq v (S) + v (T), \ forall ~ S, T \ subseteq N.}$

Bu (örneğin, Bölüm V.1 (bakınız gösterilebilir 1988 Driessen bu)) supermodularity arasında eşdeğerdir ${\ displaystyle v}$

${\ Displaystyle v (S \ fincan \ {i \}) - v (S) \ leq v (T \ fincan \ {i \}) - v (T), \ forall ~ S \ subseteq T \ subseteq N \ setminus \ {i \}, \ forall ~ i \ N içinde;}$

yani, "koalisyon büyüdükçe bir koalisyona katılma teşvikleri artar" ( Shapley 1971 ), bu da yukarıda bahsedilen kartopu etkisine yol açar. Maliyet oyunları için eşitsizlikler tersine çevrilir, böylece karakteristik fonksiyon alt modüler ise maliyet oyununun dışbükey olduğunu söyleyebiliriz .

Özellikleri

Konveks işbirlikli oyunların birçok güzel özelliği vardır:

• Süpermodülerlik, önemsiz bir şekilde süper katkı anlamına gelir .
• Dışbükey oyunlar tamamen dengelidir : Dışbükey bir oyunun özü boş değildir ve bir dışbükey oyunun herhangi bir alt oyunu dışbükey olduğundan, herhangi bir alt oyunun özü de boş değildir.
• Dışbükey bir oyunun çekirdeğiyle örtüşen benzersiz bir kararlı seti vardır .
• Shapley'in değeri dışbükey oyunun kendi ağırlık merkezi çekirdek .
• Bir uç nokta arasında (tepe) göbek kullanılarak polinom zamanda bulunabilir Algoritma : Izin bir olmak permütasyon oyuncu ve izin oyuncu grubu sıralı olması ile de herhangi bir için olan . Daha sonra ödeme ile tanımlanan bir tepe olan iç kısım arasında . Çekirdeğin herhangi bir tepe noktası, uygun bir permütasyon seçilerek bu şekilde inşa edilebilir . ${\ displaystyle \ pi: N \ - N}$${\ displaystyle S_ {i} = \ {j \ in N: \ pi (j) \ leq i \}}$${\ displaystyle 1}$${\ displaystyle i}$${\ displaystyle \ pi}$${\ displaystyle i = 0, \ ldots, n}$${\ displaystyle S_ {0} = \ boşküme}$${\ displaystyle x \ in \ mathbb {R} ^ {N}}$${\ displaystyle x_ {i} = v (S _ {\ pi (i)}) - v (S _ {\ pi (i) -1}), \ forall ~ i \ N'de}$${\ displaystyle v}$ ${\ displaystyle \ pi}$

Kombinatoryal optimizasyonla benzerlikler ve farklılıklar

Alt modüler ve süpermodüler küme fonksiyonları, kombinatoryal optimizasyonda da incelenmiştir . ( Shapley 1971 ) ' deki sonuçların çoğu, submodüler fonksiyonların ilk olarak matroidlerin genelleştirmeleri olarak sunulduğu ( Edmonds 1970 )' de benzerlere sahiptir . Bu bağlamda, dışbükey maliyet oyununun özüne temel çokyüzlü denir , çünkü öğeleri matroidlerin temel özelliklerini genelleştirir .

Bununla birlikte, optimizasyon topluluğu genellikle alt modüler fonksiyonları dışbükey fonksiyonların ayrık analogları olarak kabul eder ( Lovász 1983 ), çünkü her iki tip fonksiyonun en aza indirilmesi hesaplama açısından izlenebilirdir. Ne yazık ki bu, Shapley'in orijinal süpermodüler işlev tanımıyla "dışbükey" doğrudan çelişiyor .

Ayrıca bakınız

• Konsensüs karar verme
• Koordinasyon oyunu
• Hane içi pazarlık
• Hedonik oyun
• Doğrusal üretim oyunu

Referanslar

daha fazla okuma

• Bilbao, Jesús Mario (2000), Kombinatoryal Yapılarda İşbirlikçi Oyunlar , Kluwer Academic Publishers, ISBN   9781461543930

• Davis, M .; Maschler, M. (1965), "Bir kooperatif oyunun çekirdeği", Naval Research Logistics Quarterly , 12 (3): 223–259, doi : 10.1002 / nav.3800120303

• Driessen, Theo (1988), Kooperatif Oyunlar, Çözümler ve Uygulamalar , Kluwer Academic Publishers, ISBN   9789401577878

• Edmonds, Jack (1970), "Alt modüler fonksiyonlar, matroidler ve belirli çokyüzlüler", Guy, R .; Hanani, H .; Sauer, N .; Schönheim, J. (editörler), Combinatorial Structures and Their Applications , New York: Gordon and Breach, pp. 69–87

• Lovász, László (1983), "Alt modüler fonksiyonlar ve dışbükeylik", Bachem, A .; Grötschel, M .; Korte, B. (editörler), Mathematical Programming — The State of the Art , Berlin: Springer, s. 235–257

• Leyton-Brown Kevin; Shoham, Yoav (2008), Temel Oyun Teorisi: Kısa, Çok Disiplinli Giriş , San Rafael, CA: Morgan & Claypool Publishers, ISBN   978-1-59829-593-1 . 88 sayfalık matematiksel bir giriş; 8. Bölüme bakın . Birçok üniversitede ücretsiz çevrimiçi (abonelik gerekir) .

• Lucas, William F. (1969), "Bir Oyunun Çözümü Olmayacağının Kanıtı", Amerikan Matematik Derneği İşlemleri , 136 : 219–229, doi : 10.2307 / 1994798 , JSTOR   1994798 .

• Lucas, William F. (1992) 'de "von Neumann-Morgenstern Durağan Setleri", aumann Robert J. ; Hart, Sergiu (ed.), Handbook of Game Theory, Volume I , Amsterdam: Elsevier , pp. 543–590

• Luce, RD ve Raiffa, H. (1957) Games and Decisions: An Introduction and Critical Survey , Wiley & Sons. (bkz.Bölüm 8).
• Maschler, M .; Peleg, B .; Shapley, Lloyd S. (1979), "Çekirdeğin geometrik özellikleri, çekirdekçik ve ilgili çözüm kavramları", Yöneylem Araştırması Matematiği , 4 (4): 303–338, doi : 10.1287 / moor.4.4.303

• Osborne, MJ ve Rubinstein, A. (1994) A Course in Game Theory , MIT Press (bkz. Bölüm 13,14,15)
• Moulin, Herve (1988), Axioms of Cooperative Decision Making (1. baskı), Cambridge: Cambridge University Press , ISBN   978-0-521-42458-5

• Owen Guillermo (1995), Oyun Teorisi (3. baskı), San Diego: Academic Press , ISBN   978-0-12-531151-9

• Schmeidler, D. (1969), "Karakteristik bir fonksiyon oyununun nükleolusu", SIAM Uygulamalı Matematik Dergisi , 17 (6): 1163–1170, doi : 10.1137 / 0117107 .

• Shapley, Lloyd S. (1953), " Kişilik oyunları için bir değer ", Kuhn, H .; Tucker, AW (editörler), Contributions to the Theory of Games II , Princeton, New Jersey: Princeton University Press, s. 307–317 ${\ displaystyle n}$

• Shapley, Lloyd S. (1971), "Konveks oyunların çekirdekleri", International Journal of Game Theory , 1 (1): 11–26, doi : 10.1007 / BF01753431 , S2CID   123385556

• Shapley, Lloyd S .; Shubik, M. (1966), "Dışbükey olmayan tercihlere sahip bir parasal ekonomide yarı çekirdekler", Econometrica , 34 (4): 805–827, doi : 10.2307 / 1910101 , JSTOR   1910101

• Shoham, Yoav; Leyton-Brown, Kevin (2009), Multiagent Systems: Algorithmic, Game-Theoretic ve Logical Foundations , New York: Cambridge University Press , ISBN   978-0-521-89943-7 . Hesaplamalı bir perspektiften kapsamlı bir referans; Bölüm 12'ye bakın . Ücretsiz çevrimiçi indirilebilir .

• von Neumann, John ; Morgenstern, Oskar (1944), "Oyunlar ve Ekonomik Davranış Teorisi" , Doğa , Princeton: Princeton University Press , 157 (3981): 172, Bibcode : 1946Natur.157..172R , doi : 10.1038 / 157172a0 , S2CID   29754824

• Yeung, David WK ve Leon A. Petrosyan. Kooperatif Stokastik Diferansiyel Oyunlar (Yöneylem Araştırması ve Finans Mühendisliğinde Springer Serisi), Springer, 2006. Ciltsiz - ISBN   978-1441920942 .
• Yeung, David WK ve Leon A. Petrosyan. Alt Oyun Tutarlı Ekonomik Optimizasyon: Gelişmiş İşbirlikçi Dinamik Oyun Analizi (Statik ve Dinamik Oyun Teorisi: Temeller ve Uygulamalar), Birkhäuser Boston; 2012. ISBN   978-0817682613

Dış bağlantılar

• "Cooperative game" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]