Igre ustvarjanja omrežja : delo diplomskega seminarja

Milivojević, Peter (avtor), Cabello Justo, Sergio (mentor)

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.

• Jezik: Slovenski jezik
• Ključne besede: igre ustvarjanja omrežja, teorija grafov, ravnovesje, igra vsote razdalj, igra najdaljše razdalje, cena stabilnosti, cena anarhije, algoritem
• Vrsta gradiva: Delo diplomskega seminarja/zaključno seminarsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2024
• PID: 20.500.12556/RUL-162012
• UDK: 519.17
• COBISS.SI-ID: 208333827
• Datum objave v RUL: 18.09.2024

MILIVOJEVIĆ, Peter, 2024, Igre ustvarjanja omrežja : delo diplomskega seminarja [na spletu]. Diplomsko delo. [Dostopano 4 maj 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=162012

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Network creation games

Izvleček

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.

• Ključne besede: network creation games, graph theory, equilibrium, sum of distances game, longest distance game, price of stability, price of anarchy, algorithm