Bimatricu spēļu Neša līdzsvara atrašana. Lemke-Howson algoritms

Abstract

Spēle ir situācija, kurā piedalās divi vai vairāki dalībnieki un katrs dalībnieks pieņem lēmumu par savas stratēģijas izvēli. Līdzīgas situācijas bieži sastopas dažādās nozarēs, to attēlošanai un analīzei izmanto spēļu teoriju. Darbā ir apskatīts Lemke-Howson algoritms. Darbā ir aprakstītas bimatricu spēles, nekooperatīvu spēļu piemēri, lineārais uzdevums par papildu vērtību, Lemke-Howson algoritms. Darbs ilustrēts ar diviem piemēriem, kas parāda, kā lietojams Lemke-Howson algoritms praktiski. Darba galvenais secinājums – ar Lemke-Howson algoritmu tiek atrasts viens Neša līdzsvars, taču var būt uzdevumi, kuros ir vairāki līdzsvari.

A game is a situation in which participate two or more participants and each participant decides which strategy he will choice for game. Similar situations often encountered in various sectors and to display and analyse them we can use games theory. The work introduces the Lemke-Howson algorithm. The work described bimatric games, non-cooperative game examples, the linear task for added value, the Lemkes-Howson algorithm. In the work are illustrated two examples showing how to use Lemke-Howson algorithm in practice. The main conclusion of the work is that with Lemke-Howson algorithm we found one of the Nash equilibrium, but there may be tasks with several balances.