Non-cooperative game theory

Last updated

A non-cooperative game is a form of game under the topic of game theory. Non-cooperative games are used in situations where there are competition between the players of the game. In this model, there are no external rules that enforces the cooperation of the players therefore it is typically used to model a competitive environment. This is stated in various accounts most prominent being John Nash's paper. [1]

Contents

That being said, there are many arguments to be made regarding this point as with decades of research, it is shown that non-cooperative game models can be used to show cooperation as well and vice versa for cooperative game model being used to show competition.

Some examples of this would be the usage of non-cooperative model in determining the stability and sustainability of cartels and coalitions. [2] [3]

Non zero-sum games and zero-sum games are both types of non-cooperative games. [4]

Non-cooperative game theory in academic literature

Referring to the above mentioned John Nash's 1951 article in the journal Annals of Mathematics . Nash Equilibrium, non-cooperative game theory in fact, are often referred to as "non-cooperative equilibrium". [5]

According to Tamer Başar in Lecture Notes on Non-Cooperative Game Theory, a non-cooperative game requires specifying:

  1. the number of players;
  2. the possible actions available to each player, and any constraints that may be imposed on them;
  3. the objective function of each player which he or she attempts to optimise;
  4. any time ordering of the execution of the actions if the players are allowed to act more than once;
  5. any information acquisition that takes place and how the information available to a player at each point in time depends on the past actions of other players, and;
  6. whether there is a player (nature) whose action is the outcome of a probabilistic event with a fixed (known) distribution. [6]
  7. The utility of each player for all action profile.

Assumptions

  1. Perfect recall: each player remembers their decisions and known information. [7]
  2. Self-interest: each player does not consider the effect of actions on the others but only on their own. [7]
  3. Rational: each player is interested to maximise their utility or payoff. [8] [9]
  4. Complete information: each player knows the preferences and strategies of the other players. [8]
  5. Each player has the same understanding of how the game is. [8]

Creating a non-cooperative game (basic game)

In order to understand the usage of the non-cooperative game model, we must first understand how to create a non-cooperative game.

The following will provide the requirements to create a basic non-cooperation game to encourage a basic understanding of the model

First, following the above mentioned requirements, we need to know how many players there are. For simplicity in explanation, let the number of players be n. In a 2 or 3 player game, it is still relatively easy to represent the game in a matrix. However, as they number of player increases, it becomes significantly hard and more time consuming to do so. As such we represent it in a form of mathematical equations.

Therefore the Player set would look like this {1,....., n}.

Secondly, We need to determine the possible actions that can be taken by each of the players. For simplicity in explanation, let the set of actions of a player be denoted as X

Therefore the action of player the player set will look like this {X1,....., Xn}.

Lastly, we will have to determine the utility of the player for each action profile. For this criteria, there is no fixed methodology as the utility of each player is determined by the perceived benefits of the outcome. However in theory, we generally assign a value to a player's utility so that we are able to determine each player's rational decision and preferred outcome. This is different from expected utility which is covered when solving the game [1] [6] [10]

You can refer to the list of common examples below to see how these steps creates a non-competitive game.

Analysis

Non-cooperative games are generally analysed through the non-cooperative game theory framework, which attempts to predict players' individual strategies and payoffs and in order to find the Nash equilibria. [11] [12] This framework often requires a detailed knowledge in the possible actions and the levels of information of each player. [13] It is opposed to cooperative game theory, which focuses on predicting which groups of players ("coalitions") will form, the joint actions that these groups will take, and the resulting collective payoffs that arise. Cooperative game theory does not analyse the strategic bargaining that occurs within each coalition and affects the distribution of the collective payoff between the members. Further in contrast to cooperative game theory, it is assumed that players involved have prior knowledge of their game in which they are involved, due to built in commitments. [14]

Non-cooperative game theory provides a low-level approach as it models all the procedural details of the game, whereas cooperative game theory only describes the structure, strategies and payoffs of coalitions. Therefore, cooperative game theory is referred to as coalitional, and non-cooperative game theory is procedural. [13] Non-cooperative game theory is in this sense more inclusive than cooperative game theory.

It is also more general, as cooperative games can be analysed using the terms of non-cooperative game theory where arbitration is available to enforce an agreement, that agreement falls outside the scope of non-cooperative theory: but it may be possible to state sufficient assumptions to encompass all the possible strategies players may adopt, in relation to arbitration. This will bring the agreement within the scope of non-cooperative theory. Alternatively, it may be possible to describe the arbitrator as a party to the agreement and model the relevant processes and payoffs suitably.

Accordingly, it would be desirable to have all games expressed under a non-cooperative framework. But in many instances insufficient information is available to accurately model the formal procedures available to the players during the strategic bargaining process; or the resulting model would be of too high complexity to offer a practical tool in the real world. In such cases, cooperative game theory provides a simplified approach that allows analysis of the game at large without having to make any assumption about bargaining powers.

Additionally, we must also look at the limitations that the non-cooperative model may have. We can have a clearer picture when looking at the list of assumptions stated above. As already mentioned, there are many scenarios where perfect symmetry of information is not possible which therefore results in the decision making process to be flawed. [15]

Secondly, the assumption of self-interest and rationality could be argued. Arguments are made that being rational can result in the assumption of self-interest being invalidated and vice versa. One such example could be the reduction in profits and revenue in attempts to drive out competitors for a higher market share. This thus does not follow both of the assumptions as the player is concerned with the downfall of their opponent more than the maximisation of their profits. There is the argument to be made that although mathematically sound and feasible, it is not necessarily the best method of looking at real life economical problems that are more complex in nature. [15]

Examples

Strategic games are also a form of non-cooperative game theory, where only the available strategies and combinations of options are listed to produce outcomes.

Rock-paper-scissors

Rock paper scissors.jpg

The simple example is the game of rock-paper-scissors. In the game of rock-paper-scissors, there is no cooperative option between the two players available: if Player 1 decides to play "rock", it is in Player 2's interest to play "paper"'; if Player 2 chooses to play "paper", it is in Player 1's interest to play "scissors"; and if Player 1 plays "scissors", Player 2 will, in their own interests, play "rock". The preferences of the players is cyclical, with no cooperative outcome being reached. This fails the transitive preference property.

Two children steal sweets

Suppose a shopkeeper catches two children for stealing sweets. The two children spoke separately with the shop owner in the shop office. In this case, the children have only two options: to remain silent (neither child admits it) or to say that their peers stole the sweets. If one child admits to stealing the sweets and the other does not, the child who admits will receive a warning, and the other child will be punished for four weeks. If both children admit to stealing the sweets, they will both receive a two-week punishment. If they both deny it, then both children will be punished for three weeks. One child must rely on the idea of another child to avoid minor punishment. The connection between them is that game theory generally looks at how individuals or groups make choices that will affect other parties.

Two children for steal sweets
Child A/ Child BRecognitionNon-recognition
Recognition-2, -20, -4
Non-recognition-4, 0-3, -3

The two children's first thought must have been their interests, but this would have led to the most extended punishment for both. The best option for them is for them to both admit and punish for a fortnight. Thus, this is the Nash equilibrium, also called the non-cooperative equilibrium.

Prisoner's Dilemma

A standard form Prisoner's Dilemma game. Prisoner's Dilemma.jpg
A standard form Prisoner's Dilemma game.

The Prisoner's Dilemma game is another well-known example of a non-cooperative game. The game involves two players, or defendants, who are kept in separate rooms and thus are unable to communicate. Players must decide, by themselves in isolation, whether to cooperate with the other player or to betray them and confess to law authorities. As shown in the diagram, both players will receive a higher payoff in the form of a lower jail sentence if they both remain silent. If both confess, they receive a lower payoff in the form of a higher jail sentence. If one player confesses and the other remain silent and cooperates, the confessor will receive a higher payoff, while the silent player will receive a lower payoff than if both players cooperated with each other.

The Nash equilibrium therefore lies where players both betray each other, in the players protecting oneself from being punished more.

The battle of the sexes game

The game involves two players, boy and girl, deciding either going to a football game or going to an opera for their date, which respectively represent boy's and girl's preferred activity (i.e. boy prefers football game and girl prefers opera). [16] This example is a two-person non-cooperative non-zero sum (TNNC) game with opposite payoffs or conflicting preferences. [16] Because there are two Nash equilibria, this case is a pure coordination problem with no possibility of refinement or selection. [8] Thus, the two players will try to maximise their own payoff or to sacrifice for the other and yet these strategy without coordination will lead to two outcomes with even worse payoffs for both if they have disagreement on what to do on their date.

The battle of the sexes game
Boy/ GirlFootballOpera
Football(2, 1)(-1, -1)
Opera(-1, -1)(1, 2)

Matching pennies game

This game is a two-person zero-sum game. In order to play this game, both players will each need to be given a fair two-sided penny. To start the game, both player will each choose to either flip their penny to heads or tails. This action is to be done in secrecy and there should be no attempt at investigating the choice of the other player. After both players have confirmed their decisions, they will simultaneously reveal their choices. This concludes the actions taken by the players to determine the outcome. [10]

The win condition for this game is different for both players. For simplicity in explanation, lets denote the players as Player 1 and Player 2. In order for Player 1 to win, the faces of the pennies must match (This means they must both be heads or tails). In order for Player 2 to win, the faces of the pennies must be different (This means that they must be in a combination of heads and tails). [10]

The payoff/prize of this game is receiving the loser's penny in addition to your own.

Therefore the payoff matrix will look like this:

Player1 \ Player 2HeadsTails
Heads1, -1-1, 1
Tails-1, 11, -1

Looking at this matrix, we can conclude a few basic observations. [10]

1) For all scenarios, there will be a loser and a winner.

2) This is a zero sum game where the pay out to the winner is equal to the loss of the loser.

3) There is no Pure Strategy Nash Equilibrium.

To develop a more detailed and comprehensive article, refer to the main article that gives more information with different explanations.

The difference between cooperative and non-cooperative game theory

There is a distinction between cooperative game theory and non-cooperative game theory, which follows Nash's statement: “This (cooperative game) theory is based on an analysis of the interrelationships of the various coalitions which can be formed by the players of the game. Our (non-cooperative game) theory, in contradistinction, is based on the absence of coalitions in that it is assumed that each participant acts independently, without collaboration or communication with any of the others.” [17]

Non-cooperative game theory models different situations in which agents are unable to reach a resolution to a conflict that enforces some action on one another. [18] [7] This form of game theory pays close attention to the individuals involved and their rational decision making. [13] There are winners and losers in each case, and yet agents may end up in Pareto-inferior outcomes, where every agent is worse off and there is an potential outcome for every agent to be better off. [19] Agents will have the ability to predict what their opponents will do. Cooperative game theory models situations in which a binding agreement is possible. In other words, the cooperative game theory implies that agents cooperate to achieve a common goal and they are not necessarily referred to as a team because the correct term is the coalition. Each agent has its skills or contributions that provide strength to the coalition. [20]

Further, it has been supposed that non-cooperative game theory is purported to analyse the effect of independent decisions on society as a whole. [21] In comparison, cooperative game theory focuses only on the effects of participants in a certain coalition, when the coalition attempts to improve the collective welfare. [21]

Many results or solutions proposed by the agents involved in Game Theory are important in understanding the rivalry between these agents under a set of conditions that are strategic. [18]

Solutions

Solutions in non-cooperative games are similar to all other games in game theory, but without the ones involved binding agreements enforced by the external authority. The solutions are normally based on the concept of Nash equilibrium, and these solutions are reached by using methods listed in Solution concept. Most solutions used in non-cooperative game are refinements developed from Nash equilibrium, including the minimax mixed-strategy proved by John von Neumann. [19] [9] [22]

See also

Related Research Articles

Game theory is the study of mathematical models of strategic interactions among rational agents. It has applications in all fields of social science, as well as in logic, systems science and computer science. The concepts of game theory are used extensively in economics as well. The traditional methods of game theory addressed two-person zero-sum games, in which each participant's gains or losses are exactly balanced by the losses and gains of other participants. In the 21st century, the advanced game theories apply to a wider range of behavioral relations; it is now an umbrella term for the science of logical decision making in humans, animals, as well as computers.

The prisoner's dilemma is a game theory thought experiment that involves two rational agents, each of whom can cooperate for mutual benefit or betray their partner ("defect") for individual reward. This dilemma was originally framed by Merrill Flood and Melvin Dresher in 1950 while they worked at RAND. Albert W. Tucker later formalized the game by structuring the rewards in terms of prison sentences and named it the "prisoner's dilemma".

In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equilibrium strategies of the other players, and no one has anything to gain by changing only one's own strategy. The principle of Nash equilibrium dates back to the time of Cournot, who in 1838 applied it to competing firms choosing outputs.

The game of chicken, also known as the hawk–dove game or snowdrift game, is a model of conflict for two players in game theory. The principle of the game is that while the ideal outcome is for one player to yield, the individuals try to avoid it out of pride for not wanting to look like a "chicken". Each player taunts the other to increase the risk of shame in yielding. However, when one player yields, the conflict is avoided, and the game is for the most part over.

A coordination game is a type of simultaneous game found in game theory. It describes the situation where a player will earn a higher payoff when they select the same course of action as another player. The game is not one of pure conflict, which results in multiple pure strategy Nash equilibria in which players choose matching strategies. Figure 1 shows a 2-player example.

In game theory, a player's strategy is any of the options which they choose in a setting where the outcome depends not only on their own actions but on the actions of others. The discipline mainly concerns the action of a player in a game affecting the behavior or actions of other players. Some examples of "games" include chess, bridge, poker, monopoly, diplomacy or battleship. A player's strategy will determine the action which the player will take at any stage of the game. In studying game theory, economists enlist a more rational lens in analyzing decisions rather than the psychological or sociological perspectives taken when analyzing relationships between decisions of two or more parties in different disciplines.

In game theory, an extensive-form game is a specification of a game allowing for the explicit representation of a number of key aspects, like the sequencing of players' possible moves, their choices at every decision point, the information each player has about the other player's moves when they make a decision, and their payoffs for all possible game outcomes. Extensive-form games also allow for the representation of incomplete information in the form of chance events modeled as "moves by nature". Extensive-form representations differ from normal-form in that they provide a more complete description of the game in question, whereas normal-form simply boils down the game into a payoff matrix.

In game theory, a Bayesian game is a strategic decision-making model which assumes players have incomplete information. Players hold private information relevant to the game, meaning that the payoffs are not common knowledge. Bayesian games model the outcome of player interactions using aspects of Bayesian probability. They are notable because they allowed, for the first time in game theory, for the specification of the solutions to games with incomplete information.

In game theory, strategic dominance occurs when one strategy is better than another strategy for one player, no matter how that player's opponents may play. Many simple games can be solved using dominance. The opposite, intransitivity, occurs in games where one strategy may be better or worse than another strategy for one player, depending on how the player's opponents may play.

In game theory, folk theorems are a class of theorems describing an abundance of Nash equilibrium payoff profiles in repeated games. The original Folk Theorem concerned the payoffs of all the Nash equilibria of an infinitely repeated game. This result was called the Folk Theorem because it was widely known among game theorists in the 1950s, even though no one had published it. Friedman's (1971) Theorem concerns the payoffs of certain subgame-perfect Nash equilibria (SPE) of an infinitely repeated game, and so strengthens the original Folk Theorem by using a stronger equilibrium concept: subgame-perfect Nash equilibria rather than Nash equilibria.

In game theory, a repeated game is an extensive form game that consists of a number of repetitions of some base game. The stage game is usually one of the well-studied 2-person games. Repeated games capture the idea that a player will have to take into account the impact of their current action on the future actions of other players; this impact is sometimes called their reputation. Single stage game or single shot game are names for non-repeated games.

In game theory, the outcome of a game is the ultimate result of a strategic interaction with one or more people, dependant on the choices made by all participants in a certain exchange. It represents the final payoff resulting from a set of actions that individuals can take within the context of the game. Outcomes are pivotal in determining the payoffs and expected utility for parties involved. Game theorists commonly study how the outcome of a game is determined and what factors affect it.

In game theory, the purification theorem was contributed by Nobel laureate John Harsanyi in 1973. The theorem aims to justify a puzzling aspect of mixed strategy Nash equilibria: that each player is wholly indifferent amongst each of the actions he puts non-zero weight on, yet he mixes them so as to make every other player also indifferent.

In game theory, a subgame perfect equilibrium is a refinement of a Nash equilibrium used in dynamic games. A strategy profile is a subgame perfect equilibrium if it represents a Nash equilibrium of every subgame of the original game. Informally, this means that at any point in the game, the players' behavior from that point onward should represent a Nash equilibrium of the continuation game, no matter what happened before. Every finite extensive game with perfect recall has a subgame perfect equilibrium. Perfect recall is a term introduced by Harold W. Kuhn in 1953 and "equivalent to the assertion that each player is allowed by the rules of the game to remember everything he knew at previous moves and all of his choices at those moves".

Quantal response equilibrium (QRE) is a solution concept in game theory. First introduced by Richard McKelvey and Thomas Palfrey, it provides an equilibrium notion with bounded rationality. QRE is not an equilibrium refinement, and it can give significantly different results from Nash equilibrium. QRE is only defined for games with discrete strategies, although there are continuous-strategy analogues.

In game theory, an epsilon-equilibrium, or near-Nash equilibrium, is a strategy profile that approximately satisfies the condition of Nash equilibrium. In a Nash equilibrium, no player has an incentive to change his behavior. In an approximate Nash equilibrium, this requirement is weakened to allow the possibility that a player may have a small incentive to do something different. This may still be considered an adequate solution concept, assuming for example status quo bias. This solution concept may be preferred to Nash equilibrium due to being easier to compute, or alternatively due to the possibility that in games of more than 2 players, the probabilities involved in an exact Nash equilibrium need not be rational numbers.

In game theory, the traveler's dilemma is a non-zero-sum game in which each player proposes a payoff. The lower of the two proposals wins; the lowball player receives the lowball payoff plus a small bonus, and the highball player receives the same lowball payoff, minus a small penalty. Surprisingly, the Nash equilibrium is for both players to aggressively lowball. The traveler's dilemma is notable in that naive play appears to outperform the Nash equilibrium; this apparent paradox also appears in the centipede game and the finitely-iterated prisoner's dilemma.

Cooperative bargaining is a process in which two people decide how to share a surplus that they can jointly generate. In many cases, the surplus created by the two players can be shared in many ways, forcing the players to negotiate which division of payoffs to choose. Such surplus-sharing problems are faced by management and labor in the division of a firm's profit, by trade partners in the specification of the terms of trade, and more.

<span class="mw-page-title-main">Simultaneous game</span>

In game theory, a simultaneous game or static game is a game where each player chooses their action without knowledge of the actions chosen by other players. Simultaneous games contrast with sequential games, which are played by the players taking turns. In other words, both players normally act at the same time in a simultaneous game. Even if the players do not act at the same time, both players are uninformed of each other's move while making their decisions. Normal form representations are usually used for simultaneous games. Given a continuous game, players will have different information sets if the game is simultaneous than if it is sequential because they have less information to act on at each step in the game. For example, in a two player continuous game that is sequential, the second player can act in response to the action taken by the first player. However, this is not possible in a simultaneous game where both players act at the same time.

<span class="mw-page-title-main">Jean-François Mertens</span> Belgian game theorist (1946–2012)

Jean-François Mertens was a Belgian game theorist and mathematical economist.

References

  1. 1 2 Nash, John (1951). "Non-Cooperative Games". Annals of Mathematics. 54 (2): 286–295. doi:10.2307/1969529. ISSN   0003-486X. JSTOR   1969529.
  2. ↑ Palsule-Desai, Omkar D. (2015-03-01). "Complete Versus Partial Collusion in Competing Coalitions". International Game Theory Review. 17 (1): 1540006. doi:10.1142/S021919891540006X. ISSN   0219-1989.
  3. ↑ Carraro, Carlo, ed. (2003-06-26). The Endogenous Formation of Economic Coalitions. Edward Elgar Publishing. doi:10.4337/9781781009888. ISBN   978-1-78100-988-8.
  4. ↑ Ibrahim, Khalid (4 October 2021). "Anti-Jamming Game to Combat Intelligent Jamming for Cognitive Radio Networks". IEEE Access. 9: 137941–137956. doi: 10.1109/ACCESS.2021.3117563 . S2CID   238751752.
  5. ↑ "A Brief Introduction to NON-COOPERATIVE GAME THEORY". 2010-06-10. Archived from the original on 2010-06-10. Retrieved 2021-04-27.
  6. 1 2 Başar, Tamer (26 January 2010). "Lecture Notes on Non-Cooperative Game Theory" (PDF). Hamilton Institute and CTVR in Trinity College, Dublin, Ireland.
  7. 1 2 3 Fujiwara-Greve, Takako (2015). "Non-Cooperative Game Theory". Monographs in Mathematical Economics. 1. doi:10.1007/978-4-431-55645-9. ISBN   978-4-431-55644-2. ISSN   2364-8279.
  8. 1 2 3 4 Aguirre, Iñaki. "Notes on Non-Cooperative Game Theory-Microeconomic Theory IV" (PDF).
  9. 1 2 Von Neumann, John (2007). Theory of games and economic behavior. Princeton Univ. Pr. ISBN   978-0-691-13061-3. OCLC   1081636887.
  10. 1 2 3 4 Takako, Fujiwara-Greve (23 October 2016). Non-Cooperative Game Theory. Monographs in Mathematical Economics. Vol. 1 (1st ed.). Springer Tokyo. doi:10.1007/978-4-431-55645-9. ISBN   978-4-431-56415-7.
  11. ↑ Chandrasekaran, R. "Cooperative Game Theory" (PDF).
  12. ↑ Brandenburger, Adam. "Cooperative Game Theory: Characteristic Functions, Allocations, Marginal Contribution" (PDF). Archived from the original (PDF) on 2016-05-27.
  13. 1 2 3 Chatain, Olivier (2018). "Cooperative and Non-cooperative Game Theory". In Augier, Mie; Teece, David J. (eds.). pp. 345–346. doi:10.1057/978-1-137-00772-8_468. ISBN   978-0-230-53721-7.{{cite book}}: |work= ignored (help); Missing or empty |title= (help)
  14. ↑ van Damme, E (2001). "Game theory: Noncooperative Game". www.sciencedirect.com. Retrieved 2023-04-24.
  15. 1 2 Michaelides, Panayotis G.; Papadakis, Theodoulos Eleftherios (28 January 2023). History of Economic Ideas (1st ed.). Palgrave Macmillan Cham. pp. 117–131. doi:10.1007/978-3-031-19697-3. ISBN   978-3-031-19697-3.
  16. 1 2 Biswas, Tapan (1997). Decision-Making under Uncertainty. doi:10.1007/978-1-349-25817-8. ISBN   978-0-333-66261-8. S2CID   153559123.
  17. ↑ Nash, John (1997-12-31), "3. Non-Cooperative Games. Annals of Mathematics 54 (1951) 286-295.", Classics in Game Theory, Princeton University Press, pp. 14–26, doi:10.1515/9781400829156-008, ISBN   9781400829156 , retrieved 2022-04-27
  18. 1 2 Aguirre, Inaki (2023-04-24). "Non-Cooperative Game Theory" (PDF). Retrieved 2023-04-24.
  19. 1 2 "Noncooperative Games". Encyclopedia.com. Retrieved 2022-05-02.
  20. ↑ Hamidi, Maryam; Liao, Haitao; Szidarovszky, Ferenc (2016-11-16). "Non-cooperative and cooperative game-theoretic models for usage-based lease contracts". European Journal of Operational Research. 255 (1): 163–174. doi: 10.1016/j.ejor.2016.04.064 . ISSN   0377-2217.
  21. 1 2 Non-Cooperative Game Theory (PDF). Monographs in Mathematical Economics. Vol. 1. 2015. doi:10.1007/978-4-431-55645-9. ISBN   978-4-431-55644-2.
  22. ↑ v. Neumann, J. (December 1928). "Zur Theorie der Gesellschaftsspiele". Mathematische Annalen. 100 (1): 295–320. doi:10.1007/bf01448847. ISSN   0025-5831. S2CID   122961988.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.