critical_three_seven_allocation_tables_structure
Each of the seven displayed three-round allocation tables assigns every chore once to each agent across rounds, gives the diagonal agent three chores and each other agent two, and assigns at most one of the first four chores to the diagonal agent in round zero.
Statement
theorem critical_three_seven_allocation_tables_structure : let T : Fin 7 → Fin 3 → Fin 7 → Fin 3 := ![ ![![0, 2, 1, 1, 2, 0, 0], ![1, 1, 0, 0, 1, 2, 2], ![2, 0, 2, 2, 0, 1, 1]], ![![0, 2, 1, 1, 2, 0, 0], ![1, 0, 0, 2, 1, 1, 2], ![2, 1, 2, 0, 0, 2, 1]], ![![2, 1, 2, 0, 1, 0, 0], ![1, 0, 1, 2, 0, 1, 2], ![0, 2, 0, 1, 2, 2, 1]], ![![1, 0, 2, 1, 0, 0, 2], ![2, 1, 0, 2, 1, 1, 0], ![0, 2, 1, 0, 2, 2, 1]], ![![1, 2, 2, 1, 0, 0, 0], ![0, 1, 1, 0, 2, 1, 2], ![2, 0, 0, 2, 1, 2, 1]], ![![0, 1, 2, 2, 0, 1, 0], ![1, 0, 1, 0, 1, 2, 2], ![2, 2, 0, 1, 2, 0, 1]], ![![0, 2, 2, 1, 1, 0, 0], ![1, 0, 1, 2, 0, 2, 1], ![2, 1, 0, 0, 2, 1, 2]] ] (∀ (j : Fin 7) (g : Fin 7) (i : Fin 3), (Finset.univ.filter fun t : Fin 3 => T j t g = i).card = 1) ∧ (∀ (j : Fin 7) (t i : Fin 3), (Finset.univ.filter fun g : Fin 7 => T j t g = i).card = if i = t then 3 else 2) ∧ (∀ j : Fin 7, (Finset.univ.filter fun g : Fin 7 => g.val < 4 ∧ T j 0 g = 0).card ≤ 1)
- Source
- Explicit finite allocation certificate for OP-1112, experiment 26817.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- three_agent_critical_equal_weight_allocation_familyFor three agents and seven chores, suppose each agent designates four chores high. There exist three allocations such that every chore…
The proof, explained
The theorem verifies three structural properties for seven concrete chore-allocation tables with three agents, three rounds, and seven chores: every chore is given to every agent exactly once, the diagonal agent receives three chores and other agents two in each round, and agent 0 receives at most one of the first four chores in round 0. Because the tables are explicit and all conditions involve finite domains, the proposition is decidable. The proof is completed in a single step by exhaustive computation via `decide`.
All seven allocation tables satisfy the three structural conditions: each chore is assigned to each agent exactly once across the three rounds, in each round the diagonal agent receives three chores while the other two agents receive two, and agent 0 receives at most one of the first four chores in round 0. automation
The tables are given as explicit matrices of values in $\text{Fin } 3$, and all quantifiers in the theorem statement range over the finite index sets $\text{Fin } 7$ and $\text{Fin } 3$. Consequently, the entire assertion is a closed, decidable proposition. The `decide` tactic evaluates this finite check by direct computation and confirms that all three conditions hold for all seven tables.
decide
- The entire proof is executed by Lean's computational kernel through `decide`, which exhaustively checks the finite number of cases (7 tables, 3 rounds, 7 chores, 3 agents) rather than constructing an abstract mathematical argument.
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.
set_option maxRecDepth 100000set_option maxHeartbeats 10000000theorem critical_three_seven_allocation_tables_structure : let T : Fin 7 → Fin 3 → Fin 7 → Fin 3 := ![ ![![0, 2, 1, 1, 2, 0, 0], ![1, 1, 0, 0, 1, 2, 2], ![2, 0, 2, 2, 0, 1, 1]], ![![0, 2, 1, 1, 2, 0, 0], ![1, 0, 0, 2, 1, 1, 2], ![2, 1, 2, 0, 0, 2, 1]], ![![2, 1, 2, 0, 1, 0, 0], ![1, 0, 1, 2, 0, 1, 2], ![0, 2, 0, 1, 2, 2, 1]], ![![1, 0, 2, 1, 0, 0, 2], ![2, 1, 0, 2, 1, 1, 0], ![0, 2, 1, 0, 2, 2, 1]], ![![1, 2, 2, 1, 0, 0, 0], ![0, 1, 1, 0, 2, 1, 2], ![2, 0, 0, 2, 1, 2, 1]], ![![0, 1, 2, 2, 0, 1, 0], ![1, 0, 1, 0, 1, 2, 2], ![2, 2, 0, 1, 2, 0, 1]], ![![0, 2, 2, 1, 1, 0, 0], ![1, 0, 1, 2, 0, 2, 1], ![2, 1, 0, 0, 2, 1, 2]] ] (∀ (j : Fin 7) (g : Fin 7) (i : Fin 3), (Finset.univ.filter fun t : Fin 3 => T j t g = i).card = 1) ∧ (∀ (j : Fin 7) (t i : Fin 3), (Finset.univ.filter fun g : Fin 7 => T j t g = i).card = if i = t then 3 else 2) ∧ (∀ j : Fin 7, (Finset.univ.filter fun g : Fin 7 => g.val < 4 ∧ T j 0 g = 0).card ≤ 1) := by decide