noncore_ordering_fraction
For a cooperative game v : Finset α → ℝ on a finite type α with decidable equality, noncore_ordering_fraction v is the fraction of player ordering bijections e : Fin (Fintype.card α) ≃ α whose marginal worth vector marginal_vector v e does not belong to the core of v (¬ is_in_core v (marginal_vector v e)).
Statement
noncomputable def noncore_ordering_fraction {α : Type*} [DecidableEq α] [Fintype α] (v : Finset α → ℝ) : ℝ
- Defined in
- arXiv:2611.16207, Section 1
- Verified
- 13 Nov 2026
- Axioms
- none listed
- Built on 2
- marginal_vectorFor a cooperative game v : Finset α → ℝ on a finite type α with decidable equality and an ordering bijection e : Fin (Fintype.card α) ≃ α,…
- is_in_coreAn allocation x belongs to the core of a cooperative game v on finite player set α if the total payoff equals v(univ) and every coalition…
- Used by 2
- two_thirds_convex_max_noncore_fractionFor each n, two_thirds_convex_max_noncore_fraction n is the supremum over all 2/3-convex cooperative games v on Fin n with v(∅) = 0 of the…
- two_thirds_convex_three_player_noncore_ordering_fraction_ge_two_thirdsThere exists a 2/3-convex cooperative game v on 3 players (Fin 3) satisfying v(∅) = 0 for which the probability that a uniformly random…
Read back from the Lean
Given a finite type α with decidable equality and a function v : Finset α → ℝ, noncore_ordering_fraction v is the real number defined as the quotient of:
1. The number of bijections e : Fin (Fintype.card α) ≃ α (linear orderings of α) such that the marginal vector of v under e is **not** in the core of v, divided by
2. (Fintype.card α)! (the total number of permutations of α).
Here:
- For an ordering e and an element i : α, the predecessors of i under e is the set { e(j) | j < e⁻¹(i) }.
- The marginal vector of v under e assigns to each i : α the marginal contribution v ({i} ∪ predecessors(e, i)) - v (predecessors(e, i)).
- A payoff vector x : α → ℝ is in the core of v if it is efficient (∑_{i : α} x(i) = v(univ)) and coalitionally rational (for all S ⊆ α, v(S) ≤ ∑_{i ∈ S} x(i)).
- An ordering is counted in the numerator if this marginal vector fails to be in the core (i.e. efficiency fails or there is some coalition S where v(S) > ∑_{i ∈ S} x(i)).
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
/-- The probability that the marginal worth vector of a uniformly random player ordering is not in the core. -/ noncomputable def noncore_ordering_fraction {α : Type*} [DecidableEq α] [Fintype α] (v : Finset α → ℝ) : ℝ := let _ : DecidablePred (fun (e : Fin (Fintype.card α) ≃ α) => ¬ is_in_core v (marginal_vector v e)) := Classical.decPred _ ((Finset.univ.filter (fun (e : Fin (Fintype.card α) ≃ α) => ¬ is_in_core v (marginal_vector v e))).card : ℝ) / (Nat.factorial (Fintype.card α) : ℝ)