23 января, 2024 10:03
ОСТРАЯ НОВОСТЬ

Конспект: Як теорія ігор допомагає вирішувати життєві питання

Андрей Бремзен

Алгоритм Гейла-Шепли

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

(Строго говоря, и Нобелевки по экономике нет — эту премию вручает Шведский центробанк, а не Фонд Нобеля, — ред.).

К примеру, Ллойд Шепли. Он родился в 1923-м году, стал Нобелевским лауреатом в 2012 году. Он автор того самого алгоритма Шепли, [о котором вы слышали в новостях]. Точнее было бы назвать его алгоритм Гейла-Шепли, потому что Дэвид Гейл – соавтор этой работы. К сожалению, Гейл умер несколько лет назад, а Нобелевские премии посмертно не присуждают. Исследование Шепли очень многогранно. Студентам-экономистам мы рассказываем о векторе Шепли, это так называемая концепция решения кооперативной игры. Например, нужно разделить деньги между уличными музыкантами, которые играют вместе. Один играет на скрипке, другой – на гитаре, третий – на саксофоне. За вечер им набросали 3000 рублей. Как разделить деньги, если известно, что вдвоем саксофонист и скрипач заработали бы 400 рублей, а саксофонист и гитарист – 800? Поровну поделить не совсем хорошо, потому что вклад [музыкантов в общее дело] разный. Решение подобной ситуации и разработал доктор Шепли.

Существует еще индекс Шепли-Шубика, который применяется к расчетам влияния фракций в парламенте. Например, есть 100-местный парламент. У одной партии 38 мест, у другой — 27, у последней — 35. Какая из партий более влиятельная, каков вес влияния? Если считать, что решение в парламенте принимается простым большинством голосов, то ясно, что чем больше во фракции депутатов, тем она влиятельнее. Но зависимость не должна быть линейной. Если депутатов больше половины, то ясно, что вес фракции абсолютный, а у остальных – никакого веса.

Анализ сетей в украинском парламенте

Наконец, есть алгоритм Гейла-Шепли. Он был изложен в статье 62-го года. Среди прочего он касался теории двухсторонних рынков.

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

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

Есть более практический пример – ситуация, связанная с поступлением студентов в университеты. Я бы хотел поступить в первый по списку университет, если не получится – во второй, не получится – в третий и т.д. И университеты тоже хотели бы получить студентов с конкретным набором способностей, если не получится, то со вторым набором, если нет – с третьим. У каждой стороны свои предпочтения. Это ситуация двустороннего рынка.

Алгоритм Гейла-Шепли работает просто: сначала все мужчины делают предложение женщинам, которые у них первые в списке. После чего каждая женщина, которая получила несколько предложений, отказывает всем, кроме самой привлекательной партии для нее. А этому мужчине не отвечает согласием сразу, а обещает подумать. На втором шаге мужчины либо получили отказ, либо надежду на согласие. Те, над чьим предложением думают, следующий шаг пропускают и ждут результатов. А те, кто получил отказ, обливаясь слезами, вычеркивают самую привлекательную девушку и бегут скорее ко второй по привлекательности. И на каждом шаге происходит одно и то же: те, чье предложение вернули, переходят к следующей кандидатке.

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

(Лектор также говорит о том, что рынки бывают стабильными и нестабильными, — ред.)

В 70-е и 80-е годы к развитию этой теории подключился Элвин Рот – еще один Нобелевский лауреат 2012 года. Он занялся изучением работы алгоритма на практике.

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

Применение на практике

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

Рынок – это не только базар, где стоят лотки и нужно продавать помидоры. Это сложная система взаимодействий. Почему вообще появилась потребность в централизованном алгоритме? Ведь можно оставить все как есть, обособленным, как сейчас происходит в России. Каждый сам себе ищет работу, где хочет. Медицинское сообщество ни за что не борется. Закончил медицинскую школу — иди куда хочешь, ищи себе работу. Получается, что наличие централизованного рынка подобно фондовой бирже. А зачем она вообще нужна? Люди же могут друг с другом где-то тихонечко под столом торговаться. Выясняется, что наличие централизованного места, где происходят всевозможные транзакции, предпочтительнее по сравнению с децентрализацией. И экономисты, работая в качестве инженеров, могут создавать рынки там, где их дальше не было.

Конспект: Тёмная сторона экономики

Рассмотрим следующие ситуации. Первая касается государственных школ. Как распределить всех детей города по первым классам? Как определить, в какую школу отдать ребенка? Допустим, у вас есть предпочтения: я бы хотел отдать ребенка в такую школу, если не получится – в эту, если не получится – в другую и так далее. Сами школы тоже хотели бы набрать детей сообразно предпочтениям. Одним нужны дети со способностями к рисованию, другим — к математике.

В Нью-Йорке, Бостоне, Детройте, Сан-Франциско, например, была вот такая схема: все родители указывают до 5-ти школ согласно их предпочтениям. Дальше, до того, как Элвин Рот раскритиковал эту систему, все работало так: по возможности отправить ребенка в школу, которая оказалась на первом месте, максимизировать количество людей, которые получали согласие по первому пункту.

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

Главный вопрос — какую школу указывать на первом месте. Попасть в популярную школу шансов меньше. Но не указать ее первой, значит, все-таки не использовать свой шанс. Хотя выше вероятность попасть в школу, которая идет, например, третьей в списке. Переставить ее на первое? Таким образом, возникает простор для стратегических манипуляций.

До введения алгоритма Гейла-Шепли во всех газетах писали, что родители этими манипуляциями занимались. Более того, Департамент Бостонского образования их к этому подталкивал, советуя указывать первой не самую популярную школу. А с точки зрения работы алгоритма лучше бы, чтобы все указывали как раз то, чего хотели [на самом деле]. В Бостоне манипуляция приносила выгоду. Что, кстати, было плохо с точки зрения социальной справедливости.

Книга: Нобелівський лауреат про тягар глобалізації

Что значит хорошая школа? Хорошая школа – это больше шансов поступить в высшую школу, потом — в хороший колледж, а потом получить престижную работу. И прежняя система, в которой нужно было манипулировать для получения оптимального результата, способствовала имущественному неравенству, его консервации. Это нежелательный результат. Хотелось бы с этим бороться, если мы уж замышляем справедливую систему… В связи с разными требованиями в разных школах потребовались некоторые модификации алгоритма Гейла-Шепли. Например, в США необходимо соблюдать расовый баланс. Предпочтения школ могут быть разными, но результат должен быть честным, с точки зрения общества, и он должен исключать манипуляции со стороны родителей.

О пересадке органов

Казалось бы, какое отношение донорские почки имеют к школам, но на самом деле математически задача очень похожа. У человека есть две почки. Если у кого-то из его близких обе почки отказали, то теоретически он мог бы пожертвовать одну из своих почек. При этом качество его жизни заметно не ухудшится.

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

Удивительный факт. Это объясняется тем, что в процессе беременности у женщин вырабатываются антитела к белкам отца ребенка и они потом могут препятствовать успешной трансплантации. Но такие экономисты-инженеры, как Элвин Рот, не обошли вниманием и эту сферу и уже в 80-е годы пришли к выводу, что если почка мужа не подходит жене, а почка незнакомого им человека не подходит его жене, то можно попробовать сделать операцию крест-накрест.

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

В 2003 году был первый тройной обмен, когда было три донора и три реципиента. Довольно ясно, что нет никакого физического ограничения. В 2011 году, правда, началось это все с донора-альтруиста, который решил пожертвовать свою почку тому, кому она нужна, а не кому-то из своих знакомых. Таким образом, была запущена гигантская цепочка. От благородной жертвы одного человека выиграли тридцать. Все связаны таким образом, что почка первого из них досталась нуждающемуся, донор из второй пары, чья почка не подходила его реципиенту, пожертвовал третьей и так далее.

Конспект: Пастка для української економіки

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

В России массового применения алгоритма Гейла-Шепли нет ни в медицинской, ни в образовательной среде. ЕГЭ как инструмент при поступлении в вузы изначально был светлой идеей, близкой к алгоритму Гейла-Шепли. Школьник подает документы во все вузы. А дальше вуз отбирает. В принципе, теоретически ничего не мешало запустить такой алгоритм: на сайт Министерства образования каждый школьник присылает свои результаты ЕГЭ и список предпочтения из разных вузов. Каждому школьнику была бы представлена возможность попробовать себя. А не выбирать только одно место для поступления.

Желаемый университет или доступный? А как узнать, где больше шансов поступить? А равны ли шансы отличников из провинции и из столицы? К сожалению, реализация идеи оказалась невозможной. И если поначалу можно было указывать сколько угодно мест, то теперь разрешается подавать только на пять программ. А любое заранее фиксированное количество программ сразу приводит к тому, что перед школьниками снова стоит вопрос о том, как бы эти ценные пять мест аккуратно выбрать.

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

Проверьте

Як змінилися оборонні витрати країн НАТО від початку війни в Україні

На тлі анексії Криму та початку війни на Донбасі країни-члени НАТО домовилися намагатися нарощувати оборонні …

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *