Книга Кому нужна математика? Понятная книга о том, как устроен цифровой мир - Андрей Райгородский

2l = m + 1 или l = log2(m + 1) ≈ log2(m).

В памяти нам нужно держать только l битов информации (последовательность из нулей и единиц длины l). Из предыдущих формул получается:

l ≈ log2 (m) ≈ log2 log2 (n).

Для повышения точности хеш-значения разбивают на r регистров и запоминают максимальное число нулей в каждом регистре отдельно. В результате требуется порядка r log2 (log2 (n)) битов памяти. Относительная точность оценки задается формулой 1,04÷ √r{36}.

Назад к Главе 7

Приложение к главе 8

Доказательство совместимости по стимулам аукциона второй цены

Рассмотрим аукцион второй цены, на котором один товар разыгрывается между n участниками. Обозначим vi истинную ценность товара для участника i (от английского слова value – ценность). Далее обозначим через bi ставку участника i (от англ. bid – ставка). Эти обозначения будем использовать для любого i = 1,2, …, n.

Совместимость по стимулам означает, что верна следующая теорема.

Теорема (Викри). Участник i получает максимальную прибыль, если bi = vi.

Доказательство. Если участник i получает товар, следовательно, его ставка bi была самой высокой. Поскольку мы имеем дело с аукционом второй цены, то стоимость товара равна самой высокой из оставшихся ставок:

При этом ценность товара для участника i равна vi. Значит, если участник i получает товар, то его прибыль составит

Если участник i товар не получает, он не приобретает никакой ценности и ничего не платит, то есть его прибыль равна нулю.

Дальше доказательство ведется так же, как в разделе «Результат Викри» в главе 8, и в качестве иллюстрации мы можем по-прежнему использовать рис. 8.2 и рис. 8.3. Допустим, что ставки всех участников, кроме i, фиксированы. Мы покажем, что при правдивой ставке bi = vi прибыль участника i та же или больше, чем при повышенной ставке bi > vi или пониженной bi < vi. Подчеркнем, что это утверждение верно при любых (фиксированных) ставках других участников.

Предположим, что bi > vi. Рассмотрим три случая относительно ставок bj, j≠i.

1. Допустим, что bi – самая высокая ставка и, кроме того, все остальные участники поставили меньше, чем vi (рис. 8.2 вверху). Тогда товар по-прежнему достается участнику i по стоимости maxj≠ibj, и участник i получает точно такую же прибыль (П.16), что и при правдивой ставке vi.

2. Теперь предположим, что другой участник k сделал ставку bk > bi (см. рис. 8.2 в середине). Тогда участник i товар не получает, его прибыль равна нулю. Но поскольку bi > vi, то и при честной ставке vi участник i тоже не получил бы товар. Значит, в этом случае прибыль участника i при честной ставке тоже равна нулю.

3. Наконец, допустим, что bi – самая высокая ставка и vi < maxj≠ibj < bi (см. рис. 8.2 внизу). Так как vi < bi, такая ситуация возможна. Она возникает, когда самая высокая ставка других участников выше vi, но ниже bi. Если бы i поставил vi, то i не получил бы товар, прибыль была бы равна нулю. Но теперь bi – самая высокая ставка, поэтому товар достается i. Прибыль i по-прежнему вычисляется по формуле (П.16), но только прибыль становится отрицательной, поскольку ценность товара меньше его стоимости. Значит, в этом случае прибыль i меньше, чем при честной ставке.

Во всех трех случаях 1–3 участник i не получил прибыль выше, чем при честной ставке vi.

Теперь предположим, что bi < vi, то есть ставка занижает реальную ценность. Опять рассмотрим три случая относительно ставок других участников bj, j≠i.

1ʹ. Допустим, bi – самая высокая ставка (рис. 8.3 вверху). Тогда товар по-прежнему достается участнику i по стоимости maxj≠ibj. В этом случае прибыль участника i та же, что и прежде (П.16). Она в точности такая же, как и при честной ставке vi.

2ʹ. Теперь предположим, что другой участник l сделал ставку bl > vi (рис. 8.3 в середине). В этом случае при честной ставке vi участник i товар не получает.