Research objectives: Network formation games constitute a nice game theoretical framework providing considerable insight into the mechanisms that form the topology of real world complex networks. In such games the emphasis is on the economic driving forces behind the emergence of different network topologies as equilibrium solutions. The framework effectively analyzes the tradeoff between link costs and distance costs between selfish and rational players of the game (network nodes), as the key incentives of building specific network topologies. In these games however the distance between two players is almost exclusively measured by hopcount of the shortest path that connects them. When it comes to infocommunication networks there are several reasons why this simple view is limited. In order to ensure an expedient flow of information through the network, one often needs to provision routes taking into consideration a broader set of attributes beyond mere path length, such as path reliability and resilience constraints bandwidth and perceived congestion, business relations and service level agreements between ISPs, etc. These path selection strategies are usually described under the umbrella of policy routing and indeed, a significant portion of the Internet today runs over policy routing. The analysis of Nash equilibriums coming out of such modified games is therefore a compelling question, that can help to understand and design the topology and functioning of such complex economy-driven infocommunication networks.

Open problems and research goals: Extend the framework of network formation games to support the analysis of the following aspects of routing:

• support BGP policy routing to understand the forces forming the topology of the AS level internet
• support of network coding to design network topologies where network coding can be effectively exploited for boosting network throughput
• support for greedy routing, which is one of the most important routing and searching mechanisms used in real world complex networks

Requirements:

• solid background in the area of complex networks
• aware of the main tools in applied game theory
• experience in computer programming