is_efx_goods
An 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 as much as j's bundle without g.
Statement
def is_efx_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : Prop
- Defined in
- arXiv:2610.29201 Def 1
- Verified
- 22 Oct 2026
- Axioms
- none listed
- Built on 2
- 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.
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- Used by 52
- efx_exists_of_two_universal_small_goods_irLet m and n be natural numbers with n positive. There are m+2 goods with nonnegative real additive values for n agents. Each agent values…
- is_efx_goods_iff_bundle_totalsFor real additive valuations, EFX is equivalent to the following total-value inequalities: for every pair of distinct agents i,j and each…
- efx_exists_of_strictly_positive_profilesFor fixed finite numbers of goods and agents, existence of complete EFX for every strictly positive real additive profile implies complete…
- efx_intact_obstruction_no_coarseNo assignment of the four intact old bundles and new singleton in the explicit seven-good instance is EFX after casting its item values to…
- op_1004_two_type_efx_fpo_equal_ratioFor any real number a > 1, every two-agent instance on a finite set of goods where each good is valued at a by both agents or at 1 by both…
- is_efx_goods_exists_unenviedFor a positive number of agents, any EFX allocation of nonnegative additive goods can be changed to another EFX allocation that weakly…
- efx_exists_of_positive_perturbationsFor any finite real additive valuation profile, if adding every strictly positive common real epsilon to every item value admits a…
- efx_allsource_three_pair_perturbed_strict_sanityThe perturbed partial state is strictly envy-free, and the explicit complete allocation remains EFX.
- efx_allsource_pair_sanityThe old state is envy-free with all values positive and charity small for each owner; the explicit complete witness is EFX and IR.
- efx_three_bonus_distinct_sanityEvery value in the explicit matrix is positive and each bonus is no larger than every old good for each agent. The old allocation…
- efx_three_bonus_distinct_no_realFor the explicit positive four-agent seven-good instance, if an EFX allocation assigns its four old goods to distinct agents and its three…
- is_efx_goods_insert_of_unenvied_of_minAdding a good to an unenvied agent preserves EFX if every other agent values the new good no more than every old good in that recipient's…
- efx_exists_of_common_pair_order_oddFor any positive number of agents and 2k+1 nonnegative additive goods, suppose every agent weakly prefers goods with smaller…
- 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…
- efx_exists_of_two_universal_small_goodsFor a positive number of agents with nonnegative real additive values, suppose each of the last two goods is weakly less valuable to every…
- is_efx_goods_nat_cast_iffFor natural-number item values, EFX after casting values to the reals is equivalent to all natural-number inequalities comparing each…
- is_wefx_goods_unit_weights_iff_is_efx_goodsWhen all agents have unit entitlements, weighted EFX is equivalent to standard unweighted EFX.
- 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…
- scaled_common_ratio_bivalued_efx_fpo_envyfreeable_two_agents_core_of_efx_countsNormalized two-agent bivalued core from the EFX arithmetic: if both agents' values lie in {1, r} and for every choice of the four type…
- efx_of_bundle_card_le_oneAn allocation where each agent receives at most one good is unconditionally EFX for any nonnegative additive valuations.
- efx_equal_pairs_few_blockers_ir_completionIf some old pair p has at most one blocking agent, then some complete EFX allocation preserves all old utilities while leaving all four…
- efx_no_self_three_split_full_efxA complete EFX allocation of the matrix has owners (2,1,2,1,3,2,3,1,0,0,0,0,0).
- efx_three_split_sanityAll values are positive. In the initial partial allocation (0,0,1,1,2,2,3,3), each agent values all four old bundles equally, values the…
- is_efx_goods_permute_of_utility_leA bundle permutation that weakly improves every agent's own additive value preserves EFX for nonnegative item values.
- efx_anchor_lock_full_efxThe nondegenerate instance has a complete EFX allocation with owners (3,1,1,1,2,2,1,2,1,0,3,0).
- efx_pair_binary_no_one_split_allocationFor the explicit binary nine-good matrix cast to real values, any allocation which preserves all but possibly one of the four old adjacent…
- efx_pair_binary_requires_two_splitsEvery complete EFX allocation of the explicit binary nine-good matrix cast to real values separates the two members of at least two…
- is_efx_goods_all_pairsFor nonnegative additive values, the EFX inequalities also hold when the observer and the target agent coincide.
- is_efx_goods_equiv_goodsRelabeling a finite set of goods through a bijection, both in the valuation profile and allocation, preserves and reflects EFX.
- efx_min_cycle_full_efxThe instance has a complete EFX allocation with owners (0,0,0,0,1,3,2,2,2,3,2,1,1) that strictly improves all four original utilities; it…
- efx_anchor_two_locks_preserve_threeIn the two-lock anchor family, a complete EFX allocation can preserve the original three agents’ starting utilities for every positive…
- efx_exists_of_common_pair_orderFor any finite number m of goods, any positive number n of agents, and nonnegative real additive values, suppose for every agent and goods…
- efx_no_self_three_split_sanityThe matrix is positive; each agent values every old triple equally at her baseline, values every good in her own triple at least as much…
- efx_intact_obstruction_requires_splitEvery EFX allocation of the explicit seven-good positive instance separates goods 0 and 1 or separates goods 2 and 3; hence it splits an…
- op_1004_two_type_efx_fpo_single_typeFor two agents and any finite set of identical goods valued at c > 0 by agent 0 and d > 0 by agent 1, there exists an allocation that is…
- efx_three_small_goods_completion_loss_or_splitIn the explicit eleven-good instance cast to real values, every complete EFX allocation which keeps each of the four old adjacent pairs…
- efx_pareto_lock_sanityAll values are positive. The partial allocation (1,0,0,0,1,2,4,3), where 4 means unallocated, is EFX and meets the baseline utilities; the…
- scaled_common_ratio_bivalued_efx_fpo_envyfreeable_zero_goodsWhen m = 0, the empty allocation Fin.elim0 and zero subsidy vector 0 satisfy EFX, envy-freeness with subsidies, and fractional Pareto…
- efx_no_self_three_split_perturbed_fullThe nondegenerate perturbation admits a complete EFX allocation with owners (2,1,2,1,3,2,3,1,0,0,0,0,0).
- efx_three_small_goods_obstruction_sanityIn the explicit eleven-good instance all natural item values are strictly positive, and each of goods 8,9,10 is no more valuable than…
- efx_exists_of_common_pair_order_evenFor any positive number of agents and an even number 2k of goods with nonnegative additive values, suppose every agent weakly prefers…
- efx_source_two_full_efxThe explicit complete EFX allocation preserves the other three initial utilities.
- efx_allsource_three_pair_sanityThe partial allocation is envy-free; all values are positive and charity is owner-small; the explicit full EFX allocation preserves all…
- efx_nondeg_cycle_full_efxThe nondegenerate instance has a complete EFX allocation with owners (0,0,0,0,1,3,2,2,2,3,2,1,1).
- is_efx_goods_scaleMultiplying each agent's additive valuation vector by a positive constant c_i > 0 preserves and reflects whether an allocation is EFX.
- efx_intact_obstruction_partial_efxIn the explicit seven-good instance restricted to the first six goods, assigning {5} to agent 0, {0,1} to agent 1, {2,3} to agent 2, and…
- efx_exists_of_null_last_goodFor a positive number of agents and nonnegative additive values, a good worth zero to every agent can be added while retaining existence…
- efx_three_pair_anchor_sanityThe starting allocation is envy-free with r+2 goods per bundle and one charity good; the lifted complete witness is EFX.
- efx_pair_binary_full_efxFor the explicit binary nine-good valuation matrix cast to real values, the full allocation (3,3,1,2,0,2,1,1,0), listing the owner of each…
- efx_pair_binary_no_one_splitFor the explicit binary nine-good matrix cast to real values, no allocation encoded by the one-split construction is EFX.
- efx_exists_of_universal_least_goodFor a positive number of agents and nonnegative additive values, if the last good is weakly least valuable for every agent, existence of…
- efx_three_small_goods_obstruction_no_current_irIn the explicit eleven-good instance cast to real values, every EFX coarse completion has some agent whose utility is strictly less than…
Read back from the Lean
Given natural numbers m (number of goods) and n (number of agents), a utility profile u : Fin n → Fin m → ℝ, and an allocation function σ : Fin m → Fin n assigning each good to an agent:
The definition is_efx_goods asserts that for all agents i, j : Fin n, if i ≠ j, then for every good g in agent j's bundle (bundle_of σ j), agent i's additive valuation of j's bundle with g removed is less than or equal to agent i's additive valuation of their own bundle (bundle_of σ 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
/-- An allocation of goods is EFX if removing any good from another agent's bundle eliminates envy. -/ def is_efx_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : Prop := ∀ i j : Fin n, i ≠ j → ∀ g ∈ bundle_of σ j, additive_valuation (u i) ((bundle_of σ j).erase g) ≤ additive_valuation (u i) (bundle_of σ i)