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