İçeriğe atla
Arama sonuçlarına dön

Nash Dengesi

Ortaya koyan
John Nash
Yıl
1950
Tür
algorithm
Aile
Game-theoretic

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Nash Dengesi, hiçbir oyuncunun kendi çıkarını artırmak için tek taraflı olarak sapma yapamayacağı bir oyun teorisi çözüm kavramıdır. 1950'de John Nash tarafından biçimlendirilen Lemke-Howson algoritması, strateji politoplarındaki tamamen etiketlenmiş köşe çiftlerini tanımlayarak iki matrisli oyunlarda dengeyi hesaplamalı olarak bulur.

Yöntemin mantığı

Bir Nash Dengesi'nde, her oyuncunun stratejisi diğer tüm oyuncuların stratejisine en iyi yanıttır. Her iki oyuncunun da diğerinin stratejisini bildiği bir durumu hayal edin: hiçbiri değişmek istemez çünkü bunu yapmak yalnızca kendilerine zarar verir. Lemke-Howson algoritması, oyun politoplarının geometrisinden yararlanarak, etiketleri (tatmin edilmemiş kısıtlamalar) izler ve tamamen etiketlenmiş bir çift bulunana kadar köşe çiftleri arasında pivotlama yapar; bu, her iki oyuncunun da kârlı sapmalarının olmadığı bir konfigürasyondur.

Tarih

John Nash, 1950 tarihli tezinde her sonlu oyunun en az bir karışık strateji Nash Dengesi'ne sahip olduğunu kanıtladı. 1964'te Lemke ve Howson, Nash'in varlık kanıtını pratik bir hesaplama yöntemine dönüştürerek bu dengeleri bulmak için ilk yapıcı algoritmayı yayınladılar. Çalışmaları, hesaplamalı oyun teorisi ve algoritmik ekonomi için temel oluşturdu.

Ne zaman kullanılır?

İki oyunculu ve ayrık strateji alanlarına sahip oyunları incelerken veya tamamen karışık dengeleri ararken Nash Dengesi analizini kullanın. Stratejik etkileşimin en önemli olduğu rekabet, müzakere ve koordinasyon problemlerini modellemek için uygundur. Lemke-Howson yöntemi, bozulmamış iki matrisli oyunlarda en iyi şekilde çalışır; bozulmuş durumlar sembolik hesaplama veya pertürbasyon gerektirebilir.

Sınırlar ve dikkat edilmesi gerekenler

  • Yalnızca iki oyunculu (iki matrisli) oyunlarla sınırlıdır; n-oyunculu oyunlara genişletme NP-zorudur
  • Birden fazla giriş pivotunun mümkün olduğu bozulmuş oyunlarda başarısız olur veya verimsiz hale gelir
  • Yalnızca bir denge bulabilir; sıfır toplamlı olmayan oyunlarda genellikle birden fazla denge bulunur
  • Doğrudan dinamik veya genişletilmiş form oyunlarını yeniden formüle etmeden işlemez

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Sonlu iki matrisli oyunlarda Nash dengelerini bulmak için hesaplamalı olarak verimlidir
  • Bozulmamış oyunlar için tamamen etiketlenmiş bir köşe çiftine yakınsamayı garanti eder
  • Kombinatoryal geometri ile oyun teorisi arasında teorik bir temel sağlar
  • Karışık strateji dengelerine uygulanabilir, ki bunlar genellikle saf strateji sonuçlarından daha gerçekçidir

Uygulama alanları

  • Ekonomi: piyasalarda oligopolistik rekabeti ve fiyat belirleme davranışını modelleme
  • İhaleler ve mekanizma tasarımı: birinci fiyat ve kapalı zarf ihalelerde teklif stratejilerini analiz etme
  • Siber güvenlik: ağ güvenliği oyunlarında saldırgan-savunucu dengelerini tahmin etme
  • Yaban hayatı biyolojisi: av-avcı etkileşimlerinde evrimsel olarak kararlı stratejileri analiz etme

Nasıl çalışır?

Nasıl çalışır?

1

İki matrisli oyunu, her oyuncu için en iyi yanıt koşullarını temsil eden iki doğrusal tamamlama problemi (LCP) olarak dönüştürün.

2

Oyuncunun teşvik kısıtlamalarının ihlal edildiği durumlara göre strateji politoplarının kenarlarına ve köşelerine etiketler atayın.

3

Tüm-birler köşesinden (tamamen etiketlenmiş) başlayarak, politopta gezinmek için simpleks benzeri pivotlar gerçekleştirin, tamamen etiketlenmiş bir çift keşfedilene kadar etiketleri kaldırıp ekleyin.

4

Diğer oyuncunun stratejisi verildiğinde hiçbirinin çıkarını artıramayacağını kontrol ederek her iki oyuncunun da stratejilerinin karşılıklı en iyi yanıtları oluşturduğunu doğrulayın.

Sık yapılan hatalar

  • Tek bir dengenin var olduğunu varsayar; birçok oyunun farklı çıkar etkileri olan birden fazla Nash dengesi vardır
  • Karışık strateji dengelerini (olasılıksal oyun) saf strateji dengeleriyle karıştırarak ajan davranışlarının yanlış yorumlanmasına yol açar
  • Denge için gerekli ve yeterli koşullar arasındaki ayrımı göz ardı etmek; tamamen etiketlenmiş bir çift optimalliği sağlar ancak oyuncular koordine olamazsa gerçekleştirilemeyebilir

Sık sorulan sorular

Bir oyunun Nash Dengesi olabilir mi?

Saf strateji Nash Dengeleri mevcut olmayabilir (örneğin, Taş-Kağıt-Makas), ancak her sonlu oyun, oyuncuların belirli olasılıklarla eylemler üzerinde rastgeleleştirdiği en az bir karışık strateji dengesine sahiptir.

Karışık strateji dengesi saf strateji dengesinden nasıl farklıdır?

Saf strateji dengesinde, her oyuncu belirli bir eyleme kesin olarak bağlı kalır. Karışık strateji dengesinde, her oyuncu eylemler üzerinde bir olasılık dağılımı kullanır. Karışık dengeler genellikle daha geneldir ve saf olanlar mevcut olmadığında var olur.

Lemke-Howson algoritması neden kaba kuvvet aramasına tercih edilir?

Algoritma, strateji uzaylarının politop yapısından yararlanarak arama alanını üstel olarak azaltır ve bozulmamış oyunlar için polinom zamanda yakınsama sağlar, oysa kaba kuvvet numaralandırması strateji alanı büyüdükçe uygulanamaz hale gelir.

İlgili yöntemler

Kaynaklar

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

    DOI kaynağını aç
    Kopyalandı.
  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.

    DOI kaynağını aç
    Kopyalandı.