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.
One way to restore efficiency is by means of centralized pricing. @cite_3 and Dafermos and Sparrow @cite_16 showed that marginal cost pricing induces an equilibrium flow that is optimal. Despite the effectiveness of marginal cost tolls, there are two drawbacks. First, potentially each edge in the network is tolled; an issue that is considered by @cite_26 and @cite_12 . Second, the imposed tolls can be arbitrary large; an issue that is considered by @cite_32 , @cite_0 , @cite_22 and Kleer and Sch " a fer @cite_45 . @cite_40 show that optimal tolls also exist when users are heterogeneous with respect to the tradeoff between time and money. Later this result was extended to general networks by @cite_34 , Karakostas and Kolliopoulos @cite_19 and Yang and Huang @cite_4 .
@cite_26 @cite_4 @cite_22 @cite_32 @cite_3 @cite_34 @cite_0 @cite_19 @cite_40 @cite_45 @cite_16 @cite_12
2064824188 2039786295 2123733911 2110155180
The notions of user equilibrium (UE) and system optimum (SO) often allude to the literature together with the well-known principle of marginal-cost pricing in traffic network analyses. This pricing principle states that the UE flow pattern on a network can be driven to an SO in the sense of total travel cost minimization by charging a toll on each link equal to the difference between marginal social cost and marginal private cost. In reality, users do not always behave in a UE manner, typically when there exist oligopoly Cournot-Nash (CN) firms. Users in a CN firm cooperate among themselves to minimize total cost of the firm and compete against others. In the presence of such UE-CN mixed equilibrium behaviors, we are interested in whether an SO flow pattern remains attainable by meaningful link tolls. In this paper we show that in a network with both UE and CN users, applying the traditional marginal-cost pricing for a system optimum requires that link tolls be differentiated across user classes. Because users differ from one another in an unobservable way, it is impossible to introduce discriminatory tolling on a network in a mixed behaviour equilibrium. We then seek alternative meaningful tolls by establishing the existence of nonnegative anonymous link tolls to decentralize the SO into a UE-CN mixed behavior equilibrium with resort to a rigorous mathematical programming approach. A natural generalization of the selfish routing setting arises when some of the users obey a central coordinating authority, while the rest act selfishly. Such behavior can be modeled by dividing the users into an α fraction that are routed according to the central coordinator’s routing strategy (Stackelberg strategy), and the remaining 1−α that determine their strategy selfishly, given the routing of the coordinated users. One seeks to quantify the resulting price of anarchy, i.e., the ratio of the cost of the worst traffic equilibrium to the system optimum, as a function of α. It is well-known that for α=0 and linear latency functions the price of anarchy is at most 4 3 (J. ACM 49, 236–259, 2002). If α tends to 1, the price of anarchy should also tend to 1 for any reasonable algorithm used by the coordinator. We analyze two such algorithms for Stackelberg routing, LLF and SCALE. For general topology networks, multicommodity users, and linear latency functions, we show a price of anarchy bound for SCALE which decreases from 4 3 to 1 as α increases from 0 to 1, and depends only on α. Up to this work, such a tradeoff was known only for the case of two nodes connected with parallel links (SIAM J. Comput. 33, 332–350, 2004), while for general networks it was not clear whether such a result could be achieved, even in the single-commodity case. We show a weaker bound for LLF and also some extensions to general latency functions. The existence of a central coordinator is a rather strong requirement for a network. We show that we can do away with such a coordinator, as long as we are allowed to impose taxes (tolls) on the edges in order to steer the selfish users towards an improved system cost. As long as there is at least a fraction α of users that pay their taxes, we show the existence of taxes that lead to the simulation of SCALE by the tax-payers. The extension of the results mentioned above quantifies the improvement on the system cost as the number of tax-evaders decreases. We prove the existence of tolls to induce multicommodity, heterogeneous network users that independently choose routes minimizing their own linear function of tolls versus latency to collectively form the traffic pattern of a minimum average latency flow. This generalizes both the previous known results of the existence of tolls for multicommodity, homogeneous users (, 1956) and for single commodity, heterogeneous users (, 2003). Unlike previous proofs for single commodity users in general graphs, our proof is constructive - it does not rely on a fixed point theorem - and results in a simple polynomial-sized linear program to compute tolls when the number of different types of users is bounded by a polynomial. We show that our proof gives a complete characterization of flows that are enforceable by tolls. In particular, tolls exist to induce any traffic pattern that is the result of minimizing an arbitrary function from R sup E(G) to the reals that is nondecreasing in each of its arguments. Thus, tolls exist to induce flows with minimum average weighted latency, minimum maximum latency, and other natural objectives. We give an exponential bound on tolls that is independent of the number of network users and the number of commodities. We use this to show that multicommodity tolls also exist when users are not from discrete classes, but instead define a general function that trades off latency versus toll preference. Finally, we show that our result extends to very general frameworks. In particular, we show that tolls exist to induce the Nash equilibrium of general nonatomic congestion games to be system optimal. In particular, tolls exist even when 1) latencies depend on user type; 2) latency functions are nonseparable functions of traffic on edges; 3) the latency of a set S is an arbitrary function of the latencies of the resources contained in S. Our exponential bound on size of tolls also holds in this case; and we give an example of a congestion game that shows this is tight; it requires tolls that are exponential in the size of the game. We study the efficiency implications of competition among profit-maximizing service providers in communication networks. Service providers set prices for transmission of flows through their (sub)network. The central question is whether the presence of prices will help or hinder network performance. We investigate this question by considering the difference between users' willingness to pay and delay costs as the efficiency metric. Previous work has demonstrated that in networks consisting of parallel links, efficiency losses from competition are bounded. Nevertheless, parallel-link networks are special, and in most networks, traffic has to simultaneously traverse links (or subnetworks) operated by independent service providers. The simplest network topology allowing this feature is the parallel-serial structure, which we study in this paper. In contrast to existing results, we show that in the presence of serial links, the efficiency loss relative to the social optimum can be arbitrarily large. The reason for this degradation of performance is the double marginalization problem, whereby each serial provider charges high prices not taking into account the effect of this strategy on the profits of other providers along the same path. Nevertheless, when there are no delay costs without transmission (i.e., latencies at zero are equal to zero), irrespective of the number of serial and parallel providers, the efficiency of strong oligopoly equilibria can be bounded by 1 2, where strong oligopoly equilibria are equilibria in which each provider plays a strict best response and all of the traffic is transmitted. However, even with strong oligopoly equilibria, inefficiency can be arbitrarily large when the assumption of no delay costs without transmission is relaxed.