Game Theory : Nash Equilibrium

Nash Equilibrium

 

Keseimbangan adalah Suatu strategi su(sj untuk semua s S. _i dikatakan strategi dominan bagi Pi jika u(s_i)_j), dengan u(s_i) dan u(s_j) adalah perolehan dari strategi s_i dan s_jdimana i ≥≠ ∈

Dalam setiap permainan, setiap pemaian akan selalu menggunakan dominan karena sifat rasional yang diasumsikan pada setiap pemain. Tetapi dalam beberapa permainan, tidak terdapat strategi dominan sehingga pemain harus mencari strategi lain untuk memaksimumkan perolehannya. Dengan menggunakan mixed-strategy seorang pemain dapat menentukan strategi yang akan digunakannya dengan cara memilih strategi yang akan digunakannya dengan suatu distribusi peluang sehingga strategi yang akan digunakan bukan bersifat deterministik tetapi bersifat stokastik. Dengan menggunakan mixed-strategy komposisi strategi yang akan digunakan oleh pemain adalah berupa himpunan pasangan berurut distribusi-distribusi peluang yang akan digunakan oleh setiap pemain.

Defenisi lain tentang keseimbangan Nash adalah kondisi dimana strategi-strategi yang digunakan oleh setiap pemain adalah strategi yang optimal baginya jika diberikan strategi pemain lainnya dalam permainan tersebut dimana setiap pemain tidak dapat meningkatkan hasil perolehannya dengan menggantikan strateginya.

Arti keseimbangan Nash menurut John Nash adalah jika ada serangkaian strategi untuk sebuah permainan dimana tidak ada pemain yang bisa beruntung dengan mengubah strateginya sedangkan pemain lain mempertahankan strateginya tidak berubah, maka serangkaian strategi tersebut dan perimbangan (payoff) yang koresponden membentuk keseimbangan Nash.

Memilih Strategi

Dalam permainan dua pemain berjumlah nol ini tujuannya adalah menemukan jawab yang kokoh bagi kedua pemain. Memilih strategi sama artinya

dengan menemukan jawab permainan. Jawab yang dimaksud hanya ada bila tiap pemain berusaha memperkecil derita atau memperbesar perolehan, dengan kata lain tiap pemain berusaha meraih strategi optimal bagi dirinya sehingga tidak ada lagi dari antara pemain yang dapat meningkatkan posisi masing-masing dengan memilih strategi lain. Hasil yang diharapkan bila kedua pemain telah menggunakan strategi optimalnya disebut “harga permainan”. Salah satu langkah dari satu permainan adalah pemilihan satu strategi oleh tiap pemain. Usaha menemukan strategi optimal dan harga permainan di sebut menyelesaikan

permainan dan langkah berikutnya tidak boleh lagi dilanjutkan dan permainan telah selesai.

Kriteria Maksimin dan Minimaks

Tujuan utama menyelesaikan suatu permainan adalah menentukan strategi optimal. Strategi optimal dapat ditentukan dengan menggunakan teori yang disebut teori minimaks yang pada prinsipnya mengatakan bahwa tiap pemain secara sepihak mencari tingkat keamanan yang maksimum bagi diri sendiri.

Dalam memilih strategi optimal, beberapa asumsi ditetapkan terlebih dahulu yaitu:

Berdasarkan asumsi diatas, tiap pemain mengetahui bahwa pemain yang lain cukup rasional serta mempunyai tujuan yang sama yaitu memaksimumkan perolehan sendiri. Pemain I memeriksa tiap baris dari matriks perolehan dan memilih harga maksimum dari harga minimum. Cara menentukan pilihan seperti ini adalah cara yang konservatif dan biasa disebut sebagai cara memilih yang terbaik dari antara yang terburuk. Cara ini juga disebut kriteria maksimum dari minimum disingkat dengan kriteria maksimin.

Sebaliknya, pemain II menyelesaikan permainan untuk menentukan strategi optimal dengan menggunakan teori yangn dinamakan teori minimaks. Teori ini menetapkan bahwa pemain secara sepihak mencari tingkat keamanan yang maksimum bagi dirinya sendiri, yaitu dengan memilih derita terkecil dari antara sejumlah derita maksimum. Cara ini ialah memilih kriteria minimum dari maksimum atau disingkat dengan minimaks. 1) Bahwa kedua pemain memiliki kepintaran yang sama 2) Tiap pemain sudah mengetahui strategi yang lain 3) Tiap pemain mengetahui jumlah perolehan sendiri dan derita pemain lain 4) Tiap pemain harus menentukan strategi (pilihan).

 

Peranan Dominasi

Pemain A dan B

x	y	z
8	4	7,5
7	3,5	3
8	4	7,5

pemain A untuk Horizontal dan B untuk Vertical

 

Lihat kembali contoh yang diatas, terlihat bahwa strategi 1 menghasilkan keuntungan maksimum bagi A, tanpa memperhatikan strategi mana yang dipilih B. Sehingga strategi 1 dikatakan mendominasi strategi 2. untuk kasus dimana suatu strategi secara sempurna didominasi oleh strategi lain, strategi yang didominasi dapat dibuang dari matriks pay-off karena pemain tidak pernah memilihnya.

Untuk pemain B, strategi x didominasi oleh strategi y karena kerugian strategi x selalu lebih besar daripada kerugian strategi y tanpa memperhatikan strategi yang dipilih A. strategi x juga didominasi oleh strategi z. Karena itu, strategi x dapat dibuang.

Pemain A hanya dapat memilih strategi 1, yanng berarti B akan memilih strategi y untuk meminimumkan kerugian menjadi 4 daripada 7,5. Ingat bahwa solusinya tetap sama. Jadi, jika setiap pemain memiliki sebuah strategi dominan, games akan mencapai keseimbangan atau memiliki saddle point.

http://repository.usu.ac.id/bitstream/123456789/22982/3/Chapter%20II.pdf