Skip to content
Kembali ke hasil pencarian

Ekuilibrium Nash

Diperkenalkan oleh
John Nash
Tahun
1950
Jenis
algorithm
Keluarga
Game-theoretic

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Ekuilibrium Nash adalah konsep solusi teori permainan di mana tidak ada pemain yang dapat menyimpang secara sepihak untuk meningkatkan keuntungan mereka.

Diformalisasi oleh John Nash pada tahun 1950, algoritma Lemke-Howson secara komputasi menemukan ekuilibria dalam permainan bimatriks dengan mengidentifikasi pasangan simpul berlabel lengkap dalam politop strategi.

Intuisi di balik metode

Dalam Ekuilibrium Nash, strategi setiap pemain adalah respons terbaik terhadap strategi setiap pemain lainnya. Bayangkan situasi di mana kedua pemain mengetahui strategi pemain lain: tidak ada yang ingin berubah karena melakukannya hanya akan merugikan mereka. Algoritma Lemke-Howson mengeksploitasi geometri polihedra permainan, melacak label (kendala yang tidak terpenuhi) dan melakukan pivot melalui simpul hingga pasangan berlabel lengkap ditemukan—sebuah konfigurasi di mana kedua pemain tidak memiliki penyimpangan yang menguntungkan.

Sejarah

John Nash membuktikan dalam disertasinya tahun 1950 bahwa setiap permainan terbatas memiliki setidaknya satu Ekuilibrium Nash strategi campuran. Pada tahun 1964, Lemke dan Howson menerbitkan algoritma konstruktif pertama untuk menemukan ekuilibria ini, mengubah bukti keberadaan Nash menjadi metode komputasi praktis. Karya mereka menjadi dasar bagi teori permainan komputasi dan ekonomi algoritmik.

Kapan digunakan

Gunakan analisis Ekuilibrium Nash saat mempelajari permainan dengan dua pemain dan ruang strategi diskrit, atau saat mencari ekuilibria campuran penuh. Cocok untuk memodelkan masalah persaingan, negosiasi, dan koordinasi di mana interaksi strategis sangat penting. Metode Lemke-Howson bekerja paling baik untuk permainan bimatriks non-degeneratif; kasus degeneratif mungkin memerlukan komputasi simbolik atau perturbasi.

Batasan dan pertimbangan

  • Terbatas pada permainan bimatriks (dua pemain); perluasan ke permainan n-pemain adalah NP-hard
  • Gagal atau menjadi tidak efisien pada permainan degeneratif di mana beberapa pivot masuk dimungkinkan
  • Mungkin hanya menemukan satu ekuilibrium; banyak ekuilibrium sering ada dalam permainan non-zero-sum
  • Tidak secara langsung menangani permainan dinamis atau bentuk ekstensif tanpa reformulasi

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Secara komputasi efisien untuk menemukan ekuilibria Nash dalam permainan bimatriks terbatas
  • Menjamin konvergensi ke pasangan simpul berlabel lengkap untuk permainan non-degeneratif
  • Memberikan dasar teoretis yang menghubungkan geometri kombinatorial dengan teori permainan
  • Dapat diterapkan pada ekuilibria strategi campuran, yang seringkali lebih realistis daripada hasil strategi murni

Penerapan

  • Ekonomi: memodelkan persaingan oligopolistik dan perilaku penetapan harga di pasar
  • Lelang dan desain mekanisme: menganalisis strategi penawaran dalam lelang harga pertama dan tertutup
  • Keamanan siber: memprediksi ekuilibria penyerang-bertahan dalam permainan keamanan jaringan
  • Biologi satwa liar: menganalisis strategi stabil secara evolusioner dalam interaksi predator-mangsa

Cara kerjanya

Cara kerjanya

1

Mengubah permainan bimatriks menjadi dua masalah komplementaritas linear (LCP), satu untuk setiap pemain, yang mewakili kondisi respons terbaik mereka.

2

Menetapkan label pada tepi dan simpul politop strategi berdasarkan kendala insentif pemain mana yang dilanggar.

3

Dimulai dari simpul semua-satu (berlabel lengkap), lakukan pivot mirip simpleks untuk menavigasi politop, menghapus dan menambahkan label hingga pasangan berlabel lengkap ditemukan.

4

Memastikan bahwa strategi kedua pemain membentuk respons terbaik bersama dengan memeriksa bahwa tidak ada yang dapat meningkatkan keuntungan mereka mengingat strategi pemain lain.

Kesalahan umum

  • Mengasumsikan ekuilibrium unik ada; banyak permainan memiliki banyak ekuilibrium Nash dengan implikasi keuntungan yang berbeda
  • Mencampuradukkan ekuilibrium strategi campuran (permainan probabilistik) dengan ekuilibrium strategi murni, yang mengarah pada kesalahpahaman perilaku agen
  • Mengabaikan perbedaan antara kondisi yang diperlukan dan cukup untuk ekuilibrium; pasangan berlabel lengkap memenuhi optimalitas tetapi mungkin tidak terwujud jika pemain tidak dapat berkoordinasi

Pertanyaan yang sering diajukan

Bisakah sebuah permainan tidak memiliki Ekuilibrium Nash?

Ekuilibrium Nash strategi murni mungkin tidak ada (misalnya, Batu-Gunting-Kertas), tetapi setiap permainan terbatas memiliki setidaknya satu ekuilibrium strategi campuran di mana pemain melakukan pengacakan atas tindakan dengan probabilitas tertentu.

Bagaimana ekuilibrium strategi campuran berbeda dari ekuilibrium strategi murni?

Dalam ekuilibrium strategi murni, setiap pemain berkomitmen pada tindakan tertentu dengan kepastian. Dalam ekuilibrium strategi campuran, setiap pemain menggunakan distribusi probabilitas atas tindakan. Ekuilibrium campuran seringkali lebih umum dan ada ketika yang murni tidak ada.

Mengapa algoritma Lemke-Howson lebih disukai daripada pencarian brute-force?

Algoritma ini mengeksploitasi struktur politop ruang strategi, mengurangi ruang pencarian secara eksponensial dan mencapai konvergensi dalam waktu polinomial untuk permainan non-degeneratif, sedangkan enumerasi brute-force menjadi tidak layak seiring bertambahnya ruang strategi.

Metode terkait

Sumber

  1. Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.

    Buka referensi DOI
    Disalin.
  2. Lemke, C. E., & Howson Jr, J. T. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413-423.

    Buka referensi DOI
    Disalin.