The “Price of Anarchy” Under Nonlinear and Asymmetric Costs

References

• Basu S., Pollack R., Roy M.-F.Algorithms in Real Algebraic Geometry (2006) 102nd ed.(Springer-Verlag, Berlin, Germany) Algorithms and Computation in Mathematics SeriesCrossref, Google Scholar
• Beckmann M., McGuire C. B., Winsten C. B.Studies in the Economics of Transportation (1956) (Yale University Press, New Haven, CT) Google Scholar
• Braess D. Über ein Paradoxon aus der Verkehrsplanung. Unternehmenforschung (1968) 12:258–268Google Scholar
• Chau C. K., Sim K. M. The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands. Oper. Res. Lett. (2003) 31:327–334Crossref, Google Scholar
• Cole R., Dodis Y., Roughgarden T. Pricing network edges for heterogeneous selfish users. Conference version appeared in STOC (2003) 521–530 http://doi.acm.org/10.1145/780542.780618Crossref, Google Scholar
• Correa J., Schulz A., Stier Moses N. Computational complexity, fairness, and the price of anarchy of the maximum latency problem. Proc. 10th Integer Programming Combinat. Optim. Conf. (IPCO’04), Lecture Notes in Computer Science (2004) 3064Berlin, Germany:59–73Crossref, Google Scholar
• Correa J., Schulz A., Stier Moses N. Selfish routing in capacitated networks. Math. Oper. Res. (2004) 29(4):961–976Link, Google Scholar
• Dafermos S. Traffic equilibria and variational inequalities. Transportation Sci. (1980) 14:42–54Link, Google Scholar
• Dafermos S. Toll patterns for multiclass-user transportation networks. Transportation Sci. (1973) 7:211–223Link, Google Scholar
• Dafermos S., Nagurney A. A network formulation of market equilibrium problems, and variational inequlities. Oper. Res. Lett. (1984) 3:274–290Crossref, Google Scholar
• Dafermos S., Sparrow F. T. The traffic assignment problem for a general network. J. Res. National Bureau Standards B (1969) 73B:91–118Crossref, Google Scholar
• Dubey P. Inefficiency of Nash equilibria. Math. Oper. Res. (1986) 11:1–8Link, Google Scholar
• Florian M., Hearn D., Ball M., Magnanti T., Monma C., Nemhauser G. Network equilibrium models and algorithms. Handbook of Operations Research and Management Science (1995) 8(Elsevier Science Publishing Company, Amsterdam, The Netherlands) Google Scholar
• Florian M., Los M. A new look at static spatial price equilibrium problems. Regional Sci. Urban Econom. (1982) 12:579–597Crossref, Google Scholar
• Gabay D., Moulin H., Bensoussan A., Kleindorfer P., Tapiero C. S. On the uniqueness and stability of Nash-equilibria in non-cooperative games. Applied Stochastic Control in Econometrics and Management Science (1980) (North Holland, Amsterdam, The Netherlands) Google Scholar
• Hammond J. H. Solving asymmetric variational inequalities and systems of equations with generalized nonlinear programming algorithms. (1984) . Ph.D. thesis, MIT, Boston, MAGoogle Scholar
• Hearn D., Ramana M., Marcotte P., Nguyen S. Solving congestion toll pricing models. Equilibrium and Advanced Transportation Modeling(Kluwer Academic Publishers, Boston, MA) 109–124Google Scholar
• Hearn D., Yildirim M., Marcotte P., Gendreau M. A toll pricing framework for traffic assignment problems with elastic demand. Transportation and Network Analysis—Current Trends (2002) (Kluwer Academic Publishers, Boston, MA) 135–145Crossref, Google Scholar
• Johari R., Tsitsiklis J. N. Network resource allocation and a congestion game. Math. Oper. Res. (2003) 29(3):407–435Link, Google Scholar
• Koutsoupias E., Papadimitriou C. H., Meinel G., Tison S. Worst-case equilibria. Proc. 16th Annual Sympos. on Theoretical Aspects of Comput. Sci., Lecture Notes in Computer Science (1999) 1563(Springer-Verlag, Trier, Germany) 387–396Crossref, Google Scholar
• Marcotte P. Network design problem with congestion effects: A case of bilevel programming. Math. Programming (1986) 34:142–162Crossref, Google Scholar
• Nagurney A.Network Economics: A Variational Inequality Approach (1993) (Kluwer Academic Publishers, Boston, MA) Crossref, Google Scholar
• Nagurney A., Dong J., Zhang D. A supply chain network equilibrium model. Transportation Res. E (2002) 38:281–303Crossref, Google Scholar
• Nesterov Y., Nemirovskii A.Interior Point Polynomial Algorithms in Convex Programming. SIAM Stud. Appl. Math. (1994) 13(SIAM, Philadelphia, PA) Crossref, Google Scholar
• Pan V. Y. Solving a polynomial equation: Some history and recent progress. SIAM Rev. (1997) 39:187–220Crossref, Google Scholar
• Pang J-S., Facchinei F.Finite-Dimensional Variational Inequalities and Complementarity Problems (2003) I and II(Springer Verlag, New York) Google Scholar
• Patriksson M. The traffic assignment problem: Models and methods. Monograph (1994) . http://www.math.chalmers.se/∼mipat/LATEX/book_pub.pdfGoogle Scholar
• Perakis G. The price of anarchy under nonlinear and asymmetric costs. (2003) . Working paper, ORC, MIT, Boston, MAGoogle Scholar
• Perakis G., Sood A. Competitive multi-period pricing for perishable products: A robust optimization approach. Math. Programming (2006) 107(1–2):295–335Crossref, Google Scholar
• Roughgarden T. The price of anarchy is independent of the network topology. Proc. 34th ACM Sympos. Theory Comput. (2002) (Springer, Berlin, Germany) 428–437Crossref, Google Scholar
• Roughgarden T. Selfish routing. (2002) . Ph.D. thesis, Cornell University, Ithaca, NYGoogle Scholar
• Roughgarden T., Tardos E. How bad is selfish routing. Proc. 41st IEEE Sympos. Foundations of Comput. Sci. (2000) 93–102Crossref, Google Scholar
• Roughgarden T., Tardos E. Bounding the inefficiency of equilibria in nonatomic congestion games. J. ACM (2002) 49(2):236–259Crossref, Google Scholar
• Smith M. J. The existence, uniqueness and stability of traffic equilibria. Transportation Res. (1979) 13B:295–304Crossref, Google Scholar
• Sun J. A convergence analysis for a convex version of Dikin’s algorithm. Ann. Oper. Res. (1996) 62:357–374Crossref, Google Scholar
• Wardrop J. G. Some theoretical aspects of road traffic research. Proc. Inst. Civil Engineers, Part II (1952) 325–378Crossref, Google Scholar