In this thesis, we focus on the algorithmic properties of a cellular automaton known as rotor walks. This model has been introduced in two distinct ways. Firstly, as a fundamental operation within another cellular automaton known as Sandpiles, which models the collapse of a sand pile when it becomes too high. Secondly, due to its resemblance to wel...
A Stochastic Game is played by two players, MAX and MIN, by moving a token on a set of states. At each step, both players simultaneously choose an action which moves the token to a new state according to a probability distribution dependent on both actions. In addition, player MIN has to pay to player MAX a value depending on the new state. This co...
Congestion games are a well-studied areaof research, and Network congestion games (NCG) model the problem of congestion in flow networks. The most common problem is to study, broadly speaking, how well or how bad a model of NCG is in terms of total cost for all players when each player plays selfishly. We view network congestion games from a formal...
We consider congestion games on graphs. In nonatomic games, we are given a set of infinitesimal players. Each player wants to go from one vertex to another by taking a route of minimal cost, the cost of a route depending on the number of players using it. In atomic splittable games, we are given a set of players with a non-negligible demand. Each p...
