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

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

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

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

Примеры

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

Типичные примеры механизмов, не являющихся 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})}$.

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

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

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}')}$

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

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

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

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

А однопараметрическая область это игра, в которой каждый игрок я получает определенное положительное значение v_я для "выигрыша" и значение 0 для "проигрыша". Простым примером является аукцион по продаже отдельных предметов, на котором v_я это ценность, которую игрок я присваивает элементу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

1. Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Ива (2007). Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN  0-521-87282-0.
2. «Стойкость к групповой стратегии и социальный выбор между двумя альтернативами» (PDF).
3. Yokoo, M .; Sakurai, Y .; Мацубара, С. (2004). «Эффект фальшивых ставок на комбинаторных аукционах: новое мошенничество на интернет-аукционах». Игры и экономическое поведение. 46: 174–188. CiteSeerX  10.1.1.18.6796. Дои:10.1016 / S0899-8256 (03) 00045-9.