Situasi ketika terdapat keseimbangan dalam strategi dominan dalam permainan cukup jarang terjadi. Dan tidak semua permainan dapat menemukan solusi dengan membuang strategi yang didominasi secara ketat. Contoh permainan yang sesuai disajikan pada Tabel 16.8.

Pemain kedua akan memilih strategi A jika dia berasumsi bahwa pemain pertama akan memilih strategi Z; pada saat yang sama, strategi B lebih disukai baginya jika yang pertama memilih Y.

Tabel 16.8.

Wajar jika kita berasumsi bahwa jika tidak ada strategi yang dominan bagi semua pemain, maka pilihan masing-masing pemain bergantung pada ekspektasi terhadap pilihan pemain lainnya. Selanjutnya kita akan melihat konsep solusi berdasarkan ide ini.

16.2.4 Keseimbangan Nash

Selain situasi yang dibahas di bagian sebelumnya, terdapat situasi14 yang wajar untuk dimodelkan berdasarkan asumsi berikut:

Saat membuat keputusan, pemain dipandu oleh tindakan yang diharapkan dari mitranya;

harapannya adalah keseimbangan (bertepatan dengan tindakan yang sebenarnya dipilih oleh mitra).

Jika kita berasumsi bahwa semua pemain adalah orang yang rasional, sehingga masing-masing memilih strategi yang memberikan hasil paling besar sesuai harapannya, maka asumsi ini mengarah pada konsep pengambilan keputusan yang disebut Keseimbangan Nash. Dalam keseimbangan, setiap pemain tidak punya alasan untuk merevisi ekspektasinya.

Secara formal, keseimbangan Nash didefinisikan sebagai berikut.

Definisi 90:

Seperangkat strategi x X adalah ekuilibrium Nash15 jika

1) strategi x i setiap pemain adalah respon terbaiknya terhadap strategi yang diharapkan dari pemain lain xe −i:

ui (xi , xe −i ) = maks ui (xi , xe −i ) i = 1, . . . , N;

x iX saya

14 Kita dapat membayangkan populasi pemain tipe A (misalnya kucing) dan pemain tipe B (misalnya tikus). Seorang pemain tipe A, ketika bertemu dengan pemain tipe B, memiliki ekspektasi mengenai perilaku partner tipe B, dibenarkan oleh pengalamannya sendiri atau pengalaman orang lain, dan dipandu oleh mereka terlebih dahulu (dan sebaliknya). Namun, ini bukan satu-satunya situasi di mana pendekatan yang dipertimbangkan sudah memadai.

15 matematikawan Amerika John Nash menerima Penghargaan Nobel di bidang Ekonomi pada tahun 1994 bersama dengan J. Harsanyi dan R. Selten "untuk analisis perintis mereka tentang keseimbangan dalam teori permainan non-kooperatif." Konsep keseimbangan dikemukakan dalam artikel berikut: J.F. Nash: Titik Keseimbangan dalam Permainan N-Person,

Prosiding National Academy of Sciences Amerika Serikat 36 (1950): 48–49; J. F. Nash: Non-Cooperative Games, Annals of Mathematics 54 (1951): 286–295 (terjemahan bahasa Rusia. J. Nash: Non-Cooperative Games, dalam buku Matrix Games, N. N. Vorobyov (ed.), M.: Fizmatgiz, 1961: 205–221).

Perlu dicatat bahwa Nash sendiri tidak memasukkan ekspektasi ke dalam definisi tersebut. Definisi asli Nash bertepatan dengan sifat yang dibahas di bawah ini.

xe −i = x−i saya = 1, . . . , N

Perhatikan bahwa ketika menggunakan ekuilibrium Nash untuk memodelkan situasi permainan, pertanyaan tentang apakah para pemain mengetahui tujuan mitranya, apakah mereka mengetahui rasionalitas mitranya, apakah mereka tahu cara menghitungnya, dll., menghilang ke latar belakang. Cara pembentukan ekspektasi diambil di luar lingkup analisis; Yang penting di sini adalah ekspektasi berada dalam keseimbangan.

Tetapi jika analisis keseimbangan Nash tidak mempedulikan apakah seorang pemain mengetahui tujuan pemain lain, maka validitas pertimbangan konsep Nash dalam konteks permainan dengan informasi yang sempurna mungkin dipertanyakan. Masalahnya adalah istilah " informasi lengkap“dalam teori permainan memiliki arti yang agak sempit. Sebenarnya hanya menyiratkan kelengkapan informasi tentang jenis mitra (istilah “tipe pemain” dijelaskan pada paragraf tentang permainan Bayesian).

Seperti yang mudah dilihat, definisi ekuilibrium Nash di atas setara dengan sifat berikut, yang biasanya digunakan sebagai definisi:

Seperangkat strategi x X adalah ekuilibrium Nash jika strategi xi setiap pemain merupakan respons terbaiknya terhadap strategi pemain lain x−i:

ui (xi , x−i ) = maks ui (xi , x−i ) i = 1, . . . , N

x iX saya

Properti ini juga dapat ditulis dalam bentuk fungsi respons (peta).

Definisi 91:

Menampilkan respon pemain ke-i,

Ri : X−i 7→Xi

menugaskan setiap himpunan strategi pemain lain, x−i X−i , himpunan strategi pemain ke-i, yang masing-masing merupakan respons terbaik terhadap x−i . Dengan kata lain,

ui (yi , x−i ) = maks ui (xi , x−i ) x−i X−i , yi Ri (x−i )x i X i

Pengenalan pemetaan respons memungkinkan kita untuk menulis definisi ekuilibrium Nash dengan lebih ringkas: seperangkat strategi x X adalah ekuilibrium Nash jika

xi Ri (x−i ) saya = 1, . . . , N

Jika respon setiap pemain tidak ambigu (merupakan fungsi), maka himpunan kesetimbangan Nash berimpit dengan himpunan solusi sistem persamaan:

xi = Ri (x−i ) saya = 1, . . . , N.

Pada Tabel 16.8, tampilan respons pemain digambarkan dengan menyorot hadiah yang sesuai dengan tindakan optimal. Ekuilibrium Nash dalam permainan ini adalah sel (B, Y), karena hasil dari kedua pemain di dalamnya ditekankan.

Mari kita ilustrasikan penggunaan fungsi respons dengan menggunakan contoh permainan di mana pemain memiliki rangkaian strategi.

Permainan 5. “Perdagangan Internasional”

Dua negara secara bersamaan memilih tingkat bea masuk, τi. Volume perdagangan antar negara16,x, tergantung pada bea masuk yang ditetapkan sebagai

x = 1 − τ1 − τ2

Tujuan setiap negara adalah memaksimalkan pendapatan ui = τi x.

Kami memaksimalkan kemenangan negara pertama,

τ1 (1 − τ1 − τ2 )

menurut τ1, mengingat tingkat bea yang ditetapkan oleh negara ke-2 harus ditetapkan. Kondisi orde pertama berbentuk

1 − 2τ1 − τ2 = 0

Karena fungsi yang dimaksimalkan benar-benar cekung, kondisi orde pertama sesuai dengan maksimum global.

Kondisi urutan pertama untuk masalah memaksimalkan keuntungan negara ke-2 ditemukan serupa:

1 − τ1 − 2τ2 = 0

Setelah memecahkan sistem dua persamaan linear, kami menemukan keseimbangan Nash:

τ1 = τ2 = 1/3

Respon optimal negara pertama terhadap tingkat bea masuk yang ditetapkan oleh negara kedua dijelaskan oleh fungsinya

τ1 (τ2 ) =1 − τ 2

Demikian pula fungsi respon negara ke-2 adalah

τ2 (τ1 ) =1 − τ 1 2

Untuk menemukan keseimbangan Nash, Anda perlu menyelesaikan sistem persamaan

τ1 (τ2) = τ1,

τ2 (τ) = τ .

Pencarian keseimbangan Nash ditunjukkan secara grafis pada Gambar. 16.3. Titik-titik yang terletak pada kurva respons optimal τ1 (τ2) dan τ2 (τ1) dicirikan oleh fakta bahwa garis singgung kurva indiferen pemain sejajar dengan sumbu koordinat yang sesuai. Ingatlah bahwa kurva indiferen adalah himpunan titik-titik di mana utilitas individu yang bersangkutan adalah sama (ui (x) = const). Kesetimbangan ditemukan sebagai titik potong kurva respons.

Keuntungan menggunakan konsep ekuilibrium Nash adalah bahwa solusi dapat ditemukan dalam permainan yang tidak memungkinkan untuk membuang strategi yang didominasi. Namun, konsepnya sendiri mungkin lebih kontroversial karena mengandalkan asumsi kuat mengenai perilaku pemain.

Hubungan antara konsep solusi yang diperkenalkan dijelaskan oleh pernyataan berikut:

16 Dalam permainan ini, untuk mempermudah, kami tidak membedakan antara ekspor dan impor.

Beras. 16.3. Ekuilibrium Nash dalam permainan perdagangan internasional

Teorema 151:

Jika x = (x1, . . . , xm) adalah ekuilibrium Nash dalam permainan tertentu, maka tidak ada strategi penyusunnya yang dapat dibuang sebagai akibat dari penerapan prosedur pembuangan strategi yang didominasi secara ketat secara berurutan.

Teorema kebalikannya benar dalam hal keunikan.

Teorema 152:

Jika, sebagai akibat dari penolakan berurutan terhadap strategi yang didominasi secara ketat, setiap pemain hanya mempunyai satu strategi, xi, maka x = (x1, . . . , xm) adalah keseimbangan Nash dalam permainan ini.

Bukti untuk kedua pernyataan ini diberikan dalam Lampiran B (hal. 641). Penting bagi kita di sini bahwa konsep Nash tidak bertentangan dengan gagasan rasionalitas yang melekat dalam prosedur membuang strategi yang didominasi secara ketat.

Tampaknya wajar untuk berasumsi bahwa keseimbangan yang terdefinisi secara wajar tidak dapat dihilangkan dengan membuang strategi yang didominasi secara ketat. Teorema pertama dapat dilihat sebagai konfirmasi bahwa konsep Nash cukup masuk akal. Perhatikan bahwa hasil ini hanya berlaku untuk dominasi ketat. Kita dapat memberikan contoh ekuilibrium Nash dengan satu atau lebih strategi yang didominasi secara lemah (lihat, misalnya, Tabel 16.11 di halaman 652).

16.2.5 Ekuilibrium Nash dalam strategi campuran

Tidaklah sulit untuk membuat contoh permainan yang tidak memiliki keseimbangan Nash. Permainan berikut memberikan contoh situasi seperti itu.

Permainan 6. “Inspeksi”

Dalam permainan ini, pemain pertama (orang yang diuji) dihadapkan pada pilihan - membayar atau tidak membayar pajak penghasilan. Yang kedua, pemeriksa pajak, yang memutuskan perlu atau tidaknya memeriksa wajib pajak tersebut. Jika seorang pemeriksa “menangkap” seorang wajib pajak yang tidak bermoral, ia mengenakan denda kepadanya dan menerima promosi yang lebih dari sekedar kompensasi atas biaya-biayanya; dalam hal pemeriksaan terhadap Wajib Pajak yang sehat, pemeriksa meskipun tidak menerima insentif, namun tetap menanggung biaya yang berkaitan dengan pemeriksaan tersebut. Matriks payoff disajikan pada Tabel 16.9.

Apabila pemeriksa yakin bahwa wajib pajak akan memilih untuk tidak membayar pajak, maka ada baiknya pemeriksa melakukan pemeriksaan tersebut. Sebaliknya, jika wajib pajak yakin akan diperiksa, maka lebih baik ia membayar pajaknya. Begitu pula jika pemeriksa yakin bahwa wajib pajak akan membayar pajak, maka tidak ada gunanya pemeriksa memeriksanya, dan jika wajib pajak yakin bahwa pemeriksa tidak akan memeriksanya, maka ia akan memilih untuk tidak membayar pajak. . Respons optimal ditunjukkan pada tabel dengan menyorot imbalan yang sesuai. Jelasnya, tidak ada sel yang dapat menjadi ekuilibrium Nash, karena tidak ada sel yang menekankan kedua hasil pada saat yang bersamaan.

Dalam permainan seperti itu, setiap pemain berkepentingan untuk memastikan bahwa rekannya tidak dapat menebak strategi mana yang dipilihnya. Hal ini dapat dicapai dengan memasukkan unsur ketidakpastian ke dalam pilihan strategi.

Strategi yang kita bahas sebelumnya biasanya disebut strategi murni. Strategi murni dalam permainan statis pada dasarnya bertepatan dengan tindakan para pemainnya. Namun dalam beberapa permainan, wajar jika memperkenalkan strategi campuran juga. Di bawah strategi campuran memahami distribusi probabilitas pada strategi murni. Dalam kasus khusus ketika himpunan strategi murni setiap pemain terbatas,

Xi = (x1 saya , . . . , xn saya saya )

(permainan yang sesuai disebut terbatas), strategi campuran diwakili oleh vektor probabilitas dari strategi murni yang sesuai:

µi = (µ1 saya , . . . , µn saya saya )

Mari kita nyatakan himpunan strategi campuran pemain ke-i dengan Mi:

Mi = µi µk i > 0, k = 1, . . . , nih; µ1 saya + · · · + µn saya saya = 1

Seperti yang telah kita catat, asumsi standar teori permainan (seperti teori ekonomi) adalah jika imbalannya adalah nilai acak, maka pemain lebih memilih tindakan yang memberi mereka imbalan terbesar yang diharapkan. Hasil yang diharapkan dari pemain ke-i, sesuai dengan himpunan strategi campuran semua pemain, (µ1, . . . , µm), dihitung dengan rumus

Harapannya dihitung berdasarkan asumsi bahwa pemain memilih strategi secara independen (dalam arti statistik).

Strategi campuran dapat direpresentasikan sebagai hasil pengacakan tindakan pemain, yaitu hasil pilihan acaknya. Misalnya, untuk memilih masing-masing dari dua kemungkinan strategi dengan probabilitas yang sama, seorang pemain dapat melempar koin.

Penafsiran ini menyiratkan bahwa pilihan strategi bergantung pada beberapa sinyal yang dapat diamati oleh pemain itu sendiri, namun rekannya tidak bisa17. Misalnya, seorang pemain dapat memilih strategi berdasarkan suasana hatinya, apakah dia mengetahui distribusi probabilitas suasana hatinya, atau bagaimana dia bangkit pada hari itu18.

Definisi 92:

Himpunan strategi campuran µ = (µ1, . . . , µm) adalah Ekuilibrium Nash dalam strategi campuran, Jika

1) strategi µ i setiap pemain merupakan respon terbaiknya terhadap strategi yang diharapkan dari pemain lain µe −i:

U(µi , µe −i ) = maks U(µi , µe −i ) i = 1, . . . , N;

μ aku aku

2) ekspektasi bertepatan dengan strategi yang sebenarnya dipilih:

μe −i = μ−i i = 1, . . . , N.

Perhatikan bahwa ekuilibrium Nash dalam strategi campuran adalah ekuilibrium Nash biasa dalam apa yang disebut perluasan permainan campuran, yaitu permainan yang strategi murninya merupakan strategi campuran dari permainan aslinya.

Mari kita temukan keseimbangan Nash dalam strategi campuran di Game 16.2.5.

Mari kita nyatakan dengan µ kemungkinan wajib pajak tidak membayar pajak penghasilan,

A melalui ν - kemungkinan pemeriksa pajak memeriksa wajib pajak.

DI DALAM Dalam notasi ini, keuntungan yang diharapkan wajib pajak adalah sama dengan

U1 (µ, ν) = µ[ν · (−1) + (1 − ν) · 1] + (1 − µ)[ν · 0 + (1 − ν) · 0] =

= µ(1 − 2ν),

A imbalan yang diharapkan oleh inspektur adalah

U2 (µ, ν) = ν[µ 1 + (1 − µ) (−1)] + (1 − µ)[µ 0 + (1 − µ) 0] = = = ν(2µ − 1 )

Jika probabilitas verifikasinya kecil (ν< 1/2), то налогоплательщику выгодно не платить налог, т. е. выбрать µ = 1. Если вероятность проверки велика, то налогоплательщику выгодно заплатить налог, т. е. выбрать µ = 0. Если же ν = 1/2, то налогоплательщику все равно, платить налог или нет, он может выбрать любую вероятность µ из интервала . Таким образом, отображение отклика налогоплательщика имеет вид:

Dengan argumentasi serupa, kita temukan jawaban pemeriksa pajak:

0 jika µ< 1/2

ν(µ) = , jika µ = 1/2

1 jika µ > 1/2.

17 Jika sinyal yang diamati oleh pemain bergantung secara statistik, maka hal ini dapat membantu pemain mengoordinasikan tindakan mereka. Hal ini mengarah pada konsep keseimbangan berkorelasi.

18 Selanjutnya kita akan mempertimbangkan bagaimana efek pengacakan dapat dicapai dalam kerangka keseimbangan Bayesian.

Grafik respon kedua pemain disajikan pada Gambar. 16.4. Sumbu pada diagram ini mewakili probabilitas (masing-masing ν dan µ). Mereka memiliki satu titik yang sama (1/2, 1/2). Poin ini sesuai dengan ekuilibrium Nash dalam strategi campuran. Dalam keseimbangan ini, seperti yang selalu terjadi dalam keseimbangan dengan strategi campuran nondegenerate (yaitu, dalam keseimbangan di mana tidak ada strategi yang dipilih dengan probabilitas 1), setiap pemain mengacak strategi yang memberikan utilitas yang diharapkan sama. Probabilitas penggunaan strategi murni yang sesuai yang dipilih oleh pemain tidak ditentukan oleh struktur pembayaran pemain tersebut, namun oleh struktur pembayaran rekannya, yang dapat menyebabkan kesulitan tertentu dalam menafsirkan keputusan ini.

Beras. 16.4. Menampilkan umpan balik dalam game "Inspeksi"

Berbeda dengan keseimbangan dalam strategi murni, keseimbangan dalam strategi campuran dalam permainan terbatas selalu ada19, yang merupakan konsekuensi dari pernyataan umum berikut.

Teorema 153:

Mari kita asumsikan bahwa dalam permainan G = hI, (Xi )i I , (ui )i I i untuk setiap pemain, himpunan strategi Xi tidak kosong, kompak dan cembung, dan fungsi pembayaran ui (·) adalah cekung di xi dan kontinu. Maka permainan G memiliki keseimbangan Nash (dalam strategi murni).

Adanya strategi campuran Ekuilibrium Nash dalam permainan dengan jumlah strategi murni yang terbatas merupakan konsekuensi dari kenyataan bahwa keseimbangan strategi campuran adalah keseimbangan strategi murni dalam perluasan permainan campuran.

Teorema 154 (Akibat Akibat (Teorema Nash)):

Ekuilibrium Nash dalam strategi campuran ada dalam permainan terbatas mana pun.

Perhatikan bahwa keberadaan keseimbangan dalam permainan strategi murni tidak mengecualikan keberadaan keseimbangan dalam strategi campuran yang tidak merosot.

Pertimbangkan dalam Game 16.2.1 “Memilih Komputer” sebuah kasus di mana manfaat kompatibilitas sangat signifikan, yaitu a< c и b < c. В этом варианте игры два равновесия в чистых стратегиях: (IBM, IBM) и (Mac, Mac). Обозначим µ и ν вероятности выбора компьютера IBM PC первым и вторым игроком соответственно. Ожидаемый выигрыш 1-го игрока равен

U1 (µ, ν) = µ[ν · (a + c) + (1 − ν) · a] + (1 − µ)[ν · 0 + (1 − ν) · c] = = µ[ν · 2c − (c − a)] + (1 − ν)c

dan tanggapannya terlihat seperti itu

µ(ν) = ,

Pembayaran yang diharapkan dari pemain ke-2 adalah

jika ν< (c − a)/2c

jika ν = (c − a)/2c

jika ν > (c − a)/2c.

U2 (µ, ν) = ν[µ c + (1 − µ) 0] + (1 − ν)[µ b + (1 − µ) (b + c)] =

= ν[µ 2c − (b + c)] + b + (1 − µ)c

dan tanggapannya terlihat seperti itu

ν(µ) = ,

jika µ< (b + c)/2c

jika µ = (b + c)/2c

jika µ > (b + c)/2c.

Grafik tampilan respon dan titik-titik yang sesuai dengan ketiga kesetimbangan ditunjukkan pada Gambar. 16.5. Seperti dapat dilihat, dalam permainan yang sedang dipertimbangkan, selain dua keseimbangan dalam strategi murni, terdapat satu keseimbangan dalam strategi campuran yang tidak merosot. Probabilitas yang bersesuaian adalah sama

µ = b + c dan ν = c − a

Beras. 16.5. Kasus ketika dalam permainan “Computer Choice” terdapat tiga keseimbangan, salah satunya adalah keseimbangan dalam strategi campuran non-degenerasi

Lampiran A

Teorema diulangi, nomornya diperbarui, tidak ada tautan ke aplikasi ini. A dan B dapat ditukar

Teorema 155:

Mari kita asumsikan bahwa dalam permainan G = hI, (Xi )i I , (ui0 )i I i untuk setiap pemain, himpunan strategi Xi tidak kosong, kompak dan cembung, dan fungsi pembayaran ui (·) adalah cekung di xi dan kontinu. Lalu ada keseimbangan Nash.

Bukti: Mari kita buktikan bahwa peta respons, Ri (·), setiap pemain adalah semikontinu atas dan nilainya untuk setiap x−i X−i tidak kosong dan cembung. Ketidakkosongan mengikuti teorema Weierstrass (fungsi kontinu pada himpunan kompak mencapai maksimum).

16.2. Game statis dengan informasi lengkap

Mari kita buktikan konveksitas. Misalkan z0 , z00 Ri (x−i ). Tentu saja, u(z0 , x−i ) = u(z00 , x−i cekung di xi dari fungsi ui (·) maka untuk α

u(αz0 + (1 − α)z00 , x−i ) > αu(z0 , x−i ) + (1 − α)u(z00 , x−i ) =

U(z0 , x−i ) = u(z00 , x−i )

Karena fungsi ui (·) mencapai maksimum pada titik z0 dan z00, maka terjadi pertidaksamaan tegas

mustahil. Dengan demikian,

αz0 + (1 − α)z00 Ri (x−i )

Sekarang mari kita buktikan semikontinuitas atas dari pemetaan Ri (·). Perhatikan barisan xn i yang konvergen ke x¯i dan barisan xn −i yang konvergen ke x¯−i , dan xn i Ri (xn −i ). Perhatikan bahwa karena kekompakan himpunan Xj x¯i Xi dan x¯−i X−i . Kita perlu membuktikan bahwa x¯i Ri (x¯−i ). Menurut definisi pemetaan respons

u(xn saya , xn −i ) > u(xi , xn −i ) xi Xi , n

Dari kontinuitas fungsi ui (·) berikut ini

u(¯xi , x¯−i ) > u(xi , x¯−i ) xi Xi

Jadi, menurut definisi pemetaan respons yang diperkenalkan di atas, x¯i Ri (x¯−i ). Berdasarkan sifat-sifat peta Ri (·) dan teorema Kakutani yang baru saja dibuktikan,

mari kita buktikan keberadaan ekuilibrium Nash, yaitu seperangkat strategi x X untuk

yang telah selesai

xi Ri (x−i ) saya = 1, . . . , N

Kita definisikan pemetaan R(·) dari X ke X sebagai berikut:

R(x) = R1 (x−1 ) × · · · × Rn (x−n )

Perhatikan bahwa pemetaan ini memenuhi sifat yang sama dengan masing-masing pemetaan Ri (·), karena ini adalah hasil kali Kartesiusnya.

Pemetaan R(·) dan himpunan X memenuhi sifat-sifat yang diperlukan agar teorema Kakutani dapat dipenuhi. Dengan demikian, ada titik tetap dalam pemetaan

Lampiran B

Dalam lampiran ini, kami secara formal membuktikan pernyataan tentang hubungan antara ekuilibrium Nash dan prosedur untuk membuang strategi yang didominasi secara ketat secara berurutan.

Pertama, kami secara formal mendefinisikan prosedur untuk membuang strategi yang didominasi secara ketat secara berurutan. Biarkan game aslinya diberikan sebagai

G = hI, (Xi )Saya , (ui )Saya saya.

Mari kita tentukan urutan permainan (G[t] )t=0,1,2,... , yang masing-masing diperoleh dari permainan berikutnya dengan membuang strategi yang didominasi secara ketat. Permainan berbeda satu sama lain dalam rangkaian strategi yang dapat diterima:

G[t] = hI, (Xi [t] )Saya , (ui )Saya saya

Prosedurnya dimulai dengan G= G.

Himpunan strategi yang diperbolehkan dari pemain ke-i pada langkah t + 1 dari prosedur yang dipertimbangkan dianggap sama dengan himpunan strategi yang tidak didominasi secara ketat dari pemain ke-i dalam permainan pada langkah ke-t. Kami akan menunjukkan rangkaian strategi yang tidak didominasi secara ketat dengan NDi (lihat definisi strategi yang didominasi secara ketat (Definition89, hal. 631)). Secara formal

NDi = xi Xi yi Xi : ui (yi , x−i ) > ui (xi , x−i ) x−i X−i

Dengan demikian, kita dapat menuliskan langkah prosedur yang dimaksud sebagai berikut:

X saya = ND saya [t]

dimana NDi [t] adalah himpunan strategi yang tidak didominasi dalam permainan G[t] .

Sekarang mari kita sajikan bukti Teorema 151 dan 152 (hal. 636). Teorema 151 menyatakan sebagai berikut:

: Jika x = (x1, . . . , xm) adalah ekuilibrium Nash dalam beberapa permainan, maka tidak ada strategi yang dapat dibuang sebagai akibat dari penerapan prosedur untuk membuang strategi yang didominasi secara ketat secara berurutan.

Dengan menggunakan notasi yang baru saja diperkenalkan, Teorema 151 menyatakan bahwa jika x adalah keseimbangan Nash pada permainan awal G, maka pada setiap langkah t

xi Xi [t] , saya saya, t = 1, 2, . . .

x X[t] , t = 1, 2, . . .

Bukti (Bukti Teorema 151): Misalkan ada langkah τ sedemikian rupa sehingga strategi xi dari beberapa pemain i I harus dibuang. Diasumsikan bahwa tidak ada strategi yang dibuang pada langkah sebelumnya:

x X[t] , t = 1, . . . , τ.

Berdasarkan definisi dominasi ketat, ada strategi lain untuk pemain i, x0 i Xi [τ], yang memberikan pemain ini dalam permainan G[τ] imbalan yang lebih tinggi untuk pilihan lainnya

ui (x0 saya , x−i ) > ui (xi , x−i ) x−i X− [τ saya ]

Secara khusus, hubungan ini harus berlaku untuk x−i, karena kita berasumsi bahwa strategi x−i tidak dibuang pada langkah prosedur sebelumnya (x−i X− [τ i ]). Cara,

: Jika, sebagai akibat dari membuang strategi yang didominasi secara ketat, setiap pemain hanya mempunyai satu strategi, xi, maka x = (x1, . . . , xm) adalah keseimbangan Nash dalam permainan ini.

Teorema ini berlaku untuk kasus ketika, dalam proses membuang, didominasi secara ketat

strategi dimulai dari beberapa langkah ¯ hanya tersisa satu rangkaian strategi, yaitu t x

Teorema tersebut menyatakan bahwa x adalah ekuilibrium Nash unik dari permainan aslinya.

Bukti (Bukti Teorema 152): Karena, berdasarkan teorema yang baru saja dibuktikan, tidak ada satupun ekuilibria Nash yang dapat dibuang, kita hanya perlu membuktikan bahwa himpunan strategi x yang ditentukan adalah ekuilibrium Nash. Mari kita berasumsi bahwa hal ini tidak terjadi. Artinya ada strategi x˜i dari beberapa pemain i sedemikian rupa

ui (xi , x−i )< ui (˜xi , x−i )

Dengan asumsi, strategi x˜i dibuang pada beberapa langkah τ karena tidak bertepatan dengan xi. Jadi, ada beberapa strategi yang sangat dominan x0 i Xi [τ] , jadi

ui (x0 saya , x−i ) > ui (˜xi , x−i ) x−i X− [τ saya ]

Khususnya, pertidaksamaan ini berlaku untuk x−i = x−i:

ui (x0 saya , x−i ) > ui (˜xi , x−i )

Strategi x0 i tidak dapat bertepatan dengan strategi xi, karena dalam hal ini pertidaksamaan di atas saling bertentangan. Selanjutnya, harus ada strategi x00 i yang mendominasi strategi x0 i pada langkah tertentu τ0 > τ, yaitu.

Termasuk

ui (x00 saya , x−i ) > ui (x0 saya , x−i )

Sekali lagi dapat dikatakan bahwa strategi x00 i tidak dapat bertepatan dengan strategi xi, jika tidak maka pertidaksamaan di atas akan saling bertentangan.

Melanjutkan argumen ini, kita memperoleh urutan langkah τ< τ0 < τ00 < . . .

dan strategi terkait yang diperbolehkan x0 i , x00 i , x000 i , . . ., tidak bertepatan dengan xi . Ini adalah kontra-

/ 667. Dua pemain menempatkan suatu benda pada bidang, yaitu memilih koordinatnya (x, y). Pemain 1 berada di titik (x 1, y1), dan pemain 2 berada di titik (x2, y2). Pemain 1 memilih koordinat x dan pemain 2 memilih koordinat y. Setiap orang berusaha untuk menempatkan objek sedekat mungkin dengannya. Tunjukkan bahwa dalam permainan ini setiap pemain mempunyai strategi yang sangat dominan.

/ 668. Buktikan bahwa jika dalam suatu permainan setiap pemain mempunyai strategi yang sangat dominan, maka strategi tersebut merupakan satu-satunya keseimbangan Nash.

/ 669. Jelaskan mengapa ekuilibrium strategi dominan juga harus berupa ekuilibrium Nash. Berikan contoh permainan yang terdapat keseimbangan strategi dominan dan terdapat pula keseimbangan Nash yang tidak sesuai dengan keseimbangan strategi dominan.

Temukan semua keseimbangan Nash di game berikut.

/ 670. Game 16.2.1 (hal.625), yang kemenangannya disajikan dalam Tabel??////??

/ 671. “Kacang”

Dua pemain berbagi 4 kacang. Setiap orang mengajukan tawaran untuk kacang: xi = 1, 2 atau 3. Jika x1 + x2 6 4, maka setiap orang mendapat apa yang diminta, jika tidak, keduanya tidak mendapat apa-apa.

/ 672. Dua orang guru Fakultas Ekonomi sedang menulis buku pelajaran. Kualitas buku teks (q) tergantung pada usahanya (masing-masing e1 dan e2) sesuai fungsinya

q = 2(e1 + e2 ).

Fungsi tujuan masing-masing mempunyai bentuk

ui = q − ei ,

yaitu kualitas dikurangi usaha. Anda dapat memilih upaya tingkat 1, 2 atau 3.

/ 673. “Roda ketiga” Masing-masing dari tiga pemain memilih salah satu sisi mata uang: “kepala” atau “ekor”. Jika

Jika pilihan para pemain bertepatan, maka setiap pemain diberikan 1 rubel. Jika pilihan salah satu pemain berbeda dengan pilihan dua pemain lainnya, maka dia membayar mereka 1 rubel.

/ 674. Tiga pemain memilih salah satu dari tiga alternatif: A, B atau C. Alternatifnya dipilih berdasarkan suara terbanyak. Setiap pemain memilih satu dan hanya satu alternatif. Jika tidak ada alternatif yang mendapat suara mayoritas, maka alternatif A yang akan dipilih. Imbalan para pemain, bergantung pada alternatif yang dipilih, adalah sebagai berikut:

u1 (A) = 2, u2 (A) = 0, u3 (A) = 1,

u1 (B) = 1, u2 (B) = 2, u3 (B) = 0,

u1 (C) = 0, u2 (C) = 1, u3 (C) = 2.

/ 675. Dua blok pemilu sedang dibentuk untuk bersaing memperebutkan kursi di dewan legislatif kota N-sk. Setiap blok dapat memilih salah satu dari tiga orientasi: “kiri” (kiri), “kanan” (kanan) dan “ekologis” (E). Setiap orientasi masing-masing dapat menarik 50, 30 dan 20% pemilih. Diketahui, jika orientasi yang mereka minati tidak terwakili dalam pemilu, maka pemilih dari kelompok yang bersangkutan tidak akan memilih. Jika blok-blok tersebut memilih orientasi yang berbeda, masing-masing blok akan menerima bagian suara yang sesuai. Jika blok-blok tersebut memilih orientasi yang sama, maka suara dari kelompok pemilih yang bersangkutan akan dibagi rata di antara mereka. Tujuan dari setiap blok adalah untuk mendapatkan jumlah terbesar suara.

/ 676. Dua pemain menempatkan satu titik pada pesawat. Satu pemain memilih absis, yang lain -

ordinat. Kemenangan mereka diberikan oleh fungsi:

a) ux (x, y) = −x2 + x(y + a) + y2 , uy (x, y) = −y2 + y(x + b) + x2 ,

b) ux (x, y) = −x2 − 2ax(y + 1) + y2 , uy (x, y) = −y2 + 2by(x + 1) + x2 , c) ux (x, y) = − x − y/x + 1/2y2 , uy (x, y) = −y − x/y + 1/2x2 ,

(a, b - koefisien).

/ 677. "Pria Es Krim di Pantai"

Dua pembuat es krim menjual es krim di pantai pada hari yang panas. Pantai dapat dianggap sebagai satu segmen. Pembuat es krim memilih di mana mereka seharusnya berada di pantai, yaitu memilih koordinat xi. Pelanggan tersebar merata di sepanjang pantai dan membeli es krim dari penjual terdekat. Jika x1< x2 , то первый обслуживают (x1 + x2 )/2 долю пляжа, а второй - 1 − (x1 + x2 )/2. Если мороженщики расположатся в одной и той же точке (x1 = x2 ), покупатели поровну распределятся между ними. Каждый мороженщик стремиться обслуживать как можно bagian yang besar pantai

/ 678. "Lelang" Pertimbangkan lelang seperti yang dijelaskan dalam Game 16.2.2, dengan syarat pemenangnya

lelang pemain membayar harga yang dia sebutkan.

/ 679. Analisis Game 16.2.1 “Memilih Komputer” (hal. 624) dan temukan jawaban atas pertanyaan-pertanyaan berikut:

a) Dalam kondisi apa pada parameter a, b dan c akan terjadi keseimbangan dalam strategi dominan? Keseimbangan ini akan seperti apa?

b) Dalam kondisi parameter apa hasil ketika keduanya memilih IBM ekuilibrium Nash? Kapan keseimbangan ini menjadi satu-satunya? Mungkinkah ini juga merupakan keseimbangan dalam strategi dominan?

/ 680. Masing-masing dari dua tetangga di pintu masuk memilih apakah dia akan menyapu pintu masuk seminggu sekali atau tidak. Biarkan setiap orang mengevaluasi sendiri manfaat dari kemurnian ganda pada > 0 satuan moneter, keuntungan dari kebersihan tunggal ada di b > 0 satuan, dari pintu masuk yang tidak bersih - di 0, dan biaya partisipasi pribadi Anda dalam pembersihan - di c > 0. Berapakah perbandingan antara a, b, dan c dalam permainan? keseimbangan bentuk: (0 ) tidak ada yang membersihkan, (1) ada yang membersihkan, (2) keduanya bersih?

/ 681. Misalkan dalam permainan tertentu yang terdiri dari dua pemain, yang masing-masing memiliki 2 strategi, terdapat keseimbangan Nash yang unik. Tunjukkan bahwa dalam permainan ini setidaknya salah satu pemain memiliki strategi yang dominan.

/ 682. Masing-masing dari dua pemain (i = 1, 2) mempunyai 3 strategi: a, b, c dan x, y, z. Mengambil namanya sebagai rangkaian karakter yang tak terbatas seperti iwaniwaniwan. . . , tetapkan hasil pemain pertama sebagai berikut: u1 (a, x) = “dan”, u1 (a, y) = “dalam”, u1 (a, z) = “a”, u1 (b, x) = “n”, u1 (b, y) = “dan”, u1 (b, z) = “dalam”, u1 (c, x) = “a”, u1 (c, y) = “n”, u1 (c, z ) = "dan". Alih-alih setiap huruf dalam nama, gantikan nomornya dengan alfabet, yang menggunakan Tabel 16.10. Dengan menggunakan nama belakang dengan cara yang sama, tentukan hadiah pemain kedua, u2 (·).

1) Apakah ada strategi yang dominan dan sangat dominan dalam permainan Anda? Jika ya, apakah strategi-strategi tersebut membentuk keseimbangan dalam strategi dominan?

2) Apa akibat dari penolakan terus-menerus terhadap strategi yang didominasi secara ketat?

3) Temukan keseimbangan Nash dari permainan ini.

Tabel 16.10.

/ 683. Buatlah permainan matriks yang terdiri dari tiga pemain dengan menggunakan nama depan, nama belakang dan patronimik yang masing-masing mempunyai 2 strategi. Jawablah pertanyaan pada tugas sebelumnya.

/ 684. Isikan kemenangan yang hilang pada tabel berikut sehingga menghasilkan permainan. . .

(0) tidak ada keseimbangan Nash,

(4) ada empat keseimbangan Nash.

/ 685. 1) Jelaskan mengapa dalam ekuilibrium Nash ada imbalannya Pemain ke-i tidak boleh kurang dari

min maks ui (xi , x−i ).

x −iX −ix iX saya

2) Jelaskan mengapa dalam ekuilibrium Nash mana pun, hasil dari pemain ke-i tidak dapat diperoleh

Teori permainan adalah ilmu yang menggunakan metode matematika untuk mempelajari perilaku partisipan dalam situasi yang mungkin berkaitan dengan pengambilan keputusan. Subyek teori ini adalah situasi permainan dengan aturan yang telah ditetapkan sebelumnya. Selama permainan, berbagai aksi bersama dimungkinkan - koalisi pemain, konflik...

Sering dicatat bahwa oligopoli sebenarnya adalah permainan karakter - permainan di mana, seperti dalam catur atau poker, setiap pemain harus memprediksi tindakan lawan - gertakannya, aksi balasannya, gertakan balasannya - sebaik mungkin. . Oleh karena itu, para ekonom oligopoli senang dengan munculnya buku yang sangat banyak dan sangat matematis pada tahun 1944 berjudul Game Theories and Economic Behavior.

Strategi pemain ditentukan oleh fungsi tujuan yang menunjukkan menang atau kalahnya peserta. Bentuk permainan ini bermacam-macam. Paling variasi sederhana– permainan dengan dua peserta. Jika sebuah permainan melibatkan setidaknya tiga pemain, koalisi dapat terbentuk, sehingga mempersulit analisis. Dari sudut pandang jumlah pembayaran, permainan dibagi menjadi dua kelompok - zero-sum dan non-zero-sum. Permainan zero-sum juga disebut permainan zero-sum: keuntungan beberapa pihak sama persis dengan kerugian yang lain, dan jumlah total kemenangannya sama dengan 0. Berdasarkan sifat kesepakatan awal, permainan dibedakan menjadi kooperatif dan non kooperatif.

Contoh paling terkenal dari permainan non-zero-sum non-kooperatif adalah dilema tahanan.

Jadi. 2 pencuri tertangkap basah dan didakwa melakukan sejumlah pencurian. Masing-masing dari mereka menghadapi dilema - apakah akan mengakui pencurian lama (yang belum terbukti) atau tidak. Apabila hanya 1 orang pencuri yang mengaku, maka yang mengaku diancam dengan pidana penjara paling singkat 1 tahun, dan yang lain paling lama 10 tahun. Jika kedua pencuri mengaku pada saat yang sama, maka keduanya akan menerima keringanan hukuman kecil - 6 tahun, tetapi jika keduanya tidak mengaku, maka mereka akan dihukum hanya untuk pencurian terakhir - 3 tahun. Para tahanan duduk di sel yang berbeda dan tidak bisa sepakat satu sama lain. Ini adalah permainan non-kooperatif dengan jumlah bukan nol (negatif). Ciri khas dari permainan ini adalah tidak menguntungkan bagi kedua peserta untuk dibimbing oleh kepentingan pribadinya. “Dilema tahanan” dengan jelas menunjukkan ciri-ciri penetapan harga oligopolistik.

3.1. Keseimbangan Nash

(Dinamakan menurut John Forbes Nash) dalam teori permainan, suatu jenis keputusan dalam permainan dua pemain atau lebih di mana tidak ada satu peserta pun yang dapat meningkatkan hasil dengan mengubah keputusannya secara sepihak ketika peserta lain tidak mengubah keputusannya. Rangkaian strategi yang dipilih oleh para partisipan dan imbalannya disebut ekuilibrium Nash.

Konsep ekuilibrium Nash (NE) sebenarnya tidak diciptakan oleh Nash, Antoine Augustine Cournot menunjukkan cara menemukan apa yang kita sebut ekuilibrium Nash dalam permainan Cournot. Oleh karena itu, beberapa penulis menyebutnya keseimbangan Nash-Cournot. Namun, Nash adalah orang pertama yang menunjukkan dalam disertasinya Noncooperative Games (1950) bahwa keseimbangan Nash harus ada untuk semua permainan berhingga dengan jumlah pemain berapa pun. Sebelum Nash, hal ini hanya dibuktikan pada permainan zero-sum 2 pemain oleh John von Neumann dan Oskar Morgernstern (1947).

Definisi formal.

Mari kita asumsikan bahwa ini adalah permainan yang terdiri dari n orang dalam bentuk normal, yang merupakan himpunan strategi murni, dan merupakan himpunan hasil. Ketika setiap pemain memilih strategi di profil strategi, pemain tersebut menerima kemenangan. Perhatikan bahwa kemenangan bergantung pada keseluruhan profil strategi: tidak hanya pada strategi yang dipilih oleh pemain itu sendiri, tetapi juga pada strategi orang lain. Profil strategi adalah ekuilibrium Nash jika mengubah strategi tidak bermanfaat bagi pemain mana pun, yaitu bagi siapa pun:

Sebuah permainan dapat memiliki ekuilibrium Nash dalam strategi murni atau strategi campuran (yaitu, memilih strategi murni secara stokastik dengan frekuensi tetap). Nash membuktikan bahwa jika strategi campuran diperbolehkan, maka dalam setiap permainan n pemain akan ada paling sedikit satu keseimbangan Nash.

Sepanjang hidupnya, seseorang dipaksa untuk membuat keputusan tertentu mengenai berbagai macam masalah, mulai dari perselisihan sehari-hari - siapa yang akan membersihkan kamar di rumah atau bagaimana memperbaiki kotanya, hingga negosiasi internasional, lelang jutaan dolar, dan bahkan militer. tindakan. Dan dalam semua situasi ini, seseorang berusaha memaksimalkan keuntungannya sendiri. Namun pada saat yang sama, ia selalu harus memilih: bekerja sama dengan orang lain atau hanya memikirkan keuntungannya sendiri, tanpa mempedulikan keuntungan orang lain. Sebuah contoh klasik yang menunjukkan bahwa dalam mengejar keuntungan pribadi tidak selalu mungkin untuk dicapai hasil terbaik, berbicara "Dilema Tahanan".

Dua narapidana A dan B diduga melakukan tindak pidana dengan ancaman hukuman maksimal 10 tahun penjara. Namun belum ada bukti langsung. Oleh karena itu, penyelidikan menawarkan masing-masing tahanan untuk membuat kesepakatan - untuk mengakui apa yang mereka lakukan dan menyalahkan inisiatif kejahatan tersebut pada orang lain. Jika salah satu mengaku dan tahanan lainnya tetap diam, maka tahanan pertama akan dikurangi hukumannya menjadi tiga tahun untuk membantu penyelidikan, dan yang kedua akan dipenjara selama 10 tahun.

Jika keduanya membuat kesepakatan dengan penyelidikan dan mengakui kejahatannya, maka masing-masing akan menerima hukuman 5 tahun. Namun jika keduanya bungkam, maka karena kurang bukti maka akan dibebaskan. Para narapidana berada di sel yang berbeda sehingga tidak bisa saling sepakat dan mengoordinasikan perilakunya selama interogasi. Tak satu pun dari mereka tahu persis apa yang akan dilakukan satu sama lain. Keputusan apa yang akan diambil masing-masing dari mereka? Apa yang akan terjadi?

Setiap narapidana punya pilihan: diam atau mengaku. Inilah dilema narapidana: haruskah dia memberatkan orang lain atau haruskah dia mencoba peruntungannya dan tidak mengaku, mengambil risiko besar? Tergantung pada pilihan narapidana dalam situasi ini, ada empat kemungkinan hasil.

Mari kita lihat:

1. Jika kedua narapidana mengaku, masing-masing mendapat hukuman lima tahun penjara;

2. Jika narapidana A tetap diam, dan narapidana B memberikan kesaksian yang memberatkannya, maka narapidana pertama akan dipenjara selama 10 tahun, dan narapidana kedua selama tiga tahun;

3. Begitu pula sebaliknya, jika narapidana A mengaku, dan narapidana B diam, maka narapidana pertama dipenjara tiga tahun, dan narapidana kedua 10 tahun;

4. Dan jika keduanya tetap bungkam, maka karena kurang bukti maka mereka dibebaskan.

Manakah dari hasil berikut yang paling realistis? Untuk menjawab pertanyaan ini, Anda perlu mengetahui alasan masing-masingnya. Beginilah alasan Tahanan A:

« Katakanlah tahanan B mengaku. Kalau saya juga mengaku, saya dapat hukuman 5 tahun. Jika saya tetap diam, saya akan mendapat 10 tahun. Jadi kalau napi B mengaku, mending aku juga mengakui perbuatanku.

Jika tahanan B tetap diam, apa yang harus saya lakukan? Jika saya mengaku, saya akan mendapat 3 tahun. Dan jika aku juga tetap diam, aku akan bebas. Tentu saja, pilihan sempurna, tapi aku tidak yakin tahanan B akan tinggal diam, aku tidak percaya padanya. Jadi sebaiknya saya bersaksi.

Jadi, apa pun yang dilakukan Tahanan B, sebaiknya aku mengaku.”

Alasan Tahanan B serupa, dan dia juga sampai pada kesimpulan bahwa lebih baik dia mengaku, terlepas dari apa yang dilakukan Tahanan A.

Apa yang terjadi? Masing-masing narapidana memilih strategi yang meskipun tidak memberikan hasil terbaik (pembebasan), namun merupakan yang terbaik bagi masing-masing narapidana untuk setiap perilaku lawannya. Karena tujuan masing-masing narapidana adalah meminimalkan hukumannya tanpa mempedulikan narapidana lainnya, maka mengakui dan memberatkan satu sama lain adalah strategi yang paling menguntungkan bagi mereka masing-masing. Sederhananya, apa pun yang dilakukan pihak lain, setiap orang akan mendapatkan lebih banyak keuntungan dengan berkhianat. Oleh karena itu, para narapidana akan memilih strategi “Mengaku” dan akan menerima hukuman 5 tahun penjara.

Jadi, dalam contoh ini, kita melihat bahwa keputusan yang dibuat oleh satu pemain mempengaruhi keputusan pemain lain (dan sebaliknya) dan pada akhirnya mempengaruhi hasil akhir permainan.

Contoh lain permainan yang melibatkan orang-orang dengan tujuan yang berbeda (berlawanan), yang hasilnya bergantung pada keputusan semua peserta, adalah poker, catur, penalti dalam sepak bola, dan banyak permainan lainnya.

Namun selain permainan tradisional, ada juga permainan antar manusia. hubungan serius seperti persaingan pasar, perlombaan senjata, polusi lingkungan, pemilu, perdagangan, dll. Misalnya, perusahaan yang bersaing di pasar harus memperhatikan tindakan pesaing ketika mengambil keputusan. Atau contoh ilustratif lainnya - perlombaan senjata antar negara Uni Soviet dan Amerika pada 1950-1990an. Selama hampir setengah abad, kedua negara besar ini menghabiskan banyak uang untuk membeli senjata, mengimbangi satu sama lain. Jika ada kepercayaan di antara mereka, mereka tidak akan menghabiskan banyak uang untuk membeli senjata, tetapi akan membelanjakannya dengan bijak HAI manfaat yang lebih besar (untuk pendidikan, kesehatan, pensiun, dll.) dan kedua belah pihak akan mendapatkan manfaat dari hal ini. Namun sebaliknya, masing-masing negara, karena tidak mempercayai negara lain, terus memproduksi senjata dan tidak ada yang mendapat keuntungan dari hal ini.

Semua hubungan serius ini disebut juga permainan, karena di dalamnya, seperti dalam permainan biasa, hasilnya bergantung pada keputusan (strategi) seluruh peserta. Dan ilmu yang mempelajari hubungan serius ini disebut teori permainan . Oleh karena itu, kata "permainan" di pada kasus ini seharusnya tidak membawa Anda ke dalam kebingungan. Konsep ini ditafsirkan lebih luas dalam teori permainan dibandingkan dalam kehidupan sehari-hari.

Keseimbangan Nash

Jadi, dalam Dilema Tahanan, situasinya berkembang sedemikian rupa sehingga, dengan bertindak secara individu secara rasional dan wajar, para narapidana akhirnya mendapatkan hukuman lima tahun penjara. Namun, sebagaimana telah kami catat, ini bukanlah hasil yang paling optimal. Ada pilihan yang lebih baik: dibebaskan jika keduanya tetap diam.

Tentunya setiap narapidana dalam mengambil keputusan beralasan seperti ini: “Jika kami berdua tetap diam, kami akan bebas. Tentu saja ini lebih baik daripada dipenjara lima tahun. Tapi di manakah jaminan bahwa yang kedua juga akan tetap diam? Lagi pula, jika saya tetap diam dan orang lain bersaksi, maka saya akan masuk penjara selama 10 tahun! Tidak, saya lebih suka mengakui perbuatan saya.”

Jelas bahwa rasa saling tidak percaya satu sama lain tidak memungkinkan terjadinya situasi ketika semua orang dibebaskan. Selain itu, para narapidana duduk di sel yang berbeda dan masing-masing mengambil keputusan tanpa mengetahui keputusan yang lain dan masing-masing tergoda untuk bersaksi melawan yang lain dan mendapat hukuman 3 tahun, bukannya 5 atau 10 tahun. Ternyata hasil terbaik – untuk dilepaskan – tidak dapat diandalkan dan tidak stabil. Itulah sebabnya para narapidana memilih strategi yang, jika bukan memberikan hasil terbaik, namun dapat diandalkan dan menghilangkan risiko penipuan dan pengkhianatan. Hasil ini disebut ekuilibrium Nash.

Keseimbangan Nash (Nash keseimbangan) adalah kombinasi strategi pemain dan kemenangannya sedemikian rupa sehingga tidak ada pemain yang dapat meningkatkan kemenangannya dengan mengubah strateginya, kecuali peserta lain mengubah strateginya. Catatan: Ekuilibria Nash terjadi dalam permainan di mana para pemain bertindak secara independen satu sama lain dan tidak dapat bekerja sama dan mengoordinasikan tindakan mereka.

Secara sederhana, ekuilibrium Nash adalah situasi di mana strategi masing-masing pemain merupakan respons terbaik terhadap strategi pemain lain dan tidak menguntungkan bagi setiap pemain untuk mengubah strateginya.

Ekuilibrium Nash bukanlah hasil yang terbaik, namun dalam situasi di mana setiap orang bermain untuk diri mereka sendiri, ini adalah hasil yang optimal untuk setiap pemain karena menghilangkan risiko dan kerugian yang akan dialami setiap pemain jika pemain lain memutuskan untuk menipu atau mengkhianatinya.

Ekuilibrium Nash adalah ekuilibrium yang stabil karena merupakan keuntungan bagi para pemain untuk mempertahankannya, karena perubahan apa pun akan membuat keadaan mereka lebih buruk. Namun jika kerjasama muncul dalam hubungan antar pemain, maka keseimbangan Nash tidak lagi menjadi keseimbangan, karena menjadi mungkin untuk mencapai hasil yang lebih baik. Misalnya, jika dalam “Dilema Tahanan” para pemain memiliki kesempatan untuk menyepakati kerja sama, yaitu keduanya harus diam, atau jika mereka yakin bahwa pihak lain tidak akan berkhianat dan juga akan diam, maka situasi bisa berakhir bagi keduanya dengan hasil yang lebih baik - pelepasan.

Kesimpulan: Ekuilibrium Nash menunjukkan bahwa setiap pemain bisa menang lebih banyak jika ada kerja sama, kepercayaan dan kejujuran di antara para pemain, dan setiap pemain, dengan berbuat lebih baik untuk orang lain, akan berbuat lebih baik untuk dirinya sendiri.

Ilustrasi dari postnauka.com

Dan Oscar Morgenstern menjadi pendiri cabang matematika baru yang menarik, yang disebut “teori permainan”. Pada tahun 1950-an, matematikawan muda John Nash menjadi tertarik pada bidang ini. Teori keseimbangan menjadi topik disertasinya yang ditulisnya saat berusia 21 tahun. Maka lahirlah strategi permainan baru yang disebut "Nash Equilibrium", yang pantas mendapatkan Hadiah Nobel bertahun-tahun kemudian - pada tahun 1994.

Jarak yang jauh antara penulisan disertasi dan pengakuan umum menjadi ujian bagi para ahli matematika. Kejeniusan yang tidak dikenali mengakibatkan gangguan mental yang serius, namun John Nash mampu menyelesaikan masalah ini berkat pikiran logisnya yang sangat baik. Teorinya tentang “keseimbangan Nash” memenangkan Hadiah Nobel, dan hidupnya difilmkan dalam film “Beautiful Mind”.

Secara singkat tentang teori permainan

Karena teori ekuilibrium Nash menjelaskan perilaku manusia dalam lingkungan interaksional, maka ada baiknya meninjau kembali konsep dasar teori permainan.

Teori permainan mempelajari perilaku partisipan (agen) dalam kondisi interaksi satu sama lain seperti permainan, ketika hasilnya bergantung pada keputusan dan perilaku beberapa orang. Peserta mengambil keputusan berdasarkan prediksinya tentang perilaku orang lain, yang disebut strategi permainan.

Ada pula strategi dominan, dimana seorang partisipan memperoleh hasil yang optimal atas setiap perilaku partisipan lainnya. Ini adalah strategi win-win terbaik pemain.

Dilema Tahanan dan Terobosan Ilmiah

Dilema tahanan adalah permainan di mana peserta dipaksa untuk membuat keputusan rasional untuk mencapai tujuan bersama dalam menghadapi alternatif yang saling bertentangan. Pertanyaannya adalah pilihan mana yang akan dia pilih, dengan menyadari kepentingan pribadi dan umum, serta ketidakmungkinan mendapatkan keduanya. Pemain sepertinya terjebak dalam kondisi permainan yang ketat, yang terkadang memaksa mereka untuk berpikir sangat produktif.

Dilema ini dipelajari oleh seorang matematikawan Amerika dan keseimbangan yang ia peroleh bersifat revolusioner. Ide baru ini sangat jelas mempengaruhi pendapat para ekonom tentang bagaimana pelaku pasar membuat pilihan, dengan mempertimbangkan kepentingan orang lain, dengan interaksi yang erat dan persinggungan kepentingan.

Cara terbaik untuk mempelajari teori permainan adalah contoh spesifik, karena disiplin matematika ini sendiri bukanlah teori yang kering.

Contoh Dilema Tahanan

Misalnya, dua orang melakukan perampokan, jatuh ke tangan polisi dan diinterogasi di sel terpisah. Pada saat yang sama, petugas polisi menawarkan setiap peserta istilah yang menguntungkan, di mana dia akan dibebaskan jika dia bersaksi melawan rekannya. Setiap penjahat memiliki serangkaian strategi berikut yang akan ia pertimbangkan:

1. Keduanya bersaksi pada waktu yang sama dan menerima hukuman 2,5 tahun penjara.
2. Keduanya tetap bungkam pada saat yang sama dan menerima hukuman masing-masing 1 tahun, karena dalam kasus ini dasar bukti kesalahan mereka akan kecil.
3. Yang satu bersaksi dan mendapat kebebasan, sedangkan yang lain bungkam dan mendapat hukuman 5 tahun penjara.

Tentu saja, hasil kasus ini bergantung pada keputusan kedua peserta, namun mereka tidak bisa mencapai kata sepakat, karena mereka duduk di sel yang berbeda. Benturan kepentingan pribadi dalam perebutan kepentingan bersama juga terlihat jelas. Setiap tahanan memiliki dua pilihan tindakan dan 4 kemungkinan hasil.

Rantai kesimpulan logis

Jadi, penjahat A mempertimbangkan pilihan berikut:

1. Saya diam dan pasangan saya diam - kami berdua akan mendapat hukuman 1 tahun penjara.
2. Saya menyerahkan pasangan saya dan dia menyerahkan saya - kami berdua mendapat hukuman 2,5 tahun penjara.
3. Saya tetap diam, dan pasangan saya mengadukan saya - saya mendapat 5 tahun penjara, dan dia mendapat kebebasan.
4. Saya menyerahkan pasangan saya, tetapi dia tetap diam - saya mendapatkan kebebasan, dan dia mendapat 5 tahun penjara.

Mari kita sajikan matriksnya solusi yang memungkinkan dan hasil untuk kejelasan.

Tabel kemungkinan hasil dari dilema narapidana.

Pertanyaannya, apa yang akan dipilih masing-masing peserta?

“Kamu tidak bisa diam, kamu tidak bisa berbicara” atau “Kamu tidak bisa diam, kamu tidak bisa berbicara”

Untuk memahami pilihan peserta, Anda perlu mengikuti alur pemikirannya. Mengikuti alasan pidana A: jika saya diam dan pasangan saya diam, kami akan menerima hukuman minimal (1 tahun), tetapi saya tidak tahu bagaimana dia akan berperilaku. Jika dia bersaksi melawan saya, lebih baik saya bersaksi juga, kalau tidak saya bisa masuk penjara selama 5 tahun. Lebih baik saya mengabdi 2,5 tahun daripada 5 tahun. Jika dia tetap diam, maka saya harus lebih banyak bersaksi, karena dengan cara ini saya akan mendapat kebebasan. Peserta B berpendapat dengan cara yang persis sama.

Tidak sulit untuk memahami bahwa strategi dominan setiap penjahat adalah memberikan kesaksian. Titik optimal dari permainan ini datang ketika kedua penjahat bersaksi dan menerima “hadiah” mereka - 2,5 tahun penjara. Teori permainan Nash menyebut hal ini sebagai keseimbangan.

Solusi optimal Nash yang suboptimal

Sifat revolusioner dari pandangan Nash tidaklah optimal jika kita mempertimbangkan partisipan individu dan kepentingan pribadinya. Lagipula pilihan terbaik- adalah tetap diam dan bebas.

Ekuilibrium Nash merupakan titik konvergensi kepentingan, dimana setiap partisipan memilih opsi yang optimal baginya hanya jika partisipan lain memilih strategi tertentu.

Mempertimbangkan opsi ketika kedua penjahat tetap diam dan hanya menerima hukuman 1 tahun, kita dapat menyebutnya sebagai opsi Pareto-optimal. Namun, hal itu hanya mungkin terjadi jika para penjahat bisa mencapai kesepakatan terlebih dahulu. Namun hal ini pun tidak menjamin hasil yang diharapkan, karena godaan untuk mundur dari perjanjian dan menghindari hukuman sangatlah besar. Kurangnya kepercayaan penuh satu sama lain dan bahaya hukuman 5 tahun memaksa kami untuk memilih opsi pengakuan dosa. Sangatlah tidak masuk akal untuk berpikir bahwa para peserta akan tetap berpegang pada pilihan diam saat bertindak dalam konser. Kesimpulan ini dapat ditarik dengan mempelajari keseimbangan Nash. Contoh hanya membuktikan maksudnya.

Egois atau rasional

Teori ekuilibrium Nash menghasilkan temuan menakjubkan yang menyangkal prinsip-prinsip yang sudah ada sebelumnya. Misalnya, Adam Smith memandang perilaku setiap peserta sebagai tindakan yang sangat egois, sehingga membuat sistem menjadi seimbang. Teori ini disebut " tangan tak kasat mata pasar".

John Nash melihat bahwa jika semua peserta bertindak hanya demi kepentingan mereka sendiri, hal ini tidak akan pernah menghasilkan hasil kelompok yang optimal. Mengingat pemikiran rasional melekat pada setiap peserta, maka pilihan yang ditawarkan oleh strategi ekuilibrium Nash lebih mungkin terjadi.

Eksperimen murni laki-laki

Contoh utama adalah permainan Blonde Paradox, yang meskipun tampaknya tidak tepat, merupakan ilustrasi yang jelas tentang cara kerja teori permainan Nash.

Dalam permainan ini Anda perlu membayangkan sekelompok orang bebas datang ke sebuah bar. Ada sekelompok gadis di dekatnya, salah satunya lebih disukai daripada yang lain, katakanlah seorang pirang. Bagaimana seharusnya pria bersikap untuk mendapatkan sahabat untuk diriku?

Jadi, alasan para pria: jika semua orang mulai mengenal si pirang, kemungkinan besar tidak ada yang akan mendapatkannya, maka teman-temannya juga tidak akan mau bertemu dengannya. Tidak ada seorang pun yang ingin menjadi pilihan kedua. Namun jika para pria memilih untuk menghindari si pirang, maka kemungkinan masing-masing pria menemukan teman baik di antara para wanita adalah tinggi.

Situasi keseimbangan Nash tidak optimal untuk pria, karena hanya mengejar kepentingan egoisnya sendiri, semua orang akan memilih si pirang. Dapat dilihat bahwa hanya mengejar kepentingan egois akan mengakibatkan runtuhnya kepentingan kelompok. Ekuilibrium Nash berarti setiap orang bertindak demi kepentingannya sendiri, yang sejalan dengan kepentingan seluruh kelompok. Ini bukanlah pilihan optimal untuk semua orang secara pribadi, namun optimal untuk semua orang berdasarkan strategi keseluruhan untuk sukses.

Seluruh hidup kita adalah permainan

Pengambilan keputusan di dunia nyata sangat mirip dengan permainan, di mana Anda mengharapkan perilaku rasional tertentu dari peserta lain. Dalam bisnis, di tempat kerja, dalam tim, di perusahaan, dan bahkan dalam hubungan dengan lawan jenis. Dari transaksi besar hingga transaksi biasa situasi kehidupan semuanya mematuhi satu hukum atau lainnya.

Tentu saja dipertimbangkan situasi permainan dengan para penjahat dan bar hanyalah ilustrasi yang bagus untuk menunjukkan keseimbangan Nash. Contoh dilema seperti ini sangat sering muncul di pasar riil, dan hal ini terutama berlaku dalam kasus dimana dua perusahaan monopoli mengendalikan pasar.

Strategi campuran

Seringkali kita terlibat bukan hanya satu, tapi beberapa permainan sekaligus. Memilih salah satu pilihan dalam suatu permainan, berpedoman pada strategi yang rasional, namun berakhir pada permainan yang lain. Setelah beberapa keputusan rasional Anda mungkin merasa tidak puas dengan hasil Anda. Apa yang harus dilakukan?

Mari kita pertimbangkan dua jenis strategi:

• Strategi murni adalah perilaku seorang partisipan yang muncul dari pemikiran tentang kemungkinan perilaku partisipan lainnya.
• Strategi campuran atau strategi acak adalah pergantian strategi murni secara acak atau pemilihan strategi murni dengan probabilitas tertentu. Strategi ini disebut juga acak.

Mengingat perilaku ini yang kita dapatkan Tampilan Baru untuk keseimbangan Nash. Jika sebelumnya dikatakan bahwa pemain memilih strategi satu kali, maka dapat dibayangkan perilaku lain. Dapat diasumsikan bahwa pemain memilih strategi secara acak dengan probabilitas tertentu. Permainan di mana keseimbangan Nash tidak dapat ditemukan dalam strategi murni selalu memiliki strategi campuran.

Ekuilibrium Nash dalam strategi campuran disebut ekuilibrium campuran. Ini adalah keseimbangan di mana setiap peserta memilih frekuensi optimal dalam memilih strateginya, dengan syarat peserta lain memilih strateginya dengan frekuensi tertentu.

Penalti dan strategi campuran

Contoh strategi campuran dapat diberikan dalam permainan sepak bola. Ilustrasi terbaik dari strategi campuran mungkin adalah adu penalti. Jadi, kami punya kiper yang hanya bisa melompat ke satu sudut, dan pemain yang akan mengambil penalti.

Jadi, jika pertama kali pemain memilih strategi melakukan tembakan ke sudut kiri, dan penjaga gawang juga jatuh ke sudut ini dan menangkap bola, lalu bagaimana perkembangan kedua kalinya? Jika seorang pemain melakukan tendangan sudut yang berlawanan, kemungkinan besar hal itu terlalu kentara, tetapi melakukan pukulan sudut yang sama juga tidak kalah kentaranya. Oleh karena itu, baik penjaga gawang maupun penendang tidak punya pilihan selain mengandalkan pilihan acak.

Oleh karena itu, dengan bergantian memilih secara acak dengan strategi murni tertentu, pemain dan penjaga gawang berusaha mendapatkan hasil yang maksimal.

Versi halaman saat ini sejauh ini tidak diperiksa peserta berpengalaman dan mungkin berbeda secara signifikan dari versi, diakses 9 Mei 2012; diperlukan pemeriksaan 2 suntingan.

Pergi ke: navigasi,mencari

John Forbes Nash, November 2006

Keseimbangan Nash(Bahasa inggrisNash keseimbangan) dinamai John Forbes Nash- jadi masuk teori permainan adalah suatu jenis keputusan dalam permainan dua pemain atau lebih dimana tidak ada peserta yang dapat menambah kemenangan dengan mengubah keputusannya secara sepihak, sedangkan peserta lain tidak mengubah keputusannya. Rangkaian strategi yang dipilih oleh para partisipan dan imbalannya disebut ekuilibrium Nash .

Konsep keseimbangan Nash (NE) bukan pertama kali digunakan oleh Nash; Antoine Auguste Courtnot menunjukkan bagaimana menemukan apa yang kita sebut keseimbangan Nash dalam permainan Cournot. Oleh karena itu, beberapa penulis menyebutnya Kesetimbangan Nash-Cournot. Namun, Nash adalah orang pertama yang mengemukakan disertasinya tentang permainan non-kooperatif pada tahun 1950, bahwa keseimbangan seperti itu harus ada untuk semua permainan terbatas dengan jumlah pemain berapa pun. Sebelum Nash, ini hanya terbukti untuk permainan 2 pemain jumlah nolJohn von Neumann Dan Oscar Morgenstern(1947).

Definisi formal

Katakanlah - permainanN orang dalam bentuk normal, yang merupakan serangkaian strategi murni, dan merupakan serangkaian hasil. Ketika setiap pemain memilih strategi di profil strategi , pemain menerima kemenangan. Perhatikan bahwa kemenangan bergantung pada keseluruhan profil strategi: tidak hanya pada strategi yang dipilih oleh pemain itu sendiri, tetapi juga pada strategi orang lain. Profil strategi adalah ekuilibrium Nash jika mengubah strategi tidak bermanfaat bagi pemain mana pun, yaitu bagi siapa pun

Sebuah permainan dapat memiliki keseimbangan Nash dalam strategi murni atau dalam Campuran(yaitu, ketika memilih strategi murni secara stokastik dengan frekuensi tetap). Nash membuktikannya jika kita mengizinkan strategi campuran, lalu di setiap pertandingan N pemain akan memiliki setidaknya satu keseimbangan Nash.

literatur

Vasin A. A., Morozov V. V. Teori permainan dan model ekonomi matematika - M.: Moscow State University, 2005, 272 hal.

Vorobyov N. N. Teori permainan untuk ekonom cybernetic - M.: Nauka, 1985

Mazalov V.V.Teori dan aplikasi permainan matematika - Lan Publishing House, 2010, 446 hal.

Petrosyan L.A., Zenkevich N. A., Shevkoplyas E. V. Teori permainan - St. Petersburg: BHV-Petersburg, 2012, 432 hal.

Efisiensi Pareto

Bahan dari Wikipedia - ensiklopedia gratis

Pergi ke: navigasi,mencari

Optimalitas Pareto- keadaan sistem di mana nilai setiap kriteria tertentu yang menggambarkan keadaan sistem tidak dapat ditingkatkan tanpa memperburuk posisi elemen lainnya.

Jadi, dalam kata-katanya sendiri Pareto: “Setiap perubahan yang tidak menimbulkan kerugian bagi siapa pun dan menguntungkan sebagian orang (menurut penilaian mereka sendiri) adalah suatu perbaikan.” Artinya, hak atas segala perubahan yang tidak menimbulkan kerugian tambahan bagi siapa pun diakui.

Himpunan keadaan optimal Pareto suatu sistem disebut “himpunan Pareto”, “himpunan alternatif optimal Pareto”, atau “himpunan alternatif optimal Pareto”.

Situasi ketika efisiensi Pareto tercapai adalah situasi ketika seluruh manfaat dari pertukaran telah habis.

Efisiensi Pareto adalah salah satu konsep sentral ilmu ekonomi modern. Berdasarkan konsep tersebut maka dibangun Teorema Dasar Pertama dan Kedua kesejahteraan. Salah satu penerapan optimalitas Pareto adalah apa yang disebut. Distribusi sumber daya pareto (tenaga kerja dan modal) selama integrasi ekonomi internasional, yaitu penyatuan ekonomi dua negara atau lebih. Menariknya, distribusi Pareto sebelum dan sesudah integrasi ekonomi internasional dijelaskan secara matematis secara memadai (Dalimov R. T., 2008). Analisis menunjukkan bahwa nilai tambah sektor dan pendapatan sumber daya tenaga kerja bergerak berlawanan arah sesuai dengan persamaan konduktivitas termal yang terkenal, mirip dengan gas atau cairan di luar angkasa, yang memungkinkan penerapan metodologi analisis. digunakan dalam fisika dalam kaitannya dengan masalah ekonomi migrasi parameter ekonomi.

Pareto optimal menyatakan bahwa kesejahteraan masyarakat mencapai maksimum, dan distribusi sumber daya menjadi optimal, jika ada perubahan dalam distribusi ini memperburuk kesejahteraan setidaknya satu orang subjek sistem ekonomi.

Keadaan pasar optimal pareto- situasi di mana tidak mungkin untuk meningkatkan posisi setiap peserta dalam proses ekonomi tanpa secara bersamaan mengurangi kesejahteraan setidaknya salah satu pihak lainnya.

Menurut kriteria Pareto (kriteria pertumbuhan kesejahteraan sosial), pergerakan menuju optimal hanya mungkin terjadi dengan distribusi sumber daya yang meningkatkan kesejahteraan setidaknya satu orang tanpa merugikan orang lain.

Kembali