20.500.12556/RUL-162012 Igre ustvarjanja omrežja delo diplomskega seminarja Network creation games Osrednja tema diplomske naloge so igre ustvarjanja omrežja, pri katerih so igralci predstavljeni kot vozlišča v grafu, ki želijo glede na pravila igre izboljšati svoj položaj s sebično izbiro strategij. Običajno ima vsak igralec dva sebična cilja. Prvi cilj je minimiziranje stroškov ustvarjanja povezav (omrežja), drugi cilj pa je minimiziranje stroškov uporabe omrežja (razdalje do ostalih vozlišč). Delo se osredotoča na dve osnovni različici problema, kjer igralci ne morejo ustvariti novih povezav in jih tako zanima le strošek uporabe omrežja. V prvi osnovni različici igralci minimizirajo vsoto razdalj do ostalih vozlišč, v drugi osnovni različici pa minimizirajo najdaljšo razdaljo do ostalih vozlišč. V nalogi so predstavljeni nekateri izreki za obravnavane igre, ki nam pomagajo razumeti obnašanje igralcev in ravnovesna stanja. Prav tako se v nalogi spoznamo s pojmoma cena anarhije in cena stabilnosti. Naloga tudi opazuje obnašanje grafov za nekaj različnih algoritmov, ki iščejo ravnovesni graf oziroma simulirajo igro. The central theme of the thesis is network creation games, in which players are represented as nodes in a graph, aiming to improve their positions according to the game’s rules through selfish strategy choices. Typically, each player has two selfish goals. The first goal is to minimize the costs of creating connections (network), and the second goal is to minimize the cost of network usage (distance to other nodes). The work focuses on two basic versions of the problem where players cannot create new connections and are only concerned with the cost of usage. In the first basic version, players minimize the sum of distances to other nodes, while in the second basic version, they minimize the longest distance to other nodes. The thesis presents some theorems for the games under consideration, which help us understand the behavior of players and equilibrium states. We also become familiar with the concepts of the price of anarchy and the price of stability. The thesis also analizes behavior of graphs for several different algorithms that seek an equilibrium graph or simulate the game. igre ustvarjanja omrežja teorija grafov ravnovesje igra vsote razdalj igra najdaljše razdalje cena stabilnosti cena anarhije algoritem network creation games graph theory equilibrium sum of distances game longest distance game price of stability price of anarchy algorithm true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2024-09-18 08:15:46 2024-09-18 08:15:55 2024-09-20 12:54:26 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 143630 208333827 14211.pdf 14211.pdf 1 1A456C90B5D1F7B44AA09451332619A1 88b384a10726a22e946efe95aa4f5a76761c92d8db3374b7baa179da1c2173dd 5b9ec946-7585-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=191026 Fakulteta za matematiko in fiziko 0 0 0