TEORI PERMAINAN
Aplikasi Teori Permainan Lawan
pemain (punya intelegensi yang sama). Setiap pemain mempunyai beberapa strategi untuk saling mengalahkan.
Two-Person Zero-Sum Game
Permainan dengan 2 pemain dengan perolehan (keuntungan) bagi salah satu pemain merupakan kehilangan (kerugian) bagi pemain lainnya.
Matriks/tabel payoff (perolehan)
tabel yang menunjukkan perolehan bagi pemain baris
Strategi Murni Digunakan jika permainan stabil Titik sadel
ada titik saddle (saddle point)
minimaks = maksimin
Contoh : Pemain A
Pemain B Strategi 1 Strategi 2 Strategi 3 Strategi 4 Strategi 5 Strategi 6
Strategi 1
5
10
-20
15
5
7
Strategi 2
15
8
16
-10
13
12
Strategi 3
11
11
12
14
14
12
Tentukan strategi terbaik bagi masing-masing pemain!! Jawab : Pemain A
Pemain B
Minimum
Strategi 1 Strategi 2 Strategi 3 Strategi 4 Strategi 5 Strategi 6 Strategi 1
5
10
-20
15
5
7
-20
Strategi 2
15
8
16
-10
13
12
-10
Strategi 3
11
11
12
14
14
12
11
maks
15
11
16
15
13
12
Teori Permainan, oleh Hotniar Siringoringo, hal. 1
Minimaks = maksimin = 11 Titik sadel
11
permainan seimbang (stabil)
nilai permainan (v)
Strategi Campuran Strategi campuran digunakan jika permainan tidak seimbang. Pemilihan strategi dilakukan dengan mengevaluasi kombinasi strategi lawan menggunakan prinsip peluang.
Definisikan : xi adalah peluang pemain baris akan menggunakan strategi ke-i Yj adalah peluang pemain kolom akan menggunakan strategi ke-j.
y1
y2
...
yn
Strategi 1
Strategi 2
...
Strategi n
x1
Strategi 1
a11
a12
...
a1n
x2
Strategi 2
a21
a22
...
a2n
.
.
.
.
.
.
.
.
.
.
.
.
xm
Strategi m
am1
am2
...
amn
Solusi Grafik Solusi grafik dapat digunakan jika paling salah satu pemain mempunyai hanya 2 strategi (2 x n atau m x 2).
Perhatikan matriks payoff untuk dua pemain berikut : B
A
y1
y2
y3
...
yn
x1
a11
a12
a13
...
a1n
x2 = 1-x1
a21
a22
a23
...
a2n
Menghitung x1 dan x2 dengan menganggap pemain B menggunakan strategi murni. Maka ekspektasi perolehan bagi pemain A adalah sbb:
Teori Permainan, oleh Hotniar Siringoringo, hal. 2
Strategi murni B
Ekspektasi perolehan A
1
a11 x1 + a21x2
2
a12 x1 + a22x2
3
a13 x1 + a23x2
.
.
.
.
.
.
n
a1n x1 + a2nx2
Ekspektasi digambarkan dengan sumbu horizontal x1 (0 sampai 1) dan vertikal sebagai ekspektasi perolehan. Nilai optimum (x1, x2 dan v) akan didapat dari titik perpotongan Titik perpotongan menunjukkan strategi B yang digunakan, maka y1, y2, ..., yn selanjutnya dapat ditentukan. Contoh 1: Perhatikan matriks payoff permainan di bawah ini: Pe
Pemain B
ma
Strategi 1
Strategi 2
Strategi 3
Strategi 4
Strategi 5
in
Strategi 1
2
4
5
-2
-1
A
Strategi 2
3
-1
-2
6
5
Permainan di atas memiliki nilai minimaks = 3 dan nilai maksimin = -2
permainan
tidak seimbang
Dengan solusi grafik: Pe
Pemain B
ma
y1
in A
y2
y3
y4
y5
Strategi 1 Strategi 2 Strategi 3 Strategi 4 Strategi 5 x1 Strategi 1
2
4
5
-2
-1
x2 Strategi 2
3
-1
-2
6
5
Teori Permainan, oleh Hotniar Siringoringo, hal. 3
Bagi Pemain A :
Strategi murni B
Ekspektasi perolehan A
1
2x1 + 3x2 =(2-3)x1+3
2
5x1-1
3
7x1-2
4
-8x1+6
5
-6x1+5
4 5 5 4 1 3 2 1 0
0.5
1 x1
2 -2 3 Ada 6 titik perpotongan yang menjadi kandidat solusi optimal untuk x1 (titik perpotongan garis (1,2), (1,3), (2,4), (2,5), (3,4) dan (3,5)). Karena pemain A adalah pemain baris dimana dia akan memaksimumkan ekspektasi perolehan minimumnya, maka solusi optimalnya adalah titik perpotongan ungu (perpotongan garis (2,4)). Dengan demikian x1 = 7/13 dan x2 = 1-7/13 = 6/13.
Teori Permainan, oleh Hotniar Siringoringo, hal. 4
v = 5x1 -1 = 22/13
diperoleh dengan memasukkan nilai x1 pada pers (2) atau (4).
Bagi Pemain B: Solusi optimal bagi pemain A di atas merupakan perpotongan garis (2) dan (4), Hal ini menunjukkan bahwa B dapat mengkombinasikan kedua strategi tersebut. Kombinasi strategi 2 dan 4 menunjukkan bahwa y1 = y3 = y5 = 0.
Pe
Pemain B
ma
y2
in A
y4
Strategi 2 Strategi 4 x1 Strategi 1
4
-2
x2 Strategi 2
-1
6
Strategi murni A Ekspektasi perolehan B 1
4y2 - 2y4 =(4+2)y2-2=6y2-2
2
-7y2+6
6y2-2=-7y2+6, maka y2 = 8/13 dan y4 = 5/13; y1 = y3 = y5 = 0; v = 22/13 (sama dengan nilai di atas).
Contoh 2: Perhatikan permainan dengan matriks payoff berikut: B
A
1
2
1
2
4
2
2
3
3
3
2
4
-2
6
Penyelesaian : Tidak ada saddle point, dan pemain B memiliki hanya 2 strategi
Bagi Pemain B:
Teori Permainan, oleh Hotniar Siringoringo, hal. 5
solusi grafik.
Strategi murni A
Ekspektasi payoff B
1
-2y1+4
2
-y1+3
3
y1+2
4
-8y1+6
5 4 3 3 2 1
2
1 0
y1
0.5
1
-2 4
Ada 3 titik maksimum (perpotongan warna ungu, biru dan hijau). Pemain B sebagai pemain kolom akan meminimumkan ekspektasi perolehan maksimumnya, maka solusi y1 = 2/3 dan y2 = 1/3; v = -2*2/3 + 4 =8/3
optimalnya adalah titik hijau
Pemain A Titik optimum bagi pemain B merupakan perpotongan strategi 1 dan 3 pemain A. B
A
1
2
1
2
4
3
3
2
Teori Permainan, oleh Hotniar Siringoringo, hal. 6
Strategi murni B
Ekspektasi payoff A
1
-x1+3
2
2x1+2
-x1+3 = 2x1+2
x1 = 1/3, x2 = 0, x3 = 2/3, x4 = 0 dan v = 8/3 (sama dengan di atas).
Metode Simpleks
Bentuk umum LP bagi pemain baris : Min z = X 1 + X 2 + ... + X m Sub. To : a11 X 1 + a 21 X 2 + ... + a m1 X m ≥ 1 a12 X 1 + a 22 X 2 + ... + a m 2 X m ≥ 1 Μ
Μ
a1n X 1 + a 2n X 2 + ... + a m n X m ≥ 1 X 1 , X 2 ,..., X m ≥ 0 x Xi = i ; v
z=
1 v
Bentuk umum LP bagi pemain kolom (Dual pemain baris) Maks. w = Y1 + Y2 + ... + Yn
Sub. To : a11Y1 + a12Y2 + ... + a1n Yn ≤ 1 a 21Y1 + a 22Y2 + ... + a 2n Yn ≤ 1 Μ
Μ
a m1Y1 + a m 2Y2 + ... + a mnYn ≤ 1 Y1 , Y2 ,..., Yn ≥ 0
Yi =
yj v
; w=
1 v
Perhatikan kembali matriks payoff berikut:
Teori Permainan, oleh Hotniar Siringoringo, hal. 7
Pemain B
Pe ma
Strategi 1
Strategi 2
Strategi 3
Strategi 4
Strategi 5
in
Strategi 1
2
4
5
-2
-1
A
Strategi 2
3
-1
-2
6
5
Maka bentuk umum LP untuk pemain baris (pemain A) adalah : Min. z = X 1 + X
2
Sub. To : 2X1 + 3X 2 ≥ 1 4X1 − X 2 ≥1 5X1 − 2X 2 ≥1 − 2X1 + 6X 2 ≥1 − X1 + 5X 2 ≥1 X 1, X 2 ≥ 0
Maka bentuk umum LP untuk pemain kolom (pemain B) adalah : Maks. w = Y1 + Y 2 + Y 3 + Y 4 + Y 5 Sub. To:
2Y1 + 4Y 2 + 5Y3 − 2Y 4 − Y5 ≤ 1 3Y1 − Y 2 − 2Y3 + 6Y 4 + 5Y5 ≤ 1 Y1 , Y 2 , Y3 , Y 4 , Y5 ≥ 0
Tabel simpleks awal (iterasi-0):
VB
Y1
Y2
Y3
Y4
Y5
s1
s2
NK
w
-1
-1
-1
-1
-1
0
0
0
s1
2
4
5
-2
-1
-
0
1
s2
3
-1
-2
6
5
0
1
1
Iterasi-1:
Teori Permainan, oleh Hotniar Siringoringo, hal. 8
VB
Y1
Y2
Y3
Y4
Y5
s1
s2
NK
w
-3/5
-1/5
0
-7/5
-6/5
1
0
1/5
Y3
2/5
4/5
1
-2/5
-1/5
1
0
1/5
s2
19/5
3/5
0
26/5
23/5
2
1
7/5
VB
Y1
Y2
Y3
Y4
Y5
s1
s2
NK
w
11/26
-1/26
0
0
1/26
6/13
7/26
15/26
Y3
9/13
11/13
1
0
5/26
15/13
1/13
4/13
Y4
19/26
3/26
0
1
23/26
5/13
5/26
7/26
Iterasi-2 :
Iterasi-3: optimal
VB
Y1
Y2
Y3
Y4
Y5
s1
s2
NK
w
5/11
0
1/22
0
0.0472
7/22
3/11
13/22
Y2
9/11
1
13/11
0
5/22
15/11
1/11
4/11
Y4
7/11
0
-3/22
1
0.85839
5/22
2/11
5/22
Y1 = Y3 = Y5 = 0
Y2 = 4/11
y1 = y3 = y5 = 0; 4 Y2 y2 = = 11 = 8 ; 13 w 13 22
z = w = 13/22; X1 = s1 = 7/22
X2 = s2 = 3/11
w = 13/22
Y4 = 5/22
x1 =
v=1/w=
1 = 22 13 13 22
5 Y4 y4 = = 22 = 5 13 w 13 22
7 X1 = 22 = 7 13 13 z 22
3 X2 x2 = = 11 = 6 13 13 z 22
Teori Permainan, oleh Hotniar Siringoringo, hal. 9