bundle_card_bounds_of_ef1_non_wasteful
For any allocation rule on n agents and k * n + r objects that is non-wasteful and EF1, every agent receives either k or k + 1 objects (Lemma 2 of Chernulich and Yenmez 2026).
Statement
theorem bundle_card_bounds_of_ef1_non_wasteful (n k r : ℕ) (hn : 0 < n) (hr : r < n)
(f : (Fin n → LinearOrder (Fin (k * n + r))) → Fin n → Finset (Fin (k * n + r)))
(h_alloc : is_allocation_rule f) (h_nw : is_non_wasteful_rule f) (h_ef1 : is_ef1_rule f)
(succ : Fin n → LinearOrder (Fin (k * n + r))) (i : Fin n) :
k ≤ (f succ i).card ∧ (f succ i).card ≤ k + 1- Source
- step towards op_1321_impossibility_extension
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_allocation_ruleGiven types Agent and Object, a rule f : (Agent -> LinearOrder Object) -> Agent -> Finset Object satisfies is_allocation_rule if for every…
- is_non_wasteful_ruleGiven finite types Agent and Object with decidable equality on Object, a rule f : (Agent -> LinearOrder Object) -> Agent -> Finset Object…
- is_ef1_ruleGiven types Agent and Object with decidable equality on Object, a rule f : (Agent → LinearOrder Object) → Agent → Finset Object satisfies…
- pairwise_dominatesA finite bundle S : Finset α pairwise-dominates a finite bundle S' : Finset α for an agent with weak preference relation le : α → α → Prop…
The proof, explained
By the EF1 condition, removing at most one object from any agent's bundle allows an injective assignment into any other agent's bundle, implying that no two bundle sizes can differ by more than 1 (|f(b)| ≤ |f(a)| + 1). Because the allocation is disjoint and non-wasteful, the sum of all n bundle sizes is exactly k * n + r. Comparing agent i's bundle to all others using the pairwise bound shows that receiving fewer than k objects would force the total count below n * k, while receiving more than k + 1 objects would force the total count above (k + 1) * n + r. Thus, every agent must receive either k or k + 1 objects.
For any two agents a and b, agent b's bundle has cardinality at most |f(a)| + 1.
By the EF1 condition, there exists a subset S ⊆ f(b) with |S| ≤ 1 such that agent a's bundle pairwise dominates f(b) \ S. Pairwise dominance implies an injection from f(b) \ S into f(a), giving |f(b) \ S| ≤ |f(a)|. Since |f(b) \ S| = |f(b)| - |S| and |S| ≤ 1, it follows that |f(b)| ≤ |f(a)| + 1.
uses
Finset.card_le_card_of_injOn,Finset.card_sdiff_of_subsethave h_pair : ∀ a b : Fin n, (f succ b).card ≤ (f succ a).card + 1 := by intro a b obtain ⟨S, hS_sub, hS_card, h_dom⟩ := h_ef1 succ a b obtain ⟨g, hg_in, hg_inj, -⟩ := h_dom have h_le := Finset.card_le_card_of_injOn g hg_in hg_inj have h_diff := Finset.card_sdiff_of_subset hS_sub omega
The sum of the cardinalities of all n agents' bundles equals k * n + r.
Because f is an allocation rule, the bundles assigned to distinct agents are pairwise disjoint. Non-wastefulness means the union of all n bundles is the complete set of objects Fin (k * n + r). Summing the cardinalities across all agents therefore yields the total number of objects, k * n + r.
uses
Finset.card_biUnion,Finset.card_univ,Fintype.card_finhave h_disj : ((Finset.univ : Finset (Fin n)) : Set (Fin n)).PairwiseDisjoint (f succ) := by intro a _ b _ hab exact h_alloc succ a b hab have h_sum_eq := Finset.card_biUnion h_disj have h_nw' := h_nw succ rw [h_nw'] at h_sum_eq rw [Finset.card_univ, Fintype.card_fin] at h_sum_eq have h_sum : ∑ j : Fin n, (f succ j).card = k * n + r := h_sum_eq.symm
Splitting off agent i's bundle from the total sum leaves at most (n - 1) * (|f(i)| + 1) objects for the remaining agents.
Isolating agent i from the sum gives |f(i)| + ∑_{j ≠ i} |f(j)| = k * n + r. Because every other agent j satisfies |f(j)| ≤ |f(i)| + 1 by the pairwise bound, summing over the remaining n - 1 agents gives ∑_{j ≠ i} |f(j)| ≤ (n - 1) * (|f(i)| + 1).
uses
Finset.add_sum_erase,Finset.mem_univ,Finset.sum_le_card_nsmul,nsmul_eq_mul,Finset.card_erase_of_mem,Finset.card_univ,Fintype.card_finconstructor · -- k ≤ (f succ i).card have h_erase : (f succ i).card + ∑ j ∈ Finset.univ.erase i, (f succ j).card = k * n + r := by rw [Finset.add_sum_erase Finset.univ (fun j => (f succ j).card) (Finset.mem_univ i), h_sum] have h_bound : ∑ j ∈ Finset.univ.erase i, (f succ j).card ≤ (n - 1) * ((f succ i).card + 1) := by have h1 : ∑ j ∈ Finset.univ.erase i, (f succ j).card ≤ (Finset.univ.erase i).card • ((f succ i).card + 1) := by apply Finset.sum_le_card_nsmul intro j _ exact h_pair i j rw [nsmul_eq_mul, Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin] at h1 exact h1
Agent i receives at least k objects: k ≤ |f(i)|.
Suppose for contradiction that |f(i)| < k, which means |f(i)| + 1 ≤ k. Then the total number of objects |f(i)| + ∑_{j ≠ i} |f(j)| would be bounded by |f(i)| + (n - 1) * k < k + (n - 1) * k = n * k. However, the total number of objects is k * n + r ≥ n * k, a contradiction.
uses
Nat.mul_le_mul_left,Nat.add_mul,one_mul,Nat.sub_add_cancel,mul_comm,Nat.le_add_rightby_contra! h have h1 : (f succ i).card + 1 ≤ k := h have h2 : (n - 1) * ((f succ i).card + 1) ≤ (n - 1) * k := Nat.mul_le_mul_left (n - 1) h1 have h_split : (n - 1) * k + k = n * k := by have : (n - 1) * k + 1 * k = (n - 1 + 1) * k := (Nat.add_mul (n - 1) 1 k).symm rw [one_mul] at this rw [this, Nat.sub_add_cancel hn] have h_bound' : (f succ i).card + ∑ j ∈ Finset.univ.erase i, (f succ j).card < n * k := by calc (f succ i).card + ∑ j ∈ Finset.univ.erase i, (f succ j).card _ ≤ (f succ i).card + (n - 1) * ((f succ i).card + 1) := by omega _ ≤ (f succ i).card + (n - 1) * k := by omega _ < k + (n - 1) * k := by omega _ = (n - 1) * k + k := by omega _ = n * k := h_split have h_ge : n * k ≤ (f succ i).card + ∑ j ∈ Finset.univ.erase i, (f succ j).card := by calc n * k = k * n := mul_comm n k _ ≤ k * n + r := Nat.le_add_right (k * n) r _ = (f succ i).card + ∑ j ∈ Finset.univ.erase i, (f succ j).card := h_erase.symm omegaAgent i receives at most k + 1 objects: |f(i)| ≤ k + 1.
Summing the pairwise inequality |f(i)| ≤ |f(j)| + 1 over all n agents j yields n * |f(i)| ≤ ∑_j |f(j)| + n = (k * n + r) + n. Since r < n, this sum is strictly less than k * n + n + n = n * (k + 2). Dividing through by n gives |f(i)| < k + 2, which for natural numbers is equivalent to |f(i)| ≤ k + 1.
uses
Finset.sum_le_sum,Finset.sum_const,Finset.card_univ,Fintype.card_fin,nsmul_eq_mul,Finset.sum_add_distrib,mul_one,mul_comm,Nat.lt_of_mul_lt_mul_left· -- (f succ i).card ≤ k + 1 have h_le : ∑ j : Fin n, (f succ i).card ≤ ∑ j : Fin n, ((f succ j).card + 1) := by apply Finset.sum_le_sum intro j _ exact h_pair j i rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] at h_le rw [Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul, mul_one] at h_le rw [h_sum] at h_le have h1 : k * n + r + n < (k + 2) * n := by calc k * n + r + n < k * n + n + n := by omega _ = (k + 2) * n := by ring have h2 : n * (f succ i).card < n * (k + 2) := by calc n * (f succ i).card ≤ k * n + r + n := h_le _ < (k + 2) * n := h1 _ = n * (k + 2) := mul_comm (k + 2) n have h3 : (f succ i).card < k + 2 := Nat.lt_of_mul_lt_mul_left h2 omega
Finset.card_le_card_of_injOn- An injective mapping from a finite set s into a finite set t implies |s| ≤ |t|.
Finset.card_sdiff_of_subset- If s ⊆ t, then |t \ s| = |t| - |s|.
Finset.card_biUnion- The cardinality of a pairwise disjoint union of finite sets is the sum of their cardinalities.
Finset.card_univ- The cardinality of Finset.univ for a finite type equals the cardinality of the type.
Fintype.card_fin- The cardinality of Fin n is n.
Finset.add_sum_erase- For any element a in s, the term f(a) plus the sum over s \ {a} equals the sum over s.
Finset.mem_univ- Every element of a finite type belongs to Finset.univ.
Finset.sum_le_card_nsmul- If every term in a finite sum is at most c, then the sum is at most the cardinality of the index set times c.
nsmul_eq_mul- Scalar multiplication by a natural number n on natural numbers coincides with standard multiplication.
Finset.card_erase_of_mem- Removing an element that belongs to a finite set decreases its cardinality by 1.
Nat.mul_le_mul_left- Multiplying both sides of an inequality by a natural number preserves the inequality: a ≤ b implies c * a ≤ c * b.
Nat.add_mul- Right distributivity of multiplication over addition: (a + b) * c = a * c + b * c.
one_mul- 1 * a = a for any element a.
Nat.sub_add_cancel- If m ≤ n, then (n - m) + m = n.
mul_comm- Multiplication is commutative: a * b = b * a.
Nat.le_add_right- For any natural numbers n and k, n ≤ n + k.
Finset.sum_le_sum- Pointwise inequality between summands over a finite set implies inequality between their sums.
Finset.sum_const- The sum of a constant c over a finite set s equals |s| * c.
Finset.sum_add_distrib- The sum of a sum of functions over a finite set distributes into the sum of their individual sums.
mul_one- a * 1 = a for any element a.
Nat.lt_of_mul_lt_mul_left- If a * b < a * c for natural numbers, then b < c.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- For any allocation rule on n agents and k * n + r objects that is non-wasteful and EF1, every agent receives either k or k + 1 objects. -/theorem bundle_card_bounds_of_ef1_non_wasteful (n k r : ℕ) (hn : 0 < n) (hr : r < n) (f : (Fin n → LinearOrder (Fin (k * n + r))) → Fin n → Finset (Fin (k * n + r))) (h_alloc : is_allocation_rule f) (h_nw : is_non_wasteful_rule f) (h_ef1 : is_ef1_rule f) (succ : Fin n → LinearOrder (Fin (k * n + r))) (i : Fin n) : k ≤ (f succ i).card ∧ (f succ i).card ≤ k + 1 := by have h_pair : ∀ a b : Fin n, (f succ b).card ≤ (f succ a).card + 1 := by intro a b obtain ⟨S, hS_sub, hS_card, h_dom⟩ := h_ef1 succ a b obtain ⟨g, hg_in, hg_inj, -⟩ := h_dom have h_le := Finset.card_le_card_of_injOn g hg_in hg_inj have h_diff := Finset.card_sdiff_of_subset hS_sub omega have h_disj : ((Finset.univ : Finset (Fin n)) : Set (Fin n)).PairwiseDisjoint (f succ) := by intro a _ b _ hab exact h_alloc succ a b hab have h_sum_eq := Finset.card_biUnion h_disj have h_nw' := h_nw succ rw [h_nw'] at h_sum_eq rw [Finset.card_univ, Fintype.card_fin] at h_sum_eq have h_sum : ∑ j : Fin n, (f succ j).card = k * n + r := h_sum_eq.symm constructor · -- k ≤ (f succ i).card have h_erase : (f succ i).card + ∑ j ∈ Finset.univ.erase i, (f succ j).card = k * n + r := by rw [Finset.add_sum_erase Finset.univ (fun j => (f succ j).card) (Finset.mem_univ i), h_sum] have h_bound : ∑ j ∈ Finset.univ.erase i, (f succ j).card ≤ (n - 1) * ((f succ i).card + 1) := by have h1 : ∑ j ∈ Finset.univ.erase i, (f succ j).card ≤ (Finset.univ.erase i).card • ((f succ i).card + 1) := by apply Finset.sum_le_card_nsmul intro j _ exact h_pair i j rw [nsmul_eq_mul, Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin] at h1 exact h1 by_contra! h have h1 : (f succ i).card + 1 ≤ k := h have h2 : (n - 1) * ((f succ i).card + 1) ≤ (n - 1) * k := Nat.mul_le_mul_left (n - 1) h1 have h_split : (n - 1) * k + k = n * k := by have : (n - 1) * k + 1 * k = (n - 1 + 1) * k := (Nat.add_mul (n - 1) 1 k).symm rw [one_mul] at this rw [this, Nat.sub_add_cancel hn] have h_bound' : (f succ i).card + ∑ j ∈ Finset.univ.erase i, (f succ j).card < n * k := by calc (f succ i).card + ∑ j ∈ Finset.univ.erase i, (f succ j).card _ ≤ (f succ i).card + (n - 1) * ((f succ i).card + 1) := by omega _ ≤ (f succ i).card + (n - 1) * k := by omega _ < k + (n - 1) * k := by omega _ = (n - 1) * k + k := by omega _ = n * k := h_split have h_ge : n * k ≤ (f succ i).card + ∑ j ∈ Finset.univ.erase i, (f succ j).card := by calc n * k = k * n := mul_comm n k _ ≤ k * n + r := Nat.le_add_right (k * n) r _ = (f succ i).card + ∑ j ∈ Finset.univ.erase i, (f succ j).card := h_erase.symm omega · -- (f succ i).card ≤ k + 1 have h_le : ∑ j : Fin n, (f succ i).card ≤ ∑ j : Fin n, ((f succ j).card + 1) := by apply Finset.sum_le_sum intro j _ exact h_pair j i rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] at h_le rw [Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul, mul_one] at h_le rw [h_sum] at h_le have h1 : k * n + r + n < (k + 2) * n := by calc k * n + r + n < k * n + n + n := by omega _ = (k + 2) * n := by ring have h2 : n * (f succ i).card < n * (k + 2) := by calc n * (f succ i).card ≤ k * n + r + n := h_le _ < (k + 2) * n := h1 _ = n * (k + 2) := mul_comm (k + 2) n have h3 : (f succ i).card < k + 2 := Nat.lt_of_mul_lt_mul_left h2 omega