# Learning to Play Network Games

## Amy Greenwald

### Abstract

The idea of learning to play equilibrium strategies in repeated games
is an active area of research in the game-theoretic community. Game
theorists are primarily concerned with the outcome of learning
algorithms in the limit: i.e., over an infinite amount of time. One of
the goals of this research is to apply computer science ideology to
learning theory. In particular, this thesis will consider imposing
restrictions on traditional learning algorithms such that players
learn to play approximations to equilibrium strategies in bounded
amounts of time. The idea of such bounded learning algorithms is to
quickly learn to exploit the obvious, while ignoring any subtleties.
Bounded learning is applicable to network games, in which players
learn to utilize networks during times of minimal congestion. These
games are atypical as compared with traditional games described in the
game-theoretic literature, since their underlying structure is not
commonly understood by the players, and moreover, common knowledge of
rationality is not a valid assumption. As such, this class of
repeated games does not naturally lend itself to belief-based learning
algorithms. Rather, this thesis will investigate learning algorithms
for network games that are analyzed solely on the basis of
performance, without requiring that players maintain prior beliefs
about expected network congestion. In sum, the initial focus of this
thesis is to explore an application of computer science ideology to
learning algorithms in game theory; secondly, bounded game-theoretic
learning will be applied to routing and congestion problems in network
environments.