diplomsko delo
Veljko Dudić (Author), Aljaž Zalar (Mentor)

Abstract

Iskanje globalnega minimuma matematičnih funkcij je zelo težek problem, za katerega ne obstaja algoritem polinomske časovne zahtevnosti. Z uporabo Lasserrejevih hierarhij lahko globalni minimum iščemo na učinkovit način, pri čemer pa nimamo zagotovila, da ga bomo res našli v okviru računskih zmožnosti današnje programske opreme. V tem diplomskem delu te hierarhije uporabimo na področju teorije iger za dva igralca in iščemo optimalne stra- tegije obeh igralcev. Statistično analiziramo časovno zahtevnost posameznih nivojev hierarhij in poiščemo mejo uporabnosti hierarhij na tem področju.

Keywords

Nasheovo ravnovesje;globalni minimum;Lasserrejeva hierarhija;momentni problem;visokošolski strokovni študij;diplomske naloge;

Data

Language: Slovenian
Year of publishing:
Typology: 2.11 - Undergraduate Thesis
Organization: UL FRI - Faculty of Computer and Information Science
Publisher: [V. Dudić]
UDC: 519.83(043.2)
COBISS: 135371011 Link will open in a new window
Views: 16
Downloads: 8
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Usage of Lasserre hierarchies in game theory
Secondary abstract: Finding the global minimum of mathematical functions is a very difficult problem, for which there is no algorithm of polynomial time complexity. By using Lasserre hierarchies, we can search for the global minimum in an effi- cient way, but we have no guarantee that we will actually find it within the computational capabilities of today’s software. In this thesis we apply these hierarchies to the field of game theory for two players and search for the opti- mal strategies of both players. We statistically analyze the time complexity of individual levels of hierarchies and find boundary uses of hierarchies in this area.
Secondary keywords: game theory;Nash equilibrium;global minimum;Lasserre hierarchy;moment problem;computer science;computer and information science;diploma;Teorija iger;Matematika;Računalništvo;Univerzitetna in visokošolska dela;
Type (COBISS): Bachelor thesis/paper
Study programme: 1000470
Embargo end date (OpenAIRE): 1970-01-01
Thesis comment: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages: 51 str.
ID: 17509546