Обсуждение: Теорема Гиббарда – Саттертуэйта.

Эта статья уровня 5 имеет рейтинг Start-class по шкале оценки контента Википедии . Она представляет интерес для следующих WikiProjects :

Экономика Высокая важность Эта статья находится в рамках WikiProject Economics , совместных усилий по улучшению освещения экономики в Википедии. Если вы хотите принять участие, посетите страницу проекта, где вы можете присоединиться к обсуждению и увидеть список открытых задач.Экономика Википедия:WikiProject Экономика Шаблон:WikiProject Экономика Экономика Высокий Данная статья имеет высокую степень важности по шкале важности проекта . Теория игр. Самое важное Эта статья является частью WikiProject Game theory , попытки улучшить, расширить и стандартизировать статьи Википедии, связанные с Game theory . Нам нужна ваша помощь! Присоединяйтесь | Исправьте красную ссылку | Добавьте контент | Выскажите свое мнениеТеория игр Википедия:WikiProject Теория игр Шаблон:WikiProject Теория игр Теория игр Вершина Данная статья получила оценку «Высшая важность» по шкале важности . Выборы и референдумы Эта статья находится в рамках проекта WikiProject Elections and Referendums , продолжающегося усилия по улучшению качества, расширению и созданию новых статей, касающихся выборов , избирательной реформы и других аспектов демократического принятия решений. Для получения дополнительной информации посетите страницу нашего проекта .Elections and ReferendumsWikipedia:WikiProject Elections and ReferendumsTemplate:WikiProject Elections and ReferendumsElections and Referendums

Ссылка или определение того, что означает «навязывание» в данном случае, были бы очень полезны.

Я адаптировал соответствующую часть статьи Эрроу о теореме невозможности, чтобы объяснить навязывание систем голосования. Возможно, это все еще не ясно. Хуже того, методы голосования обычно выбирают победителей, а не порядки предпочтений, но я не могу придумать подходящих слов. Надеюсь, вы или кто-то другой сделаете лучше. Тим Айворсон 11:10, 17 июля 2004 (UTC)

Я бы не охарактеризовал теорему Гиббарда-Саттертуэйта как вытекающую из теоремы Эрроу. Никакой очевидной связи, за исключением, возможно, техники комбинаторного анализа, в первоначальных доказательствах не наблюдается. А современный подход (ср. подход Неринга или Барбары к пространству функций или геометрический подход Саари) стремится доказать, что обе теоремы являются тривиальными следствиями гораздо более общих утверждений о допустимости scfs. Amcfreely 04:14, 4 августа 2005 (UTC) [ ответить ]

Неправильно. Теоремы Гиббарда-Саттертуэйта и Эрроу эквивалентны. Очень легко доказать одну из них, используя другую. Например, давайте рассмотрим, как доказать GS из Эрроу: Предположим, что теорема GS неверна. Тогда у вас есть неманипулируемая схема голосования, которая предоставляет вам только выигрышную альтернативу. Применяйте ее итеративно, каждый раз удаляя предыдущую выигрышную альтернативу из списка. В итоге вы получите полный линейный порядок альтернатив. Таким образом, вы получите механизм голосования, который дает вам полный порядок альтернатив. Теперь из теоремы Эрроу вы знаете, что этот механизм не является IIA, поэтому вы можете получить настройку, в которой избиратель i может изменить результат между a и b , играя с позицией альтернативы c . Теперь избавьтесь от всех других альтернатив, кроме a , b и c . Теперь избиратель i может изменить победителя ( a или b ), играя со своим отчетом о рейтинге, который он дает c . Следовательно, схема голосования является манипулируемой. Если это недостаточно формально для вас, сядьте с ручкой и бумагой и попробуйте написать пример. Я уверен, что вы справитесь. mousomer 5 августа 2005 г.

Если они эквивалентны, означает ли это, что закон Гиббарда-Саттертуэйта, как и закон Эрроу, не применяется к системам, которые предоставляют информацию, выходящую за рамки порядкового номера, например, к системам, которые запрашивают количественные ранги? -- Gwern (вклад) 23:55 13 сентября 2011 (GMT)

Теорема Гиббарда-Саттертуэйта, как она написана, касается отображения линейных порядков в линейные порядки. Результат справедлив и для слабых порядков, отображающихся в линейные порядки (равные результаты в бюллетенях ничего не меняют). Я кратко объяснил это в записи, но я думаю, что у нас должна быть ссылка на это. Я процитировал обзорную работу Тейлора, но если у кого-то есть ссылка на более старую статью, в которой это утверждается (в идеале впервые), пожалуйста, замените мою ссылку. Это почти создает впечатление, что Тейлор придумал эту идею, когда я ее написал.

Если кто-то хочет разобраться в этом, но не может начать, я с радостью предоставлю вам список ссылок из статьи Тейлора. Я просматриваю ее и ряд других источников, но это может занять некоторое время. CRGreathouse ( t | c ) 05:17, 28 августа 2006 (UTC) [ ответить ]

(Если похоже, что Тейлор придумал идею, как ее написал CRGreathouse, то, скорее всего, так и было; Тейлор с подозрением относится к тому, что слышит голоса и черпает все свои идеи прямо из мыслей других DJB). — Предыдущий неподписанный комментарий добавлен 4.35.92.11 (обсуждение) 19:31, 30 мая 2016 (UTC) [ ответить ]

Важно отметить, что теорема справедлива только для детерминированных систем. Это проще всего увидеть, если рассмотреть следующий известный недетерминированный контрпример («Случайный бюллетень»): каждый избиратель отмечает своего любимого кандидата в бюллетене, затем один из бюллетеней вытягивается наугад, чтобы определить победителя. Эта система не является диктаторской, все кандидаты могут победить, и всегда стратегически оптимально честно отметить своего любимого кандидата. Пользователь: heitzig-j 04 ноября 2008 г. — Предыдущий недатированный комментарий был добавлен в 03:28, 5 ноября 2008 г. (UTC). [ ответить ]

Упомянутый метод не восприимчив к тактическому голосованию в смысле теоремы: Если ваш бюллетень вытащен, лучше всего, когда на нем отмечен ваш истинный фаворит. Если он не вытащен, совершенно неважно, что на нем отмечено. Поэтому, независимо от того, какой бюллетень будет вытащен, для вас оптимально отметить вашего истинного фаворита. В терминах теории игр честное голосование всегда является строго доминирующей стратегией, и, следовательно, единственное равновесие Нэша — это когда все избиратели голосуют честно. Heitzig-j ( talk ) 18:07, 14 ноября 2008 (UTC) [ ответить ]

Я согласен и добавил неслучайность как квалификатор. В противном случае результат может быть интерпретирован слишком широко. -- Xeeron ( обсуждение ) 12:27, 2 марта 2010 (UTC) [ ответить ]

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

Джордж П.

ПРИМЕЧАНИЕ: Я не удалил слово «неслучайный» из статьи, но настоятельно рекомендую это сделать, поскольку, пока система не станет диктаторской, она все равно будет подвержена тактическому голосованию.

Однако мне бы хотелось достичь консенсуса по этому вопросу, прежде чем просто вносить изменения.

Возможно, редактирование могло бы упомянуть, что выбор одного бюллетеня наугад будет представлять собой «диктаторскую» систему. Однако любая система, которая включает выбор более двух бюллетеней наугад (до проведения детерминированного расчета для определения победителя), будет подчиняться результату теоремы.

Более того, я считаю, что часть «неслучайная» может быть примером «политически мотивированного абордажа» (см. мой более поздний комментарий), поскольку это предполагает, что STV не подпадает под теорему Эрроу (потому что STV имеет случайное перераспределение голосов в системе). STV не включен в бюллетень на референдуме в Великобритании, но это предпочтительная система большинства политиков-либералов-демократов, и дебаты по AV будут использоваться в качестве платформы для того, чтобы попросить избирателей дать им мандат на STV.

Однако система STV, как и все недиктаторские избирательные системы, по-прежнему подвержена тактическому голосованию (на самом деле она в большей степени подвержена тактическому голосованию из-за необходимости предотвращения «эрозии» в процессе перераспределения). Отсюда и плакаты на ирландских выборах, призывающие сторонников основных партий в разных областях одного и того же «избирательного округа» голосовать за разных кандидатов).

Однако это свидетельствует о настоятельной необходимости заморозить эту статью до мая 2011 года, поскольку в противном случае она, скорее всего, превратится в минное поле для политических подсчетов очков и «ослепления наукой».

Джордж П.

Также: Могу ли я предложить заморозить или строго контролировать эту статью на период до 5 мая 2011 года? Обоснование: Она будет подвергнута политически мотивированному «заключению» в преддверии референдума по альтернативному голосованию в Соединенном Королевстве (в мае следующего года).

- Сторонники AV захотят показать, что AV - это «нетактическая» система голосования, поэтому они могут попытаться сделать эту статью непонятной или добавить в нее раздел, пытаясь убедить людей голосовать за AV.

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

Джордж П — Предыдущий неподписанный комментарий добавлен 144.82.84.88 (обсуждение) 14:22, 15 ноября 2010 (UTC) [ ответить ]

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

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

Это также зависит от того, что я бы назвал «тактическими» соображениями, но это не математически детерминированное или вероятностное, а подразумевает непрерывную серию человеческих суждений в сознании каждого кардинала. Это не было бы признано «системой голосования» псефологом.

Слово «диктаторский», похоже, имеет определенное, техническое значение в этом контексте, с которым я не знаком. Может ли кто-то знающий вставить его в статью? - Toptomcat ( обсуждение ) 07:45, 8 ноября 2008 (UTC) [ ответить ]

Я предоставил ссылку на теорему Эрроу. Kiefer.Wolfowitz ( обсуждение ) 13:10, 21 февраля 2010 (UTC) [ ответ ]

Могу ли я предложить заморозить или строго контролировать эту статью на период до 5 мая 2011 года? Обоснование: она будет подвергнута политически мотивированному «заключению» в преддверии референдума по альтернативному голосованию в Соединенном Королевстве (в мае следующего года).

- Сторонники AV захотят показать, что AV - это «нетактическая» система голосования, поэтому они могут попытаться сделать эту статью непонятной или добавить в нее раздел, пытаясь убедить людей голосовать за AV.

-Тем временем сторонники FPTP могут попытаться использовать его для высказывания резких политических тезисов, которые, обоснованные или нет, будут умалять энциклопедическую природу статьи, которая, когда она была написана, была написана в духе математической честности. —Предыдущий неподписанный комментарий добавлен 144.82.84.88 (обсуждение • вклад )

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

Аксиома: Любой порядок альтернатив является допустимым голосованием. (Универсальный домен)

Аксиома: Должна быть выбрана одна из альтернатив. (Основная Директива)

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

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

2. Существует по крайней мере один набор голосов, такой, что включение дополнительного кандидата в число голосов каждого может привести к тому, что проигравший вариант станет победителем.

Доказательство: Предположим, что номинантами являются {x,y,z}. Предположим, что около трети избирателей голосуют за "x вместо y вместо z", около трети голосуют за "y вместо z вместо x", а остальные голосуют за "z вместо x вместо y". Без потери общности предположим, что x является победителем. (Мы могли бы поменять метки альтернатив, если необходимо, чтобы сделать "x" меткой победителя.) Предположим, что y, проигравшая альтернатива, удаляется из каждого голосования. Остаются только две альтернативы, поэтому применяется правило большинства, и поскольку около 2/3 голосуют за z вместо x, выбор из {x,z} — z. Это доказывает первую часть теоремы. Теперь восстановите y в голосах; это меняет победителя обратно с z на x, что доказывает вторую часть теоремы.

Значимость: Когда многие избиратели не обладают стратегическим опытом или испытывают трудности с координацией своих стратегий голосования с другими избирателями (например, с согласованием с другими избирателями того, за какой компромисс голосовать или какой рейтинг поставить на первое место), результатом часто можно манипулировать на этапе выдвижения кандидатур путем добавления или удаления альтернатив. Это поднимает важные вопросы: как и кем выдвигаются кандидаты, и какой (недиктаторский, ненавязывающий, обычно детерминированный) метод голосования наименее подвержен манипуляциям со стороны стратегического выдвижения кандидатур? (Подсказка: взгляните на метод голосования «Максимизировать подтвержденное большинство», который находит порядок финиша, который минимизирует размер наибольшего неподтвержденного большинства в смысле minlexmax. Определение: большинство, которое поставило x выше y, называется «утвержденным», если порядок финиша ставит x выше y.)

Пример 1: Из-за проблемы порчи при правиле относительного большинства многие потенциальные кандидаты решают не баллотироваться, и каждая партия выдвигает не более одного кандидата на должность. Этот вид манипуляции не обязательно более вреден для общества, чем выдвижение большего количества альтернатив (при правиле относительного большинства), но отсутствие конкуренции может вызвать много проблем: лучшие кандидаты могут не быть выдвинуты; партии (и их сторонники) пожалеют о своем выборе кандидата, если негативная информация о нем/ней появится до дня выборов; избиратели должны принять нежелательную политику кандидата вместе с желаемой; вопросы не решаются, поскольку небольшое колебание голосов может вызвать множество крупных изменений политики; подотчетность подрывается, поскольку меньшинства «по одному вопросу» могут объединиться, чтобы сформировать победную коалицию большинства; и подотчетность по большинству вопросов подрывается, поскольку большинство вопросов (например, взятки коррумпированного правительства богатым особым интересам) не имеют первостепенного значения для избирателей и, таким образом, не влияют на выборы.

Пример 2: (Вопиюще большая проблема с методом голосования Борда) Предположим, что 66% избирателей предпочитают X вместо Y. При использовании большинства методов голосования X с большим отрывом победит Y. Однако во многих контекстах легко найти дополнительную альтернативу Y2, которая очень похожа на Y, поэтому меньшинство, которое предпочитает Y вместо X, также предпочтет Y2 вместо X, а также немного хуже Y, так что почти все избиратели предпочтут Y вместо Y2. Учитывая метод Борда, Y победит, если также будет номинирован худший клон (предполагая искренние предпочтения избирателей): X получит 2 очка от 66% и ноль очков от 34%, в то время как Y получит 2 очка от 34% плюс 1 очко от 66%. Чем больше будет номинировано худших клонов, тем больше будет перевес, который можно будет преодолеть. Если мы предположим, что несколько сторонников X также стратегически продвинуты, то также будут номинированы худшие клоны X. (Соус для гуся — соус для гусака.) Это означает, что публичные выборы превратятся в фарс, если использовать метод Борда.

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

(Примечание 2: Методы голосования, которые не принимают порядки предпочтений от избирателей, такие как голосование по одобрению или голосование по диапазону, также могут быть показаны как манипулируемые стратегическим выдвижением кандидатур, учитывая разумные предположения о том, как голосуют избиратели. Для одобрения предположим, что значительное количество избирателей одобрят своего наиболее предпочтительного кандидата и не одобрят своего наименее предпочтительного кандидата. Для голосования по диапазону предположим, что значительное количество избирателей проголосуют за своего наиболее предпочтительного кандидата с максимальным баллом и за своего наименее предпочтительного кандидата с минимальным баллом. Эти предположения разумны, потому что эти стратегии оптимальны — другие стратегии тратят по крайней мере часть веса голоса — и они очевидны или легки для изучения, например, стратегия не тратить свой голос на кандидата, у которого, по-видимому, нет шансов на победу, очевидна при использовании метода «голосуй за одного; правило большинства». Обратите внимание, что если все избиратели голосуют за оптимальную стратегию, когда есть только два кандидата, то одобрение, голосование по диапазону и большинство других методов сводятся к правилу большинства, когда есть только два (Номинанты, и если большинство избирателей голосуют за оптимальную стратегию, то небольшое изменение доказательства показывает, что Одобрение, Голосование по диапазону и многие другие методы также поддаются манипуляции посредством стратегического выдвижения. Кроме того, даже если делаются различные предположения о поведении избирателей, все равно может быть легко продемонстрировать стратегическое выдвижение.)

(Примечание 3: теорема, подобная теореме Эрроу, тоже может быть подогнана под эту структуру, что неудивительно. Например, независимость нерелевантных альтернатив становится последовательностью выбора: если x выбран, а y не выбран, когда набор кандидатов — это {x,y}, то y не должен быть выбран ни из одного набора кандидатов, содержащего x. Для полноты картины приведем более простую, но мощную теорему Эрроу: каждый метод голосования, который всегда выбирает по крайней мере одного победителя, удовлетворяет универсальному домену и сводится к правилу большинства, когда ранжируются только две альтернативы, не соответствует последовательности выбора.) SEppley ( talk ) 22:53, 27 августа 2011 (UTC) [ ответить ]

В статье говорится, что теорема Эрроу похожа на теорему Гиббарда-Саттертуэйта, за исключением того, что она относится к функциям социального упорядочения вместо функций социального выбора. Это не единственное отличие, и, по моему мнению, это не самое существенное отличие, поскольку теорему Эрроу можно переписать для функций социального выбора (как это сделали многие авторы). SEppley ( talk ) 01:49, 28 августа 2011 (UTC) [ reply ]

Сен и другие считали, что это важное различие. Пожалуйста, улучшите статью, используя высококачественные ссылки, такие как надежный источник, объясняющий вашу точку зрения. Кифер . Вулфовиц 12:30, 28 августа 2011 (UTC) [ ответить ] 

@SEppley у вас есть ссылка на этих авторов? – Maximum Limelihood Estimator 20:26, 21 апреля 2024 (UTC) [ ответить ]

По крайней мере. То же самое можно сказать о психозе (шизофрении, иррациональности): психотический избиратель не будет голосовать в соответствии со своими предпочтениями, даже если следование собственным (? ...) предпочтениям ведет к его собственному благополучию, а обратное — нет (безумие). DJB — Предыдущий неподписанный комментарий добавлен 4.35.92.11 (обсуждение) 19:26, 30 мая 2016 (UTC) [ ответить ]

Статья Уоррена Д. Смита 2006 года не утверждает, что кардинальное голосование является стратегически защищенным, а только то, что существуют кардинальные методы со свойством, что если избиратель предпочитает кандидата A кандидату B, то этот избиратель никогда не оценит B выше, чем AI, то есть рейтинг, выведенный из рейтингового бюллетеня, никогда не должен противоречить честному рейтингу избирателя. Сравните это с критерием предательства фаворита , который гласит, что первый предпочтительный (в стиле большинства) бюллетень, выведенный из ранжированного бюллетеня, никогда не должен противоречить честной оценке избирателем его или ее фаворита.

Ранжированные методы, соответствующие критерию предательства фаворита, не обязательно являются стратегически защищенными, поэтому ранжированные методы, соответствующие ранжированию, также не следует считать таковыми.

По какой-то причине Брамс и Фишберн называют голосование, согласованное с рейтингом, «искренним» голосованием, а Уоррен Д. Смит называет его «честным» голосованием. Но этот точный термин отличается от иммунитета стратегии. Wotwotwoot ( talk ) 17:16, 16 февраля 2024 (UTC) [ ответить ]

Вы совершенно правы относительно принципа откровения.

Я думаю, что моя правка была неясной, хотя — я не хотел утверждать, что кардинальные системы голосования абсолютно честны или защищены от стратегий. Вместо этого смысл был в том, чтобы указать, что за пределами класса систем голосования с ранжированным выбором существуют механизмы , которые гарантируют честность (например, механизм Викри–Кларка–Гроувза ). Закрытые кривые Limelike ( обсуждение ) 04:01, 17 февраля 2024 (UTC) [ ответить ]

Статья не слишком сложная, но в целом ее трудно полностью понять. Она предполагает, что читатели знакомы с такими терминами, как «прямолинейный» и «доминантная стратегия». Хотя есть ссылка на конкретную страницу, которая определяет эти термины, эта страница также довольно сложна и больше сосредоточена на общем определении, чем на этом конкретном случае.

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

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

Более того, те же самые проблемы также появляются в статье о теореме Даггана-Шварца. Я должен был бы рассмотреть их там, но эта страница, похоже, в значительной степени игнорируется. Wikikeyer (обсуждение) 17:41, 31 августа 2024 (UTC) [ ответить ]

Согласен на 100%! Я очень занят на этом фронте, но, кажется, я начал составлять черновик переделки либо в draftspace, либо в моем namespace, на который вы можете с удовольствием взглянуть. – Закрыто Limelike Curves ( обсуждение ) 22:04, 1 сентября 2024 (UTC) [ ответить ]