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

Orehar, Anamari (author), 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.

• Language: Slovenian
• Keywords: teorija iger, Nasheovo ravnovesje, statistična analiza, Lasserejeve hierarhije, bimatrične igre
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2023
• PID: 20.500.12556/RUL-152703
• COBISS.SI-ID: 167956739
• Publication date in RUL: 04.12.2023

Secondary language

• Language: English
• Title: Statistical analysis of efficiency of solving bimatrix games using LemkeHowson algorithm

Abstract

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.

• Keywords: game theory, Nash equilibrium, statistical analysis, Lasserre hierarchies, bimatrix games