Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Cooperative Game Theory <s> We propose an abstract approach to coalition formation that focuses on simple merge and split rules transforming partitions of a group of players. We identify conditions under which every iteration of these rules yields a unique partition. The main conceptual tool is a specific notion of a stable partition. The results are parametrized by a preference relation between partitions of a group of players and naturally apply to coalitional TU-games, hedonic games and exchange economy games. <s> BIB001 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Cooperative Game Theory <s> "Introduction to the Theory of Cooperative Games" systematically studies the main solutions of cooperative games: the core, bargaining set, kernel, nucleolus, and the Shapley value of TU games, and the core, the Shapley value, and the ordinal bargaining set of NTU games. To each solution, a separate chapter is devoted, in which its properties are investigated in full detail. Moreover, important variants are defined or even intensively analyzed. Separate chapters cover continuity, dynamics, and geometric properties of solutions of TU games. This study culminates in uniform and coherent axiomatizations of all the foregoing solutions (excluding the bargaining set). Except for the Shapley value such axiomatizations have not appeared in any book. Moreover, "Introduction to the Theory of Cooperative Games" contains a detailed analysis of the main results on cooperative games without side payments. Such analysis is very limited or non-existent in the existing literature on game theory. <s> BIB002 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Cooperative Game Theory <s> The Shapley value is a key solution concept for coalitional games in general and voting games in particular. Its main advantage is that it provides a unique and fair solution, but its main drawback is the complexity of computing it (e.g., for voting games this complexity is #p-complete). However, given the importance of the Shapley value and voting games, a number of approximation methods have been developed to overcome this complexity. Among these, Owen's multi-linear extension method is the most time efficient, being linear in the number of players. Now, in addition to speed, the other key criterion for an approximation algorithm is its approximation error. On this dimension, the multi-linear extension method is less impressive. Against this background, this paper presents a new approximation algorithm, based on randomization, for computing the Shapley value of voting games. This method has time complexity linear in the number of players, but has an approximation error that is, on average, lower than Owen's. In addition to this comparative study, we empirically evaluate the error for our method and show how the different parameters of the voting game affect it. Specifically, we show the following effects. First, as the number of players in a voting game increases, the average percentage error decreases. Second, as the quota increases, the average percentage error decreases. Third, the error is different for players with different weights; players with weight closer to the mean weight have a lower error than those with weight further away. We then extend our approximation to the more general k-majority voting games and show that, for n players, the method has time complexity O(k^2n) and the upper bound on its approximation error is O(k^2/n). <s> BIB003 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Cooperative Game Theory <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> Basics of Cooperative Game Theory <s> In this paper, we consider the problem of measurement allocation in a spatially correlated sensor field. Our objective is to determine the probability of each sensor's being measured for improved observability; the sensor located at less correlated area should be assigned more probability. To this end, we quantify the level of correlation of each sensor through the mutual information criterion reflecting the level of uncertainty about unattended locations. Then we deploy the Shapley value, a representative single-valued solution concept in cooperative game theory. The Shapley value expresses the average marginal contribution of each sensor to the observation of a spatially correlated sensor field, and can be used to allocate the probability of each sensor's being measured in proportion to its contribution. Against the intractability in computing the true Shapley value, we deploy a randomized methods based on sampling, which can compute the approximate Shapley value with linear time complexity. Through numerical experiments, we evaluate the approximate Shapley value achieved by the randomized method by comparing it to the exact Shapley value, and estimate how the measurement allocation based on the Shapley value contributes to the overall observability and coverage. <s> BIB005 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Cooperative Game Theory <s> In this paper we develop a polynomial method based on sampling theory that can be used to estimate the Shapley value (or any semivalue) for cooperative games. Besides analyzing the complexity problem, we examine some desirable statistical properties of the proposed approach and provide some computational results. <s> BIB006 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Cooperative Game Theory <s> In this paper, we consider the measurement allocation problem in a spatially correlated sensor field. Our goal is to determine the probability of each sensor's being measured based on its contribution to the estimation reliability; it is desirable that a sensor improving the estimation reliability is measured more frequently. We consider a correlation model reflecting transmission power limit, noise in measurement process and channel, and channel attenuation. Then the estimation reliability is defined as the distortion error between the event source in the sensor field and its estimation at the sink. Motivated by the correlation nature, we model the measurement allocation problem into a cooperative game, and then express each sensor's contribution using Shapley value — a formal quantification of individual player's average marginal contribution. Against the intractability in the computation of exact Shapley value, we deploy randomized method that enables to compute approximate Shapley value within reasonable time. In numerical experiments, we evaluate approximate Shapley value by comparing it to the exact one, and illustrate that measurement allocation according to Shapley value turns to the balance between the estimation reliability and network lifetime. <s> BIB007 </s> Game Theory for Wireless Sensor Networks: A Survey <s> Basics of Cooperative Game Theory <s> Energy consumption is an important performance measure in wireless sensor networks (WSN). Data transmission strategies of the WSN nodes have a great impact on the energy consumption. When the nodes work separately, the chosen strategy is local optimum and cannot prolong the whole network's lifetime due to the selfishness of each node. To reduce the whole WSN's energy consumption and prolong its lifetime, some nodes will cooperate and form a coalition. Based on the game theory, in this paper we adopt Shapley value as the coalition's payoff sharing mechanism. Consequently, we propose an energy-efficient coalition game model according to each node's Shapley value. The transferring process of the Markov states is used to simulate the process of forming coalitions. Based on the idea of Bargaining set, the concept of absorbing coefficient is given to control the transferring process. Experimental results show that the proposed model can be well used to prolong the WSN lifetime. <s> BIB008
To reduce the whole WSN's energy consumption and prolong its lifetime, some nodes will cooperate and form a coalition. Coalitional game theory is one of the most important cooperative game theory, thus, cooperative game theory is sometimes denoted as coalitional game theory BIB004 . For a WSN obeying the cooperative game theory, cooperating groups are formed and players choose strategies to maximize their own groups' utility. Coalitional game theory allows a reduction of power consumption in WSN by forming coalitions. Saad et al. BIB004 proposed a merger and split approach for coalition formation, which calculates the value of the utility function for every possible permutation of nodes and finds groups with the best utility value. Here, grouping is treated as a basic method to organize sensor nodes for cooperation between nodes. In this formation, the nodes know nothing about the grouping. On the other hand, a group leader is assigned as a special node which processes the information of the newly entered sensor nodes and decides who will be their possible group member in a group. We can group the nodes in two ways for different applications: (1) All the sensor nodes have similar sensed data could be placed in the same group, for example, sensing application. (2) The sensor nodes with shorter distances between them are allocated in the same group, for example, sending data from a source node to the sink. Apt and Witzel BIB001 proposed a generic approach for coalition formation through simple merge and split operations. Cooperative game theory can be further categorized into two branches: Transferable-utility game (TU) BIB002 and non-transferable-utility game (NTU)  . In TU game the payoff of the measurement allocation game is transferable. In NTU game the payoff for each agent in a coalition depends only on the actions selected by the agents in the coalition. ( ) (1 2 ) Shapley value is derived from the solution concept in cooperative game theory which was defined by Shapley  . It is one of the most important solution concepts in cooperative game theory and a representative single-valued solution concept in the theory of cooperative games BIB002 . An agent's Shapley value gives an indication of its prospects of playing the game in cooperative game theory. It is useful when there is a need to allocate the worth that a set of players can achieve if they agree to cooperate. The Shapley value was defined for TU games and NTU games in regard to conflicts among players  . Wu et al. BIB008 adopted Shapley values as the coalition's payoff sharing mechanism based on game theory. Byun et al. BIB005 investigated the spatial correlation in the context of measurement allocation that enables efficient detection of phenomena in inaccessible area. Byun and Balasingham BIB007 modeled the measurement allocation problem into a cooperative game using the Shapley value. They found a set of stable payoff allocations such as core values for all agents to satisfy. In order to avoid intractability in the computation of exact Shapley value, they deployed a randomized method to compute the approximate Shapley value within a reasonable time. Fatima et al. BIB003 proved that finding the exact Shapley value is Sharp-P-complete (#P-complete). Castro et al. BIB006 developed an approximation technique to compute the Shapley value based on the randomized method for cooperative game. They used sampling to estimate the Shapley value and any semi-values.