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 2145512846 2048523876 1974835443 2126014631 2288112308 2099481767 1991014770 1565111024
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. It is well known that in a network with arbitrary (convex) latency functions that are a function of edge traffic, the worst-case ratio, over all inputs, of the system delay caused due to selfish behavior versus the system delay of the optimal centralized solution may be unbounded even if the system consists of only two parallel links. This ratio is called the price of anarchy (PoA). In this paper, we investigate ways by which one can reduce the performance degradation due to selfish behavior. We investigate two primary methods (a) Stackelberg routing strategies, where a central authority, e.g., network manager, controls a fixed fraction of the flow, and can route this flow in any desired way so as to influence the flow of selfish users; and (b) network tolls, where tolls are imposed on the edges to modify the latencies of the edges, and thereby influence the induced Nash equilibrium. We obtain results demonstrating the effectiveness of both Stackelberg strategies and tolls in controlling the price of anarchy. For Stackelberg strategies, we obtain the first results for nonatomic routing in graphs more general than parallel-link graphs, and strengthen existing results for parallel-link graphs, (i) In series-parallel graphs, we show that Stackelberg routing reduces the PoA to a constant (depending on the fraction of flow controlled). (ii) For general graphs, we obtain latency-class specific bounds on the PoA with Stackelberg routing, which give a continuous trade-off between the fraction of flow controlled and the price of anarchy, (iii) In parallel-link graphs, we show that for any given class L of latency functions, Stackelberg routing reduces the PoA to at most α + (1 - α) · ρ(L), where α is the fraction of flow controlled and ρ(L) is the PoA of class L (when α = 0). For network tolls, motivated by the known strong results for nonatomic games, we consider the more general setting of atomic splittable routing games. We show that tolls inducing an optimal flow always exist, even for general asymmetric games with heterogeneous users, and can be computed efficiently by solving a convex program. Furthermore, we give a complete characterization of flows that can be induced via tolls. These are the first results on the effectiveness of tolls for atomic splittable games. The second of a two-part series, this paper derives an efficient solution to the minimal-revenue tolls problem. As introduced in Part I, this problem can be defined as follows: Assuming each trip uses only a path whose generalized cost is smallest, find a set of arc tolls that simultaneously minimizes both average travel time and out-of-pocket cost. As a point of departure, this paper first re-solves the single-origin problem of Part I, modeling it as a linear program. Then with a change of variable, it transforms the LP's dual into a simple longest-path problem on an acyclic network. The multiple-origin problem - where one toll for each arc applies to all origins - solves analogously. In this case, however, the dual becomes an elementary linear multi-commodity max-cost flow problem with an easy bundling constraint and infinite arc capacities. After a minor reformulation that simplifies the model's input to better accommodate output from common traffic assignment software, a solution algorithm is exemplified with a numerical example. This paper derives a simple fast algorithm for computing minimal-revenue tolls in a single-origin network. It assumes that trips have the same value of time, that they make user-optimizing path choices, and they have multiple destinations--but come from the same origin. The algorithm finds tolls that induce a traffic pattern minimizing average time per trip at a minimal average toll per trip. Formally, let X be the set of all feasible traffic assignments and assume all trips have the same value of time [alpha]>0; then the algorithm inputs a network with the system-optimizing flow xo vector and associated arc times t(xo). It outputs an optimal arc toll vector c*[greater-or-equal, slanted]0 such that for x[set membership, variant]X:([alpha]t(xo)+c*)T(x-xo)[greater-or-equal, slanted]0 Â forÂ x[set membership, variant]X (user Â optimal) That is, xo[set membership, variant]X becomes user-optimal, too. Compared to marginal-cost tolls, which would also produce this same effect, the min-revenue tolls c* possess important practical advantages. Perforce, they provide the same system-optimal network usage, but at a much cheaper price to the traveler--remarkably, they assure at least one toll-free path to every destination. In addition, min-revenue tolls have admirable stability: even large increases in travel demand can leave the solution c* virtually unchanged--an important feature since traffic volume can change continuously but tolls cannot. Finally, they provide guidance regarding potential network improvements. The algorithm presented is very efficient, easily able to solve networks with tens of thousands of nodes. A greedy potentials calculator, its expected running time for an n-node road network is a speedy O(n), while its worst case time for any network is O(m), where m is the number of arcs. Reducing traffic congestion via toll pricing has been a central topic in the operations research and transportation literature and, recently, it has been implemented in several cities all over the world. Since, in practice, it is not feasible to impose tolls on every edge of a given traffic network, we study the resulting mathematical problem of computing tolls on a predefined subset of edges of the network so as to minimize the total travel time of the induced equilibrium flow. We first present an analytical study for the special case of parallel edge networks highlighting the intrinsic complexity and nonconvexity of the resulting optimization problem. We then present algorithms for general networks for which we systematically test the solution quality for large-scale network instances. Finally, we discuss the related optimization problem of computing tolls subject to a cardinality constraint on the number of edges that have tolls. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 653, 262-285 2015 The problem of computing optimal network tolls that induce a Nash equilibrium of minimum total cost has been studied intensively in the literature, but mostly under the assumption that these tolls are unrestricted. Here we consider this problem under the more realistic assumption that the tolls have to respect some given upper bound restrictions on the arcs. The problem of taxing subnetworks optimally constitutes an important special case of this problem. We study the restricted network toll problem for both non-atomic and atomic (unweighted and weighted) players; our studies are the first that also incorporate heterogeneous players, i.e., players with different sensitivities to tolls. For non-atomic and heterogeneous players, we prove that the problem is NP-hard even for single-commodity networks and affine latency functions. We therefore focus on parallel-arc networks and give an algorithm for optimally taxing subnetworks with affine latency functions. For weighted atomic players, the problem is NP-hard already for parallel-arc networks and linear latency functions, even if players are homogeneous. In contrast, for unweighted atomic and homogeneous players, we develop an algorithm to compute optimal restricted tolls for parallel-arc networks and arbitrary (standard) latency functions. Similarly, for unweighted atomic and heterogeneous players, we derive an algorithm for optimally taxing subnetworks for parallel-arc networks and arbitrary (standard) latency functions. The key to most of our results is to derive (combinatorial) characterizations of flows that are inducible by restricted tolls. These characterizations might be of independent interest. We study the negative consequences of selfish behavior in a congested network and economic means of influencing such behavior. We consider a model of selfish routing in which the latency experienced by network traffic on an edge of the network is a function of the edge congestion, and network users are assumed to selfishly route traffic on minimum-latency paths. The quality of a routing of traffic is measured by the sum of travel times (the total latency).It is well known that the outcome of selfish routing (a Nash equilibrium) does not minimize the total latency. An ancient strategy for improving the selfish solution is the principle of marginal cost pricing, which asserts that on each edge of the network, each network user on the edge should pay a tax offsetting the congestion effects caused by its presence. By pricing network edges according to this principle, the inefficiency of selfish routing can always be eradicated.This result, while fundamental, assumes a very strong homogeneity property: all network users are assumed to trade off time and money in an identical way. The guarantee also ignores both the algorithmic aspects of edge pricing and the unfortunate possibility that an efficient routing of traffic might only be achieved with exorbitant taxes. Motivated by these shortcomings, we extend this classical work on edge pricing in several different directions and prove the following results.We prove that the edges of a single-commodity network can always be priced so that an optimal routing of traffic arises as a Nash equilibrium, even for very general heterogeneous populations of network users.When there are only finitely many different types of network users and all edge latency functions are convex, we show how to compute such edge prices efficiently.We prove that an easy-to-check mathematical condition on the population of heterogeneous network users is both necessary and sufficient for the existence of edge prices that induce an optimal routing while requiring only moderate taxes. In this paper, we present a combined study of price competition and traffic control in a congested network. We study a model in which service providers own the routes in a network and set prices to maximize their profits, while users choose the amount of flow to send and the routing of the flow according to Wardrop's principle. When utility functions of users are concave and have concave first derivatives, we characterize a tight bound of 2-3 on efficiency in pure strategy equilibria of the price competition game. We obtain the same bound under the assumption that there is no fixed latency cost, i.e., the latency of a link at zero flow is equal to zero. These bounds are tight even when the numbers of routes and service providers are arbitrarily large. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008 Congestion toll pricing addresses the classic traffic assignment problem for which Wardrop enunciated two principles of traffic flow: user-optimal behavioral hypothesis and the notion and system-optimality. (See Florian and Hearn, 1995, for a recent review of the traffic assignment problem and Johnson and Mattson, 1992 for a recent volume of papers on road pricing.) The traditional objective of congestion pricing has been to determine link tolls which will cause the solution of the tolled user-optimal problem to be optimal for the untolled system problem (Arnott and Small, 1994). In most of the literature, the one choice given has been the vector of marginal social cost pricing tolls.