Примеры

Для демонстрации этих определений будут рассмотрены два очень простых примера задачи устойчивых паросочетаний.

Для начала допустим, что имеется множество из двух мужчин {m, m’ } и множество из двух женщин {w, w’ }. Списки предпочтений выглядят так:

• m предпочитает w женщине w’;
• m’ предпочитает w женщине w’;
• w предпочитает m мужчине m’;
• w’ предпочитает m мужчине m’.

Если рассматривать этот набор списков предпочтений на интуитивном уровне, он представляет ситуацию полного согласия: мужчины сходятся во мнениях относительно порядка женщин, а женщины — относительно порядка мужчин.

В такой ситуации существует уникальное устойчивое паросочетание, состоящее из пар (m, w) и (m’, w’). Другое идеальное паросочетание, состоящее из пар (m’, w) и (m, w’), не является устойчивым, потому что пара (m, w) образует неустойчивость по отношению к этому паросочетанию. (Как m, так и w предпочли бы бросить своих партнеров и образовать новую пару.)

В следующем примере ситуация немного усложняется. Предположим, действуют следующие предпочтения:

• m предпочитает w женщине w’;
• m’ предпочитает w’ женщине w;
• w предпочитает m’ мужчине m;
• w’ предпочитает m мужчине m’.

Что же происходит на этот раз? Предпочтения двух мужчин противоположны (они ставят на первое место разных женщин); то же самое можно сказать и о предпочтениях двух женщин. Однако предпочтения мужчин полностью противоречат предпочтениям женщин.

Во втором примере существуют два разных устойчивых паросочетания. Сочетание, состоящее из пар (m, w) и (m’, w’ ), является устойчивым — оба мужчины довольны, насколько это возможно, и ни один из них не покинет своего партнера.

Однако паросочетание из пар (m’, w) и (m, w’ ) тоже устойчиво, так как обе женщины довольны, насколько это возможно. Запомните этот важный момент, прежде чем двигаться дальше, — в заданной ситуации может существовать более одного устойчивого паросочетания.