2004 · 113 citations · 10 references
Natural SciencesBusiness EconomicsEconomicsMicroeconomicsOptimizationTaxationLinear ProgrammingNetwork FlowsNetwork OptimizationOptimal TaxationTransportation EconomicsTransportation ProblemsDuality TheoryEquilibriumLatency MinimizationMulti-commodity Flow ProblemMulticommodity FlowNetwork EquilibriumNonlinear Complementarity ProblemsPrimal Linear Programming
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.
10
Tim Roughgarden, Éva Tardos · Journal of the ACM · 2002 · 1.6K citations
Studies in the Economics of Transportation.
R. J. Smeed, Martin J. Beckmann, C. B. McGuire et al. · The Economic Journal · 1957 · 1.5K citations