Везде
Aggregation of voting designs
Table of contents
Annotation Estimate Publication content
References Comments
Share
QR
Metrics
Aggregation of voting designs
Annotation
PII
S042473880010524-5-1
DOI
10.31857/S042473880010524-5
Publication type
Article
Status
Published
Authors
Vladimir Danilov 
Occupation: Principal Scientific Researcher
Affiliation: Central Economics and Matthematics Institute, Russian Academy of Sciences
Address: Moscow, Russian Federation
Aleksandr Karzanov
Occupation: Chief scientific researcher
Affiliation: Central Economics and Mathematics Institute, Russian Academy of Sciences
Address: Russia
Gleb Koshevoy
Affiliation: Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute)
Address: Russia
Edition
Volume 56 Issue 3
Pages
103-112
Abstract

A Condorcet domain (a domain of linear orders where the majority rule does not violate the transitivity) can be considered as a ground (or design) of organizing a voting procedure. In the present paper we make a next step, namely, we discuss an organization of choices among designs. Here we restrict ourselves by considering those Condorcet domains that are produced with the help of rhombus tilings. Our main result asserts that the majority rule correctly aggregates designs which are produced by use of cubillages, which are three-dimensional generalizations of rhombus tilings. More precisely, to every cubillage  we associate a superdomain  of designs and give an aggregation rule  on this superdomain. We show that the resulting aggregated tiling (design) always belongs to the same superdomain. Also we show that such rules  are agreeable within the intersection of superdomains.

Keywords
rhombus tiling, Condorcet domain, median, cubillage, zonotope, majority rule.
Acknowledgment
This study was supported by the Russian Foundation for Basic Research (project 20-010-00569-А).
Received
02.09.2020
Date of publication
04.09.2020
Number of purchasers
27
Views
1562
Readers community rating
0.0 (0 votes)
Cite   Download pdf
1 1. ВВЕДЕНИЕ
2 В работах (Данилов, Карзанов, Кошевой, 2010б; Danilov, Koshevoy, 2013) мы изучали, как строить максимальные области Кондорсе с помощью ромбических тайлингов (двумерных кубильяжей). Здесь мы хотим проделать аналогичную работу с трехмерными кубильяжами, которые порождают похожие области, но уже не для агрегирования линейных порядков, а для областей Кондорсе. Дело в том, что выбор области Кондорсе — это фактически выбор дизайна для проведения выборов. И какой дизайн выбрать — это задача для агрегирования.
3 Задача агрегирования индивидуальных мнений в общем и часто неформальном виде всегда стояла и решалась разными средствами, начиная от кулачных споров и кончая утонченными процедурами голосования. В случае бинарного выбора задача решается правилом простого большинства или его модификацией, типа взвешенного большинства или системы большинств Монжарде. Однако в случае большего числа альтернатив положение усложняется. Рассмотрим задачу агрегирования линейных порядков на множестве альтернатив X , т.е. задачу определения по индивидуальным линейным порядкам избирателей группового, агрегированного линейного порядка. Естественно предполагать, что при агрегировании должна учитываться структурированность линейных порядков. То есть множество LO(X) линейных порядков — это не просто множество, а множество, несущее несколько интересных структур (подробнее об этом в разд. 2).
4 Неявно учет этих структур был инициирован Раймоном Луллом (1299 г.), а в более явной форме маркизом де Кондорсе (1785 г.). Они предлагали строить агрегированный порядок с помощью агрегирования бинарных задач, относящихся к сравнению всех пар альтернатив a и b . Недостаток этого метода, обнаруженный самим Кондорсе (так называемый парадокс Кондорсе), состоял в том, что построенные таким способом агрегированные попарные бинарные отношения (типа a<b ) могли оказаться (и часто оказывались) нетранзитивными и тем самым не давали никакого группового линейного порядка.
5 Один из выходов из этого парадокса состоит в том, чтобы допускать к рассмотрению не любые линейные порядки, а только некоторые (обычно связанные с дополнительной структурой на множестве альтернатив X . В таких ограниченных областях правило простого большинства может работать вполне прилично. В этом случае говорят об областях Кондорсе.
6 Первый интересный пример такой области предложил Д. Блэк (Black, 1948). Область состоит из так называемых однопиковых предпочтений и впоследствии стала предметом изучений разными авторами (см., например, (Fishburn, 1997; Monjardet, 2009; Puppe, 2018)). В работе (Данилов, Карзанов, Кошевой, 2010б) мы предложили использовать ромбические тайлинги для построения большого числа областей Кондорсе, где область однопиковых предпочтений является лишь простейшим частным случаем.
7 В данной работе мы делаем следующий шаг и рассматриваем задачу агрегирования уже самих областей Кондорсе. Область Кондорсе D можно понимать как способ организации выборов (дизайна выборов). А именно потребуем, чтобы (при отсутствии в этой области своих истиных предпочтений) избиратели называли линейные порядки из этой области D. Затем по правилу большинства заявленные ими порядки агрегируются в групповой порядок. Конечно, это открывает возможности для манипулирования и стратегического поведения. И тем не менее такой способ дизайна выборов представляет интерес. Поэтому мы обсуждаем далее задачу агрегирования таких дизайнов. Избиратели (быть может, совсем другие) выражают свое отношение-предпочтение к тем или иным дизайнам выборов; задача следующего уровня — сделать выбор из этих дизайнов, т.е. агрегирование дизайнов.
8 Далее мы ограничиваемся агрегированием тайлинговых дизайнов, т.е. фактически агрегированием ромбических тайлингов. Они, как и линейные порядки, задаются некоторыми бинарными данными (инверсиями). Это позволяет агрегировать данные с помощью правила простого большинства. Однако, как и в случае линейных порядков, агрегированные данные могут не соответствовать никакому тайлингу. Поэтому здесь снова нужно ограничивать область допустимых тайлингов (такие ограниченные множества тайлингов называются суперобластями). Большие суперобласти ромбических тайлингов можно строить с помощью трехмерных кубических тайлингов. Оказывается, что для таких кубильяжных суперобластей агрегирование дизайнов-тайлингов с помощью правила большинства снова дает тайлинг.
9 2. ЛИНЕЙНЫЕ ПОРЯДКИ И ОБЛАСТИ КОНДОРСЕ
10 Мы предполагаем, что предпочтения избирателей описываются линейными порядками. Линейный порядок — это полное асимметричное транзитивное отношение. Зафиксируем некоторое конечное множество альтернатив (кандидатов) X . Удобно считать, что X=[n]={1,...,n}  — это множество первых n положительных натуральных чисел. Типичная альтернатива обозначается как i , j , ... . На этом множестве имеются два выделенных линейных порядка: α=(1<2<...<n) и ω=(n<n-1<...<2<1) . Множество всех линейных порядков на [n] обозначается LO=LOn , типичный порядок — с помощью σ или <σ . Множество LO имеет несколько интересных для дальнейшего структур, о которых мы кратко напомним1.
1. Подробно с этим можно ознакомиться в (Danilov, Koshevoy, 2013).
11 Первая, самая простая структура, — это инволюция. Для каждого линейного порядка σ можно образовать противоположный линейный порядок σ∘ . Например, α и ω противоположны друг другу.
12 Вторая — это бинарная форма линейного порядка на [n] . Обозначим через Ω множество пар (i,j) элементов в [n] , таких что i<j . Пара (i,j) из Ω называется инверсией линейного порядка σ=<σ , если j<σi . Множество всех инверсий порядка σ обозначается как Inv(σ) ; это некоторое подмножество в Ω , которое однозначно определяет исходный порядок σ . Например, Inv(α)=∅ , Inv(ω)=Ω , и вообще Inv(σ∘)=Ω-Inv(σ) . Так что бинарная форма хорошо согласована с инволюцией.
13 Бинарная форма (или бинарное представление) образует набор бинарных данных, которыми кодируется порядок и которые можно агрегировать с помощью правила простого большинства. Пусть имеется множество N избирателей. Каждый избиратель a∈N имеет свое предпочтение относительно альтернатив из [n] , выраженное линейным порядком σa∈LO . Спрашивается, как агрегировать эти индивидуальные порядки в один групповой порядок σ ? Правило простого большинства, предложенное Кондорсе, фактически сводится к следующему. Для каждого избирателя его предпочтение σa переводится сначала в бинарную форму Inv(σa)⊂Ω , а затем эти формы-подмножества агрегируются. Удобно представить эти подмножества их характеристическими функциями, т.е. ввести функции νa:Ω→{0,1} , которые равны 1 на подмножестве Inv(σa) и 0 — на его дополнении. После этого мы суммируем все функции, образуя функцию ν=∑a∈N‍νa . Такая функция дает мультиподмножество в Ω. Наконец, мы образуем подмножество Inv=(i,j)∈Ω, ν(i,j)>|N|/2. (Здесь и далее мы неявно предполагаем, что число избирателей |N| нечетно. Это делается исключительно для простоты изложения.) И если это подмножество Inv (агрегат бинарных данных) является множеством инверсий некоторого линейного порядка σ (т.е. Inv=Inv(σ) ), то σ считается групповым, агрегированным порядком. Но, как обнаружил Кондорсе, так получается далеко не всегда.
14 Возникает вопрос, какие бинарные данные (т.е. какое подмножество Υ в Ω ) соответствуют линейным порядкам (т.е. имеет вид Inv(σ) для некоторого σ∈LO ). Для этого необходимо, чтобы Υ было транзитивным (если (i,j)∈Υ и (j,k)∈Υ , то (i,k)∈Υ ), как и его дополнение в Ω (последнее свойство называется котранзитивностью). Оказывается, что эти два свойства — транзитивность и котранзитивность — достаточны, для того чтобы множество Υ представлялось как множество инверсий некоторого линейного порядка. При агрегировании бинарных данных оба свойства могут нарушаться, что и приводит к парадоксу Кондорсе.
15 Использование бинарной формы (инверсий) позволяет определить на множестве LO структуру частичного порядка (так называемый слабый порядок Брюа). А именно пишем σ«τ, если Inv(σ)⊂Inv(τ) . Впрочем этот порядок далее почти не используется. Более важным оказывается отношение совместимости (компатибельности), введенное в (Chameni-Nembua, 1989).
16 Определение. Дла линейных порядка σ и τ называются совместимыми (обозначаем σ≈τ ), если подмножество Inv(σ)∪Inv(τ) транзитивно, а Inv(σ)∩Inv(τ) котранзитивно.
17 Это дает еще одну структуру на множестве LO — структуру симметричного рефлексивного отношения ≈ . Тем самым множество LO становится множеством вершин (неориентированного) графа (LO,≈) . Заметим, что если σ«τ, то σ и τ совместимы, так что этот граф поглощает все отношения сравнения в посете Брюа. Кроме того, он соединяет любой порядок σ с его противоположным σ∘ .
18 На рис. 1 изображен граф Чамени-Нембуа в простейшем случае n=3 .
19

Рис. 1. Граф Чамени-Нембуа для n=3 (слово abc обозначает здесь линейный порядок a&lt;b&lt;c )
20 Вернемся к вопросу об агрегировании. Как уже говорилось, в общем случае агрегирование бинарных данных линейных порядков не приводит к линейному порядку. Однако если рассматривать не произвольные линейные порядки, а только порядки из некоторого заранее оговоренного подмножества (области, домена) D⊂LO , можно ожидать, что парадокс Кондорсе не возникнет. Такие области линейных порядков называются областями Кондорсе (ОК). Исследованию и построению таких областей было посвящено несколько работ (Fishburn, 1997; Monjardet, 2009; Black, 1948; Chameni-Nembua, 1989; Puppe, 2018; Puppe, Slinko, 2019). Оказалось, что отношение совместимости имеет самое прямое отношение к ОК. А именно имеет место факт, установленный Чамени-Нембуа (см. (Danilov, Koshevoy, 2013)).
21 Предложение 1. Пусть D  — клика в графе (LO,≈) . Тогда D является областью Кондорсе. Обратное верно, если область D содержит порядки α и ω .
22 Кликой в графе называется подмножество вершин, которые попарно соединены ребрами. Далее мы ограничимся областями, содержащими порядки α и ω . В этом случае нет разницы между кликами в графе (LO,≈) и областями Кондорсе. Однако как строить интересные (например, максимальные) клики — вопрос непростой, и в следующем разделе мы обсудим способ получить широкий класс максимальных ОК с помощью так называемый ромбических тайлингов. Близкий прием будет применен для построения хороших суперобластей дизайнов (т.е. ОК) с использованием кубильяжей. А пока мы приведем один результат агрегирования ОК.
23 Предположим, что каждый индивид a из нашей группы участников N ратует за некоторую клику Da (или, что то же самое, за ОК Da ). Как можно было бы агрегировать эти клики? Надо образовать множество D (которое можно назвать медианой данного мультимножества в LO), состоящее из тех линейных порядков σ , которые входят в состав Da более чем у половины индивидов a . (Фактически мы делаем то же, что и при агрегировании линейных порядков, только ситуация тут проще, потому что область-клика Da уже задана как подмножество и нам не надо заниматься его бинарной кодировкой.)
24 Предложение 2. Медианная область D является кликой (и, тем самым, ОК).
25 Доказательство. Пусть два порядка σ и τ принадлежат медианной области D . Так как σ и τ принадлежат Da для более чем половины избирателей, то существует избиратель a такой, что его область Da содержит и σ , и τ . Но тогда порядки σ и τ совместимы между собой как члены клики Da . Таким образом, любые два порядка в D совместимы, так что D является кликой и, следовательно, ОК. █
26 Мы не знаем, верен ли этот факт для ОК без условия на α и ω . Однако при выполнении этого условия (что далее всюду предполагается), мы получаем универсальное правило агрегирования областей Кондорсе (клик, или дизайнов), которое можно назвать медианным правилом. Более точно, пусть CD обозначает множество областей Кондорсе, содержащих α и ω (или, что то же самое, множество клик в графе (LO,≈) , содержащих α и ω ). Тогда медианное правило задает отображение med:CDN→CD. Универсальность этого правила в том, что оно применимо к любым ОК. Однако универсальность влечет и существенный недостаток медианного правила. Он заключается в том, что даже когда исходные ОК Di максимальны (как области Кондорсе; максимальность понимается по включению), то результирующая медианная ОК D может не быть максимальной, а может быть довольно небольшой. Понятно, что наибольший интерес представляют именно максимальные ОК. В частности, как показано в (Danilov, Koshevoy, 2013; Puppe, Slinko, 2019), в этом случае агрегированный порядок принадлежит той же ОК.
27 Пример 1. Приведем пример, когда медиана трех максимальных ОК оказывается немаксимальной ОК. В этом примере n=4 . Здесь и далее линейный порядок изображается просто словом (стрингом) из разных альтернатив, идущих от наименьшей альтернативы к наибольшей. К примеру, слово «2314» изображает линейный порядок 2
28 Рассмотрим три ОК, заданные списками:
29 D1={1234,2134,2314,2341,3214,3241,3421,4321},
30 D2={1234,1324,1342,3124,3142,3412,3421,4312,4321},
31 D3={1234,1234,2134,2143,2413,2431,4213,4231,4321}.
32 Можно проверить (см. разд. 3), что это действительно ОК, причем максимальные. Медиана этих трех областей состоит из четырех порядков 1234, 2134, 3421 и 4321, и она немаксимальна (она содержится в большей области D1 ).
33 Ситуация с универсальным медианным правилом агрегирования ОК напоминает следующую. Предположим, мы агрегируем линейные порядки по правилу единогласия. Тогда получается транзитивный порядок, но, как правило, неполный. Чтобы медианный агрегат максимальных ОК тоже был максимальной ОК, надо ограничить множество допустимых ОК. В дальнейшем подмножества в множестве MaxCD максимальных ОК мы называем суперобластями (чтобы отличать их от областей в LO). В разд. 3 мы напомним способ построения максимальных ОК, основанный на использовании ромбических тайлингов. А затем рассмотрим трехмерные обобщения тайлингов — кубильяжи — для построения хороших суперобластей.
34 3. ТАЙЛИНГОВЫЕ ОБЛАСТИ КОНДОРСЕ
35 Мы начнем с описания класса областей Кондорсе, которые строятся с помощью ромбических тайлингов. Такие ОК, рассмотренные в (Данилов, Карзанов, Кошевой, 2010б), образуют обширный и интересный класс максимальных ОК, и мы далее будем ориентироваться именно на тайлинговые ОК.
36 Ромбический тайлинг — это правильное замощение плоского выпуклого центрально симметричного 2n-угольника (зоногона) параллелограммами (для краткости называемыми ромбами). Чтобы задать зоногон Z=Z(n,2) , надо взять n векторов ξ1,...,ξn в верхней полуплоскости (можно считать, что ξi=(ti,1) и t1<...<tn ) и образовать зоногон Z как сумму по Минковскому n отрезков [0,ξi] , i=1,...,n . Иначе говоря, Z=∑iαiξi,    0≤αi≤1.
37 Ромбом называется параллелограмм, полученный сдвигом суммы двух различных отрезков [0,ξi] и [0,ξj] ; пара (i,j) — это тип такого ромба.
38 Ромбический тайлинг (или просто тайлинг) это множество T ромбов в зоногоне Z, которые покрывают зоногон, причем ромбы пересекаются только по своим граням. Тайлинг T определяет плоский направленный граф GT , вершины которого состоят из вершин ромбов из T, а ребра — из ребер ромбов из T, ориентированных снизу вверх. Каждое ребро параллельно некоторому вектору ξi , и это i называется цветом ребра.
39 Змейкой в тайлинге T называется направленный путь в графе GT , идущий из нижней вершины 0 зоногона Z в верхнюю вершину ξ1+...+ξn . Одна из змеек изображена на рис. 3. Следующие утверждения можно найти, например, в (Данилов, Карзанов, Кошевой, 2010а). 1. Множество цветов ребер любой змейки биективно множеству [n].
40 Тем самым каждая змейка S тайлинга T определяет линейный порядок <S на [n] . Цвета ребер змейки идут снизу вверх в порядке возрастания. В силу этого мы не делаем особого различия между змейкой S и соотвествующим линейным порядком <S . Например, самая левая змейка, проходящая по левой границе зоногона, дает линейный порядок α ; правая граничная змейка — дает ω . Множество всех змеек тайлинга T обозначается Σ(T) .
41 2. Сопоставление ромбу тайлинга его типа является биекцией T в Ω .
42 Иначе говоря, для каждой пары (i,j)∈Ω существует, и притом ровно один, ромб тайлинга T с типом (i,j) . В частности, число ромбов любого ромбического тайлинга равно n(n+1)/2 .
43 3. Множество инверсий Inv(<S) линейного порядка <S , заданного змейкой S, устроено так. Змейка S делит T на две половины ромбов: расположенные слева от змейки и расположенные справа. Тогда Inv(<S) состоит из типов ромбов, расположенных слева от змейки S. В силу этого утверждения любые змейки (как порядки на [n] ) совместимы. Так что множество Σ(T) всех змеек тайлинга T является кликой графа (LO,≈) , а следовательно, областью Кондорсе. В (Danilov, Koshevoy, 2013) показано, что ОК Σ(T) является максимальной ОК, причем содержащей порядки α и ω . Поэтому правило большинства задает отображение агрегирования smT:Σ(T)N→Σ(T).
44 4. Характерным свойством тайлинговых ОК является так называемое свойство связности. Два линейных порядка σ и τ считаются соседними, если Inv(σ) отличается от Inv(τ) не более чем на один элемент. Цепью назовем последовательность порядков (σ1,...,σN) , так что σk и σk+1 соседи для любого k от 1 до N-1 .
45 Свойство связности (для максимальной клики в LO) можно формулировать разными (но эквивалентными) способами, начиная от слабого: «Существует возрастающая цепь от α до ω » — и кончая сильным: «Любые порядки связаны некоторой цепью». Имеет место следующее утверждение.
46 Утверждение. Тайлинговая ОК — это в точности максимальная связная ОК, содержащая порядки α и ω .
47 Пример 2. Области D1 , D2 и D3 , рассмотренные в примере 1, являются областями Σ(T) для трех тайлингов, изображенных на рис. 2.
48

Рис. 2. Три тайлинга для примера 1
49 Пример 3. Область Блэка, состоящая из однопиковых порядков на [n] , соответствует множеству змеек антистандартного тайлинга. Однако здесь удобнее говорить о противоположной области одноямных предпочтений и, соответственно, о стандартном тайлинге.
50 Линейный порядок σ=<σ на [n] называется одноямным, если у него имеется только один локальный минимум. Иначе говоря, пусть i*=min(σ)  — нахудший (наименьший) элемент относительно порядка σ . Тогда ограничение σ на интервал [i*,...,n] совпадает с натуральным порядком α (когда 1<2<...<n ), а ограничение на интервал [1,...,i*] совпадает с порядком, противоположным натуральному. Эквивалентно можно сказать, что нижний конус любого элемента i (т.е. множество тех j , что i>σj ) образует интервал в [n] .
51 Стандартный тайлинг можно определить так. Из нижней вершины 0 зоногона выходит (n-1) ромб с типами {1,2} , {2,3} ,..., {n-1,n} соответственно. Такая система ромбов однозначно достраивается до ромбического тайлинга, который и называется стандартным. Таким образом, на первом этаже имеется n-1 ромб, на втором — n-2 ромба, и так далее, на последнем (n-1) этаже располагается единственный ромб с типом {1,n} (рис. 3).
52

Рис. 3. Стандартный тайлинг для n=5 (стрелками изображена змейка, дающая одноямный линейный порядок 3
53 Вершины графа G для такого тайлинга имеют вид суммы векторов ξi , где i пробегает некоторый интервал в [n] . Поэтому змейка, т.е. возрастающий путь, дает растущую цепочку интервалов, с каждым шагом увеличивающуюся на один элеменет. Вместе с характеризацией одноямных предпочтений это показывает, что змейки стандартного тайлинга — это в точности одноямные порядки.
54 4. СУПЕРОБЛАСТИ И КУБИЛЬЯЖИ
55 До сих пор мы напоминали теорию агрегирования линейных порядков. Если мы берем тайлинг T, то, пользуясь правилом простого большинства, можно агрегировать любые мультимножества из Σ(T) . Иначе говоря, тайлинг T можно рассматривать как дизайн организации выборов (далее — просто дизайн). А именно мы предлагаем каждому участнику (избирателю) назвать некоторый порядок из Σ(T) и затем с помощью отображения smT:Σ(T)N→Σ(T) агрегируем эти порядки. Но тайлингов, а следовательно, и дизайнов, много, и встает задача – как можно агрегировать эти дизайны-тайлинги.
56 Схема рассуждения тут аналогична той, которую мы излагали в разд. 2. Вспомним, что агрегирование линейных порядков мы начинали с построения бинарной формы. Аналогично можно поступить и здесь применительно к тайлингам (идея следующего определения инверсий восходит к работе (Манин, Шехтман, 1986)). Пусть T — некоторый тайлинг зоногона Z(n) . И пусть i<j<k  — тройка элементов из [n] . Если редуцировать тайлинг T по всем цветам, кроме i,j и k (см. (Данилов, Карзанов, Кошевой, 2019)), мы получим тайлинг на множестве {i,j,k} . А таких тайлингов, как легко убедиться, всего два — стандартный и антистандартный. Тройка ijk называется инверсией тайлинга T, если этот редуцированный тайлинг антистандартный. Множество всех инверсий тайлинга T обозначается Inv(T), и это некоторое подмножество в множестве [n]3 всех троек в [n] . Важно то, что множество Inv(T)⊂[n]3 однозначно определяет тайлинг T. Оно считается бинарной формой (или кодировкой) тайлинга.
57 Если теперь нам дано мультимножество тайлингов (Ta,a∈N) , мы можем по правилу простого большинства образовать медиану их бинарных форм, т.е. множеств Inv(Ta) , получая в результате некоторое подмножество Inv . И если последнее действительно является инверсным множеством некоторого тайлинга T, этот однозначно определенный тайлинг следует считать агрегатом (или медианой) исходного мультимножества. Трудности тут ровно те же, что и при агрегировании линейных порядков — агрегированное множество Inv может не быть множеством инверсий никакого тайлинга.
58 Обратимся к задаче построения хороших суперобластей в T. И так же, как мы использовали ромбические тайлинги для построения хороших областей линейных порядков, обратимся к использованию трехмерных обобщений тайлингов, а именно к кубильяжам.
59 Кубильяж — это заполнение кубами уже трехмерного зонотопа. Более точно, зададимся n векторами ξi , которые принадлежат R3 и имеют форму (1,ti,ti2 ), где ti — возрастающие числа ( t1<...<tn ). Трехмерный циклический зонотоп Z=Z(n,3)  — это сумма n отрезков [0,ξi] , кубы — суммы троек таких отрезков (соответствующая тройка индексов называется типом куба). Кубильяжи (как и множество его кубов) обозначается как Q 2.
2. Более подробно об этом см. (Данилов, Карзанов, Кошевой, 2019).
60 Если мы спроектируем пространство R3 на плоскость R2 вдоль третьей координаты (будем обозначать эту проекцию как π ), наш зонотоп Z спроектируется на зоногон Z'=π(Z) , построенный на векторах π(ξi)=(1,ti) . Двумерные аналоги змеек в Z мы называем мембранами. Более точно, мембрана M в кубильяже Q зонотопа Z — это двумерный комплекс, составленный из фасет кубов кубильяжа, который при проекции π биективно проектируется на зоногон Z'=π(Z) . Так как каждая двумерная грань любого куба из Q проектируется в ромб, проекция мембраны M задает ромбический тайлинг зоногона Z' , обознаемый как π(M) , который, в свою очередь, однозначно определяет мембрану M . Таким образом, каждый кубильяж Q зонотопа Z дает много тайлингов зоногона Z' — по одному для каждой мембраны. Множество мембран кубильяжа Q обозначим как M(Q) , а соответствующее (биективно эквивалентное ему) множество тайлингов — T(Q). Мы утверждаем, что на суперобласти T(Q) приведенное выше правило большинства хорошо работает.
61 Теорема. Если Q  — некоторый кубильяж циклического зонотопа Z=Z(n,3) , то в суперобласти T(Q) правило простого большинства хорошо работает и результирующий тайлинг тоже принадлежит T(Q) .
62 Сответствующее правило агрегирования на суперобласти T(Q) обозначим как medQ:T(Q)N→T(Q). Для доказательства теоремы переформулируем все в терминах мембран кубильяжа Q . И в первую очередь надо переформулировать инверсии. Делается это, как для змеек. Каждая мембрана M делит зонотоп Z на две части — до мембраны и после нее («до» и «после» относиельно третьей координаты в R3 ). Аналогично делятся и кубы, входящие в Q . Типы кубов, расположенных до мембраны, — это в точности множество инверсий Inv тайлинга, соответствующего мембране M при проекции π .
63 Можно сказать об этом по-другому. Пусть Q — куб кубильяжа Q . Если смотреть на него в направлении роста третьей координаты (вдоль которой и происходит проекция π ), у него три видимые (освещенные, фронтальные) двумерные грани и три невидимые (затененные, тыловые). Если куб Q своей невидимой гранью соприкасается с видимой гранью другого куба Q' того же кубильяжа Q , мы говорим, что Q непосредственно предшествует кубу Q' и записываем это как Q
64 Пусть снова M  — мембрана в Q . Тогда кубы, расположенные до мембраны, образуют порядковый идеал (или стек) посета (Q, ≤). Верно и обратное, имея стек S , можно образовать мембрану M , взяв заднюю сторону объединения кубов стека S . Это показывает, что мембраны можно отождествлять со стеками в Q . Типы кубов, попавшие в этот стек, и образуют инверсное множество Inv(π(M)) . Этим мы визуализируем множество Inv(π(M)) .
65 Приступим теперь к процедуре агрегирования мембран кубильяжа Q . Или, что то же самое, к агрегированию стеков этого кубильяжа. Пусть имеется (мульти)множество мембран Ma , или, что то же самое, (мульти)множество стеков Sa (индекс a указывает на избирателя). Образуем функцию φ на Q : для куба Q нашего кубильяжа φ(Q) равно числу стеков S(Mk), содержащих Q (или, что то же самое, сколько раз тип этого куба входит в инверсное множество наших избирателей). Теперь оставляем только те кубы Q, у которых значение φ(Q) превышает половину мощности нашего мультимножества (т.е. числа избирателей — правило большинства). Мы получает некоторое множество S в Q .
66 Мы утверждаем, что это множество S является стеком нашего кубильяжа. В самом деле, если куб Q попал в S , а Q’≤Q, то любой избиратель, одобривший Q, одобряет и Q' . А раз S  — стек, то он определяет некоторую мембрану M , которая и является агрегатором (или медианой) мультимножества мембран (Ma) .
67 5. СРАВНЕНИЕ ПРАВИЛ
68 Итак, мы имеем, с одной стороны, универсально действующее медианное правило med:CDN→CD , а с другой, — для каждого кубильяжа Q свое кубильяжное правило medQ:T(Q)N→T(Q) . Конечно, в каком-то смысле все они являются правилами простого большинства. Только первое (универсальное) работает, агрегируя ОК как подмножества в LO, а ограниченные, кубильяжные правила работают с бинарными представлениями тайлинговых ОК. Покажем, что эти правила работают согласованно на общей суперобласти. Проще всего это сформулировать и показать для кубильяжных правил.
69 Предложение 3. Пусть Q1 и Q2  — два кубильяжа, и предпочтения избирателей лежат в пересечении суперобластей T(Q1) и T(Q2) . Тогда результат применения этих правил будет один и тот же.
70 В самом деле, результат зависит только от инверсных множеств Inv(Ta) .
71 Сложнее сравнить универсальное медианное правило с кубильяжным. Дело в том, что результат универсального правила med  — это некоторая ОК, как правило, немаксимальная, тогда как результат кубильяжного правила medQ  — максимальная ОК. В этом случае согласованность означает, что первая ОК лежит во второй, тайлинговой ОК. Можно сказать также, что эти правила не противоречат друг другу; просто второе усиливает первое.
72 Предложение 4. Медианное правило согласовано с любым кубильяжным.
73 Доказательство. Геометрически нужно показать, что если змейка-порядок S лежит более чем на половине мембран Ma , она лежит и на агрегированной мембране M . А змейка лежит на мембране тогда и только тогда, когда на мембране лежит любая ее вершина v. Таким образом, нам нужно проверить, что если вершина v кубильяжа лежит более чем на половине мембран Ma , то она лежит и на агрегированной мембране M .
74 Мы ограничимся рассмотрением случая, когда вершина v является внутренней точкой зонотопа Z (для вершин, лежащих на границе зонотопа, рассуждение аналогично и даже проще). Если мы отступим от вершины v немного назад (по третьей координате), мы попадем в куб Q кубильяжа (носиком которого будет вершина v). Напротив, если мы чуть продвинемся вперед (тоже по третьей координате), мы попадем в куб Q' (хвостиком которого является вершина v). Для любой мембраны Ma , проходящей через вершину v, куб Q является инверсным, тогда как Q' инверсным не является. Поэтому средняя (медианная) мембрана M проходит после куба Q и раньше куба Q' , т.е. она проходит между ними, а значит, через вершину v, потому что v — это вершина, по которой контактируют кубы Q и Q' .
75 6. ПРИМЕР
76 Чтобы все сказанное не оставалось абстракцией, рассмотрим простейший пример для n=4 . Он потребует некоторого трехмерного воображения. В этом случае имеется 4!=24 линейных порядка и 8 ромбическох тайлингов (рис. 4). Стрелки, идущие вверх, — это образующие (высшего, второго) посета Брюа–Манина–Шехтмана. Внизу находится стандартный тайлинг, наверху — антистандартный.
77

Рис. 4. Пример для n=4 (Данилов, Карзанов, Кошевой, 2019)
78 Чтобы агрегировать такие тайлинги, можно взять левую или правую восходящие ветви этого кольца. Ветвь образует цепь из пяти элементов, а агрегировать на цепи просто — например, брать медиану. По конструкции, изложенной выше, мы должны взять какой-нибудь кубильяж зонотопа Z=Z(4,3) . Их два — стандартный и антистандартный. Первый характеризуется тем, что содержит куб с вершиной в 0 и типом 123. Если посмотреть на этот кубильяж (Данилов, Карзанов, Кошевой, 2019, рис. 6), можно увидеть, что мембраны этого кубильяжа — это в точности пять тайлингов на правой восходящей ветви кольца, о котором говорилось выше.
79 Простота процедуры связана с тем, что для стандартного кубильяжа Qst зонотопа Z(4,3) естественный посет устроен очень просто — это цепь из 4 элементов. В терминах типов кубов этот порядок выглядит как лексикография 123
80 Если бы мы захотели проделать подобное для n=5 , мы встретились бы с возросшей трудностью. В этом случае у нас было бы уже 62 тайлинга (они, как и высший посет Брюа–Манина–Шехтмана, приведены в (Felsner, Ziegler, 2001)). А кубильяжей у зонотопа Z(5,3)  — десять. Их нетрудно описать, но трудно изобразить. Так что тут придется ограничиться рассмотрением одного (но, видимо, важнейшего) кубильяжа, а именно стандартного. Нарисовать его тоже нелегко, но вот соотвествующий естественный посет на множестве [5]3 изобразить можно. Его вид приведен в (Данилов, Карзанов, Кошевой, 2019). Этот посет (точнее, его диаграмма Хассе) выглядит как на рис. 5.
81

Рис. 5. Естественный посет стандартного кубильяжа зонотопа Z(5,3)
82 Глядя на этот рисунок, можно понять, что в этом посете есть 16 стеков. Иначе говоря, в стандартном тайлинге имеется 16 мембран. И суперобласть из этих 16 тайлингов можно успешно агрегировать.
83 Итак, мы видели, что с помощью ромбических тайлингов (двумерных кубильяжей) можно получать хорошо агрегируемые области линейных порядков, а используя трехмерные кубильяжи — хорошо агрегируемые суперобласти тайлинговых дизайнов. Можно пойти и дальше, применяя кубильяжи высших размерностей и соответственно агрегируя мембраны в них. Сказанное выше без особых проблем переносится на высшие размерности.

References

1. Black D. (1948). On the rationale of group decision-making. Journal of Political Economy, 56, 23–34.

2. Chameni-Nembua C. (1989). Regle majoritaire et distributivite dans le permutoedre. Math. Inform. Sci. Hum., 108, 5–22.

3. Danilov V.I., Karzanov A.V., Koshevoy G.A. (2010a). Systems of separated sets and their geometric models. Uspekhi Matematicheskikh Nauk (Russian Mathematical Surveys), 65, 4 (394), 67–152.

4. Danilov V.I., Karzanov A.V., Koshevoy G.A. (2019). Cubillages of cyclical zonotopes. Uspekhi Matematicheskikh Nauk (Russian Mathematical Surveys), 74, 6 (450), 181–244 (in Russian).

5. Danilov V.I., Karzanov A.V., Koshevoy G.A. (2010b). Condorcet domains and rhombus tilings. Economics and Mathematical Methods, 46, ¹ 4, 55–68 (in Russian).

6. Danilov V.I., Koshevoy G.A. (2013). Maximal Condorcet domains. Order, 30, 1, 181–194.

7. Felsner S., Ziegler G.M. (2001). Zonotopes associated with higher Bruhat orders. Discrete Mathematics, 241, 301–312.

8. Fishburn P. (1997). Acyclic sets of linear orders. Soc. Choice Welf., 14, 113–124.

9. Manin Yu.I., Shekhtman V.V. (1986). Higher Bruhat orders related to the symmetric group. Functional Analysis and Its Applications, 20, 2, 74–75 (in Russian).

10. Monjardet B. (2009). Acyclic domains of linear orders: a survey. In: S. Brans, W. Gehrlein, F. Roberts (eds.). The mathematics of preferebce, choice and order, 136–160. Berlin: Springer.

11. Puppe C. (2018). The single-peaked domain revisited: A simple global characterization. J. Econ. Theory, 176, 55–80.

12. Puppe C., Slinko A. (2019). Condorcet domains, median graphs and the single-crossing property. Economic Theory, 67, 285–318.

Comments

No posts found

Write a review
Translate