Prove Nash equilibrium existence in finite games using Kakutani's fixed point theorem.…
- User
Prove Nash equilibrium existence in finite games using Kakutani's fixed point theorem. Define the best response correspondence and show it's upper hemicontinuous and convex-valued satisfying fixed point conditions.
- Assistant
Detailing best response correspondence proof
The best response correspondence maps mixed strategy profiles within compact convex simplices to nonempty closed convex sets and has a closed graph, establishing upper hemicontinuity. This satisfies Kakutani's fixed point conditions, yielding a mixed-strategy Nash equilibrium in finite games.Confirming upper hemicontinuity via argmax properties
The best response correspondence arises as the argmax of continuous linear functions over compact simplices, guaranteeing nonempty convex closed values and upper hemicontinuity by the closed graph property; this confirms Kakutani’s conditions and completes the Nash equilibrium existence proof. Let (I={1, \ldots, n}) be the set of players. For each (i \in I), let (S_{i}=\left{s_{i}^{1}, \ldots, s_{i}^{k_{i}}\right}) be the finite set of pure strategies of player (i). Let (\Sigma_{i}) be the set of probability distributions on (S_{i}); we identify each element (\alpha_{i} \in \Sigma_{i}) with an element of the standard (\left(k_{i}-1\right))-dimensional simplex in (\mathbb{R}^{k_{i}}). Put (\Sigma=\prod_{i \in I} \Sigma_{i}). Then (\Sigma) is a nonempty convex compact subset of the Euclidean space (\mathbb{R}^{m}), with (m=\sum_{i=1}^{n} k_{i}).
If (\sigma=\left(\sigma_{i}\right)_{i \in I} \in \Sigma), the expected payoff of player (i) is
[ u_{i}\left(\sigma_{1}, \ldots, \sigma_{n}\right)=\sum_{s \in S} u_{i}(s) \sigma_{1}\left(s_{1}\right) \cdots \sigma_{n}\left(s_{n}\right) ]
where (S=\prod_{i=1}^{n} S_{i}) and (s=\left(s_{1}, \ldots, s_{n}\right)). For each (i \in I) define the set-valued function (B_{i}: \prod_{j \neq i} \Sigma_{j} \longrightarrow 2^{\Sigma_{i}}) by
[ B_{i}\left(\sigma_{-i}\right)=\left{\sigma_{i} \in \Sigma_{i}: u_{i}\left(\sigma_{i}, \sigma_{-i}\right) \geqslant u_{i}\left(\sigma_{i}^{\prime}, \sigma_{-i}\right) \text { for all } \sigma_{i}^{\prime} \in \Sigma_{i}\right} . ]
Each (B_{i}\left(\sigma_{-i}\right)) is nonempty because the maximum of a continuous function on a compact set is attained. Each (B_{i}\left(\sigma_{-i}\right)) is convex (it is the face of a simplex on which a linear function is maximal) and closed. Since (\prod_{j \neq i} \Sigma_{j}) is compact, the continuity of (u_{i}) implies that the graph of (B_{i}) is closed; hence (B_{i}) is upper hemicontinuous. Define a set-valued function (B: \Sigma \longrightarrow 2^{\Sigma}) by
[ B(\sigma)=\prod_{i \in I} B_{i}\left(\sigma_{-i}\right) . ]
The value (B(\sigma)) is nonempty, convex and closed. The graph of (B) is the intersection of the closed sets (\left{(\sigma, \sigma') \in \Sigma \times \Sigma: \sigma'{i} \in B{i}\left(\sigma_{-i}\right)\right}); hence (B) is upper hemicontinuous.
Thus (B) satisfies the conditions of Kakutani's fixed point theorem. There exists (\sigma^{} \in \Sigma) such that (\sigma^{} \in B\left(\sigma^{}\right)). This means that (\sigma_{i}^{} \in B_{i}\left(\sigma_{-i}^{}\right)) for each (i), that is, each (\sigma_{i}^{}) is a best response to (\sigma_{-i}^{}). Hence (\sigma^{}) is a Nash equilibrium.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.