Some Recent Advances on the Application of Game Theory to Networking

Speaker : Ariel Orda
Technion (Israel Institute of Technology)
Date: 07/11/2018
Time: 2:00 pm - 3:00 pm
Location: LINCS -DTC room

Abstract

In the first part of the talk we shall consider game theory as a tool for analyzing and predicting the evolution of the Internet topology. We study the structure and evolution of the Internet’s Autonomous System (AS) interconnection topology as a game with heterogeneous players that incorporate reliability considerations. We also consider the case where utility (or monetary) transfers are allowed between the players. In this network formation game, the utility of a player depends on the network structure, e.g., the distances between nodes and the cost of links. We analyze static properties of the game, such as the prices of anarchy and stability, as well as the (novel) price of reliability, and provide explicit results concerning the generated topologies. Furthermore, we provide dynamical analysis of topological quantities, demonstrate linear convergence rate and explain the prevalence of some “network motifs”, i.e., sub-graphs that are expected to appear frequently in the network. Through real-world data, we provide encouraging support to our predictions.

Research on the application of game theory in the context of networking has focused on non-cooperative games, where the selfish agents cannot reach a binding agreement on the way they would share the infrastructure. Many approaches have been proposed for mitigating the typically inefficient operating points. However, in a growing number of networking scenarios, selfish agents are able to communicate and reach an agreement. Hence, the degradation of performance should be considered at an operating point of a cooperative game, e.g., the Nash bargaining solution, core or nucleolus. In the second part of  the talk we shall describe a body of work that attempts to lay foundations for the application of cooperative game theory to fundamental problems in networking, with a focus on routing. Depending on the scenario, we will reach conclusions on how cooperation among agents affects their own performance as well as that of the system. We will discuss network design guidelines that follow from our findings.

Bio:

Ariel Orda is the Herman & Gertrude Gross Professor of Communications at the Technion. He received his BSc (summa cum laude), MSc and PhD at the Technion. He is an IEEE Fellow. During 1.1.2014-12.31.2017, he served as the Dean of the Viterbi Faculty of Electrical Engineering at the Technion. His research interests include network routing, the application of game theory to networking, survivability, QoS provisioning and wireless networks. He received several awards for research, teaching, and service.