Games in Networks under Robustness, Locality, and Coloring Aspects
Decentralization is a key concept in modern networks, such as the Internet, social networks, or wireless phone or sensor networks. The systematic study of how networks are formed by a multitude of non-cooperative or only mildly cooperative players, is a vivid topic in Discrete Mathe- matics, Computer Science, and Economics. In 2010, a variant addressing robustness aspects was introduced. In this model, known as adversary model or destruction model, one link in the network is destroyed at random af- ter the network has been formed. Players anticipate this disruption and try to build a network that gives them good connectivity even after the destruction. How efficiently can this be done in a decentralized setting? This thesis advances our knowledge regarding the adversary model: we bring in the modern equilibrium concept of swap equilibrium and we extend to the destruction of one vertex. This disruption tends to be more severe compared to the case that just one link is destroyed. We characterize several settings, where for some, the formed networks are provably efficient, while for others, we show they can be inefficient up to a certain degree. Apart from the adversary model, we study a model where each player v tries to maximize the number of players at distance at most k from v, for a fixed parameter k. For example, when the network models friendship, then for k = 2, players would try to maximize the number of friends plus friends of their friends, which is an interesting metric in Sociology. We prove results on the structure and efficiency of such networks. In the final chapter, the network is fixed and each player chooses one of k colors. For example, the network might describe the spatial relations between the players and colors might correspond to radio frequencies, so each player’s aim is to choose a frequency that causes as few interference as possible with the frequencies of her neighbors.