EKMA4413 – Riset Op-erasiProgram Studi Manaje-menOleh: M. Mujiya Ulkhaq

Kebun Raya Bogor, Bogor, Jawa Barat

Modul 9

Seoul, 27th of April 2014

2

Tinjauan Umum Modul 9

Secara umum, Modul 9 akan membahas tentang game theory (teori permainan).

Modul 9 terdiri dari dua kegiatan belajar:• Kegiatan Belajar 1 – Dasar-dasar Game Theory;• Kegiatan Belajar 2 – Pengambilan Kesimpulan dalam Keadaan yang Belum Sempurna.

Setelah mempelajari Modul 9, diharapkan dapat memahami pemecahan masalah dalam keadaan persaingan sehingga strategi untuk menghadapi lawan dilakukan dengan dasar dan alasan yang kuat.

Secara khusus, setelah mempelajari Modul 9, diharapkan mengerti konsep untuk menghadapi persaingan dalam keadaan:• Mengerti keadaan/strategi lawan;• Tidak mengerti keadaan lawan;• Dalam keadaan tidak pasti.

3

Dasar-dasar Game Theory

Game theory merupakan teori matematika yang digunakan dalam keadaan persaingan, di mana ada duaatau lebih pemain yang sedang bersaing.

Asumsi dalam game theory: pemain mengetahui semua strategy lawan dan hasilnya, serta semua pemainbertindak secara rasional.

Berdasarkan jumlah pemain, game theory dibagi dua: two persons dan n-persons. Namun dalam Modul ini hanya dibahas two persons.

Berdasarkan keadaan persaingan, game theory dibagi dua: zero sum games dan non-zero sum games.

Zero sum games terjadi apabila kondisi akhir adalah pemain satu menang dan lainnya kalah.

Non-zero sum games terjadi apabila dalam kondisi akhir tidak ada pemain yang menang dan kalah, hanya probabilitas menang, kalah, dan strategy yang diambil yang diketahui.

Contoh matriks payoff:

Pemain KeduaStrategi A Strategi B

Pemain Pertama

Startegi 1 100 -100

Strategi 2 -100 100

4

Strategi DominasiCara penyelesaian game theory dengan menggunakan startegi dominasi adalah dengan menghilangkanstrategi yang dianggap “kurang baik” relatif terhadap strategi lain. Dengan kata lain, strategi satu men-dominasi strategi yang lain. Strategi dominasi sangat mudah dalam implementasi namun hanya akan bekerja bila ada strategi yang dianggap mendominasi strategi yang lain. Apabila tidak ada startegi yangdianggap mendominasi, maka pemecahan masalah akan stuck atau berhenti di tengah jalan.

Contoh:

• Permainan dimulai dari Pemain 1 (pemain baris), dilanjutkan dengan Pemain 2 (kolom), kemudian kembali ke Pemain 1, begitu seterusnya.

• Untuk Pemain 1, pilih strategi yang memberikan matriks payoff dengan nilai besar, namun untuk Pemain 2, pilih strategi yang memberikan matriks payoff dengan nilai kecil.

Perusahaan BStrategi 1 Strategi 2 Strategi 3

Perusahaan A

Startegi 1 1.000 2.000 4.000

Strategi 2 1.000 0 5.000

Startegi 3 0 1.000 –1.000

5

Strategi Dominasi1. Iterasi 1: Pemain 1 “bermain”

Strategi 3 didominasi Strategi 1, (1.000>0; 2.000>1.000; 4.000>–1.000). Maka, “hilangkan” Strategi 3

2. Iterasi 2: Pemain 2 “bermain”

Strategi 3 didominasi Strategi 1 dan 2 (1.000<4.000 dan 1.000<4.000; 1.000<5.000 dan 0<5.000). Maka, “hilangkan” Startegi 3.

Perusahaan BStrategi 1 Strategi 2 Strategi 3

Perusahaan A

Startegi 1 1.000 2.000 4.000

Strategi 2 1.000 0 5.000

Startegi 3 0 1.000 –1.000

Perusahaan BStrategi 1 Strategi 2 Strategi 3

Perusahaan A

Startegi 1 1.000 2.000 4.000

Strategi 2 1.000 0 5.000

Startegi 3 0 1.000 –1.000

6

Strategi Dominasi3. Iterasi 3: Pemain 1 “bermain”

Strategi 2 didominasi Strategi 1, (1.000=1.000; 2000>0). Maka, “hilangkan” Strategi 2.

4. Iterasi 4: Pemain 2 “bermain”

Strategi 2 didominasi Strategi 1 (1.000<2.000). Maka, “hilangkan” Startegi 2.

Perusahaan BStrategi 1 Strategi 2 Strategi 3

Perusahaan A

Startegi 1 1.000 2.000 4.000

Strategi 2 1.000 0 5.000

Startegi 3 0 1.000 –1.000

Perusahaan BStrategi 1 Strategi 2 Strategi 3

Perusahaan A

Startegi 1 1.000 2.000 4.000

Strategi 2 1.000 0 5.000

Startegi 3 0 1.000 –1.000

7

Strategi DominasiHasil akhir:

Pada akhirnya, Perusahaan A akan memenangi kompetisi dengan Perusahaan B.

Strategi yang dipilih Perusahaan A adalah Strategi 1: Memberi potongan harga, di mana Perusahaan B juga memilih strategi yang sama.

Keuntungan yang diperoleh adalah Perusahaan A akan memperoleh tambahan konsumen 1.000 orang dari Perusahaan B.

Permainan ini disebut two person zero sum games.

*Permainan dikatakan berimbang apabila keuntungan yang diperoleh kedua pemain adalah 0.

Perusahaan BStrategi 1 Strategi 2 Strategi 3

Perusahaan A

Startegi 1 1.000 2.000 4.000

Strategi 2 1.000 0 5.000

Startegi 3 0 1.000 –1.000

8

Strategi Minimax-Max-imin

Bagaimana apabila tidak ada strategi yang mendominasi?

Contoh:

Dilihat dari matriks payoff di atas, tidak ada strategi yang mendominasi ataupun didominasi, baik untuk Perusahaan X maupun Perusahaan Y. Alih-alih menggunakan strategi dominasi, cara penyelesaian dengan startegi minimax-maximin bisa digunakan untuk menyelesaikan.• Untuk Pemain 1 (pemain baris), hitung nilai maksimal dari matriks payoff per kolom dari strategi

lawan. Kemudian pilih minimaks (nilai yang paling minimal dari nilai maksimal).• Untuk Pemain 2 (pemain kolom), hitung nilai minimal dari matriks payoff per baris dari strategi lawan.

Kemudian pilih maksimin (nilai yang paling maksimal dari nilai minimal).• Saddle point (hasil akhir) terjadi apabila nilai minimaks = maksimin.

Perusahaan YStrategi 1 Strategi 2 Strategi 3

Perusahaan X

Strategi 1 –3.000 –2.000 6.000

Strategi 2 2.000 0 2.000

Strategi 3 5.000 –2.000 –4.000

9

Strategi Minimax-Max-imin

Perusahaan YStrategi 1 Strategi 2 Strategi 3 Nilai Minimal

Perusahaan X

Startegi 1 –3.000 –2.000 6.000 –3.000

Strategi 2 2.000 0 2.000 0

Startegi 3 5.000 –2.000 –4.000 –4.000

Nilai Maksimal 5.000 0 6.000

Maksimin

Minimaks

Terlihat kalau Nilai Minimaks = Maksimin dan saddle point adalah 0.

Hasil akhir berarti kedua permainan berimbang

10

Mixed StrategyBagaimana apabila suatu permainan tidak memiliki saddle point (Minimaks ≠ Maksimin)?

Contoh:

Dilihat dari matriks payoff di atas, Nilai Minimaks tidak sama dengan Nilai Maksimin, maka permainan tidak mempunyai saddle point, dan dengan kata lain strategi minimax-maximin tidak dapat digunakan. Cara penyelesaiannya adalah dengan menggunakan mixed strategy (strategi campuran).

Perusahaan YStrategi 1 Strategi 2 Strategi 3 Nilai Minimal

Perusahaan X

Startegi 1 0 –2.000 2.000 –2.000

Strategi 2 5.000 4.000 –3.000 –3.000

Startegi 3 2.000 3.000 –4.000 –4.000

Nilai Maksimal 5.000 4.000 2.000

Maksimin

Minimaks

11

Mixed StrategyDalam menggunakan mixed strategy, digunakan konsep expected payoff. Nilai expected payoff dicari den-gan mengalikan probabilitas terjadinya suatu strategi dengan nilai pay-off nya. Probabilitas ini menyangkut terjadinya terjadinya strategi pemain satu dan pemain dua, sehingga disebut strategi campuran.

Probabilitas dipilih Strategi 1 oleh Pemain 1 = X1

Probabilitas dipilih Strategi 2 oleh Pemain 1 = X2

Probabilitas dipilih Strategi m oleh Pemain 1 = 1 – (X1 + X2 + … + Xm-1)

Probabilitas dipilih Strategi 1 oleh Pemain 2 = Y1

Probabilitas dipilih Strategi 2 oleh Pemain 2 = Y2

Probabilitas dipilih Strategi n oleh Pemain 2 = 1 – (Y1 + Y2 + … + Ym-1)

Expected payoff Pemain 1 = ,

di mana pij merupakan nilai dari matriks payoff jika Pemain 1

menggunakan Strategi i dan Pemain 2 menggunakan Strategy j.

m

i

n

jjiij YXp

1 1

Ingat, karena probabilitas, maka jumlah dari semua probabilitas

untuk seorang Pemain = 1

12

Mixed Strategy

Asumsikan probabilitas Perusahaan X mengambil Strategi 1 (X1) = 0,5; X2 = 0,5; X3 = 0; dan

Probabilitas Perusahaan Y mengambil Strategi 1 (Y1) = 0,5; Y2 = 0,5; Y3 = 0.

Expected payoff Perusahaan X = 0(0,5)(0,5) – 2.000(0.5)(0.5) + 2.000(0.5)(0) +

5.000(0.5)(0.5) + 4.000(0.5)(0.5) – 3.000(0.5)(0) +

2.000(0)(0.5) + 3.000(0)(0.5) – 4.000(0)(0)

= 1.750

Perusahaan YStrategi 1 Strategi 2 Strategi 3 Nilai Minimal

Perusahaan X

Startegi 1 0 –2.000 2.000 –2.000

Strategi 2 5.000 4.000 –3.000 –3.000

Startegi 3 2.000 3.000 –4.000 –4.000

Nilai Maksimal 5.000 4.000 2.000

13

Metode GrafikMetode grafis bisa digunakan untuk menyelesaikan game theory apabila permainan tidak memiliki saddle point. Selain itu, ia juga bisa digunakan apabila asumsi probabilitas dalam menggunakan suatu strategi tidak diketahui. Namun, metode grafis (dalam dua dimensi) hanya bisa digunakan apabila salah satu pe-main hanya memiliki dua strategi. Namun begitu, ilustrasi visual dari metode grafik menjadikan metode ini mudah dipahami.

Contoh:

Expected payoff A bila B menempuh Strategi 1: a11X1 + a21(1–X 1) = (a11 – a21)X1 + a21

Expected payoff A bila B menempuh Strategi 2: a12X1 + a22(1–X 1) = (a12 – a22)X1 + a22

Expected payoff A bila B menempuh Strategi n: a1nX1 + a2n(1–X 1) = (a1n – a2n)X1 + a2n

BStrategi 1

(Y1)Strategi 2

(Y2)Strategi n

(Yn)A

Startegi 1 (X1) a11 a12 a1n

Strategi 2 (1 – X1) a21 a22 a2n

14

Metode Grafik

Expected payoff A bila B menempuh Strategi 1: (a11 – a21)X1 + a21 = (2 – 4)X1 + 4 = 4 – 2X1

Expected payoff A bila B menempuh Strategi 2: (a12 – a22)X1 + a22 = (2 – 3)X1 + 3 = 3 – X1

Expected payoff A bila B menempuh Strategi 3: (a13 – a23)X1 + a23 = (3 – 2)X1 + 2 = 2 + X1

Expected payoff A bila B menempuh Strategi 4: (a14 – a24)X1 + a24 = (1 – 6)X1 + 6 = 6 – 5X1

BStrategi 1 Strategi 2 Strategi 3 Strategi 4

A

Startegi 1 (X1) 2 2 3 1

Strategi 2 (1 – X1) 4 3 2 6

15

Metode GrafikIbaratkan semua expected payoff adalah persamaan garis dan gambar garis tersebut dalam koordinat.

Expected payoff A bila B menempuh Strategi 1: Y = 4 – 2X1

Expected payoff A bila B menempuh Strategi 2: Y = 3 – X1

Expected payoff A bila B menempuh Strategi 3: Y = 2 + X1

Expected payoff A bila B menempuh Strategi 4: Y = 6 – 5X1

Maximin ada di perpotongan garis 3 – X1 dan 2 + X1.

Mencari titik potong:

3 – X1 = 2 + X1

2X1 = 3 – 2

X1 = ½

X2 = 1 – X1 = ½

Expected Payoff = 3 – X1 = 3 – ½ = 2 ½

16

Metode GrafikSelanjutnya mencari Strategi yang optimal dan expected payoff untuk Pemain B:

Dari grafik terlihat kalau dalam menemukan titik minimax hanya melibatkan Strategi 2 dan 3. Maka hanya dua strategi ini yang dipakai:

Expected payoff B bila A menempuh Strategi 1: 2Y2 + 3(1–Y2) = 3 – Y2

Expected payoff B bila A menempuh Strategi 2: 3Y2 + 2(1–Y2) = 2 + Y2

Mencari titik potong: Expected Payoff = 3 – Y2 = 3 – ½ = 2 ½

3 – Y2 = 2 + Y2

2Y2 = 3 – 2

Y2 = ½

Y3 = 1 – Y2 = ½

BStrategi 2

(Y2)Strategi 3(1 – Y2)A

Startegi 1 2 3

Strategi 2 3 2

17

Metode Grafik

Hasil akhir dari permainan di atas adalah:

Strategi optimal untuk Pemain A:

Strategi 1 dengan probabilitas ½: X1 = ½

Strategi 2 dengan probabilitas ½: X2 = ½

Strategi optimal untuk Pemain B:

Strategi 1 dengan probabilitas ½: Y1 = 0

Strategi 2 dengan probabilitas ½: Y2 = ½

Strategi 1 dengan probabilitas ½: Y3 = ½

Strategi 2 dengan probabilitas ½: Y4 = 0

Expected Payoff = 2 ½

BStrategi 1 Strategi 2 Strategi 3 Strategi 4

A

Startegi 1 2 2 3 1

Strategi 2 4 3 2 6

EKMA4413 – Riset Op-erasiProgram Studi Manaje-menOleh: M. Mujiya Ulkhaq

Kebun Raya Bogor, Bogor, Jawa Barat

Modul 9

Terima Kasih

감사합니다

Sampai Bertemu Lagi

Seoul, 27th of April 2014