Game Theory for Networking Applications

Equilibrium behaviors in games on networks are often defined by centralities of players. We show that centrality measures of a class (degree, eigenvalue centrality, Katz-Bonacich centrality, diffusion centrality, alpha-gamma centrality, and alpha-beta centrality) do characterize not just separate nodes but types of nodes. The typology relates the fact that the nodes in an undirected graph may be colored in a minimal number of colors in such a way that any node of a color has definite numbers of neighbors of definite colors. Networks of the same typology are characterized by a “type adjacency” matrix T, which shows for each type numbers of neighbors of different types. For any typology, if i and j are nodes of the same type (may be even belonging different networks of this typology), then c(i)  =  c(j), where c is any of the above-mentioned centrality measures. Networks of different size but with the same typology have common properties; in particular, game equilibria may be transplanted among networks of the same typology. For calculation of any of these centrality measures, the type adjacency matrix may be used instead of the adjacency matrix. A problem is: for which classes of networks each of a set of several centrality measures defines the same order on the set of nodes of network? We show that any network typology with two types of nodes possesses this property for the above-mentioned class of centrality measures.

In this paper, cooperative network games with pairwise interactions are considered. The cooperative version of games is investigated. For a particular type of networks, a simplified formula for the Shapley value based on a constructed characteristic function is derived. The time inconsistency of the Shapley value is shown.

We study routing on a ring network in which traffic originates from nodes on the ring and is destined to the center. The users can take direct paths from originating nodes to the center and also multihop paths via other nodes. We show that routing games with only one and two hop paths and linear costs are potential games. We give explicit expressions of Nash equilibrium flows for networks with any generic cost function and symmetric loads. We also consider a ring network with random number of users at nodes, all of them having same demand, and linear routing costs. We give explicit characterization of Nash equilibria for two cases: (i) General i.i.d. loads and one and two hop paths, (ii) Bernoulli loads. We also analyze optimal routing in each of these cases.

In this paper, we illustrate the properties of proposed dynamic secure routing game framework to effectively combat jamming attacks in distributed cognitive radio networks. We derive the saddle-point equilibrium for distributed routing game that supports a novel recovery of routing path failure against unknown attackers and enhances the security and resilience of the routing protocols in face of adversarial attacks. We use network simulation using NS-2 to corroborate our results in the paper.

As sponsored data gains popularity in industry, it is essential to understand its impact on the Internet service market. We investigate the interplay among Internet Service Providers (ISPs), Content Provider (CP), and End User (EU), where each player is selfish and wants to maximize its own profit. In particular, we consider multi-ISP scenarios, in which the network connectivity between the CP and the EU is jointly provided by multiple ISPs. We model the non-cooperative interaction between the players as a four-stage Stackelberg game, and derive the optimal behaviors of each player in equilibrium. Taking into account the transit price at intermediate ISP, we provide in-depth understanding on the sponsoring strategies of CP, and verify our results through numerical simulations.

The proliferation of novel devices and applications in the current cellular networks has forced the network operators to transform their resource allocation operations from centralized to distributed operations. This chapter discusses a novel framework based on matching games that operates in a distributed manner for future wireless networks. Moreover, this chapter also builds a bridge between matching games and resource allocation for novel 5G networking paradigms. Furthermore, the readers are also exposed to the potential challenges, key solution concepts, and algorithmic details of matching games for these 5G networking paradigms. Finally, this chapter also discusses the implementation details of matching games for these paradigms.

This paper uses a two-person mixed strategy game with stochastic time series to find the best strategy for conflict with uncontrollable forces, considered as an opponent. The framework of this game finds the best strategy towards preparation for a disaster or system crash. This strategic choice depends on payoffs and the chance that a disaster occurs. An analogue of the fluctuation theory is applied for finding the exact moment of decision making and the restriction of the system capacity. As such, any system which can indicate the crashing level could be described by this simple game framework. Analytically tractable results are obtained by using hybrid of the fluctuation theory and the mixed strategy game theory which enables to determine the decision making factors, including the best moment for decision making of the preliminary defense operation and the probability of the first observation moment when the system crashes.

Recent wide spreading of Ransomware has created new challenges for cybersecurity over large-scale networks. The densely connected networks can exacerbate the spreading and makes the containment and control of the malware more challenging. In this work, we propose an impulse optimal control framework for epidemics over networks. The hybrid nature of discrete-time control policy of continuous-time epidemic dynamics together with the network structure poses a challenging optimal control problem. We leverage the Pontryagin’s minimum principle for impulsive systems to obtain an optimal structure of the controller and use numerical experiments to corroborate our results.

The n-player Hotelling game calls for each player to choose a point on the line segment, so as to maximize the size of his Voronoi cell. This paper studies fault-tolerant versions of the Hotelling game. Two fault models are studied. The first assumes that the environment is prone to failure: with some probability, a disconnection occurs at a random point on the line, splitting it into two separate segments and modifying each player’s Voronoi cell accordingly. A complete characterization of the Nash equilibria of this variant is provided for every n. Additionally, a one-to-one correspondence is shown between equilibria of this variant and of the Hotelling game with no faults. The second fault model assumes the players are prone to failure: each player is removed from the game with i.i.d. probability, changing the payoffs of the remaining players accordingly. It is shown that for n ≥ 3 this variant of the game has no Nash equilibria.

Online live streaming enables people to communicate with popular influencers from around the world. Nowadays, social media is an integral part of our lives, and this demands a thorough analysis of such platforms. These live streaming applications have tremendous user bases, and learning the user behavior in such scenarios can be very insightful. Here, there is a great need to aggregate the individual preferences of the users into a single group preference. Social choice theory finds a considerable application here, being a framework for group decision making. In this paper, we examine the attributes of online live streaming applications utilizing the concepts of the social choice model. We perform analysis of a real-time dataset obtained from a live streaming platform and further validate the results using an Integer Linear Programming model. The analysis results clearly demonstrate the effectiveness of social choice in representing the user behavior in online live streaming applications.

In this paper, we consider a co-evolutionary model of social coordination and network formation, where heterogeneous agents of two groups make a decision on action in a 2 × 2 coordination game as well as the population with whom they costly interact. Agents of two groups support different constraints of active links. We find that in the situation of low linking cost, the co-existence of payoff dominate and risk dominate absorbing sets is determined by the population size of each group and the number of agents choosing the efficient action, not the size of overall population. If the number of agents with larger constraints is relatively larger than the size of another group’s population, and if the smaller constraint is larger than the number of efficient players, co-existence of both absorbing sets is able to be observed.

Real-world information communities exhibit inherent structures that characterize a system that is stable and efficient for content production and consumption. In this paper, we study such structures through mathematical modelling and analysis. We formulate a generic model of a community in which each member decides how they allocate their time between content production and consumption with the objective of maximizing their individual reward. We define the community system as “stable and efficient” when a Nash equilibrium is reached while the social welfare of the community is maximized. We investigate the conditions for forming a stable and efficient community under two variations of the model representing different internal relational structures of the community. Our analysis results show that the structure with “a small core of celebrity producers” is the optimally stable and efficient for a community. These analysis results provide possible explanations to the sociological observations such as “the Law of the Few” and also provide insights into how to effectively build and maintain the structure of information communities.

An effective interaction between the Social Network Services (SNS) and Cloud Computing (CC) enables the connection of people to the ubiquitous computing universe. The integration of SNS and CC is a technological revolution that presents the future of connectivity and reachability. This study explores the novel paradigm for future Internet of Things (IoT). Although there have been some studies in social-driven IoT, they merely consider the CC technique to improve service qualities and influences. In this study, S. Kim develops a novel cloud based SNS control scheme based on the reinforcement learning approach. To maximize the total SNS system performance, social services have been adaptively executed in the cloud system while taking into account the social welfare. This study can capture the properties of SNS and CC, and provides an effective solution for the social cloud system.

In this chapter, we consider an optimal charging and discharging process for multiple electric vehicles in a smart grid building to optimize the energy consumption profile of the building. The building controller aims to minimize the Square Euclidean Distance between the instantaneous energy demand and the average demand of the building. In a decentralized system, we design an energy cost-sharing model and apply a noncooperative approach to formulate an energy charging and discharging scheduling game. The distributed game minimizes the peak load and the total energy cost.

In this paper, we investigate the charging control problems of the electrical vehicles in smart grid, where electricity transactions exist between the aggregation and the electrical vehicles. We use the Stackelberg differential game to formulate the charging/discharging interactions between the aggregation and the electrical vehicles, and introduce the differential equations to reveal the dynamic behavior of the energy levels of the aggregation and the electrical vehicles. The aggregation acts as the leader, and controls the charging electricity price for the transactions to maximize the payoff. The electrical vehicles act as the followers, and control their charging/discharging power to minimize the energy cost. The open loop equilibrium solutions to the Stackelberg differential game can be obtained as the optimal solutions for the aggregations and the electrical vehicles. Numerical simulations and results show the effectiveness and advantages of the proposed algorithms.

Ever-increasing energy consumption and growing penetration of renewable energy sources stimulate the development of new power grid models and architectures. Since the decentralization of power grids raises the unreliability of power supply, it is crucial to switch to a production-oriented consumption in order to provide the stability of the grid. In this work, we describe a multi-supplier power grid model with day-ahead time span planning. We formulate and study a set of consumer cost minimization problems under flow distribution constraints. Finally, we consider an example illustrating the applicability of this model.