is irreducible and aperiodic and has a unique stationary distribution
ProvedYoungConventions.RiskDominance.perturbed_irreducible_aperiodicmarkov-chainp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-stability
Let be a finite -person game with nonempty strategy sets, let , let be a best-reply distribution for sample size , and let be an admissible experimentation (, of full support). Let with for all . Then the perturbed process of (2) satisfies:
- is a stochastic matrix (nonnegative entries, rows summing to );
- for all states (all players may experiment for periods in succession), so is irreducible;
- for every state ; together with item 2 the process returns to in exactly and in exactly periods, so it is aperiodic;
- has exactly one stationary distribution , .
This makes the stationary distribution in the definition of stochastic stability well defined.
Preamble
import Mathlib import Definitions.Def_YoungConventions_AdaptivePlay_History import Definitions.Def_YoungConventions_RiskDominance_IsBestReplyDistribution import Definitions.Def_YoungConventions_RiskDominance_IsExperimentation import Definitions.Def_YoungConventions_RiskDominance_perturbed import Definitions.Def_YoungConventions_RiskDominance_IsStationaryDistribution open Filter Topology
Formal statement
namespace YoungConventions.RiskDominance
/-- **`P^ε` is a regular (irreducible, aperiodic) chain with a unique stationary distribution.**
Young (1993), The Evolution of Conventions, Econometrica 61:57–84, §6, pp. 67–68 (PDF pp. 12–13): "Let `h` and `h′` be two distinct states. If `P^ε` is in state
`h` at time `t`, there is a positive probability that all players will experiment for `m` periods in
succession. Thus there is a positive probability that the process arrives at state `h′` at time
`t + m`, so `P^ε` is irreducible. It is aperiodic because the process can move from `h` to `h` in
exactly `m` periods, and also in exactly `m + 1` periods. Hence `P^ε` has a unique stationary
distribution `μ^ε` satisfying the equation `μ^εP^ε = μ^ε`."
For every game, `1 ≤ k ≤ m`, best-reply distribution `p`, admissible `(λ, q)` and `ε > 0` with
`ελᵢ ≤ 1`: `P^ε` is row-stochastic, every entry of `(P^ε)^m` is positive, every diagonal entry of
`(P^ε)^{m+1}` is positive, and `P^ε` has exactly one stationary distribution.
**Formalization Note.** "Irreducible" is stated in the form the page proves, `(P^ε)^m_{hh′} > 0` for
all `h, h′` (including `h = h′`), and "aperiodic" as the return to `h` in exactly `m` and `m + 1`
steps; together these say `P^ε` is primitive. The admissible range of `ε` is `0 < ε` with
`ελᵢ ≤ 1` for all `i`, the range on which (2) is a transition matrix. -/
theorem perturbed_irreducible_aperiodic {ι : Type*} [Fintype ι] [DecidableEq ι] {S : ι → Type*} [∀ i, Fintype (S i)]
[∀ i, DecidableEq (S i)] [∀ i, Nonempty (S i)]
(u : ι → ((i : ι) → S i) → ℝ) (k m : ℕ) [NeZero m] (hk : 1 ≤ k) (hkm : k ≤ m)
(p q : (i : ι) → YoungConventions.AdaptivePlay.History S m → S i → ℝ) (lam : ι → ℝ)
(hp : IsBestReplyDistribution u k p) (hq : IsExperimentation lam q)
(ε : ℝ) (hε : 0 < ε) (hεlam : ∀ i, ε * lam i ≤ 1) :
perturbed p q lam ε ∈ Matrix.rowStochastic ℝ (YoungConventions.AdaptivePlay.History S m) ∧
(∀ h h' : YoungConventions.AdaptivePlay.History S m, 0 < (perturbed p q lam ε ^ m) h h') ∧
(∀ h : YoungConventions.AdaptivePlay.History S m, 0 < (perturbed p q lam ε ^ (m + 1)) h h) ∧
∃! μ : YoungConventions.AdaptivePlay.History S m → ℝ, IsStationaryDistribution μ (perturbed p q lam ε) := by sorry
end YoungConventions.RiskDominance
Source
Young (1993), The Evolution of Conventions, Econometrica 61:57–84, §6, pp. 67–68
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.