4430
правок
Алгоритмический дизайн механизмов: различия между версиями
Материал из WEGA
Алгоритмический дизайн механизмов (посмотреть исходный код)
Версия от 00:11, 10 июля 2023
, 10 июля 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 57: | Строка 57: | ||
== Основные результаты == | == Основные результаты == | ||
'''Предметная область 1: планирование заданий''' | '''Предметная область № 1: планирование заданий''' | ||
Планирование заданий – это классическая алгоритмическая формулировка задачи: n заданий необходимо распределить между m машинами, | Планирование заданий – это классическая алгоритмическая формулировка задачи: n заданий необходимо распределить между m машинами, учитывая, что задание j требует времени обработки <math>p_{ij}</math> на машине i. В теоретико-игровой формулировке предполагается, что каждая машина i является эгоистичным субъектом, который несет затраты <math>p_{ij}</math> от обработки задания j. Заметим, что платежи в этой формулировке (и в общем случае) могут быть отрицательными, компенсируя такие затраты. Популярной алгоритмической целью является распределение заданий между машинами с целью минимизации «продолжительности работы»: <math>max_i \sum_{j \; is \; assigned \; to \; i} p_{ij}</math> (j назначено i). Это отличается от ориентации на максимизацию благосостояния, которая в данном случае сводится к минимизации <math>\sum_i \sum_{j \; is \; assigned \; to \; i} p_{ij}</math>, что еще раз иллюстрирует проблему различия алгоритмических целей. Таким образом, схема ВКГ здесь не может использоваться, и необходимо разработать новые методы. | ||
| Строка 92: | Строка 92: | ||
'''Предметная область 2: цифровые товары и максимизация доходов''' | '''Предметная область № 2: цифровые товары и максимизация доходов''' | ||
В эпоху электронной коммерции появился новый вид «цифровых товаров»: товары без предельных издержек производства – иначе говоря, товары с неограниченным объемом предложения. Одним из примеров являются песни, продаваемые через Интернет. Производство песни требует затрат, но после этого создание дополнительных электронных копий не влечет за собой никаких дополнительных расходов. Как следует продавать такие товары? Одним из вариантов может быть проведение ''аукциона'''. Аукцион представляет собой односторонний рынок, где монополист (аукционист) желает продать один или несколько товаров ряду покупателей. | В эпоху электронной коммерции появился новый вид «цифровых товаров»: товары без предельных издержек производства – иначе говоря, товары с неограниченным объемом предложения. Одним из примеров являются песни, продаваемые через Интернет. Производство песни требует затрат, но после этого создание дополнительных электронных копий не влечет за собой никаких дополнительных расходов. Как следует продавать такие товары? Одним из вариантов может быть проведение ''аукциона'''. Аукцион представляет собой односторонний рынок, где монополист (аукционист) желает продать один или несколько товаров ряду покупателей. | ||
| Строка 112: | Строка 112: | ||
'''Предметная область 3: комбинаторные аукционы''' | '''Предметная область № 3: комбинаторные аукционы''' | ||
Комбинаторные аукционы (КА) представляют собой центральную модель, имеющую теоретическое значение и практическую значимость. Она обобщает многие задачи теории алгоритмов, такие как планирование заданий и сетевая маршрутизация, и проявляется во многих реальных ситуациях. Эта новая модель имеет различные чисто вычислительные аспекты, а кроме того, демонстрирует интересные проблемы теории игр. Хотя каждый аспект важен сам по себе, очевидно, что только их объединение дает приемлемое решение. | Комбинаторные аукционы (КА) представляют собой центральную модель, имеющую теоретическое значение и практическую значимость. Она обобщает многие задачи теории алгоритмов, такие как планирование заданий и сетевая маршрутизация, и проявляется во многих реальных ситуациях. Эта новая модель имеет различные чисто вычислительные аспекты, а кроме того, демонстрирует интересные проблемы теории игр. Хотя каждый аспект важен сам по себе, очевидно, что только их объединение дает приемлемое решение. | ||
| Строка 172: | Строка 172: | ||
'''Предметная область 4: онлайн-аукционы''' | '''Предметная область № 4: онлайн-аукционы''' | ||
В классической для вычислительных наук задаче «онлайн-вычислений» входные данные алгоритма становятся известными не одномоментно, до начала вычислений, а постепенно, с течением времени. Такая структура подходит для проведения аукционов, особенно в новых электронных средах. Что происходит, когда игроки прибывают со временем, а аукционист должен принимать решения, в любой момент имея дело только с подмножеством игроков? | В классической для вычислительных наук задаче «онлайн-вычислений» входные данные алгоритма становятся известными не одномоментно, до начала вычислений, а постепенно, с течением времени. Такая структура подходит для проведения аукционов, особенно в новых электронных средах. Что происходит, когда игроки прибывают со временем, а аукционист должен принимать решения, в любой момент имея дело только с подмножеством игроков? | ||
