Nash Equilibria-public

dg-publish	permalink	tags
true	/public/nash-equilibria/	gardenEntry
Tue, 15/04/2025 19:47

Nash Equilibria under public Sat 22 Mar 2025 13:36:00 Note: Edit to permalink

Nash Equilibria under public
Tue, 15/04/2025 19:47

Understanding Nash Equilibria

What is said about finding Nash equilibria?

I understand that the equilibria cannot be anticipated.

How is this explained mathematically and logically

The process of finding Nash equilibria in game theory is both mathematically and computationally intricate. Here's how this complexity is explained mathematically and logically:

Mathematical Explanation

Definition of Nash Equilibrium:

A Nash equilibrium occurs when no player can improve their payoff by unilaterally changing their strategy, given the strategies chosen by others. Mathematically, for a strategy profile $s = (s_{1}, s_{2}, \dots, s_{n})$ , it satisfies:

u_{i} (s_{i}, s_{- i}) \geq u_{i} (s_{i}^{'}, s_{- i}) \forall s_{i}^{'} \in S_{i}

where $u_{i}$ is the utility function of player $i$ , $S_{i}$ is the strategy set for player $i$ , and $s_{- i}$ represents the strategies of all other players.

Existence Proof via Fixed-Point Theorems:
Nash's theorem guarantees the existence of at least one mixed-strategy Nash equilibrium in finite games. This proof relies on Brouwer's fixed-point theorem, which states that any continuous function mapping a compact convex set to itself has a fixed point. However, Brouwer's theorem is nonconstructive, meaning it assures existence but does not provide a method to find the equilibrium.
Combinatorial Nature:
While the definition appears rooted in continuous mathematics (due to mixed strategies), finding a Nash equilibrium is fundamentally combinatorial. It involves identifying supports (sets of pure strategies with nonzero probabilities) for each player and solving a system of equations that ensures expected utilities are equal across these supports.
Nonconvex Constraints:
The problem of finding a Nash equilibrium involves solving nonconvex constraints, making it significantly harder than related problems like finding correlated equilibria (which can be solved using linear programming).
Nonconvexity adds to the mathematical complexity and computational intractability.

Changing Nights