The hindsight optimum dominates every assignment rule
ProvedSoar.hindsight_dominatesStanding conventions. Throughout, (demand weight vectors) and (supply feature vectors) are measurable spaces, and are probability measures on them, and the match quality function is jointly measurable and bounded, for all . Expectations over i.i.d. demand units and independent i.i.d. supply units are integrals against the product measure on . The hindsight optimum value is
with the symmetric group, and the limiting hindsight optimum is .
Let be any probability space of auxiliary randomness, and let be any measurable assignment rule which, given the realized demand tuple , the realized supply tuple and a point , returns a permutation (demand is matched to supply ). Then
Role. A dynamic matching policy in the paper's sense assigns supply to each arriving demand unit as a possibly randomized function of the history; its realized assignment is one such rule , so the statement gives for every policy, the inequality Appendix A calls straightforward. It applies in particular to SOAR and to the hindsight-optimal algorithm itself, for which it is an equality.
Formalization Note The rule is allowed to depend on all of and (an anticipative rule), which is more general than the paper's non-anticipative policies; the inequality is pointwise, so the generality costs nothing. Randomization is modelled through the auxiliary probability space, which may be trivial. The measurability of into the discrete -algebra of and the boundedness of make the integrand integrable; the case reads .
import Mathlib import Definitions.Def_SoarModel open MeasureTheory open scoped BigOperators
namespace Soar
theorem hindsight_dominates {X Y Ω : Type*} [MeasurableSpace X] [MeasurableSpace Y]
[MeasurableSpace Ω] (P : Measure X) (Q : Measure Y) (μ : Measure Ω)
[IsProbabilityMeasure P] [IsProbabilityMeasure Q] [IsProbabilityMeasure μ]
(φ : X → Y → ℝ) (hφ : Measurable (Function.uncurry φ)) (C : ℝ) (hC : SoarBounded φ C)
(n : ℕ) (τ : (Fin n → X) × (Fin n → Y) → Ω → Equiv.Perm (Fin n))
(hτ : Measurable (Function.uncurry τ)) :
(∫ q, ∑ t, φ (q.1.1 t) (q.1.2 (τ q.1 q.2 t)) ∂(SoarPairMeasure P Q n).prod μ) / n
≤ SoarHindsight P Q φ n := by
sorry
end SoarRead-back
What the Lean code literally says, in plain math · claude-fable-5-1
Binders and hypotheses. Let , and be arbitrary types, each equipped with a -algebra. Let be a measure on , a measure on and a measure on , all three assumed to be probability measures (which forces nonempty and makes the measures -finite). Let be such that is measurable for the product -algebra on . Let with
(so necessarily ). Let be a fixed natural number, allowed. Let
be a map (given in curried form: for each pair and each , a permutation ), and assume is measurable, where carries the discrete -algebra in which every subset is measurable. Concretely this means: for every permutation the set belongs to the product -algebra of (the product -algebra on ) and (the -algebra on ). Note that is allowed to depend on the entire tuple , the entire tuple , and .
Definitions unfolded. With (a maximum over a finite set; ), on , and
(Bochner integral, value if not integrable; by the convention ).
Conclusion. For the fixed and ,
where the integration measure on the left is the product of (first factor) with (second factor), the integrand at the point is the assignment value of the permutation (position of is paired with position of ), the integral is a Bochner integral (value if the integrand is not integrable), and the division by follows the convention . Edge case: for both sides are and the inequality reads . The inequality is non-strict ().