Стратегическая устойчивость

В проектировании механизмов механизм , устойчивый к стратегии (SP), представляет собой форму игры , в которой каждый игрок имеет слабо доминирующую стратегию , так что ни один игрок не может получить выгоду, «шпионя» за другими игроками, чтобы узнать, во что они собираются играть. Когда игроки имеют личную информацию (например, их тип или значение какого-либо предмета), а стратегическое пространство каждого игрока состоит из возможных информационных значений (например, возможных типов или значений), правдивый механизм — это игра, в которой раскрывается истинная информация. информация является слабо доминантной стратегией для каждого игрока. Механизм SP также называется совместимым с доминирующей стратегией и стимулированием (DSIC) . чтобы отличить его от других видов совместимости стимулов .

Механизм SP невосприимчив к манипуляциям со стороны отдельных игроков (но не коалиций). Напротив, в механизме, защищенном от групповой стратегии , ни одна группа людей не может вступить в сговор, чтобы исказить свои предпочтения таким образом, чтобы улучшить положение каждого члена. В сильном механизме защиты от групповой стратегии ни одна группа людей не может вступить в сговор, чтобы исказить свои предпочтения таким образом, чтобы улучшить благосостояние хотя бы одного члена группы, не ухудшив при этом положение остальных членов.

Примеры

Типичными примерами механизмов SP являются:

• большинство голосов между двумя альтернативами;
• аукцион второй цены, когда участники имеют квазилинейную полезность ;
• механизм VCG, когда участники имеют квазилинейную полезность

Типичными примерами механизмов, не являющихся SP, являются:

• любые детерминированные недиктаторские выборы между тремя или более альтернативами;
• аукцион первой цены

SP в сетевой маршрутизации

SP также применим в сетевой маршрутизации . Рассмотрим сеть как граф , где каждое ребро (т. е. ссылка) имеет связанную с ней , известную стоимость передачи в частном порядке владельцу ссылки. Владелец ссылки желает получать вознаграждение за ретрансляцию сообщений. Отправитель сообщения в сети хочет найти путь с наименьшей стоимостью. Для этого существуют эффективные методы даже в больших сетях. Однако есть одна проблема: стоимость каждой ссылки неизвестна. Наивный подход заключался бы в том, чтобы спросить владельца каждой ссылки о стоимости, использовать эти заявленные затраты, чтобы найти путь с наименьшей стоимостью, и оплатить всем ссылкам на пути их заявленную стоимость. Однако можно показать, что данная схема оплаты не является SP, то есть владельцы некоторых ссылок могут получить выгоду, солгав о стоимости. В конечном итоге мы можем заплатить гораздо больше, чем фактическая стоимость. Можно показать, что при определенных предположениях о сети и игроках (владельцах ссылок) вариантом механизма VCG является SP.

Формальные определения

Есть набор $X$ возможных результатов.

Есть $n$ агенты, которые имеют разные оценки для каждого результата. Оценка агента $i$ представляется в виде функции:

$v_{i}:X\longrightarrow R_{+}$

который выражает ценность каждой альтернативы в денежном выражении.

Предполагается, что агенты имеют полезности квазилинейные функции ; это означает, что если результат $x$ и дополнительно агент получает оплату $p_{i}$ (положительная или отрицательная), то общая полезность агента $i$ является:

$u_{i}:=v_{i}(x)+p_{i}$

Вектор всех функций цены обозначается $v$.

Для каждого агента $i$вектор всех функций ценности других агентов обозначается через $v_{-i}$. Так $v\equiv (v_{i},v_{-i})$.

Механизм – это пара функций:

• Ан $Outcome$ функция, которая принимает на вход вектор значений $v$ и возвращает результат $x\in X$ (ее еще называют функцией социального выбора );
• А $Payment$ функция, которая принимает в качестве входных данных вектор значений $v$ и возвращает вектор платежей, $(p_{1},\dots ,p_{n})$, определяя, какую сумму должен получить каждый игрок (отрицательный платеж означает, что игрок должен заплатить положительную сумму).

Механизм называется стратегически устойчивым , если для каждого игрока $i$ и для каждого вектора ценностей других игроков $v_{-i}$:

$v_{i}(Outcome(v_{i},v_{-i}))+Payment_{i}(v_{i},v_{-i})\geq v_{i}(Outcome(v_{i}',v_{-i}))+Payment_{i}(v_{i}',v_{-i})$

Характеристика

Полезно иметь простые условия для проверки того, является ли данный механизм SP или нет. В этом подразделе показаны два простых условия, которые являются одновременно необходимыми и достаточными.

Если механизм денежных переводов является SP, то он должен удовлетворять следующим двум условиям: для каждого агента $i$:

1. Оплата агенту $i$ является функцией выбранного результата и оценок других агентов. $v_{-i}$ - но не является прямой функцией собственной оценки агента $v_{i}$. Формально существует функция цены $Price_{i}$, который принимает в качестве входных данных результат $x\in X$ и вектор оценки для других агентов $v_{-i}$, и возвращает оплату агенту $i$, такой, что для каждого $v_{i},v_{i}',v_{-i}$, если:

$Outcome(v_{i},v_{-i})=Outcome(v_{i}',v_{-i})$

затем:

$Payment_{i}(v_{i},v_{-i})=Payment_{i}(v_{i}',v_{-i})$

ДОКАЗАТЕЛЬСТВО: Если $Payment_{i}(v_{i},v_{-i})>Payment_{i}(v_{i}',v_{-i})$ затем агент с оценкой $v_{i}'$ предпочитает сообщать $v_{i}$, поскольку это дает ему тот же результат и более крупную оплату; аналогично, если $Payment_{i}(v_{i},v_{-i})<Payment_{i}(v_{i}',v_{-i})$ затем агент с оценкой $v_{i}$ предпочитает сообщать $v_{i}'$.

Как следствие, существует функция «ценника», $Price_{i}$, который принимает в качестве входных данных результат $x\in X$ и вектор оценки для других агентов $v_{-i}$, и возвращает оплату агенту $i$ Для каждого $v_{i},v_{-i}$, если:

$Outcome(v_{i},v_{-i})=x$

затем:

$Payment_{i}(v_{i},v_{-i})=Price_{i}(x,v_{-i})$

2. Выбранный исход оптимален для агента. $i$, учитывая оценки других агентов. Формально:

$Outcome(v_{i},v_{-i})\in \arg \max _{x}[v_{i}(x)+Price_{i}(x,v_{-i})]$

где максимизация ведется по всем результатам в диапазоне $Outcome(\cdot ,v_{-i})$.

ДОКАЗАТЕЛЬСТВО: Если есть другой результат $x'=Outcome(v_{i}',v_{-i})$ такой, что $v_{i}(x')+Price_{i}(x',v_{-i})>v_{i}(x)+Price_{i}(x,v_{-i})$, то агент с оценкой $v_{i}$ предпочитает сообщать $v_{i}'$, поскольку это дает ему большую общую полезность.

Условия 1 и 2 не только необходимы, но и достаточны: любой механизм, удовлетворяющий условиям 1 и 2, является SP.

ДОКАЗАТЕЛЬСТВО: исправить агента $i$ и оценки $v_{i},v_{i}',v_{-i}$. Обозначим:

$x:=Outcome(v_{i},v_{-i})$ - результат, когда агент действует правдиво.

$x':=Outcome(v_{i}',v_{-i})$ - результат, когда агент действует неправдиво.

По свойству 1 полезность агента при честной игре равна:

$u_{i}(v_{i})=v_{i}(x)+Price_{i}(x,v_{-i})$

а полезность агента при игре неправдой равна:

$u_{i}(v_{i}')=v_{i}(x')+Price_{i}(x',v_{-i})$

По свойству 2:

$u_{i}(v_{i})\geq u_{i}(v_{i}')$

поэтому доминирующей стратегией агента является действовать правдиво.

Характеристика функции результата

Фактическая цель механизма – это его $Outcome$ функция; функция оплаты — это всего лишь инструмент, побуждающий игроков быть правдивыми. Следовательно, полезно знать для определенной выходной функции, может ли она быть реализована с использованием механизма SP или нет (это свойство также называется реализуемостью ).

Свойство монотонности необходимо для устойчивости стратегии.

Истинные механизмы в однопараметрических областях

Однопараметрическая область — это игра, в которой каждый игрок $i$ получает определенное положительное значение $v_{i}$ для «выигрыша» и значение 0 для «проигрыша». Простым примером является аукцион одного предмета, на котором $v_{i}$ ценность, которую игрок $i$ присваивается элементу.

В этой ситуации легко охарактеризовать правдивые механизмы. Начнем с некоторых определений.

Механизм называется нормализованным, если за каждую проигрышную ставку выплачивается 0.

Механизм называется монотонным , если при повышении ставки игроком его шансы на выигрыш (слабо) увеличиваются.

Для монотонного механизма для каждого игрока i и каждой комбинации ставок других игроков существует критическое значение , при котором игрок переходит от проигрыша к выигрышу.

Нормализованный механизм в однопараметрической области правдив, если выполняются следующие два условия:

1. Функция назначения монотонна в каждой из заявок и:
2. Каждая выигрышная ставка приносит критическую ценность.

Правдивость рандомизированных механизмов

Существуют различные способы распространить понятие правдивости на рандомизированные механизмы. Они от самого сильного к самому слабому:

• Универсальная правдивость : для каждой рандомизации алгоритма результирующий механизм правдив. Другими словами: универсально-истинный механизм — это рандомизация детерминированных истинных механизмов, где веса могут зависеть от входных данных.
• Правдивость с сильным стохастическим доминированием (сильная SD-правдивость) : вектор вероятностей, которые агент получает, будучи правдивым, имеет стохастическое доминирование первого порядка над вектором вероятностей, которые он получает, сообщая ложные сведения. То есть: вероятность получения высшего приоритета как минимум столь же высока И вероятность получения одного из двух высших приоритетов как минимум столь же высока И ... вероятность получения одного из m высших приоритетов как минимум столь же высока. .
• Лексикографическая правдивость (лекс-правдивость) : вектор вероятностей, которые агент получает, будучи правдивым, имеет лексикографическое доминирование над вектором вероятностей, которые он получает, сообщая ложные сведения. То есть: вероятность получения высшего приоритета выше ИЛИ (вероятность получения высшего приоритета равна и вероятность получения одного из двух высших приоритетов выше) ИЛИ... (вероятность получения первого m - Приоритет 1 приоритета равен и вероятность получения одного из m высших приоритетов выше) ИЛИ (все вероятности равны).
• Правдивость со слабым стохастическим доминированием (слабая правдивость со стохастическим доминированием) : вектор вероятностей, который агент получает, будучи правдивым, не находится под стохастическим доминированием первого порядка вектором вероятностей, который он получает, сообщая ложные сведения.

Из универсального следует сильное SD, из Lex следует слабое SD, и все импликации строгие.

Правдивость с высокой вероятностью

Для каждой константы $\epsilon >0$, рандомизированный механизм называется правдивым с вероятностью $1-\epsilon$ если для каждого агента и для каждого вектора ставок вероятность того, что агент выиграет от неправдивых ставок, не превышает $\epsilon$, где за вероятность берется случайность механизма.

Если константа $\epsilon$ переходит в 0, когда число участников растет, тогда механизм с высокой вероятностью называется правдивым . Это понятие слабее полной правдивости, но в некоторых случаях оно все же полезно; см., например, консенсус-оценка .

Защита от ложного имени

Новый тип мошенничества, который стал обычным явлением в связи с обилием интернет-аукционов, — это ставки от вымышленного имени — заявки, поданные одним участником торгов с использованием нескольких идентификаторов, таких как несколько адресов электронной почты.

Защита от вымышленного имени означает, что ни у одного из игроков нет стимула делать ставки под вымышленным именем. Это более сильное понятие, чем устойчивость стратегии. В частности, аукцион Викри-Кларка-Гроувса (VCG) не является защитой от ложных имен.

Защита от ложного имени существенно отличается от защиты от групповой стратегии, поскольку предполагает, что отдельный человек в одиночку может имитировать определенное поведение, которое обычно требует совместной координации нескольких людей.

См. также

• Совместимость стимулов
• Индивидуальная рациональность
• Критерий участия – игрок не может проиграть, играя в игру (т.е. у игрока нет стимула избегать игры)

Дальнейшее чтение

• Паркс, Дэвид К. (2004), О проектировании обучаемых механизмов, в: Тумер, Каган и Дэвид Вулперт (ред.): Коллективы и проектирование сложных систем, Нью-Йорк uaO, стр. 107–133.
• Об асимптотической стратегической устойчивости классических правил социального выбора Статья Аркадия Слинько об стратегической устойчивости в системах голосования.