teori permainan
Post on 08-Jan-2016
24 Views
Preview:
DESCRIPTION
TRANSCRIPT
-
Teori Permainan
- Teori permainan berurusan dengan situasi keputusan di mana dua
orang bertentangan yang mempunyai kepandaian mempunyai tujuan
yang bertentangan
- Contoh tipikal a.l. melemparkan kampanye iklan untuk produk-produk
yang bersaing dan perang strategi dari tentara yang berlawanan
Dalam suatu permainan konflik, kedua pemain yang bertentangan
masing-masing akan mempunyai sejumlah alternatif atau strategi
(yang terbatas atau tidak terbatas). Pada setiap pasangan strategi
terkait hasil (payoff), yaitu seorang pemain membayar kepada
pema!n lainnya.
-
Permainan seperti itu dikenal sebagai Permainan dua orang dengan
jumlah nol (two-person zero-sum game) karena keuntungan yang
diperoleh oleh seorang pemain merupakan kerugian bagi pemain
lainnya. Dalam hal Ini adalah cukup untuk meringkas permainan
melaiui pendapatan seorang pemain saja Rancangan dua pemain A
dan B dengan m x n strategL ditunjukkan oleh matriks hasil dari
pemain A sebagai berikut :
-
B1 B2 . . . . Bn A1
A2
.
.
Am
a11
a21
.
.
am1
a12
a22
.
.
am2
. . . . a1n
a2n
.
.
amn
Representasl di atas menunjukkan bahwa jika A menggunakan
strategi i dan B menggunakan strategi j. hasil A adalah aij , yang
berarti hasil B adalah -aij.
-
1. Penyelesaian optimal dari permainan dua pemain dengan jumlah nolI Two-person zero-sum games
Karena permainan berakar pada pertentangan kepentingan,
penyelesaian optimal adalah memilih satu atau lebih strategi bagi
setiap pemain sedemikian bahwa setiap perubahan dalam strategi
yang terpilih tidak memperbaiki hasil dari kedua pemain.
Penyelesa!an ini dalam bentuk strategi tunggal atau beberapa
strategi campuran sesuai dengan peluang yang spesifik. Dua contoh
berikut mendemonstrasikan dua buah kasus.
-
Contoh 1
Perusahaan A dan B masing-masing menjual sebuah produk.
Perusahaan A mengiklankan di radio (A1), televisi (A2) dan surat
kabar (A3). Perusahaan B selain mengiklankan di radio (B1), televisi
(B2) dan surat kabar (B3) juga menggunakan brosur (B4).
Berdasarkan pengaruh dan intensitas kampanye, setiap perusahaan
dapat merebut sebagian dari pasar satu dengan lainnya.Matriks
berikut meringkas persentase perolehan atau kehilangan pasar dari
perusahaan A.
-
B1 B2 B3 B4 Terendah baris
A1 8 -2 9 -3 -3
A2 6 5 6 8 5 Maksimin
A3 -2 4 -9 5 -9
Tertinggi kolom
8 5 9 5
maksimaks
Penyelesaian dari permainan ini Berdasarkan pada prinsip
memastikan keputusan yang terbaik di antara yang terburuk bagi
setiap pemain.
-
Jika perusahaan A memilih strategl A1, maka apapun yang dipilih
oleh B, hal terburuk yang terjadi pada A adalah kehiiangan 3 % dari
pangsa pasar beralih ke B.
Sama halnya jika A memilih strategi A2, hasil yang terburuk adalah
memperoleh 5 % dari pangsa pasar B,
dan jika A memilih strategi A3, hasil yang terburuk adalah kehilangan
9 % dari pangsa pasar beralih ke B.
Dengan demikian A akan memilih strategi yang memberikan yang
terbaik di antara yang terburuk (Maksimin) yaitu strategi A2
-
Selanjutnya bagi B tabel matriks tersebut merupakan nilai
penyesalannya.
Dengan demikian B akan mencari penyesalan yang terendah di
antara penyesalan yang ada (Minimaks), yaitu strategi B2
Penyelesaian optimal dari permainan meminta pemilihan strategi A2
dan B2, yang berarti kedua perusahaan harus menggunakan iklan
televisi. Hasil akan menguntungkan perusahaan A karena pangsa
pasarnya naik sebesar 5 %. Dalam hal ini kita katakan nilai
permainan adalah 5 %, dan perusahaan A dan B menggunakan
penyelesaian titik pelana (Sadle-point)
-
Penyelesaian sadle-point menjamin tidak ada dari kedua perusahaan
mencoba mencari penyelesaian yang lebih baik Misalnya jika B
pindah ke strategi yang lain (B1. B3. B4), A akan tetap pada strategi
A2, hal tersebut akan mengakibatkan B akan lebih merugi yaitu
kehilangan pangsa pasarnya ke 6% atau 8%.
Sebaliknya A juga tidak akan pindah ke strategi lannya misalnya A3,
karena B dapat pindah ke B3 di mana B akan meningkat pangsa
pasarnya sebesar 9%. Kesimpulan yang sama jika A pindah ke A1.
Penyelesaian optimal sadle-point dari permainan tidak perlu
merupakan strategi baku
Sebagai gantinya penyelesaian mungkin memerlukan penggabungan
dua atau lebih strategi secara acak seperti pada contoh berikut :
-
Contoh 2:
A dan B bermain lempar koin. Setiap pemain tidak mengetahui satu
sama lain. mernilih head (H) atau tail (T). Kedua pernain akan
melempar koin secara bersamaan. Jika yang keluar HH atau TT A
menerima $ 1 dari B, sebaliknya jika yang keluar HT B akan
menerima $ 1 dari A.
Matriks hasil berikut untuk pemain A sebagai berikut :
BH BT Terendah baris
AH 1 -1 -1
AT -1 1 -1
Tertinggi kolom 1 1
-
Nilai maksimin dan minimaks dari pemainan adalah - $ 1 dan $ 1.
Karena kedua nilai tersebut tidak sama, permainan tidak mempunyai
sebuah strategi penyelesaian yang baku.
Jika AH, digunakan oleh pemain A, maka pemain B akan memilih BT
untuk menerima $ 1 dari A Jika hal tersebut terjadi A dapat pindah ke
strategi A2 untuk mebalik hasil permainan dan menerima $ 1 dari B.
Keinginan selanjutnya dari kedua pemain untuk mengganti strategi
lain menunjukkan bahwa strategi yang baku tidak diterima.
Kedua pemain secara acak harus menggunakan gabungan yang
tepat untuk untuk strategi masing-masing.
-
Dalam kasus ini nilai optimal dari permainan akan diperoleh antara
nilai maksimm dan minimaks permainan. yaitu .
Nilai Maksimin < nilai permainan < Nilai maksimin (yang lebih rendah) (yang lebih tinggi)
2. Penyelesaian Permainan dengan Strategi Campuran
Permainan dengan strategi campuran dipecahkan baik dengan
secara grafis atau dengan programa linier
Penyelesaian secara grafis sesuai dengan permainan dengan paling
sedikit satu pemain yang harus mempunyai dua strategi baku (pure
strategies).
-
Methoda ini sangat menarik karena menjelaskan ide dari pada
"saddle-point" secara grafis. Programa linier dapat dipakai untuk
memecahkan semua permainan "two-person zero-sum"
Penyelesaian permainan secara grafis.
Kita mulai dengan kasus permainan (2 x n) di mana pemain A
mempunyai dua strategi
y1 B1
y2 B2
yn Bn
x1 A1 a11 a12 . . . . a1n
1-x1 A2 A21 A22 . . . . A2n
-
Permainan ini mengasumsikan bahwa pemain A mengkombinasikan
strategi A1 dan A2 dengan masing masing peluang x1 dan 1- x1,
0 < x1 < 1.
Pemain B menggabungkan strategi B1 sampai Bn dengan peluang
y1, y2, . . . , yn di mana yj > 0 untuk j = 1, 2, . . . , n dan
y1 + y2 + . . . . + yn = 1.
Dalam kasus ini pemain A diharapkan mempeoleh keuntungan
terhadap strategi strategi baku B ke j diperoleh dari :
a1jx1 + a2j(1-x1) (a1j a2j)x1 + a2j di mana j = 1, 2, . . . . , n
-
Jadi pemain A ingin memperoleh nilai dari x1 yang memaksimumkan
minimum perkiraan keuntungan yaitu
max min {(a1j - a2j) x1 + a2j}
Contoh 3
Perhatikan permainan 2 x 4 berikut. Keuntungan untuk pemain A
Permainan ini tidak mernpunyai penyelesaian strategi baku dan
strategl yang ada harus di campurkan. Pemaln A rnernpunyai
keuntungan terhadap pemain B yang memiliki strategi baku sbb
B1 B2 B3 B4 A1 2 2 3 -1 A2 4 3 2 6
-
Penyelesaian :
Permainan di atas tidak mempunyai penyelesaian strategi murni.
Hasil yang diharapkan oleh pemain A jika B memainkan strategi
murni diberikan di bawah ini :
Strategi murni B Hasil yang diharapkan A
1 -2x1 + 4
2 -x1 + 3
3 x1 + 2
4 - 7x1 + 6
-
Gambar berikut menunjukan gambar empat garis lurus yang
berkaitan dengan strategi baku pemain B.
-
Untuk mendapatkan yang paling baik diantara yang buruk, sampul
yang paling rendah dari keempat garis tersebut merepresentasikan
keuntungan yang minimum (terburuk) untuk pemain A, apapun yang
dilakukan pemain B.
Sampul maksimum (terbaik) berhubungan dengan titik penyelesaian
maksimin pada x1 = 0,5
Titik ini adalah perpotongan dari garis ke 3 dan ke 4. Pemain A
mempunyai penyelesaian optimal dengan mencampurkan/
rnenyatukan A1 dan A2 dengan peluang 0,5 dan 0,5. Hubungan
antara nilai nilai di permainan ini, v yang diperoleh dengan
memasukkan nilai x1 = 0,5 ke dalam fungsi garis ke 3 atau ke 4 yang
menghasilkan . v = - 0,5 + 3 = 2,5 atau v = -7 x 0,5 + 6 = 2,5
-
Optimalisasi campuran Pemain B dilakukan dengan dua strategi
yang didefinisikan oleh sampul yang paling rendah pada gambar.
Ini artinya pemain B dapat mencampurkan strategi B3 dan B4 yang
mana pada kasus y1 = y2 = 0 dan y4 = 1 - y3. Sebagai hasilnya,
perkiraan keuntungan pemain B terhadap pemain A dengan strategi
baku sbb :
Strategi murni A Hasil yang diharapkan B
1 4y3 - 1
2 - 4y3 + 6
-
Penyelesaian yang terbaik dari yang terburuk untuk pernain B adalah
titik minimum pada upper envelope (sampul atas) dari 2 garis
tersebut. Proses ini sama dengan memecahkan persamaan :
4y3 - 1 = - 4y3 + 6
Penyelesaian ini memberikan y3 = 7/8, yang menghasilkan nilai
perrnainan v = 4 x (7/8) 1 = 2,5
Penyelesaian dari permainan ini membuat pemain A untuk
mengkombinasikankan A1 dan A2 dengan peluang yang sarna dan
pemain B untuk mengkombinasikan B3 dan B4 dengan peluang7/8
dan 1/8.
-
Untuk permainan dimana pemain A mempunyai m strategi dan
pemain B menpunyai dua strategi, situasi ini dapat di selesaikan
dengan cara yang sama. Perbedaan yang paling besar adalah kita
akan menggambarkan nilai yang diharapkan pemain B terhadap
strategi baku pemain A. Untuk hasilnya, kita akan mencari nilai
minimaks dan bukannya maksimin dari titik di sampul atas dari
gambar garis yang ada.
-
Penyelesaian permainan menggunakan programa linier
Teori permainan menunjang hubungan yang kuat dengan program
linear, dengan kata lain bahwa two-person zero-sum game dapat
diekspresikan sebagai program linear dan sebaliknya.
G. Dantzig (1963, p.24) menunjukkan bahwa ketika bapak teori
permainan J. von Neumann, ketika pertama kali memperkenalkan
metode simpleks pada tahun 1947, secara langung mengenali
hubungan ini dan lebih jauh menekankan konsep 'duality' dalam
program linear. Bagian ini menggambarkan solusi perrnainan oleh
program linear.
-
Peluang optimal pemain A xi, i = 1, 2, . . . . ,m, dapat ditentukan
dengan memecahkan masalah maksimin dibawah ini,
Maks {min
= = =
m
i
m
i
m
iiiniii xaxaxa
1 1 1121 ,......,, }
x1+ x2 + . . . . . .+ xm = 1
xi > 0 i = 1, 2, . . . . , m
untuk mengubah persoalan ini ke programa iinier kita misalkan :
v = min
= = =
m
i
m
i
m
iiiniii xaxaxa
1 1 1121 ,......,,
persamaan ini menghasilkan :
=
m
iiij xa
1> v j = 1, 2, . . . . , n
-
Persoalan pemain A dapat ditulis sebagai :
Maks.Z = v
d. k. v - =
m
iiij xa
1< 0 j = 1, 2, . . . . , m
x1+ x2 + . . . . . .+ xm = 1
x1 > 0 i = 1, 2 ... , m
v tidak terbatas pada tanda
-
Startegi optimal pemain B y1, y2, . . . dan yn ditentukan dengan
membahas persoalan:
Min.{maks.( jj
j ya 1 , jj
j ya 2 , . . . . ., jj
mj ya )}
y1+ y2 + . . . . . .+ yn = 1
Dengan menggunakan cara yang sama diperoleh :
Min. W = v
d. k. v - =
n
jjij ya
1> 0 i = 1, 2, . . . . , m
y1+ y2 + . . . . . .+ yn = 1
yj i = 1, 2 ... , m
v tidak terbatas pada tanda
-
Kedua masalah ini mengoptimalkan variabel yang sama
(unrestricted) v, yang merupakan nilai dari permainan. Alasannya
adalah bahwa masalah B adalah pasangan dari masalah A (anda
diminta untuk membuktikan hal ini dalam problem 14.5c-6
menggunakan definisi berpasangan dalam bab 4). Hal ini berarti
bahwa solusi optimal dari satu masalah secara otomatis
menghasilkan solusi optimal bagi yang lain.
top related