Abstract We consider a network pricing game on a parallel network with congestion effects in which link owners set tolls for travel so as to maximize profit. A central authority is able to regulate this competition by means of a (uniform) price cap. The first question we want to answer is how such a cap should be designed in order to minimize the total congestion. We provide an algorithm that finds an optimal price cap for networks with affine latency functions and a full support Wardrop equilibrium. Second, we consider the induced network performance at an optimal price cap. We show that for two link networks with affine latency functions, the congestion costs at the optimal price cap are at most 8 7 times the optimal congestion costs. For more general latency functions, this bound goes up to 2 under the assumption that an uncapped Nash equilibrium exists. However, in general such an equilibrium need not exist and this can be used to show that optimal price caps can induce arbitrarily inefficient flows.
@cite_37: Abstract Motivated by recent progress on pricing in the AI literature, we study marketplaces that contain multiple vendors offering identical or similar products and unit-demand buyers with different valuations on these vendors. The objective of each vendor is to set the price of its product to a fixed value so that its profit is maximized. The profit depends on the vendor's price itself and the total volume of buyers that find the particular price more attractive than the price of the vendor's competitors. We model the behavior of buyers and vendors as a two-stage full-information game and study a series of questions related to the existence, efficiency (price of anarchy) and computational complexity of equilibria in this game. To overcome situations where equilibria do not exist or exist but are highly inefficient, we consider the scenario where some of the vendors are subsidized in order to keep prices low and buyers highly satisfied.
@cite_7: The Internet is composed of multiple economically-independent service providers that sell bandwidth in their networks so as to maximize their own revenue. Users, on the other hand, route their traffic selfishly to maximize their own utility. How does this selfishness impact the efficiency of operation of the network? To answer this question we consider a two-stage network pricing game where service providers first select prices to charge on their links, and users pick paths to route their traffic. We give tight bounds on the price of anarchy of the game with respect to social value--the total value obtained by all the traffic routed. Unlike recent work on network pricing, in our pricing game users do not face congestion costs; instead service providers must ensure that capacity constraints on their links are satisfied. Our model extends the classic Bertrand game in economics to network settings.
@cite_44: As the provision of roads has become market driven, many intriguing issues have emerged, such as the strategic interactions among private firms in determining road supply and pricing in a network and, more importantly, the resulting inefficiencies when competition substitutes for government regulation. This paper studies both toll and capacity competition among private asymmetric roads with congestion in a network with parallel links. We find that oligopolistic competition yields higher tolls but lower construction capacities than the socially optimal levels and, as a result, the level of traffic congestion does not decline. Based on some widely used assumptions, we show that the usage or the congestion level of each road controlled by each private firm, represented by the volume-capacity (v c) ratio, is independent of the other competitors' choices of capacities and tolls in the oligopolistic market. To quantify the inefficiency of the oligopolistic equilibria via higher tolls and less realized traffic demand, we establish the upper bound of the ratio of the social welfare between the competitive equilibrium and the social optimum. The inefficiency bound depends mainly on the marginal benefit of trip-makers and the realized traffic demand at equilibrium on the private roads. Exact bounds are given by considering both the worst and symmetric cases. Naturally, our results show that the distortion disappears when the oligopoly changes to perfect competition.
@cite_24: We briefly summarize our recent work characterizing the efficiency of equilibria in pricing games in two-sided combinatorial markets.
@cite_5: We revisit price of anarchy in network routing, in a new model in which routing decisions are made by self-interested components of the network, as opposed to by the flows as in (12). This significant departure from previous work on the problem seeks to model Internet routing more accurately. We propose two models: the latency model in which the network edges seek to minimize the average latency of the flow through them on the basis of knowledge of latency conditions in the whole network, and the pricing model in which network edges advertise pricing schemes to their neighbors and seek to maximize their profit. We show two rather surprising results: the price of stability in the latency model is unbounded — Ω(n 1 60 ) — even with linear latencies (as compared with 4 in (12) for the case in which routing decisions are made by the flows themselves). However, in the pricing model in which edges advertise pricing schemes — how the price varies as a function of the total amount of flow — we show that, under a condition ruling out monopolistic situations, all Nash equilibria have optimal flows; that is, the price of anarchy in this model is one ,i n the case of linear latencies with no constant term.
@cite_46: We study the efficiency of allocations in large markets with a network structure where every seller owns an edge in a graph and every buyer desires a path connecting some nodes. While it is known that stable allocations in such settings can be very inefficient, the exact properties of equilibria in markets with multiple sellers are not fully understood even in single-source single-sink networks. In this work, we show that for a large class of natural buyer demand functions, we are guaranteed the existence of an equilibrium with several desirable properties. The crucial insight that we gain into the equilibrium structure allows us to obtain tight bounds on efficiency in terms of the various parameters governing the market, especially the number of monopolies M. All of our efficiency results extend to markets without the network structure. While it is known that monopolies can cause large inefficiencies in general, our main results for single-source single-sink networks indicate that for several natural demand functions the efficiency only drops linearly with M. For example, for concave demand we prove that the efficiency loss is at most a factor 1+M 2 from the optimum, for demand with monotone hazard rate it is at most 1+M, and for polynomial demand the efficiency decreases logarithmically with M. In contrast to previous work that showed that monopolies may adversely affect welfare, our main contribution is showing that monopolies may not be as evil' as they are made out to be; the loss in efficiency is bounded in many natural markets. Finally, we consider more general, multiple-source networks and show that in the absence of monopolies, mild assumptions on the network topology guarantee an equilibrium that maximizes social welfare.
The model of @cite_44 studies competition in both tolls and capacities and finds that tolls are higher, but capacities are lower than socially desired. Other recent models of Bertrand competition in a network setting that use different ways of modelling congestion effects are Anshelevich and Sekar @cite_46 , Chawla and Niu @cite_7 , Chawla and Roughgarden @cite_24 , Papadimitriou and Valiant @cite_5 and @cite_37 .