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.
@cite_22: 
@cite_8: We study a multi-player one-round game termed Stackelberg Network Pricing Game, in which a leader can set prices for a subset of m priceable edges in a graph. The other edges have a fixed cost. Based on the leader’s decision one or more followers optimize a polynomial-time solvable combinatorial minimization problem and choose a minimum cost solution satisfying their requirements based on the fixed costs and the leader’s prices. The leader receives as revenue the total amount of prices paid by the followers for priceable edges in their solutions. Our model extends several known pricing problems, including single-minded and unit-demand pricing, as well as Stackelberg pricing for certain follower problems like shortest path or minimum spanning tree. Our first main result is a tight analysis of a single-price algorithm for the single follower game, which provides a (1+e)log m-approximation. This can be extended to provide a (1+e)(log k+log m)-approximation for the general problem and k followers. The problem is also shown to be hard to approximate within @math for some e>0. If followers have demands, the single-price algorithm provides an @math -approximation, and the problem is hard to approximate within @math for some e>0. Our second main result is a polynomial time algorithm for revenue maximization in the special case of Stackelberg bipartite vertex-cover, which is based on non-trivial max-flow and LP-duality techniques. This approach can be extended to provide constant-factor approximations for any constant number of followers.
@cite_32: We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are colored either red or blue, and where the red edges have a given fixed cost (representing the competitor’s prices). The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest possible minimum spanning tree, using any combination of red and blue edges. The goal of the first player is to maximize the total price of purchased blue edges. This game is the minimum spanning tree analog of the well-studied Stackelberg shortest-path game. We analyze the complexity and approximability of the first player’s best strategy in StackMST. In particular, we prove that the problem is APX-hard even if there are only two different red costs, and give an approximation algorithm whose approximation ratio is at most min k,1+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 give a natural integer linear programming formulation of the problem, and show that the integrality gap of the fractional relaxation asymptotically matches the approximation guarantee of our algorithm.
@cite_15: We consider the problem of pricing n items to maximize revenue when faced with a series of unknown buyers with complex preferences, and show that a simple pricing scheme achieves surprisingly strong guarantees. We show that in the unlimited supply setting, a random single price achieves expected revenue within a logarithmic factor of the total social welfare for customers with general valuation functions, which may not even necessarily be monotone. This generalizes work of Guruswami et. al [18], who show a logarithmic factor for only the special cases of single-minded and unit-demand customers. In the limited supply setting, we show that for subadditive valuations, a random single price achieves revenue within a factor of 2O(√(log n loglog n) of the total social welfare, i.e., the optimal revenue the seller could hope to extract even if the seller could price each bundle differently for every buyer. This is the best approximation known for any item pricing scheme for subadditive (or even submodular) valuations, even using multiple prices. We complement this result with a lower bound showing a sequence of subadditive (in fact, XOS) buyers for which any single price has approximation ratio 2Ω(log1 4 n), thus showing that single price schemes cannot achieve a polylogarithmic ratio. This lower bound demonstrates a clear distinction between revenue maximization and social welfare maximization in this setting, for which [12,10] show that a fixed price achieves a logarithmic approximation in the case of XOS [12], and more generally subadditive [10], customers. We also consider the multi-unit case examined by [1111] in the context of social welfare, and show that so long as no buyer requires more than a 1 -- e fraction of the items, a random single price now does in fact achieve revenue within an O(log n) factor of the maximum social welfare.
@cite_34: We consider a bilevel model where the leader wants to maximize revenues from a taxation scheme, while the follower rationally reacts to those tax levels. We focus our attention on the special case of a toll-setting problem defined on a multicommodity transportation network. We show that the general problem is NP-complete, while particular instances are polynomially solvable. Numerical examples are given.
@cite_10: 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).
@cite_20: 
@cite_11: 
Leader-follower models as the previous ones are also known as Stackelberg games @cite_20 . Recently, lots of attention has been placed on Stackelberg pricing games. Starting with Labb ' e et al @cite_34 , who considered the problem in which a leader sets prices on a subset of edges and the follower chooses a shortest path, several authors generalized to different combinatorial problems for the follower. For example, @cite_32 studied the Stackelberg minimum spanning tree problem, and Bil o el al. @cite_10 and later Cabello @cite_11 investigated the Stackelberg shortest path tree problem. @cite_15 and @cite_8 considered the power of single-price strategies. B " o @cite_22 extended the analysis of this simple algorithm beyond the combinatorial setting.