Teori Permainan (Game Theory)

Disusun oleh :

Prof. Ir.Sigit Nugroho, M.Sc. Ph.D. Universitas Bengkulu

smr

Program Doktor Ilmu Manajemen - Sigit Nugroho 72

Pay-off Matrix Two person zero sum game

mnmm

n

n

ppa

ppa

bb

...

............

...

...

1

1111

1

ai = tindakan yang diambil pemain pertama; bj =

tindakan yang diambil pemain kedua. pij merupakan

payoff akibat interaksi kedua pemain

Program Doktor Ilmu Manajemen - Sigit Nugroho 73

Strategi Permainan

Keputusan bermain baris (kolom) tertentu dengan

peluang 1 dan semua baris (kolom) yang lain dengan

peluang 0 disebut dengan strategi murni (pure

strategy) dari pemain pertama (kedua).

Setiap pemain tahu bahwa lawan main rasional dan

memiliki tujuan yang sama, yaitu memaksimumkan

payoff dari lawan, sehingga masing-masing memilih

keputusan dengan menggunakan kriteria minimax

konservatif.

Program Doktor Ilmu Manajemen - Sigit Nugroho 74

Maximin dan Minimax serta nilai permainan

)(minmax ij

jirs ppv

)(maxmin ijij

tu ppv

Strategi murni maximin

Strategi murni minimax

Jika nilai minimax sama dengan nilai maximin, maka

nilai ini disebut dengan titik pelana (saddle point),

dan strategi murni minimax dan maximinnya disebut

dengan strategi optimal.

vv

Program Doktor Ilmu Manajemen - Sigit Nugroho 75

Maximin dan Minimax Teladan

Min Baris

2 4 1 1

3 5 4 3 Maximin

Baris

Max

Kolom 3 5 4

Minimax

Kolom

Pemain 1

Pemain 2

Program Doktor Ilmu Manajemen - Sigit Nugroho 76

Strategi Campuran dan Harapan Payoffnya

m

i

x

x

x

X

...

...

1

Pemain pertama memutuskan untuk bermain dengan

strategi baris ke i dengan peluang xi (i = 1, 2, …, m)

dimana lebih dari satu xi lebih besar dari nol.

X adalah strategi campuran

pemain pertama

m

i

ix1

1

Program Doktor Ilmu Manajemen - Sigit Nugroho 77

Strategi Campuran dan Harapan Payoffnya

nj yyyY ......1

Pemain kedua memutuskan bermain dengan

menggunakan strategi kolom j dengan peluang yj

(dimana j = 1, 2, …, n) dimana lebih dari satu yj lebih

besar dari nol.

n

j

jy1

1

Y adalah strategi campuran pemain kedua

Program Doktor Ilmu Manajemen - Sigit Nugroho 78

Strategi Campuran dan Harapan Payoffnya

m

i

n

j

ijji pyxPayoffE1 1

)(

Program Doktor Ilmu Manajemen - Sigit Nugroho 79

Strategi Maximin Optimal Pemain pertama

*

*

*

1

*

...

...

m

i

x

x

x

X

m

i

n

j

ijji pyx1 1

*

Sebesar mungkin

Program Doktor Ilmu Manajemen - Sigit Nugroho 80

Strategi Minimax Optimal Pemain kedua

***

1

* ...... nj yyyY

m

i

n

j

ijji pyx1 1

*

Sekecil mungkin

Program Doktor Ilmu Manajemen - Sigit Nugroho 81

Akibatnya …

m

i

n

j

ijji Yvpyx1 1

*

m

i

n

j

ijji Xvpyx1 1

*

m

i

n

j

ijji vpyxPayoffE1 1

**)(

Program Doktor Ilmu Manajemen - Sigit Nugroho

82

Permainan 2 x 2

*

1

*

2

21122211

1222*

1

*

1

*

2

21122211

2122*

1

1

1

yypppp

ppy

xxpppp

ppx

Langkah 1 : Periksa adanya titik pelana dalam matriks

payoff. Jika sedikitnya ada satu titik pelana, maka

strategi minimax optimalnya adalah strategi murni. Jika

tak ada titik pelana lakukan langkah 2.

Langkah 2 : Strategi minimax optimal untuk pemain

pertama dan kedua adalah sebagai berikut

Langkah 3 : Menghitung nilai permainan

2

1

2

1

**

i j

ijji pyxv

Program Doktor Ilmu Manajemen - Sigit Nugroho 83

Teladan Permainan 2 x 2

23

41Pemain 1

Pemain 2

Tentukan strategi campuran dan nilai nya !

Program Doktor Ilmu Manajemen - Sigit Nugroho 84

Dominansi suatu usaha untuk mengurangi ukuran matriks payoff

Baris ke-i mendominasi baris ke-k dala

matriks payoff jika pij ≥ pkj untuk j = 1,2, …,

n.

Bila ini terjadi, baris ke-k dapat

dieliminasi dari proses perhitungan

Kolom ke-j mendominasi kolom ke-k dalam

matriks payoff pij ≥ pik untuk i = 1,2, …, m.

Bila ini terjadi, kolom ke-j dapat

dieliminasi dari proses perhitungan

Program Doktor Ilmu Manajemen - Sigit

Nugroho

85

Dominansi

2533

0412

4265

2453

2533

4265

2453

253

425

243

25

42

24

25

42

Program Doktor Ilmu Manajemen - Sigit Nugroho 86

Perluasan Dominansi

1;1

m

kii

i

mippn

kjj

ijjik ,...,2,1;1

njpp kj

m

kii

iji ,...,2,1;1

Perihal dominansi dapat diperluas pada kasus dimana

suatu baris dapat didominasi oleh kombinasi konvex

(convex combination) baris-baris yang lain.

Suatu kolom dapat didominasi oleh kombinasi konvex

(convex combination) kolom-kolom yang lain.

n

kjj

j

;1

1

Program Doktor Ilmu Manajemen - Sigit Nugroho 87

Solusi Permainan 2 x n

Pe

main 1

Pemain 2

y1 y2 … yn

x1 p11 p12 … p1n

1-x1 p21 p22 … p2n

Program Doktor Ilmu Manajemen - Sigit Nugroho 88

Solusi Permainan 2 x n

1. Periksa adanya titik pelana. Jika ada, maka

strategi minimax optimal adalah strategi murni.

Mainkan baris dan kolom titik pelana dengan

peluang 1. Titik pelana merupakan nilai

permainan. Jika tak ada titik pelana pergi ke

langkah 2.

2. Periksa dominansi kolom. Hilangkan kolom yang

mendominasi kolom2 lain termasuk dengan

menggunakan konsep kombinasi konvex. Hal ini

digunakan untuk mengurangi ukuran permainan

dan tak diperlukan dengan menggunakan metode

grafik

Program Doktor Ilmu Manajemen - Sigit Nugroho 89

Solusi Permainan 2 x n

3. Tuliskan kendala

x1p1j + (1-x1)p2j ≥ v untuk sejumlah j kolom yang

tidak tereliminasi pada langkah 2 atau

v – (p1j-p2j)x1 ≤ p2j

4. Tuliskan kendala pada langkah 3 dalam bentuk

v – (p1j-p2j)x1 = p2j

5. Plot persamaan-persamaan dalam langkah 4.

Persamaan2 ini akan membentuk batas atas

wilayah layak yang didiskripsikan oleh kendala

dalam langkah 3 untuk 0 ≤ x1 ≤ 1, jika v diplotkan

sebagai fungsi dari x1.