We study a two-sided network investment game consisting of two sets of players, called providers and users. The game is set in two stages. In the first stage, providers aim to maximize their profit by investing in bandwidth of cloud computing services. The investments of the providers yield a set of usable services for the users. In the second stage, each user wants to process a task and therefore selects a bundle of services so as to minimize the total processing time. We assume the total processing time to be separable over the chosen services and the processing time of each service to depend on the utilization of the service and the installed bandwidth. We provide insights on how competition between providers affects the total costs of the users and show that every game on a series-parallel graph can be reduced to an equivalent single edge game when analyzing the set of subgame perfect Nash equilibria.
A slightly different, but closely related model is the game analyzed by @cite_31 . Here each edge in a series-parallel network represents a producer that competes by selecting a markup that then determines a price function. The main difference to our work is that producers are identified by an edge and thus do not have the possibility to compete on other edges.
@cite_31
172279872
Let a communication network be modelled by a directed graphG = (V,E) of n nodes and m edges. We consider aone-round two-player network pricing game, the Stackelberg ShortestPaths Tree (StackSPT) game. This is played on G, by assuming thatedges in E are partitioned into two sets: a set E F of edges with afixed positive real weight, and a set E P of edges that should bepriced by one of the two players (the leader). Given adistinguished node r ∈ V, the StackSPT game isthen as follows: the leader prices the edges in E P in such a waythat he will maximize his revenue, knowing that the other player(the follower) will build a shortest paths tree of G rooted at r,say S(r), by running a publicly available algorithm. Quitenaturally, for each edge selected in the solution, theleader’s revenue is assumed to be equal to the loaded priceof an edge, namely the product of the edge price times the numberof paths from r in S(r) that use it. First, we show that theproblem of maximizing the leader’s revenue is NP-hard as soonas |E P | = Θ(n). Then, in search of aneffective method for solving the problem when the size of E P isconstant, we focus on the basic case in which |E P| = 2, and we provide an efficient O(n 2 logn) timealgorithm. Afterwards, we generalize the approach to the case |E P| = k, and we show that it can be solved inpolynomial time whenever k = O(1).