Bimátrix játékok Nash egyensúlypontjának meghatározásáról: könnyen kezelhető speciális esetek

Absztrakt

A bimátrix játékok Nash egyensúlypontjának numerikus meghatározásával foglalkozunk. Ismerve a probléma nehézségét, néhány olyan speciális esetet tekintünk át, amikor a feladat polinomiális időben megoldható. Kijelölünk egy új osztályt, amely szintén polinomiális idejű algoritmushoz vezet. Az osztály definiálásában kulcsszerepe van a "majdnem negatív definit" mátrixoknak. Egy szükséges és egy elégséges feltételt adunk a majdnem negatív definit mátrixok jellemzésére.