Безотказный механизм
В конструкции механизма механизм сообщения правды без сожалений ( 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.
Чен и Моллер [3] изучить механизмы выбора школы . Они сосредоточены на правиле отсроченной приемки с поправкой на эффективность (EADA или EDA). [4] Известно, что EDA не является стратегией для студентов; Чен и Моллер показывают, что EDA — это RFTT. Они также показывают, что ни одно эффективное правило сопоставления, которое слабо доминировало бы по Парето над стабильным правилом сопоставления, не является RFTT.
В голосовании
[ редактировать ]Аррибильяга, Бонифачо и Фернандес [1] изучить правила голосования RFTT . Они показывают, что:
- Когда правило голосования зависит только от верхней альтернативы каждого агента (например, множественное голосование ), RFTT эквивалентно устойчивости стратегии . Это означает, что для 3 или более результатов единственными механизмами RFTT являются диктатуры (согласно теореме невозможности Гиббарда – Саттертуэйта ); а для двух исходов механизм является 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 2 ) сокращений, где n – количество дней. Каждый день происходит n принудительных сокращений в точках 1/( n +1),..., n /( n +1); резак должен сделать n +1 разрезов (по одному в каждом интервале).
- Если торт представляет собой двумерный набор (например, квадрат), то существует неадаптивный протокол принудительного разрезания, использующий 3 разреза в день. В каждый день t происходит принудительное вертикальное сокращение в точке t /( n +1). Резак должен сделать горизонтальный разрез с каждой стороны вертикального разреза.
Кресто и Тир [6] также изучите сожаление при честном разрезании торта между двумя агентами, где сожаление возникает из-за изменения предпочтений: после того, как один игрок увидит выбор другого игрока, его предпочтения могут измениться. Они предлагают вариант « режим и выбираем», позволяющий избежать такого рода сожалений.
Ссылки
[ редактировать ]- ^ Jump up to: а б Пол Аррибильяга, Р.; Бонифаций, Августин Г.; Марсело Ариэль Фернандес (2022). «Правила голосования без сожалений и правды». arXiv : 2208.13853 [ econ.TH ].
- ^ Фернандес, Марсело Ариэль (31 июля 2020 г.). «Отложенное принятие и откровение правды без сожалений» . Архив рабочих документов по экономике .
- ^ Чен, Ицю; Мёллер, Маркус (2021). «Говорить правду без сожалений при выборе школы с согласия» . Электронный журнал ССРН . дои : 10.2139/ssrn.3896306 . ISSN 1556-5068 . S2CID 236911018 .
- ^ Academic.oup.com https://academic.oup.com/qje/article-abstract/125/3/1297/1903670 . Проверено 15 января 2024 г.
{{cite web}}: Отсутствует или пусто|title=( помощь ) - ^ Тамуз, Омер; Варди, Шай; Зиани, Джуба (25 апреля 2018 г.). «Неэксплуатируемые протоколы для многократного разрезания торта» . Материалы конференции AAAI по искусственному интеллекту . 32 (1). дои : 10.1609/aaai.v32i1.11472 . ISSN 2374-3468 .
- ^ Кресто, Элеонора; Таер, Диего (01 мая 2022 г.). «Ярмарка разрезания торта для подражателей» . Социальный выбор и благосостояние . 58 (4): 801–833. дои : 10.1007/s00355-021-01375-2 . ISSN 1432-217X . S2CID 244276548 .