Oyun Teorisi Problem Set1.doc

Oyun Teorisi

Güz 2007 Problem Set 1

1. 2. Oyuncu s22 s23

1 2

s 1. Oyuncu

s24

s11

4, 2

3, 4

1, 2

7, 2

2 1

3, 8

2, 4

0, 2

5, 5

3 1

5, 1

5, 3

0, 1

5, 0

s s

matrisi iki kişilik bir oyun belirlemektedir. “Kesinlikle Mahkum Stratejilerin Elenmesi” yöntemi ile bu oyunun dengesini bulunuz. Not:

Kesinlikle Mahkum Stratejilerin Elenmesi yöntemi işe yaramıyor ise Nash Dengesine

bakılabilir. Oyunda Kesinlikle Mahkum Stratejilerin Elenmesi yöntemi ile denge varsa bu aynı zamanda bir Nash dengesidir. Tersi geçerli değildir. Çözüm: Bu matris oyunundaki stratejiler arasındaki baskınlıkları inceler isek; "s2j �S 2 için H1 ( s11 , s2j ) �H1 ( s12 , s2j ) olduğundan yani matrisin birinci satırındaki ilk bileşenler 1 2 ikinci satırındaki ilk bileşenlerden büyük-eşit olduğundan, 1. Oyuncunun s1 stratejisi s1 1 2 1 2 stratejisini basar ( s1 �s1 ). 1. Oyuncu hiç bir zaman s1 olduğu yerde s1 yi oynamayacağından 2 1 3 basılan s1 stratejisini oyundan eler. s1 ve s1 stratejileri arasında böyle bir baskınlık tanımlamak

mümkün değildir. Buna göre yeni matris yapımız aşağıdaki şekilde değişecektir.

2. Oyuncu 1

1. Oyuncu

s12

s22

s23

s24

s11

4, 2

3, 4

1, 2

7, 2

3 1

5, 1

5, 3

0, 1

5, 0

s

i i 2 i 1 Benzer şekilde "s1 �S1 için H 2 ( s1 , s2 ) �H 2 ( s1 , s2 ) , yani matrisin ikinci sütunundaki ikinci 2 bileşenler, birinci sütunundaki ikinci bileşenlerden büyük-eşittir. Buna göre, 2. Oyuncunun s2 1 2 1 i 2 i 3 2 3 stratejisi s2 stratejisini basar ( s2 �s2 ). Aynı şekilde H 2 ( s1 , s2 ) �H 2 ( s1 , s2 ) dür, yani ( s2 �s2 ) i 2 i 4 2 4 1 3 dür ve yine H 2 ( s1 , s2 ) �H 2 ( s1 , s2 ) olduğundan ( s2 �s2 ) dür. Böylece 2. Oyuncu basılan s2 , s2 4 ve s2 stratejilerini oyundan eler, yani bu stratejilere karşılık gelen matrisin birinci, üçüncü ve

dördüncü sütunları göz önüne alınmaz. Şu halde, yeni matrisimiz aşağıdaki şekilde değişir. 2. Oyuncu s22 1. Oyuncu

s11

3, 4

3 1

5, 3

s

Örneğimizin çözümüne kaldığımız yerden devam eder isek; s22 için H1 ( s13 , s22 ) �H1 ( s11 , s22 ) olduğundan yani matrisin birinci satırındaki ilk bileşen, ikinci 3 1 3 1 satırındaki ilk bileşenden büyük-eşit olduğundan ( s1 �s1 ), 1. oyuncu s1 stratejisini s1 3 stratejisine her zaman için tercih eder, çünkü s1 stratejisi daha fazla kazandırmaktadır. Böylece

son olarak oyun matrisi 2. Oyuncu s22 1. Oyuncu

s13

5, 3

yapısına indirgenir. İlk elemeyi 2. Oyuncu yapsaydı sonuç yine değişmeyecekti, buradan da anlaşılacağı gibi oyuncuların oynama sırasının, oyunun sonucu açısından bir önemi yoktur. 2

3 2 Sonuç olarak, hiç bir oyuncunun stratejisini değiştirmeyeceği s= ( s1 , s2 ) durumu oyunun denge

durumudur. Bu durumda oyuncuların elde edeceği kazançlar H1 ( B, R) H1 ( s) = 5, H 2 ( s ) =3 dir. 2.

A ve B gibi iki uçak şirketi Ankara – İstanbul arasında faaliyette bulunmaktadır. Her iki

şirketin amacı da mümkün olduğu kadar çok yolcu taşımaktır. Yolcu sayısını arttırmak isteyen şirketlerin aşağıda belirttiğimiz şekilde hareket edebileceklerini farz edelim. A ve B şirketlerinin stratejileri aşağıdaki gibidir: A1, B1: Müşteri çekmek için özel hiçbir şey yapmamak A2, B2: Uçuş süresince film göstermek. A3, B3: Günlük gazetelerde reklam yapmak. A ve B şirketlerine ait kazançları aşağıdaki matristeki gibi gösterebiliriz.

A Şirketi

A1

B1 0, 0

B Şirketi B2 100, 80

B3 200, 100

A2

100, 50

50, 0

50, 100

A3

350, 150

125, 100

350, 200

“Kesinlikle Mahkum Stratejilerin Elenmesi” yöntemi ile bu oyunun dengesini bulunuz. Çözüm: Oyuna A Şirketinin başladığını düşünelim. A Şirketi için: A3 > A1 olduğundan A1 elenir. A3 > A2 olduğundan A2 elenir. A şirketinin optimal stratejisi A3’dür.

3

A Şirketi kendisi için optimal stratejiye ulaşmıştır. Bu aşamadan sonra B Şirketi oyuna devam eder. B Şirketi için: B3 > B1 olduğundan B1 elenir. B3 > B2olduğundan B2 elenir. B şirketinin optimal stratejisi B3’dür. Sonuç olarak hiç bir şirket stratejisini değiştirmeyeceği için oyunun denge durumu: (A 3, B3) durumudur. Bu durumda A ve B şirketinin elde edeceği kazançları ise aşağıdaki gibi gösterebiliriz: H A (A3, B3) = 350 , H B (A3, B3) = 200 Bu sonuçlardan da anlaşılacağı gibi oyunun galibi A şirketidir. Hiç bir oyuncu rakibi değiştirmedikçe stratejisini değiştirmekle kazancını arttıramaz. 3.

1. Oyuncu

T M B

L 3,3 2,4 1,5

2. Oyuncu C 2,1 2,4 0,2

R 3,1 0,4 6,5

matrisi iki kişilik bir oyun belirlemektedir. Bu matris oyununun Nash dengesini bulunuz. Not:

Yukarıdaki matris oyununa bakıldığında, Kesinlikle Mahkum Stratejilerin Elenmesi

yöntemiyle bir dengeye ulaşılamadığı açıkça görülmektedir.

Çözüm:

4

1. Oyuncunun en iyi cevap fonksiyonunu bulmak için, her sütun (2. Oyuncunun strateji seçimi) incelenecek ve en iyi satır bulunacaktır. Aşağıdaki matriste 1. Oyuncunun en iyi cevap fonksiyonunun altı çizilidir.

1. Oyuncu

2. Oyuncu C 2,1 2,4 0,2

L 3,3 2,4 1,5

T M B

R 3,1 0,4 6,5

Görüldüğü gibi 2. Oyuncunun C stratejisine 1. Oyuncu 2 adet strateji ile cevap vermektedir. Aynı yöntem ile 2. Oyuncunun en iyi cevapları bulunabilir. Her satırda (1. Oyuncunun seçimi) en iyi cevapları gösterirsek matris,

1. Oyuncu

2. Oyuncu C 2,1 2,4 0,2

L 3,3 2,4 1,5

T M B

R 3,1 0,4 6,5

şeklini alır. Bu oyunda üç adet Nash dengesi vardır. Bunlar (T, L), (M, C) ve (B, R) dir. Her bir denge durumu için oyuncuların kazançlarını aşağıdaki gibi göstere biliriz. (T, L) denge durumunda: H1 (T , L) = 3, H 2 (T , L ) = 3 (M, C) denge durumunda: H1 ( M , C ) = 2, H 2 ( M , C ) = 4 (B, R) denge durumunda: H1 ( B, R ) = 6, H 2 ( B, R) = 5 4.

Mahkumlar Çıkmazı:

1.Oyuncu

2. Oyuncu L R 5,5 -1,7 7,-1 1,1

T B

5

Oyunun Nash Dengesini bulunuz. Karma Nash Dengesi varmı araştırınız. Çözüm: (Pure) Nash Dengesi = (1, 1), Bu oyunda Karma Nash Dengesi yoktur. (bunun gösterimini yapmama gerek varmı?) 5.

Korkak Tavuk:

1.Oyuncu

2. Oyuncu L R 4, 4 1, 6 6, 1 -3, -3

T B

Oyunun Nash Dengesini bulunuz. Karma Nash Dengesi varmı araştırınız. Çözüm: (Pure) Nash Dengeleri = {(6, 1), (1, 6)} Karma Nash Dengesi varlığı araştırılırsa; Nash Dengesi = {(p*,q*): (0, 1), (1, 0), (1/2, 1/2 )} sonucuna ulaşılır. 6.

Cinsiyetler Savaşı:

1.Oyuncu

2. Oyuncu Opera Maç 3, 1 0, 0 0, 0 1, 3

Opera Maç

Oyunun Nash Dengesini bulunuz. Karma Nash Dengesi varmı araştırınız. Çözüm: (Pure) Nash Dengeleri = {(3, 1), (1, 3)} 6

Karma Nash Dengesi varlığı araştırılırsa; Nash Dengesi = {(p*,q*): (0, 0), (1, 1), (3/4, 1/4 )} sonucuna ulaşılır. 7.

Birisi başkan olmak üzere 3 kişi { a, b, c} kümesinden bir proje seçecektir. Belli bir proje

için oylamada çoğunluk sağlanır ise o proje uygulamaya konulacaktır. Çoğunluk sağlanamaz ise 1 oyuncusunun (başkanın) önerdiği proje uygulanacaktır. Proje uygulandığında oyuncuların beklediği faydaların H1(a) = 3,

H2(a) = 2,

H3(a) = 1

H1(b) = 2,

H2(b) = 1,

H3(b) = 3

H1(c) = 1,

H2(c) = 3,

H3(c) = 2

Şeklinde olduğunu kabul edelim. Hangi proje kabul edilecektir. Oyun matrislerini çizerek, oyunun denge durumunu bulunuz. Çözüm: Bu tür oyunlarda oyunculardan biri oyun matrisini seçer diğer iki oyuncu oyunu oynar. Oyuncular:

I = {1, 2, 3}

Stratejiler:

a, b ve c projelerine oy verme stratejileri sıarsıyla A, B ve C olsun.

1. Oyuncunun Strateji Kümesi:

S1={A, B, C}

2. Oyuncunun Strateji Kümesi:

S2={A, B, C}

3. Oyuncunun Strateji Kümesi:

S3={A, B, C}

S = S1 �S2 �S3 �

|S| = 3 �3 �3 = 27 durum var.

1. Matris:

7

2. Oyuncu

A B C

A

3. Oyuncu B

C

a 3, 2, 1 a 3, 2, 1 a 3, 2, 1

a 3, 2, 1 b 2, 1, 3 a 3, 2, 1

a 3, 2, 1 a 3, 2, 1 c 1, 2, 3

1. Oyuncu: A 2. Matris:

2. Oyuncu

A B C

A

3. Oyuncu B

C

a 3, 2, 1 b 2, 1, 3 b 2, 1, 3

b 2, 1, 3 b 2, 1, 3 b 2, 1, 3

b 2, 1, 3 b 2, 1, 3 c 1, 2, 3

1. Oyuncu: B 3. Matris:

2. Oyuncu

A B C

A

3. Oyuncu B

C

a 3, 2, 1 c 1, 2, 3 c 1, 2, 3

c 1, 2, 3 b 2, 1, 3 c 1, 2, 3

c 1, 2, 3 c 1, 2, 3 c 1, 2, 3

1. Oyuncu: C 1. Oyuncu İçin: A > B � B elenir. A > C � C elenir. 1. Oyuncunun Optimal Stratejisi A’dır. 2. Oyuncu İçin: A > B � B elenir. C > A � A elenir. 2. Oyuncunun Optimal Stratejisi C’dır. 3. Oyuncu İçin: C > B � B elenir. C > A � A elenir. 1. Oyuncunun Optimal Stratejisi C’dır.

8

Bu Matris Oyununun Nash Dengesi : (A, C, C) � Oyun sonucunda C projesi seçilir. Oyuncuların kazançları sırasıyla : (1, 2, 3) ‘dür. 8.

Aşağıdaki matris oyununun dengesini bulunuz.

1. Oyuncu Not:

2. Oyuncu L R 3, 1 2, 4 2, 2 3, 1

T B

İncelendiğinde rahatça görülebilirki, aşağıdaki matris oyununun saf stratejisi Nash

dengesi yoktur. Yani, karma stratejili oyundur. Çözüm: Önce her oyuncunun stratejisine olasılık atayalım.

1. Oyuncu

p 1-p

T B

2. Oyuncu q 1-q L R 3, 1 2, 4 2, 2 3, 1

Buradan beklenen faydaları aşağıdaki gibi gösterebiliriz: E (p 1 ) = 3pq + 1p(1-p) + 2(1-p)q + 3(1-p)(1-q) ve E (p 2 ) = pq + 4p(1-q) + 2(1-p)q + (1-p)(1-q) Beklenen fayda fonksiyonlarının birinci türevini alarak maksimizasyon problemi çözülecektir:

9

� E (p 1 ) = 2q-1 = 0 � p ve � E (p 2 ) = 1- 4p = 0 � q Bu eşitliklerden hareketle, p* = 1/4 ve q* = 1/2 olacaktır.

Karma oyunlarda oyunun denge durumuna ulaşmak söz konusu değildir. Böyle oyunlarda ancak bir oyuncunun hangi stratejisini hangi olasılık ile oynayacağı bulunabilir. Bulunan sonuçlardan da anlaşılacağı gibi 1. Oyuncunun T stratejisini oynama olasılığı 1/4, B stratejisini oynama olasılığı 3/4‘dür. Aynı şekilde 2. Oyuncunun stratejilerini inceler isek; 2. Oyuncunun L stratejisini oynama olasılığı 1/2, R stratejisini oynama olasılığı 1/2’dir.

9.

Aşağıdaki matris oyununun Karma Strateji dengesini bulunuz.

1. Oyuncu

2. Oyuncu L R 3, 1 2, 4 2, 2 3, 1

T B

Çözüm: p* =

10.

d -c , a-b-c+d

q* =

D-B A- B -C + D

Consider the two – player game in which each of two players states a number in the set

{1, ..., M}. If the two players state same number, then player 1 pays 1 dollar to player 2; otherwise player 2 pays 1 dollar to player 1. For M =2, construct the payoff matrix and find the Nash equilibria of the game (where payoffs are equal to dollars).

10

Çözüm: Nash Dengesi = {(p*,q*) | (1/2, 1/2 )}

11