next up previous
Next: Nash Equilibrium Up: Models, Algorithms and Economics Previous: Competitive Equilibrium

  
Game Theory

The definitions are from the book [#!MWG95!#]. A game consists of players, rules, outcomes, and payoffs. The strategies of a player are the decision rules that specify how a player will act in every possible scenario. In other words, strategy is a function from the set of scenarios to an action. A pure strategy (or deterministic) specifies a fixed action, given a specific scenario. Let Si be the set of pure strategies for the player i. A mixed strategy (random) for a player i is a function $\sigma_i:S_i \rightarrow
[0,1]$ such that for each pure strategy $s_i\in S_i$, a probability $\sigma_i(s_i) \ge 0$ is assigned, that this strategy will be taken. Moreover $\sum_{s_i\in S_i}\sigma_i(s_i)=1$. Observe that the set of mixed strategies for a player forms a simplex. Let Si consists of M pure strategies, then the Simplex is


Denote by $\Gamma=[I,\{S_i\},\{u_i(.)\}]$, the game with I players, each with strategy set Si, and a payoff function $u_i(s_1,s_2,\cdots,s_I)$ depending upon the outcomes arising from strategies $(s_1,\cdots,s_I)$. Profile for player i's opponent's is denoted by s-i=(s1, s2, ..., si-1, si+1, ..., sI).

Consider the following game called Prisoner's Dilemma. In fact you can play a variant of this game on the web! See the following web-site. Two people are held as prisoners in separate cells for a possible involvement in a fraud. If both of them confess then they get 5 years in the prison. If one confesses and other doesn't then the first one gets 1 year and the other one 10 years, and if neither of them confess then each gets 2 years. Of course the objective of each of them is to minimize their time in the prison. Here is the payoff table (notice that the utility is the negative of the number of years in the prison).

    Prisoner 2  
    Don't Confess Confess
  Don't Confess -2, -2 -10, -1
Prisoner 1      
  Confess -1, -10 -5, -5

A strategy $s_i\in S_i$ is called dominant for a player i if for all $s'_i \in S_i$, $u_i(s_i, s_{-i}) \ge u_i(s'_i, s_{-i})$. In the Prisoner's Dilemma example, the strategy (confess, confess) is dominant! The reason is as follows: Considering Player 1. Let Player 2 plays Don't Confess. Then utility for Player 1 is highest by playing Confess (-1 v/s -2). Similarly if Player 2 plays Confess, then utility for Player 1 is highest by playing Confess (-5 v/s -10). Therefore Confess is the dominant strategy for Player 1. By symmetry, Confess is the dominant strategy for Player 2, as well.

Similarly we can define dominant mixed strategies for player i. A strategy $\sigma_i$ is a dominant strategy for player i if $u_i(\sigma_i, \sigma_{-i}) \ge u_i(\sigma'_i, \sigma_{-i})$, for all $\sigma'_i\in \Delta(S_i)$ and $\sigma_{-i}\in
\Pi_{j\not=i}\Delta(S_j)$.


next up previous
Next: Nash Equilibrium Up: Models, Algorithms and Economics Previous: Competitive Equilibrium
Anil Maheshwari
2003-03-05