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

В теории игр , асимметричный игра , где игроки имеют отдельную информацию называется strategyproof или strategyproof (SP) , если она является слабо- доминирующей стратегией для каждого игрока , чтобы показать его / ее личную информацию, ^{[1] : 244} т.е. с учетом нет информации о том, что делают другие, вам лучше или, по крайней мере, не хуже, если вы будете правдивы.

SP также называют правдивым или совместимым со стимулом доминирующей стратегии (DSIC) , ^{[1] : 415,} чтобы отличить его от других видов совместимости стимулов .

SP-игра не всегда защищена от сговора, но ее надежные варианты защищены; с группой strategyproofness ни одна группа людей не может вступить в сговор , чтобы недостоверные свои предпочтения таким образом , что делает каждый член лучше, и с сильной группой strategyproofness ни одна группа людей не может вступить в сговор , чтобы недостоверные свои предпочтения таким образом , что составляет по меньшей мере один член группы лучше, не делая хуже ни одному из оставшихся членов. ^[2]

Примеры [ править ]

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

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

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

Обозначение [ править ]

Есть набор возможных исходов.${\ displaystyle X}$

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

${\ displaystyle v_ {i}: X \ longrightarrow R _ {+}}$

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

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

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

Вектор всех функций-значений обозначается .${\ displaystyle v}$

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

Механизм представляет собой пару функций:

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

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

${\displaystyle 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, то он должен удовлетворять следующим двум условиям для каждого агента : ^{[1] : 226}${\displaystyle i}$

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

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

тогда:

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

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

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

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

тогда:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Характеристика функции результата [ править ]

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

Правдивые механизмы в однопараметрических доменах [ править ]

Домен с одним параметром является игра , в которой каждый игрок я получает определенное положительное значение v _I для «победы» и значение 0 для «потери». Простым примером является аукцион одного предмета, в котором v _i - это стоимость, которую игрок i присваивает предмету.

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

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

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

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

Нормализованный механизм в однопараметрической области является истинным, если выполняются следующие два условия: ^{[1] : 229–230}

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

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

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

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

Защита от ложных имен [ править ]

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

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

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

См. Также [ править ]

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

Дальнейшее чтение [ править ]

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

Ссылки [ править ]