Game Theory for Wireless Sensor Networks: A Survey <s> Coalition Formation <s> Players adaptively learn how to bargain. A characteristic function describes the available surplus. The underlying bargaining game extends the Nash demand game by allowing subcoalitions to reach an agreement. Players' demands must be multiples of a money unit. We show that stochastically stable allocations (SSA) (i.e., allocations that are most stable to unlikely errors) are a subset of the core. Uniqueness does not obtain even when the money unit becomes arbitrarily small. Nonetheless, every SSA is related to the allocation that maximizes the product of players' utilities over the core; i.e., constrained egalitarian solution for TU-games. <s> BIB001 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Coalition Formation <s> Wireless sensor networks (WSN) are planted for sensing the area which people mostly concern and to send data of light, pressure, sound, and so on, back to people to make further analyses. Differ from normal lineal networks, WSN are usually restricted by energy store, plethoric information flow, and short communication distance. So, there are many research hotpots in WSN such as routing, economization of energy, adaptive self-configuration, etc. Among these aspects, the area of quality of service (QoS) remains largely open. This is due to that the optimal alive sensor node number is difficult to determine in a certain focused area which satisfies the requirement of QoS. In the paper, under a circumstance of ITS (Intelligent Transportation Systems) application, a modified Gur Game strategy based on localized information is given to determine the optimal alive node number in a focused area. In the strategy, all nodes use local information to modify their finite state automaton, and the base station receives the QoS feedback and gives the dynamic density domination information. The simulation results about the band shape density domination are given. The results show that the strategy can effectively control the density of nodes and meet the requirement of QoS even with impediment added. <s> BIB002 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Coalition Formation <s> This paper proposes a dynamic coalition formation algorithm for efficient sleep time allocation in a wireless sensor network (WSN) deployed to localize targets based on cooperation among the nodes. The sleep time allocation problem is formulated as a non-convex cooperative game and the concept of the core is exploited to solve this problem. In this formulation, determinant of the Cramer-Rao lower bound (CRLB) is used to evaluate the accuracy of estimations. Finally, an algorithm is proposed based on a best-reply rule which converges to the core with probability one if the core of the game is non-empty. <s> BIB003 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Coalition Formation <s> In this tutorial, we provided a comprehensive overview of coalitional game theory, and its usage in wireless and communication networks. For this purpose, we introduced a novel classification of coalitional games by grouping the sparse literature into three distinct classes of games: canonical coalitional games, coalition formation games, and coalitional graph games. For each class, we explained in details the fundamental properties, discussed the main solution concepts, and provided an in-depth analysis of the methodologies and approaches for using these games in both game theory and communication applications. The presented applications have been carefully selected from a broad range of areas spanning a diverse number of research problems. The tutorial also sheds light on future opportunities for using the strong analytical tool of coalitional games in a number of applications. In a nutshell, this article fills a void in existing communications literature, by providing a novel tutorial on applying coalitional game theory in communication networks through comprehensive theory and technical details as well as through practical examples drawn from both game theory and communication application. <s> BIB004 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Coalition Formation <s> Lifetime maximization is a key challenge in the design of sensor-network-based tracking applications. In this paper, formation of optimal coalitions of nodes is investigated for data acquisition in bearings-only target localization such that the average sleep times allocated to the nodes are maximized. Cooperative game theory is utilized as a tool to devise a distributed dynamic coalition formation algorithm in which nodes autonomously decide which coalition to join, while maximizing their feasible sleep times. If each node follows the proposed algorithm, the average sleep time for the entire network eventually converges to its maximum feasible value conditional on the pre-defined localization accuracy. This algorithm can also be employed in tracking slow moving targets. <s> BIB005 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Coalition Formation <s> In this paper, formation of optimal coalitions of nodes is investigated for data acquisition in bearings-only target localization such that the average sleep time allocated to the nodes is maximized. Targets are required to be localized with a prespecified accuracy where the localization accuracy metric is defined to be the determinant of the Bayesian Fisher information matrix (B-FIM). We utilize cooperative game theory as a tool to devise a distributed dynamic coalition formation algorithm in which nodes autonomously decide which coalition to join while maximizing their feasible sleep times. Nodes in the sleep mode do not record any measurements, hence, save energy in both sensing and transmitting the sensed data. It is proved that if each node operates according to this algorithm, the average sleep time for the entire network converges to its maximum feasible value. In numerical examples, we illustrate the tradeoff between localization accuracy and the average sleep time allocated to the nodes and demonstrate the superior performance of the proposed scheme via Monte Carlo simulations. <s> BIB006 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Coalition Formation <s> Energy consumption is one of the most important factors in wireless sensor networks (WSNs). Data transfer of sensor nodes makes great impact on the energy consumption of WSNs. To reduce the energy consumption, some nodes in a WSN form a coalition by transferring data coordinately instead of transferring alone. In this paper, we consider obtaining the method for data transfer strategies that can be specified as the proportion of the data sent by a node and that of the data forwarded by a node. First, we form the WSN coalitions based on Markov-process, and propose the concept of absorption coefficient to measure the coalitional profiles. Then, we use Nash equilibrium to determine the approximate data transfer strategies of the formed coalitions. Preliminary results of our simulation experiments show that the model proposed in this paper is effective to reduce the energy consumption of WSNs. <s> BIB007 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Coalition Formation <s> One important issue of designing wireless sensor networks is how we can improve the energy efficiency. As we know, for the same quality-of-service (QoS) requirement, a cooperative multiple-input-multiple-output (MIMO) scheme requires less transmission energy than a noncooperative single-input-single-output (SISO) scheme. However, the advantage of the cooperative MIMO scheme over the noncooperative SISO scheme does not always exist once the cost in terms of the additional overhead has been considered. In this paper, we focus on how we can select a proper transmission scheme, with the goal of improving the energy efficiency, e.g., prolonging the network lifetime. In particular, we model the transmission scheme selection problem as a non-transferable coalition formation game, with the characteristic function based on the network lifetime. Then, a simple algorithm based on a merge-and-split rule and the Pareto order is proposed to form coalition groups among individual sensor nodes. The resulting coalitional structure is characterized through novel stability notions and shows which transmission scheme is employed and which cluster nodes are chosen to collaborate with the cluster head. Extensive simulation results are provided to demonstrate the effectiveness of our proposed game model and algorithm. <s> BIB008
Agastya BIB001 studied a dynamic social learning model by focusing on allocations and completely abstracts from coalition formation process. Wu et al. BIB007 formed the WSN coalitions on the basis of Markov-process, and proposed the concept of absorption coefficient to measure the coalitional profiles and then use NE to determine the approximate data transfer strategies of the formed coalitions. Some nodes in a WSN form a coalition by transferring data coordinately instead of transferring independently in order to reduce energy consumption. Wu et al. BIB008 focused on how to select a proper transmission scheme for improving the energy efficiency. They modeled the transmission scheme selection problem as a non-transferable coalition formation game with the characteristic function based on the network lifetime. They further proposed a simple algorithm based on a merge-and-split rule and the Pareto order to form coalition groups among individual sensor nodes. Gharehshiran and Krishnamurthy BIB003 BIB005 BIB006 used cooperative game theory as a tool to devise a distributed dynamic coalition formation algorithm in which nodes autonomously decide which coalition to join while maximizing their feasible sleep times. The sleep time allocation problem is formulated as a non-convex cooperative game and the concept of the core is exploited to solve this problem. They solved two problems: BIB002 What are the optimal coalition structures for localizing multiple targets with a pre-specified accuracy? (2) How can nodes dynamically form optimal coalitions to ensure that the average sleep time allocated to the nodes is maximized? The two questions are solved nicely within the framework of coalition formation in a cooperative game. Saad et al. BIB004 classified coalitional game theory into three categories: Class I-canonical coalitional games (as a coalition comprising all nodes, it is not optimal), Class II-coalitional formation games (as a main branch of cooperative game theory, comprises several disjoint coalitions), and Class III-coalitional graph games (Figure 2 ). The classification is intended to provide an application-oriented approach to coalitional game theory. According to the coalitional game theory, n sensor nodes form the game by a triplet G = <N, v, S > characteristic form, where G is a coalitional game, N = {1, ..., N} is a fixed set of players called the grand coalition (the coalition comprising all nodes, it is not optimal), S = {S 1 , ..., S l } denotes a coalitional structure and a partition of N, and v is a characteristic function of coalition value which quantifies the worth of a coalition in a game. The coalitional game G seeks to form cooperative coalitions to strengthen their positions in the game. Any coalition S i (i = 1,..., l) represents an agreement between the players in S to act as a single entity. Nodes in each coalition share measurements to localize a particular target. 