27/04/2015
GAME THEORY
OPERATIONAL RESEARCH II Agustina Eunike, ST., MT., MBA. Industrial Engineering – University of Brawijaya
Teori permainan merupakan bagian dari studi rational behavior terhadap kesalingtergantungan atau interdependensi antar pemain. Para pemain memiliki persamaan kepentingan untuk mendapatkan bagian keuntungan sebesar mungkin. Para pemain memiliki kepentingan yang saling bersinggungan untuk memaksimalkan bagian keuntungan masing-masing.
GAME THEORY
GAME THEORY
Pengambilan keputusan rasional seorang pemain membutuhkan antisipasi terhadap respon pesaing.
Setiap pemain bermain rasional, dengan asumsi memiliki intelegensi yang sama, dan tujuan sama, yaitu memaksimumkan payoff, dengan kriteria maksimin dan minimaks.
Ekspektasi terhadap perilaku pesaing tidaklah selalu sesuai harapan. ketidakpastian menjadi pertimbangan penting dari permainan ini.
GAME THEORY Syarat dan Ketentuan: Tabel yang disusun menunjukkan keuntungan pemain baris, dan kerugian pemain kolom.
Terdiri dari 2 pemain, keuntungan bagi salah satu pemain merupakan kerugian bagi pemain lain. Tujuan dari teori permainan ini mengidentifikasi strategi yang optimal
adalah
Prisoner’s Dilema Dua orang ditangkap oleh polisi dan didakwa menjadi pelaku tindakan yang melawan hukum. Dua orang tersebut ditahan dalam ruang yang terpisah sehingga keduanya tidak bisa untuk berkomunikasi.
Permainan dikatakan adil jika hasil akhir menghasilkan nilai nol (0), tidak ada yang menang/kalah.
1
27/04/2015
Prisoner’s Dilema
Prisoner’s Dilema Dua orang tersebut akan diinterogasi dan sebelum diinterogasi kedua tersangka tersebut diberi tahu bahwa:
Pilihan tindakan (strategi) yang bisa dipilih oleh kedua tersangka tersebut beserta konsekuensinya dapat digambarkan sebagai berikut:
– Jika salah satu mengaku dan yang lain tidak mengaku, maka yang mengaku akan bebas dan yang tidak mengaku akan mendapat hukuman 20 tahun penjara. – Jika dua-duanya tidak mengaku maka keduanya akan dipenjara selama 1 tahun. – Jika dua tersangka tersebut mengaku maka keduanya akan dipenjara selama 5 tahun.
Apakah yang seharusnya dilakukan oleh kedua tersangka tersebut??
Tindakan yang akan diambil Tersangka 1 • Tersangka 1
• Tersangka 2
– Jika ia mengaku maka kemungkinan ia akan dihukum 5 tahun jika ternyata tersangka 2 juga mengaku atau akan bebas jika tersangka 2 tidak mengaku. – Jika ia tidak mengaku maka kemungkinan ia akan dihukum 20 tahun jika ternyata tersangka 2 mengaku atau akan dihukum 1 tahun kalau tersangka 2 juga tidak mengaku.
– Jika ia mengaku maka kemungkinan ia akan dihukum 5 tahun jika ternyata tersangka 1 juga mengaku atau akan bebas jika tersangka 1 tidak mengaku. – Jika ia tidak mengaku maka kemungkinan ia akan dihukum 20 tahun jika ternyata tersangka 1 mengaku atau akan dihukum 1 tahun kalau tersangka 1 juga tidak mengaku.
Apapun tindakan yang akan diambil oleh tersangka 2, bagi tersangka 1 akan selalu lebih menguntungkan untuk mengaku!
Apapun tindakan yang akan diambil oleh tersangka 1, bagi tersangka 2 akan selalu lebih menguntungkan untuk mengaku!
Strategi yang akan diambil oleh tersangka 1 dan tersangka 2 • •
Tindakan yang akan diambil Tersangka 2
Berdasarkan analisa tersebut maka bisa dipastikan keduanya akan mengaku!! Kedua orang tersebut akan dihukum selama 5 tahun!
Apakah yang akan terjadi kalau mereka diperbolehkan berkomunikasi?? • Keduanya akan bekerjasama dan masing-masing akan tutup mulut sehingga mereka masing-masing hanya akan dihukum selama 1 tahun.
Apakah yang akan terjadi kalau mereka diperbolehkan berkomunikasi??
2
27/04/2015
Apakah yang akan terjadi kalau mereka diperbolehkan berkomunikasi??
Intisari Prisoner’s Dilemma Kedua pemain akan memiliki kondisi lebih baik apabila mereka dapat bekerja sama atau kooperatif dalam memecahkan masalah Oleh karena itu, polisi akan memisahkan tersangka ke dalam ruang interogasi berbeda
Titik keseimbangan atau equilibrium tidak harus efisien. Titik keseimbangan non-kooperatif di dalam Prisoner’s Dilemma menghasilkan pemecahan masalah yang bukan merupakan hasil terbaik yang dikehendaki kedua pihak
Nash Equilibrium Tidak ada satu pemainpun yang memiliki insentif untuk mengubah strategi, terhadap pilihan pemain lainnya. Apabila keduanya mengaku, maka titik keseimbangan tercapai yang disebut sebagai Nash Equilibrium Apabila keduanya tidak mengaku, maka tidak dapat dikategorikan sebagai Nash Equilibrium, karena pesaing akan selalu ingin melawan atau memberontak Nash equilibrium is a solution concept of a non-cooperative game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only their own strategy
Two-Person, Zero Sum Games • Strategi – Aturan yang ditetapkan diawal terkait tindakan yang harus diberikan pada situasi tertentu, untuk tiap tahap permainan.
Two-Person, Zero Sum Games • Melibatkan hanya dua orang player • Jumlah perolehan player pemenang sama dengan jumlah kerugian player yang kalah net winning kedua player sama dengan nol • Karakteristik two-person game – Ada pilihan strategi untuk player I – Ada pilihan strategi untuk player II – Ada tabel payoff
Two-Person, Zero Sum Games Asumsi: • Kedua pemain adalah rasional • Kedua pemain memilih strategi yang mendorong kesejahteraannya sendiri.
• Tabel Payoff – Menunjukkan perolehan pemain I yang dihasilkan dari tiap kombinasi strategi tiap pemain.
3
27/04/2015
Game “Odds and Evens”
Game “Odds and Evens”
• Setiap player saling menunjukkan satu atau dua jari secara bersamaan. Bila banyaknya jari yang keluar sama sehingga jumlahnya genap maka player I memenangkan taruhan sebesar $1 dari player II, dan sebaliknya • Strategi tiap player menunjukkan satu atau dua jari
Payoff Table for the Odds and Evens Game Player II Strategy 1 2 1 1 -1 Player I 2 -1 1
“Political Campaign Problem”
“Political Campaign Problem”
• Dua orang politisi saling bersaing untuk dapat duduk di kursi DPR. Kampanye harus dilakukan pada dua hari terakhir. Kedua politisi tersebut berkeinginan menghabiskan masa kampanye di dua kota, Surabaya dan Malang. Agar waktu yang dimiliki dapat digunakan dengan efektif dan efisien, mereka merencanakan untuk untuk melakukan perjalanan di malam hari dan menghabiskan waktu 1 hari penuh pada tiap kota atau dua hari penuh pada satu kota. Untuk pengaturan yang optimal, tiap politisi melakukan pengukuran terhadap dampak yang dapat diperoleh (mungkin menang atau kalah) dari berbagai variasi waktu tinggal, baik untuk dirinya maupun lawan politiknya. Strategi mana yang terbaik untuk digunakan oleh politisi tersebut?
Formulasi Tabel Payoff untuk “Political Campaign Problem” Total Perolehan Suara yang Dimenangkan Politisi I (x 1.000 suara) Politisi II Strategi 1 2 3 1 Politisi I
2
Strategi • Strategi 1: menghabiskan satu hari di masing-masing kota • Strategi 2: menghabiskan dua hari di Surabaya • Strategi 3: menghabiskan dua hari di Malang
Variasi I :Dominated Strategy Total Perolehan Suara yang Dimenangkan Politisi I (x 1.000 suara) Politisi II Strategi 1 2 3 Politisi I
1
1
2
2
1
0
4 5
3
0
1
-1
3
4
27/04/2015
Variasi I
Variasi I
Total Perolehan Suara yang Dimenangkan Politisi I (x 1.000 suara) Politisi II Strategi 1 2 3
Total Perolehan Suara yang Dimenangkan Politisi I (x 1.000 suara) Politisi II Strategi 1 2 3
Politisi I
1
1
2
4
2
1
0
5
3
0
1
-1
Politisi I
1
1
2
2
1
0
5
3
0
1
-1
Variasi I
Variasi I
Total Perolehan Suara yang Dimenangkan Politisi I (x 1.000 suara) Politisi II Strategi 1 2 3 1 Politisi I
1
2
Total Perolehan Suara yang Dimenangkan Politisi I (x 1.000 suara) Politisi II Strategi 1 2 3
4
2
1
0
5
3
0
1
-1
Variasi I • Kedua politisi mengambil strategi 1 • Politisi I akan mendapatkan payoff sebesar 1 dari politisi II (politisi I merebut 1.000 suara dari politisi II) • Payoff 1 nilai game • Fair game nilai game = 0 • Unfair game nilai game ≠ 0
4
Politisi I
1
1
2
2
1
0
4 5
3
0
1
-1
Strategi Maximin‐Minimax Pemain 1 strategi maximin Setiap strategi dicari kemungkinan terburuknya, Pilih strategi yang kemungkinan terburuknya memiliki payoff yang terbesar jika dibandingkan dengan strategi yang lain.
Pemain 2 strategi minimax – Dasar pemikiran sama dengan maximin pada pemain 1. – Pada tabel payoff nilai yang besar (positif) justru menunjukkan kerugian yang besar pada pemain 2 sehingga maximin menjadi minimax!
5
27/04/2015
Variasi II
Variasi II : Minimax Criterion Total Perolehan Suara yang Dimenangkan Politisi I (x 1.000 suara)
Total Perolehan Suara yang Dimenangkan Politisi I (x 1.000 suara) Politisi II Strategi 1 2 3 Politisi I
1
-3
-2
6
2
2
0
2
3
5
-2
-4
Strategi
Politisi II
Minimum
1
2
3
1
-3
-2
6
2
2
0
2
0
3
5
-2
-4
-4
Maksimum
5
0
6
Politisi I
-3 maximin
↓ Minimax
Variasi II
Variasi III
• Nilai game = 0 fair game • Player (politisi) I memilih strategi dengan minimum payoff terbesar (maximin) • Player (politisi) II memilih strategi dengan maximum payoff terkecil (minimax) • Maximin = minimax saddle point stable solution
Total Perolehan Suara yang Dimenangkan Politisi I (x 1.000 suara) Politisi II Strategi 1 2 3 Politisi I
Variasi III
0
-2
2
2
5
4
-3
3
2
3
-4
Variasi III
Total Perolehan Suara yang Dimenangkan Politisi I (x 1.000 suara) Politisi II Strategi Minimum 1 2 3 1
0
-2
2
-2
2
5
4
-3
-3
3
2
3
-4
-4
Maksimum
5
4
2
Politisi I
1
maximin
• • • • •
Maximin ≠ Minimax Tidak ada saddle point Unstable solution Tidak dapat diselesaikan dengan “pure strategy” Diselesaikan dengan “mixed strategies”
↓ Minimax
6
27/04/2015
Latihan :
Latihan :
• Tentukan strategi optimal untuk tiap pemain dengan menggunakan dominated strategy beserta nilai payoff-nya. • Berikan daftar strategi dominasi dari tiap pemain yang digunakan untuk mengeliminasi strateginya
• Tentukan saddle point -nya II 1
2
3
4
1
3
-3
-2
-4
2
-4
-2
-2
1
3
1
-1
2
0
II I 1
I
2
3
4
1
2
-3
-1
1
2
-1
1
-2
2
3
-1
2
-1
3
Mixed Strategies • xi = probabilitas player I menggunakan strategi i; i = 1, 2, …, m • yj = probabilitas player II menggunakan strategi j, j = 1, 2, …, n • pij = payoff jika player I menggunakan strategi murni i dan player II menggunakan strategi murni j • v* = payoff optimal
GAME THEORY
MIXED STRATEGY
Mixed Strategies
Mixed Strategies Player 2
m
x i 1
1
i
j 1
j
1
2
……
n
i
Proba bilitas
y1
y2
……
yn
x1
p11
p12
……
p1n
1
n
y
Strategi
j
1 m
n
v * pij xi y j i 1 j 1
2 Player 1
: m EPO
EPO**
n
p j 1
x yj
1j 1
n
x2
p21
p22
……
p2n
:
:
:
……
:
p j 1
2j
x2 y j
: n
xm
pm1 m
p i 1
pm2
……
m
x y1
i1 i
p i 1
pmn
pmj xm y j j 1
m
x y2
i2 i
……
p i 1
x yn
in i
**EPO: Expected Payoff
7
27/04/2015
Mixed strategies
Mixed Strategies
• Minimax theorem – If mixed strategies are allowed, the pair of mixed strategies that is optimal according to the minimax criterion provides a stable solution with v = v = v (the value of the game), so that neither player can do better by unilaterally changing his strategy
Solusi Optimal • Player I memilih strategi xi yang memaksimumkan EPO terkecil dalam kolom (maximin EPO) • Player II memilih strategi yj yang meminimumkan EPO terbesar dalam baris (minimax EPO)
Mixed Strategies
Mixed Strategies • Contoh untuk variasi III • Player I (x1, x2, x3) = (½, ½, 0) • Player II (y1, y2, y3) = (0, ½, ½)
m m m v max min ai1 xi , ai 2 xi ,......, ain xi xi i 1 i 1 i 1 n n n v min max a1 j y j , a2 j y j ,......, amj y j yj j 1 j 1 j 1 dimana
v v optimal dicapai bila v v v*
Mixed Strategies
Mixed Strategies
Reduced Payoff Table for Variation III Player II
Probability
x1
Pure strategy 1
1 – x1
2
Probability Player I
y1
y2
y3
1
2
3
0
-2
2
5
4
-3
(y1, y2, y3) (1, 0, 0) (0, 1, 0) (0, 0, 1)
Expected Payoff 0x1 + 5(1 – x1) = 5 – 5x1 – 2x1 + 4(1 – x1) = 4 – 6x1 2x1 – 3(1 – x1) = – 3 + 5x1
8
27/04/2015
Mixed Strategies 6
Mixed Strategies • Minimum EPO untuk player 1 ditandai dengan garis batas yang terendah dari garis dalam grafik • Maximin EPO untuk player 1 titik potong tertinggi yang terletak pada garis batas minimum EPO
maximin point
5
expected payoff
4 3 2 1 0
x1
-1 0
0,25
0,5
0,75
1
– Titik potong garis (4 – 6x1) dan (-3 + 5x1)
-2 -3
-4
Mixed Strategies
Mixed Strategies
v 4 6 x1
4 6 x1 3 5 x1
11
11x1 7
46 7
x1 7
2
11 x2 1 x1
11 v 3 5 x1
1 7
3 5 7
4
11
11
2
11
• Titik maximin untuk player 1 dihasilkan dari perpotongan antar grafik EPO player 1 jika player 2 memilih pure strategy 2 dan 3 • y1 = 0 • y 2 = y2 • y3 = 1 – y2
11
Mixed Strategies
Mixed Strategies
Reduced Payoff Table for Variation III Player II
Probability
x1
Pure strategy 1
x2
2
Probability Player I
y1 = 0
y2 = y2
y3 = 1 – y2
1
2
3
0
-2
2
5
4
-3
(x1, x2) (1, 0) (0, 1)
Expected Payoff –2y2 + 2(1 – y2) = 2 – 4y2 4y2 – 3(1 – y2) = – 3 + 7y2
9
27/04/2015
Mixed Strategies 2 4 y2 3 7 y2 11 y2 5
v 2 4 y2
11
24 5
y2 5
2
11 y3 1 y 2 1 5 6
Mixed Strategies
11 v 3 7 y2
• Strategi campuran yang dipilih player 1 = (x1*, x2*, x3*) = (7/11, 4/11, 0) • Strategi campuran yang dipilih player 2 = (y1*, y2*, y3*) = (0, 5/11, 6/11) • Nilai game optimal = v* = 2/11
11
3 7 5
11
2
11
11
Mixed Strategies Contoh: m x 2
Mixed Strategies • Permasalahan Two Person Zero Sum Games dapat diselesaikan dengan metode graphical bila tabel payoff membentuk matriks 2 x n atau m x 2 • Permasalahan Two Person Zero Sum Games dengan tabel payoff yang membentuk matriks m x n dapat diselesaikan dengan linier programming
Besar Kemenangan Player I Player II
Strategi
Minimum
1
2
1
2
4
2
2
2
3
2
3
5
3
3
4
-2
6
-2
Maksimum
5
6
Player I
} maximin
↓ Minimax
Mixed Strategies Contoh: m x 2
Mixed Strategies Contoh: m x 2
Besar Kemenangan Player I Player II
Probabilitas Probabilitas
Player I
y1
y2 = 1 – y1
Minimum
PS
1
2
x1
1
2
4
2
x2
2
2
3
2
x3
3
5
3
3
x4
4
-2
6
-2
5
6
Maksimum
(x1, x2, x3, x4) (1, 0, 0, 0) (0, 1, 0, 0) (0, 0, 1, 0) (0, 0, 0, 1)
Expected Payoff 2y1 + 4(1 – y1) = 4 – 2y1 2y1 + 3(1 – y1) = 3 – y1 5y1 + 3(1 – y1) = 3 + 2y1 -2y1 + 6(1 – y1) = 6 – 8y1
10
27/04/2015
Mixed Strategies Contoh: m x 2
Mixed Strategies Contoh: m x 2
EPO titik minimaks
6
3 20,3 3,6 v 6 8 y1
10 y1 3
5 4 EPO1
3
EPO2
2
EPO3
1
EPO4
0 -1 0
v 3 2 y1
3 2 y1 6 8 y1
7
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1
y1 3 0,3 10 y2 1 y1 1 0,3 0,7
y1
-2
-3
Mixed Strategies Contoh: m x 2 • Titik minimax untuk player II dihasilkan dari perpotongan antar grafik EPO player II jika player I memilih pure strategy 3 dan 4 • x1 = 0 • x2 = 0 • x3 = x3 • x4 = 1 – x3
Mixed Strategies Contoh: m x 2 (y1, y2) (1, 0) (0, 1)
Expected Payoff 5x3 – 2(1 – x3) = – 2 + 7x3 3x3 + 6(1 – x3) = 6 – 3x3
6 80,3 3,6
Mixed Strategies Contoh: m x 2 Besar Kemenangan Player I Player II
Probability
y1
y2
Pure strategy
1
2
x1 = 0
1
2
4
x2 = 0
2
2
3
x3 = x3
3
5
3
x4 = 1 – x3
4
-2
6
Probability
Player I
Mixed Strategies Contoh: m x 2 2 7 x3 6 3 x3 10 x3 8 x3 8
0,8
10 x4 1 x2
1 0,8 0,2
v 2 7 x3
2 70,8 3,6 v 6 3 x3 6 30,8 3,6
11
27/04/2015
Mixed Strategies Contoh: m x 2 • Strategi campuran yang dipilih player 1 = (x1*, x2*, x3*, x4*) = (0; 0; 0,8; 0,2) • Strategi campuran yang dipilih player 2 = (y1*, y2*) = (0,3; 0,7) • Nilai game optimal = v* = 3,6 GAME THEORY
LINEAR PROGRAMMING
Linier Programming • Untuk permasalahan Two Person Zero Sum Games dengan matriks payoff mxn
Linier Programming: Player I min z xm 1 K ST m
p i 1
x xm 1 0; j 1,2,..., n
ij i
m xi 1 i 1 xi 0, i 1,2,..., m
Linier Programming: Player II
Linier Programming
max z yn 1 K
Tabel Payoff Player I Strategi
p j 1
ij
y j yn 1 0; i 1,2,..., m
n y j 1 j 1 y j 0, j 1,2,..., n
Minimum
2
3
1
3
-1
-3
-3
2
-3
3
-1
-3
3
-4
-3
3
-4
Maksimum
3
3
3
ST n
Player II 1
Player I
12
27/04/2015
Linier Programming
Linier Programming Tabel Payoff Player I
• Nilai maximin positif –K=0
Strategi
• Nilai maximin negatif – K ≥ |nilai maximin| – Maximin = -3 ≤ 0 (ada kemungkinan nilai v ≤ 0) no feasible solution – Ditambahkan konstanta K, dimana = |-3| = 3 – Misal: K = 5
Linier Programming: Player I
Player I
Player II 1
2
3
1
8
4
2
2
2
8
4
3
1
2
8
Linier Programming: Player I
max z x4 K
max z x4 5
ST
ST
p11x1 p21x2 p31x3 x4 0
8 x1 2 x2 x3 x4 0
p12 x1 p22 x2 p32 x3 x4 0
4 x1 8 x2 2 x3 x4 0
p13 x1 p23 x2 p33 x3 x4 0
2 x1 4 x2 8 x3 x4 0
x1 x2 x3 1
x1 x2 x3 1
xi 0, i 1,2,3
xi 0, i 1,2,3
LINGO
LINGO
max = x4 - 5; 8*x1 4*x1 2*x1 x1
+ 2*x2 + x3 – x4 >= 0; + 8*x2 + 2*x3 – x4 >= 0; + 4*x2 + 8*x3 – x4 >= 0; + x2 + x3 = 1;
13
27/04/2015
Linier Programming: Player II
Linier Programming: Player II
min z y4 K
min z y4 5
ST p11 y1 p12 y2 p13 y3 y4 0
ST 8 y1 4 y2 2 y3 y4 0
p21 y1 p22 y2 p23 y3 y4 0
2 y1 8 y2 4 y3 y4 0
p31 y1 p32 y2 p33 y3 y4 0
y1 2 y2 8 y3 y4 0
y1 y2 y3 1
y1 y2 y3 1
y j 0, j 1,2,..., n
y j 0, j 1,2,..., n
LINGO
LINGO
min = y4 - 5; 8*y1 2*y1 y1 y1
+ 4*y2 + 2*y3 - y4 <= 0; + 8*y2 + 4*y3 - y4 <= 0; + 2*y2 + 8*y3 - y4 <= 0; + y2 + y3 = 1;
Hasil • V = -0,6444 • (x1, x2, x3) = (0,4444; 0,2444; 0,3111) • (y1, y2, y3) = (0,3111; 0,2444; 0,4444)
Soal Strategi
Pemain I
1 2 3 4 5
1 -2 2 2 -1 -3
2 2 1 2 4 6
Pemain II 3 4 1 0 4 -1 -1 -2 0 1 -2 2
5 -1 0 -3 2 4
14
27/04/2015
Soal Strategi
Pemain I
1 2 3 4 5
1 -2 2 2 -1 -3
2 2 1 2 4 6
Soal Pemain II 3 4 1 0 4 -1 -1 -2 0 1 -2 2
Soal: jawab • Pemain I = (0; 2/5; 0; 3/5; 0) • Pemain 2 = (2/5; 0; 0; 3/5; 0) • Payoff = v* = 1/5
5 -1 0 -3 2 4
Strategi Pemain I
2 4 5
Pemain II 1 4 2 -1 -1 1 -3 2
References • Hillier, Frederick and Lieberman, Gerald J., Introduction to Operations Research, 7th ed, McGraw-Hill, New York, 2001. • Taha, Hamdy, Operation Research : An Introduction, 8th ed, Pearson Education Inc., NJ, 2007. • Winston, Wayne L., Operations Research: Application & Algorithms, 4th ed, Thomson Learning, Belmont – CA, 2003.
15
