We consider a basic resource allocation game, where the players' strategy spaces are subsets of @math and cost utility functions are parameterized by some common vector @math and, otherwise, only depend on the own strategy choice. A strategy of a player can be interpreted as a vector of resource consumption and a joint strategy profile naturally leads to an aggregate consumption vector. We assume that resources can be priced, that is, the game is augmented by a price vector @math and players have quasi-linear overall costs utilities meaning that in addition to the original costs utilities, a player needs to pay the corresponding price per consumed unit. We investigate the following question: for which aggregated consumption vectors @math can we find prices @math that induce an equilibrium realizing the targeted consumption profile? For answering this question, we develop a duality-based framework and derive a characterization of the existence of such @math and @math . We show that our characterization can help to unify parts of three largely independent streams in the literature -- tolls in transportation systems, Walrasian market equilibria and congestion control in communication networks. Besides reproving existing results we establish novel existence results by drawing connections to polyhedral combinatorics and discrete convexity.
A large body of work in the area of transportation networks is concerned with congestion toll pricing, see for example Knight @cite_12 , @cite_13 , Smith @cite_8 , and @cite_9 . @cite_13 showed that for the Wardrop model with homogeneous users, charging the difference between the marginal cost and the real cost in the socially optimal solution (marginal cost pricing) leads to an equilibrium flow which is optimal. @cite_75 considered the case of heterogeneous users, that is, users value latency relative to monetary cost differently. For single-commodity networks, the authors showed the existence of tolls that induce an optimal flow as Nash flow. Yang and Huang @cite_55 , @cite_0 and Karakostas and Kolliopoulos @cite_61 proved that there are tolls inducing an optimal flow for heterogenous users even in general networks - all proofs are based on linear programming duality. Swamy @cite_25 and Yang and Zhang @cite_26 proved the existence of optimal tolls for the atomic splittable model using convex programming duality.
@cite_61 @cite_26 @cite_75 @cite_8 @cite_9 @cite_55 @cite_0 @cite_13 @cite_25 @cite_12
1521705705 2064824188 2099481767 1996393333 1565111024 2129592590 2123733911 2145512846 2051688498
We examine how the selfish behavior of heterogeneous users in a network can be regulated through economic disincentives, i.e., through the introduction of appropriate taxation. One wants to impose taxes on the edges so that any traffic equilibrium reached by the selfish users who are conscious of both the travel latencies and the taxes will minimize the social cost, i.e., will minimize the total latency. We generalize previous results of Cole, Dodis and Roughgarden that held for a single origin-destination pair to the multicommodity setting. Our approach, which could be of independent interest, is based on the formulation of traffic equilibria as a nonlinear complementarity problem by Aashtiani and Magnanti (1981), We extend this formulation so that each of its solutions will give us a set of taxes that forces the network users to conform, at equilibrium, to a certain prescribed routing. We use the special nature of the prescribed minimum-latency flow in order to reduce the difficult nonlinear complementarity formulation to a pair of primal-dual linear programs. LP duality is then enough to derive our results. 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. 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. The paper shows that if the cost and demand functions satisfy certain weak smoothness conditions then the marginal cost taxation of a transportation network is optimal in the usual local sense. Interactions between the cost of travel along a link and flow along other links and between the demand for travel along a route and flow along other routes are permitted. 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. It is well known that in the standard traffic network equilibrium model with a single value of time (VOT) for all users, a so-called marginal-cost toll can drive a user equilibrium flow pattern to a system optimum. This result holds when either cost (money) or time units are used in expressing the objective function of the system optimum and the criterion for user equilibrium. This paper examines the multi-criteria or the cost-versus-time network equilibrium and system optimum problem in a network with a discrete set of VOTs for several user classes. Specifically, the following questions are investigated: Are the user-optimal flows dependent upon the unit (time or money) used in measuring the travel disutility in the presence of road pricing? Are there any uniform link tolls across all individuals (link tolls that are identical for all user classes) that can support a multi-class user equilibrium flow pattern as a system optimum when the system objective function is measured by either money or time units? What are the general properties of the valid toll set? 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. 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. Arguments for social interference developed by Pigou and Graham illustrate common misinterpretations of the meaning of cost and its variation with output, 582. — I. The private owner of a natural opportunity secures maximum return from it by charging that rent which halts the application of investment at the point which is socially most advantageous, 584. — II. The notion of decreasing cost is a fallacy; competitive price fixation under decreasing cost or increasing returns an impossible situation, 592. — III. The law of comparative advantage in international trade is fundamentally sound, 599. — Importation a method of using resources to produce the imported good, and will be employed under competitive conditions only when more efficient than a direct method, 603. — The competitive system has important defects, but they lie outside the mechanical theory of exchange relations, 605.