Statistična analiza uspešnosti reševanja bimatričnih iger s pomočjo Lemke-Howsonovega algoritmaOrehar, Anamari (Avtor) Zalar, Aljaž (Mentor) teorija igerNasheovo ravnovesjestatistična analizaLasserejeve hierarhijebimatrične igreIskanje Nashevega ravnovesja v bimatričnih igrah je težek problem. Algoritem Lemke--Howson rešuje ta problem z orodji linearnega programiranja, njegova teoretična časovna zahtevnost pa je lahko celo eksponentna. V diplomskem delu predstavimo matematično ozadje Lemke--Howsonovega algoritma in naredimo statistično analizo njegove uspešnosti za reševanje bimatričnih iger različnih velikosti. Analiziramo vplive različnih vhodnih parametrov na čas reševanja. Algoritem primerjamo tudi z novejšimi Lasserejevimi hierarhijami, ki temeljijo na semidefinitnem programiranju. Statistične analize uspešnosti Lemke--Howsonovega algoritma v literaturi nismo našli, tako da je to glavni doprinos tega dela.20232023-12-04 14:58:44Diplomsko delo/naloga152703VisID: 36715COBISS_ID: 167956739sl