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_33: Network pricing games provide a framework for modeling real-world settings with two types of strategic agents: owners (operators) of the network and users of the network. Owners of the network post a price for usage of the link they own so as to attract users and maximize profit; users of the network select routes based on price and level of use by other users. We point out that an equilibrium in these games may not exist, may not be unique and may induce an arbitrarily inefficient network performance. Our main result is to observe that a simple regulation on the network owners market solves all three issues above. Specifically, if an authority could set appropriate caps (upper bounds) on the tolls (prices) operators can charge, then: the game among the link operators has a unique and strong Nash equilibrium and the users' game results in a Wardrop equilibrium that achieves the optimal total delay. We call any price vector with these properties a great set of tolls. As a secondary objective, we want to compute great tolls that minimize total users' payments and we provide a linear program that does this. We obtain multiplicative approximation results compared to the optimal total users' payments for arbitrary networks with polynomial latencies of bounded degree, while in the single-commodity case we obtain a bound that only depends on the topology of the network. Lastly, we show how the same mechanism of setting appropriate caps on the allowable prices extends to the model of elastic demands.
@cite_3: THE CAPABILITIES AND EFFICIENT OPERATION OF SEVERAL TYPES OF TRANSPORTATION SYSTEMS ARE STUDIED. FOR HIGHWAY TRAFFIC THE MAIN EMPHASIS IS ON CONGESTION AND ITS CONSEQUENCES. QUEUING MODELS ARE USED TO DETERMINE FLUCTUATIONS IN WAITING TIME FOR TWO CASES, THE FLOW OF CARS THROUGH AN INTERSECTION AND THE PASSING OF SLOWER CARS BY FASTER CARS ON A TWO-LANE HIGHWAY. THE RESULTS OF THESE STUDIES ARE INCORPORATED INTO A NON-LINEAR MODEL OF HIGHWAY TRAFFIC BEHAVIOR ON A ROAD NETWORK. THE CAPACITIES ARE EXPRESSED BY THE RELATIONSHIP BETWEEN TRAFFIC FLOWS ON ALL ROUTES AND THE COSTS ENCOUNTERED ON EACH AS A RESULT OF THESE FLOWS. HIGHWAY TRAFFIC DEMANDS ARE THE RESULT OF A GREAT MANY INDIVIDUAL DECISIONS ABOUT DESTINATION, ROUTES, AND PREFERRED SPEEDS. THE ANALOGY BETWEEN HIGHWAY TRAFFIC EQUILIBRIUM AND THE MARKET RESPONSE MODELS USED BY ECONOMISTS IS GIVEN. IF THE INDIVIDUALLY INCURRED COST OF TRANSPORTATION IS REGARDED AS THE "PRICE" IN THE TRANSPORTATION "MARKET," THE ECONOMIST'S DEMAND CURVE BECOMES APPLICABLE. FOR A SINGLE ROAD IT GIVES THE FLOW OF TRAFFIC DEMANDED FOR ANY GIVEN COST ENCOUNTERED ON THAT ROAD. GENERALLY, THE HIGHER THE COST, THE SMALLER THE FLOW. CONSIDERING A ROAD NETWORK THE DEMAND FUNCTION GIVES THE FLOWS ON EACH ROUTE IN RESPONSE TO A SET OF TRANSPORTATION COSTS ALONG THESE ROUTES. EQUILIBRIUM EXISTS IF THE FLOWS ON ALL ROADS RESULTING FROM THESE COSTS ARE THE SAME AS THE FLOWS THAT PRODUCE THESE SAME COSTS. THIS CONCEPT IS APPLIED TO A STUDY OF TRAFFIC EQUILIBRIUM AND USE OF THE ANALYSIS IN THE PREDICTION OF TRAFFIC FLOWS IS DISCUSSED. THE ANALYSIS OF DEMAND AND OF EQUILIBRIUM RECOGNIZES THAT FREEDOM OF CHOICE IS PART OF THE SERVICE RENDERED BY THE ROAD NETWORK. TOLLS FROM THE USERS OF CONGESTED ROADS AT RATES THAT WOULD MEASURE THE COST TO OTHERS CAUSED BY THE AVERAGE ROAD USER WOULD ENCOURAGE BETTER USE OF THE HIGHWAY SYSTEM. THERE ARE OBSERVATIONS ON HOW CLOSELY MAXIMUM EFFICIENCY CAN BE APPROACHED BY PROPER CHOICE OF RATES ON PRESENT TOLL ROADS AND BY OTHER WAYS OF PENALIZING ADDITIONS TO TRAFFIC CONGESTION. BECAUSE OF THE NONLINEAR RELATIONSHIP BETWEEN USE AND COST, SUCH PRICING DOES NOT NECESSARILY PRODUCE REVENUES EQUAL TO THE TOTAL COST OF OPERATING AND FINANCING THE INDIVIDUAL FACILITY. SOME OBSERVATIONS ON THE QUESTION OF CRITERIA FOR EXTENSIONS OR IMPROVEMENTS OF THE NETWORK TO RELIEVE CONGESTION ARE GIVEN. AUTHOR
Recently, following our question on competition regulation of price competition between edge owners, @cite_33 consider the setting in which a central authority is allowed to put different toll caps on different edges of the network. Their main result is that for all network topologies there are toll caps so that firms are willing to put their toll equal to the cap, and the induced equilibrium flow is the optimal flow. An example of such caps are marginal tolls as introduced by @cite_3 . Notice that the assumption of individual toll caps is important. In practice, however, toll cap discrimination is often not allowed, which motivates our work on uniform toll caps.