Ценообразование процессорного времени
Ключевые слова и синонимы
Конкурентный аукцион (Competitive auction); рыночное равновесие (Market equilibrium); планирование ресурсов (Resource scheduling)
Постановка задачи
В данной задаче рассматривается модель вальрасовского равновесия[1] для определения цен на процессорное время. В рыночной модели задачи о планировании заданий процессора владелец процессорного времени продает клиентам временные интервалы, и цена каждого временного интервала зависит от стратегии продавца и предложений клиентов (оценочных функций). В случае вальрасовского равновесия рынок чист, и каждый клиент максимально удовлетворен в соответствии со своей оценочной функцией и текущими ценами. В работе Дэна, Хуан и Ли [1] были установлены условия существования вальрасовского равновесия и получены результаты сложности для определения существования равновесия. В ней также обсуждаются вопросы избыточного предложения процессорного времени и динамики цен.
Нотация
Рассмотрим комбинаторный аукцион [math]\displaystyle{ (\Omega, I, V) }[/math].
• Товары: продавец продает [math]\displaystyle{ m }[/math] видов неделимых товаров. Обозначим за [math]\displaystyle{ \Omega = \{ \omega_1 \times \delta_1, ..., \omega_m \times \delta_m \} }[/math] множество товаров, где [math]\displaystyle{ \delta_j }[/math] – доступное количество позиции [math]\displaystyle{ \omega_i }[/math].
• Агенты: на рынке имеется [math]\displaystyle{ n }[/math] агентов, выступающих в роли покупателей, обозначаемых [math]\displaystyle{ I = \{ 1, 2, n \} }[/math].
• Оценочные функции: каждый покупатель [math]\displaystyle{ i \in I }[/math] имеет оценочную функцию [math]\displaystyle{ v_i: 2^{\Omega} \to \mathbb{R}^+ }[/math] для представления максимальной суммы денег, которую он готов заплатить за определенную совокупность товаров. Пусть [math]\displaystyle{ V = \{v_1, v_2, ..., v_n \} }[/math].
XOR-комбинация двух оценочных функций [math]\displaystyle{ v_1 }[/math] и [math]\displaystyle{ v_2 }[/math] определяется следующим образом:
[math]\displaystyle{ (v_1 \; XOR \; v_2)(S) = max \{ v_1(S), v_2(S)\} }[/math].
Атомарной заявкой называется оценочная функция [math]\displaystyle{ v }[/math], обозначаемая парой [math]\displaystyle{ (S, q) }[/math], где [math]\displaystyle{ S \subset \Omega }[/math] и [math]\displaystyle{ q \in \mathbb{R}^+ }[/math]:
[math]\displaystyle{ v(T) = q }[/math], если [math]\displaystyle{ S \subset T }[/math], и [math]\displaystyle{ v(T) = 0 }[/math] в противном случае.
Любая оценочная функция [math]\displaystyle{ v_i }[/math] может быть выражена XOR-комбинацией атомарных заявок:
[math]\displaystyle{ v_i = (S_{i1}, q_{i1}) \; XOR \; (S_{i2}, q_{i2}) ... \; XOR \; (S_{in}, q_{in}) }[/math].
Если имеются входные данные в виде [math]\displaystyle{ (\Omega, I, V) }[/math], продавец определяет распределение и вектор цен в качестве выходных данных:
• Распределение [math]\displaystyle{ X = \{ X_0, X_1, X_2, ..., X_n \} }[/math] представляет собой разбиение [math]\displaystyle{ \Omega }[/math], в котором [math]\displaystyle{ X_i }[/math] – совокупность товаров, выделенная покупателю [math]\displaystyle{ i }[/math], а [math]\displaystyle{ X_0 }[/math] – множество нераспределенных товаров.
• Вектор цен [math]\displaystyle{ p }[/math] – это неотрицательный вектор в пространстве [math]\displaystyle{ \mathbb{R}^m }[/math], j-м элементом которого является цена товара [math]\displaystyle{ \omega_j \in \Omega }[/math].
Для любого подмножества [math]\displaystyle{ T = \{ \omega_1 \times \delta_1, ..., \omega_m \times \delta_m \} \subset \Omega }[/math] определим [math]\displaystyle{ p(T) = \sum_{j = 1}^m \sigma_j p_j }[/math]. Если покупателю [math]\displaystyle{ i }[/math] выделена совокупность [math]\displaystyle{ X_i }[/math], его полезность равна [math]\displaystyle{ u_i(X_i, p) = v_i(X_i) - p(X_i) }[/math].
Определение. Вальрасовское равновесие для комбинаторного аукциона [math]\displaystyle{ (\Omega, I, V) }[/math] представляет собой кортеж [math]\displaystyle{ (X, p) }[/math], где [math]\displaystyle{ X = \{ X_0, X_1, ..., X_n \} }[/math] – распределение, а [math]\displaystyle{ p }[/math] – вектор цен, удовлетворяющий условиям:
(1) [math]\displaystyle{ \; p(X_0) = 0 }[/math];
(2) [math]\displaystyle{ \; u_i(X_i, p) \ge u_i (B, p), \; \forall B \subset \Omega, \; \forall 1 \le i \le n }[/math].
Такой вектор цен также называется рыночной клиринговой ценой, вальрасовской ценой или равновесной ценой.
Задача о планировании заданий процессора
В ориентированной на рынок модели распределения ресурсов процессора есть два типа игроков: поставщик ресурса и n потребителей. Поставщик продает потребителям временные интервалы процессора, каждый потребитель имеет задания, требующие фиксированного объема времени процессора, и его оценочная функция зависит от временных интервалов, выделенных для задания, обычно от последнего выделенного временного интервала. Предположим, что все задания выпускаются в момент времени t = 0, и каждое задание требует si единиц времени. Задания можно прерывать без затрат на вытеснение, как это часто моделируется для заданий процессора.
Переводя ситуацию на язык комбинаторных аукционов, на рынке имеется [math]\displaystyle{ m }[/math] товаров (единиц времени), [math]\displaystyle{ \Omega = \{ \omega_1, ..., \omega_m \} }[/math], и [math]\displaystyle{ n }[/math] покупателей (заданий), [math]\displaystyle{ I = \{ 1, 2, ..., n \} }[/math]. Каждый покупатель имеет оценочную функцию [math]\displaystyle{ v_i }[/math], зависящую только от времени завершения. Более того, если это не указано явно, оценочная функция каждого задания является невозрастающей относительно времени завершения.
Основные результаты
Рассмотрим следующую задачу линейного программирования:
[math]\displaystyle{ max \sum_{i = 1}^n \sum_{j = 1}^{k_i} q_{ij} x_{ij} }[/math]
такую, что [math]\displaystyle{ \sum_{i, j | \omega_k \in S_{ij}} x_{ij} \le \delta_k, \; \forall \omega_k \in \Omega }[/math]
[math]\displaystyle{ \sum_{j = 1}^{r_j} x_{ij} \le 1, \; \forall 1 \le i \le n }[/math]
[math]\displaystyle{ 0 \le x_{ij} \le 1, \; \forall i, j }[/math].
Обозначим задачу как LPR (релаксацию линейного программирования), а ее целочисленное ограничение – как IP (целочисленное программирование). Следующая теорема показывает, что из ненулевого разрыва между задачей целочисленного программирования IP и ее линейной релаксацией следует несуществование вальрасовского равновесия.
Теорема 1. В комбинаторном аукционе вальрасовское равновесие существует тогда и только тогда, когда оптимум IP равен оптимуму LPR. Размер задачи LP линейно зависит от общего числа XOR-заявок.
Теорема 2. Задача определения существования вальрасовского равновесия в задаче планирования заданий на процессоре является NP-трудной в сильном смысле.
Теперь рассмотрим задачу планирования заданий, в которой все оценочные функции клиентов линейны. Предположим, что в момент времени t = 0 на одной машине запускается [math]\displaystyle{ n }[/math] заданий, время выполнения j-го задания составляет [math]\displaystyle{ s_j \in \mathbb{N}^+ }[/math], а вес [math]\displaystyle{ w_j \ge 0 }[/math]. Целью планирования является минимизация взвешенного времени завершения: [math]\displaystyle{ \sum_{i = 1}^n w_i t_i }[/math], где [math]\displaystyle{ t_i }[/math] – время завершения задания [math]\displaystyle{ i }[/math]. Такая задача называется задачей MWCT (минимальное взвешенное время завершения).
Теорема 3. В одномашинной задаче планирования заданий MWCT вальрасовское равновесие всегда существует, если [math]\displaystyle{ m \ge EM + \Delta }[/math], где [math]\displaystyle{ m }[/math] – общий объем процессорного времени, [math]\displaystyle{ EM = \sum_{i=1}^n s_i }[/math] и [math]\displaystyle{ \Delta = max_k \{ s_k \} }[/math]. Равновесие может быть вычислено за полиномиальное время.
Следующая теорема доказывает существование невозрастающей последовательности цен в случае, если существует вальрасовское равновесие.
Теорема 4. Если существует вальрасовское равновесие в задаче планирования заданий, то оно может быть приведено к равновесию с последовательным распределением и невозрастающим вектором равновесных цен.
Применение
Информационные технологии изменили образ жизни людей, создав множество цифровых товаров, таких как программы для обработки текстов, компьютерные игры, поисковые системы и онлайн-сообщества. Новая экономика уже потребовала применения многих теоретических инструментов (новых и старых, из экономики и других смежных дисциплин) для их разработки и производства, маркетинга и ценообразования. Отсутствие полного понимания новой экономики в основном связано с тем, что цифровые товары часто могут быть повторно произведены без дополнительных затрат, хотя в числе трудностей могут выступать и другие многочисленные факторы. Работа Дэна, Хуан и Ли [1] посвящена процессорному времени как товару, продаваемому на рынке, с помощью вальрасовской модели ценообразования в экономике. Процессорное время как коммерческий продукт широко изучается в сетевых коллективных вычислениях. Обособление ценообразования на процессорное время позволяет отложить в сторону другие сложные вопросы, вызванные второстепенными факторами, а полное понимание этого особого цифрового товара (или услуги) может пролить свет на изучение других товаров в цифровой экономике.
Использование процессорного времени несколькими клиентами было важнейшим вопросом в развитии концепции операционных систем. Развитие сетевых коллективных вычислений предполагает полное использование вычислительных ресурсов, например, процессорного времени, дискового пространства, пропускной способности. В работах [2, 5] были предложены ориентированные на рынок схемы для эффективного распределения ресурсов вычислительной сетки. В дальнейшем появились различные практические и имитационные системы управления ресурсами вычислительных сетей. Помимо распределения ресурсов в распределенных сетях, экономический механизм также был внедрен в задачи управления перегрузками TCP, см. Келли [4].
См. также
Литература
1. Deng, X., Huang, L.-S., Li, M.: On Walrasian Price of CPU time. In: Proceedings of COCOON'05, Knming, 16-19 August 2005, pp. 586-595. Algorithmica 48(2), 159-172 (2007)
2. Ferguson, D., Yemini, Y., Nikolaou, C.: Microeconomic Algorithms for Load Balancing in Distributed Computer Systems. In: Proceedings of DCS'88, pp.419-499. San Jose, 13-17 June 1988,
3. Goldberg, A.V., Hartline, J.D., Wright, A.: Competitive Auctions and Digital Goods. In: Proceedings of SODA'01, pp. 735-744. Washington D.C., 7-9 January 2001
4. Kelly, F.P.: Charging and rate control for elastic traffic. Eur. Trans. Telecommun. 8,33-37 (1997)
5. Kurose, J.F., Simha, R.: A Microeconomic Approach to Optimal Resource Allocation in Distributed Computer Systems. IEEE Trans. Comput. 38(5), 705-717 (1989)
6. Nisan, N.: Bidding and Allocation in Combinatorial Auctions. In: Proceedings of EC'00, pp. 1-12. Minneapolis, 17-20 October 2000