03964.com

文档资料库 文档搜索专家

文档资料库 文档搜索专家

INTERNATIONAL J OURNAL OF M ULTIDISCIPLINARY S CIENCES AND ENGINEERING, VOL . 3, NO. 4, APRIL 2012

An Overview of Game Theory and its Applications in Communication Networks

I. A. Shah, S. Jan, I. Khan and S. Qamar

Abstract—Due to its capability to solve the situations of conflict and competition, Game Theory has been used as a mathematical tool in economics, politics, biology and human psychology. Nash Equilibrium, being the solution of a non-cooperative game, gives a stable state in a sense that no agent/player have any positive incentive to deviate from its current adopted strategy, when all others players of the game stick to their current moves. The Pareto Efficiency is the solution of a game where the utility gained by a player by deviating from the current strategy causes at least one other player worst off. In Communication Networks, the cooperation to follow a certain protocol cannot be taken as for granted, keeping in view the selfish nature of now a day’s network entities. To cope with the selfish and competitive behavior of the network entities, Game Theory provides a feasible solution for resource utilization and service provisioning. This paper presents the detailed overview of the Game Theory concepts and its applications in the Communication Networks, both from cooperative and non-cooperative perspectives. Keywords—Game Theory, Nash Equilibrium, Cooperative Games, Non-Cooperative Games and Communication Networks

I. INTRODUCTION ame Theory [1-3] is the study of mathematical models, which are used in a situation when multiple entities interact with each other in a strategic setup. The theory in its true sense deals with the ability of an entity or individual (called player in Game Theory) to take a certain decision keeping in view the effect of other entities decisions on him, in a situation of confrontation. A wage negotiation between a firm and its employees can be considered as a game between two parties, where each party makes a decision or move in the negotiation process based on other party’s move. Similarly, a business run by a group of people can be considered as a game played against its competitors or customers. The concept of modern Game Theory was introduced by John Von Neumann and Oskar Morgenstern [4] in 1944, who described the word ‘game’ for the first time by systematically specifying the rules of the game, the move of players, the information they possess during their moves and the outcome for each player at the end of the game [5]. They are considered

I. A. Shah is with University of Engineering and Technology, Mardan Campus, Khyber Pakhtunkhwa Pakistan; e-mail: ibrar @ nwfpuet.edu.pk. S. Jan is with University of Engineering and Technology, Mardan Campus, Khyber Pakhtunkhwa Pakistan; e-mail: sadaqat@ nwfpuet.edu.pk. I. Khan is with University of Engineering and Technology, Mardan Campus, Khyber Pakhtunkhwa Pakistan; e-mail: imrankhan@ nwfpuet.edu.pk. S. Qamar is with King Abdulaziz University, North Jeddah Branch Saudi Arabia; e-mail: sqamar@kau.edu.sa

G

the pioneers of modern Game Theory who modeled the economic situations as decision mathematics models for the first time and presented it as a static game, where individuals come into contact only once. Their models were successfully used in economics in later years. In 1950, John McDonalds [6] published his famous book “Strategy in Poker, Business and War”, where he demonstrated the use of strategic interaction in the real world environments. Game Theory took a revolutionary leap when John Nash presented the models for non-cooperative games in 1951 [7]. His proposed solution for non-cooperative games, later on called Nash Equilibrium, is still considered as a standard for any conflicting situation’s outcome. R. Luce and H. Raiffa [9], [10] introduced the concept of incomplete information in games in 1957, where they argued that it is not necessary that the participants of a game are fully aware about the rules under which they play and about the utility functions of other players. The cooperative games were introduced by Harsanyi [11] in 1960, where he argued that the commitments (i.e. threats, punishments, agreements) in a game are enforceable. The progress of Game Theory continued since its inception and later on was used in many other fields other than economics. Game Theory has now become an important mathematical tool, which is used in situations that involves several entities whose decisions are influenced by the decisions of other entities playing with them. Any game, when played, consists of the participants called players or agents of the game, each having his own preference or goal. Each player of the game has an associated amount of benefit or gain which he receives at the end of the game, called payoff or utility, which measure the degree of satisfaction an individual player derives from the conflicting situation. For each player of the game, the choices available to them are called strategies. The solution of a game is referred to as Nash Equilibrium or Strategic Equilibrium, where each player cannot get a better payoff than the existing one by individually changing to another strategy. The utility function is a mapping of a player’s choices into a real number [1]. To understand the concepts presented so for, refer to Table 1, where two players P1 and P2 come in a strategic interaction to play this game. For ease, the game is represented by a matrix, called payoff matrix, which shows the choices available to players and the outcome for each choice he makes against the others. As shown in the payoff matrix of the game between P1 and P2, each have to decide either to choose X or Y. The setup is strategic, so the choice of individual player’s payoff depends on the choice made by other player as a response to his strategy. If player P1 chooses X, then his payoff depends upon 5

[ISSN: 2045-7057]

www.ijmse.org

INTERNATIONAL J OURNAL OF M ULTIDISCIPLINARY S CIENCES AND ENGINEERING, VOL . 3, NO. 4, APRIL 2012

which choice the player P2 makes. If P1 choose X and P2 also chooses X, P1 payoff will be 2, otherwise 10. Similarly, if P1 chooses the Y, then depending upon the choice of P2 he will either receive 10 or 3. The same choices and outcome will happen for player P2 as well. Here in this game, the players are P1 and P2, the strategies for each are X and Y and the benefits or outcome of the game are represented in the form of matrix where each entry shows the payoffs in the form (payoff of P1, payoff of P2) duple. The numerical outcome for each player depends on the utility function used by each in the situation in which this game is played.

? ? ?

If both suspects confess the crime, each will serve in jail for ten years. If both deny the crime, both will serve in jail for 3 years. If one confess and the other deny, the confessor will be set free and the denier will be sent to jail for 15 years.

The choices available to the suspects and their corresponding outcomes when they play this game are given in the Table 2. Suspect 1 Confess (10,10) (15,0) Deny (0,15) (3,3)

P2 X (2,8) (5,10) Y (10,5) (3,3)

Suspect 2

Confess Deny

P1

Table 2: Prisoners’ Dilemma

X Y

Table 1: Strategic form of a game

Formally, a game can be defined [1] as consisting of a non-empty finite set of N= {N1, N2, … .., N|N|} players, a complete set of actions/strategies Ai={a1,a2,…a|Ai|} for each Ni ? ??N. A set of all strategies space of all players, represented by the matrix A=A1xA2x…xA|N|. A(ai,a-i) is a strategy profile when a player Ni ???N selects an action ai from its action set Ai against the actions of all other players N-i. The subscripted notation –i is a convenient way to represent a set of entities or set of events excluding a specific entity or event in a strategic setup. For example N-i means set of all players excluding Ni and a-i means set of actions of all players excluding the action of the player Ni during a strategic interaction. At the end of the game, each player Ni ???N gets benefit in the form of a real number (R) called payoff of the player which is determined by the utility function Ui as: Ui=Ai ? R. The rest of the paper is organized as follows: Section II presents two important games in game theory. Section III discusses the solution concepts of game theory with examples. This section also gives a brief overview of pure and mixed strategy Nash Equilibrium. Section IV gives the introduction to the various types of games in detail. Section V outlines the use of game theory in communication networks at different layers of the protocol stack. Finally, in Section V we conclude this paper. II. EXAMPLES OF GAMES A. Prisoners’ Dilemma The well known game of Prisoner’s Dilemma was presented by Professor Tucker of Princeton University in 1950 [12], [13]. This game depicts an imaginary situation where two persons are arrested under the suspicion of their involvement in a crime. The police place both the suspects in separate rooms so they are not able to communicate with each other during the interrogation process. Each suspect is informed of the following payoffs based on their strategies, separately:

Prisoner’s Dilemma is an example of simultaneous move game and the solution lies in one of the concept of Game Theory called dominant strategy. The game is solvable and both players will be better off, if they opt for the (Deny, Deny) strategy giving both a maximum payoff of 3 years jail sentence. Since both players of the game are unaware of the decision of each other due to no communication and therefore no cooperation is possible in this case. To solve this game, each player has to weight the possible outcome of his strategies as well as the opponent’s decisions in this game. Considering the above game in the Suspect 1 prospective, the possible payoffs for his difference strategies are: (Confess, Confess) = 10 years, (Confess, Deny) = 0 years, (Deny, Confess) = 15 years, (Deny, Deny) =3 years. By a method call Cell-by-Cell Inspection, Confess seems the best strategy to be played by Suspect 1, irrespective of the Suspect 2’s strategies. In Game Theory’s terminology, such a strategy is called the dominant strategy or best response and is defined as the strategy of a player which earns him the larger payoff than any other strategies, irrespective of the strategies played by other players in a game. All other strategies are called dominated strategies. In the game above, Suspect 1 will always go for Confess, irrespective of suspect 2 decisions. Similarly, in the prospective of Suspect 2, Confess is the dominant strategy; irrespective of Suspect 1’s adopted strategies. Assuming that both players are rational, the solution of this game is (Confess, Confess) i.e., both players play their dominant strategies. B. Battle of the Sexes Another famous game in the field of Game Theory is called the Battle of the Sexes and was introduced by R. Duncan Luce and Howard Raiffa [9] in 1957. The game is played between a wife and husband and both have to decide between two independent and simultaneous accruing events to attend. The game assumes that there are two events, a football match and a musical concert, and both the husband and wife have different payoffs from each. The payoff matrix and the strategy set for each player is shown in the Table 3. By looking at the strategy matrix of the Table 3, none of the players would like to end up attending an event alone so (Football, Music) and (Music, Football) are two unacceptable outcomes in both player’s prospective. However, husband 6

[ISSN: 2045-7057]

www.ijmse.org

INTERNATIONAL J OURNAL OF M ULTIDISCIPLINARY S CIENCES AND ENGINEERING, VOL . 3, NO. 4, APRIL 2012

prefers Football more than Music based on his utility function while the wife has high preference for Music based on her Wife Football (3,1) (0,0) Music (0,0) (1,3)

??????? ? ? ?????? ? ? i ∈ N, ? A' i ∈ A And for any j ∈ N, for any A ' j ∈ A: ??????? ? ? ?????? ? C. Pure and Mixed Strategy Nash Equilibrium

(2) (3)

Husband

Football Music

Table 3: Battle of the Sexes

utility function. In this particular game, there is no dominant strategy for both players and hence the solution space is either (Football, Football) or (Music, Music). This particular example shows that a game might have more than one solutions i.e., multiple Nash Equilibriums. III. SOLUTION CONCEPTS IN GAME THEORY A. Nash Equilibrium Definition: Nash Equilibrium [7] for any game is the set of strategies of all players, called the strategy profile, where no player can increase its payoff by changing his current strategy, assuming that all other players keep their current strategies intact. Mathematically, a Nash Equilibrium of a game is the strategy profile A of all players such that: (1) U i ( A i , A ? i ) ≥ U i ( A ' i, A ? i ) ? i ∈ N, ? A' i ∈ A Where Ai is the current strategy of player i against all other strategies of other players (A-i). A’i are all other strategies of player i. This simply means that a strategy profile A (combined strategies of all the players) will be a Nash Equilibrium if and only if the condition in the Equation (1) holds for all the players. In the examples given in the Sections III (A) and III (B), (Confess, Confess) is the Nash Equilibrium for the Prisoner’s Dilemma game while (Football, Football) and (Music, Music) are the Nash Equilibriums for the Battle of the Sexes game. In the case of all other outcomes in the given games, players can deviate from their current strategies to increase their payoffs and hence they are not accepted as the Nash Equilibriums. B. Pareto Efficiency Definition: Pareto Efficiency or Pareto Optimality, named after Vilfredo Pareto, is defined as “A situation is said to be Pareto efficient if there is no way to rearrange things to make at least one person better off without making anyone worse off” [14]. Pareto Efficiency is the measures the performance a game outcome. If such a strategy exists in a game, where any single player can increase his payoff by changing his current strategy without hurting the payoffs of other players, then the outcome is not Pareto Efficient. In other words, in a Pareto Efficient outcome of a game, every player stick to the current strategy and if a single deviation of a player can increase his payoff, it will definitely harm the payoff of other players in the game. It is not always necessary that a Nash Equilibrium outcome of a game be the Pareto Efficient one. Mathematically, a strategy profile A will be Pareto Efficient if and only if there is no such other profiles Ai’ and A’j, such that for any players i, j:

When players are playing a game, the strategies can be pure or mixed. In a pure strategy game, all the players are taking moves in discrete values. This means that all the players have are playing with a probability of one on all of their set of strategies. Refer to the example game in the Section III (A) again with different payoff values as given in the Table 4, with two players P1 and P2. The set of strategies for both are {X ,Y}. If both players pick X or Y discretely during the play of a game, then their strategies are called pure and the equilibrium in such a case is called pure strategy Nash Equilibrium. However, in some situations players don’t always play with pure strategies. For example if the game shown in the Table 4 is repeated for multiple times, it is possible that in some stages of the game, the players might decide to randomize their strategies by picking multiple strategies from their strategies set with some probabilities. By definition, a game is called of mixed strategy when the players randomize their moves over the set of pure strategies and the outcome of the game is called mixed strategy Nash Equilibrium [15]. Let us assume that player P1 picks X with a probability of 0.7 times and Y with a probability of 0.3 times. It is assumed that player P2 play with pure strategies, either X or Y. For this game, the player P1 will have an expected payoff for playing X or Y in terms of player P1 ‘s randomization. i.e: Expected payoff of P2 for playing X= [(2*0.7)+(2*0.3)=2] and for playing Y=[(3*0.7)+(1*0.3)=2.4]. P2 X P1 X(probability=0.7) Y(probability=0.3) (2,2) (4,2) Y (1,3) (0,1)

Table 4: Mixed Strategy Nash Equilibrium

The mixed strategies are normally used in the repeated games where players know the history of each other’s preference over the strategy set. There might be situation that a player plays with mixed strategy when he is indifferent towards his all pure strategies or when the game is of a pure guess or when the players can guess the next move of each other [1]. There might be a situation for a player to play with mixed strategies, when the strategies available to it are not dominated by each other in his own set of choices. There might be the situations where a pure strategy game does not converge to the Nash Equilibrium. The mixed strategy games always have a Nash Equilibrium solution. In order to calculate the expected utilities in mixed strategies applied by the players of the Battle of the Sexes game, lets assume that the women want to go to music and football events equally likely as shown in the Table 5. For this 7

[ISSN: 2045-7057]

www.ijmse.org

INTERNATIONAL J OURNAL OF M ULTIDISCIPLINARY S CIENCES AND ENGINEERING, VOL . 3, NO. 4, APRIL 2012

assumption, let the husband want to randomize his move over his pure strategies by 1/3 and 2/3 i.e., he will want 1/3 of the time to go to music event and 2/3 of the time to go to the football event. The expected utilities of wife in terms of the mixed strategies of her husband can be calculated as follows: ??????? ? ? ???????????, ?? ? ? ? ??? ??????? ??? ? ? ?1 ? ?? ??????? ??? ? ??????? ? ? ????????, ?? ? ? ? ??? ??????? ??? ? ? ?1 ? ?? ??????? ??? ?

(4)

towards the game depends on the actions of other agents in the game [17]. Most of the problems in Communication Networks have been modeled as non-cooperative games, where each node is considered to be a selfish self maximizer without taking care of the benefit of other nodes in a conflicting situation. However, there are some studies where the coalitions games have been modeled to study the individual nodes behavior in a network each contributing to a coalition [17]. B. Sequential and Simultaneous Move Games Those games where the players take their decisions sequentially are called sequential move or extensive games. The basic characteristic of these games is that the players are aware about the strategies of other players and the moves are observable. The sequential move games involve strategic interaction where there is a very strict order of play and the players take turns during making their decisions. Each player has the knowledge about the decision of a player who moves ahead of him. Such games require strategic interaction in terms of a player’s current move effects on the future move and this adds to help every player to calculate his current strategy. The game of chess is an example of sequential move games. These games are solved with decision tree or game tree. The sequential games can be one shot or repeated [18]. In the simultaneous or strategic move games, players are unaware of the other player’s strategies ahead of time and the moves are simultaneous in that sense. The information about other players selection of a strategy over his strategy profile is not known to other players but it is assumed that the list of the strategies might be known. In these type of games each player thinks strategically not only about their own best response but also the best responses of other players in the game. Normally, the simultaneous move games are represented by the game matrix or payoff matrix. Prisoner’s Dilemma and the Battle of the Sexes are the example of simultaneous move games. C. Zero-Sum and Non-Zero Sum Games A game is called Zero-Sum where the total payoffs of all the players are equal to zero at the end of the game. These are the games which present the total win-total loss of players in a game. These are strictly competitive games where the player’s interaction is in complete conflict. Many games are Zero-Sum e.g., in all sport games; one team or individual’s win (+1) is the loss (-1) of the other team or individual. In the Non-Zero sum game, every player gets some share of the total benefit or some loss at the end of the game. There is no total loss and the competition is not that much strict as of the Zero-Sum games. The basic difference between these two games is that in ZeroSum games, the players have no common interests and in Non-Zero-Sum games, players have conflicting and sometimes common interests. These types of games are very common in most economic activities and trading. D. Games with Perfect and Imperfect Information When each player knows exactly about all the decision of other players during his turn, the type of game is called a game with complete information. For example, all the sequential

(5)

Where E(U)Mw is the expected value of wife’s payoff when the husband is going to the music event 1/3(?) times in the game. Similarly E(U)Fw is the expected payoff of wife when the husband is going (1- ? ) times to the football match. payoff w M is the wife payoff in pure strategies when her husband is opting for music event. Similarly, the wife can also randomize her moves over her pure strategies and husband can derive his expected value of utility from the game of mixed strategies. Wife Football(1/3) (3,1) (0,0) Music(2/3) (0,0) (1,3)

Husband

Football(2/3) Music(1/3)

Table 5: Battle of the Sexes with Mixed Strategy

IV. GAMES TYPES Depending on the player’s knowledge about each other’s strategies, payoffs, and past histories; games can be subdivided into different categories. Depending upon the number of players, a game can be classified as 2-player game or n-players where n>2. Depending upon the cooperation level, information available and the occurring of moves of the individual players the games can be broadly categorized as follows. A. Non-Cooperative and Cooperative Games In non-cooperative games, each participant player acts in his own interest and the unit of analysis is always the individual player instead of group of players. In these types of games, the players are always selfish – i.e., they always try to increase their own individual payoffs without taking care of other player’s payoffs in the game. So, non-cooperative game theory studies the competitive nature of individual players where players come into contact with the sole aim to increase their own benefits from the strategic situation [16]. In cooperative games, the groups of players are the unit of analysis and the players tend to increase their group payoffs as well as their own. A cooperative game can be considered as a competition among the groups in a game rather than individual players. The applications of cooperative game theoretical models are in the situations where players form groups, called coalitions, and the individual or group of player’s contribution

[ISSN: 2045-7057]

www.ijmse.org

8

INTERNATIONAL J OURNAL OF M ULTIDISCIPLINARY S CIENCES AND ENGINEERING, VOL . 3, NO. 4, APRIL 2012

games are games of complete information. In other cases, when there is no information about other players past strategies then the game is called of imperfect information. All simultaneous move games are games of imperfect information. For example the games presented in the Sections III (A) and III (B) (The Prisoner’s Dilemma and the Battle of the Sexes) are the games of incomplete information. E. Games with Complete and Incomplete Information When all the factors of the game are the common knowledge to all the participant players, such games are called games with complete information. The information in the game is symmetric and each player equally knows about other player’s strategies and payoffs associated with those strategies in these players prospective. The complete information games are perfectly competitive and the moves of the players are extremely strategic and calculated. The games where the knowledge of players regarding each other strategies and payoffs is limited are called games of incomplete information. These games can further be categorized as games of symmetric incomplete information or games of asymmetric incomplete information [19]. In the symmetric incomplete information, the absence of knowledge is equal for all the players. For example, in a sealed bid auction all players are equally unaware about the strategies of other players and the outcome associated with each. In the case of asymmetric incomplete information, some players know more than the other players. This knowledge or asymmetric information can be used by the possessive player as a threat or ultimatum to the other players of the game for his own advantage. For example, in the game of poker each player has only partial knowledge about the cards held by the other players. V. APPLICATION OF GAME THEORY IN COMMUNICATION NETWORKS Almost all the communication systems follow some standards, e.g., the Internet architecture follows the popular TCP/IP (Transmission Control Protocol/Internet Protocol) [ 20] protocol suits where all the involved network entities are assumed to follow the rules of the protocol in exact order. However, the cooperation to follow a certain protocol cannot be taken as for granted. Since devices are built by different vendors and it is quite possible that some manufacturers design their network devices such that they behave selfishly by deviating from the standard protocol, while other devices adhere to the same set of rules in the same network. This selfish behavior enables the individual devices to maximize their own performance in the shared network resource pool at the cost of others [21]. There is also the possibility that the end users of these devices program them in a selfish way. This maximization of one’s own benefit in a communication system at the cost of other users is called selfishness in the game theory. There are two approaches to cope with this selfish behavior in otherwise cooperative communication system. First, there are studies which provide some incentives and punishment mechanisms to force these selfish entities for cooperation. The misbehavior can also be modeled as a trust mechanism where only those entities in the network are served

who cooperate [22], [23]. The other approach to tackle this behavior is found in the non-cooperative game theory. This theory gives a perfect match and aim to solve the selfish behavior of the individual entities in a network by outlining rules of the game, which are same for all the participant agents. By not following these rules of the game, saying generally, no network entity can do better while others are following the same set of rules. This gives a huge advantage to address the non-cooperative behavior as for as telecommunication systems are concerned. The use of noncooperative game theoretic models is not new and a huge amount of literature can be found at different protocol layers and for different telecommunication systems. There is a huge amount of work on the access mechanisms, which tries to solve the non-cooperative behavior of nodes during accessing the shared medium with the game theoretic approaches [24]. The routing layer problems have been solved in many contexts, initially taking the concept of the application of noncooperative game theory in transportation system and then extending the same findings to the network routing [25]. Thus, the aim of applying the game theoretic models for routing solves the path finding problem, where routing and resource allocation problems have been solved as a joint game formulation. The non-cooperative routing games aim to solve the ‘path’ problem where a path is the route established inside a network from a source to destination, both aim to maximize the route benefit for themselves and compete with other source, destination pairs in the network. The problems at transport layer have been addressed in many research findings [26], where the behavior of TCP protocol has been fully analyzed and solutions from the non-cooperative game theory have been provided to solve the congestion problem in the selfish environment. There is a huge interest in studying the cognitive radio networks with the help of non-cooperative game theory [27-30]. Since cognitive networks consist of primary and secondary users, the spectrum access mechanism is designed with a game outlining the rules to maximize the spectrum utilization as well as the user’s personal payoffs. Similarly, the problems at MAC layer relating to the channel assignment are tackled using game theory in the work [40], [41], [42], [43]. Several telecommunication problems have been addressed in studies where the mechanisms are being developed based on the models from cooperative game theory. The studies of [22], [23], address the issues concerning the physical layer of the protocol stack using cooperative game theory. The network layer issues have been addressed in the work of [23], while congestion control cooperative games have been studied by [31], [32]. Comparatively, designing cooperative games in a large system like Internet and other scalable networks faces many challenges ranging from efficiency, complexity and fairness among the individual users. The fundamental role of the cooperation among the entities of a network and their effect on the overall system performance has been reported in most recent studies. This basis of cooperative communication can be traced back to the work of [33], who has introduced the relay channel cooperation games. Recently the work of [34], [35] have used the idea of cooperative communications and proposed models based on the cooperative strategies by the network entities. In their proposed models [25], the authors 9

[ISSN: 2045-7057]

www.ijmse.org

INTERNATIONAL J OURNAL OF M ULTIDISCIPLINARY S CIENCES AND ENGINEERING, VOL . 3, NO. 4, APRIL 2012

have proved that multi-hop forwarding achieves optimal capacity scaling in network of large population. Similarly, in [36], [37] the authors have proven that the use of cooperation can increase the energy efficiency in wireless ad-hoc networks. However, these studies assume that the network users cooperate and forward the packets for others in the network at the expense of their own energy consumption. In the emerging networks, which are distributed in nature and not being in the authority of single organization; this assumption cannot hold. For example Mobile Ad-hoc Networks [38] and Wireless Mesh Networks (WMNs) [39] are very decentralized, auto configured and the nature of resource is very distributed. In such environment, the assumption of cooperation may not be valid. The increased capability of reprogrammability of wireless devices offers another threat to this assumption. It is, therefore, important that the issues in networks like WMNs and MANETs should be addressed by using the concepts from non-cooperative game theory. VI. CONCLUSION This paper presents a detailed study of game theory and the associated concepts. The classification of games based on the information, rules, moves and rationality has been discussed. The two famous games in the literature of game theory, Prisoner’s Dilemma and the Battle of the Sexes have been investigated in detail with the associated concepts of pure and mixed strategies. Nash Equilibrium along with Pareto Efficiency has been covered in detail along with their properties. Finally, the paper gives an insight to the use of game theory in the problems of Communication Networks both from cooperative and non-cooperative perspectives. REFERENCES

[1] [2] [3] [4] [5]

[14]

[15] [16] [17]

[18] [19] [20] [21]

[22]

[23]

[24]

[25]

[26]

[27]

[6] [7] [8] [9] [10] [11]

[12]

[13]

M. J. Osborne, An Introduction to Game Theory. Oxford University Press New York, NY, 2004. G. Owen, “Game Theory”, London, UK: Academic Press, 3rd edition, October1995. D. Fudenberg and J. Tirole, “Game Theory”, MIT Press, 1983. J. von Neumann and O. Morgenstern, “Theory of Games and Economic Behavior”, Princeton University Press, 1944. J. Von Neumann, O. Morgenstern, A. Rubinstein and H. W. Kuhn, Theory of Games and Economic Behavior. Princeton Univ Pr, 2007. J. McDonald, Strategy in Poker, Business and War. WW Norton & Company, 1996. J. Nash, “Non-Cooperative Games”, Second series, vol. 54, No. 2, pp. 286-295, 1951. R. D. Luce and H. Raiffa, Games and Decisions: Introduction and Critical Survey. Dover Pubns, 1989. R. D. Luce and H. Raiffa, Games and Decisions: Introduction and Critical Survey. Dover Pubns, 1989. R. D. Luce and H. Raiffa, "Game and decisions," 1957. J. C. Harsanyi, "Games with incomplete information played by" bayesian" players, i-iii. part i. the basic model," Management Science, pp. 159-182, 1967. Prisoner's Dilemma, Stanford encyclopaedia of Philosophy, Available online at; http://plato.stanford.edu/entries/prisonerdilemma/ [Accessed January, 2012]. A. Rapoport and M. Chammah, “Prisoner’s dilemma: a study in conflict and cooperation”, The University of Michigan Press, Second edition 1970.

[28]

[29]

[30]

[31]

[32]

[33]

[34]

W. David, K. Yeung, and L. A. Petrosyan, “Cooperative Stochastic Differential Games”, Springer Series in Operations Research and Financial Engineering, 2004. I. K. Ge?kil and P. L. Anderson, Applied Game Theory and Strategic Behavior. Chapman & Hall/CRC, 2010. E. E. C. Damme, "Non-cooperative games," Discussion Paper, 2000. R. J. Aumann and J. H. Dreze, "Cooperative games with coalition structures," International Journal of Game Theory, vol. 3, pp. 217-237, 1974. J. Friedman (Ed.), “The Rational Choice Controversy”, Yale University Press, 1996. A. K. Dixit, S. Skeath and D. H. Reiley, Games of Strategy. Norton New York, 1999. W. R. Stevens, TCP/IP Illustrated: The Protocols. AddisonWesley Professional, 1994. A. Urpi, M. Bonuccelli and S. Giordano, "Modelling cooperation in mobile ad hoc networks: a formal description of selfishness," 2003. Z. Han and K.J. Liu, “Resource Allocation for Wireless Networks: Basics, Techniques, and Applications”, New York, USA: Cambridge University Press, 2008. T. Alpcan and T. Basar, “A Globally Stable Adaptive Congestion Control Scheme for Internet-Style Networks with Delay”, IEEE/ACM Trans. On Networking, vol. 13, pp. 1261– 1274, Dec. 2005. L. Chen, S. H. Low and J. C. Doyle, "Random access game and medium access control design," IEEE/ACM Transactions on Networking (TON), vol. 18, pp. 1303-1316, 2010. E. Altman, T. Boulogne, R. El-Azouzi, T. Jimenez and L. Wynter, "A survey on networking games in telecommunications," Comput. Oper. Res., vol. 33, pp. 286311, 2006. T. Alpcan and T. Basar, "A game-theoretic framework for congestion control in general topology networks (I)," in IEEE Conference On Decision and Control, Maui, USA, pp. 12181224, 2002. D. Niyato and E. Hossain, "Competitive pricing for spectrum sharing in cognitive radio networks: Dynamic game, inefficiency of nash equilibrium, and collusion," Selected Areas in Communications, IEEE Journal on, vol. 26, pp. 192202, 2008. N. Nie and C. Comaniciu, "Adaptive channel allocation spectrum etiquette for cognitive radio networks," Mobile Networks and Applications, vol. 11, pp. 779-797, 2006. D. Niyato and E. Hossain, "Competitive spectrum sharing in cognitive radio networks: a dynamic game approach," Wireless Communications, IEEE Transactions on, vol. 7, pp. 2651-2660, 2008. B. Wang, Y. Wu and K. Liu, "Game theory for cognitive radio networks: An overview," Computer Networks, vol. 54, pp. 2537-2561, 2010. S. Floyd and K. Fall, "Promoting the use of end-to-end congestion control in the Internet," IEEE/ACM Transactions on Networking (TON), vol. 7, pp. 458-472, 1999. F. Kelly, "Fairness and stability of end-to-end congestion control," European Journal of Control, vol. 9, pp. 159-176, 2003. T. Basar and G. J. Olsder, “Dynamic Noncooperative Game Theory”, Philadelphia, PA, USA: SIAM Series in Classics in Applied Mathematics, Jan. 1999. T. Alpcan, T. Basar, R. Srikant, and E. Altman, “CDMA Uplink Power Control as A Noncooperative Game”, Wireless Networks, vol. 8, pp. 659–670, 2002.

[ISSN: 2045-7057]

www.ijmse.org

10

INTERNATIONAL J OURNAL OF M ULTIDISCIPLINARY S CIENCES AND ENGINEERING, VOL . 3, NO. 4, APRIL 2012

[35]

[36]

[37]

[38] [39] [40]

[41]

[42]

A. MacKenzie, L. DaSilva, and W. Tranter, “Game Theory for Wireless Engineers”, Morgan&Claypool Publishers, March 2006. R. Thrall, and W. Lucas, “N-person Games in Partition Function Form”, Naval Research Logistics Quarterly, vol. 10, pp. 281–298, 1963. T. Basar and G. J. Olsder, “Dynamic Noncooperative Game Theory”, Philadelphia, PA, USA: SIAM Series in Classics in Applied Mathematics, Jan. 1999. S. Giordano, "Mobile ad hoc networks," Handbook of Wireless Networks and Mobile Computing, pp. 325-346, 2002. I. F. Akyildiz and X. Wang, Wireless Mesh Networks. John Wiley & Sons Inc, 2009. Ibrar Shah, Sadaqat Jan, Kok-Keong Loo, “Selfish Flow Games in Non-Cooperative Multi-Radio Multi-Channel Wireless Mesh Networks With Imperfect Information”, The Sixth International Conference on Wireless and Mobile Communications (ICWMC), Valencia, Spain, Pages: 219 – 225, Year of Publication:2010, Print ISBN: 978-1-4244-8021-0 Ibrar Shah, Sadaqat Jan, Kok-Keong Loo, “Selfish Flow Games in Non-Cooperative Multi-Radio Multi-Channel Wireless Mesh Networks in Interference constrained topology ”, International Journal of Advances in Telecommunications. Volume 4, Number 2, 2011. issn: 1942-2601 Ibrar Shah, Sofian Hamad and Hamed Al-Raweshidy, “MultiRadio Multi-Channel Assignment Games in Non-Cooperative Wireless Mesh Networks With End User Bargaining”, The 7th IEEE International Conference on Natural Computation (ICNC'11), Shanghai, China. Print ISBN: 978-1-61284-180-9

Ibrar Ali Shah received his B.Sc. and M.Sc. degrees in Computer Systems Engineering from NWFP University of Engineering & Technology, Peshawar, Pakistan in 2004 and 2007 respectively. Currently, he is with Wireless Networks & Communications Centre, Brunel University, London UK working towards his PhD. His research mainly focuses on cooperative and noncooperative behavior in Wireless Mesh Networks where he is working on routing and channel assignment problems by using game theoretic models for fairness, QoS and throughput optimization. Sadaqat Jan is working as Assistant Professor in Computer Software Engineering Department at University of Engineering and Technology, Mardan Campus, Pakistan. He received his PhD degree from Brunel University, UK and Master degree from NWFP University of Engineering and Technology Peshawar, Pakistan. His research interests include Grid Computing, Mobile Computing, and Information retrieval, Distributed Systems, Semantic Web, Knowledge Engineering and Computer Networks. He is a member of IEEE.

Imran Khan is working as Assistant Professor in Department of Telecommunication Engineering at University of Engineering and Technology, Mardan Campus, Pakistan since 2004. He received his PhD and Master degree from AIT, Thailand. He is student member of IEICE and IEEE. Mr. Khan’s research interests include performance analysis of wireless communications systems, OFDM, OFDMA, MIMO, BICM-ID based systems and cooperative networks.

Shahzad Qamar is working as a Lecturer in Faculty of Computing and IT at King Abdulaziz University, Saudi Arabia. Shahzad has done his MS in Wireless and Mobile Networks from Bournemouth University UK. Shahzad Qamar’s research focus is on the new emerging technologies like Green and Cloud Computing, QoS in WiMAX and WiFi Networks.

[ISSN: 2045-7057]

www.ijmse.org

11

相关文章:

- An Overview of the Theory and Applications metasurf....pdf
*An**Overview**of*the*Theory**and**Applications*metasurfaces_电子/电路_工程科技_专业资料。Metamaterials are engineered by arranging a set*of*small scatterers or ...

- Chapter_09Capital Market Theory An Overview(公司理财-四川大学....pdf
- Chapter 9 zsong@scu.edu.cn Capital Market
*Theory*:*An**Overview*9-0 PDF 文件使用 "pdfFactory Pro" 试用版本创建 | www.fineprint.com.cn Risk, ...

- ...Theory, Problem and SolutionAn Overview of the Sp_论文....pdf
- China
*and*World Population Development:*Theory*, Problem*and*Solution*An**Overview**of*the Sp_专业资料。Deelvopmen:htTeor Problem dSolton*an*i uAnOvreo ...

- Chapter5 Critical Perspectives_图文.ppt
- Film
*Theory*provides*an*alternative set*of*critical approaches评论角度: Auteur...21. Critical Perspectives Typical Thematic Concerns Here is*an**overview**of*...

- 英语论文从目的论角度分析情景喜剧的字幕翻译_图文.doc
- he makes
*an**overview**of*the subtitle translation...*communication*between China*and*foreign countries, ... carried forward part*of**his*teacher’s*theory*....

- Day 1 -Overview of Game Theory_图文.ppt
- A Short Course on the
*Application**of**Game**Theory*to Wireless*Networks*James Neel Lecture 1*An**Overview**of**Game**Theory*July 30, 2003*An**Overview**of*...

- overview of learning theory (tong).pdf
*overview**of*learning*theory*(tong)_*IT*/计算机_专业资料。《机器学习Machine ... Learning*Theory*15 / 24 Empirical Processes Empirical process is*an*...

- Overview on Games in Networks.pdf
*overview*on*Game**Theory**and*how*it*applies to ...*communication**networks*because*its*model*of*the ...For instance,*in*TCP,*an*individual user might ...

- Computational complexity theory- an overview.pdf
- Computational complexity
*theory*-*an**overview*_专业...messages with the prover over the*communication*...*In*the end, the veri er passes*his*verdict -...

- ...and Control System Design- an Overview.pdf
- Design-
*an**Overview*_信息与通信_工程科技_专业资料... neural*network*, fuzzy logic*theory*, gain ...systems*and**its**applications*to modeling*and*...

- Theory and applications of artificial endocrine system-an ....pdf
*Theory**and**applications**of*artificial endocrine system-*an**overview*_信息与通信_工程科技_专业资料。维普资讯 http://www.cqvip.com 第2 7卷 增刊 200 6年 7...

- An Overview of Finite-Time Stability.pdf
*An**Overview**of*Finite-Time Stability_工学_高等...Finally some*applications**of*the*theory*will be ... certain aircraft maneuvers,*communication**networks*,...

- ...in Wireless Networks An Overview of Game-Theoret....pdf
- Wireless
*Networks**An**Overview**of**Game*-Theoretic ...ciency, quality*of*service (QoS),*game**theory*,... a mixture*of*delay-sensitive*applications*(e.g...

- coupled mode theory for optical waveguides an overview.pdf
- coupled mode
*theory*for optical waveguides*an**overview*_信息与通信_工程科技_...starts with a brief description*of*the conventional CMT*and**its**applications*...

- ...Communication Systems Theory and Applications.pdf
- Millimeter-Wave Wireless
*Communication*Systems*Theory**and**Applications*_韩语学习_...M. Smulders This paper presents*an**overview**of*60 GHz technology*and**its*...

- 08-2 CH01.Overview fo Cryptography and its applications.pdf
- Introduction to Cryptography with Coding
*Theory*(...Ch1.*Overview**of*Cryptography &*Its**Applications*...*Communication*Scenario 2008-09-10 CNSL-Internet-...

- Data Fusion for Modern Engineering Applications An Overview_....pdf
- Modern Engineering
*Applications**An**Overview*_专业资料...The recent interest*in*the*theory**and*taxonomy ... two way*communication*; Decentralised: robust ...

- An Overview of Recent Progress in the Study of Dist....pdf
*An**Overview**of*Recent Progress*in*the Study*of*...*communication*noise,*and*uncertainties*in**network*...[128]*and*the*game**theory**in*distributed ...

- COMMUNICATIONS OF EASST 1 Overview Softure Adaptable, ....pdf
*theory**in*order to attach to (mobile) components... the following presents*an**overview**of*the ...*applications*for next generation*networks*;*and*the...

- ...NETWORKS A COOPERATIVE BARGAINING GAME THEORETIC_图文.pdf
- we first present
*an**overview**of*the*game*...*theory**and*noncooperative*game**theory*, respectively...*its*way directly into practical*network**applications*...

- A survey on game theory applications in wireless networks
- Finance Applications of Game Theory
- Theory of burst-mode receiver and its applications in optical multiaccess networks
- Game_Theory(2012)
- Game theory for wireless networks 4
- Game theory for wireless networks 6
- Game theory for wireless networks 5
- Game theory for wireless networks 3
- Game theory for wireless networks 2
- Game Theory - Mathematical Fundaments and Examples of Applications