Механизм без сожалений

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

Свобода от сожалений — это расслабление правдивости : каждый правдивый механизм свободен от сожалений, но есть свободные от сожалений механизмы, которые не являются правдивыми. В результате свободные от сожалений механизмы существуют даже в ситуациях, в которых сильные результаты невозможности препятствуют существованию правдивых механизмов.

Существует конечное множество X потенциальных результатов . Существует множество N агентов. Каждый агент i имеет предпочтение P _i над X.

Механизм или правило — это функция f , которая получает в качестве входных данных предпочтения агентов P1,...,Pn и возвращает в качестве выходных данных результат из X.

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

Предполагается, что, как только агент наблюдает результат работы механизма, он испытывает сожаление, если его отчет является доминируемой стратегией «задним числом». То есть: учитывая все возможные предпочтения других агентов, которые совместимы с наблюдаемым результатом, существует альтернативный отчет, который дал бы ему такой же или лучший результат.

Механизм сообщения правды без сожалений ^[1] — это механизм, в котором агент, сообщающий о своих правдивых предпочтениях, никогда не испытывает сожалений.

Фернандес ^[2] изучает RFTT в двустороннем сопоставлении. Он показывает, что:

• На рынке сопоставления один к одному алгоритм Гейла-Шепли (GS) является RFTT для обеих сторон, независимо от того, какая сторона предлагает. Более того, GS является уникальным механизмом RFTT в классе квантильно-устойчивых механизмов сопоставления. За пределами этого класса существуют другие механизмы RFTT, но они не являются естественными. В частности, Бостонский механизм и главные торговые циклы не являются RFTT. Более того, на рынке GS правдивость является уникальным отчетом, который гарантирует отсутствие сожалений.
  • Например, предположим, что есть две женщины: Алиса и Батья, и двое мужчин: Чен и Дэн. Предпочтения женщин: Алиса: Дэн>Чен, Батья:Чен>Дэн. Предпочтения мужчин: Дэн:Батья>Ни один>Алиса, Чен:Алиса>Батья. Предположим, что мужчины делают предложение. Тогда, при правдивых отчетах, соответствие будет Дэн-Батья, Чен-Алиса. Если Алиса усечет свои предпочтения и сообщит только Дэна, то соответствие будет Батья-Чен, и Алиса останется безработной. В этом случае Алиса сожалеет, что не была честна, так как честность гарантировала бы, что она будет трудоустроена.
• На рынке сопоставления «многие к одному» (например, сопоставление больниц и врачей) GS, предлагающий врача, является RFTT для обеих сторон, но GS, предлагающий больницу, не является RFTT. Это подтверждает решение NRMP перейти от GS, предлагающего больницу, к GS, предлагающему врача.

Чен и Моллер ^[3] изучают механизмы выбора школы . Они фокусируются на правиле отложенного принятия с поправкой на эффективность (EADA или EDA). ^[4] Известно, что EDA не является стратегией, защищающей студентов; Чен и Моллер показывают, что EDA является RFTT. Они также показывают, что ни одно эффективное правило соответствия, которое слабо доминирует по Парето над стабильным правилом соответствия, не является RFTT.

Аррибильяга, Бонифасио и Фернандес ^{[1] изучают} правила голосования RFTT . Они показывают, что:

• Когда правило голосования зависит только от верхней альтернативы каждого агента (например, голосование большинства ), RFTT эквивалентно strategyproofness . Это означает, что для 3 или более результатов единственными механизмами RFTT являются диктатуры (по теореме о невозможности Гиббарда-Саттертуэйта ); а для 2 результатов механизм является RFTT тогда и только тогда, когда он является расширенным правилом большинства .
  • В качестве примера, чтобы увидеть, что относительное голосование не является RFTT для 3 результатов, предположим, что рейтинг предпочтений агента z>y>x. Если он видит, что x избран, то, оглядываясь назад, голосование за y является доминирующей стратегией: оно никогда не может навредить (поскольку x уже является худшим результатом), и оно может помочь (если y и x были равны).
• Для эгалитарных правил голосования : все нейтральные варианты (т. е. разрыв ничьих фиксированным порядком агентов) являются RFTT. Анонимные варианты (разрыв ничьих фиксированным порядком кандидатов) являются RFTT, если есть по крайней мере m -1 избирателей, или число избирателей делит m -1.
• Для правила голосования с правом вето (правило подсчета очков, при котором все кандидаты получают 1 балл, за исключением наименее предпочтительного, который получает 0), результаты аналогичны эгалитарным правилам. Аналогично, k-одобрение — это RFTT.
• Другие правила подсчета очков могут не быть RFTT. В частности, голосование Борда , голосование по принципу большинства и голосование Дауделла , а также все эффективные анонимные правила не являются RFTT.
• Все правила голосования, соответствующие Кондорсе , которые также удовлетворяют слабому условию монотонности, не являются RFTT. Это условие выполняется, в частности, для правил Симпсона, Коупленда, Янга, Доджсона, Фишберна и Блэка (как в анонимной, так и в нейтральной версии). Правила последовательного исключения также не являются RFTT.

Тамуз, Варди и Зиани ^[5] изучают сожаление при честном разрезании торта . Они изучают вариант повторяющейся игры «разрежь и выбери» . В стандартной игре «разрежь и выбери» не склонный к риску резак разрезал бы торт на две равные по его мнению части. Но в их условиях каждый день есть другой резак, играющий в «разрежь и выбери» с одним и тем же выбирающим. Каждый резак знает все прошлые выборы выбирающего и может потенциально использовать эту информацию, чтобы сделать разрез, который гарантирует ему больше половины торта. Их цель — разработать неэксплуатируемые протоколы — протоколы, в которых резак никогда не может знать, какой кусок выберет выбирающий, и поэтому всегда разрезает торт на две равные по его мнению части. Идея состоит в том, чтобы ограничить позиции, в которых резак может разрезать торт; такие протоколы называются протоколами принудительного разрезания . Простой неэксплуатируемый протокол принудительного разрезания: в каждый день брать все куски, полученные в предыдущий день (принудительным и непринудительным разрезанием), и заставлять резак разрезать каждый из этих кусков на две части. Этот протокол использует 2 ⁿ разрезов, где n — количество дней. Существуют протоколы, которые используют меньше разрезов, в зависимости от количества измерений торта:

• Если торт представляет собой n -мерное выпуклое множество, то существует протокол принудительного разрезания без зависти, который использует n разрезов (один разрез в день). Каждый день резак вынужден делать разрез в другом измерении, ортогональном всем предыдущим разрезам, поэтому информация из предыдущих дней бесполезна.
• Если торт одномерный, то:
  • Существует адаптивный протокол принудительного разреза без зависти, который использует 3 разреза в день. Каждый день есть один адаптивный принудительный разрез, и резак должен сделать два дополнительных разреза (по одному с каждой стороны принудительного разреза).
  • Не существует неадаптивного протокола принудительного разреза, который использовал бы фиксированное количество разрезов в день;
  • Существует неадаптивный протокол принудительного разрезания, который использует O( n ² ) разрезов, где n — количество дней. В каждый день выполняется n принудительных разрезов по 1/( n +1),..., n /( n +1); резак должен сделать n +1 разрезов (по одному в каждом интервале).
• Если торт представляет собой двумерное множество (например, квадрат), то существует неадаптивный протокол принудительного разреза, использующий 3 разреза в день. В каждый день t выполняется вертикальный принудительный разрез в момент времени t /( n +1). Резак должен сделать горизонтальный разрез с каждой стороны вертикального разреза.

Кресто и Таджер ^[6] также изучают сожаление при честном разрезании торта между двумя агентами, где сожаление возникает из-за изменения предпочтений: после того, как один игрок видит выбор другого игрока, его предпочтения могут измениться. Они предлагают вариант разрезания и выбора , который позволяет избежать такого рода сожаления.