NETWORKING GAMES, STRONG NASH EQUILIBRIUM AND OPTIMAL ROUTING
on Friday, April 27th, at 1:00 p.m. in room A106, Computer Science Building, Aalto University School of Science.
Vladimir Mazalov, Prof., Ph.D., Dr. Sci.
Karelian Research Centre of the Russian Academy of Sciences
Many real problems in modern networks and supercomputing such as resource distribution, scheduling and routing, spam fighting, etc. can be solved by game-theoretic methods. The players here can be the users, the jobs, the packages, etc. Networking games can be divided for two classes in respect of the traffic being divided (Wardrope games) or not (KP models) for units. The players can use the selfish and cooperative strategies.
Selfish players have different utility functions (for instance, latency functions of linear, quadratic or exponential form) and the main problem here is to find the equilibrium. That is a part of congestion games. We will consider the main methods of congestion and potential games. For general networks we find the potential functions and use it to construct the Nash equilibrium. Cooperative agents are interested in maximizing the common utility. Comparison of these costs is estimated by the price of anarchy. We present the different
approaches how to find it. We consider the Braess paradox and discuss the conditions for its existence. Some examples of real networks are presented.
Vladimir Mazalov finished his PhD studies in Faculty of the Applied Mathematics, Leningrad University in 1980. After that he has mainly worked in research projects funded by the Russian Academy of Sciences, in 1980-1998 in Chita Institute of Natural Resources, East Siberia. Currently, he is Professor of the Chair of Probability Theory and Data Analysis, Petrozavodsk State University and Director of the Institute of Applied Mathematical Research, Karelian Research Center, Russian Academy of Sciences.