AFTD Auto-Formalizing Theoretical Domains

bundle_card_bounds_of_ef1_non_wasteful

theoremverified

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.

  1. 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.

    lines 7–13

    uses Finset.card_le_card_of_injOn, Finset.card_sdiff_of_subset

      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
  2. 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.

    lines 14–21

    uses Finset.card_biUnion, Finset.card_univ, Fintype.card_fin

      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
  3. 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).

    lines 22–34

    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_fin

      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
  4. 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.

    lines 35–53

    uses Nat.mul_le_mul_left, Nat.add_mul, one_mul, Nat.sub_add_cancel, mul_comm, Nat.le_add_right

        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
  5. Agent 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.

    lines 54–71

    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

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