Как-то раз n парней и n девчат собрались потанцевать. Им нужно разбиться на пары. Каждый имеет свои предпочтения относительно лиц противоположного пола, а именно, может упорядочить их от наиболее предпочтительного к наименее предпочтительному. Будем считать, что предпочтения строгие, то есть не бывает ситуации безразличия, когда несколько партнёров одинаково хороши для данного человека.
Хочется, чтобы разбиение на пары было устойчивым, т. е. чтобы не нашлось таких юноши и девушки, что если они бросят своих текущих партнёров и объединятся, то им обоим станет лучше (с точки зрения их предпочтений).
Существует ли такой набор предпочтений, что как ни разбивай на пары, всегда будет получаться неустойчивое разбиение?
Факультет экономических наук НИУ ВШЭ
Комментарии
Как я понимаю, существует.. Если мы их выстроим в ряд, скажем, что это первый мальчик, это второй и т.д... И с девочками сделаем также; так тогда неустойчивое равновесие будет тогда, когда первый мальчик предпочитает последнюю девочку, второй мальчик - предпоследнюю девочку, и асболютно аналогично для девочек. Тогда, разрывая любую связь $ Мальчик_k ; Девочка_{n-k} \cup Мальчик_f ; Девочка_{n-f} $, общество будет "более довольным", если мы теперь соединим их наоборот.
Второй мальчик предпочитает предпоследнюю девочку пред-предпоследней, пред-предпоследнюю пред-пред-предпоследней и т.д.
Аналогично с девочками. Также их выстроим, и скажем, что первая девочка предпочитает последнего мальчика предпоследнему, предпоследнего пред-предпоследнему и т.д...
Получаем циклическое предпочтение, всё время замыкающееся.
Короче, парадокс Кондерсе в других словах. Пример, с нарушенной транзитивностью. Вот. Может, и бред, конечно :)
м1 м2 м3
д3 д2 д1
д2 д1 д3
д1 д3 д2
И в чём проблема? Рассмотрим разбиение (м1-д3, м2-д2, м3-д1). Оно будет устойчивым вне зависимости от того, какие предпочтения у девочек.
А если у девочек предпочтения абсолютно противоположные? Я думал, что мы говорим об устойчивости, исходя из суммы полезности всех мальчиков и девочек. Т.е. если проранжировать их как 0,1 и 2. Тогда бОльшая полезность будет достигнута, если выберут в своём списке второго партнёра.
Никаких полезностей, и тем более их сумм, тут нет:)
Необходимо, чтобы положение обоих в паре улучшилось. Значит каждый должен, грубо говоря, подняться вверх на строчку в своих предпочтениях. Наличие такого набора означает, что чем больше раз пара распадается, тем все более улучшается положение обоих. Но число партнеров ограничено, и первый в ранге предпочтений в итоге будет достигнут. Тогда для этого человека дальнейшей пользы распад пары уже не принесет. А раз он не приносит пользы одному из партнеров, значит является устойчивым.
Можно придумать набор предпочтений и несколько последовательных разбиений, так что переход от предыдущего разбиения к следующему происходит, когда какие-то два человека объединяются, бросая своих менее предпочтительных партнёров, и при этом разбиение на последнем шаге совпадает с разбиением на первом, что убедительно докажет, что такие переходы можно продолжать бесконечно.
Если лень придумывать такой пример, можно посмотреть мой.
Показать пример
м1 м2 м3 д1 д2 д3
д1 д2 д2 м2 м1 м2
д2 д1 д1 м1 м2 м1
д3 д3 д3 м3 м3 м3
м1д1 м2д1 м2д2 м1д2 м1д1
м2д3 м1д3 м1д3 м2д3 м2д3
м3д2 м3д2 м3д1 м3д1 м3д2