Jumat, 13 April 2018
Techniques for Solving Static.
Sebagaimana
dinyatakan pada awal bab ini solusi untuk permainan adalah a
prediksi
apa yang setiap pemain dalam game itu akan lakukan. Ini mungkin sangat
prediksi
yang tepat, di mana solusi memberikan satu strategi optimal untuk masing-masing
pemain.
Ketika ini terjadi, solusinya dikatakan unik. Namun, seringkali
kasus
bahwa solusi untuk permainan tertentu kurang tepat, bahkan ke
Sejauh
tidak ada strategi yang tersedia yang dikesampingkan. Seperti yang diharapkan
banyak
teknik solusi yang berbeda telah diusulkan untuk berbagai jenis
pertandingan.
Untuk permainan statis, dua teknik solusi yang luas telah diterapkan.
Set
pertama teknik solusi bergantung pada konsep dominasi. Sini
solusi
untuk permainan ditentukan dengan mencoba untuk mengesampingkan strategi yang a
orang yang
rasional tidak akan pernah bermain. Argumen berdasarkan dominasi mencari
jawab
pertanyaan “Strategi apa yang pemain rasional tidak pernah mainkan?”
Set kedua
teknik solusi didasarkan pada konsep
keseimbangan.
Dalam permainan non-kooperatif, keseimbangan terjadi ketika tidak ada satupun
para
pemain, bertindak secara individu, memiliki dorongan untuk menyimpang dari yang
diprediksi
larutan.
Dengan teknik solusi ini permainan diselesaikan dengan menjawab
pertanyaan
"Apa sifat-sifat suatu solusi harus memiliki untuk itu menjadi sebuah
ekuilibrium?
”.
Pada
bagian berikut ini kami menguji berbagai teknik dominan itu
dapat
diterapkan untuk permainan statis, dan dua konsep kesetimbangan. Selanjutnya
bab lebih
lanjut konsep kesetimbangan yang biasa digunakan dalam teori permainan
akan
disajikan dan didiskusikan.
Sebuah.
Dominasi Ketat.
Suatu
strategi dikatakan didominasi secara ketat jika strategi lain selalu
memberikan
hasil yang lebih baik apa pun yang dilakukan pemain lain dalam game. Ini
teknik
solusi membuat asumsi yang tampaknya masuk akal bahwa
a . Strict
Dominance
Jika seorang pemain
secara
sadar memainkan strategi yang sangat didominasi mereka tidak dapat
memaksimalkan mereka
hasil yang
diharapkan, mengingat keyakinan mereka tentang apa yang akan dilakukan pemain
lain. Di dalam
rasa
seorang pemain yang memainkan strategi yang sangat didominasi dikatakan
irasional.
Menerapkan
prinsip aturan dominasi ketat dari jenis irasional ini
tingkah
laku. Untuk mengilustrasikan teknik ini, kami menggunakannya untuk memecahkan
narapidana
permainan
dilema. Dalam menerapkan prinsip dominasi yang ketat kami memeriksa
masing-masing
pemain
pada gilirannya dan mengecualikan semua strategi yang benar-benar didominasi.
Ini
proses
mungkin mengesampingkan semua kecuali satu strategi untuk setiap pemain. Ini
berlaku untuk
game
dilema tahanan, dan teknik ini menghasilkan solusi unik
untuk game
ini.
Pertimbangkan
dulu dilema yang dihadapi tahanan 1. Haruskah dia mengaku atau
haruskah
dia tetap diam berharap tahanan lain melakukan hal yang sama. Itu
prinsip
dominasi ketat berpendapat bahwa tahanan 1 harus mengaku. Itu
alasan
untuk ini adalah bahwa apa pun tahanan 2 memutuskan untuk melakukan tahanan 1
selalu
lebih baik
mengaku. Ini berarti tidak mengakui secara ketat didominasi dan sebagainya
tampaknya
masuk akal untuk menganggapnya tidak akan dimainkan. Logika yang sama berlaku
sama untuk
narapidana 2 dan dominasi yang begitu ketat memprediksi bahwa dia akan juga
mengaku.
Solusi untuk game ini berdasarkan dominasi yang ketat adalah keduanya
tahanan
mengaku meskipun keduanya akan lebih baik jika tidak mengaku.
Setidaknya
salah satu pemain dalam gim ini bisa, dengan hasil yang berbeda
membuat
lebih baik tanpa pemain lain yang dibuat lebih buruk dari solusi ini
dikatakan
Pareto tidak efisien. (Kenyataannya jika kedua pemain tidak mengakui keduanya
lebih
baik.)
Perlu
dicatat di sini bahwa penyebab inefisiensi Pareto bukan itu
para
pemain tidak dapat berkomunikasi, tetapi mereka tidak dapat berkomitmen
diri
mereka sendiri untuk hasil yang efisien Pareto. Bahkan jika kedua tahanan itu
setuju
sebelum
ditangkap, tak satu pun dari mereka akan mengaku, begitu ditahan di dalam
kepentingan
pribadi mereka untuk melakukan yang sebaliknya. Ini menggambarkan perbedaannya
antara
teori permainan non-kooperatif dan kooperatif. Dalam permainan kooperatif
teori
kedua narapidana bisa masuk menjadi mengikat dan dapat dilaksanakan
kesepakatan
untuk tidak mengaku dan jadi dibuat lebih baik. Ini tidak mungkin di
teori
permainan non-kooperatif.
Memecahkan
game peluncuran produk sebelumnya yang dijelaskan dalam Latihan
menggunakan prinsip dominasi yang ketat.
Weak Dominance.
Suatu
strategi dikatakan didominasi lemah jika strategi lain membuat
orang yang
lebih baik dalam beberapa situasi dan membuat mereka acuh pada yang lain.
Sekali
lagi tampaknya masuk akal untuk mengasumsikan bahwa pemain rasional tidak akan
memainkan
strategi
yang didominasi lemah, karena mereka bisa melakukan setidaknya juga, dan mungkin
lebih baik
lagi, dengan memainkan strategi dominan. Pertimbangkan permainan bentuk normal
ditunjukkan
pada Gambar 2.3. Di game ini ada dua pemain masing-masing dengan dua
strategi
yang mungkin. Pemain 1 dapat bergerak "naik" atau "turun",
dan pemain 2 bisa
bergerak
baik “kiri” atau “kanan”. Imbalan diberikan dalam matriks, di mana yang pertama
Angka
adalah bayaran untuk pemain 1 dan angka kedua adalah bayaran untuk pemain 2.
Untuk
permainan ini tidak ada strategi yang tersedia yang dikesampingkan menggunakan
prinsip
dominasi
yang ketat. Ini karena tidak ada strategi yang membuat pemain itu lebih buruk
dalam
segala situasi. Misalnya, jika pemain 1 memainkan "naik" maka pemain
2 adalah
acuh tak
acuh antara "kiri" dan "kanan". Demikian pula jika pemain 2
memainkan "kiri" pemain 1 adalah
acuh tak
acuh antara "naik" dan "ke bawah". Meskipun kami tidak
dapat mengajukan banding ke
prinsip
dominasi ketat untuk mengesampingkan salah satu strategi yang tersedia, kita
bisa
menerapkan
prinsip dominasi lemah.
Aplikasi
Dominance weak.
Menurut prinsip pemain dominasi lemah 1 tidak akan pernah bermain
"Turun"
dan ini bisa dikesampingkan. Demikian pula pemain 2 tidak akan pernah bermain
"benar",
dan ini
juga bisa dikesampingkan. Ini hanya menyisakan satu strategi tersisa untuk
setiap
pemain. Hasil yang diprediksi adalah pemain 1 akan bergerak “naik” dan pemain
2 akan
bergerak "kiri". Sekali lagi ini adalah solusi tidak efisien Pareto.
Hal ini karena
hasil
"down / left" membuat pemain 2 lebih baik dan pemain 1 tidak lebih
buruk.
Alasan
pemain 1 tidak beralih bermain "turun", meskipun ini mengarah
untuk
peningkatan Pareto, adalah bahwa hal itu memerlukan risiko yang lebih besar
untuk pemain ini. Jika pemain
2 bermain
"benar" maka pemain 1 pasti lebih buruk dari bergerak
"turun"
bukannya
"naik". Unsur menghindari risiko yang tidak perlu ini tercermin dalam
prinsip
dominasi lemah.
Iterated Strict Dominance
Iterasi
dominasi ketat mengasumsikan bahwa dominasi yang ketat dapat diterapkan
berturut-turut
untuk pemain yang berbeda dalam suatu permainan. Misalnya, jika satu aturan
pemain
keluar
strategi tertentu, karena sangat didominasi oleh yang lain, maka itu
diasumsikan
pemain lain mengenali ini dan bahwa mereka juga percaya yang lain
pemain
tidak akan memainkan strategi yang didominasi ini. Ini pada gilirannya dapat
menuntun mereka
mengecualikan
strategi yang didominasi, dan seterusnya. Dengan cara ini dimungkinkan untuk
kecualikan
semua kecuali satu strategi untuk setiap pemain, dan karenanya buat prediksi
unik
untuk permainan
yang sedang dianalisis.
Dalam game
ini pemain 1 memiliki dua kemungkinan strategi, "naik" dan
"turun", dan
pemain 2
memiliki tiga kemungkinan strategi, "kiri", "tengah" dan
"kanan". Mulanya
baik
"naik" atau "turun" secara ketat didominasi oleh yang lain
untuk pemain 1.
Namun
untuk pemain 2 "kanan" secara ketat didominasi oleh
"tengah". Menarik bagi
dominasi
ketat kita dapat beralasan bahwa pemain 2 tidak akan pernah bermain
"benar". Jika pemain 1
juga tahu
bahwa pemain 2 adalah rasional dan tidak akan bermain "benar", lalu
"naik" sekarang
ketat
mendominasi "turun" untuk pemain 1. Iterasi ketat dominasi sekarang
memprediksi
bahwa
"bawah" tidak akan dimainkan. Akhirnya jika pemain 2 tahu bahwa
pemain 1 tidak akan pernah
bergerak
"turun" kemudian mengulangi dominasi ketat memprediksi bahwa pemain 2
akan bermain
"tengah".
Solusi unik untuk game ini berdasarkan berurutan atau iterasi
Oleh
karena itu, dominasi ketat "atas / tengah".
Teknik
dominasi terakhir adalah dominasi yang lemah. Ini adalah
sama dengan
dominasi yang ketat, kecuali di sini adalah dominasi lemah
diterapkan
secara berurutan ke pemain yang berbeda dalam game. Sekali lagi ada kemungkinan
itu
teknik ini
dapat menghasilkan solusi unik untuk permainan tertentu.
Satu masalah dengan dominasi yang lemah, yang tidak dimiliki oleh
mengulangi
dominasi yang ketat, adalah bahwa solusi yang diprediksi dapat bergantung pada
urutan di
mana strategi pemain dihilangkan. Ini benar untuk game
ditunjukkan
pada 1111ika kita mulai dengan menerapkan dominasi lemah untuk pemain 1 lalu
kami
memprediksi bahwa para pemain akan memilih solusi unik "atas /
tengah". Jika kita
pertama
menerapkan dominasi lemah untuk pemain 2 maka yang bisa kita simpulkan adalah
pemain itu
2 tidak
akan bermain "benar". Jelaslah urutan di mana kita menerapkan
dominasi lemah
secara
signifikan mempengaruhi hasil pertandingan yang diprediksi. Sayangnya untuk
sebagian besar
permainan
pilihan ini sepenuhnya sewenang-wenang.
Perlu
dicatat bahwa dalam menerapkan argumen dominasi iterasi kita
mengasumsikan
versi rasionalitas yang lebih kuat daripada yang kita lakukan dengan dominasi
belaka.
Dengan
dominasi kita mengasumsikan bahwa pemain rasional tidak akan bermain didominasi
strategi.
Dengan dominasi berulang kami berasumsi bahwa pemain yang rasional tidak akan
melakukannya
strategi
bermain didominasi, dan juga bahwa pemain menganggap bahwa pemain lain
rasional
dan tidak akan melakukan ini. Untuk dominasi berulang untuk memprediksi secara
akurat
orang
tidak hanya harus rasional tetapi menganggap orang lain juga rasional,
dan
persyaratan ini perlu diperkuat dengan setiap iterasi. (Untuk
Sebagai
contoh, saya perlu berasumsi bahwa Anda percaya bahwa saya percaya Anda percaya
itu
Saya
rasional, dan seterusnya. Jika urutan penalaran ini tak terbatas kita miliki
Asumsi
yang sering digunakan dari pengetahuan umum tentang rasionalitas.) As
jumlah
iterasi menjadi besar asumsi tambahan ini menjadi
semakin
meragukan. Contoh permainan di mana prinsip
pengulangan
dominasi yang ketat diambil hingga ekstrim adalah Rosenthal's (1981)
permainan
kelabang.
Jika
permainan menghasilkan solusi unik dengan menerapkan ketat, lemah atau
dominasi
iterasi maka permainan itu dikatakan dominasi dipecahkan. Itu
masalah
utama dengan semua teknik solusi ini adalah yang sering mereka berikan sangat
prediksi
yang tidak tepat tentang game.
Dalam
argumen permainan ini berdasarkan dominasi mengarah ke sangat tidak tepat
prediksi
bahwa apa pun bisa terjadi! Jika solusi yang lebih spesifik untuk jenis ini
permainan
diperlukan maka teknik solusi yang lebih kuat harus diterapkan. Ini
menuntun
kita pada teknik solusi tidak berdasarkan dominasi tetapi pada
konsep
kesetimbangan.
Nash
Equilibrium
Sebagaimana
dinyatakan dalam pendahuluan untuk argumen bagian ini berdasarkan
dominasi mengajukan
pertanyaan “Strategi apa yang akan dilakukan oleh pemain yang rasional?
bermain?
“Berbeda dengan konsep ekuilibrium Nash yang dimotivasi oleh
pertanyaan
“Properti apa yang harus dimiliki oleh ekuilibrium? "Jawaban untuk ini
pertanyaan
dari John Nash (1951), berdasarkan banyak karya sebelumnya oleh Cournot
(1838),
adalah bahwa dalam ekuilibrium, strategi yang dipilih setiap pemain diberikan
secara optimal
bahwa
setiap pemain lain memilih strategi keseimbangan. Jika ini bukan
Kasusnya,
setidaknya satu pemain ingin memilih strategi yang berbeda dan sebagainya
kita tidak
bisa berada dalam ekuilibrium. Sekali lagi konsep ini berusaha untuk menerapkan
asumsi
ekonom bahwa individu rasional dalam arti bahwa mereka
berusaha
untuk memaksimalkan kepentingan diri mereka sendiri.
Menemukan
kesetimbangan Nash untuk permainan apa pun melibatkan dua tahap. Pertama,
kami
mengidentifikasi strategi optimal masing-masing pemain dalam menanggapi apa
yang lainnya
pemain
mungkin melakukannya. Ini melibatkan bekerja melalui setiap pemain secara
bergantian dan
menentukan
strategi optimal mereka. Ini dilakukan untuk setiap kombinasi
strategi
oleh pemain lain. Kedua, ekuilibrium Nash diidentifikasi saat
semua
pemain memainkan strategi optimal mereka secara bersamaan.
Sebenarnya
metodologi di atas hanya mengidentifikasi strategi murni
Nash
equilibria. Itu tidak mengidentifikasi strategi campuran Nash equilibria. Yang
murni
kesetimbangan
strategi adalah di mana setiap pemain memainkan satu strategi spesifik.
Campuran
kesetimbangan
strategi adalah di mana setidaknya satu pemain dalam permainan mengacak
beberapa
atau semua strategi murni mereka. Ini berarti bahwa pemain menempatkan
distribusi
probabilitas atas strategi alternatif mereka. Misalnya, pemain
mungkin
memutuskan untuk memainkan masing-masing dari dua strategi murni yang tersedia
dengan probabilitas
0,5, dan
tidak pernah memainkan strategi lain. Oleh karena itu, strategi murni adalah a
strategi
campuran terbatas dengan probabilitas satu diberikan kepada yang terpilih
strategi,
dan nol untuk semua yang lain. Konsep strategi campuran Nash
ekuilibrium
dibahas nanti di bagian ini.
Untuk
mengilustrasikan metodologi dua tahap untuk menemukan (strategi murni)
Kesetimbangan
Nash kami terapkan pada permainan dilema tahanan.
ahap satu.
Pertama-tama
kita perlu mengidentifikasi strategi optimal untuk setiap tahanan,
tergantung
pada apa yang mungkin dilakukan tahanan lain. Jika tahanan 1 mengharapkan
tahanan 2
untuk mengaku maka strategi terbaik narapidana 1 juga mengaku (-6 adalah
lebih baik
dari -9). Ini ditunjukkan pada Gambar 2.7 dengan menggarisbawahi elemen
pembayaran ini
untuk
tahanan 1 di sel yang sesuai dengan kedua narapidana mengaku. Jika
napi 1
mengharapkan tahanan 2 tidak mengaku, maka strategi terbaik narapidana adalah
masih
mengaku (kali ini lebih baik dari -1). Sekali lagi kami tunjukkan ini
menggarisbawahi
elemen pembayaran ini untuk narapidana 1. Analisis yang sama adalah
dilakukan
untuk napi 2 dan imbalan strategi terbaiknya digarisbawahi.
Tahap Dua.
Selanjutnya
kita menentukan apakah kesetimbangan Nash ada dengan memeriksa
terjadinya
strategi optimal yang diidentifikasi sebelumnya. Jika semua imbalan dalam
sel
digarisbawahi kemudian sel itu sesuai dengan ekuilibrium Nash. Ini adalah
benar
menurut definisi, karena dalam ekuilibrium Nash semua pemain memainkannya
strategi
optimal mengingat bahwa pemain lain juga memainkan strategi optimal mereka. Di
permainan
dilema tahanan hanya satu sel yang semua elemennya digarisbawahi.
Ini sesuai
dengan kedua narapidana mengaku, dan jadi ini adalah Nash yang unik
keseimbangan
untuk game ini.
Prediksi
untuk game dilema tahanan ini sama seperti itu
diturunkan
menggunakan dominasi ketat. Bahkan memang benar bahwa yang unik ketat
solusi
dominasi adalah ekuilibrium Nash yang unik. Kebalikan dari ini
Namun
pernyataan itu tidak selalu benar. Sebuah ekuilibrium Nash yang unik tidaklah
demikian
selalu
merupakan solusi dominan yang unik dan unik. Dalam pengertian ini ekuilibrium
Nash adalah
konsep
solusi yang lebih kuat daripada dominasi yang ketat. Karena alasan inilah Nash
konsep
ekuilibrium dapat memprediksi solusi unik untuk permainan di mana ketat
dominasi
tidak. Ini diilustrasikan dalam game yang digunakan sebelumnya
menunjukkan
bahwa permainan mungkin bukan dominasi yang dapat dipecahkan. Game ini
ditampilkan
Sebagaimana dinyatakan sebelumnya argumen
berdasarkan
dominasi yang diterapkan pada game ini memprediksi bahwa apa pun bisa terjadi.
Menggunakan
metodologi dua tahap untuk menemukan keseimbangan (strategi murni) Nash
Namun
menghasilkan prediksi unik bahwa pemain 1 akan memilih "turun" dan
Pemain 2
akan memilih "benar". Oleh karena itu, konsep kesetimbangan Nash
sangat
berguna ketika argumen dominasi tidak memberikan yang unik
larutan.
Satu hasil
penting dari teori permainan adalah bahwa untuk permainan berhingga (yaitu
permainan
dengan
jumlah pemain dan strategi yang terbatas) selalu ada setidaknya satu
Nash
ekuilibrium. Sebelum berpikir bahwa hasil ini berarti kita selalu bisa
buat
prediksi yang pasti tentang apa yang akan dilakukan orang-orang dalam game apa
pun yang berikut ini
dua
kualifikasi perlu dinyatakan.
Pertama,
hasil di atas hanya benar jika kita memasukkan strategi campuran, seperti
serta
strategi murni. Ini berarti bahwa kita tidak dapat selalu menyatakan dengan
pasti
apa yang
semua pemain dalam game akan lakukan, tetapi kami hanya dapat memberikan
probabilitas
untuk berbagai hasil yang terjadi. Kemungkinan ini dibahas
di bawah.
Kedua,
hasil di atas tidak mengesampingkan kemungkinan kelipatannya
Nash equilibria.
Memang banyak permainan yang menunjukkan banyak kesetimbangan Nash. Dengan
multiple
equilibria masalahnya adalah bagaimana memilih satu ekuilibrium dari banyak
orang. Di
Jawaban
atas pertanyaan ini banyak penyempurnaan ekuilibrium Nash
mengusulkan
untuk mencoba dan membatasi set equilibria yang mungkin.
Mixed Strategy Nash Equilibrium.
·
wo-person, zero-sum
game
Ada
dua jenis persoalan Two-person, zero-sum game. Pertama, pemain yang posisi
pilihan terbaiknya bagi bagi setiap pemain dicapa dengan memilih satu strategi
tunggal sehingga permainannya disebut permainan strategi murni (pure-strategi
game). Kedua, permainan yang kedua pemainnya melakukan pencampuran terhadap
strategi-strategi yang berbeda dengan maksud untuk mencapai posisi pilihan
terbaik. Disebut strategi permainan campuran (mixed-strategy game)
·
Pure-strategi game
Pemain
yang akan memaksimumkan dan mengidentifikasi strategi optimumnya dengan
menggunakan criteria maksimum, sedangkan pemain yang meminimumkan akan
mengidentifikasi starategi optimumnya dengan menggunakan criteria minimaks.
Jika nilai sama maka permainan telah terpecahkan. Dalam kasus seperti itu, maka
telah terjadi titik keseimbangan. Disebut saddle point. Jika nilai maksimin
tidak sama dengan minimaks, maka titik keseimbangan tidak akan tercapai dan
berarti tidak dapat diselesaikan dengan strategi murni sebaliknya dilakukan
dengan strategi campuran criteria maksimin (untuk pemain yang
memaksimumkan)dapatkan nilai minimum dari masing-masing baris. Nilai terbesar
(nilai maksimum) dari nilai-nilai minimum ini adalah nilai maksimin. Dengan
demikian, maka untuk permainan dengan strategi murni ini, strategi optimumnya
adalah baris tempat nilai maksimin terletak. criteria minimaks (untuk
permainan yang meminimumkan)dapatkan nilai maksimum pada masing-masing kolom.
Nilai terkecil (nilai minimum) dari nilai-nilai maksimum ini adalah nilai
minimaks. Dengan demikian, maka untuk permainan dengan strategi murni ini,
strategi optimumnya adalah kolom tempat nilai minimaks terletak.
·
Mixed-strategy game
pada game yang tidak memiliki saddle point, penyelesainannya
harus dilakukan dengan menggunakan strategi campuran. Para pemain dapat
memainkan seluruh strateginya sesuai dengan set probabilitas yang telah
ditetapkan. Solusi persoalan strategi campuran ini masih didasarkan pada
kriteria maksimin dan minimaks. Perbedaanya adalah kolom memaksimumkan
ekspektasi payoff terkecil, sedangkan baris meminimumkan ekspektasi payoff
terbesar pada suatu baris. Seperti halnya strategi murni, pada strategi
campuran berlakunya hubungan. Ada beberapa metode untuk menyelesaikan permainan
jenis ini, diantaranya adalah dengan cara grafis dengan menggunakan program
linier.
