Цитаты из книги «Кому нужна математика?»

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

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

Математический анализ аукциона второй цены и доказательство совместимости по стимулам впервые предложил американский экономист Уильям Викри. Его статья, которая заложила основы теории аукционов, вышла в 1961 году [27]. В 1996-м за эти исследования Викри получил Нобелевскую премию по экономике.

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

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

Оказалось, что двух пользователей «Фейсбука» в среднем разделяет не шесть, а всего 4,74 рукопожатия! Статья Себастьяно Виньи и соавторов [10] быстро обрела известность в научном мире и за его пределами. О ней писали ВВС и New York Times. Результаты уже сейчас попали в популярную литературу и специальные учебники. Виртуальный мир оказался еще теснее, чем реальный — тот, в котором мы живем!

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

Теперь представьте, что мы сначала выбираем два сервера, а потом наименьшую очередь из двух. Во-первых, в этом случае на сервер 5 мы в принципе не попадаем никогда. В худшем случае мы попадем на сервер 4. Но для этого мы должны наудачу вытянуть сервер 4 и сервер 5. Два сервера из пяти можно выбрать десятью способами: 1 и 2, 1 и 3, 1 и 4, 1 и 5, 2 и 3, 2 и 4, 2 и 5, 3 и 4, 3 и 5, 4 и 5. Все эти пары равновероятны. Шансы, что из десяти возможных пар мы вытянем именно самую неудачную, 4 и 5, всего 1:10. При этом свободный сервер 2 входит в четыре из десяти пар.

Казалось бы, открытие сделано? Но, как всегда в науке, это было только начало.

отправкой обычной почты или грузов. Запрос с вашего браузера поступает на так называемый веб-сервер под именем mipt.ru, веб-сервер МФТИ. Веб-сервер — это специально выделенный компьютер, который отвечает за поиск нужного файла и его отправку в браузер пользователя. У каждого сайта, или домена — mipt.ru, rzd.ru, google.com и других, — свой веб-сервер, и часто не один.Получив ваш запрос, веб-сервер МФТИ отправляет в ваш браузер файл с содержанием главной страницы. Дальше вы начинаете ее читать, кликаете на ссылки, загружаете документы. И каждый раз веб-сервер МФТИ отправляет вам новые странички, фотографии, тексты и все остальное. Кроме вас на сайт заходят другие пользователи, с другими запросами. У веб-сервера работы хватает! И когда ее слишком много, ваши запросы должны дожидаться своей очереди.