4501
правка
Алгоритмический дизайн механизмов: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритмический дизайн механизмов (посмотреть исходный код)
Версия от 10:19, 9 июля 2023
, 9 июля 2023→Постановка задачи
Irina (обсуждение | вклад) м (→Литература) |
Irina (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
'''Мотивирующий пример: поиск кратчайших путей''' | '''Мотивирующий пример: поиск кратчайших путей''' | ||
Пусть дан взвешенный граф. Задача заключается в том, чтобы найти кратчайший путь (с учетом весов ребер) между заданными исходной и целевой вершинами. Каждое ребро контролируется эгоистичным субъектом, а вес ребра, | Пусть дан взвешенный граф. Задача заключается в том, чтобы найти кратчайший путь (с учетом весов ребер) между заданными исходной и целевой вершинами. Каждое ребро контролируется эгоистичным субъектом, а вес ребра, <math>w_e</math>, представляет собой частную информацию. Если ребро выбрано алгоритмом для включения в кратчайший путь, оно понесет затраты, равные его весу со знаком минус (затраты на связь). Платежи ребрам разрешены, и общая полезность ребра, входящего в кратчайший путь и получающего платеж <math>p_e</math>, предполагается равной <math>u_e = p_e - w_e</math>. Обратите внимание, что ''кратчайший путь находится с учетом истинных весов агентов, хотя разработчику они не известны''. | ||
| Строка 19: | Строка 19: | ||
'''Абстрактная формулировка''' | '''Абстрактная формулировка''' | ||
Структура состоит из множества A альтернатив, или результатов, и n игроков, или агентов. Каждый игрок i имеет оценочную функцию | Структура состоит из множества A альтернатив, или результатов, и n игроков, или агентов. Каждый игрок i имеет оценочную функцию <math>v_i: A \to \mathfrak{R}</math>, которая присваивает ценность каждой возможной альтернативе. Эта оценочная функция принадлежит к области <math>V_i</math> всех возможных оценочных функций. Положим <math>V = V_1 \times \cdots \times V_n</math> и <math>V_{- i} = \prod_{j \ne i} V_j</math>. Заметим, что этот подход обобщает пример с поиском кратчайшего пути, приведенный выше: A – это все возможные s - t путей в данном графе, <math>v_e(a)</math> для некоторого пути <math>a \in A</math> равно либо <math>w_e</math> (если <math>e \in a</math>), либо нулю. | ||
Функция социального выбора f: V | ''Функция социального выбора'' <math>f: V \to A</math> назначает социально желательную альтернативу любому заданному профилю оценок игроков. Это служит параллелью понятию алгоритма. Механизм представляет собой кортеж M = (f; p1, : : где f – функция социального выбора, а pi: V !< 8t (для i = 1..: ; n) - цена, взимаемая с игрока i. Интерпретация заключается в том, что специалист по социальному планированию просит игроков раскрыть свои истинные оценки, выбирает альтернативу в соответствии с f, как если бы игроки действительно действовали правдиво, и, кроме того, вознаграждает/наказывает игроков ценами. Эти цены должны порождать «правдивость» в следующем сильном смысле: независимо от того, что заявляют другие игроки, в интересах игрока i всегда раскрыть свою истинную оценку, поскольку это максимизирует его полезность. Формально это можно изложить следующим образом: | ||
| Строка 48: | Строка 48: | ||
Существуют два разных, но тесно связанных направления исследований. Первое представляет собой серию работ, изучающих «цену анархии» заданной системы. Эти работы анализируют существующие системы, пытаясь количественно оценить потерю социальной эффективности из-за эгоистичного характера участников, в то время как подход алгоритмического дизайна механизмов заключается в том, чтобы понять, как следует проектировать новые системы. Подробнее об этом см. статью «Цена анархии». Второе касается алгоритмического исследования различных способов вычисления равновесий. Эти работы привносят вычислительные аспекты в экономику и теорию игр, поскольку задаются вопросом, какие представления о равновесии разумно принять, если требуется вычислительная эффективность; а работы, описанные здесь, привносят теорию игр и экономику в вычислительные науки и теорию алгоритмов, поскольку задаются вопросом, какие алгоритмы разумно разработать, если требуется устойчивость к эгоистичному поведению. Подробнее об этом см., например, статьи «Алгоритмы для равновесия Нэша» и «Равновесие в общем случае». | Существуют два разных, но тесно связанных направления исследований. Первое представляет собой серию работ, изучающих «цену анархии» заданной системы. Эти работы анализируют существующие системы, пытаясь количественно оценить потерю социальной эффективности из-за эгоистичного характера участников, в то время как подход алгоритмического дизайна механизмов заключается в том, чтобы понять, как следует проектировать новые системы. Подробнее об этом см. статью «Цена анархии». Второе касается алгоритмического исследования различных способов вычисления равновесий. Эти работы привносят вычислительные аспекты в экономику и теорию игр, поскольку задаются вопросом, какие представления о равновесии разумно принять, если требуется вычислительная эффективность; а работы, описанные здесь, привносят теорию игр и экономику в вычислительные науки и теорию алгоритмов, поскольку задаются вопросом, какие алгоритмы разумно разработать, если требуется устойчивость к эгоистичному поведению. Подробнее об этом см., например, статьи «Алгоритмы для равновесия Нэша» и «Равновесие в общем случае». | ||
== Основные результаты == | == Основные результаты == | ||
'''Предметная область 1: планирование заданий''' | '''Предметная область 1: планирование заданий''' | ||