Полiт.ua Государственная сеть Государственные люди Войти
6 декабря 2016, вторник, 13:21
Facebook Twitter LiveJournal VK.com RSS

НОВОСТИ

СТАТЬИ

АВТОРЫ

ЛЕКЦИИ

PRO SCIENCE

ТЕАТР

РЕГИОНЫ

02 ноября 2012, 12:24

Как всех переженить по алгоритму Гейла-Шепли?

Эдвин Лонг. Ярмарка невест в Вавилоне (1875)
Эдвин Лонг. Ярмарка невест в Вавилоне (1875)

1 ноября профессор экономики, председатель ученого совета Российской экономической школы (РЭШ) Сергей Измалков в рамках «Публичных лекций Полит.ру» выступил с лекцией «Как правильно всех переженить». Он рассказал об алгоритмах, за которые в этом году была присуждена нобелевская премия по экономике Ллойду Шепли и Элвину Роту (последний к тому же успешно применил разработки на практике). «Им дали премию за теорию стабильных размещений и за практику дизайна механизмов», – процитировал лектор формулировку Нобелевского комитета. Этот механизм может использоваться в различных ситуациях взаимообмена между различными акторами. Собственно вопрос, на который отвечает алгоритм: а можно ли так воспроизвести обмен между участниками, чтобы всем стало немного лучше?

Надо отметить, что одно из достижений Шепли - алгоритм Гейла-Шепли не ищет ответ, как найти наилучший вариант для конкретного человека, - он направлен на то, чтобы в целом ситуация каждого улучшилась. «Алгоритм находит ровно то, как бы люди сторговались по циклам», – разъясняет Сергей Измалков. В начале лектор привел более простые примеры с обменом между домами между гипотетическими жильцами в них. В первом цикле обмена между собой обмениваются люди, каждому из которых из совокупности всех домов больше всего нравится дом другого. Их дома выключаются из обмена. Новый круг обмена происходит только между оставшимися участниками и домами. И так происходит, пока все циклы не замкнутся.

Алгоритм может применяться при размещении студентов в общежитии и при решении множества других вопросов: как распределить студентов по вузам, как всех переженить (то есть найти наиболее эффективное сочетание по партнерству между мужчинами и женщинами). Здесь ситуация усложняются тем, что нужно учитывать двустороннее предпочтение – и мужчины, и женщины имеют предпочтения. Как работает алгоритм Гейла-Шепли в этой ситуации? 

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

Однако лектор показал, что, в случае, если выбор будет делать женщины, результат может быть несколько иным. Однако позже было доказано, что изменения будут незначительны, а при больших числах – практически не окажут какого-либо влияния. При данном механизме возможны манипуляция и нечестная игра со стороны тех, кто принимает выбор. Но и тут ситуация аналогична: кто-то, конечно, может чуть улучшить свою ситуацию, однако изменение будет незначительно. 

Практическое применение алгоритма продемонстрировало, что он даже может спасать жизни - в этом в том числе заслуга Элвина Рота. С помощью алгоритма был налажен инструмент обмена между донорами почек, каждый из которых был готов пожертвовать своему близкому свой орган. Основная проблема состоит в том, что почка должна подходить по многим разным параметрам. Поэтому и понадобился взаимообмен между донорами. Правда, выяснилось, что операции нужно проводить одновременно, чтобы никто из участников обмена не смог от них отказаться, пока об этом не знает другой.

«Часть вклада Элвина Рота состояла в том, чтобы убедить госпитали закупать оборудование, выделять палаты, организовывать работу врачей таким образом, чтобы можно было проводить одновременные операции… Если проводить по три операции одновременно, то этого может быть достаточно, чтобы вообще среди всех пар доноров и людей, которым нужны почки, можно было бы обеспечить данный обмен», – отметил Измалков.

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

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

Пооблемам самоорганизации различных сообществ посвящена выходящая в издательстве О.Г.И. новая книга известного социального мыслителя, профессора и заведующего кафедрой Прагматики культуры НИУ ВШЭ, основателя и управляющего рекомендательным сервисом Имхонет, автора переведенных на различные языки книг «Экономика символического обмена» и «Манифест новой экономики» Александра Долгина. Она называется "Как нам стать договоропригодными, или Практическое руководство по коллективным действиям".

Обсудите в соцсетях

Система Orphus
Подпишитесь
чтобы вовремя узнавать о новых спектаклях и других мероприятиях ProScience театра!
3D Apple Facebook Google GPS IBM iPhone PRO SCIENCE видео ProScience Театр Wi-Fi альтернативная энергетика «Ангара» античность археология архитектура астероиды астрофизика Байконур бактерии библиотека онлайн библиотеки биология биомедицина биомеханика бионика биоразнообразие биотехнологии блогосфера бозон Хиггса визуальная антропология вирусы Вольное историческое общество Вселенная вулканология Выбор редакции гаджеты генетика география геология глобальное потепление грибы грипп демография дети динозавры ДНК Древний Египет естественные и точные науки животные жизнь вне Земли Западная Африка защита диссертаций землетрясение зоопарк Иерусалим изобретения иммунология инновации интернет инфекции информационные технологии искусственный интеллект ислам историческая политика история история искусства история России история цивилизаций История человека. История институтов исчезающие языки карикатура католицизм квантовая физика квантовые технологии КГИ киты климатология комета кометы компаративистика компьютерная безопасность компьютерные технологии коронавирус космос криминалистика культура культурная антропология лазер Латинская Америка лженаука лингвистика Луна мамонты Марс математика материаловедение МГУ медицина междисциплинарные исследования местное самоуправление метеориты микробиология Минобрнауки мифология млекопитающие мобильные приложения мозг Монголия музеи НАСА насекомые неандертальцы нейробиология неолит Нобелевская премия НПО им.Лавочкина обезьяны обучение общество О.Г.И. открытия палеолит палеонтология память педагогика планетология погода подготовка космонавтов популяризация науки право преподавание истории происхождение человека Протон-М психология психофизиология птицы ракета растения РБК РВК регионоведение религиоведение рептилии РКК «Энергия» робототехника Роскосмос Роспатент русский язык рыбы Сингапур смертность Солнце сон социология спутники старообрядцы стартапы статистика технологии тигры торнадо транспорт ураган урбанистика фармакология Фестиваль публичных лекций физика физиология физическая антропология фольклор химия христианство Центр им.Хруничева школа эволюция эволюция человека экология эпидемии этнические конфликты этология ядерная физика язык

Редакция

Электронная почта: politru.edit1@gmail.com
Адрес: 129343, Москва, проезд Серебрякова, д.2, корп.1, 9 этаж.
Телефоны: +7 495 980 1893, +7 495 980 1894.
Стоимость услуг Полит.ру
Свидетельство о регистрации средства массовой информации
Эл. № 77-8425 от 1 декабря 2003г. Выдано министерством
Российской Федерации по делам печати, телерадиовещания и
средств массовой информации. Выходит с 21 февраля 1998 года.
При любом использовании материалов веб-сайта ссылка на Полит.ру обязательна.
При перепечатке в Интернете обязательна гиперссылка polit.ru.
Все права защищены и охраняются законом.
© Полит.ру, 1998–2014.