game theory
DESCRIPTION
operational researchTRANSCRIPT
FILM BEAUTIFUL MIND
Dalam film tersebut,John Nash menemukan idenya saat ia tertarik pada seorang gadis di café. Nash berpikir, kalau ada sejumlah laki-laki yang baku hantam satu sama lain untuk memperebutkan hati seorang gadis, bisa jadi kisah mereka akan berakhir di rumah sakit tanpa ada satu priapun yang mendapatkan si gadis. Oleh karenanya, menurut Nash masing-masing pria akan menjalankan strategi tertentu yang jitu untuk memikat si gadis. Si pria juga harus memperhatikan strategi pesaingnya. Seandainya pria lain sudah membawakan bunga, maka ia harus datang dengan pusiti atau musik. Lantas ketika ia datang dengan puisi, si pesaing pun akan mengatur strategi baru; mungkin datang dengan musik. Demikian seterusnya hinga masing-masing akan menemukan satu strategi yang ia anggap terbaik sebagai respon atas strategi yang dijalankan orang lain. Kondisi ini yang dalam teori ekonomi dikenal dengan keseimbangan Nash.
Teori permainan (game theory) adalah bagian dari ilmu pengetahuan yang berkaitan dengan
pembuatan keputusan pada saat dua pihak atau lebih berada dalam kondisi persaingan atau konflik dimana tujuannya untuk memenangkan permainan
dari pesaingnya.
Pembahasan pada materi ini dititik beratkan pada:
GOAL
• Mahasiswa dapat memahami konsep dasar pengambilan keputusan dalam situasi multi alternatif.
• Mahasiswa akan dapat mengetahui berbagai macam ilustrasi dalam penyelesaian masalah keputusan dengan metoda teori permainan.
OUTLINE
PENDAHULUAN
PENDAHULUAN
• Definisi: bagian dari ilmu pengetahuan yang berkaitan dengan pembuatan keputusan pada saat dua pihak atau lebih berada dalam kondisi persaingan atau konflik, dimana setiap lawan berkeinginan untuk mengoptimumkan keputusannya sendiri dengan kerugian lawannya.
• Contoh : kampanye iklan peluncuran produk-produk yang bersaing dan perencanaan taktik-taktik perang melawan tentara musuh.
PENDAHULUAN
• Model-model teori permainan ini dapat diklasifikasikan dalam beberapa cara, bergantung pada faktor-faktor berikut: • banyaknya pemain, • jumlah keuntungan dan kerugian, • banyaknya strategi yag dilakukan dalam
permainan
Klasifikasi Model Game Theory
• Banyaknya pemain:• Two Person Game; banyaknya pemain dua
pihak(baik individu atau kelompok)
• N Person Game; banyaknya pemain adalah N pihak (N>2)
• Jumlah keuntungan dan kerugian:• Zero-sum Game/ Constant-Sum Game; jumlah
kerugian dan keuntungan dari permainannya adalah nol
• Non Zero-sum Game; jumlah kerugian dan keuntungan dari permainannya bukan nol
Klasifikasi Model Game Theory
• Jadi, TWO PERSON ZERO SUM; sebuah permainan dengan dua pemain, dimana keuntungan satu pemain sama dengan kerugian pemain lainnya.
• Contoh dari N-person Non Zero-sum Game; sejumlah perusahaan melakukan kampanye advertensi yang intensif untuk memperoleh daerah pemasaran yang lebih besar.
ELEMEN – ELEMEN DASAR TEORI PERMAINAN
Persoalan two-person zero-sum game
Perhatikan matriks payoff berikut ini!
Persoalan two-person zero-sum game
Perhatikan matriks payoff berikut ini!
menyatakan outcome atau pembayaran dari strategi permainan yang berbeda
Persoalan two-person zero-sum game
Perhatikan matriks payoff berikut ini!
bilangan-bilangan positif ini menyatakan perolehan keuntungan bagi pihak yang ditulis pada baris sebagai pemain yang akan
memaksimumkan, dan sekaligus merupakan kerugian bagi pihak yang ditulis pada kolom sebagai pemain yang akan
meminimumkan
Strategi
• Strategi adalah tindakan pilihan• Aturan permainan menjelaskan tentang
bagaimana cara para pemain memilih strategi-strategi mereka
• Suatu strategi dinyatakan dominan apabila payoff yang ada pada suatu strategi bersifat superior (paling tinggi) dibandingkan dengan setiap payoff pada strategi lainnya
• Nilai permainan menyatakan ekspetasi outcome per permainan jika kedua pemain melakukan strategi terbaik (strategi optimum) mereka.
Strategi
• Strategi optimum adalah strategi yang menjadikan seorang pemain berada pada posisi pilihan terbaik, tanpa memperhatikan tindakan-tindakan pemain lawan.
• Tujuan model permainan adalah untuk mengidentifikasi strategi optimum bagi masing-masing pemain
TWO–PERSON, ZERO–SUM GAME
PURE – STRATEGY GAME
Permainan yang posisi pilihan terbaiknya bagi setiap pemain dicapai dengan memilih satu strategi tunggal
(strategi murni)
PURE – STRATEGY GAME
Pemain A yang akan memaksimumkan akan mengidentifikasi strategi
optimumya dengan menggunakan criteria maksimin, sedangkan pemain B
yang akan meminimumkan akan mengidentifikasi strategi optimumnya
dengan menggunakan criteria minimaks.
PURE – STRATEGY GAME
• Jika nilai maksimin = minimaks maka permainan selesai (disebut saddle point)
• Jika maksimin ≠minimaks permainan harus diselesaikan dengan strategi campuran (mixed-strategy game)
PURE – STRATEGY GAME
Contoh: Dua buah perusahaan sedang dlm proses perencanaan strategi advertensi masing-masing.
Struktur strategi dan payoff-nya sebagai berikut:
PERUSAHAAN B
B1 B2 B3
Perusahaan
A
A1 1 9 2
A2 8 5 4
Carilah nilai permainan dan strateginya!
PURE – STRATEGY GAME
Jawab: cari nilai maksiminnya dan minimaksnya.Struktur strategi dan payoff-nya sbb:
Minimaks = maksimin,
Jadi strategi optimum bagi A adalah A2 dan strategi untuk B adalah B3, dengan nilai permainan 4.
Perusahaan B Minimum
BarisB1 B2 B3
Perusahaan
A
A1 1 9 2 1
A2 8 5 4* 4 maksimin
Maksimum
Kolom
8 9 4
minimaks
MIXED – STRATEGY GAME
Pada game yang tidak mempunyai saddle point, penyelesaiannya harus
dilakukan dengan menggunakan strategi campuran.
MIXED – STRATEGY GAME
Perhatikan matriks payoff dari suatu game berikut ini:
Perusahaan B
B1 B2 B3
Perusahaan
A
1 0 -2 2
2 5 4 -3
3 2 3 -4
MIXED – STRATEGY GAME
Struktur strategi dan payoff-nya sbb:
maksimin ≠ nilai minimaks, maka permainan di atas tidak mempunyai saddle point
Perusahaan B Minimum
barisB1 B2 B3
Perusahaan
A
1 0 -2 2 -2 <MAKSIMIN
2 5 4 -3 -3
3 2 3 -4 -4
Maksimum
Kolom
5 4 2
MINIMAKS
MIXED – STRATEGY GAME
• pada permainan yang tidak mempunyai saddle point ini para pemain dapat memainkan seluruh strateginya sesuai dengan set probabilitas yang telah ditetapkan.
Xi = probabilitas pemain A memilih strategi i (i = 1,2,…,m)
Yi = probabilitas pemain B memilih strategi j (j = 1,2,…,n)
∑ xi = ∑ xj = 1
X1, Yj ≥ 0 untuk setiap I dan j
MIXED – STRATEGY GAME
Dalam bentuk matriks:
Solusi persoalan strategi campuran ini masih didasarkan pada kriteria maksimin dan minimaks.
B
Y1 Y2 ……... Yn
A
X1 a11 a12 a1n
X2 a21 a22 a2n
. . . .
. . . .
. . . .
Xm am1 am2 amn
MIXED – STRATEGY GAME
• Secara matematis:• Pemain A akan memilih :
xi (xi ≥ 0, ∑ xi = 1) yang menghasilkan:
v_ = maks xi {min (∑a11 xi , ∑ a12xi,……., ∑ ainxi)}• Pemain B akan memilih :
yj (yj ≥ 0, ∑ yj = 1) yang menghasilkan:
v- = min yj {maks (∑a1j yj , ∑ a2jyj,……., ∑ amjyj)}
MIXED – STRATEGY GAME
• Jika xi dan yj berkorespondensi dgn solusi optimum maka v_ = v-
• Jika xi* dan yj* =solusi optimum maka ekspektasi optimum dari permainan:v* = , ∑ ∑ aij xi*yj*
• Mixed strategy game dpt diselesaikan dgn cara grafis dan dgn menggunakan program linier.
SOLUSI GRAFIS PERMAINAN (2 x n) dan (m x 2)
• Syarat penggunaan: salah seorang dari pemain hanya mempunyai 2 buah strategi.
B
Y1 Y2 ……... Yn
AX1 a11 a12 a1n
X2=1-X1 a21 a22 a2n
SOLUSI GRAFIS PERMAINAN (2 x n) dan (m x 2)
• Berdasarkan strategi murni dari B, maka ekspektasi payoff untuk A adalah:
Strategi
murni B
Ekspektasi payoff A
1 (a11-a21)X1+a21
2 (a12-a22)X1+a22
. .
N (a1n-a2n)X1+a2n
SOLUSI GRAFIS PERMAINAN (2 x n) dan (m x 2)
• Berdasarkan kriteria minimaks untuk permainan dengan strategi campuran, pemain A harus memilih nilai X1 yang akan memaksimumkan ekspetasi payoff minimumnya. Hal ini dpt dicari dgn cara menggambarkan fungsi-fungsi X1.
SOLUSI GRAFIS PERMAINAN (2 x n) dan (m x 2)
matriks payoff:
Carilah nilai permainan ini dan strateginya.
Contoh:
SOLUSI GRAFIS PERMAINAN (2 x n) dan (m x 2)
Berdasarkan strategi murni dari B, maka ekspektasi payoff untuk A adalah:
Jawab
Strategi
murni B
Ekspektasi
payoff A
1 -5 X1+ 5
2 -6 X1+ 4
3 5 X1+ -3
SOLUSI GRAFIS PERMAINAN (2 x n) dan (m x 2)
Jawab
-
-
-
-
-
-
-
-
-3
4
5
0maksimin
1 x1
Ekspektasi payoff
-
-
-
-
-
-
-2
2
3
1
-1
-
-
SOLUSI GRAFIS PERMAINAN (2 x n) dan (m x 2)
Maksimim ekspetasi payoff V = maks xi { min (5 – 5x1), (4 – 6x1), (-3 + 5x1) }
V = maks xi { min (4 – 6x1), (-3 + 5x1) }
Jawab
SOLUSI GRAFIS PERMAINAN (2 x n) dan (m x 2)
• Titik potong dicari secara aljabar biasa:4 – 6x1 = -3 + 5x1
11x1 = 7
X1* = 7/11
Karena x1* + x2* = 1, maka x2* = 4/11
Jawab
SOLUSI GRAFIS PERMAINAN (2 x n) dan (m x 2)
• Mencari koordinat Y:v = v* = -3 + 5(7/11) = 2/11
v* = dan v* = ∑∑aijxiyj.
sehingga: y1*(5-5x1) + y2*(4-6x1) + y3*(-3+5x1) = 2/11
20/11y1* + 2/11 y2* + 2/11 y3* = 2/11
dengan y1* + y2* + y3* = 1
Jawab
SOLUSI GRAFIS PERMAINAN (2 x n) dan (m x 2)
Dalam hal ini, persamaan ∑ aij xi yang tidak melewati titik maksimim berkorespondensi dengan yj* = 0 (supaya tidak menaikkan expected payoff); karena itu, y1* = 0 sehingga y2* + y3* = 1 atau y3* = 1- y2* masukan pada persamaan (1), didapat:
jika x1 = 0 4y2* - 3y3* = 2/11 ; x1
x1 = 1 -2y2* + 2y3* = 2/11 ; x2
sehingga di dapat: y3* = 6/11
y2* = 5/11
Jawab
SOLUSI GRAFIS PERMAINAN (2 x n) dan (m x 2)
Dengan demikian, maka solusi optimum untuk kedua pemain adalah:
Pemain A: (x1, x2) = (7/11, 4/11)
Pemain B: (y1,y2,y3) = (0, 5/11, 6/11)
dengan nilai game v* = 2/11
Jawab
SOLUSI PROGRAM LINIER PERMAINAN (m x n)
Seperti dikemukakan di muka, kriteria maksimim dapat di formulasikan sebagai
Maks {min i1 xi, i2, …, in xi }
Dimana I = 1 dan xi ≥ 0 i = 1, …, m
Jika v = min ( i1 xi, i2 xi, …, in )
SOLUSI PROGRAM LINIER PERMAINAN (m x n)
Matriks payoff dari suatu permainan sebagai berikut:
Tentukanlah strategi optimum untuk masing-masing pemain!
Contoh:
B
1 2 3
1 3 -1 -3
A 2 -3 3 -1
3 -4 -3 3
SOLUSI PROGRAM LINIER PERMAINAN (m x n)
Dari matriks payoff di atas kita tahu bahwa nilai maksiminnya adalah -3 sehingga nilai permainannya dapat berharga negative atau nol.
Karena itu, diperlukan suatu konstanta k yang harganya paling sedikit sama dengan nilai maksimin yang negative itu.
Konstanta k itu kemudian ditambahkan kepada seluruh elemen matriks.
Jawab:
SOLUSI PROGRAM LINIER PERMAINAN (m x n)
Misalnya digunakan K = 5, maka matriksnya menjadi:
Jawab:
B
1 2 3
1 8 4 2
A 2 2 8 4
3 1 2 8
SOLUSI PROGRAM LINIER PERMAINAN (m x n)
Formulasi program linier untuk pemain B adalah:
Maks. W = Y1 + Y2 + Y3
s/t 8Y1 + 4Y2 + 2Y3 ≤ 1
2Y1 + 8Y2 + 4Y3 ≤ 1
Y1 + 2Y2 + 8Y3 ≤ 1
Y1, Y2, Y3 ≥ 0
Jawab:
SOLUSI PROGRAM LINIER PERMAINAN (m x n)
Setelah formulasi di atas diselesaikan dengan metode simpleks, maka didapat tabel optimum sebagai berikut:
Jawab:
Basis Y1 Y2 Y3 S1 S2 S3 solusi
W 0 0 0 5/49 11/196 1/14 45/196
Y1
Y2
Y3
1 0 0 1/7 -1/14 O
0 1 0 -3/196 31/196 -1/14
0 0 1 -1/98 -3/98 1/7
1/14
11/196
5/49
SOLUSI PROGRAM LINIER PERMAINAN (m x n)
Strategi optimum untuk pemain A diperoleh dari solusi dual persoalan di atas, maka:
Z = w = 45/196, X1 = 5/49, X2 = 11/196, X3 = 11/45
Sehingga:
X1* = X1/z = 20/45
X2* = X2/z = 11/45
X3* = X3/z = 14/45
Jawab:
LATIHAN SOAL
Soal 1.
Diketahui matriks payoff sebagai berikut:
Carilah nilai permainan ini dan strateginya!
B
1 2 3
A1 2 -3 -4
2 -6 -1 1
Soal 2.
Pertimbangkan permainan (2x4) berikut ini.
Carilah nilai permainan A dan B!
B
1 2 3 4
A1 2 2 3 -1
2 4 3 2 6