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 товар не получает.
