AFTD Auto-Formalizing Theoretical Domains

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

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