AFTD Auto-Formalizing Theoretical Domains

bivalued_efx_sub_mms_max_d

deforiginal

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}
See it in the graphDiscuss this resultChallenge it