da_woman_k_known_safely_manipulable
def
In men-proposing deferred acceptance with nm men, nw women and complete rankings (no truncation), some woman who knows the rankings of k other agents has a misreport that is safe (never worse, whatever the unknown agents rank) and profitable (strictly better for some rankings of the unknown agents); arXiv:2502.18805, Def. 3.1.
Statement
def da_woman_k_known_safely_manipulable (nm nw k : ℕ) : Prop
- Defined in
- College Admissions and the Stability of Marriage (1962), men-proposing deferred acceptance; It's Not All Black and White: Degree of Truthfulness for Risk-Avoiding Agents, arXiv:2502.18805 v3, Def. 3.1 and Sec. 8.1
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Built on 3
- 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_weakly_prefersUnder a woman's true ranking (unmatched worst), outcome a is at least as good as outcome b.
- woman_strictly_prefersUnder a woman's true ranking (unmatched worst), outcome a is strictly better than outcome b.
- Used by 1
- da_three_by_three_three_known_safely_manipulableIn the 3x3 market with complete rankings, a woman who knows three agents can safely and profitably manipulate men-proposing deferred…
Lean source view module on GitHub
/-- Following arXiv:2502.18805 (Def. 3.1), for men-proposing deferred acceptance in a market of `nm` men and `nw` women with complete rankings (no truncation), and a woman as the manipulator: some woman `w0`, knowing the rankings of `k` other agents (men `Km`, women `Kw`), has a report `P` instead of her true ranking `T` that is safe (never worse, whatever the unknown agents rank) and profitable (strictly better for some rankings of the unknown agents). -/ def da_woman_k_known_safely_manipulable (nm nw k : ℕ) : Prop := ∃ (w0 : Fin nw) (Km : Finset (Fin nm)) (Kw : Finset (Fin nw)), w0 ∉ Kw ∧ Km.card + Kw.card = k ∧ ∃ (km : Fin nm → Fin nw → Fin nw) (kw : Fin nw → Fin nm → Fin nm) (T P : Fin nm → Fin nm), (∀ m ∈ Km, Function.Injective (km m)) ∧ (∀ w ∈ Kw, Function.Injective (kw w)) ∧ Function.Injective T ∧ Function.Injective P ∧ (∀ (rm : Fin nm → Fin nw → Fin nw) (rw : Fin nw → Fin nm → Fin nm), (∀ m, Function.Injective (rm m)) → (∀ w, Function.Injective (rw w)) → (∀ m ∈ Km, rm m = km m) → (∀ w ∈ Kw, rw w = kw w) → woman_weakly_prefers T (deferred_acceptance rm (Function.update rw w0 P) w0) (deferred_acceptance rm (Function.update rw w0 T) w0)) ∧ (∃ (rm : Fin nm → Fin nw → Fin nw) (rw : Fin nw → Fin nm → Fin nm), (∀ m, Function.Injective (rm m)) ∧ (∀ w, Function.Injective (rw w)) ∧ (∀ m ∈ Km, rm m = km m) ∧ (∀ w ∈ Kw, rw w = kw w) ∧ woman_strictly_prefers T (deferred_acceptance rm (Function.update rw w0 P) w0) (deferred_acceptance rm (Function.update rw w0 T) w0))