12

Математика в реальной жизни. Часть 1. Алгоритм отложенного одобрения

Математика в реальной жизни. Часть 1. Алгоритм отложенного одобрения Математика, Нобелевская премия, Элвин Рот, Ллойд Шепли, Экономика, Видео, Длиннопост

Данный пост будет первым из моих постов по применению математики в реальной жизни. В ближайших постах я хочу рассмотреть такие проблемы, как "справедливое распределение оплаты таксисту между несколькими пассажирами (попутчиками)", а также хочу в цифрах рассказать некоторые факты про автомобильные пробки. Надеюсь, что вам будет интересно, ведь тут не просто математика, а математика, применимая к жизни. Однако в первой части я затрону вопрос несколько более общий, но очень важный для всех нас с вами.

Кто же люди, изображенные на фотографии и за что они в 2012 году получили нобелевские премии по экономике? Это американские ученые, которые разработали «теорию стабильного распределения и практическое применение рыночных моделей».

Говоря русским языком, они придумали, как наилучшим с некоторой точки зрения образом свести между собой две нуждающиеся друг в друге группы людей или организаций. Например, абитуриентов с ВУЗами, учащихся со школами, организаций с сотрудниками, врачей с пациентами, поставщиков услуг с их потребителями и даже, при некоторых оговорках, мужиков с бабами.

Что значит наилучшим способом - это значит наименее конфликтным и наиболее справедливым способом.

На примере мужиков с бабами это будет выглядеть так:

0) Пусть у нас есть группа мужских и женских особей с не обязательно равным количеством (кто-то останется без пары, а что поделать). Причем у каждой особи есть свой список предпочтений особей противоположного пола. Например, Васе больше всего нравится Маша, немного меньше Даша, еще немного меньше Наташа, а на остальных он в принципе бы не женился. У каждой девушки есть такой же список парней. Задача всех поженить

Математика в реальной жизни. Часть 1. Алгоритм отложенного одобрения Математика, Нобелевская премия, Элвин Рот, Ллойд Шепли, Экономика, Видео, Длиннопост

1) Мужчины делают предложение наиболее предпочитаемой женщине;

2) Каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть», на все остальные отвечает «нет»;

3) Мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;

4) Если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;

5) Если женщине пришло наилучшее предложение, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «да» и далее предложений не принимает;

6) Шаги повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.

7) ????????

8) PROFIT!


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

Конечно в реальной жизни никто пока никого женить таким способом не собирается, зато этот же принцип уже успешно применяется в различных социально-экономических сферах жизни за рубежом, например:

1) В 1962 году была переформатирована национальная американская система подбора медицинского персонала (предполагала максимальную корреляцию запросов работодателя и работника).

2) В начале XXI века в системе среднего образования в США. В частности, на такие механизмы распределения школьников по государственным школам в США перешли Нью-Йорк, Бостон, Новый Орлеан, Вашингтон и Денвер.

3) Известны частные случаи применения алгоритма при выборе аспирантами своих руководителей.


Что можно сделать полезного с помощью данного алгоритма:

1) Создать в России справедливую систему распределения учеников по школам по примеру США, а также аспирантов по руководителям и абитуриентов по ВУЗам. Например, абитуриенты могут подавать списки ВУЗов/специальностей по своим приоритетам, а ВУЗы могут ранжировать абитуриентов по результатам ЕГЭ или на основании любой другой оценочной системы.

2) Создать систему распределения врачей по пациентам. В результате у лучших врачей будет возможность не иметь дело с не желаемыми им пациентами, плюс офигенный стимул для врачей и пациентов быть "лучше" друг для друга.

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

4) Опять же при введении соответствующих законов можно распределять данным образом создателей и получателей каких-либо услуг

5) Распределение донорских органов и т.д.


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


Вот ссылочка на очень подробную статью (осторожно - много формул!) https://www.nes.ru/dataupload/files/professors/sonin1-13.pdf


А вот небольшой видосик совсем без формул

Найдены возможные дубликаты

+2

да, помню фильм "Игры разума". Джон Неш (Рассел Кроу) объяснял друганам, как теток правильно выбирать. Кто не видел фильма - советую...

Иллюстрация к комментарию
+1
Пусть у нас есть группа мужских и женских особей с не обязательно равным количеством (кто-то останется без пары, а что поделать).

Дальше можно не читать, это буду я. Математика бесполезна.

раскрыть ветку 1
0

Зато математика говорит, что сторона, которая активно действует, оказывается в более выгодном положении. "решение получается более хорошим для стороны, которая делает предложения". Но это и без математики понятно :)

+1
Математика - гимнастика для ума! Автор, пиши скорее продолжение.
0

Любопытно, плюсую.

0
Звиздеть — не мешки ворочать, будет реализация, вот тогда и поговорим, а пока что это лишь колебания воздуха
раскрыть ветку 3
-1

Есть реализация в США, вы читали пост?

раскрыть ветку 2
0
Хорошо, есть процентные данные по этой реализации и ее улучшению по сравнению с тем, что без нее? Мне интересны конкретные данные этого метода в цифрах, без воды
раскрыть ветку 1
-1

Совсем забыл добавить - эта задача еще называется "Задача о марьяже"

Похожие посты
Похожие посты закончились. Возможно, вас заинтересуют другие посты по тегам: