安定マッチング

$|A|=|B|=n$ とし、$A$ の各元は $B$ の元全体に、$B$ の各元は $A$ の元全体に、同順位のない順位（選好）を付けているとする。$A$ と $B$ の間の完全マッチング $M$ に対し、$M$ で組になっていない $a\in A$、$b\in B$ が、「$a$ は $M$ での相手より $b$ を好み、$b$ も $M$ での相手より $a$ を好む」を満たすとき、$(a,b)$ をブロッキング対という。ブロッキング対をもたない完全マッチングを安定マッチングという。