
Research
Abstracts  2007 
Network Pricing via Stackelberg GamesErik Demaine & Oren WeimannStackelberg Games:A Stackelberg game is a oneround game introduced by the German economist Heinrich Freiherr von Stackelberg [6]. There are two players in the game: the leader moves first, then the follower moves, and then the game is over. The follower optimizes its own objective function, knowing the leader's move. The leader, sometimes referred to as the market leader, has to optimize its own objective function by anticipating the optimal response of the follower. Companies may engage in Stackelberg competition if one has some sort of advantage enabling it to move first. Moving observably first is the most obvious means of commitment: once the leader has made its move, it is committed to that action. Network Pricing:Suppose that you work for a networking company that owns many pointtopoint connections between several locations, and your job is to sell these connections. A customer wants to construct a network connecting some locations (or all of them). The customer can buy connections that you are selling, but can also buy connections offered by your competitors. The customer will always buy the cheapest possible connections. Your company has researched the price of each connection offered by the competitors. Your goal is to set the price of each of your connections in order to maximize your revenue, that is, the sum of the prices of the connections that the customer buys from you. Network pricing can be cast as a Stackelberg game. The game is played on a graph (representing the network), whose edges are colored either red or blue. The blue edges represent your connections, and the red edges have a given fixed cost and represent the competitor's prices. You, as the leader, choose an assignment of prices to the blue edges, and the follower (the customer) then buys the cheapest set of edges that connect his locations, using any combination of red and blue edges. Your goal is to maximize the total price of purchased blue edges. There is an obvious tradeoff: not to put too a high price on the connections—otherwise the customer will not buy them—but on the other hand put sufficiently high prices to optimize revenue. The case where the customer wants to connect only two locations has been studied in the literature; see van Hoesel [5] for a survey. Complexity and approximability results have recently been obtained in [4,2]: the problem is strongly NPhard and O(log b)approximable where b is the number of blue edges. A generalization of the problem to more than one customer has been tackled using mathematical programming tools, in particular bilevel programming [3]. This generalization was motivated by the problem of setting tolls on highway networks. A geometric version of the problem was introduced in [1]. Progress:So far we have been focusing on the case where the customer wishes to connect the entire network in the form of a minimum spanning tree. We have shown that the problem is APXhard even if there are only two different red costs, and devised an approximation algorithm whose approximation ratio is at most min{k, 3 + 2 ln b, 1 + ln W}, where k is the number of distinct red costs, b is the number of blue edges, and W is the maximum ratio between red costs. We also have a natural integer linear programming formulation of the problem, where the integrality gap of the fractional relaxation asymptotically matches one of the approximation guarantees of our algorithm. Future Work:Does the minimum spanning tree version of the problem have a constantfactor approximation algorithm? We believe that a superconstant lower bound can be shown. References:[1] J. Cardinal, M. Labbé, S. Langerman, and B. Palop. "Pricing of geometric transportation networks". In Proc. Canadian Conference on Computational Geometry (CCCG), pages 92–96, 2005. [2] A. Grigoriev, S. van Hoesel, A. van der Kraaij, M. Uetz, and M. Bouhtou. "pricing network edges to cross a river". In Proc. Workshop on Approximation and Online Algorithms (WAOA), number 3351 in Lecture Notes in Computer Science, pages 140–153, 2005. [3] M. Labbé, P. Marcotte, and G. Savard. "A bilevel model of taxation and its application to optimal highway pricing". Management Science, 44(12):1608–1622, 1998. [4] S. Roch, G. Savard, and P. Marcotte. "An approximation algorithm for Stackelberg network pricing". Networks, 46(1):57–67, 2005. [5] S. van Hoesel. "An overview of Stackelberg pricing in networks". Research Memoranda 042, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization, 2006. [6] H. von Stackelberg. "Marktform und Gleichgewicht (Market and Equilibrium)". Verlag von Julius Springer, Vienna, 1934. 

