The bound of price of anarchy for multi-class and multi-criteria traffic equilibrium problem

Abstract

In this paper, we use the variational method to study the efficiency loss of user equilibrium for the multi-class, multi-criterion traffic equilibrium with general tolls and a discrete set of value of time. By introducing three important parameters ters k ₁, k ₂, k ₃, we derive several bounds of price of anarchy for this problem when tolls are considered and not considered as part of the system cost, with the cost-based criterion.

Keywords

Value of time / variational method / price of anarchy / multi-class multi-criterion traffic equilibrium

References

[1] Chau G.P., Sim P.H.. The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands. Operations Research Letters, 2003, 31: 327-334.

[2] Correa J.R., Schulz A.S., Stier-Moses N.E.. Selfish routing in capacitated networks. Mathematics of Operations Research, 2004, 29: 961-976.

[3] Dial R.B.. Network-optimized road pricing, part I: aparable and a model. Operations Research, 1999, 47(1): 54-64.

[4] Dial R.B.. Network-optimized road pricing, part II: algorithms and examples. Operations Research, 1999, 47(2): 327-336.

[5] Guo X.L., Yang H.. User heterogeneity and bi-criteria system optimum. Transportation Research Part B, 2009, 43: 379-390.

[6] Guo X.L., Yang H., Liu T.L.. Bounding the inefficiency of logit-based stochastic user equilibrium. European Journal of Operational Research, 2010, 201: 463-469.

[7] Guo X.L., Yang H.. Pareto-improving congestion pricing and revenue refunding with multiple user classes. Transportation Research Part, 2010, 44: 972-982.

[8] Han D., Yang H.. The multi-class, multi-criterion trafficquilibrium and the efficiency of congestion pricing. Transportation Research Part E, 2008, 44: 753-773.

[9] Han D., Lo H.K., Sun J., Yang H.. The toll effecton price of anarchy when costs are nonlinear and asymmetric. European Journal of Operations Research, 2008, 186: 300-316.

[10] Han D., Yang H., Wang X.L.. Efficiency of plate-number-based traffic rationing in general networks. Research Part E, 2010, 46: 1095-1110.

[11] Koutsoupias E., Papadimitriou C.H.. Worst-case equilibria. Lecture Notes in Computer Science, 1999, 1563: 404-413.

[12] Marcotte, P. & Zhu, D.L. (1997). Equilibria with infinitely manydifferentiated classes of customers. In: Pang, J.S., Ferris, M. (eds.), Complementarity and variational problems, state of art, pp. 234–258. SIAM

[13] Marcotte P., Zhu D.L.. Existence and computation of optimal tolls in multiclass network equilibrium problem. Operations Research Letters, 2009, 37: 211-214.

[14] Papadimitriou, C.H. (2001). Algorithms, games, and the Internet. In: Heraklion, Greece (ed.), The 33rd Annual ACM Symposium on Theory of Computing (STOC), 749–753, New York, 2001, ACM Press

[15] Perakis G.. The price of anarchy when costs are non-separable and asymmetric. Lecture Notes in Computer Science, 2004, 3064: 46-58.

[16] Perakis G.. The “Price of Anarchy” under nonlinear and asymmetric costs. Mathematics of Operations Research, 2007, 32(3): 614-628.

[17] Roughgarden T., Tardos. How bad is selfish routing?. Journal of the ACM, 2002, 49(2): 236-259.

[18] Roughgarden T., Tardos. Bounding the inefficiency of equilibria in nonatomic games. Games and Economic Behavior, 2004, 47: 389-403.

[19] Yang H., Huang H.J.. The multi-class, multi-criteria traffic network equilibrium and systems optimum problem. Transportation Research Part B, 2004, 38: 1-15.

[20] Yang H., Han D., Lo H.K.. Atomic splitable selfishrouting with polynomial cost functions. Networks and Spatial Economics, 2008, 8(4): 443-451.

[21] Yang, H. & Huang, H.J. (eds.) (2005). Mathematical and Economic Theory of Road Pricing. Elsevier

[22] Yang H., Xu W., Heydecker B.. Bounding the efficiency of road pricing. Transportation Research Part E, 2010, 46: 90-108.

[23] Yu X.J., Huang H.J., Liu T.L.. Efficiency loss of the multiclss stochastic traffic equilibrium assignment with fixeddemand. Journal of Transportation Systems Engineering and Information Technology, 2009, 9(4): 83-89.