Game theory: proof V is convex and compact

1k Views Asked by At

Consider a non-cooperative game $(N,S_i,u_i)$.

$\bullet \ N = \{1,...,n\}$ is the set of players.

$\bullet$ For every player $i$, the set $S_i$ is the finite set of pure strategies.

$\bullet$ For every player $i$, the function $u_i: (S_1 \times ... \times S_n) \to \mathbb{R}$ is the utility function of $i$.

A belief of player $i$ about the opponents' choices is a probability distribution $\beta_i \in \Delta S_{(-i)}$, with: $$S_{-i} := S_1 \times ... \times S_{i-1} \times S_{i+1} \times ... \times S_n$$

Suppose that player $i$ has belief $\beta_i$ about the opponents' choices. Then, for every pure strategy $s_i$ he can choose, the corresponding expected utility would be given by: $$U_i(s_i,\beta_i) := \sum_{s_{-i} \in S_{-i}} \beta_i (s_{-i}) u_i(s_i,s_{-i})$$

The strategy $\hat{s_i}$ is called optimal under the belief $\beta_i$ if: $$U_i(\hat{s_i},\beta_i) \geq U_i(s_i,\beta_i) \ \forall s_i \in S_i$$

The strategy $s_i$ is called rational if there is some belief $\beta_i$ about the opponents' choices under which $s_i$ is optimal. For a given belief $\beta_i$ this boils down to whether the believed utility difference vector $v(\hat{s_i},\beta_i)$ is non-negative where: $$v(\hat{s_i},\beta_i)=[U_i(\hat{s_i},\beta_i) - U_i(s_i,\beta_i)]_{s_i \in S_i} \in \mathbb{R}^{|S_i|}$$

Let this be the set of all believed utility difference vectors: $$V_i(\hat{s_i})=\{v(\hat{s_i},\beta_i)\ |\ \beta_i \in \Delta (S_i)\}$$


Is there anyone here who can help me with proving that $V_i(\hat{s_i}$ is convex and compact? So far we've only had a introductory course in game theory, mostly about nash equilibria and determining strategies from matrices... Im quite overwhelmed by the first question of our follow-up course...

This is all I know:

A set is compact $\leftrightarrow$ every sequence in the set has a convergent subsequence which converges to a element in that set.

We can assume $\Delta (S_{-i})$ is compact.

So, actually we only have to prove that a continuous function transforms a compact domain into a compact image, but how?

Anything would be appreciated!!

----EDIT----

Is this enough for convexity:

$V_i(\hat{s_i})$ is convex if for any $v(\hat{s_i},\beta_i),w(\hat{s_i},\beta_i) \in V_i(\hat{s_i})$ the point $t \cdot v + (1-t) \cdot w \in V_i \ \forall \ t \in [0,1]$.

$t \cdot v(\hat{s_i},\beta_i) + (1-t) \cdot w(\hat{s_i},\beta_i)$

=>

$t \cdot [U_i(\hat{s_i},\beta_i) - U_i(s_i,\beta_i)] + (1-t) \cdot [U_i(\hat{s_i},\beta_i) - U_i(s_i,\beta_i)]$

=> $[U_i(\hat{s_i},\beta_i) - U_i(s_i,\beta_i)]= a$

$t \cdot a + (1-t) \cdot a = a \in V_i$