BAB II DASAR TEORI
Perkembangan zaman telah membuat hubungan manusia semakin kompleks. Interaksi antar kelompok-kelompok yang mempunyai kepentingan berbeda kemudian melahirkan konflik untuk mempertahankan kepentingan masingmasing. Untuk penyelesaian masalah ini diperlukan sebuah kajian mendalam yang melibatkan berbagai aspek keilmuan.
Dalam perkembangannya, konflik sosial yang terjadi bisa juga didekati dengan pendekatan matematis. Untuk melihat sebuah fenomena yang melibatkan banyak variabel dan terjadi secara berulang-ulang, diperlukan suatu pendekatan pemodelan yang dinamakan sistem dinamik. Salah satu teori sistem dinamik yang cocok untuk memodelkan konflik sosial adalah theory of moves yang merupakan salah satu pengembangan dari classic games theory.
2.1 Definisi Game Theory
Games theory secara keilmuan berakar dari hasil kerja von Neumann dan Morgensten (von Neumann and Morgensten, 1944). Games theory merupakan salah satu fokus ilmu matematika dalam strategi pengambilan keputusan pada interaksi sosial. Teori ini menggambarkan situasi dimana dua atau lebih orang (disebut pemain) masing-masing akan memilih dua atau lebih tindakan yang disebut strategi. Kemungkinan dari output yang dihasilkan bergantung kepada pilihan yang dibuat oleh semua pemain.
5
2.1.1 Games Strategis Games strategis adalah model untuk menghasilkan keputusan dimana terdiri dari N pemain, salah satu pemain memilih aksinya. Pilihan aksi pemain hanya boleh dilakukan satu kali dan tidak bisa diubah lagi setelah itu. Definisi : Games Strategis adalah 〈 N , ( Ai ), (π i )〉 dimana N adalah jumlah pemain, Ai adalah himpunan berhingga dari aksi yang diambil oleh pemain i, dan π i adalah pilihan yang diinginkan oleh pemain i. Dalam pembahasannya pilihan yang diiinginkan akan diganti dengan fungsi
payoff
u i : A → ℜ . Setiap pemain akan memaksimalkan nilai payoff-nya.
Sehingga games strategis akan di definisikan dengan: 〈 N , ( Ai ), (u i )〉
2.1.2 Pareto Optimal
Outcome a ∈ A dari game 〈 N , ( Ai ), (u i )〉 adalah Pareto Optimal jika tidak terdapat outcomes lainnya b ∈ A yang membuat setiap pemain setidaknya sama baiknya dengan pemain lain yang lebih baik.
Definisi : Outcome a adalah Pareto Optimal jika tidak ada outcome b sehingga
∀ j∈N u j (a) ≤ u j (b) dan ∃ j∈N u j (a) < u j (b)
2.2 Teori utilitas (utility theory) 2
Pemodelan dalam games theory biasanya dipresentasikan dalam bentuk matriks payoff. Dari ini dapat dilihat konflik kepentingan antar masing-masing pemain yang terlibat. Masing-masing pemain kita asumsikan sudah mempunyai target dan keinginan dalam menyelesaikan suatu konflik kepentingan. Kemudian kita 2
Parsons,S. dan Wooldridge, M. (2002, An Introduction to Game Theory and Decision Theory. Dalam Parsons, S. Gmytrasiewicz, P. dan Wooldrige , M.,editor, Game Theory and Decision Theory in Agent-Based Systems,hal 5-6 . Kluwer Academic Publisher.
6
asumsikan terdapat himpunan Ω = {ω1 , ω 2 , ω 3 ,...} dari outcomes yang diinginkan oleh pemain sebelumnya.
Kita akan memformulasikan keinginan-keinginan pemain yang terlibat dalam games ke dalam suatu fungsi yang dinamakan fungsi utilitas (utility function), yang memetakan setiap outcome ke dalam suatu bilangan real. Secara matematika dapat diformulasikan sebagai berikut ui : Ω → ℜ Besar dan kecilnya bilangan real yang digunakan tergantung kepada seberapa besar pengaruh kejadian terhadap hasil yang diinginkan oleh masing-masing pemain. Sebagai contoh jika ω dan ω ' , keduanya merupakan hasil yang mungkin dalam Ω , dan u i (ω ) ≥ u i (ω ' ) maka outcome ω lebih diinginkan oleh pemain ke i dari pada outcome ω ' . Kita dapat juga menuliskannya dalam notasi:
ω φ i ω' Sebagai penyederhanaan notasi dari u i (ω ) ≥ u i (ω ' )
2.3 Theory of Moves (TOM)
Theory of moves merupakan pengembangan dari classic games theory, dimana pada teori ini dikembangkan model dinamik. Seorang pemain dalam theory of moves mempunyai pengetahuan dalam menentukan strategi awal dan menentukan langkah selanjutnya secara berurutan atau pilihan strategi yang lainnya.
Theory of Moves (TOM) lebih spesifik digunakan untuk memodelkan konflik antara dua pemain yang terlibat dalam permainan. TOM dimodelkan dengan formulasi dasar berupa matriks payoff 2x2, dimana setiap pemain mempunyai informasi lengkap mengenai kedua matriks payoff dan pengatahuan tentang profil
7
strategi awal. Kerangka kerja TOM membuat pemain dapat melakukan perubahan dalam penentuan langkah ke depan. Penentuan ini bukan hanya pilihan langkah yang harus segera dijalankan, tetapi juga antisipasi langkah selanjutnya dari langkah tersebut. Bahkan pemain dapat memprediksi dua langkah ke depan yang akan dijalankan. Untuk menjalankan konsep ini, ada beberapa aturan spesifik, yaitu:3 1. Permainan dimulai dari output yang diinginkan, yaitu state awal, yang merupakan titik potong antara baris dan kolom dari matrik 2x2. 2. Salah satu pemain secara sepihak bisa mengubah strateginya, dengan demikian state awal berubah ke state baru, pada baris atau kolom yang sama dengan state awal. Pemain ini disebut pemain 1 (P1). 3. Pemain 2 (P2) dapat merespon perubahan dari strategi pemain pertama, dengan begitu permainan bergerak ke state baru. 4. Respon yang berganti-ganti ini akan berlanjut sampai kedua pemain (P1 atau P2) yang mendapat giliran melangkah tidak merubah strateginya. Dimana kejadian ini merupakan output dari permainan. 5. Pemain tidak akan bergerak dari state awal jika dalam langkahnya: i.
Menuju state dengan nilai payoff lebih kecil
ii.
permainan kembali ke state awal (membuat state awal sebagai output)
6. Jika dalam pilihan rasional seorang pemain bisa tidak bergerak dan pemain lainnya memutuskan bergerak, maka pemain yang bergerak lebih diutamakan, sehingga outcome akan ditentukan olehnya. Untuk menghasilkan keputusan, setiap pemain akan melihat tiga langkah ke depan dengan metode backward induction untuk memutuskan strategi mana yang paling menguntungkan. Keputusan yang dihasilkan dalam permainan disebut dengan
3
Arjita Ghosh, Sandip Sen, Theory of Moves Learners: Toward Non-Myopic Equilibria. AAMAS’05 Utrectht,Neteherland.2005
8
state equilibrium. Dalam pendekatan ini bisa saja didapat Non Myopic Equlibrium.
Model yang biasa dipakai dalam TOM adalah chicken model. Bentuk chicken ini dihasilkan dari pemodelan konflik rudal nuklir antara Uni Soviet (Rusia) dengan Amerika di Kuba pada tahun 1962. Matrik payoff yang dihasilkan adalah:
Gambar 1 Matriks Cuban missile crisis dalam bentuk Chicken
2.4
Backward Induction
Untuk menentukan strategi pengambilan keputusan dalam TOM digunakan backward
induction.
Backward
induction
adalah
proses
iterasi
untuk
menyelesaikan sequential games. Pada langkah pertama, salah satu pemain menentukan strategi optimal dari pemain yang bergerak terakhir dalam game, dan pergerakan dari pemain yang bergerak berikutnya ditentukan dari aksi yang dilakukan oleh pemain terakhir. Proses berlanjut sampai semua pemain sudah menentukan semua pergerakannya.
2.5
Learning TOM Players
Dalam realita konflik, setiap pemain tidak selalu mempunyai informasi lengkap tentang strategi lawan. Untuk kasus seperti ini, maka dikembangkan learning
9
TOM. Tujuan yang ingin dicapai dengan learning TOM adalah menduga pilihan yang diambil oleh lawan dari games yang berulang dengan state awal yang diambil secara acak.
Untuk memudahkan learning, maka harus ditentukan perkiraan peluang bersyarat pergerakan lawan dari state awal permainan dimulai dan pemain yang memulai permainan pertama kali. Dalam hal ini, peluang bersyarat sangat penting karena pergerakan lawan dari suatu state sangat bergantung kepada sejauh mana permainan akan berlanjut.
Untuk menghitung peluang bersyarat dari masing-masing pergerakan pemain maka dapat dilakukan sebagai berikut:
Misal, matrik payoff 2x2 suatu permainan sebagai berikut :
Gambar 2 Matrik dasar bersama pilihan state masing-masing
Misalkan suatu urutan permainan sebagai berikut: C
R
C
R
C
S 0 → S1 → S 2 → S 3 → S 0 P00,c
P10,c
P20,c
P00,c , P10,c dan P20,c adalah peluang bersyarat dari pergerakan untuk pemain R pada state S1, pemain C pada state S2 dan pemain R pada state S3 secara berurutan terlihat bahwa state awal adalah S0 dan pemain C yang memulai permainan (untuk mempermudah presentasi maka indeks atas tidak akan disertakan). Dalam
10
urutan permainan diatas, untuk memutuskan strategi permainan maka pemain C akan melihat ke depan P0 dan P2, peluang pemain R dari frekuensi bergerak dan tidak bergeraknya pemain R dari masing-masing state dengan state awal S0. Dan bergantung pada P2, pemain C bisa menghitung peluangnya sendiri (P1). Perhitungan Peluang
Tujuan dari perhitungan peluang ini adalah untuk menghitung peluang bergeraknya C pada state S0, PC(S0). Dalam proses backward induction, harus dihitung terlebih dahulu peluang pada state S2, PC(S2), yaitu sebagai berikut:4 Asumsikan untuk setiap i, Qi = 1 − Pi dan U x ( y ) adalah payoff dari permainan yang didapat oleh pemain x di state y PC ( S 2) ← 0 Jika U C ( S 0) > U C ( S 2) maka PC ( S 2)+ = P2 . {C diuntungkan jika R bergerak dari S 3 ke S 0, hasil dari permainan berupa cycle} Jika U C ( S 3) > U C ( S 2) maka PC ( S 2)+ = Q2 . {C diuntungkan jika R berhenti di S 3 , permainan berhenti di S 3} Karena TOM tidak membolehkan terjadinya cycle, dan P0 × P1 × P2 adalah peluang terjadinya cycle, maka proses untuk menghitung PC (S0) adalah sebagai berikut: PC ( S 0) ← 0 Jika U C ( S 3) > U C ( S 0) maka PC ( S 0)+ = P0 × P1 × Q2 . {C diuntungkan jika permainan berhenti pada S 3} jika U C ( S 2) > U C ( S 0) maka PC ( S 0)+ = P0 × Q1 . {C diuntungkan jika permainan berhenti di S 2} jika U C ( S1) > U C ( S 0) maka PC ( S 0)+ = Q0 {C diuntungkan jika permainan berhenti di S1}
4
ibid
11
Untuk mendapatkan hasil dari permainan maka setelah peluang dihitung, permainan dilaksanakan dengan peluang seorang pemain melakukan pergerakan dari state dimana dia berada. Iterasi akan berhenti ketika pemain tidak bergerak atau jika cycle terbentuk. Catatan jika C bergerak dari S0, R harus menghitung PR(S1) berdasarkan estimasi dari P10,c, dan keputusannya akan bergerak atau tidak di S3. Atau, jika R memutuskan untuk bergerak ke S1, maka C dapat dihitung kembali dengan perhitungan sebelumnya dari P1, untuk memilih pergerakannya di S2.
Konfergensi menuju NMEs: Apabila prosedur backward inductio n digabung dengan cara pengambilan keputusan diatas, maka cycles akan tereliminasi. Untuk melihat hal ini, catat bahwa dalam skenario diatas, keputusan R pada state 3 adalah deterministik, karena hanya akan berubah jika dan hanya jika U R ( S 0) > U R ( S 3) . Pada awalnya, C belum yakin dengan keputusan di atas dan mengasumsikan P2 sebesar 0.5. Pengamatan terhadap keputusan R kembali diulang pada state 3, estimasi C terhadap P2 akan konvergen ke 1 atau 0. Keadaan ini, pada gilirannya akan menuju ke P1 konvergen ke 1 atau 0, bergantung kepada nilai utility yang didapat C pada state S2, S3, S0. Kondisi terkini bisa direfleksikan dari permainan selanjutnya oleh setiap pemain, dimana dalam setiap gilirannya, memberikan kesempatan kepada pemain lainnya untuk membuat estimasi yang akurat dari pilihan relative mereka. Karena learning berdasar pada backward induction, pilihan deterministik yang akurat digunakan untuk memperbarui estimasi yang sebelumnya menghasilkan nilai yang buruk. Setiap kali permainan diulang, peluang akan kecil atau besar untuk menghasilkan gerakan yang pasti berdasarkan pilihan aktual. Hasil yang di dapat, pemain akan konvergen pada NMEs.
12
