==== Game Theory - Nash Equilibrium ====


Author: Marcin Jędrzejczyk

Supervisor: mgr inż. Mateusz Ślażyński


==== Basics ====

=== Strategy ===
 
A strategy defines a set of moves or actions a player will follow in a given game. A strategy must be complete, defining an action in every contingency, including those that may not be attainable in equilibrium. For example, a strategy for the game of checkers would define a player's move at every possible position attainable during a game. Such moves may be random, in the case of mixed strategies.

**strategy=/=move**

The strategy concept is sometimes (wrongly) confused with that of a move. A move is an action taken by a player at some point during the play of a game (e.g., in chess, moving white's Bishop a2 to b3). A strategy on the other hand is a complete algorithm for playing the game, telling a player what to do for every possible situation throughout the game.

=== Payoff ===

In any game, payoffs are numbers which represent the motivations of players. Payoffs may represent profit, quantity, "utility," or other continuous measures (cardinal payoffs), or may simply rank the desirability of outcomes (ordinal payoffs). In all cases, the payoffs must reflect the motivations of the particular player.

=== Player ===
Any participant in a game who  has a nontrivial set of strategies (more than one) and selects among the strategies based on payoffs. If a player is non-strategic, selecting strategies randomly, the player is named  a nature player.




==== How to represent a game ====

- **matrices** - we use it to show players payoffs, according to combination of players moves


|	   |                 ^ Player 2              ||
|	   |                 | Action C | Action D |
^ Player 1 | Action A	     | 1,5	| 0,0      |
|   :::    | Action B	     | 7,9	| 2,6      |



- **game tree** - it is build from players moves, leafs hold payoffs values
 
{{:pl:dydaktyka:dss:projects:equilibrium:gametree.png?nolink&600|}}


**For every game tree, there is only one way to represent it using matrix.

But for every matrix, there are multiple ways to represent it using a game tree.**


**Exercise 1:** Create a payoff matrix for game where 2 players bet on coin toss result.


==== More than basics ====


**Pure strategy** - a pure strategy provides a complete definition of how a player will play a game. In particular, it determines the move a player will make for any situation he or she could face. A player's strategy set is the set of pure strategies available to that player.
**Mixed strategy** - a mixed strategy is an assignment of a probability to each pure strategy. This allows for a player to randomly select a pure strategy. Since probabilities are continuous, there are infinitely many mixed strategies available to a player.
Of course, one can regard a pure strategy as a degenerate case of a mixed strategy, in which that particular pure strategy is selected with probability 1 and every other strategy with probability 0.
A totally mixed strategy is a mixed strategy in which the player assigns a strictly positive probability to every pure strategy. (Totally mixed strategies are important for equilibrium refinement such as trembling hand perfect equilibrium.) A player would only use a mixed strategy when he is indifferent between several pure strategies, and when keeping the opponent guessing is desirable - that is, when the opponent can benefit from knowing the next move.

			
**Nature player** is a participant in a game who selects from among her strategies randomly, based on some predetermined probability distribution, rather than strategically, based on payoffs. Simply, a nature player allows the introduction of uncertainty or randomness into a game.


**
Dominated strategy** - a strategy is dominated if, regardless of what any other players do, the strategy earns a player a smaller payoff than some other strategy. Hence, a strategy is dominated if it is always better to play some other strategy, regardless of what opponents may do. If a player has a dominant strategy than all others are dominated, but the converse is not always true. A strictly dominant strategy is always played in equilibrium, and thus strictly dominated strategies never are. For example, in the prisoner's dilemma, each player has a dominated strategy. Equilibrium exist with weakly dominated strategies, however.

**Weakly dominant strategy** - a strategy is weakly dominant if, regardless of what any other players do, the strategy earns a player a payoff at least as high as any other strategy, and, the strategy earns a strictly higher payoff for some profile of other players' strategies. Hence, a strategy is weakly dominant if it is always at least as good as any other strategy, for any profile of other players' actions, and is strictly better for some profile of others' strategies. If a player has a weakly dominant strategy, than all others are weakly dominated. If a strategy is always strictly better than all others for all profiles of other players' strategies, than it is strictly dominant.




**Strictly dominant strategy**- a strategy is strictly dominant if, regardless of what any other players do, the strategy earns a player a strictly higher payoff than any other. Hence, a strategy is strictly dominant if it is always strictly better than any other strategy, for any profile of other players' actions. If a player has a strictly dominant strategy, than he or she will always play it in equilibrium. Also, if one strategy is strictly dominant, than all others are dominated. For example, in the prisoner's dilemma, each player has a strictly dominant strategy.


==== Main topic - Equilibrium: ====

 
=== Equilibrium ===

{{:pl:dydaktyka:dss:projects:equilibrium:xkcd.png?nolink|}}

An equilibrium, (or Nash equilibrium, named after John Nash) is a set of strategies, one for each player, such that no player has incentive to unilaterally change his action. Players are in equilibrium if a change in strategies by any one of them would lead that player to earn less than if she remained with his current strategy. For games in which players randomize (mixed strategies), the expected or average payoff must be at least as large as that obtainable by any other strategy.


Other definitions to better grasp it
1.	Technically, a Nash equilibrium is a set of strategies, one for each player, such that no player has incentive to change his or her strategy given what the other players are doing. 
2.	Practically speaking, a Nash equilibrium is a law that no one has incentive to break even in the absence of an effective police force. In a sense, these laws are self-enforcing.
3.	Following traffic signals is an example of Nash equilibrium at work. When another car is speeding toward you, you do not stop at the red light because a police officer will give you a ticket if you go. You stop because you do not want to die.

=== Equilibrium Refinement ===

An equilibrium refinement provides a way of selecting one or a few equilibriums from among many in a game. Many games may contain several Nash equilibriums, and thus offer no clear prediction about the likely outcome. Each refinement attempts to define some equilibriums as "more likely," "more rational" or "more robust" to deviations by players than others. For example, if one equilibrium Pareto dominates another (results in all players earning more ), then it may be viewed as more likely to be chosen by the players.

<fc #fffff></fc>

**QUESTION 1:** What is the equilibrium of the below  game?
|         |    ^	Player 2 ||
|         |    |  X    | Y       |
^ Player 1 |   A  <fc #ffffff>spja</fc> |	10 , 10 | 15 ,  5 |
| :::     |    B  <fc #ffffff>scja</fc> | 5 , 15  | 12 , 12 |
		
			
			
			


**Real life example**
Consider following situation: there are two convenient stores right next to your house, your Nash Strategy when buying milk in the morning would be to go to the cheapest store, given each store’s price. And similarly, the Nash Strategy for the storekeeper would be to price their milk just below their competitor in order to attract you, given their competitor’s price and your strategy of going for the cheapest store.

{{:pl:dydaktyka:dss:projects:equilibrium:fun.png?nolink|}}

=== Others equilibriums: ===


== Stackelberg Equilibrium ==

Consider a situation where an agent is a central public authority (police, government, etc.) that needs to design and publish a policy that will be observed and reacted to by other agents.

•	the leader – publicly commits to a strategy
•	the follower(s) – play a Nash equilibrium with respect to the commitment of the leader

Stackelberg equilibrium is a strategy profile that satisfies the above conditions and maximizes the expected utility value of the leader.

==Correlated Equilibrium ==

Correlated equilibrium is a solution concept that is more general than the well known Nash equilibrium. The idea is that each player chooses their action according to their observation of the value of the same public signal. A strategy assigns an action to every possible observation a player can make. If no player would want to deviate from the recommended strategy (assuming the others don't deviate), the distribution is called a correlated equilibrium.



//Interesting note//
One of the advantages of correlated equilibrium is that they are computationally less expensive than Nash equilibrium. This can be captured by the fact that computing a correlated equilibrium only requires solving a linear program whereas solving a Nash equilibrium requires finding its fixed point completely. Another way of seeing this is that it is possible for two players to respond to each other's historical plays of a game and end up converging to a correlated equilibrium

**QUESTION 2:** How many equilibriums (in pure strategies) does the following  game have?
	


|          |            ^ Player 2                                     |||
|          |            |Rock	        | Paper         |	Scissors |
^ Player 1 | Rock	| 0 ,  0	|-1 ,  1	| 1 , -1         |
| :::      | Paper	| 1 , -1	| 0 ,  0	|-1 ,  1         |
| :::      | Scissors	| -1 ,  1	| 1 , -1	| 0 ,  0         |

		
				
				
				
				

==== Tools ====

**Gambit** (requires installation) is an open-source collection of tools for doing computation in game theory. With Gambit, you can build, analyze, and explore game models.   
http://www.gambit-project.org/

**Game Theory Explorer** (web based, requires to enable flash in browser) http://gte.csc.liv.ac.uk/gte/builder/
























==== DESCRIPTION OF PRISON DILEMMA ====


**Players:**

- Prisoner 1 

- Prisoner 2

**Strategies:**

Prisoner 1 and 2: { Silence, Talks}

**Payoffs:**

If both remain silence both get 1 year in jail.

If both talks both get 5 years in jail.

If one talk and other is salience, the talkative is free while his colleague get 10 years in jail.

**Equilibrium:**

Nash Equilibrium is {P1 talks, P2 talks}(-5,-5), because in such combination none of the prisoners can get better result with only changing his action.

And why {P1 talks, P2 talks} is not a Nash Equilibrium. If Prisoner 1 remain silent, Prisoner can easily start talking and change his -1 to 0 (however it leaves Prisoner 1 with -10).

**Array representation**

|	      |         ^ Prisoner 2       ||
|	      |         |  Talks |  Silence | 
| Prisoner 1  | Talks	| -5,-5	 |  0,-10   |
|   :::       | Silence	| -10,0  |  -1,-1   |

**Tree representation**
 TODO dodać zdjęcie


You can try if you could outwit your partner in crime in a simple game:
http://www.gametheory.net/Mike/applets/PDilemma/Pdilemma.html


Let's see how we can work with Game Theory Explorer:
 Ordered List Item
  -	Go to http://gte.csc.liv.ac.uk/gte/builder/ and activate flash

  - Click Strategic Form and then "Click to edit",  

{{:pl:dydaktyka:dss:projects:equilibrium:punkt2.png?nolink|}}

  -  Now we are ready to model a game, write payoffs and strategy names for each player, then click "Confirm changes and align payoffs"
 

{{:pl:dydaktyka:dss:projects:equilibrium:punkt3.png?nolink|}}


  - You can also see how you game looks in tree form and matrix layout.
 
{{:pl:dydaktyka:dss:projects:equilibrium:punkt4a.png?nolink|}}

{{:pl:dydaktyka:dss:projects:equilibrium:punkt4b.png?nolink|}}
 

  - Now you can use Game Explorer to run your model and find Equilibrium.
 
{{:pl:dydaktyka:dss:projects:equilibrium:punkt5.png?nolink|}}


**Exercise 2**: BATTLE OF THE SEXES
 A couple, Adam and Beth, decide independently whether to go to a soccer game or to the ballet in the evening. Each person likes to do something together with the other, but the man prefers soccer, and the woman prefers ballet.

Propose players payoffs(at least 2) and check if they have equilibrium.

**Exercise 3:** 
Create model of rock, paper, scissors , lizard, Spock game for two players and check if it have equilibrium.


{{:pl:dydaktyka:dss:projects:equilibrium:rockpaperscissorslizardspock.jpg?nolink&600|}}

**Exercise 4:**
Think about how we can represent exam as a game between teacher and student. Please prepare your model and check if there is equilibrium.



If you want to see how already mentioned games look like in game theory explorer, you can use already prepared files:

{{:pl:dydaktyka:dss:projects:equilibrium:open.png?nolink&400|}}

{{ :pl:dydaktyka:dss:projects:equilibrium:exam.xml |}}

{{ :pl:dydaktyka:dss:projects:equilibrium:battleofsexes1.xml |}}

{{ :pl:dydaktyka:dss:projects:equilibrium:battleofsexes2.xml |}}

{{ :pl:dydaktyka:dss:projects:equilibrium:prison_dilemma.xml |}}

{{ :pl:dydaktyka:dss:projects:equilibrium:rockpaperscissors.xml |}}

{{ :pl:dydaktyka:dss:projects:equilibrium:rockpaperscissorslizardspock.xml |}}















==== Bibliography: ====

https://www.youtube.com/watch?v=IwBUXH-L4yQ

https://www.economics.utoronto.ca/osborne/2x3/tutorial/NEFEX.HTM

http://www.gambit-project.org/

http://www.gametheory.net/

http://www.thelondonglobalist.org/how-game-theory-affects-your-everyday-life/

http://gametheory101.com/courses/game-theory-101/what-is-a-nash-equilibrium/

http://gte.csc.liv.ac.uk/gte/builder/

http://www.econport.org/content/handbook/gametheory/useful/equilibrium/nashpure.html

http://www.mikeshor.com/courses/gametheory/quizzes/quiz1.html

http://www.mikeshor.com/courses/gametheory/quizzes/quiz3.html