«Университет открытий»: как аналитика «прикручивается» к жизни

6 Мая 2019

Просчитать оптимальный вариант развития взаимоотношений бывает очень не просто, особенно когда у каждой из сторон имеются свои предпочтения относительно другой. На финальной лекции проекта «Университет открытий» Александр Богданов, доцент кафедры информационных технологий и бизнес-аналитики ИЭМ ТГУ, на примере задачи поиска устойчивых паросочетаний рассказал, как работает алгоритм отложенного предложения.

Умение анализировать варианты развития событий и принимать обоснованные решения актуально не только в сфере бизнеса. На лекции проекта «Университет открытий» участники разобрали, как действует алгоритм отложенного принятия предложения, за разработку которого в 2012 году Ллойд Шепли был удостоен Нобелевской премии по экономике.

– Традиционно этот алгоритм объясняют на примере поиска устойчивых пар из множества мужчин и женщин, у которых имеются определенные предпочтения друг относительно друга. Задача заключается в том, чтобы распределить партнеров по парам так, чтобы ни у кого из участников не возникло желание уйти из пары или попытаться сменить партнера, то есть чтобы результат удовлетворял всех, – объясняет Александр.

Решение этой задачи предложили в 1962 году математики Девид Гейл и Ллойд Шепли. Их статья называлась «Поступление в колледж и стабильность браков». В ней авторы рассматривали проблему оптимального распределения абитуриентов по колледжам: сформулировали критерии такого распределения и поставили вопрос о его существовании. Свои рассуждения они проиллюстрировали на примере абстрактного брачного рынка, участниками которого являются мужчины и женщины, желающие вступить в брак и имеющие предпочтения друг относительно друга.

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

– Немногие математические результаты удается вот так сразу, как говорится, «из коробки», взять и «прикрутить» к практике. Обычно жизнь оказывается сложнее, и полученный математический результат приходится адаптировать к суровым условиям действительности», – поясняет Александр Богданов. – Алгоритм Гейла-Шепли не стал исключением. Со временем стало ясно, что он требует доработки. Его модификацией и вопросами практического применения занимался Элвин Рот – второй нобелевский лауреат.

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

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

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

В Институте экономики и менеджмента ТГУ данный алгоритм отложенного принятия предложения изучают на курсе «Теория игр», он применяется при распределении студентов по научным руководителям.

Для справки: Лекции «Университета открытий» организует Управление нового набора ТГУ дважды за учебный год – весной и осенью. Эти мероприятия открытые и бесплатные для всех желающих. Темы становятся известны в начале курса и публикуются на странице регистрации. Новые лекции «Университета открытий» запланированы на октябрь – ноябрь 2019 года.


Возврат к списку