§4, p. 6 — the service probabilities of a truthful mechanism satisfy Σ_{i∈S} q^M_i ≤ rank(S)
ProvedCHMSPricing.SpmPartition.sum_servProb_le_rankLet be a truthful mechanism for a downward-closed feasibility constraint , and let be the probability that serves agent . Then for every set of agents
where is the size of a largest feasible subset of .
For a partition matroid with part of capacity this gives , the constraint on the probabilities used in Appendix C.2 ( for one unit, for units).
Formalization Note The page states the chain ; with densities , so only the second inequality is stated. Only feasibility and measurability of are used, but the hypothesis is the full truthfulness bundle, matching the page's setting. Values: each value distribution is given by a density that is measurable and strictly positive on a bounded interval with , integrates to there and puts no mass outside (the paper says only "distribution function with density ").
import Mathlib import Definitions.Def_CHMSPricing_SpmPartition_ValueDist import Definitions.Def_CHMSPricing_SpmPartition_SetSystem import Definitions.Def_CHMSPricing_SpmPartition_Mechanism
namespace CHMSPricing.SpmPartition
theorem sum_servProb_le_rank {ι : Type*} [Fintype ι] [DecidableEq ι]
(D : ι → ValueDist) (J : SetSystem ι) (M : Mechanism ι) (hM : IsTruthful D J M)
(S : Finset ι) :
∑ i ∈ S, servProb D M i ≤ (J.rank S : ℝ) := by sorry
end CHMSPricing.SpmPartition
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.