bivalued_efx_sub_mms_max_d
For natural numbers n and R, the supremum of the set of natural numbers d such that has_bivalued_efx_sub_mms_instance n R d holds.
Statement
noncomputable def bivalued_efx_sub_mms_max_d (n : ℕ) (R : ℕ) : ℕ
- Related work
- arXiv:2611.15582
- Verified
- 15 Nov 2026
- Axioms
- none listed
- Built on 1
- has_bivalued_efx_sub_mms_instanceGiven natural numbers n, R, and d, there exists a finite additive instance with n agents where each item value is either 1 or the natural…
Read back from the Lean
For given natural numbers n (number of agents) and R (valuation ratio/value):
bivalued_efx_sub_mms_max_d n R is defined as the supremum (sSup in ℕ) of the set of natural numbers d such that there exists a "bivalued EFX sub-MMS instance" with parameters (n, R, d), which means there exist:
- a number of goods m : ℕ,
- a valuation profile u : Fin n → Fin m → ℝ,
- an allocation σ : Fin m → Fin n,
- an agent i : Fin n,
such that:
1. For all agents j and goods g, the valuation u j g is bivalued: u j g = 1 or u j g = R.
2. The allocation σ is envy-free up to any good (EFX) for goods with respect to u: for all distinct agents i', j' : Fin n and every good g in j''s bundle (i.e., σ g = j'), agent i''s additive valuation of j''s bundle with g removed is at most agent i''s additive valuation of their own bundle:
∑ x ∈ (σ⁻¹(j') \ {g}), u i' x ≤ ∑ x ∈ σ⁻¹(i'), u i' x.
3. Agent i's additive valuation of their bundle σ⁻¹(i) is strictly less than their 1-out-of-d maximin share (MMS), where the 1-out-of-d MMS is defined as:
⨆ (P : Fin m → Fin d), ⨅ (k : Fin d), ∑ x ∈ P⁻¹(k), u i x.
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 largest integer d for which some n-agent additive instance with item values in {1, R} has a complete EFX allocation leaving an agent strictly below her 1-out-of-d maximin share. -/ noncomputable def bivalued_efx_sub_mms_max_d (n : ℕ) (R : ℕ) : ℕ := sSup {d : ℕ | has_bivalued_efx_sub_mms_instance n R d}