Все начиналось с чисто теоретической задачи, решенной нынешним профессором Университета Калифорнии в Лос-Анджелесе Ллойдом Шепли, а продолжилось созданием приложений, которые спасают жизни и делают людей более счастливыми. Шепли — один из основоположников теории игр, фундамента современной экономической теории; концепции и теоремы его имени встречаются в любом магистерском курсе экономики, а Элвин Рот из Гарварда — один из отцов современной экспериментальной экономики. Но премия — за конкретный математический результат и его применение на практике.
Теоретический алгоритм.
В 1962 году Дэвид Гейл из Университета Брауна и Ллойд Шепли, работавший в знаменитой корпорации RAND, доказали красивую абстрактную теорему, формулировка и идея доказательства которой так просты, что их можно изложить на пальцах. Есть N юношей и N девушек, и у каждого есть какие-то предпочтения относительно возможного партнера. Каждая девушка может сказать, «в каком порядке» ей нравятся юноши: этот — на первом месте, этот — на втором и так далее, до самого конца. В конце списка стоит тот, кто нравится меньше всех. И у каждого юноши есть свой рейтинг девушек. Теорема Гейла-Шепли говорит, что можно разбить юношей и девушек на пары так, чтобы получившаяся комбинация была стабильной, то есть не было бы такого юноши и девушки, которые хотели бы бросить свои пары и стать новой парой. Конечно, то, что разбивка получилась стабильной, не означает, что все абсолютно счастливы. Кому-то мог достаться партнер, стоящий далеко не на первом месте в рейтинге. И тем не менее это уже кое-что: участникам невыгодно покидать пары, созданные для них алгоритмом. Собственно, алгоритм Гейла–Шепли несложен. Можно сделать так. Сначала каждый юноша делает предложение «девушке своей мечты» — той, которая стоит в его рейтинге первой. Каждая девушка выбирает самое привлекательное из сделанных ей предложений (если, конечно, они вообще есть), но не торопится принимать его. После этого те юноши, чье предложение было отклонено в первом раунде, снова делают предложения. Может оказаться, что какая-то девушка предпочтет новое предложение тому, которое она выбрала (но не приняла!) раньше, что ж, тогда автор предложения, которое теперь отвергнуто, будет иметь возможность сделать кому-то предложение в следующем раунде. Работа алгоритма прекращается в тот момент, когда оказывается, что все разбились на пары (в том, что в итоге так и получится, состоит теорема Гейла–Шепли),— и теперь предложения окончательно принимаются.