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.
|
