Теперь давайте изучим несколько свойств этого алгоритма. Самое главное свойство, которое, собственно, и доказывает, что у нас для любого набора предпочтений найдется по крайней мере один стабильный мэтчинг. Оказывается, что в результате работы алгоритма отсроченного принятия предложения гарантированно получится стабильный мэтчинг. Для того чтобы это доказать, нужно проверить два свойства. Во-первых, что выполняется свойство индивидуальной рациональности, и во-вторых, что выполняется свойство парной рациональности. Давайте проверим свойство индивидуальной рациональности. Предположим противное: пусть оно не выполняется. Тогда найдется какой-то мужчина или какая-то женщина, которым было бы выгоднее остаться одному. Ну, давайте предположим для определенности, что нашелся мужчина m, которому было бы выгоднее остаться одному, чем быть вместе с той альтернативой, которая получилась в результате работы алгоритма отсроченного принятия предложения. Но это невозможно. В алгоритме мужчина m не мог сделать предложение женщине μ(m), то есть той женщине, которая у него получилась в этом мэтчинге μ, потому что она хуже в списке его предпочтений, чем альтернатива «остаться одному», а это означает, по определению алгоритма, по описанию алгоритма, что мужчина m никогда бы не сделал предложение этой женщине μ(m). Точно так же, если бы вдруг в этом мэтчинге нашлась бы женщина w, которая оказалась в паре с мужчиной, который хуже, чем альтернатива «остаться одной», мы бы получили, что это невозможно, потому что, по описанию алгоритма отсроченного принятия предложения, женщина отказывает любому мужчине, который хуже, чем альтернатива «остаться одной». Таким образом, мэтчинг μ обладает свойством индивидуальной рациональности. Теперь проверим, что мэтчинг μ обладает свойством парной рациональности. Снова предположим противное. Пусть нашлась такая пара m и w, такие мужчина и женщина, что им было бы лучше вместе, чем с теми парами, которые получились в результате работы алгоритма отсроченного принятия предложения. Но если для мужчины m женщина w лучше, чем та женщина, которая находится в паре в соответствии с мэтчингом μ, то это означает, что мужчина m обязан был раньше сделать предложение вот этой вот женщине w, и раз они не остались в паре, то это означает, что женщина w отказалась от этого предложения. Но тогда получается, что для женщины w альтернатива, которая у нее есть в мэтчинге μ, лучше альтернативы «быть вместе с мужчиной m». А это противоречие тому предположению, которое мы сделали до этого: что для мужчины m и женщины w быть вместе друг с другом было бы лучше, чем вместе с теми парами, которые у них есть в мэтчинге μ. Полученное противоречие доказывает, что мэтчинг μ обладает свойством парной рациональности. Мы рассмотрели алгоритм отсроченного принятия предложения, в котором делали первыми предложения мужчины. Естественно, может возникнуть вопрос: а почему же первыми не могут делать предложения женщины? Могут, тогда получится в каком-то смысле симметричный алгоритм. Мы будем называть соответственно M-proposing DAA — тот алгоритм, в котором первыми предложения делают мужчины, а W-proposing DAA — алгоритм, в котором первыми делают предложения женщины. Если применить W-proposing DAA к предыдущему примеру, то получится мэтчинг, в котором мужчина m1 будет в паре с женщиной w1, мужчина m2 будет в паре с женщиной w3, а мужчина m3 будет в паре с женщиной w2. Естественно, выполняется свойство, аналогичное свойству 1, то есть мэтчинг, который получается в результате работы W-proposing DAA, тоже является стабильным. Еще одно определение. Давайте называть женщину w достижимой для мужчины m, если существует по крайней мере один стабильный мэтчинг, в котором мужчина m находится в паре с женщиной w. В предыдущем примере существовало два стабильных мэтчинга. Мужчина m1 в этих стабильных мэтчингах находился оба раза с женщиной w1, поэтому она является единственной достижимой для него женщиной. Для мужчины m2 и m3 достижимыми являются женщины w2 и w3, поскольку найдутся такие стабильные мэтчинги, в которых m2 и m3 могут претендовать на w2 и на w3. Другими словами, пара не является достижимой в тех случаях, если она слишком хороша или, наоборот, слишком плоха, чтобы встретиться вместе в стабильном мэтчинге. Можно дать и симметричное определение достижимости мужчины m для женщины w. В предыдущем примере для женщины w1 был достижимым только мужчина m1, в то время как для женщин w2 и w3 были достижимы мужчины m2 и m3. Давайте рассмотрим еще несколько свойств алгоритма отсроченного принятия предложения. В результате работы M-proposing DAA каждый мужчина получает наилучшую из достижимых для него женщин, то есть этот алгоритм приводит к такому стабильному мэтчингу, в котором все мужчины оказываются довольными. Каждый из них оказывается в паре с той женщиной, которая является наилучшей из достижимых для него. Наоборот, симметричное свойство. В результате работы W-proposing DAA каждая женщина получает наилучшего из достижимых для нее мужчин. В каком-то смысле это свойство является хорошей новостью. Существует рецепт успеха: та сторона, которая делает предложение, получает наилучшего возможного, достижимого, партнера. То есть нужно не ждать, а делать предложения первыми. Еще одно свойство. Если есть два стабильных мэтчинга μ1 и μ2, причем эти мэтчинги можно сравнить с точки зрения предпочтений мужчин, то есть предположим, что в мэтчинге μ1 у всех мужчин в паре стоит не худшая альтернатива, чем в мэтчинге μ2. Тогда оказывается, что для всех женщин мэтчинг μ1 будет не лучше мэтчинга μ2, то есть, наоборот, для женщин в мэтчинге μ1 будет в паре стоять не лучший мужчина, чем в мэтчинге μ2. То есть если есть два каких-то стабильных мэтчинга, которые можно сравнить с точки зрения предпочтений мужчин, — один из них лучше другого, то с точки зрения женщин, эти два стабильных мэтчинга будут сравниваться с точностью до наоборот. Лучшим будет тот, который хуже для мужчин. И это в каком-то смысле плохая новость. Не получится сделать хорошо абсолютно всем. Интересы мужчин и женщин оказываются противоположными. В стабильных мэтчингах чем лучше пара, которая есть у мужчин, тем хуже пара, которая есть у женщин. Подчеркну, что речь идет о сравнении только стабильных мэтчингов. Давайте рассмотрим такой пример свадебного рынка. Даны 4 мужчины, 4 женщины и их предпочтения на множестве соответствующих альтернатив. Можно проверить, что при таком наборе предпочтений существует 4 стабильных мэтчинга. Эти мэтчинги μ1, μ2, μ3 и μ4 перечислены на слайде. Мэтчинг μ1 получается в результате работы алгоритма отсроченного принятия предложения, в котором предложения делают мужчины. Он является наилучшим из стабильных мэтчингов для мужчин и наихудшим из стабильных мэтчингов для женщин. Можно проверить, что мэтчинг μ4 получается в результате работы алгоритма отсроченного принятия предложений, в котором предложения делают женщины. И он является наилучшим из стабильных мэтчингов для женщин и наихудшим из стабильных мэтчингов для мужчин. Мэтчинги μ2 и μ3 хуже для мужчин, чем мэтчинг μ1, но лучше, чем мэтчинг μ4. Обратим внимание, что мы не можем сравнить между собой мэтчинги μ2 и μ3, потому что нельзя про них сказать, что в одном из них для всех мужчин альтернативы, которые у них есть, не хуже, чем в другом мэтчинге. Точно так же мэтчинги μ2 и μ3 хуже для женщин, чем мэтчинг μ4, но лучше для женщин, чем мэтчинг μ1. При этом мы снова не можем сравнить мэтчинги μ2 и μ3 с точки зрения женщин. Получается, что все стабильные мэтчинги можно упорядочить в виде вот такой вот решетки, в которой чем выше располагается мэтчинг, тем он лучше для мужчин и тем хуже для женщин. Если оказалось, что один из стабильных мэтчингов выше другого, то есть можно спуститься по цепочке, от одного к другому, то тот, который выше, является более предпочтительным для мужчин, но менее предпочтительным для женщин. Вот какими бы ни были предпочтения, все стабильные мэтчинги можно упорядочить в виде такой решетки, в которой интересы мужчин оказались противоположными интересам женщин.
