Bab III Analisis Rantai Markov Sistem Markov (atau proses Markov atau rantai Markov) merupakan suatu sistem dengan satu atau beberapa state atau keadaan, dan dapat berpindah dari satu state ke state yang lain pada setiap tahapan waktu menurut probabilitas tertentu. Rantai Markov dapat digunakan untuk memodelkan permainan berulang. Analisis rantai Markov merupakan cara umum pemodelan permainan berulang, tetapi pemain hanya dapat membawa informasi dari permainan satu tahap sebelumnya.
Berbagai eksperimen telah menunjukkan bahwa serangkaian percobaan akan membentuk suatu proses trial independen, kemungkinan hasil dari tiap eksperimen akan sama dan muncul dengan probabilitas yang sama. Lebih jauh lagi, pengetahuan tentang hasil eksperimen sebelumnya tidak mempengaruhi hasil eksperimen berikutnya.
Teori probabilitas modern mempelajari proses percobaan dengan hasil percobaan sebelumnya mempengaruhi prediksi hasil percobaan berikutnya. Sebagai contoh, prestasi seorang mahasiswa dapat diprediksi berdasarkan hasil serangkaian ujian yang telah diselesaikan. Tetapi memperbolehkan generalitas seperti ini akan membuat hasil yang general sangat sulit dibuktikan. Pada tahun 1907, A.A. Markov memulai studi penting tentang rantai proses jenis baru. Dalam proses ini, hasil eksperimen yang diberikan dapat mempengaruhi hasil eksperimen berikutnya. Jenis proses ini disebut rantai Markov.
III.1 Menentukan Rantai Markov
Rantai Markov digambarkan sebagai berikut: terdapat satu set keadaan, S = {s 1 , s 2 , …, s r }. Proses berawal dari salah satu state atau keadaan ini dan bergerak secara berturut-turut dari satu keadaan ke keadaan lain. Setiap pergerakan disebut step atau langkah. Jika rantai berada pada state s i , maka kemudian akan bergerak ke state s j pada tahap berikutnya dengan probabilitas p ij , dan probabilitas ini tidak bergantung pada state sebelum sekarang. Probabilitas p ij disebut probabilitas
22
transisi. Proses dapat tetap berada pada state yang sama, dan hal ini muncul dengan probabilitas p ii . Contoh penggunaan rantai Markov adalah pada perkiraan cuaca. Misalkan di suatu daerah tidak pernah mendapatkan cuaca cerah dalam dua hari berturut-turut. Jika hari ini cuaca cerah, maka keesokan harinya kemungkinan akan turun hujan atau salju. Jika hari ini hujan atau bersalju, maka terdapat peluang yang sama untuk terjadi cuaca yang sama pada hari berikutnya. Perubahan cuaca menjadi hujan atau salju memiliki peluang yang sama untuk berubah menjadi cuaca cerah. Dengan informasi ini kita dapat membuat rantai Markov. Kondisi cuaca dibuat sebagai state yaitu hujan (R), cerah (N), dan salju (S). Dari informasi sebelumnya dapat ditentukan probabilitas transisi. Cara yang paling sesuai untuk merepresentasikan rantai Markov ini adalah dengan menggunakan array seperti di bawah ini.
III.2 Matriks Transisi
Entri pada baris pertama matriks P pada contoh sebelumnya merepresentasikan probabilitas untuk berbagai jenis cuaca sehari setelah hari hujan. Demikian pula entri pada baris kedua dan ketiga merepresentasikan berbagai jenis cuaca yang mengikuti hari cerah dan bersalju. Matriks persegi seperti ini disebut matriks transisi atau matriks probabilitas transisi.
Jika diberikan bahwa hari ini rantai berada pada state i, dan akan berada pada state j dua hari yang akan datang, probabilitasnya ditunjukkan dengan p(2) ij . Pada contoh sebelumnya, dapat dilihat bahwa jika hari ini hujan, maka kejadian bahwa lusa akan turun salju merupakan disjoint union dari tiga kejadian berikut: 1. besok akan hujan dan lusa akan turun salju. 2. besok cuaca cerah dan lusa akan turun salju.
23
3. besok dan lusa akan turun salju. Probabilitas kejadian pertama merupakan hasil perkalian probabilitas kondisional dari probabilitas besok hujan jika diketahui hari ini hujan dengan probabilitas kondisional lusa turun salju jika diketahui besok hujan. Dengan menggunakan matriks transisi P, perkalian tersebut dapat ditulis sebagai p 11 p 13 . Dua kejadian lainnya juga dapat dinyatakan sebagai perkalian entri matriks P. Sehingga dapat dituliskan p(2) 13 = p 11 p 13 + p 12 p 23 + p 13 p 33 Persamaan ini mengingatkan pada perkalian titik antara dua vektor; yaitu melakukan perkalian titik antara baris pertama matriks P dengan kolom ketiga matriks P. Secara umum, jika suatu rantai Markov memiliki state sebanyak r, maka p(2) ij =
r
∑p k =1
ik
p kj .
Pembahasan berikutnya adalah tentang tingkah laku jangka panjang dari rantai Markov ketika berawal dari suatu state yang dipilih dengan distribusi probabilitas pada set keadaan, yang disebut vektor probabilitas. Suatu vektor probabilitas dengan r komponen merupakan vektor baris yang entrinya tidak negatif dan jumlahnya 1. Jika u merupakan vektor probabilitas yang merepresentasikan keadaan awal dari rantai Markov, maka komponen ke-i dari u merepresentasikan probabilitas rantai berawal dari keadaan s i . Misalkan P merupakan matriks transisi dari suatu rantai Markov, dan u merupakan vektor probabilitas yang merepresentasikan distribusi awal, maka probabilitas rantai akan berada pada state i setelah n tahapan merupakan entri ke-i pada vektor u(n) = uPn.
Jika pada contoh sebelumnya digunakan vektor probabilitas awal u = (1/3 1/3 1/3), maka dapat dihitung distribusi keadaan pada hari ketiga sebagai berikut. 0,406 0,203 0,391 u(3) = uP3 = (1/3 1/3 1/3) 0,406 0,188 0,406 = (0,401 0,188 0,401) 0,391 0,203 0,406
24
III.3 Rantai Markov Berabsorbsi
Suatu state penyerap (absorbing state) merupakan suatu keadaan dengan probabilitas keluar dari keadaan tersebut adalah nol.
Suatu sistem Markov
berabsorbsi merupakan suatu sistem Markov yang memuat minimal satu keadaan penyerap, dan memungkinkan untuk berpindah dari setiap keadaan non-absorbsi ke keadaan absorbsi dalam satu atau beberapa tahapan waktu. Dalam menganalisis suatu sistem berabsorbsi, keadaan diberi nomor sedemikian sehingga keadaan penyerap menjadi urutan terakhir. Matriks transisi P untuk sistem berabsorbsi akan tampak sebagai berikut: [ S ] [T ] P= [0] [ I ] I merupakan matriks identitas berukuran m x m (m adalah jumlah keadaan penyerap), S merupakan matriks persegi berukuran (n - m) x (n – m) dengan n merupakan jumlah total keadaan sehingga n-m adalah jumlah keadaan nonabsorbsi, 0 merupakan matriks nol, dan T merupakan matriks berukuran (n – m) x m. Matriks S memberikan probabilitas transisi untuk pergerakan di antara keadaan non absorbsi. Matriks fundamental untuk sistem berabsorbsi adalah matriks yang didapatkan dari perhitungan berikut. Q = (I – S)-1 Matriks ini diperlukan dalam perhitungan jumlah langkah yang dibutuhkan untuk mencapai keadaan penyerap. Sebuah contoh pembentukan matriks transisi pada rantai Markov berabsorbsi adalah sebagai berikut. Misalkan terdapat diagram transisi seperti gambar berikut.
Gambar III. 1 Diagram Transisi Sebuah Sistem Markov Berabsorbsi
25
Keadaan 3 dan 4 adalah keadaan penyerap (diberi urutan nomor terakhir), maka matriks transisi untuk sistem Markov berabsorbsi ini adalah seperti di bawah ini.
Untuk mendapatkan waktu absorbsi dalam sistem Markov berabsorbsi, dilakukan perhitungan matriks fundamental Q. 0,75 0 Q = (I – S) = − 0,2 0,8 -1
−1
4/3 0 = 1/ 3 5 / 4
Jika berangkat dari keadaan i, maka jumlah tahapan yang diharapkan untuk mencapai state j sebelum absorbsi adalah entri ij dari matriks Q. Sebagai contoh, jika berangkat dari keadaan 2, dan ingin menuju keadaan 1 sebelum absorbsi, maka jumlah tahapan yang diharapkan adalah entri (2,1) dari matriks Q yaitu 1/3. Dengan kata lain, dari keadaan 2, diharapkan singgah di keadaan 1 dengan waktu rata-rata 1/3 kali sebalum absorbsi.
Perkalian matriks QT menghasilkan probabilitas berakhir di berbagai keadaan penyerap. Misalkan jika baris ke-i dari matriks QT adalah [x y z t], maka berawal dari keadaan i, terdapat probabilitas sebesar x berakhir di keadaan penyerap pertama, probabilitas sebesar y berakhir di keadaan penyerap kedua, dan seterusnya.Pada contoh sebelumnya, hasil perkalian matriks QT adalah 2 / 3 1/ 3 QT = 1/ 6 5 / 6 Entri baris kedua adalah [1/6 5/6], hal ini berarti jika berangkat dari keadaan 2, terdapat satu di antara enam kesempatan untuk berakhir di keadaan penyerap pertama yaitu keadaan 3, dan lima dari enam kesempatan berakhir di keadaan penyerap kedua yaitu keadaan 4.
26
Bab IV Replikator Dinamik IV.1 Persamaan Replikator Waktu Diskrit Persamaan replikator umumnya juga digunakan untuk menganalisis dinamik dari permainan berulang, khususnya di bidang biologi. Persamaan replikator untuk probabilitas pemain menggunakan strategi ke-i dituliskan sebagai x i = αxi (π i − πˆ ) dengan xi
: probabilitas pemain menggunakan strategi ke-i
x i
: turunan waktu dari x i
α
: koefisien untuk persamaan replikator
πi
: payoff untuk pemain yang menggunakan strategi ke-i
πˆ
: payoff rata-rata semua strategi (= π 1 x 1 + π 2 x 2 + … + π n x n , untuk n strategi)
Tidak seperti pada bab sebelumnya, kali ini pemain dapat menggunakan strategi campuran, dan selama lelang berulang, probabilitas menggunakan setiap strategi berubah.
Asumsikan bahwa satu kali lelang merupakan satu tahapan waktu, sehingga suatu persamaan replikator waktu diskrit dapat diturunkan. Strategi diurutkan dari payoff yang paling kecil, sehingga jika terdapat n strategi, maka π 1 ≤ π 2 ≤ … ≤ π n . Selama lelang berulang, pemain yang menggunakan strategi ke-i dapat menyadari bahwa strategi ke-j lebih baik daripada strategi ke-i dan kemudian mengubah strateginya menjadi strategi ke-j. Probabilitas pemain mengubah strategi menjadi strategi ke-j pada lelang berikutnya diberikan oleh persamaan berikut: p ij = βx j (π j – π i ) , jika π j > π i p ij = 0 , pada kondisi lainnya β merupakan koefisien untuk persamaan replikator, nilainya harus cukup kecil untuk menjamin bahwa setiap p ij lebih kecil atau sama dengan 1, dan
∑
n j =i +1
pij ≤ 1 untuk semua i. Semakin sering pemain menggunakan strategi ke-j
27
dan semakin besar perbedaan antara π i dan π j , maka pemain akan lebih senang menggunakan strategi ke-j.
Jika diberikan probabilitas x i (t) yaitu probabilitas pemain menggunakan strategi ke-i pada saat t, dapat dituliskan: i −1
x i (t + 1) = x i (t) +
∑p j =1
n
ji
x j (t ) − xi (t ) ∑ pij j =i +1
i
n
j =1
j =i +1
= xi (t ) + xi (t )∑ β (π i − π j ) x j (t ) − xi (t ) ∑ β (π j − π i ) x j (t ) n
= xi (t ) + βxi (t )∑ x j (t )(π i − π j ) j =1
= xi (t ) + βxi (t )(π i − πˆ ) p ji merupakan probabilitas berganti strategi dari strategi j ke strategi i (π j < π i ), x j (t) adalah probabilitas pemain menggunakan strategi j pada saat t, p ij adalah probabilitas berganti strategi dari i ke j (π j > π i ), dan x i (t) adalah probabilitas pemain menggunakan strategi i pada saat t.
Dengan menerapkan persamaan replikator waktu diskrit ini, keterbatasan rantai Markov dalam representasi perubahan strategi dapat diatasi.
IV.2 Aplikasi Replikator Dinamik dalam Lelang Berulang
Contoh perhitungan lelang berulang dengan menggunakan replikator dinamik ini telah diterapkan dalam penelitian tesis analisis teori permainan pada pasar listrik[]. Dalam model perhitungan, suatu perusahaan P0 mengumumkan keinginan untuk membeli listrik sebesar d MWh dengan harga maksimum yang diterima (P) sebesar 12. Dua perusahaan P1 dan P2 menawarkan untuk menjual listrik sebesar d MWh kepada P0. Kedua perusahaan ini memiliki kapasitas pembangkitan yang cukup untuk mensuplai energi listrik kepada P0. Biaya pembangkitan P1 dan P2 masing-masing adalah c 1 = 5 dan c 2 = 7. Harga penawaran masing-masing adalah p 1 dan p 2 , asumsikan juga harga penawaran diskrit dengan interval 1. Maka harga penawaran yang bisa dilakukan P1 adalah
28
c 1 + i (i= 1, 2, 3, 4, 5, 6), dan harga penawaran P2 adalah c 2 + i (i = 1, 2, 3, 4). Jika p1 = p2, P1 dan P2 masing-masing menjual sebesar d/2 MWh listrik kepada P0 dengan harga listrik adalah
p1 . Asumsikan biaya yang diperlukan untuk menjual d/2 MWh 2
c c1 dan 2 . Jika salah satu perusahaan menawarkan listrik dengan 2 2
harga yang lebih rendah, maka perusahaan tersebut yang berhak menjual d MWh listrik kepada P0. Payoff yang didapatkan masing-masing pemain untuk setiap strategi adalah harga penawaran dikurangi dengan biaya pembangkitan. Dari permainan ini dapat dibuat matriks payoff permainan sebagai berikut.
Tabel IV. 1 Matriks Payoff Permainan Lelang 8 Strategi P1 (p1)
7 (2, 0) 8 (1.5, 0.5) 9 (0, 1) 10 (0, 1) 11 (0, 1)
Strategi P2 (p2) 9 10 (2, 0) (2, 0) (3, 0) (3, 0) (2, 1) (4, 0) (0, 2) (2.5, 1.5) (0, 2) (0, 3)
11 (2, 0) (3, 0) (4, 0) (5, 0) (3, 2)
Ekuilibrium Nash dari permainan ini adalah strategi (p 1 , p 2 ) = (7, 8), sedangkan strategi Pareto efisien adalah (p 1 , p 2 ) = (10, 11), (11, 10), (11, 11). Perhitungan replikator dinamik dilakukan dengan menggunakan software MATLAB® (source code terdapat pada Lampiran). Asumsikan jika lelang pertama diawali dengan distribusi probabilitas pemilihan strategi mendekati efisien Pareto.
Tabel IV. 2 Distribusi Probabilitas Pemilihan Strategi Permainan Strategi P1 P2
7 0.0001 -
8 0.0001 0.0001
9 0.0001 0.0001
10 0.0001 0.0001
11 0.9996 0.9997
Evolusi dari perkembangan strategi dapat diamati sebagai berikut. Pada lelang pertama, payoff (dilambangkan dengan notasi π) untuk P1 adalah
29
π (7) 2,0000 π (8) 2,9999 π (9) = 3,9994 π (10) 4,9988 π (11) 2,9991 Dengan π(7) adalah payoff yang didapatkan P1 ketika menggunakan strategi p 1 = 7. Dapat dilihat bahwa π(10) lebih besar dari π(11). Karena P2 memilih strategi p 2 = 11 dengan probabilitas 0,9997, P1 dan P2 akan seri dengan probabilitas 0,9997 jika P1 memilih strategi p 1 = 11. Strategi ini memberikan payoff sebesar u 1 = 3 untuk P1. Jika P1 mengambil strategi p 1 = 10, P1 menang terhadap P2 dengan probabilitas 0,9997 dan mendapat payoff u 1 = 5. Efisiensi Pareto tidak menjamin optimalitas individu, dan dalam kasus ini P1 bisa mendapat payoff lebih tinggi dengan menurunkan harga penawarannya. Dengan alasan ini, P1 akan menggeser strategi dari p 1 = 11 ke p 1 = 10. Jika pada titik ini P1 mengetahui bahwa payoff yang bisa didapat pada ekuilibrium Nash hanya sebesar u 1 = 2, P1 kemungkinan akan lebih memilih u 1 = 3 dengan memilih p 1 = 11. Tetapi pada awalnya P1 tidak mengetahui ekuilibrium Nash, maka tidak ada yang menghalangi P1 untuk menggeser strategi dari p 1 = 11 menjadi p 1 = 10. Untuk P2, payoff yang didapatkan pada lelang pertama adalah π (8) 0,9999 π (9) 1,9995 = π (10) 2,9989 π (11) 1,9992 Penjelasan yang sama berlaku untuk P2. P2 mendapat payoff u 2 = 0 pada ekuilibrium Nash, sehingga menggeser strategi dari p 2 = 11 menjadi p 2 = 10 merupakan evolusi strategi yang beresiko bagi P2, karena akan mengakibatkan P1 menurunkan lagi harga penawarannya. Tetapi P2 tidak mengetahui bahwa biaya pembangkitannya lebih besar dari P1, sehingga P2 akan mengubah strategi dari p 2 = 11 menjadi p 2 = 10. Observasi di atas menunjukkan kesulitan dalam menjaga pemain tetap pada strategi Pareto efisien ketika terdapat banyak penjual dalam lelang. Dalam model
30
yang diasumsikan dalam penelitian ini, pemain tidak memiliki informasi tentang pemain lain. Dalam lelang sebenarnya, kemungkinan pemain memiliki informasi tentang pemain lain dari data historis atau kondisi yang diinformasikan kepada pemain lain. Informasi ini dapat memberikan petunjuk bagi pemain untuk memprediksikan ekuilibrium Nash.
Setelah 500 kali lelang, evolusi strategi dari (p 1 , p 2 ) = (11, 11) ke (p 1 , p 2 ) = (10, 10) dapat dilihat pada tabel di bawah ini.
Tabel IV. 3 Distribusi Probabilitas Setelah 500 Lelang
Strategi P1 P2
7 0.0000 -
8 0.0000 0.0000
9 0.0161 0.1198
10 0.9839 0.8506
11 0.0000 0.0296
Pada titik ini, payoff untuk P1 adalah π (7) 2,0000 π (8) 3,0000 π (9) = 3,7627 π (10) 2,2796 π (11) 0,0914 Payoff P2 adalah π (8) 1,0000 π (9) 1,9839 = π (10) 1,4758 π (11) 0,0000 Karena π(9) lebih besar dari π(10) untuk P1 dan P2, maka kedua pemain akan menggeser strategi dari (p 1 , p 2 ) = (10, 10) menjadi (p 1 , p 2 ) = (9, 9). Pengulangan evolusi strategi ini akan mengarahkan P1 dan P2 ke ekuilibrium Nash. Dan setelah 10.000 kali lelang, distribusi probabilitas akan menghasilkan probabilitas satu pada strategi ekuilibrium Nash seperti pada tabel berikut.
Tabel IV. 4 Distribusi Probabilitas Setelah 10000 Lelang
Strategi P1 P2
7 1.0000 -
8 0.0000 1.0000
9 0.0000 0.0000
31
10 0.0000 0.0000
11 0.0000 0.0000
