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
2123733911 2064824188 1521705705 2288112308
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. 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 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 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.