AFTD Auto-Formalizing Theoretical Domains

is_optimal_stochastic_mst_strategy

def

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'
See it in the graphDiscuss this resultChallenge it