Statistična analiza uspešnosti reševanja bimatričnih iger s pomočjo Lemke-Howsonovega algoritma

Orehar, Anamari (avtor), Zalar, Aljaž (mentor)

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.

• Jezik: Slovenski jezik
• Ključne besede: teorija iger, Nasheovo ravnovesje, statistična analiza, Lasserejeve hierarhije, bimatrične igre
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2023
• PID: 20.500.12556/RUL-152703
• COBISS.SI-ID: 167956739
• Datum objave v RUL: 04.12.2023

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Statistical analysis of efficiency of solving bimatrix games using LemkeHowson algorithm

Izvleček

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.

• Ključne besede: game theory, Nash equilibrium, statistical analysis, Lasserre hierarchies, bimatrix games