Path player games. Analysis and applications (Q933614)

This book introduces a new class of network games, called path player games. These games provide a new approach for modeling routing problems on networks from the point of view of the network operators. Each player is assumed to own one path (that is, a sequence of edges) in the network and offers an amount of flow that he allows to be routed along his path. Applications of these games occur in public transportation, telecommunication networks and information networks. The book consists of five chapters, the first of which provides a brief introduction. Chapter 2 introduces the notion of path player game and studies the equilibria of such games. It is also shown that path player games are exact potential games, that is, games for which an exact potential function exists. Chapter 3 extends the results of the previous chapter to a more general setting, namely to games on polyhedra. These games are an instance of generalized games, that is, games where the strategy set of a player depends on the strategies chosen by the other players. Generalized Nash equilibria are studied and a special class of polyhedral games is discussed where the set of equilibria corresponds to the set of optimal solutions of a linear program. Chapter 4 is devoted to an application of the results obtained for path player games and games on polyhedra to the line planning problem, where lines have to be chosen from a given line pool and frequencies have to be determined in such a way as to satisfy the customers' demand. It is shown that line planning games are a generalization of path player games and a special case of games on polyhedral. A numerical example based on the German railway system is presented in detail. Chapter 5 offers a brief summary.