4430
правок
Алгоритмический дизайн механизмов: различия между версиями
Материал из WEGA
Алгоритмический дизайн механизмов (посмотреть исходный код)
Версия от 13:07, 9 июля 2023
, 9 июля 2023→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
''Функция социального выбора'' <math>f: V \to A</math> назначает социально желательную альтернативу любому заданному профилю оценок игроков. Это служит параллелью понятию алгоритма. Механизм представляет собой кортеж M = (f | ''Функция социального выбора'' <math>f: V \to A</math> назначает социально желательную альтернативу любому заданному профилю оценок игроков. Это служит параллелью понятию алгоритма. ''Механизм'' представляет собой кортеж <math>M = (f, p_1, ..., p_n)</math> где f – функция социального выбора, а <math>p_i: V \to \mathfrak{R}</math> (для i = 1, ..., n) - цена, взимаемая с игрока i. Интерпретация заключается в том, что специалист по социальному планированию просит игроков раскрыть свои истинные оценки, выбирает альтернативу в соответствии с f, как если бы игроки действительно действовали правдиво, и, кроме того, вознаграждает/наказывает игроков ценами. Эти цены должны порождать «правдивость» в следующем сильном смысле: независимо от того, что заявляют другие игроки, в интересах игрока i всегда раскрыть свою истинную оценку, поскольку это максимизирует его полезность. Формально это можно изложить следующим образом: | ||
Определение 1 (правдивость). M является «правдивым» (в доминирующих стратегиях), если для любого игрока i, любого профиля оценок других игроков v_ | '''Определение 1 (правдивость)'''. Механизм M является «правдивым» (в доминирующих стратегиях), если для любого игрока i, любого профиля оценок других игроков <math>v_{-i} \in V_{-i}</math> и любых двух оценок игрока <math>iv_i, v'_i \in V_i</math>, выполняется соотношение | ||
где f( | |||
<math>v_i(a) - p_i (v_i, v_{-i}) \ge v_i(b) - p_i (v'_i, v_{-i})</math>, где <math>f(v_i, v_{-i}) = a</math> и <math>f(v'_i; v_{-i}) = b</math>. | |||
| Строка 32: | Строка 33: | ||
Определение 2 (максимизация общественного благосостояния). Функция социального выбора f: V | '''Определение 2 (максимизация общественного благосостояния)'''. Функция социального выбора <math>f: V \to A</math> максимизирует общественное благосостояние, если <math>f(v) \in argmax_{a \in A} \sum_i v_i(a)</math> для любого <math>v \in V</math>. | ||
