Theorem 2 — 1/e expected welfare in both XOS secretary models
OpenLinMatroidSecretary.Online.Supplement.theorem_2Let be a finite labelled set of items and the agents. Each agent has an eligibility set and an XOS valuation on its subsets, fixed before agents arrive in uniformly random order. Allocated bundles must be eligible and pairwise disjoint, with independent union. There exist online algorithms with both of the following guarantees.
- For every known linear matroid on , representable over any field, and every , a policy can be chosen as a function of before any agent data are given. It sees only revealed eligibility sets, their valuations, and its own past assignments.
- For every known finite field , dimension , and finite ground type , one policy can be chosen before the representation and before the agent data. It additionally observes only the vectors of revealed eligible elements, in the common coordinate system.
In each model, for every XOS instance, every positive-probability run produces a feasible allocation, and for every feasible offline allocation ,
Thus the bound holds for the offline optimum. Every is covered, including ; there is no sample-size or large- restriction. Expectations average the uniform arrival order and the policy's internal randomness. This companion result extends the mission to agent arrivals and XOS welfare and is not used to prove the retained goal Theorem 1.
Differences from the source:
- encoding: online randomized decisions on the information revealed so far → behavioural probability distributions on bundles, queried on histories of eligibility sets, their subset valuations, restricted revealed vectors and previous assigned bundles; reason: finite-horizon perfect-recall decisions admit behavioural kernels; no agent indices, future data, outside values or unseen vectors are inputs; policies are chosen before instances and, in the online clause, before representations
- encoding: comparison with F(OPT(N)) → comparison with F(T*) for every feasible allocation T*; reason: finitely many allocations exist and the empty allocation is feasible, so the offline maximum is attained
- encoding: finite labelled items and agents, finite-dimensional representations, and the constant 1/e → finite types E, agents Fin n, coordinates Fin d, arbitrary-field representability for the known clause, and Real.exp (-1); reason: finite reindexing and coordinates preserve the model, including n=1,2 and the empty-agent case; exp(-1)=1/e
- encoding: XOS valuations defined only on eligible subsets → the published XOS predicate on D ↦ f_a(D ∩ E_a); reason: nonnegative clauses extend by zero outside E_a and restrict back, so this neither restricts nor reveals any additional valuation data
import Mathlib import Definitions.Def_LinMatroidSecretary_Online_Supplement_Allocation
namespace LinMatroidSecretary.Online.Supplement
/-- Theorem 2, STOC 2027 #608, PDF p. 21 (printed p. 19), both information models.
In each clause the policy is chosen before the agents' eligibility sets and valuations;
in the second it is also chosen before the vector representation. Comparison against
every feasible allocation is equivalent to comparison against the attained offline optimum. -/
theorem theorem_2 :
(∀ (E : Type) [Fintype E] [DecidableEq E] (M : Matroid E),
M.E = Set.univ → IsLinear M → ∀ n : ℕ,
∃ π : AllocationPolicy E Unit n, π.Valid ∧
∀ I : Instance E n, I.Valid →
AlwaysFeasible M π I (fun _ => ()) ∧
∀ Tstar : Fin n → Finset E, Feasible M I Tstar →
Real.exp (-1) * welfare I Tstar ≤ expectedWelfare π I (fun _ => ())) ∧
(∀ (F : Type) [Field F] [Fintype F] (d n : ℕ)
(E : Type) [Fintype E] [DecidableEq E],
∃ π : AllocationPolicy E (Fin d → F) n, π.Valid ∧
∀ (v : E → Fin d → F) (I : Instance E n), I.Valid →
AlwaysFeasible (linMatroid (F := F) v) π I v ∧
∀ Tstar : Fin n → Finset E, Feasible (linMatroid (F := F) v) I Tstar →
Real.exp (-1) * welfare I Tstar ≤ expectedWelfare π I v) := by sorry
end LinMatroidSecretary.Online.Supplement