ABSTRACT
Contents 14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 14.2 A Coalition Game-Theoretic Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
14.2.1 Coalition Forms of N-Person Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 14.2.1.1 Characteristic Function Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 14.2.1.2 Partition Function Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 14.2.1.3 Graph Function Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
14.2.2 Solution Concepts for Coalition Games. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 14.3 Coalition Forms of Games for Wireless Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
14.3.1 A Packet-Forwarding Coalition Game in CFF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 14.3.2 Interference Channel with Externalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322 14.3.3 Coalitions on Graph: Two Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
14.3.3.1 Myerson’s Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 14.3.3.2 Jackson and Wolinsky Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
14.4 Coalition Formation Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 14.4.1 Dynamic Models of Coalition Formation Process for Wireless Networks . . . . . 327
14.4.1.1 A Merge-and-Split Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 14.4.1.2 A Constrained Coalition Game Approach . . . . . . . . . . . . . . . . . . . . . . . . . . 327
14.4.2 Dynamic Modeling of Coalition Formation with Markov Chains . . . . . . . . . . . . 328
14.5 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 14.5.1 Computational Complexity for Dynamic Wireless Networks . . . . . . . . . . . . . . . . . 335
14.6 Conclusions and Open Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
14.1 Introduction Recent advances in technology have led to the development of distributed and self-configuring wireless network architectures. Cooperation among network nodes has been proposed as a technique for the efficient use of network resources. However, several recent works have shown that when self-interested wireless nodes are allowed to cooperate, in certain scenarios, they may prefer to cooperate with a selected set of other nodes rather than with the entire set of nodes [1-3]. For example, when wireless receivers in an interference channel are allowed to cooperate, by jointly decoding their received signals, cooperation among all nodes in the network results in maximum gains. But when the receivers cooperate using linear multiuser detectors, the cooperation among all the network nodes depends on the SNR regime and the detector employed [1]. In such scenarios, it is important to analyze cooperative interactions between small groups of nodes, as well as cooperative interactions among all network nodes. To model such cooperative scenarios, we consider the cooperative network as a coalition game, using concepts from coalition game theory.
