Game Theory Applications in Network Design

Game Theory Applications

in Network Design

Sungwook Kim

Sogang University, South Korea

A volume in the Advances in Wireless

Technologies and Telecommunication (AWTT)

Book Series

Published in the United States of America by

Information Science Reference (an imprint of IGI Global)

701 E. Chocolate Avenue

Hershey PA 17033

Tel: 717-533-8845

Fax: 717-533-8661

E-mail: [email protected]

Web site: http://www.igi-global.com

Copyright © 2014 by IGI Global. All rights reserved. No part of this publication may be reproduced, stored or distributed in

any form or by any means, electronic or mechanical, including photocopying, without written permission from the publisher.

Product or company names used in this set are for identification purposes only. Inclusion of the names of the products or

companies does not indicate a claim of ownership by IGI Global of the trademark or registered trademark.

Library of Congress Cataloging-in-Publication Data

British Cataloguing in Publication Data

A Cataloguing in Publication record for this book is available from the British Library.

All work contributed to this book is new, previously-unpublished material. The views expressed in this book are those of the

authors, but not necessarily of the publisher.

For electronic access to this publication, please contact: [email protected].

Kim, Sungwook.

Game theory applications in network design / by Sungwook Kim.

pages cm

Includes bibliographical references and index.

ISBN 978-1-4666-6050-2 (hardcover) -- ISBN 978-1-4666-6051-9 (ebook) -- ISBN 978-1-4666-6053-3 (print & perpetual

access) 1. Game theory. I. Title.

HB144.K56 2014

003’.72015193--dc23

2014007984

This book is published in the IGI Global book series Advances in Wireless Technologies and Telecommunication (AWTT)

(ISSN: 2327-3305; eISSN: 2327-3313)

Managing Director:

Production Editor:

Development Editor:

Acquisitions Editor:

Typesetter:

Cover Design:

Lindsay Johnston

Jennifer Yoder

Erin O’Dea

Kayla Wolfe

Christina Henning

Jason Mull

Advances in Wireless

Technologies and

Telecommunication (AWTT)

Book Series

• Cellular Networks

• Digital Communication

• Global Telecommunications

• Grid Communications

• Mobile Technology

• Mobile Web Services

• Network Management

• Virtual Network Operations

• Wireless Broadband

• Wireless Sensor Networks

Xiaoge Xu

The University of Nottingham Ningbo China

ISSN: 2327-3305

EISSN: 2327-3313

Mission

The wireless computing industry is constantly evolving, redesigning the waysin which individualsshare

information. Wireless technology and telecommunication remain one of the most important technolo￾gies in business organizations. The utilization of these technologies has enhanced business efficiency

by enabling dynamic resources in all aspects of society.

The Advances in Wireless Technologies and Telecommunication Book Series aims to provide

researchers and academic communities with quality research on the concepts and developments in the

wireless technology fields. Developers, engineers, students, research strategists, and IT managers will

find this series useful to gain insight into next generation wireless technologies and telecommunication.

Coverage

IGI Global is currently accepting manuscripts

for publication within this series. To submit a pro￾posal for a volume in this series, please contact our

AcquisitionEditors [email protected]

or visit: http://www.igi-global.com/publish/.

The Advancesin Wireless Technologies and Telecommunication (AWTT) Book Series(ISSN 2327-3305) is published by IGI Global, 701

E. Chocolate Avenue, Hershey, PA 17033-1240, USA, www.igi-global.com. This series is composed of titles available for purchase individu￾ally; each title is edited to be contextually exclusive from any other title within the series. For pricing and ordering information please visit

http://www.igi-global.com/book-series/advances-wireless-technologies-telecommunication-awtt/73684. Postmaster: Send all address changes

to above address. Copyright © 2014 IGI Global. All rights, including translation in other languages reserved by the publisher. No part of this

series may be reproduced or used in any form or by any means – graphics, electronic, or mechanical, including photocopying, recording, taping,

or information and retrieval systems – without written permission from the publisher, except for non commercial, educational use, including

classroom teaching purposes. The views expressed in this series are those of the authors, but not necessarily of IGI Global.

Titles in this Series

For a list of additional titles in this series, please visit: www.igi-global.com

Game Theory Applications in Network Design

Sungwook Kim (Sogang University, South Korea)

Information Science Reference • copyright 2014 • 543pp • H/C (ISBN: 9781466660502) • US $225.00 (our price)

Convergence of Broadband, Broadcast, and Cellular Network Technologies

Ramona Trestian (Middlesex University, UK) and Gabriel-Miro Muntean (Dublin City University, Ireland)

Information Science Reference • copyright 2014 • 333pp • H/C (ISBN: 9781466659780) • US $235.00 (our price)

Handbook of Research on Progressive Trends in Wireless Communications and Networking

M.A. Matin (Institut Teknologi Brunei, Brunei Darussalam)

Information Science Reference • copyright 2014 • 592pp • H/C (ISBN: 9781466651708) • US $380.00 (our price)

Broadband Wireless Access Networks for 4G Theory, Application, and Experimentation

Raul Aquino Santos (University of Colima, Mexico) Victor Rangel Licea (National Autonomous University of

Mexico, Mexico) and Arthur Edwards-Block (University of Colima, Mexico)

Information Science Reference • copyright 2014 • 452pp • H/C (ISBN: 9781466648883) • US $235.00 (our price)

Multidisciplinary Perspectives on Telecommunications, Wireless Systems, and Mobile Computing

Wen-Chen Hu (University of North Dakota, USA)

Information Science Reference • copyright 2014 • 305pp • H/C (ISBN: 9781466647152) • US $175.00 (our price)

Mobile Networks and Cloud Computing Convergence for Progressive Services and Applications

Joel J.P.C. Rodrigues (Instituto de Telecomunicações, University of Beira Interior, Portugal) Kai Lin (Dalian

University of Technology, China) and Jaime Lloret (Polytechnic University of Valencia, Spain)

Information Science Reference • copyright 2014 • 408pp • H/C (ISBN: 9781466647817) • US $180.00 (our price)

Research and Design Innovations for Mobile User Experience

Kerem Rızvanoğlu (Galatasaray University, Turkey) and Görkem Çetin (Turkcell, Turkey)

Information Science Reference • copyright 2014 • 377pp • H/C (ISBN: 9781466644465) • US $190.00 (our price)

Cognitive Radio Technology Applications for Wireless and Mobile Ad Hoc Networks

NatarajanMeghanathan(JacksonStateUniversity,USA) andYenumulaB.Reddy(GramblingStateUniversity,USA)

Information Science Reference • copyright 2013 • 370pp • H/C (ISBN: 9781466642218) • US $190.00 (our price)

701 E. Chocolate Ave., Hershey, PA 17033

Order online at www.igi-global.com or call 717-533-8845 x100

To place a standing order for titles released in this series, contact: [email protected]

Mon-Fri 8:00 am - 5:00 pm (est) or fax 24 hours a day 717-533-8661

Ad majorem Dei gloriam

Table of Contents

Preface .................................................................................................................................................... x

Acknowledgment ................................................................................................................................ xix

Quotes .................................................................................................................................................. xx

Section 1

Fundamental Ideas of Game Theory

Chapter 1

Introduction ............................................................................................................................................. 1

INTRODUCTION...........................................................................................................................................1

HISTORY OF GAME THEORY.....................................................................................................................2

APPLIED AREAS OF GAME THEORY.......................................................................................................5

Chapter 2

Basic Concepts for Game Theory ......................................................................................................... 21

INTRODUCTION.........................................................................................................................................21

CLASSIFICATIONS OF GAMES................................................................................................................24

CLASSIFICATION OF GAME SOLUTIONS.............................................................................................29

Chapter 3

Game Models in Various Applications ................................................................................................. 44

INTRODUCTION.........................................................................................................................................44

NON-COOPERATIVE GAMES...................................................................................................................44

COOPERATIVE GAMES.............................................................................................................................90

SPECIAL DOMAINS OF GAME THEORY..............................................................................................105

Section 2

Game Theoretic Applications for Network Management Issues

Chapter 4

Game Theory for Wireless Ad Hoc Networks .................................................................................... 130

INTRODUCTION.......................................................................................................................................130

PHYSICAL LAYER....................................................................................................................................131

DATA LINK LAYER...................................................................................................................................133

NETWORK LAYER...................................................................................................................................138

TRANSPORT LAYER................................................................................................................................141

APPLICATION LAYER..............................................................................................................................142

SUMMARY.................................................................................................................................................143

Chapter 5

Game Theory for Smart Grid .............................................................................................................. 146

INTRODUCTION.......................................................................................................................................146

GAME MODELS FOR DEMAND SIDE MANAGEMENT.....................................................................147

PRICING GAMES FOR SMART GRID LOAD BALANCING................................................................149

DYNAMIC GAMES FOR SMART GRID.................................................................................................151

ENERGY STORAGE MANAGEMENT IN SMART GRID......................................................................153

LEARNING BASED GAMES FOR SMART GRID..................................................................................154

SUMMARY.................................................................................................................................................155

Chapter 6

Game Theory for Network Security ................................................................................................... 158

INTRODUCTION.......................................................................................................................................158

NON-COOPERATIVE GAMES FOR NETWORK SECURITY...............................................................158

COOPERATIVE GAMES FOR NETWORK SECURITY.........................................................................165

MULTI-OBJECTIVE OPTIMIZATION FOR SECURITY GAMES.........................................................166

GAME THEORY FOR INFORMATION WARFARE................................................................................167

SUMMARY.................................................................................................................................................168

Chapter 7

Game Theory for Cognitive Radio Networks ..................................................................................... 172

INTRODUCTION.......................................................................................................................................172

NON-COOPERATIVE SPECTRUM SHARING GAMES........................................................................173

COOPERATIVE SPECTRUM SHARING GAMES FOR COGNITIVE RADIO NETWORKS..............178

ECONOMIC GAMES FOR COGNITIVE RADIO NETWORKS.............................................................180

SECURITY GAMES FOR COGNITIVE RADIO NETWORKS..............................................................183

SUMMARY.................................................................................................................................................184

Chapter 8

Game Theory for Wireless Network Resource Management ............................................................. 188

INTRODUCTION.......................................................................................................................................188

GAME MODELS FOR WLAN RESOURCE MANAGEMENT...............................................................188

GAME MODELS FOR CDMA NETWORK RESOURCE MANAGEMENT..........................................190

GAME MODELS FOR OFDM NETWORK RESOURCE MANAGEMENT..........................................192

GAME MODELS FOR CELLULAR NETWORKS RESOURCE MANAGEMENT..............................193

GAME MODELS FOR MULTI-HOP NETWORK RESOURCE MANAGEMENT................................195

GAME MODELS FOR SENSOR NETWORK ENERGY MANAGEMENT...........................................196

GAME MODELS FOR 4G WIRELESS NETWORK RESOURCE MANAGEMENT............................198

SUMMARY.................................................................................................................................................200

Section 3

Advanced Game Paradigm Topics:

Case Studies in Network Design

Chapter 9

Game-Based Approach for Network Routing Applications ................................................................ 205

COOPERATIVE GAME THEORETIC ONLINE ROUTING (CGOR) SCHEME...................................205

GAME THEORETIC MULTI-OBJECTIVE ROUTING (GMOR) SCHEME...........................................212

INCENTIVE-BASED AD-HOC NETWORK ROUTING (IANR) SCHEME...........................................218

COOPETITION GAME BASED MULTI-PATH ROUTING (CGMR) SCHEME FOR MOBILE

AD-HOC NETWORKS...........................................................................................................................227

TRUST BASED INCENTIVE COOPERATIVE RELAY ROUTING (TICRR) SCHEME FOR

WIRELESS NETWORKS.......................................................................................................................234

Chapter 10

Power Control Schemes Based on Game Theory ............................................................................... 244

EVOLUTIONARY GAME-BASED POWER CONTORL (EGPC) SCHEME.........................................244

STACKELBERG GAME-BASED POWER CONTORL (SGPC) SCHEME............................................251

DYNAMIC VOLTAGE SCALING (DVS) SCHEME.................................................................................255

WEIGHTED VOTING BASED POWER CONTROL (WVPC) SCHEME FOR FEMTOCELL

NETWORKS............................................................................................................................................259

INTERVENTION GAME BASED MULTI-OBJECTIVE POWER CONTROL (IGMPC)

SCHEME FOR FEMTOCELL NETWORKS..........................................................................................266

Chapter 11

Bargaining Solutions for Resource Allocation Problems ................................................................... 277

NASH BARGAINING BASED BANDWIDTH MANAGEMENT (NBBM) SCHEME...........................277

NASH BARGAINING BASED VOLTAGE SCALING (NBVS) SCHEME..............................................285

KALAI-SMORODINSKY BARGAINING BASED BANDWIDTH ADJUSTMENT (KSBBA)

SCHEME..................................................................................................................................................290

NEGOTIATION GAME BASED COOPERATIVE BANDWIDTH BARGAINING (NGCBB)

SCHEME..................................................................................................................................................294

BLOTTO GAME BASED STRATEGIC RESOURCE ALLCATION (BGSRA) SCHEME......................300

INTERVENIENT STACKELBERG GAME BASED BANDWIDTH ALLOCATION (ISGBA)

SCHEME..................................................................................................................................................304

Chapter 12

Bandwidth Management Algorithms by Using Game Models ........................................................... 311

QOS-AWARE BANDWIDTH ALLCATION (QSBA) SCHEME...............................................................311

ADAPTIVE CALL ADMISSION CONTROL (ACAC) SCHEME FOR HETEROGENEOUS

OVERLAY NETWORKS........................................................................................................................315

MECHANISM DESIGN BASED ONLINE BANDWIDTH ALLOCATION (MDOBA) SCHEME.........322

NEGOTIATION BARGAINING GAME BASED BANDWIDTH MANAGEMENT (NBGBM)

SCHEME FOR MULTI-HOP RELAYING NETWORKS......................................................................328

DUAL-LEVEL BANDWIDTH MANAGEMENT (DLBM) SCHEME FOR OVERLAY

NETWORKS............................................................................................................................................339

Chapter 13

Game-Based Control Mechanisms for Cognitive Radio Networks .................................................... 352

TWO-WAY MATCHING GAME BASED BANDWIDTH SHARING (TMGBS) SCHEME...................352

MULTI-LEADER MULTI-FOLLOWER STACKELBERG (MMS) SCHEME FOR COGNITIVE

RADIO NETWORKS..............................................................................................................................360

REVERSED STACKELBERG BANDWIDTH SHARING (RSBS) SCHEME FOR COGNITIVE

MULTI-HOP CELLULAR NETWORKS................................................................................................370

TRUST-BASED RADIO SPECTRUM SHARING (TRSS) SCHEME FOR COGNITIVE RADIO

NETWORKS............................................................................................................................................377

REPEATED BAYESIAN-BASED SPECTRUM AUCTION (RBSA) SCHEME FOR COGNITIVE

RADIO NETWORKS..............................................................................................................................381

LEARNING BASED SPECTRUM SHARING (LSS) SCHEME FOR COGNITIVE RADIO

NETWORKS............................................................................................................................................389

Chapter 14

Economic Approach for Network Management ................................................................................. 401

STACKELBERG GAME BASED PRICE CONTROL (SGPC) SCHEME FOR WIRELESS

NETWORKS............................................................................................................................................401

MARKET SHARING GAME BASED BANDWIDTH MANAGEMENT (MSGBM) SCHEME FOR

WIRELESS NETWORKS.......................................................................................................................407

BARGAINING AND FICTITIOUS PLAY BASED BANDWIDTH MANAGEMNET (BFPBM)

SCHEME FOR WIRELESS NETWORKS.............................................................................................413

PUBLIC GOODS GAME BASED FILE SHARING (PGGFS) SCHEME FOR P2P NETWORKS........418

Chapter 15

Game-Based Control Approach for Smart Grid .................................................................................. 429

BIFORM GAME BASED COGNITIVE RADIO CONTROL (BGCRC) SCHEME FOR SMART

GRID COMMUNICATIONS...................................................................................................................429

SPECTRUM MANAGEMENT ALGORITHMS IN THE BGCRC SCHEME..........................................430

COOPETITION GAME BASED GROUPING AND SCHEDULING (CGGS) SCHEME FOR

SMART GRID MANAGEMENT............................................................................................................435

Chapter 16

Game Paradigm for Wired Networks .................................................................................................. 447

EVOLUTIONARY MINORITY GAME BASED CONGESTION CONTROL (EMGCC)

SCHEME FOR WIRED NETWORKS....................................................................................................447

RELATED WORK......................................................................................................................................449

THE MAIN STEPS OF THE EMGCC SCHEME......................................................................................452

SUMMARY.................................................................................................................................................453

Chapter 17

Concluding Remarks ........................................................................................................................... 455

READING LISTS FOR KEY ISSUES IN GAME THEORY.....................................................................455

DIRECTIONS FOR FUTURE RESERACH..............................................................................................466

Compilation of References ............................................................................................................... 470

About the Author .............................................................................................................................. 494

Index .................................................................................................................................................495

x

Preface

Network Design with its many variants is one of the most active research areas. In addition, new problems

in this area are constantly propounded by practitioners working in different aspects of network design

such as construction, routing, and staged deployment. Furthermore, many new design paradigms such

as ATM, ad-hoc, and telecommunications add rich new flavors to existing problems. Including mobile

cellular networks and ad-hoc wireless networks, future generation networks will most likely consist of

intelligent devices capable of sensing the environment and effectively adjusting their transmission pa￾rameters according to the current network conditions and QoS specifications. These devices will oppor￾tunistically use the network resource while selecting the transmission rates, transmission powers, access

method, route to final destination for a multi-hop network, etc. This mechanism will greatly influence

the performance of all the other users in the network. In addition, most of today’s networks are large￾scale with lack of access to centralized information, consist of users with diverse requirements, and are

subject to dynamic changes. These factors naturally motivate a new distributed control paradigm, where

the network infrastructure is kept simple and the network control functions are delegated to individual

agents, which make their decisions independently. The interactions among devices sharing a common

network resource can be formally modeled as games. The outcome of these games and consequently

the overall network performance can be predicted using a game theoretic formulation. Therefore, the

interaction of multiple selfish decision-makers necessitates the use of game theory.

Game theory is a mathematical framework to analyze complex interactions of cooperative or com￾peting decision makers taking into account their preferences and requirements. The origins of game

theory go far back to the so called marriage contract problem in Babylonian times (in the early years of

the first millennium). Recent work suggests that the division of an inheritance described in the Talmud

predicts the modern theory of cooperative games. Relatively new, in 1713, James Waldegrave wrote

out a strategy for a card game that provided the first known solution to a two-player game. Despite

these early efforts and many other contributors in the history of game theory, it is widely accepted that

the origin of the formal study of game theory began with John von Neumann and Oskar Morgenstern’s

book, Theory of Games and Economic Behavior (published in 1944). This pioneering work focused on

finding unique strategies that allowed players to minimize their maximum losses by considering, for

every possible strategy of their own, all the possible responses of other players. During the 1940s, game

theory emerged from the fields of mathematics and economics to provide a revolutionary new method

of analysis. Therefore, originally, game theory was invented to explain complicated economic behavior.

The golden age of game theory occurred in the 1950s and 1960s when researchers focused on finding

sets of strategies, known as equilibria, to solve a game if all players behaved rationally. The most famous

of these is the Nash equilibrium proposed by John Nash. Nash also made significant contributions to

xi

bargaining theory and examined cooperative games where threats and promises are fully binding and

enforceable. Today game theory provides a language for discussing conflict and cooperation. With its

effectiveness in studying complex dynamics among players, game theory has been widely applied in

economics, political science (e.g., voter behavior), sociology (network games), law (antitrust), computer

science (defending networks against attacks), military science, biology (evolutionary strategies), pure

philosophy, with occasional appearances in psychology, religion (recall Aumann’s Talmud paper), physics

(quantum games), telecommunications, logistics, etc. In these fields, game theory has been employed

to achieve socially optimal equilibrium.

Nowadays, game theory has been widely recognized as an important tool in the research area of net￾work design. A promising potential application of game theory in communication networks is the area

of congestion control, network routing, load balancing, multi-commodity flow, resource allocation, and

quality of service provisioning. Intensive research work has also been devoted to game models in wireless

mobile networks. Some of the main issues are power control, bandwidth pricing, incentive mechanism

for cooperation between mobile nodes, resource sharing, the access control to a common radio channel,

and auctions for wireless bandwidth. In addition, new problems are constantly propounded in various

areas such as network security and software engineering. In recent years, these issues have become an

increasingly important part of network design.

In applying game theory for wireless communications and networking, wide application examples

can be efficiently addressed. The applications are mainly motivated by the inherent characteristics of

wireless systems. First, wireless bandwidth is very scarce and limited resource in communications. With

the increasing number of wireless access terminals, wireless bandwidth scarcity and hence competition

among mobile users becomes more severe. This competition for limited resources closely matches with

the concept of game theory. Second, the wireless network systems become more complicated with respect

to network size, protocol heterogeneity, QoS sensitive multimedia services, and dynamic interactions.

In such issues, game theory is able to significantly help better understand the complex interactions and

design more efficient, scalable, and robust protocols. Third, the current-generation wireless systems

can provide mobile users with high-speed data services at rates substantially higher than those of the

previous generation. As a result, the demand for mobile information services with high reliability, fast

response times, and ubiquitous connectivity continues to increase rapidly. Therefore, the effectiveness

of network performance has become critically important both in terms of practical utility and commer￾cial viability, and presents a rich area for research. This demands intelligent network management and

operation, which may well be solved within the game theoretical framework.

Game theory hopefully will lead to new collaborative research initiatives and help advance the state￾of-the-art. The goal of this book is to focus on the active area of applications of game theory to understand

current trends, identify understudied areas, and formulate new directions for further investigation. To

satisfy this goal, this book will present an introduction on game theory with an emphasis on applications

for network design issues. The first section of this book introduces the fundamental concepts of game

theory, while the second section explores application fields of game theory, including wireless ad-hoc

networks, smart grid, network security, cognitive radio, and network resource management. Finally, the

last section of this book discusses advanced applications in network design such as power control, access

control, bandwidth adaptation, routing, and game theoretic solutions for the network management. These

three sections will be valuable to professionals in the field and researchers in other areas who want an

introduction to current game theoretic research frontiers in network design. This book is descriptive and

adopts an algorithmic approach. It assumes that readers have some familiarity with algorithms, computer

xii

networks, and telecommunications. The unique feature of this book is that it gives algorithmic treatment

to all the issues addressed and highlights the intuition behind each of the algorithms presented.

This book specifically treats the recent research and the use of game theoretic techniques that are

playing particularly important and distinctive roles in the network design domain. An important com￾ponent of this book is examples of algorithms, which will give the readers the opportunity to clearly

understand to get game theoretic solutions for specific network design issues. The content provided in

this book should help readers understand the necessary background, concepts, and principles in using

game theory approaches. Therefore, this book is useful for undergraduate and graduate students in com￾puter science and information technology disciplines. In particular, this book can serve as an essential

reference for students, educators, research strategists, scientists, researchers, and engineers in the field

of network design.

OUTLINE OF THE BOOK

The key challenge in this book is to provide the basic idea of game theory and fundamental understanding

the game theoretic interactions among network entities. The research presented in this book focuses on

modeling, analyzing, and solving the network design problems. There are two main ways to capitalize

game theory in network design. One approach is used to analyze existing systems. After a game model

is developed, it can be used to investigate the properties of the systems. The other approach is used to

design a new system. Instead of fixing a game and analyzing its outcome, game theory is adopted to

get the desired outcome. When a suitable game model is discovered, a system can obtain the properties

that are looked for. Nowadays, a lot of models for network design problems have been proposed based

on the game theory paradigm.

To provide a didactic approach for studying game theory, this book is organized in three sections. In

section 1, we will study the fundamental ideas of game theory. Before we discuss how to apply game

theory in different network design problems, the choice of a design technique is crucial and must be

emphasized. Therefore, this section presents game theory history, different game models, and solution

concepts that can be applied to the design, implementation, and analysis of network design problems. In

addition to the explanation of the basic principles, we will also illustrate the limitations and trade-offs

of different approaches.

The chapters in section 1 cover the fundamental ideas of game theory. In chapter 1, game theory

history and approaches are surveyed. Even though game theory can be traced back to ancient China, the

mathematical theory of games was developed in the 1940s. At that time, John Nash transformed game

theory into a more general tool that enabled the analysis of win-win and lose-lose scenarios, as well

as win-lose situations. In the 1950s-1970s, game theory was developed extensively by many scholars.

Lots of game theorists have won Nobel prizes in economics, and John Maynard Smith was awarded the

Crafoord Prize for his application of game theory to biology. Nowadays, game theory is used in the social

science, economics, biology, engineering, political science, international relations, computer science, and

philosophy. In this chapter, game theory applications in various academic fields are briefly presented.

In chapter 2, basic concepts for game theory and game model classification are introduced. Games

are classified various criteria as non-cooperative games vs. cooperative games, static games vs. dynamic

games, discrete games vs. continuous games, zero-sum games vs. non zero-sum games, n-player games

vs. population games, perfect information games vs. imperfect information games, complete informa-

xiii

tion games vs. incomplete information games, pure strategy games vs. mixed strategy games, unitary

games vs. hybrid games, egalitarian games vs. hierarchical games, or symmetric games vs. asymmetric

games. In addition, famous game solutions are introduced. Solutions for non-cooperative games are

Nash equilibrium, Pareto equilibrium, Subgame Perfect Nash equilibrium, Bayesian-Nash equilibrium,

-equilibrium, correlated equilibrium, Wardrop equilibrium, and evolutionary stable strategy. Solutions

for cooperative games are Pareto optimality, Core, Shapley Value, the nucleolus, Nash bargaining solu￾tion, Kalai-Smorodinsky bargaining solution, egalitarian bargaining solution, and Rubinstein bargaining

solution. All the issues are covered in chapter 2.

In chapter 3, various game models are presented. As non-cooperative games, static game, dynamic

game, sequential game, repeated game, stochastic game, jamming game, potential game, congestion

game, Stackelberg game, differential game, Bayesian game, evolutionary game, supermodular game,

global game, signaling game, intervention game, negotiation game, minority game, jamming game, and

dictator game are explained. As cooperative games, coalitional game, coalition formation game, canoni￾cal coalition game, matching game, voting game, and bargaining games, such as Nash bargaining game,

Kalai-Smorodinsky bargaining game, Rubinstein bargaining game, are introduced. Special domain of

game theory, hybrid games, such as coopetition game and biform game, and reverse game theory, auc￾tion game, metagames, and modified game theory are presented.

Section 2 explores application fields of game theory, including wireless ad-hoc networks, smart grid,

network security, cognitive radio, and network resource management. The purpose of this section is to

study existing game models applied in the field of network design. Through this section, readers can

find that game theory is tightly related to network design problems. Using game theory, existing network

control approaches cannot only achieve the goal of the flexibility of network resource management and

the higher utilization but also greatly facilitate the adjustment of working conditions. Until now, the

applications were still in the initial stage of theoretical research; more in-depth research on the game

theory in a variety of equilibrium and development of the application of new models are needed in order

to ensure a more efficient and flexible network management. From section 2, readers can gain better

understanding the existing game theoretic approaches for network design problems and some insights

on further research directions.

Chapter 4 provides a tutorial survey and overview of the most recent practical implementations for

wireless ad hoc networks. For ad hoc networks, game theory can offer an effective tool to model adapta￾tions that may occur at different layers and also has a strong role to play in the development and analysis

of protocols. This chapter shows that game theory can play a significant role to model adaptations that

may occur at different layers in wireless ad hoc networks.

Chapter 5 presents game-theoretic approaches for the analysis of smart grid systems. Smart grid is a

modernized electrical grid that uses information and communications technology to gather and act on

information, such as information about the behaviors of suppliers and consumers, in an automated fashion

to improve the efficiency, reliability, economics, and sustainability of the production and distribution of

electricity. Since game theory has strong potential for the analysis of smart grid systems, game-theoretic

approach presents a promising tool to address several emerging problems in SG systems.

Chapter 6 provides an overview and classifications of existing game theoretic approaches to network

security. Network security involves the authorization of access to data in a network, which is controlled

by the network administrator. Network security covers a variety of computer networks, both public and

private, that are used in everyday jobs conducting transactions and communications among businesses,

government agencies, and individuals. This survey highlights important game theoretic applications to

network security.

xiv

In chapter 7, we classify state-of-the-art game theoretic research contributions on cognitive radio

networks and provide a comprehensive overview of game models. A cognitive radio is a transceiver

designed to use the best wireless channels in its vicinity. Such a radio automatically detects available

channels in wireless spectrum, then accordingly changes its transmission or reception parameters to al￾low more concurrent wireless communications in a given spectrum band at one location. This process

is a form of dynamic spectrum management. By using game theory, the spectrum sharing mechanism

can achieve the higher spectrum utilization in cognitive radio networks.

Chapter 8 provides a tutorial overview on game theoretic approaches for the network resource

management issues with the most recent practical implementations. Network resource management is

one of the most challenging and important aspects of network design to significantly improve network

performance. However, a proper understanding of a resource management algorithm often requires an

understanding of a number of complex interrelated processes. In this chapter, we classify state-of-the-art

research contributions on the network resource management and discuss the fundamental concepts and

properties to explain on how to apply the game theory.

In section 3, each chapter covers the advanced game models developed for network design problems.

This section deals with the case study of modeling, design, and analysis of game-theoretic schemes in

communications and networking areas. Different game models have been applied to solve a diverse set

of network design problems. In addition, under different practical constraints, some applications for dif￾ferent network scenarios are given as examples. By considering the technical challenges of a variety of

networks, we will show how to employ different game models for different scenarios in cellular networks,

wireless networks, ad-hoc and sensor networks, femto-cell networks, and wired communication networks.

In chapter 9, game-based network routing schemes are introduced; Cooperative Game Theoretic Online

Routing (CGOR) scheme, Game Theoretic Multi-Objective Routing (GMOR) scheme, Incentive-Based

Ad-Hoc Network Routing (IANR) scheme, Coopetition Game-Based Multi-Path Routing (CGMR) scheme,

and Trust-Based Incentive Cooperative Relay Routing (TICRR) scheme are explained in detail. In the

CGOR scheme, adaptive online path setup and packet distribution algorithms are developed for wireless

networks. The most important feature of the CGOR scheme is the integrated approach by employing a

coordination paradigm to provide the energy efficiency and network stability during network operations.

The GMOR scheme is a new game-theoretic routing scheme for sensor networks. The IANR scheme is

designed as an adaptive online routing scheme by using an incentive-based model. In the IANR scheme,

new path-setup, incentive-computing, and reservation algorithms are developed. For practical network

operations, these developed algorithms are designed in a self-organizing, dynamically online, and dis￾tributed fashion to work together in a coordinated manner. The CGMR scheme is designed based on the

coopetition game model and simulated annealing approach. In the CGMR scheme, wireless nodes are

assumed as self-interested game players and make local decisions in a distributed manner. Therefore,

routing packets are adaptively distributed through multiple paths in pursuit of the main goals such as

load balancing and network reliability. For wireless networks, the TICRR scheme can take into account

the measure of the probability of a relay node succeeding at a given relay service and maximize the

network performance. By considering the current network condition, the TICRR scheme can select the

most adaptable relay node and pay the incentive-price for relay service.

In chapter 10, power control schemes based on game theory are introduced; Evolutionary Game￾Based Power Control (EGPC) scheme, Stackelberg Game-Based Power Control (SGPC) scheme, Dy￾namic Voltage Scaling (DVS) scheme, Weighted Voting-Based Power Control (WVPC) scheme, and

Intervention Game-Based Multi-Objective Power Control (IGMPC) scheme are explained in detail. The