is_optimal_stochastic_mst_strategy
A strategy T is an optimal strategy solving the adaptive MST identification problem for graph G with edge probabilities p if T solves the MST-ID problem for G and for every strategy T' that solves the MST-ID problem for G, the expected cost of T under p is at most the expected cost of T' under p.
Statement
def is_optimal_stochastic_mst_strategy {V : Type*} [DecidableEq V] (G : SimpleGraph V) (p : Sym2 V → ℝ) (T : StochasticMstStrategy (Sym2 V)) : Prop
- Defined in
- arXiv:2610.40844 Section 2.1 & Lemma 3.2
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Built on 3
- stochastic_mst_solvesA strategy T solves the adaptive MST identification problem for G if it solves the problem starting from the empty state of contracted and…
- stochastic_mst_strategy_costFor an edge probability function p assigning each edge e the probability that e has weight 1, the expected number of queries of a strategy…
- StochasticMstStrategyAn adaptive strategy for binary stochastic MST identification is a binary decision tree on a type of edges: either a leaf (no further…
Read back from the Lean
For a simple graph G on vertex type V (with decidable equality), an edge probability/weight function p : Sym2 V → ℝ, and a decision tree strategy T : StochasticMstStrategy (Sym2 V), is_optimal_stochastic_mst_strategy G p T asserts that:
1. T solves the stochastic MST problem for G (stochastic_mst_solves G T), and
2. For all strategies T' : StochasticMstStrategy (Sym2 V), if T' solves the stochastic MST problem for G (stochastic_mst_solves G T'), then the expected cost of T under p is less than or equal to the expected cost of T' under p (stochastic_mst_strategy_cost p T ≤ stochastic_mst_strategy_cost p T').
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A strategy is optimal for an instance (G, p) if it solves MST-ID and minimizes expected cost. -/ def is_optimal_stochastic_mst_strategy {V : Type*} [DecidableEq V] (G : SimpleGraph V) (p : Sym2 V → ℝ) (T : StochasticMstStrategy (Sym2 V)) : Prop := stochastic_mst_solves G T ∧ ∀ T' : StochasticMstStrategy (Sym2 V), stochastic_mst_solves G T' → stochastic_mst_strategy_cost p T ≤ stochastic_mst_strategy_cost p T'