Аннотация:
Рассматривается задача назначения цен на ресурсы с целью максимизации суммарной полезности агентов (производителей). Функции полезности агентов предполагаются неизвестными. Определение цен происходит итеративно на основе лишь информации о реакциях агентов на предложенные цены. Рассмотрены случаи асинхронных реакций и случайных функций полезности, порожденных последовательностью независимых одинаково распределенных случайных величин. Анализ опирается на теорию выпуклой онлайн оптимизации: мы применяем алгоритм SOLO FTRL (Orabona, Pal, 2018) к двойственно задаче. Для задачи с асинхронными реакциями производителей получены оценки в среднем и с большой вероятностью для отклонения целевой функции от оптимального значения и для невязок в ограничениях. Эти оценки имеют порядок $O(T^{-1/4})$ по числу $T$ итераций и справедливы как в среднем, так и с большой вероятностью. Для задачи со случайными полезностями получены оценки такого же характера для среднего сожаления относительно лучшей последовательности цен.
Сформулируем данный результат более формально. Пусть $x^{(k)}\in \mathbb R^{d_k}$: вектор объемов товаров, производимых $k$-м агентом, $A_{ij}^{(k)}$ — количество $i$-го ресурса, которое требуется для производства $j$-го товара, $b\in\mathbb R^m_{++}$ — вектор объемов имеющихся ресурсов, $a^{(k)}\in \mathbb R^{d_k}_{++}$ — вектор максимальных объемов выпуска товаров $k$-м агентом, $f_k(x^{(k)};\xi_t)$ — случайные функции полезности агентов, $(\xi_t)_{t=1}^T$ — независимые одинаково распределенные случайные величины со значениями в компактном множестве. Функции $f_k$ предполагаются сильно вогнутыми по первому аргументу. Пусть $x_t^*$ — оптимальная кооперативная стратегия:
\[ x^*_t\in\arg\max_{x\in S} F(x;\xi_t),\quad S=\{x:Ax:=\sum_{k=1}^n A^{(k)} x^{(k)}\le b; 0\le x^{(k)} \le a^{(k)}, k=1,…,n\},\]
$ F(x;\xi_t)=\sum_{k=1}^n f_k(x^{(k)};\xi_t)$. Не приводя несложных явных формул упомянутого алгоритма SOLO FTRL для $\lambda_t$, укажем оценки сожаления и невязок в среднем:
\[ \frac{1}{T}\max\{\mathsf E\sum_{t=1}^T(F(x^*_t;\xi_t)-F(\widetilde x(\lambda_t);\xi_t)),
\sum_{t=1}^T\|\mathsf E(b-A\widetilde x(\lambda_t))\|
\}\le C T^{-1/4}.\]
Здесь $ \widetilde x^{(k)}(\lambda) =\arg\min_{0\le x^{(k)} \le a^{(k)}}(f_k(x^{(k)};\xi_t)-\langle A^{(k)} x^{(k)},\lambda\rangle) $ — реакции агентов. Последовательность цен $\lambda_t$ зависит только от этих реакций.
