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

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

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

Примеры

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

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

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

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

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

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\equiv (v_{i},v_{-i})}$

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

• Функция , которая принимает в качестве входных данных вектор значений и возвращает результат (ее также называют функцией социального выбора ); ${\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, является СП.

ДОКАЗАТЕЛЬСТВО: Зафиксируйте агента и оценки . Обозначим: ${\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}$

Свойство монотонности необходимо для стратегической устойчивости. ^{[ необходима цитата ]}

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

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

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

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

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

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

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

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

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

Существуют различные способы распространить понятие правдивости на рандомизированные механизмы. Они перечислены от самых сильных к самым слабым: ^{[3] : 6–8}

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

Универсальный подразумевает сильное SD, Lex подразумевает слабое SD, и все импликации строгие. ^{[3] : Теория 3.4}

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

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

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

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

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

False-name-proofness означает, что нет стимула для любого из игроков делать ставки с ложным именем. Это более сильное понятие, чем strategyproofness. В частности, аукцион Vickrey–Clarke–Groves (VCG) не является false-name-proof. ^[4]

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

Смотрите также

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

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

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

Ссылки

1. Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
2. "Групповая стратегия-устойчивость и социальный выбор между двумя альтернативами" (PDF) . Архивировано из оригинала (PDF) 2020-02-12.
3. Чакрабарти, Дипарнаб; Свами, Чайтанья (2014-01-12). «Максимизация благосостояния и правдивость в проектировании механизмов с порядковыми предпочтениями». Труды 5-й конференции по инновациям в теоретической информатике . ITCS '14. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 105–120. doi :10.1145/2554797.2554810. ISBN 978-1-4503-2698-8. S2CID  2428592.
4. Yokoo, M.; Sakurai, Y.; Matsubara, S. (2004). «Эффект ставок с поддельными именами на комбинаторных аукционах: новое мошенничество на интернет-аукционах». Игры и экономическое поведение . 46 : 174–188. CiteSeerX 10.1.1.18.6796 . doi :10.1016/S0899-8256(03)00045-9.