XOS agent arrivals, feasible allocations and online policies
DefinitionLinMatroidSecretary_Online_Supplement_AllocationLet be a finite labelled item set and let the agents be . An instance fixes an eligibility set and a valuation for each agent before the random arrival order is drawn. The validity predicate requires to be XOS on : a maximum of finitely many, at least one, nonnegative additive clauses. It uses the published predicate on ; values outside subsets of are immaterial. An allocation is feasible on an agent set when , its bundles are pairwise disjoint, and is independent in the given matroid. Its welfare is
The predicate of linearity requires a representation in over some field , with no finiteness restriction on .
An observation consists of the current eligibility set, value queries on its subsets, and a vector for each eligible item. A policy receives the arrival-ordered observations so far and its previously assigned bundles, and outputs a distribution on bundles. It receives no agent indices or unrevealed data. In the known-matroid model the vector component is the one-point type, and the policy may be chosen as a function of the known matroid. In the online-representation model the vector component is ; only vectors restricted to revealed eligibility sets enter observations. The policy is a function with no feasibility or competitive guarantee bundled into its type. Validity says all output probabilities are nonnegative and sum to one.
For an arrival permutation and sequence of bundles , the conditional run probability is the product of the policy's step probabilities. The final allocation assigns to agent . The expected welfare is
Always feasible means that every positive-probability run yields a feasible allocation. The empty allocation is permitted. When the expected welfare is zero and .
This interface separates the information available to an online policy from its required guarantees and provides the allocation model for Theorem 2 and Lemma 7.
import Mathlib
import Definitions.Def_DSICHardRev_ValuationClasses
import Definitions.Def_LinMatroidSecretary_Online_Setting
/-!
Agent-arrival model of §5, Bérczi–Dughmi–Livanos–Soto–Verdugo, STOC 2027 #608,
PDF pp. 19–21, 25. Eligibility sets may overlap. Value queries and vectors are restricted
to revealed eligibility sets. Policies contain only functions, with validity stated separately.
-/
namespace LinMatroidSecretary.Online.Supplement
open Finset
noncomputable section
variable {E : Type} [Fintype E] [DecidableEq E] {n : ℕ}
/-- XOS on `S`, by applying the published general XOS predicate to the valuation
extended by ignoring items outside `S`. Values of `f` outside subsets of `S` are unused. -/
def IsXOSOn (S : Finset E) (f : Finset E → ℝ) : Prop :=
DSICHardRev.IsXOS (fun D => f (D ∩ S))
/-- Data fixed before the random order is drawn; no algorithm or guarantee is a field. -/
structure Instance (E : Type) (n : ℕ) where
elig : Fin n → Finset E
val : Fin n → Finset E → ℝ
/-- Each agent has a finite maximum of nonnegative additive clauses on its eligible items. -/
def Instance.Valid (I : Instance E n) : Prop :=
∀ a, IsXOSOn (I.elig a) (I.val a)
/-- Feasibility for the agents in `X`: eligibility, disjointness, independent union. -/
def FeasibleOn (M : Matroid E) (elig : Fin n → Finset E) (X : Finset (Fin n))
(T : Fin n → Finset E) : Prop :=
(∀ a ∈ X, T a ⊆ elig a) ∧
(∀ a ∈ X, ∀ b ∈ X, a ≠ b → Disjoint (T a) (T b)) ∧
M.Indep (↑(X.biUnion T) : Set E)
/-- A feasible allocation to all agents. -/
def Feasible (M : Matroid E) (I : Instance E n) (T : Fin n → Finset E) : Prop :=
FeasibleOn M I.elig univ T
/-- Total value of an allocation. Only feasible allocations are used for comparisons. -/
def welfare (I : Instance E n) (T : Fin n → Finset E) : ℝ :=
∑ a, I.val a (T a)
/-- A finite matroid is linear if it has a finite-dimensional representation over some
field. The field is not required to be finite. -/
def IsLinear (M : Matroid E) : Prop :=
∃ (K : Type) (_ : Field K) (d : ℕ) (v : E → Fin d → K),
M = linMatroid (F := K) v
/-- What one arrival reveals. In the known-matroid model `V = Unit`, so there is no
vector information. Queries are only on subsets of `elig`; vectors only on its elements. -/
structure Observation (E V : Type) where
elig : Finset E
value : {D : Finset E // D ⊆ elig} → ℝ
vec : {e : E // e ∈ elig} → V
/-- A behavioural policy sees arrival-ordered observations and its own earlier bundles.
There are no agent indices, unrevealed data, representation or correctness proofs in the input. -/
structure AllocationPolicy (E V : Type) (n : ℕ) where
choose : (t : ℕ) → (Fin (t + 1) → Observation E V) →
(Fin t → Finset E) → Finset E → ℝ
/-- Each output is a probability distribution on bundles, even on unused histories. -/
def AllocationPolicy.Valid {V : Type} (π : AllocationPolicy E V n) : Prop :=
∀ t h past, (∀ D, 0 ≤ π.choose t h past D) ∧ ∑ D, π.choose t h past D = 1
/-- Observed information of an agent; full `I` and `v` are not passed to the policy. -/
def observation {V : Type} (I : Instance E n) (v : E → V) (a : Fin n) :
Observation E V :=
{ elig := I.elig a
value := fun D => I.val a D.val
vec := fun e => v e.val }
/-- Run probability conditional on the arrival permutation. Choices at a step use only
the observations up to that step and the bundles strictly before it. -/
def allocationRunProb {V : Type} (π : AllocationPolicy E V n) (I : Instance E n)
(v : E → V) (σ : Equiv.Perm (Fin n)) (b : Fin n → Finset E) : ℝ :=
∏ t : Fin n, π.choose t.val
(fun j => observation I v (σ ⟨j.val, by omega⟩))
(fun j => b ⟨j.val, by omega⟩) (b t)
/-- Final allocation indexed by agents, rather than by arrival positions. -/
def allocationAlg (σ : Equiv.Perm (Fin n)) (b : Fin n → Finset E) : Fin n → Finset E :=
fun a => b (σ.symm a)
/-- Exact expected welfare: uniform random order and the policy's behavioural randomness.
`0! = 1`, so this also defines the zero-agent case without division by zero. -/
def expectedWelfare {V : Type} (π : AllocationPolicy E V n) (I : Instance E n)
(v : E → V) : ℝ :=
((n.factorial : ℝ))⁻¹ * ∑ σ : Equiv.Perm (Fin n), ∑ b : Fin n → Finset E,
allocationRunProb π I v σ b * welfare I (allocationAlg σ b)
/-- Always feasible means feasible on every positive-probability complete run. -/
def AlwaysFeasible {V : Type} (M : Matroid E) (π : AllocationPolicy E V n)
(I : Instance E n) (v : E → V) : Prop :=
∀ σ b, 0 < allocationRunProb π I v σ b → Feasible M I (allocationAlg σ b)
end
end LinMatroidSecretary.Online.Supplement