Примеры

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

Для начала допустим, что имеется множество из двух мужчин {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’ ) тоже устойчиво, так как обе женщины довольны, насколько это возможно. Запомните этот важный момент, прежде чем двигаться дальше, — в заданной ситуации может существовать более одного устойчивого паросочетания.

Узнай цену консультации

"Да забей ты на эти дипломы и экзамены!” (дворник Кузьмич)