20.500.12556/RUL-161586 Algoritmi za iskanje Nashevega ravnovesja v bimatričnih igrah Algorithms for finding Nash equilibrium in bimatrix games Iskanje Nashevega ravnovesja v bimatrični igri je problem iskanja strateškega profila igralcev igre, kjer nobeden izmed njih svojega dobička ne more povečati s samostojno spremembo stran od obstoječega strateškega profila. Problem je računsko zahteven in pripada razredu PPAD-polnih problemov. Skozi leta je bila za reševanje problema predlagana vrsta različnih algoritmičnih pristopov. V diplomski nalogi predstavimo matematično ozadje treh najvidnejših algoritmov iz literature in jih implementiramo v programskem jeziku Julia. Uspešnost njihovega reševanja primerjamo na bimatričnih igrah različnih velikosti in dveh različnih tipov. V nalogi izpostavimo vprašanje numerične stabilnosti algoritma Lemke-Howson, ki je v literaturi pomanjkljivo predstavljeno. Finding Nash equilibrium in a bimatrix game is the problem of finding a strategy profile for the players of the game, where none of them can improve their payoffs by individually deviating from the existing strategy profile. The problem is computationally demanding and belongs to the class of PPAD complete problems. Through the years different algorithmic approaches were proposed for solving the problem. We present the mathematical background of three visible algorithms from the literature and implement them in Julia programming language. We evaluate their performance on bimatrix games of different sizes and two different types. We put forth the question of numerical stability in the case of Lemke-Howson algorithm, which we feel is not sufficiently described in the literature. Nashevo ravnovesja bimatrična igra teorija iger dominirana strategija celoštevilsko programiranje Nash equilibrium bimatrix game game theory dominated strategy integer programming true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2024-09-12 12:40:24 2024-09-12 12:40:28 2024-10-25 11:33:55 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 37452 212962307 Leonardis_Tomaz_jonatan_-_Algoritmi_za_iskanje_Nashevega_ravnovesja_v_bimatricnih_igrah.pdf Leonardis_Tomaz_jonatan_-_Algoritmi_za_iskanje_Nashevega_ravnovesja_v_bimatricnih_igrah.pdf 1 014143F9295F49153A32ABAE6A62AD49 53f9210406c6077bed8f6537cdb684f541c2b53e44fbe9dc20f466d5d3af5150 5f2494e6-70f3-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=190545 Fakulteta za računalništvo in informatiko 0 0 0