VIII Международная студенческая научная конференция Студенческий научный форум - 2016

Введение

Любовь… Глупо отрицать, что это чувство является одним из самых важных чувств в жизни каждого. Благодаря любви люди испытывают весь спектр доступных эмоций – от безудержного счастья, до полной опустошенности. Стремление найти вторую половинку заложено в природе человека, однако, в отличие от животных, которых на уровне инстинктов волнует лишь репродуктивная сторона, человеку важно найти постоянного спутника жизни, поддержку, опору, верного друга и просто любимого человека. Однако, печальная статистика показывает, что далеко не все браки приводят к счастливой семейной жизни. Многие из них не проходят проверку временем и распадаются. Процесс довольно неприятный и болезненный, поэтому каждый ищет способ избежать его и найти именно такого человека, с которым получится долго и счастливо. Важность и вечная актуальность данной проблемы привели к тому, что данным вопросом начала заниматься прикладная математика, в частности, теория игр.

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

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

Использование теории игр помогает лицу, принимающему решение, подойти к нему более обоснованно и последовательно, провести критический

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

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

Более того, как было упомянуто выше, данную науку используют для того, чтобы исследовать одно из самых волшебных, волнующих чувств, которое только может испытать человек – любовь. Так, в 2012 году Нобелевская премия по экономике была присуждена Элвину Роту и Ллойду Шепли за «теорию стабильного распределения и практическое применение рыночных моделей», в частности предложенному ими алгоритму устойчивых браков, которому и будет посвящена данная работа.

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

История теории любви в теории игр началась еще задолго до 2012 года. В 1962 году в журнале American Mathematical Monthly была опубликована работа " College admissions and the stability of marriage " (Поступление в колледж и стабильность браков) математиков Девида Гейла из Университета Брауна и Ллойда Шепли из Принстонского университета. Эта работа относилась к теории коалиционных (кооперативных) игр, которые характеризуются тем, что их участники могут объединять свои усилия и сотрудничать, получая больший по сравнению с равновесным выигрыш. Задача, которую рассматривали ученые, позже получила название задачи о марьяже.

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

Итак, пусть M = {m₁, …, mn} – мужчины и W = {w₁, …, w_m} – женщины – это два конечных непересекающихся множества игроков. Как было отмечено ранее, у каждого мужчины есть предпочтения на множестве женщин и наоборот. Представим предпочтения мужчины m_i в виде упорядоченного списка P(m_i) элементов множества W ⊃ {m_i}, а предпочтения женщин w_i в виде упорядоченного списка P(w_j) элементов множества M ⊃ {w_j}, предполагая, что все предпочтения строгие. Тогда, например, запись P(m₂) = w₁ w₅w₈…w₃ значит, что мужчине m₂ больше всего нравится женщина w₁, затем w₅, а женщина w₃нравится ему меньше всего.

Введем еще одно обозначение P, которое будет представлять собой набор предпочтений всех игроков, то есть P= {P(m₁), P(m₂), …, P(mn), P(w₁), P(w₂),…, P(w_m)}. Следовательно, можно сделать вывод, что для того, чтобы задать модель марьяжа, необходимо ввести два множества игроков M и W и набор предпочтений P.

Распределением или размещением по парам μ называется взаимно однозначное отображение множества M ⊃ W на себя, которое обладает некоторыми свойствами. Во-первых, μ(m_i) ∈ W ⊃ {m_i} и μ(w_j) ∈ M ⊃ {w_j}, что значит, что у каждого мужчины или женщины есть пара противоположного пола или он (она) остается холостым (незамужней). Во-вторых, если μ(m_i) = w_j, то μ(w_j) = mi, то есть если мужчина m_iсостоит в паре с женщиной w_j, то и женщина w_jсостоит в паре с мужчиной m_i.

Приведем конкретный пример, наглядно демонстрирующий, как происходит распределение на стабильные пары согласно описанному алгоритму. Для простоты возьмем равное количество мужчин и женщин n=m=4. Определим набор предпочтений всех игроков:

P (m₁) = w₁, w₃, w₄, w₂

P(m₂) = w₁, w₄, w₃, w₂

P (m₃) = w₃, w₂, w₄, w₁

P (m₄) = w₂, w₄, w₁, w₃P (w₁) = m₁, m₃, m₄, m₂

P(w₂) = m₁, m₄, m₂, m₃

P (w₃) = m₄, m₃, m₂, m₁

P (w₄) = m₂, m₁, m₄, m₃

Тогда матрица предпочтений для данного случая будет иметь вид:

	w1	w2	w3	w4
m1	1, 1	4, 1	2, 4	3, 2
m2	1, 4	4, 3	3, 3	2, 1
m3	4, 2	2, 4	1, 2	3, 4
m4	3, 3	1, 2	4, 1	2, 3

Первая цифра в каждой паре цифр, представленных в матрице, соответствует месту женщины, которое она занимает в предпочтениях мужчины, а вторая цифра, соответственно, месту мужчины в предпочтениях женщины. Например, для мужчины m₁ наиболее предпочтительной является женщина w₁, затем w₃, затем w₄ и наконец w₂, что соответствует набору предпочтений, указанных для него в условиях задачи.

На первом этапе каждый мужчина делает предложение наиболее предпочитаемой женщине, а каждая женщина принимает предложение самого предпочитаемого мужчины. Так, m₁ делает предложение w₁, m₂ – тоже w₁, m₃ – w₃, а m₄ – w₂. Как мы видим из матрицы, m₁также является наиболее предпочтительным для w₁, поэтому она примет его предложение, и откажет m₂. w₂и w₃также примут предложения m₄ и m₃, несмотря на то, что данные мужчины не являются для них наиболее предпочтительными, так как больше предложений им не поступило. Однако, в отличие от w₁, w₂ и w₃ скажут не радостное и уверенное «да», а кокетливо или уныло произнесут - «может быть».

	w1	w2	w3	w4
m1	1, 1	4, 1	2, 4	3, 2
m2	1, 4	4, 3	3, 3	2, 1
m3	4, 2	2, 4	1, 2	3, 4
m4	3, 3	1, 2	4, 1	2, 3

Таким образом, по результатам первого этапа мы имеем три стабильные пары, одна из который, а именно m₁ и w₁ уже точно сформирована.

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

В нашем примере отвергнутым оказался только мужчина m₂, который в этот раз делает предложение женщине w₄. Как мы видим из матрицы, на предыдущем этапе w₄вообще не поступило ни одного предложения, поэтому она принимает предложение m₂без всяких сравнений, а m₂не разрушает ни одну из сложившихся ранее пар.

	w1	w2	w3	w4
m1	1, 1	4, 1	2, 4	3, 2
m2	1, 4	4, 3	3, 3	2, 1
m3	4, 2	2, 4	1, 2	3, 4
m4	3, 3	1, 2	4, 1	2, 3

В результате мы имеем четыре стабильные пары, так как не встречаются два человека из разных пар, которые обоюдно хотели бы образовать союз, а именно m₁ и w₁, m₂ и w₄, m₃ и w₃ и m₄ и w₂. Однако, данное распределение предпочтительнее с точки зрения мужчин, так как они делают предложение первыми. Интересно посмотреть, какого будет стабильное распределение в нашем примере, если первый шаг будут делать женщины.

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

	w1	w2	w3	w4
m1	1, 1	4, 1	2, 4	3, 2
m2	1, 4	4, 3	3, 3	2, 1
m3	4, 2	2, 4	1, 2	3, 4
m4	3, 3	1, 2	4, 1	2, 3

Так, w₁ делает предложение m₁, w₂ – тоже m₁, w₃ – m₄ и наконец w₄ – m₂. По уже знакомому нам алгоритму, m₁выбирает w₁ и отвергает w₂, так как w₁является для него самым предпочтительным вариантом. m₂и m₄принимают предложения, отвечая на них не однозначное «да», а «может быть».

	w1	w2	w3	w4
m1	1, 1	4, 1	2, 4	3, 2
m2	1, 4	4, 3	3, 3	2, 1
m3	4, 2	2, 4	1, 2	3, 4
m4	3, 3	1, 2	4, 1	2, 3

Таким образом, как и в первом случае, мы имеем одну точно сложившуюся стабильную пару - m₁и w₁, что неудивительно, ведь они занимают первое место в списке предпочтений друг у друга. Также мы получаем две пары, которые могут распасться в последующих этапах.

Итак, на втором этапе отвергнутая и оставшаяся без пары w₂делает предложение следующему по списку своих предпочтений кандидату, то есть m₄. Теперь m₄имеет два предложения – от w₂и от w₃. Выбирая для себя наиболее предпочтительный вариант, он отвергает w₃и говорит «может быть» w₂.

	w1	w2	w3	w4
m1	1, 1	4, 1	2, 4	3, 2
m2	1, 4	4, 3	3, 3	2, 1
m3	4, 2	2, 4	1, 2	3, 4
m4	3, 3	1, 2	4, 1	2, 3

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

	w1	w2	w3	w4
m1	1, 1	4, 1	2, 4	3, 2
m2	1, 4	4, 3	3, 3	2, 1
m3	4, 2	2, 4	1, 2	3, 4
m4	3, 3	1, 2	4, 1	2, 3

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

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

Этап 1. Каждый холостой мужчина делает предложение наиболее привлекательной для него женщине либо выходит из игры, если одиночество для него предпочтительнее. Затем каждая женщина рассматривает все поступившие предложения и самому достойному кандидату говорит «может быть», а всех остальных отвергает. Женщина также может предпочесть одиночество лучшему кандидату и сказать ему «нет». Если женщине не сделали предложение, ей остается только ждать.

Этап 2. Каждый отвергнутый мужчина вновь делает предложение, но уже следующей по списку его предпочтений женщине, после чего каждая женщина сравнивает новое и старое предложение, и выбирает для себя одно наиболее привлекательное, а остальные отвергает.

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

Нобелевская премия по экономике в 2012 году

Модель, сформированная Гейлом – Шепли в 1962 году представляла собой математическую модель двусторонних рынков, и, на самом деле, поиск стабильного набора пар среди мужчин и женщин был лишь одним из вариантов ее использования. Классическими примерами двусторонних рынков считаются женщины и мужчины, работники и фирмы, высшее образовательные учреждения и абитуриенты, доноры и больные, нуждающиеся в пересадки органов, и для всех этих рынков поиск устойчивого размещения становился возможен благодаря алгоритму Гейла – Шепли.

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

Дело в том, что в США в 1940 – х годах наблюдалась нехватка молодых врачей, что привело к возникновению конкуренции между больницами за студентов медицинских университетов. В следствие этого, позицию ординатора будущим докторам предлагали еще до того, как они выбирали специализацию и начинали осваивать профессию, а если же студент отказывался от места, то оно вообще терялось, так как предлагать кому – либо еще уже было поздно. По этой причине больницы ввели крайние сроки, до наступления которых студент должен был решить, согласен ли он принять предложенное место или предпочитает отказаться от него. В следствие этого, решения принимались в спешке, что не могло не сказаться на качестве медицинского персонала. Поэтому в 1950 – х года была разработана программа NRMP (National Resident Matching Program), которой заинтересовался Элвин Рот.

Проанализировав данную программу, он показал, что в своей работе она использовала алгоритм, который был похож на предложенный ранее Гейлом – Шепли. Теория Рота так бы и осталась теорией, если бы в 1990 – х годах в функционирование программы не вмешался бы человеческий фактор. Растущее число женщин – медиков стало приводить к тому, что влюбленные пытались попасть в одну и ту же больницу, и молодые люди стали отказываться от выгодных предложений, для того, чтобы работать вместе со своей второй половинкой. Тогда руководство программы обратилось к Роту, который разработал систему врачей, опираясь на алгоритм Гейла – Шепли, которая учитывала интересы семейный пар, создавая ежегодно около двадцати тысяч стабильных распределений.

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

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

Таким образом, Ллойду Шепли Нобелевская премия в 2012 году досталась за разработанную теорию, а Элвину Роту – за применение этой теории на практике.

Заключение

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

Возвращаясь к основной теме реферата, то есть к любви, мы понимаем, что алгоритм, проанализированный автором данной работы, действительно эффективен и помогает создавать стабильные пары. Кто – то может сказать, что пары, полученные при использовании данного алгоритма можно назвать лишь стабильными, но не счастливыми, так как люди в паре могут не являться друг для друга наиболее желанными и привлекательными. Однако, важно помнить, что случай, когда женщина и мужчина в паре не являются друг для друга самыми предпочитаемыми возникает только тогда, когда наиболее желаемый вариант, увы, имеет более сильные чувства к другому объекту. В этом то и состоит вся сложность любви, ее природа и особенность, поэтому даже такой серьезной науке как математике не под силу решить эту проблему, ведь, как говорят в народе – насильно мил не будешь.

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

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

И все же первая любовь, она навеки,Как не старайся все забыть и заглушить.Увидев где-то, спать ложась, опустишь веки И вот она, красавица, мешает мирно житьУж сколь лет, казалось бы, минуло.И сколько раз влюблялся и терял.Но безнадежно так меня тянуло,Лишь к той, чьих сладких губ не целовал ...И вот итог суровых дней скитаний:Любовь тех дней давно живет с другим.И видя взгляд, наполненный воспоминаний ...Я просто должен с нею быть, иль быть один ...

С. Есенин

Список литературы:

1. Е. Железова, С. Измалков, К. Сонин, И. Хованская, Теория и практика двусторонних рынков// Вопросы экономики, №1, 2013 год.

2. Ф.Т. Алексеров, С.Г. Кисельгоф, Лауреаты Нобелевской премии – 2012: Ллойд Шепли и Элвин Рот// Экономический журнал ВШЭ, 2012 год.

3. D. Gale, L. S. Shapley, College admissions and the stability of marriage// The American Mathematical Monthly, Vol. 69, №1 (Jan., 1962), pp. 9-15

4. Финансы, Давай поженимся, 16 октября 2012 год.

[онлайн] Доступ через:

http://lenta.ru/articles/2012/10/15/nobel/

1. Л.Г. Лабскер, Н.А. Ященко, Теория игр в экономике, практикум с решениями задач, «КноРус», Москва, 2012 год.

2. Л.Г. Лабскер, Теория критериев оптимальности и экономические решения, монография, «КноРус», 2014 год.

3. Ш. Максим, Поступить в хорошую школу, удачно жениться, рационально распределить ресурсы// Наука и жизнь, 18 декабря 2012 год.

[онлайн] Доступ через:

http://www.nkj.ru/news/21251/

1. Л.Г. Лабскер, Л.О. Бабешко, Игровые методы в управлении экономикой и бизнесом, «Дело», Москва, 2001 год.

Код для цитирования: Скопировать