Онлайн-поиск цены и портфель: сначала выбери противника сравнения

Если различаешь одноразовый выбор и повторную перебалансировку - переходи к «Теперь сам».

Как думаешь: можно ли сравнить себя со всемогущим предсказателем?

Поступают предложения 20,100,4. Приняв первое, получишь 20, а знающий будущее выберет 100. Не приняв первое, можно столкнуться с другой последовательностью 20,4, где высокий курс больше не появится. Онлайн-стратегия обязана принять решение до следующего предложения.

В повторном выборе активов всезнающий противник мог бы каждый день выбирать победителя. Это гораздо сильнее, чем выбрать один постоянный набор долей на все дни. Теорема о сравнении с постоянным портфелем не обещает догнать меняющегося каждый день победителя. Прежде чем искать коэффициент, надо определить допустимый класс офлайн-стратегий.

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

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

Механизм: выровнять два худших сценария

Для одноразовой максимизации зададим положительные границы m ≤ p_t ≤ M. Алгоритм принимает первое предложение не ниже порога r; если такого нет, принимает последнее, а о последнем шаге известно до его завершения. Если порог сработал, доход не меньше r, а оптимум не больше M, отношение не больше M/r. Если порог не сработал, все предложения меньше r, а последний доход не меньше m, отношение меньше r/m. Худшая из двух границ минимальна при равенстве M/r = r/m, откуда r² = mM.

Именно геометрическое среднее появляется из баланса двух рисков: продать рано слишком дёшево или ждать слишком долго и остаться с нижней ценой. При m = 4, M = 100 порог 20, отношение не больше пяти. Среднее арифметическое 52 не выравнивает риски: падение с цены чуть ниже 52 до 4 даст отношение почти 13. Без положительной нижней границы такое доказательство вообще не даёт конечного отношения.

В однонаправленном обмене разрешено конвертировать часть исходного запаса по каждому курсу, но обратный обмен запрещён. Можно распределять продажу по порогам. Поэтому результат для обязательной продажи всего запаса разом нельзя выдавать за оптимальный алгоритм этой более гибкой задачи.

Для портфеля пусть x_t,j - множитель цены актива j за день t, а b_j ≥ 0, Σb_j = 1 - постоянные доли. В начале каждого дня доли возвращают к b. Капитал после T дней равен произведению Π_t Σ_j b_j x_t,j. Постоянные доли не означают «один раз купить и забыть»: изменение цен сдвигает доли, поэтому требуются новые сделки. В идеализированной модели нет комиссий и ограничения делимости.

Возьмём конечную сетку из N постоянных портфелей и разделим исходный капитал поровну между ними. Каждый ведёт свой счёт. Общие доли на следующий день - среднее их долей, взвешенное накопленным капиталом. Прошлый победитель получает больший вес, но будущие множители в расчёт не входят. Суммарный капитал равен среднему капиталов экспертов; он не меньше капитала лучшего эксперта, делённого на N. Потеря в логарифме капитала не больше log N, поэтому средняя потеря на день исчезает при росте T для фиксированной сетки.

Непрерывная универсальная стратегия Ковера смешивает все постоянные доли на симплексе. Её асимптотическая гарантия сравнивает средний логарифмический рост с лучшим постоянным перебалансируемым портфелем, выбранным после наблюдения всей последовательности. Это не гарантия положительного дохода, малого риска или превосходства над произвольной меняющейся стратегией; ограничения модели входят в содержание теоремы.

Правило

Порог sqrt(mM) относится к одноразовому принятию цены в положительном ограниченном диапазоне. Гарантия универсального портфеля относится к лучшему постоянному перебалансируемому портфелю. Не меняй запас, разрешённые действия и класс сравнения между формулировкой и выводом.

Разбор: пороговая продажа

Программа перебирает все тройки предложений из маленькой сетки. Вторая часть независимо показывает, что сумма капиталов экспертов в точности совпадает с капиталом их адаптивной смеси. В расчёте используются дроби, чтобы не скрыть равенство ошибкой float.

from itertools import product
from fractions import Fraction as F


def prodazha(ceny, porog):
    for p in ceny:
        if p >= porog:
            return p
    return ceny[-1]


m, M, porog = 4, 100, 20
ceny = [4, 19, 20, 100]
plohoe = max(F(max(s), prodazha(s, porog))
             for s in product(ceny, repeat=3))
print('порог:', porog, 'худшее отношение на сетке:', plohoe)

b = [F(0), F(1, 2), F(1)]
kapitaly = [F(1, 3)] * 3
obshchij = F(1)
dni = [(F(2), F(1, 2)), (F(1, 2), F(2))] * 2
for x, y in dni:
    dolya = sum(k * v for k, v in zip(kapitaly, b)) / obshchij
    obshchij *= dolya * x + (1 - dolya) * y
    kapitaly = [k * (v * x + (1 - v) * y)
                for k, v in zip(kapitaly, b)]
    assert obshchij == sum(kapitaly)
luchshij = max(k * 3 for k in kapitaly)
print('капитал смеси:', obshchij)
print('лучший эксперт:', luchshij)
print('смесь не хуже лучшего / 3:', obshchij >= luchshij / 3)
print('постоянная половина на каждый актив:', kapitaly[1] * 3)

порог: 20 худшее отношение на сетке: 5
капитал смеси: 379/256
лучший эксперт: 625/256
смесь не хуже лучшего / 3: True
постоянная половина на каждый актив: 625/256

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

Разбор: фиксированная половина и «купил и держи»

Пусть за два дня множители первого актива 2 и 1/2, второго 1/2 и 2. Купленные в начале доли вернутся к исходной цене: оба произведения равны единице. Постоянный портфель 50/50 каждый день получает множитель 1,25, за два дня 1,5625. Разница возникает из ежедневного возврата долей к половине. Если в модели запрещены такие сделки или есть комиссия, этот расчёт уже не описывает доступную стратегию.

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

Порог для интервала с нулевой нижней границей теряет конечную конкурентную гарантию. Сравнение портфеля со всезнающим ежедневным переключателем завышает обещание теоремы Ковера. Использование текущего дневного множителя при выборе долей на тот же день подглядывает в будущее и превращает онлайн-эксперимент в офлайн. В тесте стратегии момент поступления данных должен быть явно зафиксирован.

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

Онлайн-решения о цене ресурса, принятии задания и распределении бюджета используют похожие балансы риска. Смешивание экспертов применяется и вне денежных задач: в выборе моделей, кодировщиков и алгоритмов. Для честного сравнения полезно сначала написать, какие действия доступны эксперту и когда он получает информацию. После этого граница сожаления или конкурентное отношение приобретает определённый смысл.

Теперь сам

Цены лежат в [9,144]. Какой порог выравнивает два худших сценария и каково гарантированное отношение офлайн-дохода к онлайн-доходу?