Normal-form game

From Theory

Notes for CS 8803 - Game Theory and Computer Science. Spring 2008

A normal-form game $G = (N,A = \times_{i=1}^N A_i, u: A \rightarrow \reals^N)$ consists of an integer number of players $N \geq 1$ , action sets $A i$ (not necessarily finite), the set of action profiles $A = A_1 \times A_2 \times \ldots \times A_N$ , and a payoff function (also called utility function) $u:A \rightarrow \reals^N$ , where,

$u(a_1,a_2,\ldots,a_N) = \left(u_1(a_1,\ldots,a_N),\ldots,u_N(a_1,\ldots,a_N),\right).$

This is meant to model a game in which each of $N$ players simultaneously picks an action $a_i\in A_i$ from their respective set of actions. The payoff to player $i \leq N$ is then $u i (a)$ , where the action profile is the vector of actions $a=(a_1,\ldots,a_N) \in A.$

[edit]

Mixed strategies

A mixed strategy is a randomized strategy for playing the game. Let $Δ i$ denote the set of probability distributions over $A i$ . Let $\Delta = \Delta_1 \times \Delta_2 \ldots \times \Delta_N$ . Each $\sigma_i \in \Delta_i$ is called a mixed strategy, and reflects a randomized choice of actions. A pure strategy is a probability distribution that assigns probability 1 to one action. Given mixed strategy profile $\sigma=(\sigma_1,\ldots,\sigma_N) \in \Delta$ , the payoff function $u$ is extended to $Δ$ by expected value,

$u(\sigma_1,\ldots,\sigma_N) = {\mathbb E}_{a_1 \sim \sigma_1,\ldots,a_N\sim\sigma_N}[u_i(a_1,\ldots,a_N)].$

Here, each $a i$ is drawn independently from its respective probability distribution.

Note that in the case where $A i$ is infinite, to be formally correct one would need to use Measure theory, but I'm not going to get into that. Deal with it!

The production of this material was supported in part by NSF award SES-0734780.

Retrieved from "http://wiki.cc.gatech.edu/theory/index.php/Normal-form_game"

Normal-form game

From Theory

Mixed strategies

Views

Personal tools

Navigation

Search

Toolbox