da_three_by_three_three_known_safely_manipulable
theoremverifiedoriginal
In the 3x3 market with complete rankings, a woman who knows three agents can safely and profitably manipulate men-proposing deferred acceptance: woman 0 (true m0 > m1 > m2) knows woman 1 (m1 > m0), man 0 (w1 > w0) and man 1 (w0 > w1), and swaps m1 and m2. So the RAT-degree of deferred acceptance without truncation is at most 3 in this market, refuting the conjecture of arXiv:2502.18805 (Sec. 8.1) that 5 is tight.
Statement
theorem da_three_by_three_three_known_safely_manipulable :
da_woman_k_known_safely_manipulable 3 3 3- Related work
- operator (Claude), 2026-10-03: counterexample to the conjecture of arXiv:2502.18805 v3 (Sec. 8.1) that the RAT-degree 5 of deferred acceptance without truncation is tight
- Verified
- 02 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- da_woman_k_known_safely_manipulableIn men-proposing deferred acceptance with nm men, nw women and complete rankings (no truncation), some woman who knows the rankings of k…
- woman_weakly_prefersUnder a woman's true ranking (unmatched worst), outcome a is at least as good as outcome b.
- deferred_acceptanceMen-proposing deferred acceptance (Gale-Shapley): the man each woman ends up with, given each man's ranking of the women and each woman's…
- woman_strictly_prefersUnder a woman's true ranking (unmatched worst), outcome a is strictly better than outcome b.
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.
/-- In the 3-man, 3-woman market with complete rankings, three known agents already let a woman manipulate men-proposing deferred acceptance safely and profitably: woman 0 (true ranking m0 > m1 > m2) knows woman 1 (m1 > m0 > ...), man 0 (w1 > w0 > ...) and man 1 (w0 > w1 > ...), and swaps m1 and m2. So the RAT-degree of deferred acceptance without truncation is at most 3 here, not 5: the conjecture of arXiv:2502.18805 (Sec. 8.1) that 5 is tight fails in this market, where 5 is all the other agents. -/theorem da_three_by_three_three_known_safely_manipulable : da_woman_k_known_safely_manipulable 3 3 3 := by let km : Fin 3 → Fin 3 → Fin 3 := ![![1, 0, 2], ![0, 1, 2], ![0, 1, 2]] let kw : Fin 3 → Fin 3 → Fin 3 := ![![0, 1, 2], ![1, 0, 2], ![0, 1, 2]] let T : Fin 3 → Fin 3 := ![0, 1, 2] let P : Fin 3 → Fin 3 := ![0, 2, 1] -- the outcome only depends on the unknown man 2 and woman 2 have key : ∀ a : Fin 3 → Fin 3, Function.Injective a → ∀ b : Fin 3 → Fin 3, Function.Injective b → woman_weakly_prefers T (deferred_acceptance ![km 0, km 1, a] (Function.update ![T, kw 1, b] 0 P) 0) (deferred_acceptance ![km 0, km 1, a] (Function.update ![T, kw 1, b] 0 T) 0) := by unfold woman_weakly_prefers decide +kernel refine ⟨0, {0, 1}, {1}, by decide, by decide, km, kw, T, P, by decide, by decide, by decide, by decide, ?_, ?_⟩ · intro rm rw hrm hrw hKm hKw have e1 : rm = ![km 0, km 1, rm 2] := by funext m; fin_cases m · exact hKm 0 (by decide) · exact hKm 1 (by decide) · rfl have e2 : ∀ X, Function.update rw 0 X = Function.update ![T, kw 1, rw 2] 0 X := by intro X; funext w; fin_cases w · simp · simp [hKw 1 (by decide)] · simp rw [e1, e2, e2] exact key _ (hrm 2) _ (hrw 2) · refine ⟨km, kw, by decide, by decide, fun _ _ => rfl, fun _ _ => rfl, ?_⟩ unfold woman_strictly_prefers decide +kernel