Интеллектуальные развлечения. Интересные иллюзии, логические игры и загадки.

Как найти жену и донора почки?

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

2012 год. Ллойд Шепли и Элвин Рот «Как найти жену и донора почки»

Учёные первыми описали схему «мэтчинга». Шепли и Гейл исследовали проблему формирования стабильных супружеских пар для двух равновеликих групп мужчин и женщин. Они доказали, что существует алгоритм, позволяющий задать такую парную конфигурацию, при которой невозможно создание новых обоюдовыгодных пар. В конце статьи авторы выразили надежду на то, что их алгоритм когда–нибудь будет применён на практике.

Вскоре нашёлся экономист, который исполнил желание Шепли и Гейла. Элвин Рот применил математический алгоритм для решения таких проблем типа распределения медиков–интернов по больницам, школьников по госшколам, а также для сведения доноров почек с пациентами, ожидающими пересадки. Однако механизм мэтчинга пока не идеален, так как сильно зависит от того, насколько правдиво игроки сообщают о своих предпочтениях.

Лекция Алексея Савватеева про вектор Шепли

Те, кто не осилят более часа видео, ниже краткое содержание:

1. имея толпу людей, есть алгоритм, чтобы можно было бы делать устойчивые пары из 2–х человек. Суть в том, что у каждого человека есть списки предпочтений, они сортируют их в порядке убывания значимости и идут к своим возможным партнерам. Если не получилось, то идут к следующему, если получилось, то образуют устойчивую пару, ну или становятся в ожидание, т.к. сами находятся не в первых позициях. Чтобы сделать устойчивую пару из трех людей — все сложнее, для четырех наука обосралась и не нашла решения. Суть алгоритма очень простая, я удивлен за что тут вообще премию давать — за доказательство?

2. вектор Шекли. На самом деле и не вектор, просто так кто–то обозвал. Смысл в том, что не всех устраивает деление "поровну". Надо было научиться как–то разделять профит или ответственность между элементами группы. Это можно сделать если понять какой вклад вносят каждое из сочетаний элементов.

Dmitry   20.10.2013