m (undo last change)
Line 55: Line 55:
  
 
<!-- End Part 1 -->
 
<!-- End Part 1 -->
 +
 
== Part 2: Cournot Competition ==
 
== Part 2: Cournot Competition ==
  
Nash Equilibrium in Economics
+
'''Nash Equilibrium in Economics'''
 +
 
 
In the game of economy, we are interested in the strategic interactions between players in a market/industry, and how the strategy of a player is affected by the existence of another player.
 
In the game of economy, we are interested in the strategic interactions between players in a market/industry, and how the strategy of a player is affected by the existence of another player.
 
In 1838, before John Nash formalized the proof of Nash Equilibrium, even before his birth, Antoine Augustin Cournot showed that a stable equilibrium exists in his model of competition between to producers, "If either of the producers, misled as to his true interest, leaves it temporarily, he will be brought back to it."
 
In 1838, before John Nash formalized the proof of Nash Equilibrium, even before his birth, Antoine Augustin Cournot showed that a stable equilibrium exists in his model of competition between to producers, "If either of the producers, misled as to his true interest, leaves it temporarily, he will be brought back to it."
Line 181: Line 183:
 
Lions are an example of an evolutionarily stable strategy, meaning that any small change in strategy will reduce fitness in some way. A group of lions may benefit from becoming larger by increasing strength relative to other lions, allowing for resolution of territorial disputes, but larger animals consume more energy and this strategy may increase the cost more than increasing the benefit, meaning this change in strategy reduces profit. Another group may benefit from becoming smaller by decreasing the energy spent relative to other lions, allowing for greater energy efficiency, but smaller lions may be less successful at hunting and this strategy may decrease the benefit more than decreasing the cost, again reducing profit.  
 
Lions are an example of an evolutionarily stable strategy, meaning that any small change in strategy will reduce fitness in some way. A group of lions may benefit from becoming larger by increasing strength relative to other lions, allowing for resolution of territorial disputes, but larger animals consume more energy and this strategy may increase the cost more than increasing the benefit, meaning this change in strategy reduces profit. Another group may benefit from becoming smaller by decreasing the energy spent relative to other lions, allowing for greater energy efficiency, but smaller lions may be less successful at hunting and this strategy may decrease the benefit more than decreasing the cost, again reducing profit.  
  
 +
<div style="display: flex; justify-content: center;">
 
[[File:MA279Group2Fall22ProjectGraph3.1.png|500px|thumbnail|center|Potential Profits of Different Sized Species]]
 
[[File:MA279Group2Fall22ProjectGraph3.1.png|500px|thumbnail|center|Potential Profits of Different Sized Species]]
 +
</div>
  
 
When all species in an environment possess an evolutionarily stable strategy, it forms a Nash equilibrium, since any change in strategy for any one player (species) will be purely detrimental, so changes in strategy do not stick around. Changes in strategy do still occur, since mutation is random, not by choice, but these changes lose out in competition with the evolutionarily stable strategy. Stable does not necessarily mean the strategy is impermeable, since changes in the environment can necessitate evolution, but so long as everything else around an evolutionarily stable species stays the same, that species will not adjust its strategy.
 
When all species in an environment possess an evolutionarily stable strategy, it forms a Nash equilibrium, since any change in strategy for any one player (species) will be purely detrimental, so changes in strategy do not stick around. Changes in strategy do still occur, since mutation is random, not by choice, but these changes lose out in competition with the evolutionarily stable strategy. Stable does not necessarily mean the strategy is impermeable, since changes in the environment can necessitate evolution, but so long as everything else around an evolutionarily stable species stays the same, that species will not adjust its strategy.
Line 189: Line 193:
 
Territorial behaviors can be explained using the hawk-dove game. Assume we have two male lions, Alex and Bob. If Alex and Bob both act as doves, they share food peacefully. If Alex changes his strategy to become a hawk, Alex now gains all the food in the area, and Bob must find some other area to hunt in. Alex's change in strategy is strictly better than before, meaning his strategy is stable for now. Bob can increase his individual gain by also becoming a hawk, if (V-C)/2 > 0. However, if Bob stayed a dove it would increase the total resources for the lion species, since becoming a hawk decreases the total gain to V - C.  
 
Territorial behaviors can be explained using the hawk-dove game. Assume we have two male lions, Alex and Bob. If Alex and Bob both act as doves, they share food peacefully. If Alex changes his strategy to become a hawk, Alex now gains all the food in the area, and Bob must find some other area to hunt in. Alex's change in strategy is strictly better than before, meaning his strategy is stable for now. Bob can increase his individual gain by also becoming a hawk, if (V-C)/2 > 0. However, if Bob stayed a dove it would increase the total resources for the lion species, since becoming a hawk decreases the total gain to V - C.  
  
 +
<div style="display: flex; justify-content: center;">
 
[[File:MA279Group2Fall22ProjectGraph3.2.png|500px|thumbnail|center|Outcome Space for Hawk-Dove Game]]
 
[[File:MA279Group2Fall22ProjectGraph3.2.png|500px|thumbnail|center|Outcome Space for Hawk-Dove Game]]
 +
</div>
  
 
This results in the emergence of territorial behavior in more aggressive species due to territorial species gaining a higher payoff. If two species A and B both engage in Hawk-Dove games for territorial control, they may end up with strategies S(A) and S(B). Both A and B seek to maximize their own gains whenever possible. Species A engages in territorial behavior, so the Nash equilibrium remains at one hawk, one dove, and S(A) has a species profit of V. Species B engages in selfish behavior, so the Nash equilibrium is two hawks as both species members avoid receiving nothing, and S(B) has a species profit of V - C. Because a higher profit means more energy can be spent towards reproduction, S(A) leads to more offspring than S(B), and thus S(A) is the greater strategy. Over time, this strategy leads species A to outperform species B, leading more dominant species to adopt territorial behaviors to increase their efficiency.
 
This results in the emergence of territorial behavior in more aggressive species due to territorial species gaining a higher payoff. If two species A and B both engage in Hawk-Dove games for territorial control, they may end up with strategies S(A) and S(B). Both A and B seek to maximize their own gains whenever possible. Species A engages in territorial behavior, so the Nash equilibrium remains at one hawk, one dove, and S(A) has a species profit of V. Species B engages in selfish behavior, so the Nash equilibrium is two hawks as both species members avoid receiving nothing, and S(B) has a species profit of V - C. Because a higher profit means more energy can be spent towards reproduction, S(A) leads to more offspring than S(B), and thus S(A) is the greater strategy. Over time, this strategy leads species A to outperform species B, leading more dominant species to adopt territorial behaviors to increase their efficiency.
  
 
<!-- End Part 3 -->
 
<!-- End Part 3 -->
 +
 +
== Part 4: Game Theory and Elections ==
 +
 +
Game theory has widely use among human society. One example would be
 +
 +
<!-- End Part 4 -->
  
 
== References ==
 
== References ==

Revision as of 22:20, 27 November 2022

Part 1: Introduction and Terms

What is game theory and where did it come from?

Game theory is a discipline of mathematics that gives an axiomatic way to represent and examine systems of rational actors. It uses the suspected preferences of the actors to predict outcomes of games with certain rules and/or conditions. For example we could use game theory to determine the prices that two competing duopolies in a local market should set in order to maximize each of their profits.

While some situations studied in modern game theory can trace their roots all the way back to ancient Greece, game theory first emerged as a formal mathematical sub-discipline from the works of mathematician John von Nueman and economist Oskar Morgenstern in the 1940s. In their work, game theory was extremely limited in scope and dealt almost entirely with games limited to two actors and of the “zero sum” variety, meaning one player's losses are always the winnings of the other player. Since then game theory has been applied to a huge range of other fields, most notably economics but also in political science, evolutionary biology, computer science, management, philosophy, epidemiology, and any other discipline that involves competition among self interested agents.

Key Definitions

There are many types of games, conditions, and actors that can be studied in game theory, for completeness most if not all of those terms will be described here even if they are not needed for the applications below as they are important from a pedagogical point of view and can help better illustrate the variety of applications game theory can be useful in.

Player - a rational actor looking to maximize his own outcomes in a game (agent, actor, player, etc can all be used interchangeably and mean the same thing)

Game - a set of strategies that actors/players can undertake whose combinations can lead to different possible outcomes

Strategy Space - the total space of all possible pure strategies each player can play the game with, the ways a single player X can play the game is player X’s strategy space

Pure Strategy - a strategy is pure if it provides a definitive move to make in every possible situation

Mixed Strategy - a strategy is mixed when players assign a probability distribution to every possible pure strategy in their strategy space, mixed strategies may be difficult to understand so consider the case of a penalty shootout. The kicker has a dominant foot, so a pure strategy may be to kick with their dominant foot every time, but the goalie may then defend that side more heavily leading to a worse outcome, so by switching from foot to foot they employ a mixed strategy that creates a better outcome. [Switching observed to be the better strategy in real life by Chiappori, Levitt, and Groseclose, (2002)]

Dominant strategy - a strategy that exists for a player when they have one strategy they should always undertake to reach their optimal outcome regardless of other players’ actions

Strategy Profile - a group formed by choosing one strategy for every player

Outcome Space - the total space of all possible outcomes that can be reached in a single game

Simple Game - a game where each player has only two outcomes, winning or losing

Cooperative Games - a game is cooperative when agents can form alliances/coalitions that can not be violated, a game is noncooperative otherwise

Simultaneous Game - a game is simultaneous if players all move at the same time, or they lack knowledge of previous moves making them effectively simultaneous. If a game is not simultaneous it is considered sequential.

Symmetric Game - a symmetric game is a game in which the outcomes are determined solely based on the strategies employed, not on who is playing them. In other words, all the players are identical, an example of this type is the prisoner's dilemma which we will showcase as our prime introductory example

(In)finite Game - games that can be finished in finitely many moves are considered finite, games that can go on forever with no player being able to achieve a winning or losing strategy can be considered infinite. The games we will discuss are finite, as there is a lack of mathematically rigorous infinite games to study, however an interested reader may want to examine a potential, not so rigorous, foreign policy application of the infinite game here (https://youtu.be/0bFs6ZiynSU)

Best response correspondence - is the choice, or response, a player makes to maximize their own outcome given another player’s actions. Notation: in this project we’ll represent the better response of player i to an opposing strategy X with BRi(X)

Nash Equilibrium - a strategy profile where no player benefits from altering their chosen strategy, essentially it is a “solution” to a noncooperative game. John Nash proved in 1951 that at least one such equilibrium must exist for all games with a finite set of actions.

We can represent games with tables and matrices where each dimension represents a player and the corresponding cells represent the expected outcomes for each combination of individual players’ strategies. We can use these tables to quickly find equilibria and make best response calculations/curves. We will use representations such as these in the coming examples. Now that we've covered all the background, we'll start to make the block of definitions more concrete and interesting with the classic example of game theory, the prisoner's dilemma.

Nash Equilibrium and the Prisoner's dilemma

A strong and popular example of game theory applied to decision making is the age-old “Prisoner’s Dilemma.” In this thought experiment, the authorities have arrested two criminals, we’ll call them prisoners A and B, and are holding them in separate rooms where they cannot speak to each other or receive any indication of each other’s intended decisions. From this description and our definition above we note this game is simultaneous, as neither player is informed of the other’s actions. Next, the authorities realize they don’t have enough hard evidence to convict either prisoner so they have to rely on a confession. The prosecutor offers A a deal, if he snitches on B, he will go free if B stays silent, or serve 5 years if B also snitches on A. The same deal is offered to B. If both stay quiet they each get 2 years on a lowered charge the prosecutors can prove. Note that in this game we impose the condition that staying quiet on the basis of honor or loyalty is irrational. The outcomes are represented in the following table.

Outcome Space for Prisoner's Dilemma

Trivially, we can see that both prisoners staying quiet is the mutually ideal solution. However, we can show that the Nash equilibrium is when both prisoners snitch. If A stays quiet, he runs the risk of being imprisoned for 10 years, so it benefits him to switch to snitching, where he will either go free or serve 5 years. The same goes for B, so neither benefits from staying quiet. Sohe equilibrium is not the ideal solution, since they could both serve 2 years but without knowledge of the other prisoner’s intentions they can never choose to stay quiet. In game theory we say this situation is not Pareto efficient. An equilibrium is considered Pareto efficient or Pareto optimal when the Nash equilibrium is the ideal outcome.

Now that we’ve seen a trivial example to familiarize ourselves with the concepts, the following non-trivial applications should become more clear.


Part 2: Cournot Competition

Nash Equilibrium in Economics

In the game of economy, we are interested in the strategic interactions between players in a market/industry, and how the strategy of a player is affected by the existence of another player. In 1838, before John Nash formalized the proof of Nash Equilibrium, even before his birth, Antoine Augustin Cournot showed that a stable equilibrium exists in his model of competition between to producers, "If either of the producers, misled as to his true interest, leaves it temporarily, he will be brought back to it."

To demonstrate Cournot's model of competition, we will look into a simple example of the wall clock market of West Lafayette. Suppose Boilermaker Clockery is the only player in the market, denoted by $ BC $, and $ S_{BC} $ is the set of its possible strategies. In this case, the quantity of wall clocks produced is the only independent variable we take into consideration (we will consider price as a function of quantity), so we will use $ q \in S_{BC} $ for it. Suppose that the potential demand of wall clocks in West Lafayette is $ 20{,}000 $, and we will use a naive model

$ D(p)=20{,}000-200p $

for the demand, where $ p $ is the price of a clock and each dollar of increment in price would lead to $ 200 $ less clocks in demand. Suppose the total production cost is

$ C(q)=5q $

i.e., $ c=5 $ dollars for each clock produced, and Boilermaker Clockery will always produce enough clocks to match the demand as long as it's profitable,

$ \begin{align} q=&D(p)\\ =&20{,}000-200p \end{align} $

we will have the following function for the market unit price for each clock,

$ p(q)=\frac{20{,}000-q}{200} $

and the total revenue would be

$ \begin{align} R(q)=&p(q) \cdot q\\ =&\frac{(20{,}000-q) \cdot q}{200} \end{align} $

Since this is a monopoly, Boilermaker Clockery can pick the best strategy by maximizing the total profit

$ \begin{align} P(q)=&R(q)-C(q)\\ =&\frac{20{,}000q}{200}-\frac{q^2}{200}-5q \end{align} $

To do so, we need to know how total profit respond to change in quantity of clocks produced, a.k.a. the marginal profit,

$ \begin{align} MP(q)=&\frac{d}{dq}P(q)\\ =&\frac{20{,}000}{200}-\frac{2q}{200}-5\\ =&95-\frac{q}{100} \end{align} $

The total profit is maximized when

$ \begin{align} MP(q)=&95-\frac{q}{{100}}=0\\ q=&9500 \end{align} $

i.e., increasing production no longer generate more profit. It is obvious that the extremum is a maximum in this case, but in general, we can determine by computing and showing that the second derivative is negative,

$ \frac{d^2}{dq^2}P(q)=-\frac2{200} $

The unit price would be

$ \begin{align} p(9500)=&\frac{20{,}000-9500}{200}\\ =&52.5 \end{align} $

The maximum total profit would be

$ \begin{align} P(9500)=&9500\cdot\left(p(9500)-c\right)\\ =&9500\cdot(52.5-5)\\ =&451{,}250 \end{align} $

However, the monopoly is no longer possible, as the infamous IU Horology Inc. decides to enter the West Lafayette market. There are now two clock producers in the market, denoted by the set $ \{BC, IU\} $, and $ \forall i \in \{BC, IU\} $, let $ S_i $ be the set of strategies that

......


Part 3: Game Theory and Evolution

Game theory has had surprisingly many applications in the fields of biology, especially concerning evolution and the strategies which species employ. While species do not necessarily choose which strategies they adopt, the process of evolution results in those species adopting varied strategies. In the game of evolution, the fitness of a species determines its payoffs (the cost of a strategy subtracted from its benefits), and the goal is to slowly optimize a strategy to the best fitness possible.

To demonstrate the principles of evolutionary game theory, we will utilize lions as an example. The fitness of a lion is dependent on its efficiency of obtaining food and the number of offspring produced. When hunting, lions exert energy, which is a cost, in order to obtain food to regain energy, which is a benefit. Subtracting the cost of hunting with the benefit of food provides the profit of hunting. Maximizing this profit allows lions to exert their energy in other ways, such as defending from attackers or supporting offspring.

Lions are an example of an evolutionarily stable strategy, meaning that any small change in strategy will reduce fitness in some way. A group of lions may benefit from becoming larger by increasing strength relative to other lions, allowing for resolution of territorial disputes, but larger animals consume more energy and this strategy may increase the cost more than increasing the benefit, meaning this change in strategy reduces profit. Another group may benefit from becoming smaller by decreasing the energy spent relative to other lions, allowing for greater energy efficiency, but smaller lions may be less successful at hunting and this strategy may decrease the benefit more than decreasing the cost, again reducing profit.

Potential Profits of Different Sized Species

When all species in an environment possess an evolutionarily stable strategy, it forms a Nash equilibrium, since any change in strategy for any one player (species) will be purely detrimental, so changes in strategy do not stick around. Changes in strategy do still occur, since mutation is random, not by choice, but these changes lose out in competition with the evolutionarily stable strategy. Stable does not necessarily mean the strategy is impermeable, since changes in the environment can necessitate evolution, but so long as everything else around an evolutionarily stable species stays the same, that species will not adjust its strategy.

The Hawk-Dove Game, or Game of Chicken, is a variant of the Prisoner's Dilemma with slightly different flavoring. In this game, both players want to take some resource V. If a player chooses to be a Hawk, they fight for control of the resource; if a player chooses to be a Dove, they aim for a peaceful resolution. If two doves meet, they share equally, each receiving V/2. If a hawk and a dove meet, the hawk scares away the dove, so the hawk gets V while the dove gets 0. If two hawks meet, they fight over the resource, so their gains are reduced by some value C corresponding to the cost of fighting; therefore, they each get (V-C)/2 on average.

Territorial behaviors can be explained using the hawk-dove game. Assume we have two male lions, Alex and Bob. If Alex and Bob both act as doves, they share food peacefully. If Alex changes his strategy to become a hawk, Alex now gains all the food in the area, and Bob must find some other area to hunt in. Alex's change in strategy is strictly better than before, meaning his strategy is stable for now. Bob can increase his individual gain by also becoming a hawk, if (V-C)/2 > 0. However, if Bob stayed a dove it would increase the total resources for the lion species, since becoming a hawk decreases the total gain to V - C.

Outcome Space for Hawk-Dove Game

This results in the emergence of territorial behavior in more aggressive species due to territorial species gaining a higher payoff. If two species A and B both engage in Hawk-Dove games for territorial control, they may end up with strategies S(A) and S(B). Both A and B seek to maximize their own gains whenever possible. Species A engages in territorial behavior, so the Nash equilibrium remains at one hawk, one dove, and S(A) has a species profit of V. Species B engages in selfish behavior, so the Nash equilibrium is two hawks as both species members avoid receiving nothing, and S(B) has a species profit of V - C. Because a higher profit means more energy can be spent towards reproduction, S(A) leads to more offspring than S(B), and thus S(A) is the greater strategy. Over time, this strategy leads species A to outperform species B, leading more dominant species to adopt territorial behaviors to increase their efficiency.


Part 4: Game Theory and Elections

Game theory has widely use among human society. One example would be


References

Easley, Kleinberg, Networks, Crowds, and Markets: http://www.cs.cornell.edu/home/kleinber/networks-book/

Khan Academy, Prisoner's Dilemma: https://www.khanacademy.org/economics-finance-domain/ap-microeconomics/imperfect-competition/oligopoly-and-game-theory/v/more-on-nash-equilibrium

Mixed strategy in penalty shootouts: https://pricetheory.uchicago.edu/levitt/Papers/ChiapporiGrosecloseLevitt2002.pdf

Nash, John. “Non-Cooperative Games.” Annals of Mathematics, vol. 54, no. 2, 1951, pp. 286–95. JSTOR, https://doi.org/10.2307/1969529. Accessed 26 Nov. 2022.

Stanford Encyclopedia of Philosophy, Game Theory: https://plato.stanford.edu/entries/game-theory/#Mot

Stanford Encyclopedia of Philosophy, Evolutionary Game Theory: https://plato.stanford.edu/entries/game-evolutionary/

University of Illinois's CS440 Artificial Intelligence, Prisoner's Dilemma: https://courses.engr.illinois.edu/ece448/sp2020/slides/lec35.pdf

University of Maryland's ECON414 Game Theory, Simultaneous Games: https://terpconnect.umd.edu/~dvincent/econ414/lec04.pdf

Wikipedia, Prisoner's Dilemma Table: https://en.wikipedia.org/wiki/Prisoner%27s_dilemma

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett