Pricing Games in Heterogeneous Parallel Networks

In this masters thesis we study a 2­level game where, on an n­link network from a source s to a target t, a unit of flow wants to move from s to t using the link with the lowest cost, while the link operators compete for profit by assigning tolls to links and thus creating a toll congestion game. We examine only affine latencies for the links. In addition, each flow user responds to tolls in a heterogeneous way, i.e. each player p in the flow has a different time­money sensitivity value, which is described by a distribution function α(p). We first present some definitions and properties of pricing homogeneous games, heavily based on previous work, and using them as base, we extend them to describe pricing games with heterogeneous users. We introduce a new term, the sensitivity split function αs(t), defined for any 2 links of the network as the time­money sensitivity value for which, given a set of tolls t, the link costs are equal. With the help of αs we describe some properties around the selfish behaviour of heterogeneous users for different tolls, as well as prove the existence of bounds for the sensitivity values that are relevant to the game. Then, arriving at the main body of this study, we investigate the existence of a Nash Equilibrium in the profit game between the link operators for different cases of heterogeneous users. We show there is no Nash Equilibrium when there are many users with 0 sensitivity, i.e. players not affected by tolls, forcing us to assume onward α(p) > 0. We then investigate cases of fixed distribution functions, where the user behaviour remains homogeneous (making them pseudo­heterogeneous games), through which we then describe how flow, tolls and equilibria behave as that fixed value changes. Using all the above, we study step distribution functions, where, by limiting our scope to 2 links, we prove a strong requirement for the value of a potential Nash Equilibrium in the profit game between the link operators, connecting it to the equilibrium of an equivalent pseudo­heterogeneous game. We finally present and analyse an algorithm that calculates that equilibrium, if it exists, in time linear with regard to the step function's cardinality, and we finish with some discussion about potential future work.