Правило медианного голосования

Правило медианного голосования или медианный механизм — это правило группового принятия решений в одномерной области. Каждый человек голосует, записывая свое идеальное значение, и правило выбирает одно значение, которое (в базовом механизме) является медианой всех голосов.

Мотивация

Многие сценарии группового принятия решений включают одномерную область. Некоторые примеры:

Члены городского совета должны определить общий размер годового городского бюджета.
Несколько человек, работающих в одном офисе, должны определить температуру кондиционирования воздуха.
Родители школьников должны решить, какой продолжительностью должны быть ежегодные школьные каникулы.
Общественность должна решить, где разместить объект на одномерной улице.

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

Простой способ принятия решения — правило среднего голосования : спросите каждого участника, каков его пик, и возьмите среднее значение всех пиков. Но этим правилом легко манипулировать. Например, предположим, что пик Алисы равен 30, пик Джорджа — 40 и пик Ханы — 50. Если все избиратели сообщат о своих истинных пиках, фактическая сумма будет 40. Но Алиса может манипулировать и говорить, что ее пик на самом деле равен 0; тогда среднее значение будет 30, что является фактическим пиком Алисы. Таким образом, Алиса выиграла от манипуляции. Аналогичным образом, любой агент, чей пик отличается от результата, имеет стимул манипулировать ложным пиком и сообщать о нем.

Напротив, правило медианы определяет фактический бюджет на основе медианы всех голосов. Это простое изменение делает правило неэффективным для стратегии : ни один избиратель не сможет выиграть, сообщив о ложном пике. В приведенном выше примере медиана равна 40, и она остается равной 40, даже если Алиса сообщает 0. Фактически, поскольку истинный пик Алисы находится ниже медианы, никакой ложный отчет Алисы потенциально не может уменьшить медиану; Алиса может только увеличить медиану, но это ухудшит ее положение.

Предварительные условия

Правило медианного голосования справедливо в любых условиях, когда агенты имеют одномаксимальные предпочтения . , что существует некоторый линейный порядок альтернатив, такой, что для каждого агента i с пиком pi _{Это означает} :

Если p _i > a > b , то агент i предпочитает a b;
Если b > a > p _i , то агент i предпочитает a перед b.

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

Обратите внимание, что однопиковость не подразумевает какой-либо конкретной меры расстояния между альтернативами и не подразумевает ничего об альтернативах, находящихся по разные стороны от пика. В частности, если a > p _i > b, то агент может предпочесть либо a b, либо b a.

Процедура

агенту i в 1,..., n предлагается сообщить значение pi _.Каждому Значения сортируются в порядке возрастания p ₁ ≤ ... ≤ p _n . В базовом механизме выбранное значение, когда n нечетно, равно p _(n+1)/2 , что равно медиане значений (когда n четно, выбранное значение равно p _n/2 ):

выбор = медиана( p ₁ , ..., p _n ).

Доказательство устойчивости стратегии

Вот доказательство того, что медианное правило не является стратегическим:

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

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

Обобщенные медианные правила

Медиана с фантомами

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

Например, предположим, что голоса составляют 30, 40 и 50. Без фантомов правило медианы выбирает 40. Если мы добавим два фантома в точке 0, тогда правило медианы выберет 30; если мы добавим два фантома в 100, правило медианы выберет 50; если мы добавим медианы 20 и 35, правило медианы выберет 35.

Вот несколько особых случаев правил фантомной медианы, предполагающих, что все голоса находятся в диапазоне от 0 до 100:

Если в 0 имеется n -1 фантомов, то правило медианы возвращает минимум всех реальных голосов.
Если в 100 есть n -1 фантомов, то правило медианы возвращает максимум всех реальных голосов.
Если в точке 50 имеется n -1 фантомов, то правило медианы возвращает 50, если некоторые идеальные точки выше, а некоторые ниже 50; в противном случае он возвращает голос, наиболее близкий к 50.

Мулен ^[1] доказал следующие характеристики:

Правило является анонимным , устойчивым к стратегии и эффективным по Парето для всех однопиковых предпочтений, если оно эквивалентно медианному правилу с не более чем n -1 фантомами.
Правило является анонимным и устойчивым к стратегии для всех однопиковых предпочтений, если оно эквивалентно медианному правилу с не более чем n +1 фантомами.
Правило является неуязвимым для всех однопиковых предпочтений тогда и только тогда, когда оно эквивалентно правилу минимакса следующей формы. Есть 2 ^н параметры, b _S для любого подмножества S избирателей. Правило возвращает минимум по всем подмножествам S и максимум (все пики избирателей в S и b _S ). ^{[ нужны разъяснения ]}

Дополнительные характеристики

Характеристики Мулена учитывают только правила, которые являются «только пиками», то есть правило зависит только от n пиков. Чинг ^[2] доказал, что все правила, которые являются стратегически устойчивыми и непрерывными , даже если они не являются «только пиковыми», являются дополненными медианными правилами, то есть могут быть описаны вариантом медианного правила с некоторыми 2 ^н параметры.

Характеристики Мулена требуют, чтобы правила обрабатывали все однопиковые предпочтения. Несколько других работ допускают правила, которые обрабатывают только подмножество однопиковых предпочтений:

Берга и Сэридзава ^[3]^{: Раздел 3} разрешить правилам обрабатывать только минимально богатые предпочтения. Они доказывают, что даже в этой меньшей области правила, устойчивые к стратегии, являются в точности обобщенными медианными правилами.
Массо и Морено ^[4] разрешить правила, которые обрабатывают только симметричные однопиковые предпочтения (симметрия означает, что результат, находящийся дальше от пика, должен быть менее предпочтительным, чем результат, расположенный ближе к пику, даже если результаты находятся по разные стороны от пика). Класс механизмов, устойчивых к стратегии, в этой меньшей области строго больше, чем класс обобщенных медианных правил. В частности, правила могут нарушаться из-за точек разрыва. Их результат позволяет разрабатывать правила, учитывающие ограничения осуществимости.
Граница и Иордания ^[5]^{: Разделы 3,4,5} разрешить правила, обрабатывающие только квадратичные предпочтения. В одномерной ситуации это эквивалентно функциям полезности вида $u_{i}(x)=-|x-p_{i}|$ . В этой области они доказывают, что любое неуязвимое для стратегии правило, соблюдающее критерий единогласия, является бескомпромиссным , то есть: если пик агента находится справа от результата, и он перемещает свой пик дальше вправо, то результат не меняется; и аналогично слева. И наоборот, каждое бескомпромиссное правило является стратегией. Они доказывают, что правило бескомпромиссно, если оно имеет не более 2 ^н фантомные избиратели (то есть не более 2 ^н точки, которые могут быть избраны, даже если они не являются пиком какого-либо избирателя), и его соответствие избранным (сопоставление каждого профиля с набором индексов реальных + фантомных избирателей, чей пик избран) имеет замкнутый график . Как следствие, каждое бескомпромиссное правило непрерывно. Однако бескомпромиссное правило, которое также является дифференцируемым, должно быть диктаторским.

Граница и Иордания ^[5]^{: Разделы 6,7} обобщить понятия однопиковых предпочтений и медианных правил голосования на многомерные условия. Они рассматривают три класса предпочтений: сепарабельные ( $u_{i}(x)=\sum _{j=1}^{m}u_{i,j}(x_{j})$ , где каждое v _i,j представляет собой однопиковую функцию полезности); квадратичный ( $u_{i}(x)=-(x-p)^{T}A(x-p)$ где A — симметричная положительно определенная матрица ); и их пересечение сепарабельного квадратичного уравнения ( $u_{i}(x)=-\sum _{j=1}^{m}a_{i,j}\cdot (x_{j}-p_{j})^{2}$ , где a _i,j — положительные константы). В квадратичных несепарабельных областях единственными устойчивыми к стратегии механизмами являются диктаторские. Но в разделимых областях существуют многомерные механизмы защиты от стратегии, состоящие из одномерных механизмов защиты от стратегии, по одному на каждую координату.

Берга и Сэридзава ^[3]^{: Раздел 4} ищите правила, которые одновременно неуязвимы для стратегии и удовлетворяют условию, которое они называют «отсутствие права вето»: ни один человек не должен иметь возможность избежать какой-либо альтернативы, которая станет результатом, заявив о некоторых предпочтениях. Они характеризуют обобщенные медианные правила как единственные правила, устойчивые к стратегии, в «минимально богатых областях». Они доказали, что единственная максимальная область, включающая в себя минимально богатую область, которая допускает существование правил, устойчивых к стратегии, удовлетворяющих условию «отсутствия права вето», является областью выпуклых предпочтений .

Барбера, Гюль и Стакетти ^[6] также обобщить понятия однопиковых предпочтений и медианных правил голосования на многомерные условия.

Барбера и Джексон ^[7] охарактеризовал устойчивые к стратегии правила для слабо однопиковых предпочтений, в которых максимальный набор может содержать две альтернативы.

Мулен охарактеризовал устойчивые к стратегии правила с одним плато для предпочтений — обобщение однопиковых предпочтений, в которых каждому агенту разрешено иметь целый интервал идеальных точек. ^[8]

Применение в нефтяной промышленности

В 1954 году Иранский нефтяной консорциум принял правило, подобное медиане, для определения общего годового объема добычи нефти в Иране. Ежегодно роль каждой компании-члена оценивалась по ее фиксированной доле в общем объеме производства. Выбранный результат x представлял собой самый высокий уровень, при котором сумма долей участников, голосовавших за уровни выше x, составляла не менее 70%. ^[9]^: 103-108

Связанные понятия

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

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

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

Даммет и Фаркухарсон представляют собой достаточное условие стабильности в играх с голосованием. ^[10]^{[ нужны дальнейшие объяснения ]}

Ссылки

^ Мулен, Х. (1980). «О стратегической устойчивости и однопиковости». Общественный выбор . 35 (4): 437–455. дои : 10.1007/BF00128122 . S2CID 154508892 .
^ Чинг, Стивен (декабрь 1997 г.). «Стратегическая устойчивость и медианные избиратели ». Международный журнал теории игр . 26 (4): 473–490. дои : 10.1007/BF01813886 . hdl : 10722/177668 . S2CID 42830689 .
^ Перейти обратно: ^а ^б Берга, Долорс; Сэридзава, Сигэхиро (январь 2000 г.). «Максимальная область действия правил, устойчивых к стратегии, с одним общественным благом». Журнал экономической теории . 90 (1): 39–61. дои : 10.1006/jeth.1999.2579 .
^ Массо, Хорди; Морено де Барреда, Инес (июнь 2011 г.). «О стратегической устойчивости и симметричной одновершинности». Игры и экономическое поведение . 72 (2): 467–484. дои : 10.1016/j.geb.2010.12.001 . hdl : 2072/53376 .
^ Перейти обратно: ^а ^б Бордер, Ким С.; Джордан, Дж. С. (январь 1983 г.). «Прямые выборы, единогласие и фантомные избиратели» . Обзор экономических исследований . 50 (1): 153. дои : 10.2307/2296962 . JSTOR 2296962 .
^ Барбера, Сальвадор; Гюль, Фарук; Стаккетти, Эннио (декабрь 1993 г.). «Обобщенные медианные схемы и комитеты избирателей». Журнал экономической теории . 61 (2): 262–289. дои : 10.1006/jeth.1993.1069 .
^ Барбера, Сальвадор; Джексон, Мэтью (июль 1994 г.). «Характеристика устойчивых к стратегии функций социального выбора для экономик с чистыми общественными благами» (PDF) . Социальный выбор и благосостояние . 11 (3). дои : 10.1007/BF00193809 .
^ Мулен, Х. (август 1984 г.). «Обобщенные победители Кондорсе для предпочтений с одним пиком и одним плато». Социальный выбор и благосостояние . 1 (2): 127–147. дои : 10.1007/BF00452885 .
^ Блэр, Джон М. (1976). Контроль над нефтью . дои : 10.1007/978-1-349-81487-9 . ISBN 978-1-349-81489-3 .
^ Даммет, Майкл; Фаркухарсон, Робин (1961). «Стабильность в голосовании». Эконометрика . 29 (1): 33–43. дои : 10.2307/1907685 . JSTOR 1907685 .

[1] Мулен, Х. (1980). «О стратегической устойчивости и однопиковости». Общественный выбор . 35 (4): 437–455. дои : 10.1007/BF00128122 . S2CID 154508892 .

[2] Чинг, Стивен (декабрь 1997 г.). «Стратегическая устойчивость и медианные избиратели ». Международный журнал теории игр . 26 (4): 473–490. дои : 10.1007/BF01813886 . hdl : 10722/177668 . S2CID 42830689 .

[:1-3] Перейти обратно: ^а ^б Берга, Долорс; Сэридзава, Сигэхиро (январь 2000 г.). «Максимальная область действия правил, устойчивых к стратегии, с одним общественным благом». Журнал экономической теории . 90 (1): 39–61. дои : 10.1006/jeth.1999.2579 .

[4] Массо, Хорди; Морено де Барреда, Инес (июнь 2011 г.). «О стратегической устойчивости и симметричной одновершинности». Игры и экономическое поведение . 72 (2): 467–484. дои : 10.1016/j.geb.2010.12.001 . hdl : 2072/53376 .

[:0-5] Перейти обратно: ^а ^б Бордер, Ким С.; Джордан, Дж. С. (январь 1983 г.). «Прямые выборы, единогласие и фантомные избиратели» . Обзор экономических исследований . 50 (1): 153. дои : 10.2307/2296962 . JSTOR 2296962 .

[6] Барбера, Сальвадор; Гюль, Фарук; Стаккетти, Эннио (декабрь 1993 г.). «Обобщенные медианные схемы и комитеты избирателей». Журнал экономической теории . 61 (2): 262–289. дои : 10.1006/jeth.1993.1069 .

[7] Барбера, Сальвадор; Джексон, Мэтью (июль 1994 г.). «Характеристика устойчивых к стратегии функций социального выбора для экономик с чистыми общественными благами» (PDF) . Социальный выбор и благосостояние . 11 (3). дои : 10.1007/BF00193809 .

[8] Мулен, Х. (август 1984 г.). «Обобщенные победители Кондорсе для предпочтений с одним пиком и одним плато». Социальный выбор и благосостояние . 1 (2): 127–147. дои : 10.1007/BF00452885 .

[9] Блэр, Джон М. (1976). Контроль над нефтью . дои : 10.1007/978-1-349-81487-9 . ISBN 978-1-349-81489-3 .

[10] Даммет, Майкл; Фаркухарсон, Робин (1961). «Стабильность в голосовании». Эконометрика . 29 (1): 33–43. дои : 10.2307/1907685 . JSTOR 1907685 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]