has_bivalued_efx_sub_mms_instance
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
- op_1719_bivalued_efx_sub_mms_two_agents_two_ratioFor two agents and item values in {1, 2}, there exists an additive instance with a complete EFX allocation in which some agent obtains…
- bivalued_efx_sub_mms_max_dFor 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.
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