Game Theory in Wireless and Communication Networks: Theory, Models, and Applications

by Zhu Han , Dusit Niyato , Walid Saad , Tamer Başar , Are Hjørungnes

• ISBN13: 9780521196963
• ISBN10: 0521196965
• Format: Hardcover
• Copyright: 2012-01-09
• Publisher: Cambridge University Press

Summary

This unified treatment of game theory focuses on finding state-of-the-art solutions to issues surrounding the next generation of wireless and communications networks. Future networks will rely on autonomous and distributed architectures to improve the efficiency and flexibility of mobile applications, and game theory provides the ideal framework for designing efficient and robust distributed algorithms. This book enables readers to develop a solid understanding of game theory, its applications and its use as an effective tool for addressing wireless communication and networking problems. The key results and tools of game theory are covered, as are various real-world technologies including 3G networks, wireless LANs, sensor networks, dynamic spectrum access and cognitive networks. The book also covers a wide range of techniques for modeling, designing and analysing communication networks using game theory, as well as state-of-the-art distributed design techniques. This is an ideal resource for communications engineers, researchers, and graduate and undergraduate students.

Author Biography

Zhu Han is an Assistant Professor of Electrical and Computer Engineering at the University of Houston, USA. Dusit Niyato is an Assistant Professor in the School of Computer Engineering at the Nanyang Technological University (NTU), Singapore. Walid Saad is an Assistant Professor in the Electrical and Computer Engineering Department at the University of Miami. His research interests include applications of game theory in wireless networks, small cell networks, cognitive radio, wireless communication systems (UMTS, WiMAX, LTE, etc), and smart grids. Tamer Basar is a Swanlund Chair holder and CAS Professor of Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign, USA. Are Hjrungnes was a Professor in the Faculty of Mathematics and Natural Sciences at the University of Oslo, Norway.

Table of Contents

Preface	p. xv
Introduction	p. 1
Brief introduction to the history of game theory	p. 1
Game theory in wireless and communication networks	p. 3
Organization and targeted audience	p. 4
Timeliness of the book	p. 6
Outline of the book	p. 9
Wireless networks: an introduction	p. 14
Wireless channel models	p. 15
Radio propagation	p. 15
Interference channel	p. 20
Categorization of wireless networks	p. 21
3G cellular networks and beyond	p. 21
WiMAX networks	p. 25
WiFi networks	p. 27
Wireless personal area networks	p. 31
Wireless ad hoc networks	p. 37
Wireless sensor networks	p. 40
Advanced wireless technology	p. 45
OFDM technology	p. 45
Multiple-antenna systems	p. 47
Cognitive radio	p. 49
Fundamentals of game theory
Non-cooperative games	p. 55
Non-cooperative games: preliminaries	p. 55
Introduction	p. 55
Basics of non-cooperative games	p. 56
Non-cooperative games in strategic form	p. 58
Matrix games	p. 58
Dominating strategies	p. 61
Nash equilibrium	p. 63
Static continuous-kernel games	p. 65
Mixed strategies	p. 69
Efficiency and equilibrium selection	p. 72
Dynamic non-cooperative games	p. 74
Non-cooperative games in extensive form	p. 74
Repeated games	p. 80
Stochastic games	p. 84
Special classes of non-cooperative games	p. 85
Potential games	p. 85
Stackelberg games	p. 88
Correlated equilibrium	p. 91
Supermodular games	p. 94
Wardrop equilibrium	p. 96
Summary	p. 100
Bayesian games	p. 101
Overview of Bayesian games	p. 101
Simple example	p. 101
Static Bayesian game	p. 102
Bayesian dynamic games in extensive form	p. 104
Cournot duopoly model with incomplete information	p. 105
Auction with incomplete information	p. 107
Applications in wireless communications and networking	p. 109
Packet-forwarding game '	p. 109
K-player Bayesian water-filling game	p. 112
Channel-access game	p. 116
Bandwidth-auction game	p. 119
Bandwidth-allocation game	p. 121
Summary	p. 122
Differential games	p. 124
Optimal-control theory	p. 125
Dynamic programming	p. 125
The maximum principle	p. 126
Differential games	p. 128
Main ingredients and general results	p. 128
Stackelberg differential game	p. 130
Applications of differential games in wireless communications and networking	p. 136
Summary	p. 137
Evolutionary games	p. 138
The evolutionary process	p. 139
Evolutionarily stable strategies	p. 139
Replicator dynamics	p. 141
The evolutionary game and reinforcement learning	p. 143
Applications of evolutionary games in wireless communications and networking	p. 144
Congestion control	p. 144
Evolutionary game for the Aloha protocol	p. 146
Evolutionary game for WCDMA access	p. 148
Routing-potential game	p. 149
Cooperative sensing in cognitive radio	p. 151
TCP throughput adaptation	p. 154
User churning behavior	p. 158
Dynamic bandwidth allocation with evolutionary network selection	p. 163
Summary	p. 170
Cooperative games	p. 171
Bargaining theory	p. 171
Introduction	p. 171
The Nash bargaining solution	p. 172
Sample applications in wireless and communication networks	p. 178
Coalitional game theory: basics	p. 185
Introduction	p. 185
Coalitional-game theory: preliminaries	p. 185
Class I: canonical coalitional games	p. 189
Main properties of canonical coalitional games	p. 189
The core as a solution for canonical coalitional games	p. 190
The Shapley value	p. 195
The nucleolus	p. 196
Sample applications in wireless and communication networks	p. 198
Class II: coalition-formation games	p. 203
Main properties of coalition-formation games	p. 203
Impact of a coalitional structure on solution concepts for canonical coalitional games	p. 203
Dynamic coalition-formation algorithms	p. 205
Sample applications in wireless and communication networks	p. 209
Class III: coalitional graph games	p. 215
Main properties of coalitional graph games	p. 215
Coalitional graph games and network-formation games	p. 216
Sample applications in wireless and communication networks	p. 219
Summary	p. 220
Auction theory and mechanism design	p. 221
Introduction and auction basics	p. 222
Mechanism design	p. 226
Equilibrium concepts	p. 226
Participation and incentive compatibility	p. 227
Revelation principle	p. 228
Budget balance and efficiency	p. 228
Groves mechanism	p. 229
Impossibility and possibility	p. 229
Special auctions	p. 230
VCG auction	p. 230
Share auction	p. 232
Double auction	p. 233
Examples of communication applications	p. 235
Cognitive radio	p. 236
Physical-layer security	p. 248
Summary	p. 251
Applications of game theory in communications and networking
Cellular and broadband wireless access networks	p. 255
Uplink power control in CDMA networks	p. 257
Single-cell CDMA networks	p. 258
Multi-cell wireless CDMA networks	p. 263
Resource allocation in single-cell OFDMA networks	p. 269
OFDMA resource-allocation model	p. 270
Nash bargaining solution for subcarrier allocation	p. 272
Algorithms for reaching the Nash bargaining solution	p. 274
Power allocation in femtocell networks	p. 279
Femtocell power control as a Stackelberg game	p. 280
Multi-leader multi-follower Stackelberg equilibrium	p. 284
Algorithm for reaching the Stackelberg equilibrium	p. 286
IEEE 802.16 broadband wireless access networks	p. 287
Resource allocation and admission control	p. 287
Relay-station deployment in IEEE 802.16j	p. 299
Network selection in multi-technology wireless networks	p. 307
Network selection as a non-cooperative game	p. 309
Network selection with incomplete information	p. 311
Summary	p. 320
Wireless local area networks	p. 321
MAC protocol design	p. 322
Static game	p. 323
Dynamic game	p. 324
Deviation detection and penalization	p. 325
Related work	p. 326
Random-access control	p. 326
Choice of utility function	p. 327
Dynamics of a random-access game	p. 328
Extension with propagation delay and estimation error	p. 329
Related work	p. 329
Rate selection for VoIP service on WLAN	p. 330
Game formulation	p. 330
Payoff function	p. 331
Access-point selection	p. 332
Formulation of a population game	p. 333
Price of anarchy	p. 335
Access pricing	p. 335
Related work	p. 336
Admission control	p. 337
Two-player game formulation	p. 337
Interpretation of payoff	p. 339
WiFi access-point pricing	p. 339
Pricing scheme for direct payment	p. 340
User with Web browsing	p. 341
User with file transfer	p. 342
Model for uncertain application	p. 343
Summary	p. 344
Multi-hop networks	p. 345
Routing-game basics	p. 345
Cooperation enforcement and learning using a repeated game	p. 349
System model and problem formulation	p. 349
Self-learning cooperation-enforcing framework	p. 350
Asynchronous network	p. 352
Case analysis and performance evaluations	p. 353
Hierarchical routing using a network-formation game	p. 357
System model and game formulation	p. 358
Hierarchical network-formation game solution	p. 362
Hierarchical network-formation algorithm	p. 364
Simulation results and analysis	p. 366
Other typical approaches	p. 369
Price-based solution	p. 369
Truthfulness and security using auction theory	p. 370
Evolutionary-game approach	p. 372
Summary	p. 373
Cooperative-transmission networks	p. 375
Basics of cooperative transmission	p. 376
Cooperative-transmission protocols	p. 376
State of the art and impact on different layers	p. 380
Non-cooperative game for relay selection and power control	p. 380
Relay-selection and power-control problem	p. 381
Stackelberg-game approach	p. 382
Auction-theory-based resource allocation	p. 389
Resource-allocation objectives	p. 389
Share-auction approach	p. 392
Cooperative transmission using a cooperative game in MANET	p. 399
Selfishness in packet-forwarding networks	p. 400
Cooperative transmission using a coalitional game	p. 402
Cooperative routing	p. 411
Cooperative-routing algorithms	p. 412
WiMAX IEEE 802.16j	p. 413
Summary	p. 416
Cognitive-radio networks	p. 418
Cooperative spectrum sensing	p. 421
System model	p. 421
Coalitional-game formulation	p. 423
Centralized approach and performance comparison	p. 426
Power allocation as a non-cooperative game	p. 426
Underlay spectrum access and power allocation	p. 426
Properties of the Nash equilibrium for power allocation	p. 428
Distributed algorithm	p. 429
Pigouvian taxation and social optimality	p. 431
Related work	p. 432
Medium access control	p. 432
Channel allocation	p. 433
Channel access	p. 434
Distributed algorithms	p. 435
Decentralized dynamic spectrum access	p. 436
Overlay dynamic spectrum access	p. 436
Utility function	p. 438
Decentralized algorithm for channel access	p. 439
Alternative algorithms	p. 440
Radio resource competition based on a stochastic learning game	p. 441
System model of radio resource competition	p. 441
Auction mechanism	p. 442
Secondary-user strategy	p. 443
Learning algorithm	p. 445
Cheat-proof strategies for open spectrum sharing	p. 446
One-shot non-cooperative game	p. 446
Cooperative strategy	p. 447
Repeated games	p. 448
Cheat-proof strategy	p. 449
Spectrum leasing and cooperation	p. 450
Game formulation with instantaneous CSI	p. 451
Game formulation with long-term CSI	p. 454
Service-provider competition for dynamic spectrum allocation	p. 455
User demand	p. 455
Optimal price	p. 457
Related work	p. 458
Summary	p. 458
Internet networks	p. 460
Combined flow control and routing in communication networks	p. 462
Single user with multiple links	p. 463
Multiple users with multiple parallel links	p. 465
Sample Nash equilibria	p. 471
Congestion control in networks with a single service provider	p. 473
Pricing and congestion control	p. 474
Non-cooperative Nash game between followers	p. 476
Optimal pricing policy for the service provider	p. 478
Network with a large number of followers	p. 479
Pricing and revenue sharing for Internet service providers	p. 481
Pricing game among Internet service providers	p. 482
Revenue-sharing strategies	p. 484
Distributed algorithm for finding a Nash equilibrium	p. 485
Cooperative file sharing in peer-to-peer networks	p. 487
Cooperative vs. non-cooperative file sharing	p. 489
File sharing as a coalitional game in partition form	p. 491
Distributed algorithm for coalition formation	p. 493
Coalition formation in two-peer and N-peer networks	p. 495
Summary	p. 499
References	p. 501
Index	p. 530
Table of Contents provided by Ingram. All Rights Reserved.