x, y, z

Кому нужна математика?

Андрей Райгородский, Нелли Литвак

Комментарии: 0
Андрей Райгородский, Нелли Литвак. Кому нужна математика. Понятная книга о том, как устроен цифровой мир Публикуем главу из книги «Кому нужна математика. Понятная книга о том, как устроен цифровой мир» математиков Андрея Райгородского и Нелли Литвак, посвященной применению математики во всех сферах современной жизни: от чтения Торы до занятия бизнесом.

Первая страница поисковика

Что бы мы ни собирались предпринять — от ремонта квартиры до поиска работы и планирования отпуска, — последние 10–15 лет практически любое дело мы начинаем с белой странички поисковой системы. Популярность и полезность поисковиков трудно переоценить. Один Google обрабатывает более 100 миллиардов запросов в месяц!

Мы вводим запрос, и буквально в считаные секунды на экране появляется первая страница результатов поиска. Ее содержание — тема особенно интересная, потому что большинство из нас дальше первой страницы не заходят, это широко известная статистика. Наверное, кое-какие принципы заполнения первой страницы вы уже давно заметили. Например, если вы ищете что-то связанное с товарами и услугами, то на самом видном месте — вверху первой страницы — появляется реклама. Рынок онлайн-рекламы у поисковиков просто колоссальный. Реклама — это источник доходов «Яндекса» практически на сто процентов. Число рекламодателей Google уже давно превысило миллион, а доход Google от онлайн-рекламы в 2015 году оценивался в 44 с лишним миллиарда долларов.

Почему почти у всех крупных поисковиков онлайн-реклама выглядит именно так, как сегодня на нашем экране? Почему вы видите именно эти объявления и в этом порядке? За каждым объявлением скрываются глубокие математические идеи и не одна, а целых три Нобелевские премии. В этой главе мы расскажем о математике онлайн-рекламы.

Стоимость за один клик

Поисковики в их современном виде появились сравнительно недавно — в конце 1990-х годов. Реклама — гораздо раньше: газеты, щиты, телевизионные ролики. Мы расскажем о развитии и особенностях онлайн-рекламы примерно так, как это сделал Сергей Измалков — профессор Российской экономической школы, признанный эксперт в этой области.

Все мы настолько привыкли к рекламе в поисковиках, что первый тезис Сергея застает нас врасплох: «Изначально, когда поисковые системы только-только появились, выгода такой рекламы для рекламодателей была совершенно неочевидна!»

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

Так возникла идея рекламы по ключевой фразе. Вместо «журнала» рекламодатель выбирает в поисковом запросе интересующие его слова. Скажем, если компания устанавливает пластиковые окна, то они могут выбрать запросы пластиковые окна, окна, ремонт квартиры и тому подобные. А на другие запросы, например пластиковые тарелки, их реклама не появится. Поисковик точно знает, что интересует пользователя в данный момент. На запрос жираф можно предложить туры в Африку, а на запрос рецепт пиццы — мастер-класс по ее приготовлению (а не рекламу пиццерий!).

Такой «контекстной» рекламой пользуются все поисковые системы и все крупные сайты, включая «Фейсбук» и «Ютуб». Это был первый шаг к успеху онлайн-рекламы.

Второй вопрос: за что, собственно, поисковая система будет брать деньги? Например, газеты берут за показ. Но у газеты известно число подписчиков, и объявление можно увидеть своими глазами. Поисковая система — совсем другое дело. Рекламодатели не готовы платить за показы, количество которых будет неизвестно и которые никак нельзя ни увидеть, ни проверить.

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

Так возникла еще одна ключевая идея онлайн-рекламы: стоимость за 1 клик. Когда вы видите рекламу, «Яндекс» ничего на этом не зарабатывает. Счетчик поворачивается, только если вы кликнете на рекламный линк.

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

Аукцион — специально для вас!

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

Современные поисковые системы назначают цены за клик через аукцион. Все рекламодатели заранее предлагают свою цену за клик по той или иной ключевой фразе, и в момент поискового запроса рекламные места уходят тем, кто предложил больше. Настоящая рыночная цена! Для полноты информации сообщим, что цена за клик, например в Google, обычно 1–2 доллара, но доходит и до 50 долларов и выше, особенно в финансовом секторе.

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

Каждый раз, когда вы вводите запрос типа пластиковые окна, поисковая система проводит по нему аукцион и представляет вам победителей! Это делают все поисковые системы. И поскольку один только Google обрабатывает примерно 40 тысяч запросов в секунду, то миллион аукционов в минуту — далеко не преувеличение.

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

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

Этими вопросами занимается очень интересная область современной математики под названием «Дизайн механизмов». В 2007 году ее основатели Леонид Гурвич, Эрик Маскин и Роджер Майерсон получили Нобелевскую премию по экономике. «Механизм» в данном случае — не машина, а механизм управления. Теория дизайна механизмов изучает, как создать оптимальные правила игры в условиях конкуренции: аукционы, голосование, распределение ресурсов. Онлайн-реклама — всего лишь одно из многочисленных приложений.

Аукцион второй цены

При слове «аукцион» мы обычно представляем комнату, полную хорошо одетых людей, и человека с молотком на трибуне. Участники поднимают ставки. Раз, два, три — продано! Это открытый аукцион, все слышат ставки друг друга.

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

Представьте себе наиболее простую ситуацию, так называемый аукцион первой цены. Конверты вскрыты, и товар уходит по самой высокой ставке тому, кто ее предложил. Допустим, Анна и Борис участвуют в таком аукционе. Анна готова заплатить за товар 500, а Борис 300. Оба честно написали ставки 500 и 300. Товар ушел к Анне за 500. Все справедливо, но все ли довольны? На самом деле нет. Если бы Анна написала 400 или даже 301, то получила бы товар гораздо дешевле! Получается, что правдивую ставку делать невыгодно. Самое лучшее для Анны — это разузнать или угадать ставку Бориса и поставить чуть-чуть больше.

Теперь представим, что правила изменились. Товар получает тот, кто сделал самую большую ставку, но по цене второй по величине ставки. Это называется аукционом второй цены. Анна и Борис честно пишут 500 и 300. Анна получает товар за 300.

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

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

Создать правила, при которых выгодно делать правдивые ставки, — один из основных принципов теории дизайна механизмов, он называется совместимость по стимулам. Аукцион второй цены — классический пример этого принципа. Математический анализ аукциона второй цены и доказательство совместимости по стимулам впервые предложил американский экономист Уильям Викри. Его статья, которая заложила основы теории аукционов, вышла в 1961 году[1].

В 1996-м за эти исследования Викри получил Нобелевскую премию по экономике.

Именно аукционами второй цены, в разных вариантах, пользуются все поисковые системы. По словам Сергея Измалкова, это была «четвертая революция» в онлайн-рекламе[2]. Ниже на рис. 8.1 перечислены все четыре ключевые идеи, приведшие к современной онлайн-рекламе, какой мы ее видим каждый день.

Рис. 8.1. Четыре ключевые идеи современной рекламы в поисковых системах
Рис. 8.1. Четыре ключевые идеи современной рекламы в поисковых системах

Результат Викри

Главный вклад Викри — это формальный анализ аукционов и доказательство того, что различные форматы аукционов приносят одинаковый доход продавцу. Один из удивительных результатов этого анализа заключается в том, что аукцион второй цены удовлетворяет совместимости по стимулам, то есть каждому участнику выгодно делать правдивые ставки. Понять это совсем не сложно, почти элементарно.

Вернемся к примеру, в котором Анна, Борис и еще несколько человек участвуют в аукционе второй цены. Каждый пишет свою ставку и кладет в конверт. Допустим, для Анны ценность товара 500, и ставок других участников она не знает.

Что произойдет, если Анна поставит 600? На рис. 8.2 мы представили три возможных сценария. Ставки участников обозначены жирными точками. В рамке вторая по величине ставка, это окончательная стоимость товара в аукционе второй цены. Если все остальные участники поставили меньше 500, как на рис. 8.2 вверху, то ничего не изменилось, Анна по-прежнему получает товар за вторую цену (в данном примере 300). Повышать ставку смысла не было. Если кто-то поставил больше 600, как на рис. 8.2 в середине, Анна не получает товар в любом случае. Победитель платит больше, но для самой Анны ничего не меняется. Опять же повышать ставку смысла не было (разве что из вредности, но модель этого не учитывает). Теперь представьте, что кто-то поставил 550, как на рис. 8.2 внизу. Тогда Анна получает товар за 550, а это для нее слишком дорого. В контексте онлайн-рекламы она может даже потерять на рекламе, вместо того чтобы заработать. Вывод: ставить выше 500 невыгодно.

Рис. 8.2. Три сценария, в которых Анна вместо правдивой ставки (500) делает более высокую ставку (600)
Рис. 8.2. Три сценария, в которых Анна вместо правдивой ставки (500) делает более высокую ставку (600)

Но, может, выгодно сделать более низкую ставку? Оказывается, нет! Допустим, Анна решила попробовать поставить поменьше, скажем 400. На рис. 8.3 изображены те же три сценария. Если все остальные участники поставили меньше 400, как на рис. 8.3 вверху, то ничего не изменилось, Анна по-прежнему получает товар за вторую цену (в данном случае снова 300). Если кто-то поставил больше 500, как на рис. 8.3 в середине, то Анна не получит товар в любом случае. Но если кто-то поставил 450, как на рис. 8.3 внизу, то Анна товар опять же не получает, хотя цена ее устраивала и она была готова платить больше, чем победитель. Возможность хорошей онлайн-рекламы упущена. Ставить ниже 500 тоже невыгодно!

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

Рис. 8.3. Три сценария, в которых Анна вместо правдивой ставки (500) делает более низкую ставку (400)
Рис. 8.3. Три сценария, в которых Анна вместо правдивой ставки (500) делает более низкую ставку (400)

Это очень простой и глубокий математический результат, в котором сходятся сразу две фундаментальные концепции. Одну из них мы уже обсудили, это совместимость по стимулам, при которой честные ставки самые выгодные. Вторая — это так называемое равновесие по Нэшу. Речь идет о том самом Джоне Нэше из фильма «Игры разума».

Равновесие по Нэшу представляет собой ситуацию, когда ни одному из участников не выгодно в одиночку отклоняться от выбранной стратегии. Данная концепция лежит в основе теории игр, за разработку которой Джон Нэш получил Нобелевскую премию по экономике 1994 года. «Игрой» можно назвать любую ситуацию, когда исход зависит от действий всех участников и у каждого из них свои интересы. Очевидно, что аукцион — это тоже игра. Участники выбирают ставки с целью получить товар по самой выгодной цене[3].

Как распределить несколько рекламных мест

Аукцион Викри сильно упрощает реальность. Поисковые системы разыгрывают не одно, а несколько рекламных мест разной ценности. Хорошо известно, что количество кликов очень сильно зависит от позиции рекламы на странице. Например, по статистике Google, на мобильном телефоне почти 28% пользователей кликает на самую верхнюю рекламу, а на вторую сверху — чуть больше 9%. Чем выше вероятность кликов, тем дороже место.

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

Теория Викри распространяется на случай, когда разыгрываются сразу несколько товаров. Это хорошо изученная модель аукциона, так называемый механизм Викри — Кларка — Гровса, который часто называют VCG, по первым буквам имен его создателей. Схема вычисления цен и математические свойства VCG довольно сложны и выходят за рамки нашей книги. Мы назовем только две основные особенности.

Во-первых, в аукционе VCG сохраняется свойство совместимости по стимулам: выгоднее всего делать честные ставки. Во-вторых, главная идея этого механизма та же, что и у аукциона второй цены. Возьмем снова наш простой пример. У нас один товар, Анна ставит 500, Борис 300, а остальные — еще меньше. В аукционе второй цены Анна получает товар, но платит 300, то есть максимальную ставку других участников. Примерно то же самое происходит в VCG при розыгрыше нескольких товаров. Товары уходят к тем, кто сделал на них максимальные ставки, а цены определяются не ставкой победителя, а ставками других участников.

Поисковые системы также используют обобщенный аукцион второй цены, изобретение Google. Система проста: каждый платит не свою цену, а следующую по величине. Например, рекламодатели А, Б, В и Г поставили за клик 10, 7, 3 и 1, как в табл. 8.1. Разыгрываются три места. Тогда А получает первое место за 7, Б получает второе место по цене 3, В — третье место по цене 1, а Г рекламного места не получает.

Таблица 8.1. Четыре рекламодателя и их ставки и цены за клик в обобщенном аукционе второй цены

Google пришел к этой системе исходя из идеи второй цены и многочисленных экспериментов. Исчерпывающего математического анализа такого аукциона пока нет, но кое-какие основные результаты известны. Например, делать честные ставки выгодно не всегда, просто потому что более низкие рекламные позиции могут оказаться гораздо выгоднее. Это одна из причин, по которой «Яндекс» с августа 2015 года перешел на аукционы типа VCG, где честные ставки ведут к оптимальной позиции по оптимальной цене для всех участников.

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

Обобщенный аукцион второй цены, в котором невыгодно делать честную ставку

Рассмотрим снова пример в табл. 8.1. Каждый клик для А представляет ценность 10. Допустим, вероятности клика на первой и второй позиции примерно как на десктопе: около 20 % на первой позиции и около 11 % — на второй. В этом случае ценность первой позиции для А в среднем 20 % от 10, то есть 2, а ценность второй позиции в среднем 11 % от 10, то есть 1,1.

При правдивой ставке А получает первую позицию по цене 7. Вспомним, что А платит только в случае клика. Это в среднем 20 % случаев. Значит, средняя прибыль А равна [20 % от 10] − [20 % от 7] = 2 − 1,4 = 0,6. Но если бы А поставил 6, то он получил бы вторую позицию по цене 3, то есть прибыль была бы равна [11 % от 10] − [11 % от 3] = 1,1 − 0,33 = 0,77. Это больше, чем 0,6. Получается, что для А выгоднее сделать заниженную ставку 6, а не правдивую ставку 10.

Подготовленному читателю мы рекомендуем книгу Иона Клейнберга и Дэвида Исли[4]. В частности, в главе 15 этой книги подробно анализируются свойства обобщенного аукциона второй цены. Книга написана для широкой технической публики и есть в интернете в открытом доступе.

На самом деле картина в бизнесе поисковиков еще сложнее. При оплате за клик нет смысла отдавать козырные рекламные места под плохие объявления даже по самым высоким ценам. Качественная реклама приносит больше кликов. Допустим, рекламодатель А заплатит 7, а Б всего 3, но объявление Б генерирует в 4 раза больше кликов. Объявление А получит один клик и принесет 7, а Б на том же самом месте получит 4 клика и принесет 12. Поэтому при розыгрыше рекламных мест ставка Б считается выше, чем ставка А.

Самым простым вариантом такого аукциона пользовался Yahoo! в начале 2000-х годов. Качество сайта они оценивали как вероятность клика. Тогда ставка рекламодателя определялась как средний доход, который он предлагает:

[ставка в аукционе Yahoo] = [денежная ставка рекламодателя] × [вероятность клика].

Как именно определяется качество в современных системах и как оно влияет на подсчет ставок — строгая коммерческая тайна. Это зависит от качества сайта, отзывов покупателей, интересов данного пользователя и многого другого.

В итоге качество для поисковой системы — это потенциальное число кликов, которое принесет объявление. Но крайне важен и тот факт, что пользователям нравится видеть качественные объявления. Это поддерживает репутацию поисковика. А при нынешней конкуренции она бесценна!

По ту и другую сторону онлайн-рекламы

По словам Сергея Измалкова, аукционы второй цены в реальной жизни встречаются редко. Очень трудно не дрогнуть и отдать товар за 300, когда знаешь, что можно было взять 500! Серьезная логическая ошибка заключается в том, что взять 500 не получилось бы в любом случае. Если человек знает, что с него возьмут по максимуму, он просто не назовет свою правдивую цену. Люди приспосабливаются к правилам. На этом фундаментальном наблюдении основана вся теория дизайна механизмов.

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

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

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

У рекламодателей вопросов не меньше. Средний интернет-магазин предлагает около десяти тысяч товаров. На какие ключевые фразы ставить и сколько? Как предсказать реальные доходы от кликов? Как оценить качество собственного объявления и объявления конкурента? В последнее время в мире появились тысячи маркетинговых компаний, специализирующихся на онлайн-рекламе.

Большая часть онлайн-маркетинга пока основывается на опыте и здравом смысле. Например, если у вас маленький магазин спортивной обуви, бесполезно ставить на слово «Найк», лучше поставить на «синие женские кроссовки “Найк”». Но некоторые компании уже разрабатывают и используют компьютерные программы для автоматического подсчета оптимальных ставок — например, исходя из предыдущих ставок и продаж. При растущем размахе электронной торговли у нас есть все основания полагать, что будущее — именно за автоматическими методами и математическими моделями. По ту и другую сторону онлайн-рекламы работы для математиков — непочатый край.



1. Vickrey William. Counterspeculation, auctions, and competitive sealed tenders // The Journal of finance, 16(l):8–37, 1961.

2. Помимо поисковых систем аукционами второй цены пользуется корпорация электронной торговли eBay.

3. Для читателей с математической подготовкой, которых заинтересовала теория аукционов и три Нобелевские премии, рекомендуем видеолекцию Алексея Савватеева, где он подробно и очень доходчиво объясняет математическую сторону вопроса.

4. Easley David and Kleinberg Jon. Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge University Press, 2010.

Авторы:

Андрей Райгородский, доктор физико-математических наук, профессор кафедры математической статистики и случайных процессов механико-математического факультета МГУ, профессор и научный руководитель бакалавриата кафедры «Анализ данных» факультета инноваций и высоких технологий МФТИ, руководитель отдела теоретических и прикладных исследований компании «Яндекс», преподаватель Школы анализа данных Яндекса.

Нелли Литвак, Associate Professor at Faculty of Electrical Engineering, Mathematics and Computer Sciences, University of Twente, The Netherlands
Комментарии: 0