гом? Вот какой механизм разработали Гейл и Шепли. Он состоит из нескольких раундов предложений от дам королям, которые повторяются до тех пор, пока не получится распределения по устойчивым парам. В первом раунде работы этого алгоритма все дамы делают предложение королям, которых они предпочитают больше всего. Первое место в списке дамы пик занимает король червей. У дамы червей первым стоит король треф. Дама бубен выбирает короля пик, а дама треф делает предложение королю червей. Похоже, что король червей – главный сердцеед в этой компании: он получил сразу два предложения. Он выбирает из двух дам ту, которую предпочитает больше, то есть даму треф, и отказывает даме пик. Итак, у нас есть три предварительные помолвки и один отказ.
Первый раунд
Дама, получившая отказ, вычеркивает из своего списка первого кандидата и в следующем раунде делает предложение второму – королю пик. Но теперь король пик получает два предложения. В первом раунде ему сделала предложение дама бубен, а теперь – еще и дама пик. Судя по его рейтингу, он предпочитает даму пик. Поэтому он довольно жестокосердно отвергает даму бубен (с которой у него была заключена предварительная помолвка в первом раунде работы алгоритма).
Второй раунд
Это подводит нас к третьему раунду. В каждом раунде каждая отвергнутая дама делает предложение следующему королю из своего списка, а каждый король всегда выбирает лучшее из полученных предложений. В третьем раунде получившая отказ дама бубен делает предложение королю бубен (который до этого грустно стоял у стеночки, как тот мальчик, которого никто не берет к себе в команду на уроке физкультуры). Хотя дама бубен находится в нижней части его списка, у него нет лучшего варианта, так как остальные три дамы предпочли других королей, а те приняли их предложения.
Третий раунд
Наконец все участники разбиты по парам, и все браки устойчивы. Хотя мы изложили этот алгоритм в терминологии милой салонной игры с карточными дамами и королями, он применяется сейчас во всем мире: в Дании – для распределения детей по детским садам, в Венгрии – для записи учеников в школы, в Нью-Йорке – для назначения раввинов в синагоги, а в Китае, Германии и Испании – для подбора университетов для студентов. Национальная служба здравоохранения Великобритании использует его при подборе пациентов для получения донорских органов, что помогло спасти множество жизней.
Именно на основе задачи, которую решили Гейл и Шепли, построены современные алгоритмы, используемые службами знакомств. В их случае задача усложняется неполнотой информации. Предпочтения бывают непостоянными и относительными и могут меняться изо дня в день даже в рамках одних и тех же отношений. Но, по сути, эти алгоритмы стараются, исходя из предпочтений пользователей, подобрать им партнеров, с которыми они смогут образовать устойчивые и счастливые пары. Кроме того, имеющиеся данные говорят о том, что, может быть, в этой области лучше использовать алгоритмы, чем полагаться на человеческую интуицию.
Возможно, вы заметили в алгоритме, разработанном Гейлом и Шепли, любопытную асимметрию. В нашем примере дамы делали предложения королям. Изменится ли что-нибудь, если вместо этого мы предложим королям делать предложения дамам? Как это ни удивительно, изменится. В этом случае, поменяв королей и дам местами, мы получили бы в итоге другое распределение по устойчивым парам.
Дама бубен вышла бы замуж за короля червей, а дама треф – за короля бубен. То есть две дамы обменялись бы партнерами, но получили бы при этом немного менее предпочтительных супругов. Поскольку в обоих случаях пары получаются устойчивыми, когда предложения делают дамы, то дамы и получают самых лучших партнеров, на которых они могут рассчитывать. При смене ролей в более выгодном положении окажутся короли.
Американские студенты-медики, искавшие места в клинической ординатуре, узнали, что больницы использовали этот алгоритм для распределения таких мест, причем предложения исходили от больниц. Значит, студенты оказывались в менее выгодном положении. В течение некоторого времени студенты проводили агитацию, объясняя, насколько нечестной была эта система, и в конце концов алгоритм поменяли на обратный: теперь выбрать оптимальный вариант могут студенты.
Эта история – убедительное напоминание о том, что, поскольку нашей жизнью все в большей мере управляют алгоритмы, важно понимать, как они работают и что они делают, потому что иначе можно остаться с носом.
Проблема алгоритмов в том, что их работа иногда приводит к непредвиденным последствиям. Человек, возможно, и понял бы, что происходит нечто странное, но алгоритм просто продолжает делать то, на что он был запрограммирован, какими бы абсурдными ни были последствия его деятельности.
Мой любимый пример такого рода – это история о двух букинистических магазинах, которые управлялись при помощи алгоритмов. Одному молодому ученому из Калифорнийского университета в Беркли очень хотелось заполучить экземпляр книги Питера Лоуренса «Создание мухи» (The Making of a Fly). Эту классическую работу, изданную в 1992 году, часто используют специалисты по биологии развития, но к 2011 году ее тираж был давно распродан. Наш ученый хотел купить подержанный экземпляр.
На сайте Amazon он нашел несколько экземпляров, стоивших около 40 долларов, но потом был довольно сильно потрясен, обнаружив экземпляр той же книги, продававшийся за 1 730 045 долларов и 91 цент. Продававший книгу магазин под названием profnath даже не оплачивал доставку книги. Затем ученый заметил еще один экземпляр, который стоил и того дороже! Этот магазин – bordeebook – запрашивал головокружительную сумму 2 198 177 долларов и 95 центов (плюс, разумеется, 3,99 доллара за доставку).
Молодой ученый показал все это своему научному руководителю Майклу Айзену, который предположил, что это развлекаются студенты. Однако у обоих книготорговцев были очень высокие рейтинги, и оба они казались реальными магазинами. Profnath получил за предыдущие 12 месяцев более 8000 положительных отзывов, а bordeebook за тот же период – более 125 000. Возможно, дело было всего лишь в некой странной флуктуации.
На следующий день, когда Айзен проверил, не упали ли цены до более разумного уровня, оказалось, что они, напротив, выросли. Profnath хотел теперь 2 194 443,04 доллара, а bordeebook запрашивал и вовсе феноменальную цену – ровно 2 788 233 доллара. Айзен решил подойти к этому явлению с позиций ученого и проанализировать данные. В течение нескольких следующих дней он отслеживал изменения этих странных цен, пытаясь понять, есть ли в них какая-нибудь закономерность.
В конце концов он нашел математическое правило, определявшее эскалацию цен. Если разделить цену profnath на цену bordeebook за предыдущий день, всегда получается 0,99830. Если же разделить цену bordeebook на цену profnath того же дня, всегда получается 1,27059. Каждый из продавцов запрограммировал свой сайт на использование алгоритма, который устанавливал цены на продаваемые книги. Алгоритм profnath каждый день проверял цену на книгу, установленную bordeebook, и умножал ее на 0,99830. Такой порядок действий был совершенно логичен, потому что продавец программировал свой сайт на небольшое снижение цен по сравнению с конкурентом, bordeebook. Более необычен алгоритм bordeebook. Он был запрограммирован на выявление любых изменений цены у конкурентов и умножение их новой цены на 1,27059.
В результате цена на книгу каждый день увеличивалась на 0,99830 ×1,27059, то есть в 1,26843 раза. Это вызвало экспоненциальный рост цены. Если бы profnath установил более радикальное снижение цен по сравнению с bordeebook, с течением времени цена резко уменьшалась бы, а не росла.
С алгоритмом profnath, казалось, все было ясно, но почему же алгоритм bordeebook был настроен на назначение более высокой цены? Не захотят же покупатели платить за книгу больше! Возможно, в этой фирме рассчитывали, что покупателей привлекут ее более солидная репутация и большее число положительных отзывов, особенно если цена будет лишь немного выше, чем у конкурентов, – а вначале так оно и было. Как писал Айзен в своем блоге, «казалось бы, на такие вещи полагаться довольно рискованно. А тем временем книга пылится на полке. Если, конечно, не предположить, что никакой книги на самом деле нет…»
И тут его озарило. Ну конечно! На самом деле в магазине не было этой книги. Алгоритм был запрограммирован на поиск книг, имеющихся в продаже, и предложение тех же книг с небольшой наценкой. Если бы кто-нибудь захотел купить эту книгу на проверенном веб-сайте bordeebook, магазин купил бы ее у других книготорговцев и перепродал своему клиенту. Но для покрытия расходов на эту операцию требовалась некоторая наценка. Поэтому алгоритм умножал цену книги на 1,27059, что должно было покрыть расходы на покупку книги и ее доставку, а также обеспечить получение небольшой дополнительной прибыли.
Несложные операции с логарифмами позволяют установить, что книга, вероятно, поступила в продажу за сорок пять дней до 8 апреля и стоила около 40 долларов. Тут хорошо видна мощь экспоненциального роста. Всего за полтора месяца цена взлетела до миллионов долларов! 18 апреля она достигла максимума, 23 698 655 долларов и 93 центов (плюс 3,99 за доставку), после чего кто-то из людей, работавших в profnath, наконец вмешался в это дело, осознав, что происходит нечто странное. Тогда цена книги упала до 106,23 доллара. Как и следовало ожидать, алгоритм bordeebook сразу же начал предлагать книгу за 106,23 ×1,27095 = 134,97 доллара.
Ошибка в определении цены «Создания мухи» не вызвала катастрофических последствий ни для кого из участников этой истории, но бывают и более серьезные случаи, в которых алгоритмы, используемые для оценки финансовых активов, вызывают крахи рынков. Непредусмотренные последствия работы алгоритмов – одна из основных причин для экзистенциальных опасений, которые люди испытывают по отношению к развивающимся технологиям. Что, если некая компания создаст алгоритм, задачей которого будет максимально эффективная утилизация углерода, а потом он внезапно поймет, что организмы людей, работающих на заводе, состоят из углеродных материалов, и начнет утилизировать людей для нужд углеродного производства? Кто его остановит?