AFTD Auto-Formalizing Theoretical Domains

has_bivalued_efx_sub_mms_instance

deforiginal

Given 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 number R, admitting a complete EFX allocation σ and an agent i whose bundle has value strictly less than her 1-out-of-d maximin share.

Statement

def has_bivalued_efx_sub_mms_instance (n : ℕ) (R : ℕ) (d : ℕ) : Prop
Related work
arXiv:2611.15582
Verified
15 Nov 2026
Axioms
none listed
Built on 4
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • is_efx_goodsAn allocation is EFX if for every pair of distinct agents i and j, and every good g in j's bundle, agent i values her own bundle at least…
  • maximin_shareThe maximin share of a valuation among n agents: the maximum, over partitions of the items into n bundles, of the value of the worst bundle.
  • bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
Used by 2

Read back from the Lean

The definition has_bivalued_efx_sub_mms_instance n R d asserts that there exist: 1. a natural number $m$ (the number of goods), 2. a valuation profile $u : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$, 3. an allocation $\sigma : \text{Fin } m \to \text{Fin } n$ partitioning the $m$ goods among the $n$ agents, and 4. an agent $i \in \text{Fin } n$, such that: - **Bivalued valuations**: For every agent $j \in \text{Fin } n$ and every good $g \in \text{Fin } m$, $u(j)(g) = 1$ or $u(j)(g) = R$ (cast to $\mathbb{R}$). - **EFX allocation**: The allocation $\sigma$ is envy-free up to any good (EFX) for goods with respect to $u$; that is, for all distinct agents $j_1, j_2 \in \text{Fin } n$ ($j_1 \neq j_2$) and every good $g$ in $j_2$'s bundle ($\sigma(g) = j_2$), agent $j_1$'s additive valuation of $j_2$'s bundle with $g$ removed is less than or equal to $j_1$'s additive valuation of their own bundle. - **Sub-$d$-MMS**: Agent $i$'s additive valuation of their assigned bundle $\sigma^{-1}(\{i\})$ is strictly less than their $d$-maximin share (the supremum over all partitions $P : \text{Fin } m \to \text{Fin } d$ of the infimum over all parts $k \in \text{Fin } d$ of the additive valuation of part $P^{-1}(\{k\})$ according to agent $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

/-- Predicate that an n-agent additive instance with item values in {1, R} admits a complete EFX allocation where some agent receives strictly less than her 1-out-of-d maximin share. -/
def has_bivalued_efx_sub_mms_instance (n : ℕ) (R : ℕ) (d : ℕ) : Prop :=
  ∃ (m : ℕ) (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) (i : Fin n),
    (∀ j g, u j g = 1 ∨ u j g = (R : ℝ)) ∧
    is_efx_goods u σ ∧
    additive_valuation (u i) (bundle_of σ i) < maximin_share (additive_valuation (u i)) d
See it in the graphDiscuss this resultChallenge it