AFTD Auto-Formalizing Theoretical Domains

hollow_shell_market

def

The cyclic Hollow-Shell marriage market C_n on n men and n women indexed by Z/nZ: man g ranks woman h at ((h - g) mod n) + 1 and woman h ranks man g at n - ((h - g) mod n), and each agent strictly prefers a partner with smaller rank.

Statement

def hollow_shell_market (n : ℕ) : MarriageMarket (Fin n) (Fin n)
Defined in
A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem (2026), arXiv:2609.17418, eq. (1), Prop. 5.1, Sec. 7.1
Verified
02 Oct 2026
Axioms
none listed
Built on 2
  • MarriageMarketA marriage market with types M and W consists of a relation pref_m : M → W → W → Prop representing men's preferences over women, and a…
  • cyclic_offsetFor i, j in {0, ..., n-1}, the forward cyclic offset from i to j is (j - i) mod n, a number in {0, ..., n-1}.
Used by 1

Lean source view module on GitHub

/-- The cyclic Hollow-Shell profile `C_n` (arXiv:2609.17418, eq. (1)): man `g` ranks woman `h` at `((h - g) mod n) + 1` and woman `h` ranks man `g` at `n - ((h - g) mod n)`; an agent prefers the partner it ranks lower. -/
def hollow_shell_market (n : ℕ) : MarriageMarket (Fin n) (Fin n) :=
  ⟨fun g h h' => cyclic_offset g h + 1 < cyclic_offset g h' + 1,
    fun h g g' => n - cyclic_offset g h < n - cyclic_offset g' h⟩
See it in the graphDiscuss this resultChallenge it