В переводе М. Канна. – Прим. ред.
Жирным шрифтом выделены названия алгоритмов, которые будут описаны в книге.
В рамках этой стратегии существует 33 %-ная вероятность того, что мы откажем лучшему кандидату, и 16 %-ная вероятность – что мы никогда не встретим лучшего кандидата. Конкретно, есть шесть точных возможных последовательностей для трех кандидатов: 1–2–3, 1–3–2, 2–1–3, 2–3–1, 3–1–2, и 3–2–1. Если мы начнем отбор со второго претендента, то успех вероятен только в трех комбинациях из шести (2–1–3, 2–3–1, 3–1–2), соответственно в трех остальных случаях нас постигнет неудача – дважды из-за нашей излишней взыскательности (1–2–3, 1–3–2) и один раз по причине неразборчивости (3–2–1).
Необязательно строго 37 %. Точнее, математически оптимальная доля кандидатов, которых необходимо отсмотреть, рассчитывается по формуле 1/е (е – та же математическая константа, 2,71828…, которая появляется при расчете сложных процентов). Однако вам нет необходимости знать наизусть все 12 десятичных знаков числа е. На самом деле любое значение от 35 до 40 % максимально приближает вас к успеху.
Более подробно вычислительные риски теории игр рассматриваются в главе 11.