Абитуриент, пациент, барышня на выданье… алгоритм счастья есть для всех

Заведующий кафедрой бизнес-информатики Института менеджмента и информационных технологий, доцент, доктор экономических наук Дмитрий Назаров, в сфере научных интересов которого математические и инструментальные методы в экономике, на своих лекциях рассказывает студентам о «Модели свадебного рынка», разработанной в рамках теории игр нобелевскими лауреатами по экономике 2012 года. Эта модель, кстати, вполне может помочь и абитуриентам в выборе вуза.

Нобелевская премия 2012 года по экономике была вручена двум американским ученым: экономисту и математику Ллойду Стауэллу Шепли и профессору Гарвардского университета Элвину Элиоту Роту за теорию стабильного распределения и практики устройства рынков.

Это целое направление экономики. Следуя теории нобелевских лауреатов, Дмитрий Назаров рассказывает студентам об устройстве и правилах рынка. Если рассматривать агентов рынка в качестве игроков, то для описания возможных стратегий игроков нужно разработать правила, которые бы описывали их оптимальное поведение на различных рынках, то есть отвечали на вопрос, как действовать в той или иной ситуации разным игрокам (экономическим агентам). Такие правила вырабатываются в экономике в рамках подхода, который получил название «Дизайн механизмов». Дизайном стратегий поведения и разработкой правил и игры занимаются многие выдающиеся ученые, в том числе удостоенные за свои научные труды Нобелевской премии.

Вместе с Дмитрием Назаровым предлагаем рассмотреть теорию стабильных размещений на примере задачи «Модель свадебного рынка».

«Общая постановка задачи очень проста. Пусть имеются агенты двух типов, – читает Дмитрий Назаров её условия. – У агентов одного типа есть предпочтения на множестве агентов другого типа. То есть каждый агент может поставить в цепочку агентов другого типа по убыванию. Необходимо распределить агентов одного типа по агентам другого типа так, чтобы все остались довольны своим выбором.

Введем обозначения:

P(w): предпочтения женщин на множестве мужчин (у произвольной женщины есть выбор между альтернативами в виде мужчин или «остаться одинокой»)

P(m): предпочтения мужчин на множестве женщин (у произвольного мужчины есть выбор между альтернативами в виде женщин или «остаться одиноким»).

Математический алгоритм должен найти соответствие мужчины женщине и наоборот. Предпочтения мужчин и женщин представлены выше.

Мужчина m1 из всех женщин, а их в данной ситуации 3, предпочитает женщину w2, только потом w3 и уж в последнюю очередь – w1. Есть у него и четвёртый вариант – «остаться одному».

Мужчина m2 на первое место ставит женщину w1, на второе – w2 и т.д.

А вот женщина w3, например, предпочтет только мужчину m3, в противном случае «останется одна», потому что уровень предпочтения мужчин 2 и 1 для неё более низкий, чем желание остаться одной».

Дмитрий Назаров ставит вопрос: если мы хотим наложить какие-то свойства на получившиеся распределения, сможем ли мы получить мэтчинги – соответствие мужчины женщине. Результат вы видите ниже.

Мэтчинги:

Однако не все мэтчинги устойчивые, есть и неустойчивые. Посмотрите, мужчина m2 предпочитает женщину w1, а женщина w1 предпочитает мужчину m3, то есть взаимность отсутствует. Поскольку w1 предпочитает m2 и не предпочитает m3,  мэтчинг w1 и m3 устойчивый. Мужчина m2 также предпочитает w1, но она уже занята и не расстанется со своим партнером и т.д.

В итоге хотя бы одна из этих пар распадается. В представленном списке дама w3 лучше останется одной, чем с m2. Ей этот вариант не подходит.

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

«Оказывается, можно потребовать, чтобы распределение удовлетворяло свойствам индивидуальной и парной рациональности, – когда никто не хочет расставаться со своим партнёром, не желая искать более подходящий вариант, – говорит Дмитрий Назаров. – На этот случай есть другой алгоритм, разработанный Девидом Гейли и Ллойдом Шепли, который так и называется «Алгоритм отсроченного принятия предложения» (M-DDA propousing)».

Кто первый, тот и в дамках

 «Механизм действия алгоритма M-DDA propousing (см. ниже) прост и понятен, – продолжает «свадебную» математику Дмитрий Назаров. – Первым шагом нужно договориться о том, что первыми выбор делают мужчины (или женщины M-DDA). Каждый из них выбирает лучший вариант: m1 выбирает w2, m2 – w1, m3 – w1. Как видите, w1 получает сразу два предложения – от m2 и m3. В предпочтениях у этой женщины m3 и только потом m2. Значит, она примет предложение мужчины m3. То есть образуется пара w1 и m3. Тогда как женщина w2 получила предложение от m1, а других предложений ей не поступило, поэтому она остаётся с m1.

Mужчина m2 предложений не получил, таким образом, он остался один. Свободный мужчина вынужден в своих предпочтениях спуститься ниже, – к женщине w3, которая на этот момент не занята. Но она не примет его предложение, потому что она в своих предпочтениях лучше останется одна, чем будет с m2. Следовательно, m2 в своих предпочтениях спускается ещё ниже, к w2. Женщина w2, получая предложение от m2, видит, что у неё ещё было предложение от m1. В своих предпочтениях она видит, что m1 находится на гораздо выгодных позициях, поэтому отказывает m2. В результате сложившихся мэтчингов w3 и m2 останутся без пары.

«Алгоритм отсроченного принятия предложения» (M-DDA propousing)»:

У рассмотренного алгоритма есть ряд интересных свойств. Алгоритм работает везде и всегда. Первое правило алгоритма соответствует жизненной логике: кто начинает, тот и получает лучшее предложение. Если начинают мужчины, то мужчины и получают лучшие пары. Если начинают женщины, то женщины получают лучшие пары. Соответственно, вы видите математически доказанное первое правило рынка – действуй первым. Второе правило – одновременно удовлетворить предпочтения всех нельзя. Всегда кто-то будет недоволен.

Кроме того, можно из этой задачи-игры сделать и другие выводы. Оказывается, человек может осуществлять стратегические манипуляции, то есть указывать свои неверные предпочтения. Например, женщина w2 захотела быть только с m1 и больше ни с кем. Она говорит, что будет с ним, либо останется одна. Получается, что она манипулирует, высказывая свои ненастоящие предпочтения. И такие стратегические манипуляции крайне опасны, поскольку в этом случае может получиться ненастоящее равновесие, рынок может быть «перегрет».  

Абитуриенты

Всё вышесказанное по аналогии «мужчина-женщина» можно переложить на другие сферы жизни, к примеру, «университет – абитуриенты».

Понятно, что у каждого абитуриента в предпочтении несколько вузов для поступления. Они упорядочены в строгом соответствии с их предпочтениями. В свою очередь, у каждого вуза также есть требования к абитуриентам, например, по среднему баллу ЕГЭ.

Проще говоря, университет исходя из предпочтений получает тех или иных абитуриентов. Абитуриент подает заявление в вуз, не всегда руководствуясь своими настоящими предпочтениями, понимая, что с его, к примеру, 210 баллами, он хотел бы поступить в московский вуз, но сознает высокую конкуренцию и потому лучше поступит на бюджетное место в Екатеринбурге, чем будет пробовать себя там, потому что, скорее всего,  не поступит на бюджетное место (проиграет). Хотя подчеркнем, это ненастоящее его предпочтение. Таким образом, он тоже манипулирует рынком в определенном смысле.

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

Идея-то не нова!

Алгоритм «Модели свадебного рынка» разработан достаточно давно, в 1962 году. Полвека прошло от разработки, изобретения этого алгоритма до Нобелевской премии. А возник он из очень простых соображений. В США не хватало врачей в госпиталях. Стали агитировать студентов уже с 1-2 курсов в те или иные больницы. Таким образом, студенты с начала учёбы знали, где им предстоит работать. Это решение имело недостатки. Во-первых, студенты теряли мотивацию к знаниям, так как конкретно знали, на каком рабочем месте будут работать. Во-вторых, как правило, к окончанию вуза у студентов образуются семейные пары (устойчивые мэтчинги), и случалось так, что пара распадалась, так как распределялась на работу в разные города и даже штаты. Это вызывало недовольство среди студентов, а изменить что-то было очень сложно. Тогда и обратились за составлением алгоритма распределения «врач-больница».

Кстати, аналогичным путем в Америке решают задачу о донорах и реципиентах при трансплантации органов и при распределении учеников по школам.

Вопрос предпочтений по Назарову

Дмитрий Назаров сожалеет, что мало кто из студентов знает об алгоритме отсроченного принятия предложения теории американских экономистов, поэтому старается популяризировать её на своих лекциях. Переложив теорию на практику, кроме озвученных, он задает студентам и другие задачи, например, о подборе соседей (когда участники рынка одного типа). Студенты Дмитрия Назарова выполняют лабораторные и самостоятельные работы по данной теории.

В данной теории есть очень важный момент – это построение модели предпочтений (он остается за рамками алгоритма M (W)-DDA), то есть выработке критериев, которые позволяют построить, например, такую цепочку:

В своей докторской диссертации Дмитрий Назаров также рассмотрел вопрос построения модели предпочтений на основе получения экспертных оценок и обработки их и с помощью технологий нечеткого управления. Поскольку у разнородных агентов рынка параметры различны, построение таких цепочек сводится к различным процессам рейтингования, при этом чёткие предпочтения не всегда просто найти. Теория нечётких множеств позволяет реализовать такой процесс эффективно с учётом имплицитных факторов рынка. Его исследования опубликованы в более, чем 15 статьях, индексируемых в международных базах Scopus и WoS, а доклады представлены на конференциях с очным участием в Париже, Вене, Астане, Баку, Салониках, Санкт-Петербурге, Москве и др.

Применение описанной выше модели возможно на многих рынках. В частности, ее могли бы использовать брачные агентства, выполняющие задачу свахи с учетом предпочтений потенциальных женихов и невест (по сути они это и делают), взаимоотношениях работника (выпускника вуза) и работодателя, абсолютно точно таким же образом устроен механизм риэлтерских услуг.  «Алгоритм известен, но как его применить, выстроить, в этом и состоит формализация задачи. Бизнес-аналитик, специалист, занимающийся анализом экономического поведения в целях повышения ценности бизнеса, должен апеллировать такими моделями, применять их для конкретной практической деятельности», – уверен Дмитрий Назаров.

В жизни, как на рынке

«Вариантов приложения данной идеи много и в торговле, и в сфере общественного питания. У каждого предприятия есть предпочтения в потребителях, фирмах-партнерах и т.д.  Всё это можно усовершенствовать с помощью построения модели предпочтений, – говорит Дмитрий Назаров. – Таким образом часто решают задачи в разных сегментах рынка. Хорошо это должно работать и в прямых продажах».

На примере ключевой модели предпочтений Дмитрий Назаров предлагает решать задачи так называемого автозонирования. В магазине существуют зоны с разным уровнем продаж, где-то продают больше, где-то – меньше.  На основании визуальных данных за несколько месяцев и инструментов бизнес-аналитики можно определить самые популярные зоны торговли, попытаться составить портрет потребителя для разных зон и оптимизировать процесс продаж с помощью построения модели предпочтений. Критерием того, что получилось, можно считать устойчивые мэтчинги – сочетания «покупатель – товар». Руководствуясь этим, продавцы могут выставлять свои товары в более выигрышных местах, либо менять ассортимент товаров.

Сейчас пора вступительных экзаменов, и выбор абитуриентами вузов и вузами абитуриентов — одна из ключевых задач, которую может помочь решить описанный выше алгоритм. Действительно, каждый вуз имеет уникальные предпочтения и может манипулировать выбором абитуриентов за счет дополнительных критериев. Для этого необходимо разработать дизайн механизма рынка «абитуриент — вуз».

«Хотелось бы отметить, – говорит Дмитрий Назаров, – что этот процесс итерационный (многошаговый) и должен всякий раз соответствовать требованиям Министерства образования и науки, а поэтому применение модели предпочтений и алгоритма отсроченного принятия предложения, безусловно, станет темой курсовых и выпускных квалификационных работ студентов направлений “Бизнес-информатика” и “Информационная безопасность” в последующие годы».

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

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

Заведующий кафедрой бизнес-информатики Института менеджмента и информационных технологий, доцент, доктор экономических наук Дмитрий Назаров, в сфере научных интересов которого математические и инструментальные методы в экономике, на своих лекциях рассказывает студентам о «Модели свадебного рынка», разработанной в рамках теории игр нобелевскими лауреатами по экономике 2012 года. Эта модель, кстати, вполне может помочь и абитуриентам в выборе вуза.