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

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

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

Примеры

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

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

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

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

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

Существует ряд возможных результатов. Х {\displaystyle X}

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

в я : Х ⟶ Р + {\displaystyle v_{i}:X\longrightarrow R_{+}}

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

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

ты я := в я ( х ) + п я {\displaystyle u_{i}:=v_{i}(x)+p_{i}}

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

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

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

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

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

в я ( О ты т с о м е ( в я , в − я ) ) + П а у м е н т я ( в я , в − я ) ≥ в я ( О ты т с о м е ( в я ′ , в − я ) ) + П а у м е н т я ( в я ′ , в − я ) {\displaystyle v_{i}(Результат(v_{i},v_{-i}))+Платеж_{i}(v_{i},v_{-i})\geq v_{i}(Результат(v_{i}',v_{-i}))+Платеж_{i}(v_{i}',v_{-i})}

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

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

Если механизм с денежными переводами является SP, то он должен удовлетворять следующим двум условиям для каждого агента : [1] : 226  я {\displaystyle я}

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

О ты т с о м е ( в я , в − я ) = О ты т с о м е ( в я ′ , в − я ) {\displaystyle Outcome(v_{i},v_{-i})=Outcome(v_{i}',v_{-i})}

затем:

П а у м е н т я ( в я , в − я ) = П а у м е н т я ( в я ′ , в − я ) {\displaystyle Платеж_{i}(v_{i},v_{-i})=Платеж_{i}(v_{i}',v_{-i})}

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

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

O u t c o m e ( v i , v − i ) = x {\displaystyle Outcome(v_{i},v_{-i})=x}

затем:

P a y m e n t i ( v i , v − i ) = P r i c e i ( x , v − i ) {\displaystyle Payment_{i}(v_{i},v_{-i})=Price_{i}(x,v_{-i})}

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

O u t c o m e ( v i , v − i ) ∈ arg ⁡ max x [ v i ( x ) + P r i c e i ( x , v − i ) ] {\displaystyle Outcome(v_{i},v_{-i})\in \arg \max _{x}[v_{i}(x)+Price_{i}(x,v_{-i})]}

где максимизация осуществляется по всем результатам в диапазоне . O u t c o m e ( ⋅ , v − i ) {\displaystyle Outcome(\cdot ,v_{-i})}

ДОКАЗАТЕЛЬСТВО: Если есть другой результат, такой что , то агент с оценкой предпочитает сообщить , так как это дает ему большую общую полезность. x ′ = O u t c o m e ( v i ′ , v − i ) {\displaystyle x'=Outcome(v_{i}',v_{-i})} v i ( x ′ ) + P r i c e i ( x ′ , v − i ) > v i ( x ) + P r i c e i ( x , v − i ) {\displaystyle v_{i}(x')+Price_{i}(x',v_{-i})>v_{i}(x)+Price_{i}(x,v_{-i})} v i {\displaystyle v_{i}} v i ′ {\displaystyle v_{i}'}

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

ДОКАЗАТЕЛЬСТВО: Зафиксируйте агента и оценки . Обозначим: i {\displaystyle i} v i , v i ′ , v − i {\displaystyle v_{i},v_{i}',v_{-i}}

x := O u t c o m e ( v i , v − i ) {\displaystyle x:=Outcome(v_{i},v_{-i})} - результат, когда агент действует правдиво.
x ′ := O u t c o m e ( v i ′ , v − i ) {\displaystyle x':=Outcome(v_{i}',v_{-i})} - результат, когда агент действует неправдиво.

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

u i ( v i ) = v i ( x ) + P r i c e i ( x , v − i ) {\displaystyle u_{i}(v_{i})=v_{i}(x)+Price_{i}(x,v_{-i})}

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

u i ( v i ′ ) = v i ( x ′ ) + P r i c e i ( x ′ , v − i ) {\displaystyle u_{i}(v_{i}')=v_{i}(x')+Price_{i}(x',v_{-i})}

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

u i ( v i ) ≥ u i ( v i ′ ) {\displaystyle u_{i}(v_{i})\geq u_{i}(v_{i}')}

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

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

Фактическая цель механизма — его функция; функция оплаты — это всего лишь инструмент, побуждающий игроков быть честными. Следовательно, полезно знать, учитывая определенную функцию результата, можно ли ее реализовать с помощью механизма SP или нет (это свойство также называется реализуемостью ). [ необходима цитата ] O u t c o m e {\displaystyle Outcome}

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

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

Однопараметрический домен — это игра, в которой каждый игрок получает определенное положительное значение за «выигрыш» и значение 0 за «проигрыш». Простым примером является аукцион с одним предметом, в котором — это значение, которое игрок назначает предмету. i {\displaystyle i} v i {\displaystyle v_{i}} v i {\displaystyle v_{i}} 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  ϵ > 0 {\displaystyle \epsilon >0} 1 − ϵ {\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. ^ abcde Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
  2. ^ "Групповая стратегия-устойчивость и социальный выбор между двумя альтернативами" (PDF) . Архивировано из оригинала (PDF) 2020-02-12.
  3. ^ ab Чакрабарти, Дипарнаб; Свами, Чайтанья (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. 
Retrieved from "https://en.wikipedia.org/w/index.php?title=Strategyproofness&oldid=1261936004"