Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения).
|proof=
Если Докажем от противного, что для каждого мужчины не существует устойчивого паросочетания, в котором его супругой была бы более желанная для него женщина. Предположим, для мужчины <tex>A</tex> это свойство не выполняется. Так как он оказался женат не на лучшей из кандидатур, то существует женщина <tex>a</tex>, которая предпочла ему другого, более привлекательного мужчину <tex>B</tex>, при этом женщина <tex>a</tex> для мужчины <tex>B</tex> стоит на первом месте в его текущем списке. Предположим, существует устойчивое паросочетание, содержащее <tex>\langle A, a\rangle</tex>. По определению, в устойчивом паросочетании нет неустойчивых пар. Пара <tex>\langle B, a\rangle</tex> станет неустойчивой, если <tex>B</tex> будет предпочитать <tex>a</tex> своей супруге. Значит, <tex>B</tex> женат на ком-то, кто лучше, чем <tex>a</tex>. Но такое невозможно, так как <tex>a</tex> стоит для него на первом месте. Таким образом, если женщина <tex>a</tex> вычёркивается из списка предпочтений мужчины <tex>A</tex>, то ни одно устойчивое любое паросочетание не будет содержать пары , содержащее <tex>\langle A, a\rangle</tex>, неустойчиво.
}}
