diplomsko delo
Anamari Orehar (Avtor), Aljaž Zalar (Mentor)

Povzetek

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.

Ključne besede

teorija iger;Nasheovo ravnovesje;statistična analiza;Lasserejeve hierarhije;bimatrične igre;visokošolski strokovni študij;diplomske naloge;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL FRI - Fakulteta za računalništvo in informatiko
Založnik: [A. Orehar]
UDK: 004(043.2)
COBISS: 167956739 Povezava se bo odprla v novem oknu
Št. ogledov: 51
Št. prenosov: 18
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Statistical analysis of the efficiency of solving bimatrix games using Lemke-Howson algorithm
Sekundarni povzetek: 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.
Sekundarne ključne besede: game theory;Nash equilibrium;statistical analysis;Lasserre hierarchies;bimatrix games;computer science;diploma;Računalništvo;Univerzitetna in visokošolska dela;
Vrsta dela (COBISS): Diplomsko delo/naloga
Študijski program: 1000470
Konec prepovedi (OpenAIRE): 1970-01-01
Komentar na gradivo: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani: 66 str.
ID: 21439485