Расширения

Мы начали с определения устойчивого паросочетания и только что доказали, что алгоритм Гейла–Шепли действительно строит его. Теперь будут рассмотрены некоторые дополнительные вопросы относительно поведения алгоритма Гейла–Шепли  и его связи со свойствами различных устойчивых паросочетаний.

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

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

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

С другой стороны, оно станет достижимым при выполнении версии алгоритма, в которой предложение делают женщины. А в более крупных примерах, в которых с каждой стороны задействовано более двух участников, может существовать еще большее количество возможных устойчивых паросочетаний, многие из которых не могут быть сгенерированы никаким естественным алгоритмом.

Этот пример демонстрирует некоторую «несправедливость» алгоритма Гейла– Шепли, «подыгрывающего» мужчинам. Если предпочтения мужчин идеально распределены (то есть все они ставят на первое место разных женщин), то при любом выполнении алгоритма Гейла–Шепли каждый мужчина окажется в паре со своей главной кандидатурой независимо от предпочтений женщин.

Если же предпочтения женщин полностью расходятся с предпочтениями мужчин (как в приведенном примере), то полученное устойчивое паросочетание будет насколько возможно плохим для женщин. Итак, этот простой набор списков предпочтений компактно описывает мир, в котором кому-то суждено оказаться несчастным: женщины несчастны, если предложения делают мужчины, а мужчины несчастны, если предложения делают женщины.

Давайте проанализируем алгоритм Гейла–Шепли более подробно и попробуем понять, насколько общий характер имеет эта «несправедливость».

Возникает другой, тоже очень естественный вопрос: приводят ли все выполне- ния алгоритма Гейла–Шепли к одному паросочетанию? Вопросы такого рода воз- никают во многих областях теории обработки данных: имеется алгоритм, который работает асинхронно, с множеством независимых компонентов, которые выпол- няют операции с возможностью сложных взаимодействий. Требуется определить, какую изменчивость вносит такая асинхронность в окончательный результат.

Или совершенно другой пример: независимыми компонентами могут быть не мужчины и женщины, а электронные устройства, активизирующие части крыла самолета; последствия асинхронности в их поведении могут быть очень серьезными. В текущем контексте ответ на этот вопрос оказывается на удивление простым: все выполнения алгоритма Гейла–Шепли  приводят к  одному паросочетанию.

Докажем это утверждение.