А вот если цен нет? Как, например, распределить первоклассников центрального округа Курска между школами центрального округа. У родителей первоклашек выстроены определенные предпочтения относительно школ, связанные с удаленностью школы от дома, качеством преподавания, размером и составом класса и проч. В школах центрального округа хотели бы учиться дети и из других округов - как быть с ними? И у школ могут быть предпочтения в отношении учащихся: "ученики приносят славу ей". Возникает экономическая проблема - как оптимальным образом распределить множество учащихся между множеством школ, да так, чтобы это распределение было устойчиво, независтливо и при этом бы не использовался ценовой механизм или механизм взяток-подношений.
Для этого и разработали алгоритм Гейла-Шепли. Популярно о нем можно почитать у Сонина и Измалкова в "Вопросах экономики" здесь. Этот алгоритм сейчас активно используют при различных видах неценовых распределений: студентов между вузами, больных между больницами, инвалидов и престарелых между работниками системы соцобеспечения и т.д. Частным случаем использования этого алгоритма является "брачный рынок"
На прошлой неделе мы пытались формировать "брачные пары" в Щиграх, Обояни и Мантурово. Студентки формируют свои предпочтения в отношении студентов (а юноши, соответственно, в отношении девушек) порядковым образом, т.е. этот нравится больше всех, этот на втором месте и т.д. Затем каждый претендент "подкатывает" к своей избраннице с предложением. Если предложений у избранницы два и больше, то она оставляет наилучшее предложение, а те кого "отшили" идут дальше искать счастья у следующей по порядковому номеру избранницы. Те девушки к кому предложений не поступало ждут, когда и до них дойдет очередь. Таким образом, переходя от основной к первой запасной, второй запасной и т.д., посредством перебора молодые люди находят себе "суженых".
Одним из требований алгоритма является, чтобы он давал устойчивый результат. В нашем случае это означает, что если мы поменяем условия, т.е. "предложение" руки и сердца делают девушки, а юноши выбирают, то результат должен быть тем же самым. Так вот в Обояни и Мантурово результат был устойчив, а в Щиграх не сошлось. В субботу еще раз попробую сыграть с курской группой. И что там с Щиграми не так?