Аренда лыж: решать, не зная будущего

Если ты определишь конкурентное отношение, докажешь, что «арендовать B − 1 день и купить» даёт 2 − 1/B, объяснишь, почему без случайности лучше нельзя, и знаешь, что даёт случайный день покупки, листай до «Теперь сам».

Как думаешь, когда покупать

Сервис в облаке: можно платить за машину почасово (условно 1 в день), можно купить резервирование на год за 10. Если проект проживёт неделю - аренда дешевле, если год - покупка. Сколько он проживёт, не знает никто, решать надо сегодня и каждый следующий день.

Ответь себе до чтения: какое правило лучше всего на худший случай? Купить сразу - если проект закроют завтра, переплата в десять раз. Не покупать никогда - если проект проживёт десять лет, переплата во сколько угодно раз. Где-то посередине есть день, когда покупка «окупает» аренду, и правило, связанное с этим днём, гарантирует переплату меньше чем вдвое при любом будущем.

На что это похоже

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

Знающий будущее - это и есть оптимум, с которым сравнивают онлайн-алгоритм. Он не реальный конкурент, а мерка: «насколько дорого обходится незнание».

Механизм: конкурентное отношение и противник

Определение. Онлайн-алгоритм ALG c-конкурентен, если для любой последовательности запросов σ его затраты ALG(σ) ≤ c · OPT(σ), где OPT(σ) - наименьшие затраты при знании всей σ заранее. Наименьшее такое c - конкурентное отношение. Это та же гарантия худшего случая, что у приближённых алгоритмов, только источник потерь - не трудность задачи, а незнание будущего.

Правило «купить в день k»: арендовать дни 1 … k − 1, в день k купить. Если сезон кончился на дне t:

t < k:    затраты t,               оптимум min(t, B) = t   при t < B
t >= k:   затраты (k − 1) + B,     оптимум min(t, B)
k = B:    t < B  →  отношение 1;   t >= B  →  (2B − 1) / B = 2 − 1/B

Нижняя граница для любого детерминированного правила. Противник знает правило и заканчивает сезон на дне k - сразу после покупки. Затраты k − 1 + B, оптимум min(k, B). При k ≤ B отношение (k − 1 + B)/k ≥ (2B − 1)/B, при k > B - (k − 1 + B)/B ≥ 2. Лучше 2 − 1/B не выбрать.

Случайность. Противник, знающий правило, но не знающий подброшенных монеток, не может подгадать конец сезона под день покупки. Если покупать в день i с вероятностью, пропорциональной (1 − 1/B)^(B − i), ожидаемое отношение становится 1/(1 − (1 − 1/B)ᴮ), и при больших B - e/(e − 1). Лучше не может никакой случайный алгоритм (Карлин и др., 1990).

Правило

Онлайн-алгоритм c-конкурентен, если на любом входе его затраты не больше c затрат оптимума, знающего вход заранее. Аренда лыж: «арендовать B − 1 день, затем купить» - 2 − 1/B, и это лучшее детерминированное правило; со случайным днём покупки - 1/(1 − (1 − 1/B)ᴮ) → e/(e − 1) ≈ 1,58.

Разбор: какой день покупки лучше

zatraty - сколько заплатит правило «купить в день k», если сезон длится dnej. hudshee перебирает длительность сезона и находит худшее отношение к оптимуму и день, на котором оно достигается. B = 10.

def zatraty(kupit_v_den, dnej, B):
    # прокат по 1 в день; в день kupit_v_den покупаем за B
    if dnej < kupit_v_den:
        return dnej
    return (kupit_v_den - 1) + B

def hudshee(kupit_v_den, B):
    h = 0
    t_hud = 0
    for dnej in range(1, 4 * B):
        r = zatraty(kupit_v_den, dnej, B) / min(dnej, B)
        if r > h:
            h = r
            t_hud = dnej
    return [round(h, 3), t_hud]

B = 10
for k in [1, 5, 8, 10, 12, 20, 40]:
    print(k, hudshee(k, B))
print(2 - 1 / B)

1 [10.0, 1]
5 [2.8, 5]
8 [2.125, 8]
10 [1.9, 10]
12 [2.1, 12]
20 [2.9, 20]
40 [3.9, 39]
1.9

Купить сразу: худшее отношение 10 - сезон длиной в один день. Купить на пятый день: 2,8, худший сезон - ровно пять дней. На десятый: 1,9 = 2 − 1/10, лучший вариант. Позже - снова хуже: на двадцатый день худший случай - сезон в двадцать дней, когда 19 дней аренды плюс покупка против покупки в первый день. У «купить на сороковой» худший случай упирается в горизонт перебора: чем дольше сезон, тем хуже.

Второй столбец подтверждает довод о противнике: худший сезон кончается в день покупки (у «купить на сороковой» перебор просто не дошёл до этого дня). Противнику не нужно знать будущее - ему нужно знать правило.

Разбор: монетка против противника

Тот же B = 10, но день покупки случаен: вероятность дня i пропорциональна 0,9^(10 − i). Для каждой длины сезона считается ожидаемая затрата, и берётся худшее отношение.

import math

def zatraty(kupit_v_den, dnej, B):
    if dnej < kupit_v_den:
        return dnej
    return (kupit_v_den - 1) + B

B = 10
q = 1 - 1 / B
c = 1 / (B * (1 - q ** B))
veroyatnost = []
for i in range(1, B + 1):
    veroyatnost.append(c * q ** (B - i))
pokaz = []
for p in veroyatnost:
    pokaz.append(round(p, 3))
print(pokaz)
hud = 0
for dnej in range(1, 3 * B):
    ozhidanie = 0
    for i in range(1, B + 1):
        ozhidanie = ozhidanie + veroyatnost[i - 1] * zatraty(i, dnej, B)
    hud = max(hud, ozhidanie / min(dnej, B))
print(round(hud, 4), round(1 / (1 - q ** B), 4))
print(round(math.e / (math.e - 1), 4))

[0.059, 0.066, 0.073, 0.082, 0.091, 0.101, 0.112, 0.124, 0.138, 0.154]
1.5353 1.5353
1.582

Вероятности растут от 6% в первый день до 15% в десятый: покупать рано можно, но реже. Худшее ожидаемое отношение 1,5353 - совпадает с формулой 1/(1 − 0,9¹⁰) и меньше детерминированных 1,9. При B → ∞ оно растёт к e/(e − 1) ≈ 1,582.

Почему противник проигрывает случайности: чтобы навредить, ему надо закончить сезон сразу после покупки, а день покупки он не знает. Против любой длины сезона случайное правило в среднем одинаково проигрывает оптимуму - вероятности подобраны так, что противнику всё равно, когда останавливаться.

Что ломается без этого

Решают по прогнозу без страховки. «Проект точно проживёт год» - купили сразу, проект закрыли на следующий день: переплата в B раз. Правило с конкурентным отношением страхует от худшего будущего.

Ждут слишком долго. «Купить, когда аренда в три раза превысит цену» - отношение около 4 вместо 2.

Сравнивают онлайн-алгоритм с другим онлайн-алгоритмом. Мерка - оптимум, знающий будущее; иначе непонятно, сколько стоит само незнание.

Раскрывают правило противнику. Детерминированное правило противник обыгрывает по построению. Случайное - только в среднем, и это и есть выигрыш от монетки.

Зачем это в работе

Аренда лыж - модель для десятка инженерных решений: резервировать мощность или платить по факту; когда усыплять простаивающий сервер (просыпаться дорого); когда переходить с медленного алгоритма на построение индекса; держать соединение или закрыть. Везде правило одно: продолжать дешёвое, пока накопленная плата не сравняется с ценой дорогого, - и переплата никогда не превысит двукратной. Раздача задач по серверам из первой главы - тоже онлайн-алгоритм: она решает при приходе каждой задачи, и её 2 − 1/m - конкурентное отношение.

Теперь сам

1. B = 50. Каково конкурентное отношение правила «арендовать 49 дней, потом купить»?
2. Правило «купить на третий день» при B = 10. Какой сезон для него худший и каково отношение?
3. Почему противнику, играющему против случайного правила, бесполезно знать распределение вероятностей?