Алгоритмический дизайн механизмов: различия между версиями

''Функция социального выбора'' <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, любого профиля оценок других игроков <math>v_{-i} \in V_{-i}</math> и любых двух оценок игрока i, <math>v_i, v'_i \in V_i</math>, выполняется соотношение

<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>.