20.500.12556/RUL-152703 Statistična analiza uspešnosti reševanja bimatričnih iger s pomočjo Lemke-Howsonovega algoritma Statistical analysis of efficiency of solving bimatrix games using LemkeHowson algorithm Iskanje 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. Searching for Nash Equilibrium in bimatrix games is a challenging problem. The Lemke-Howson algorithm addresses this problem using linear programming tools, and its theoretical time complexity can even be exponential. In this thesis, we present the mathematical background of the Lemke-Howson algorithm and conduct a statistical analysis of its performance in solving bimatrix games of various sizes. We analyze the impacts of different input parameters on the solving time. We also compare the algorithm with more recent Lasserre hierarchies based on semidefinite programming. We did not find statistical analyses of the performance of the Lemke-Howson algorithm in the literature, making this the primary contribution of this thesis. teorija iger Nasheovo ravnovesje statistična analiza Lasserejeve hierarhije bimatrične igre game theory Nash equilibrium statistical analysis Lasserre hierarchies bimatrix games true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2023-12-04 14:58:44 2023-12-04 14:58:44 2024-02-02 07:05:20 0000-00-00 00:00:00 2023 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 36715 167956739 Orehar_Anamari_-_Statisticna_analiza_uspesnosti_resevanja_bimatricnih_iger_s_pomocjo_Lemke-Howso.pdf Orehar_Anamari_-_Statisticna_analiza_uspesnosti_resevanja_bimatricnih_iger_s_pomocjo_Lemke-Howso.pdf 1 2496B8A85766164277E229F4E3CF4F07 942044df55c4c91a7fd2385c60c8379ed62653c5b6affe44cdc373bf9f774559 3d62f418-92ad-11ee-9ca9-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=178316 Fakulteta za računalništvo in informatiko 0 0 0