Network Pricing Games


Networks are often used by many different entities that make autonomous decisions about how to use that network. An illustrative example is cars in a traffic network that choose a shortest path from their origin to destination. Numerous of these networks are (partially) owned by firms that set prices for its usage. For example, toll charging on highways is common practice in many different countries in Asia, Europe, and North and South America. In this project we want to analyze the impact of these firms on the users of the network.

The most basic model incorporating these features is the Stackelberg network pricing game. A leader owns a subset of edges of a network and tries to maximize his profit, whereas the follower chooses a shortest path given these prices. Labbé et al. [1] showed that finding optimal prices with lower bounds is NP-hard and gave an example in which profit is maximized by using negative prices. Both results yield interesting research directions.

A more advanced model also takes into account the congestion effects of users. It is well known that the selfish behavior of users in these models yields outcomes that are inefficient. Can this inefficiency be restored if the edges are owned by a monopolist? And what happens if there are several firms competing for users? A good starting point in answering these questions is a paper by Acemoglu and Ozdaglar [2].

    This project is contributed by Marc Schröder.