Pemain P 1. Teorema 4.1 (Teorema minimax). Untuk setiap matriks pembayaran (pay off matrix), terdapat strategi optimal x* dan y* sedemikian sehingga

Riset Operasi Probabilistik Teori Permainan (Game Theory)

Nughthoh Arfawi Kurdhi, M.Sc Departement of Mathematics FMIPA UNS

Lecture 4: Mixed Strategy A. Metode Campuran (Mixed Strategy) Di dalam permainan di mana permainan tersebut tidak mempunyai titik pelana, maka para pemain akan bersandar kepada apa yang disebut sebagai strategi campuran. Hal ini berarti: 1. Pemain memainkan setiap strategi baris dengan proporsi waktu (probabilitas) tertentu. 2. Pemain memainkan setiap strategi kolom dengan proporsi waktu (probabilitas) tertentu. Jadi, tugas setiap pemain adalah menentukan proporsi waktu (probabilitas) yang diperlukan untuk memainkan strateginya. Jadi, strategi campuran adalah strategi dengan setiap pemain menggunakan distribusi probabilitas dalam memilih strateginya. Diberikan suatu matriks pembayaran yang berukuran m  n , di mana pemain P1 mempunyai m strategi i, i = 1, 2, ..., m dan pemain P2 mempunyai n strategi j, j = 1, 2, ..., n. Misalnya: xi = probabilitas pemain P1 memilih strategi ke-i. yj = probabilitas pemain P2 memilih strategi ke-j. aij = nilai pembayaran dalam matriks pembayaran (aij) yang bersesuaian dengan strategi ke-i untuk pemain P1 dan strategi ke-j untuk pemain P2.

Pemain P1

x1 x2 x3 ... xm

y1 1 a11 a21 a31 ... am1

i/j 1 2 3 ... m

Pemain P2 y2 2 a12 a22 a32 ... am2

y3 3 a13 a23 a33 ... am3

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

y4 n a1n a2n a3n ... amn

Teorema 4.1 (Teorema minimax). Untuk setiap matriks pembayaran (pay off matrix), terdapat strategi optimal x* dan y* sedemikian sehingga E ( x * , y * )  max min E( x, y)  min max E ( x, y )  v * x

y

y

x

dengan x = [x1, x2, ..., xm] dan y = [y1, y2, ..., ym] berturut-turut merupakan vektor probabilitas untuk strategi pemain P1 dan P2. Dan m

n

E ( x, y )   xi aij y j i 1 j 1

merupakan nilai harapan matematis permainan. Terdapat beberapa metode campuran yang dapat digunakan untuk menyelesaikan suatu permainan, yaitu: 1. Metode Aljabar Metode ini hanya dapat digunakan pada suatu permainan dengan masing-masing pemain mempunyai dua strategi (langkah) saja, yaitu permainan berukuran 2 × 2. 2. Metode Grafik Metode ini dapat digunakan pada suatu permainan berukuran 2 × atau × 2.



3. Metode Program Linear Metode ini dapat digunakan pada suatu permainan berukuran

× .

Catatan: Perlu diperhatikan kembali bahwa aturan dominansi dapat digunakan untuk mengubah ukuran matriks pembayaran suatu permainan menjadi lebih sederhana, sehingga dapat diselesaikan dengan metode yang lebih sederhana pula, sesuai dengan ukuran matriks setelah di dominansi. B.

Metode Campuran dengan Metode Aljabar Metode aljabar dapat digunakan pada suatu permainan berukuran 2 × 2. Contoh 1. Diberikan matriks pembayaran seperti di bawah ini. Pemain P2 1 5 1

i/j 1 2

Pemain P1

2 3 4

Matriks pembayaran dari permainan berjumlah nol dari dua orang di atas tidak mempunyai titik pelana, sehingga strategi murni tidak dapat dipergunakan. Dengan demikian, tugas para pemain adalah menentukan proporsi waktu (probabilitas) yang diperlukan untuk memainkan strategi pada baris bagi pemain P1 dan strategi kolom bagi pemain P2.  Pemain P1 Misal didefinisikan x = proporsi waktu pemain P1 yang digunakan untuk memainkan strategi ke 1. dengan 0 ≤ ≤ 1. Maka proporsi waktu (probabilitas) yang diperlukan untuk memainkan strategi pada baris kedua adalah 1-x, sehingga jumlah semua proporsi waktu yang diperlukan untuk memainkan seluruh strateginya adalah x + (1-x) = 1.  Pemain P2 Misal didefinisikan y = proporsi waktu pemain P2 yang digunakan untuk memainkan strategi ke 1. Dengan 0 ≤ ≤ 1. Maka proporsi waktu (probabilitas) yang diperlukan untuk memainkan strategi pada kolom kedua adalah 1-y, sehingga jumlah semua proporsi waktu yang diperlukan untuk memainkan seluruh strateginya adalah y + (1-y) = 1.

Pemain P1 x 1-x

i/j 1 2

Pemain P2 y 1 5 1

Selanjutnya, akan dihitung besarnya nilai x dan y.

1-y 2 3 4



Langkah 1: Menentukan strategi campuran optimum pemain P1 Perhatikan pemain P1 yang secara logika akan membagi permainannya antara baris ke 1 dan 2 sedemikian rupa sehingga ia akan mencapai kemenangan yang sama, baik apabila pemain P2 memainkan kolom 1 atau 2. Perhatikan tabel kemenangan harapan (rata-rata kemenangan) pemain P1 berikut.

P1 memainkan strategi ke 1, x kali P1 memainkan strategi ke 2, (1-x) kali Total kemenangan harapan P1

Ketika P2 memainkan strategi ke 1 P1 menang 5 unit, x kali P1 menang 1 unit, (1-x) kali

Ketika P2 memainkan strategi ke 2 P1 menang 3 unit, x kali P1 menang 4 unit, (1-x) kali

5x + 1(1-x)

3x + 4(1-x)

Bagi pemain P1, agar dapat mencapai strategi optimum, maka perlu menyamakan kemenangan harapan yang diperoleh ketika pemain P2 memainkan strategi ke 1, yaitu [5x + (1-x)], dengan kemenangan harapan yang diperoleh ketika pemain P2 memainkan strategi ke 2, yaitu [3x + 4(1x)]. Dengan demikian, berarti bahwa: 5x + (1-x) = 3x + 4(1-x) 5x – x – 3x + 4x = 4 – 1 5x = 3 x = 3/5 Sehingga x1* = 3/5, dan x2* = 1- 3/5 = 2/5. Jadi, strategi campuran optimum pemain P1 adalah

3 2 x *   ,  . Dengan demikian, strategi campuran yang optimum bagi pemain P1 dicapai jika ia 5 5 menggunakan 3/5 waktunya untuk memainkan strategi ke 1 (baris ke 1) dan 2/5 waktunya untuk memainkan strategi ke-2 (baris ke 2). Langkah 2: Menentukan strategi campuran optimum pemain P2 Selanjutnya, akan dicari strategi campuran optimum pemain P2 yang penalarannya sama dengan pemain P1, yaitu akan membagi permainannya antara kolom ke 1 dan ke 2 sedemikian rupa sehingga ia akan mencapai kemenangan yang sama, baik pemain P1 memainkan baris 1 maupun baris 2. Perhatikan tabel kekalahan harapan (rata-rata kekalahan) pemain P2.


Ketika P1 memainkan strategi ke 1 Ketika P1 memainkan strategi ke 2


P2 memainkan strategi ke 1, y kali P2 kalah 5 unit, y kali

P2 memainkan strategi ke 2, (1-y) kali P2 kalah 3 unit, (1-y) kali

Rata-rata kekalahan

P2 kalah 1 unit, y kali

P2 kalah 4 unit, (1-y) kali

y + 4(1-y)

5y + 3(1-y)

Agar pemain P2 dapat mencapai strategi optimum ia perlu menyamakan rata-rata kekalahan (kekalahan harapan) yang dideritanya ketika pemain P1 memainkan strategi ke 1, yaitu [5y + 3(1y)] dengan rata-rata kekalahan yang diderita ketika pemain P1 memainkan strategi ke 2, yaitu [y + 4(1-y)]. Dengan demikian, 5y + 3(1-y) = y + 4(1-y) 5y – 3y – y + 4y = 4 – 3 5y = 1 y = 1/5. * * Sehingga y1 = 1/5, dan y2 = 1- 1/5 = 4/5. Jadi, strategi campuran optimum pemain P2 adalah

1 4 Y *   ,  . Jadi, strategi campuran optimum bagi pemain P2 dicapai jika ia menggunakan 1/5 5 5 waktunya untuk memainkan strategi ke 1 (kolom 1) dan 4/5 waktunya untuk memainkan strategi ke 2 (kolom 2). Langkah 3: Menentukan nilai permainan Karena strategi campuran optimum kedua pemain telah didapatkan, maka akan dihitung nilai permainannya. Berkaitan dengan strategi optimum yang telah didapatkan, penyajian matriks pembayarannya adalah sebagai berikut.

Pemain P1 3/5 2/5

i/j 1 2

Pemain P2 1/5 1 5 1

4/5 2 3 4

Perhitungan nilai permainan berikut menurut pandangan P2, yaitu dengan memperhatikan setiap strategi pemain , yaitu a. Selama pemain P1 menggunakan 3/5 waktunya untuk memainkan strategi ke 1, pemain P2 kalah 5 unit sebanyak 1/5 dan 3 unit sebanyak 4/5 kali. b. Selama pemain P1 menggunakan 2/5 waktunya untuk memainkan strategi ke 2, pemain P2 kalah 1 unit sebanyak 1/5 kali dan 4 unit sebanyak 4/5 kali. Sehingga kemenangan harapan (rata-rata kemenangan) pemain P1 atau kekalahan harapan (ratarata kekalahan) pemain adalah:



2

2







V *  E ( x * , y * )   xi* aij y *j  x1* a11 y1*  a12 y 2*  x 2* a21 y1*  a22 y 2*



i 1 j 1



3  1  4  2   1   4  5.   3.   1.   4.   5  5  5  5   5   5 

3  5 12  2  1 16  3 17  2 17             5 5 5  5  5 5  5  5  5  5  17  3 2  17     . 5 5 5  5 Jadi, nilai permainan adalah 17/5. Ini berarti bahwa jika pemain P1 bermain dengan menggunakan strategi optimumnya, maka ia dapat mengharapkan kemenangan harapan (ratarata kemenangan) sebesar 17/5 unit per permainan.

Pemain P 1. Teorema 4.1 (Teorema minimax). Untuk setiap matriks pembayaran (pay off matrix), terdapat strategi optimal x* dan y* sedemikian sehingga

Recommend Documents