Автоматика и телемеханика, № 9, 2022

Обзоры

(Национальный исследовательский университет

¾Высшая школа экономики¿, Москва;

Институт проблем управления им. В.А. Трапезникова, Москва)

СТРУКТУРИРОВАННЫЕ ПРЕДПОЧТЕНИЯ:

ОБЗОР ЛИТЕРАТУРЫ¹

Проведен обзор работ по практически значимым ограничениям на про-

филь предпочтений коллектива: однопиковые предпочтения, сепарабель-

ные предпочтения, предпочтения со свойством единственного пересече-

ния, евклидовы предпочтения и их расширения. Рассмотрены как орди-

нальные, так и дихотомические предпочтения. Для структурированных

предпочтений представлена характеризация через запрещенные подпро-

фили и вероятность появления профиля с заданным свойством. Для се-

парабельных предпочтений описан алгоритм построения иерархического

дерева. Отдельно рассмотрены структурированные предпочтения, приво-

дящие к единственному устойчивому паросочетанию в задаче о марьяже.

Ключевые слова: домен предпочтений, паросочетания, однопиковость.

DOI: 10.31857/S000523102209001X, EDN: AIIVES

1. Введение

Существует множество подходов к моделированию предпочтений и поста-

новке задачи их агрегирования [1]. Базовой моделью предпочтения является

строгий линейный порядок. Кортеж линейных порядков всех агентов называ-

ется профилем предпочтений. Стандартной постановкой задачи коллектив-

ного выбора является определение общественного выбора (предпочтения) как

функции от профиля предпочтений.

Одной из основных теоретических проблем в данной области является па-

радокс Кондорсе: предпочтение коллектива, построенное на основе прави-

ла простого большинства, может иметь циклы. Данный парадокс возникает

при трех и более альтернативах. К. Эрроу [2] сформулировал ряд аксиом,

которым должна обладать процедура агрегирования предпочтений коллек-

тива. Система аксиом оказалась несовместной при трех и более альтерна-

тивах. A. Гиббард и M. Саттертуэйт [3, 4] показали, что при аналогичных

предпосылках любое правило агрегирования является манипулируемым, т.е.

¹ Работа частично профинансирована Программой фундаментальных исследований

НИУ ВШЭ.

допускает наличие выгоды для участника от искажения собственного пред-

почтения.

Одним из решений парадоксов невозможности является сужение обла-

сти применения правил агрегирования. На области профилей предпочте-

ний, не создающих циклов при использовании правила простого большин-

ства, правило простого большинства удовлетворяет аксиомам К. Эрроу, и

любое правило, отличающееся от правила простого большинства на этой об-

ласти, будет нарушать условия, близкие к аксиомам К. Эрроу [5, 6]. Правило

простого большинства имеет несколько аксиоматических обоснований [7-11],

несложно с вычислительной точки зрения и интуитивно понятно участникам

голосования.

Задача нахождения всех профилей предпочтений, для которых правило

простого большинства дает ациклическое отношение сравнения альтернатив,

решена только для случая трех и четырех альтернатив [12]. Для трех аль-

тернатив найдено компактное необходимое и достаточное условие на профиль

предпочтений: одна из альтернатив должна быть первой у не менее чем по-

ловины агентов или одна из альтернатив должна быть последней у не менее

чем половины агентов [13].

Необходимость сужения области рассматриваемых профилей предпочте-

ний привела к теории доменов предпочтений. Под доменом предпочтений

понимается подмножество линейных порядков на фиксированном множестве

альтернатив. Домен генерирует профили предпочтений, состоящие только из

линейных порядков, составляющих домен.

Ограничение предпочтений членов общества предпочтениями из некоторо-

го домена является упрощением, но так как предпочтения в обществе форми-

руются не независимо, то значительная часть его членов имеет ограниченный

набор линейных порядков, и ограничение на домен предпочтений представ-

ляется разумной предпосылкой для моделирования коллективного выбора.

Домены как ограничения на рациональность рассмотрены в [14].

Доменом Кондорсе называется такое подмножество предпочтений, что лю-

бой профиль предпочтений с нечетным числом агентов приводит к ациклич-

ному решению по правилу простого большинства. Для трех, четырех и пяти

альтернатив найдены все домены Кондорсе [15, 16]. Они значительно отли-

чаются по структуре и размеру. Для 6 альтернатив домен Кондорсе макси-

мального размера содержит 45 линейных порядков, для 7

100 линейных

порядков. Для большего числа альтернатив задача нахождения домена Кон-

дорсе максимального размера остается нерешенной [17]. Последние резуль-

таты о максимальных доменах Кондорсе представлены в [18-20]. Некоторое

обобщение понятия домена Кондорсе обсуждается в [21, 22].

Некоторые домены Кондорсе представляют собой естественные, хорошо

интерпретируемые ограничения на область задания предпочтений. К. Инада

[23, 24] и А. Сен [25] описали домены однопиковых предпочтений, однолунко-

вых предпочтений, сепарабельных предпочтений. Дж. Миррлис и К. Робертс

[26, 27] предложили концепцию предпочтений со свойством единственного пе-

ресечения. Различные ограничения на профиль предпочтений получили на-

звание структурированных предпочтений [28]. Все упомянутые выше виды

структурированных предпочтений имеют множество полезных свойств и при-

ложений, которые разобраны в данном обзоре.

Кроме гарантии существования решения задачи агрегирования в поста-

новке К. Эрроу, структурированные предпочтения снижают вычислитель-

ную сложность многих задач теории коллективного выбора, создают удобное

графическое представление предпочтений, имеют аксиоматическое обосно-

вание.

В данном обзоре представлены результаты по характеризации структури-

рованных профилей предпочтений через запрещенные подпрофили и по на-

хождению числа профилей с заданными свойствами. Характеризация струк-

турированных предпочтений важна для выявления ключевых внутренних

структур и для построения алгоритмов распознавания структурированных

предпочтений. Количество структурированных профилей предпочтений да-

ет возможность найти вероятность возникновения таких профилей в мо-

дели дискретного равновероятного распределения. Хотя такое распределе-

ние не отражает реальные данные, нахождение вероятностей представля-

ет интерес для сравнения вероятностей разных видов предпочтений между

собой.

В рамках модели равновероятного распределения общие формулы (для

произвольного числа агентов и альтернатив) получены для сепарабельных

предпочтений [29] и некоторых подклассов однопиковых предпочтений и

предпочтений со свойством единственного пересечения [30]. Для малого чис-

ла альтернатив задача подсчета числа однопиковых профилей предпочтений

решена в [31-33].

Кроме доменов Кондорсе в литературе представлены работы по изучению

диктаторских доменов, т.е. доменов, для которых единственной процедурой,

удовлетворяющей аксиомам К. Эрроу [2], является диктаторская процеду-

ра. Примерами диктаторских доменов являются домены циклической груп-

пы [34], круговые домены [35], топ-круговые домены [36], однопиковые на

окружности домены [37]. Диктаторский домен минимального размера содер-

жит только 6 типов линейных порядков при любом количестве альтернатив

[38]. Диктаторские домены имеют гораздо меньше приложений, чем домены

Кондорсе, и не будут рассмотрены в данном обзоре.

Кроме структурированных доменов в задаче агрегирования ординальных

предпочтений в обзоре рассмотрены структурированные профили предпочте-

ний в задаче о марьяже (обобщенные паросочетания) и структурированные

дихотомические предпочтения.

Структура обзора следующая. Раздел 2 вводит основные понятия и теорию

максимальных доменов Кондорсе. Раздел 3 посвящен структурированным ор-

динальным предпочтениям. Раздел 4 содержит анализ структурированных

профилей предпочтений в задаче о марьяже. Раздел 5 исследует дихотоми-

ческие предпочтения. Раздел 6 содержит заключение.

2. Основные понятия

В данной статье приняты следующие обозначения: множество альтернатив

обозначается через A = {1, . . . , m}, а множество агентов через N = {1, . . . , n}.

Каждый агент i ∈ N имеет линейный порядок предпочтения P_i на множе-

стве A (далее, если не оговорено иное, под предпочтением подразумевается

линейный порядок). Максимальный элемент в этом порядке является наи-

лучшим, минимальный наихудшим. Для aP_ic и bP_ic вводится обозначение

{a, b}P_ic. Пусть L (A) будет множеством всех возможных линейных поряд-

ков на множестве X. Кортеж из n линейных порядков является профилем

предпочтений: P = (P₁, . . . , P_n) ∈ L (A)ⁿ.

Доменом предпочтений называется подмножество линейных порядков.

Профиль предпочтений порожден доменом, если предпочтения всех агентов

принадлежат домену. Под доменом структурированных предпочтений здесь

понимается максимальный домен структурированных предпочтений, т.е. при

добавлении к такому домену любого дополнительного линейного порядка до-

мен теряет ключевое свойство, например, свойство однопиковости.

В качестве единственной модели распределения вероятностей в данной

работе используется предпосылка о независимом и равновероятном появ-

лении каждого линейного порядка предпочтения у каждого агента. Ко-

личество элементарных событий (профилей предпочтений) равно (m!)ⁿ.

Подсчитав количество профилей предпочтений с определенным свойством

#structured(m,n), можно рассчитать вероятность появления структуриро-

ванного профиля предпочтений как#stru(m!)nd(m,n)

2.1. Максимальные домены Кондорсе

Парадокс Кондорсе представляет собой ситуацию, в которой предпочтение

коллектива, построенное по правилу простого большинства, содержит цикл.

Простейшим примером является профиль предпочтений с тремя агентами и

тремя альтернативами (предпочтения записаны в столбец без знака бинарно-

го отношения P )

Далее в работе будут определены различные конфигурации определен-

ные фрагменты доменов, наличие или отсутствие которых будут определять

свойства доменов.

Конфигурация 1 (цикл Кондорсе). Существуют три агента i, j, k ∈ N и три

альтернативы a, b, c ∈ A такие, что выполнено aP_ibP_ic, cP_j aP_j b, bP_kcP_ka.

Если домен предпочтений содержит конфигурации 1, то среди профилей

предпочтений, порожденных данным доменом, найдется профиль с парадок-

сом Кондорсе. Определение домена Кондорсе через ациклическое отноше-

ние коллективных предпочтений, построенных по правилу простого большин-

ства, неоперационально, поэтому для практического применения используют

эквивалентные формулировки, представленные в теореме 1.

Теорема 1 [25]. Существуют следующие эквивалентные определения

домена Кондорсе:

(i) Домен предпочтений является доменом Кондорсе тогда и только то-

гда, когда он не содержит конфигурации 1;

(ii) Домен предпочтений является доменом Кондорсе тогда и только то-

гда, когда для каждой тройки альтернатив существует альтернати-

ва из этой тройки, для которой верно, что она либо никогда не стоит

на первом месте в сужении домена на данную тройку, либо никогда

не стоит на втором месте в сужении домена на данную тройку, ли-

бо никогда не стоит на третьем месте в сужении домена на данную

тройку.

Условие (ii) теоремы 1 отражает три способа избежать конфигурацию 1,

где каждая альтернатива находится и на первом, и на втором, и на третьем

месте. Большее число эквивалентных определений домена Кондорсе можно

найти в обзоре [39].

Одним из больших доменов Кондорсе является домен Фишберна [40], ко-

торый удовлетворяет следующей перемежающей схеме. При упорядочении

альтернатив a₁, . . . , a_m для каждой тройки альтернатив a_i, a_j , a_k верно, что

если медиана чисел i ≤ j ≤ k четна (нечетна), то альтернатива a_j никогда

не стоит на первом месте в сужении домена на эту тройку, и если медиа-

на чисел i ≤ j ≤ k нечетна (четна), то альтернатива a_j никогда не стоит на

последнем месте в сужении домена на эту тройку. Домен Фишберна связан

со многими комбинаторными структурами: проволочными диаграммами [17],

ромбическими паркетами [41], с конечными группами Коксетера [42].

Количество линейных порядков в домене Фишберна равно [17]:



(

)



m-2



m-

для четных m;



-1

|F_m| = (m + 3) 2^m-3 -







m-1



m-1



 m-1

 для нечетных m.



Домен Фишберна обладает максимальным размером среди всех доменов

Кондорсе при числе альтернатив, не превышающем семи, и является основой

для построения больших доменов Кондорсе для любого числа альтернатив

[20, 40], но данный домен не имеет ясной интерпретации и не имеет практиче-

ского применения. Известно, что при большом m существует домен Кондор-

се, содержащий не менее 2,189^m линейных порядков [20]. Раздел 3 исследует

домены меньшего размера, но с хорошо интерпретируемой структурой.

3. Структурированные ординальные предпочтения

3.1. Однопиковые предпочтения

Однопиковые предпочтения предполагают некоторое упорядочение аль-

тернатив вдоль так называемой оси (под осью понимается линейный порядок

альтернатив, понятие расстояния между альтернативами не вводится). Каж-

дый агент имеет идеальную альтернативу на этой оси. Если две альтернативы

расположены по одну сторону от идеальной альтернативы, включая возмож-

ное совпадение с идеальной, то та альтернатива, которая находится ближе к

идеальной точке, предпочитается альтернативе, находящейся дальше. Аль-

тернативы с разных сторон от идеальной могут быть упорядочены любым

способом.

Оси с прямым порядком альтернатив и с обратным порядком альтерна-

тив соответствуют идентичным друг другу однопиковым доменам. В этом

смысли данные оси эквивалентны. Например, оси 1234 и 4321 эквивалентны.

Таким образом, существуют m!/2 различных осей и доменов однопиковых

предпочтений. Домены однопиковых предпочтений содержат по 2^m-1 линей-

ных порядков [43]. Например, ось 1234 задает следующий домен из восьми

линейных порядков:

Однопиковые домены могут иметь непустое пересечение. Для однопико-

вого профиля предпочтений нельзя однозначно определить, каким однопи-

ковым доменом он порожден. Например, профиль (123, 123, 213) может быть

порожден как однопиковым доменом {123, 213, 231, 321} с осью 123, так и

однопиковым доменом {312, 132, 123, 213} с осью 312. Алгоритмы распозна-

вания однопиковых профилей предпочтений [44, 45] отвечают на вопрос о

возможности построения подходящей оси и конструируют одну из возмож-

ных осей.

Однопиковые предпочтения имеют массу приложений в экономике, психо-

логии, политических науках. Причиной этого являются теоретические свой-

ства однопиковых предпочтений. Во-первых, однопиковые предпочтения хо-

рошо интерпретируемы и допускают удобную визуализацию. В политической

науке распространена шкала правых-левых кандидатов, партий, в маркетин-

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

что они выстраиваются в линию. Во-вторых, теорема о медианном избирате-

ле [46], гласящая, что политическая позиция двух кандидатов при свободной

конкуренции будет стремиться к позиции медианного избирателя, дает до-

полнительное обоснование правилу простого большинства. В-третьих, мно-

гие вычислительные проблемы теории коллективного выбора значительно

упрощаются при однопиковых предпочтениях [47, 48], например упрощают-

ся задачи манипулирования (подробнее о задачах манипулирования см. [49]).

В-четвертых, однопиковые предпочтения имеют аксиоматическое обоснова-

ние [50]. Домен однопиковых предпочтений для каждой альтернативы имеет

хотя бы один линейный порядок с данной альтернативой на первом месте.

Все линейные порядки в этом домене связаны друг с другом, т.е. один ли-

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

обращения пар соседних альтернатив линейных порядков, при этом все про-

межуточные линейные порядки тоже принадлежат тому же домену. Кроме

того, в этом домене существует пара линейных порядков, которые имеют об-

ратный порядок альтернатив по отношению друг к другу. Таким образом,

домен однопиковых предпочтений состоит из достаточно близких предпочте-

ний, но в то же время достаточно разнообразен, так как содержит пару про-

тивоположных предпочтений.

Однолунковые предпочтения являются полной противоположностью од-

нопиковых предпочтений. Все альтернативы также находятся на оси, толь-

ко каждый агент имеет свою наихудшую альтернативу на этой оси и чем

дальше от этой альтернативы, тем лучше. В экономике данные предпочтения

встречаются при моделировании предпочтений относительно общественного

антиблага (например, предпочтения местных жителей относительно распо-

ложения на побережье загрязняющего предприятия). Анализ, проведенный

для однопиковых предпочтений, практически всегда можно применить к од-

нолунковым, поэтому далее в статье однолунковые предпочтения исследо-

ваться не будут.

Наихудшей альтернативой для каждого из агентов при однопиковых пред-

почтениях является один из концов оси. Таким образом, профиль предпочте-

ний не может иметь трех агентов с разными наихудшими альтернативами.

Конфигурация 2. Существуют три агента i, j, k ∈ N и три альтернативы

a, b, c ∈ A такие, что выполнено {a, b}P_ic, {a, c}P_j b, {b, c}P_k a.

Конфигурация 2 уточняет условие (ii) из теоремы 1: в каждой тройке

альтернатив существует альтернатива из этой тройки, для которой верно, что

она никогда не стоит на третьем месте в сужении домена на данную тройку.

Профиль предпочтений, который не содержит конфигурацию 2, называется

однопиковым по Эрроу (подробнее о данных предпочтениях см. в [2, 20, 31,

51, 52]).

Конфигурация 3. Существуют два агента i, j ∈ N и четыре альтернативы

a, b, c, d ∈ A такие, что выполнено {a, d}P_ibP_ic, {c, d}P_j bP_j a.

Конфигурация 3 задает ограничение на пары агентов. При фиксации од-

ного из агентов множество возможных предпочтений второго агента соот-

ветствует некоторому паттерну перестановок, который задается через запре-

щенные комбинации (подробнее о паттернах перестановок см. в [53]). Число

перестановок в паттерне дает число профилей с двумя агентами.

Теорема 2 [54]. Профиль предпочтений является однопиковым тогда и

только тогда, когда он не содержит конфигураций 2 и 3.

Теорема 3 [31]. Количество однопиковых профилей предпочтений

асимптотически равно

#SP(m,n) ≈

2(m-1)n.

Точное количество однопиковых профилей известно для двух агентов и

произвольного количества альтернатив [33], трех, четырех [31], пяти альтер-

натив [32] и произвольного количества агентов.

Однопиковые предпочтения имеют множество расширений. Одним из на-

правлений является рассмотрение разных классов графов вместо оси альтер-

натив. Примерами такого расширения являются однопиковые на деревьях

предпочтения [55], однопиковые на окружности предпочтения [37], однопико-

вые на произвольном графе предпочтения [56, 57].

В модели однопиковых на деревьях предпочтений альтернативы являются

вершинами связного ациклического графа (дерева) и каждый путь представ-

ляет собой ось для соответствующего подпрофиля однопиковых предпочте-

ний. В силу разнообразия деревьев данные предпочтения очень разнообраз-

ны. Существуют алгоритмы нахождения дерева, представляющего данный

профиль [58, 59], а также алгоритмы для нахождения дерева с некоторыми

нужными свойствами, например с малым количеством листьев [60]. Специ-

альная форма деревьев облегчает нахождение комитета в задаче пропорцио-

нального представительства [61].

Однопиковые на окружности предпочтения определяются аналогично

классическим однопиковым предпочтениям. Все альтернативы располагают-

ся на окружности. Каждый агент имеет свою наилучшую альтернативу и наи-

худшую альтернативу. Вдоль пути от наихудшей альтернативы до наилучшей

альтернативы упорядочены по возрастанию предпочтительности. Альтерна-

тивы с разных сторон от наилучшей (наихудшей) альтернативы могут быть

упорядочены любым способом.

Всего существуют^(m-1)!2 доменов однопиковых на окружности предпо-

чтений, в каждом из которых m2^m-2 линейных порядков. Следующие три

конфигурации характеризуют однопиковые на окружности предпочтения.

Конфигурация 4. Существуют два агента i, j ∈ N и пять альтернатив

a, b, c, d, e ∈ A такие, что выполнено {a, b}P_icP_i{d, e}, {a, e}P_j cP_j {b, d}.

Конфигурация 4 задает паттерн перестановок, называемый квадратными

перестановками [62].

Конфигурация 5. Существуют три агента i, j, k ∈ N и четыре альтернативы

a, b, c, d ∈ A такие, что выполнено {a, b}P_i{c, d}, {a, c}P_j {b, d}, {a, d}P_k {b, c}.

Конфигурация 6. Существуют три агента i, j, k ∈ N и четыре альтернативы

a, b, c, d ∈ A такие, что выполнено {a, b}P_i{c, d}, {b, c}P_j {a, d}, {c, a}P_k {b, d}.

Теорема 4 [37]. Профиль предпочтений является однопиковым на

окружности тогда и только тогда, когда он не содержит конфигураций 4,

5 и 6.

Зная количество доменов и количество линейных порядков в каждом до-

мене, получим приблизительное число однопиковых на окружности профи-

лей предпочтений.

Теорема 5. Количество однопиковых на окружности профилей предпо-

чтений асимптотически равно

(m - 1)!(

)_n

#SPC(m,n) ≈

m2^m-2

Однопиковые на окружности предпочтения имеют главным образом вы-

числительные приложения в области задачи пропорционального представи-

тельства [37].

Еще более широкий класс предпочтений моделируется предпочтениями,

близкими к однопиковым. Это класс предпочтений, которые сводятся к одно-

пиковым предпочтениям после удаления либо k альтернатив, либо k агентов,

либо разбиения множества агентов или альтернатив на k частей, либо транс-

формации предпочтений через k парных инверсий последовательно стоящих

альтернатив в некоторых предпочтениях и т.д. Параметр k в данном опреде-

лении служит мерой, характеризующей расстояние данного профиля до бли-

жайшего однопикового профиля. Для разных целей такое расстояние мож-

но определить по-разному (удаление агентов, удаление альтернатив и т.д.).

Основной проблемой данного подхода является сложность определения при-

надлежности профиля к тому или иному классу предпочтений. Значительное

число таких задач являются NP-трудными [63], но существуют алгоритмы ап-

проксимации [64]. В то же время некоторые классы предпочтений, близких

к однопиковым, выявляются просто и позволяют снизить сложность задач

манипулирования и контроля исхода голосования [65-72], задач пропорцио-

нального представительства [73], задачи ранжирования по Кемени [74].

Еще одним расширением однопиковых предпочтений являются однопико-

вые предпочтения при неполных данных [75]. Если исходные данные явля-

ются частичными порядками, а не линейными, то задача возможного вос-

становления предпочтений до однопикового профиля предпочтений является

NP-трудной. Если исходные данные представляют собой слабый порядок, то

существует алгоритм полиномиальной сложности для определения возмож-

ности восстановления профиля предпочтений до однопикового.

3.2. Сепарабельные предпочтения

К. Инада [23, 24] ввел свойство сепарабельности следующим образом. Про-

филь предпочтений является сепарабельным, если для любого подмножества

X ⊆ A, |X| ≥ 2 существует его разбиение на такие непустые подмножества

X^′,X\X^′, что для каждого агента i ∈ N имеем либо aP_ib для каждого a ∈ X^′,

b ∈ X\X^′, либо bP_ia для каждого a ∈ X^′, b ∈ X\X^′. Примерами максималь-

ных доменов сепарабельных предпочтений являются



















D₁ =

D₂ =











Все максимальные домены однопиковых предпочтений одинаково устрое-

ны, т.е. при фиксированном количестве альтернатив один домен можно по-

лучить из другого через переименование альтернатив. В отличие от однопи-

ковых, максимальные сепарабельные домены структурно отличаются друг

от друга и не могут быть сведены к одному домену через переименование

альтернатив (см. вышеприведенные примеры).

Множество сепарабельных профилей предпочтений замкнуто по отноше-

нию к операции удаления альтернатив из профиля. Таким образом, сужение

сепарабельного профиля предпочтений на любое подмножество альтернатив

является сепарабельным.

Множество альтернатив X ⊆ A называется множеством клонов для про-

филя P, если в предпочтении каждого агента альтернативы из X стоят по-

следовательно. Назовем нетривиальными множества клонов, состоящие из

более чем одной альтернативы и не совпадающие с множеством всех аль-

тернатив. К примеру, множества {1, 2} и {3, 4} являются нетривиальными

множествами клонов для D₁. Для D₂ такими множествами являются множе-

ства {3, 4} и {2, 3, 4}. Множества клонов объединяют альтернативы, которые

в некотором смысле близки друг к другу для каждого агента. Множества

клонов являются устоявшимся инструментом анализа в теории коллективно-

го выбора [76, 77].

Ацикличный ориентированный граф, в котором только одна вершина не

имеет входящих дуг, а остальные вершины имеют единственную входящую

дугу, является исходящим деревом. Вершина, не имеющая входящих дуг, яв-

ляется корнем. Вершины, не имеющие исходящих дуг, являются терминаль-

ными. Вершинно-индуцированным поддеревом является часть исходящего

дерева, которая содержит некоторую вершину дерева, всех потомков этой

вершины и соединяющие их дуги. Терминальные вершины и само исходящее

дерево являются вершинно-индуцированными поддеревьями.

Исходящее дерево T , в котором альтернативы являются листьями этого

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

иерархическим деревом, представляющим профиль сепарабельных предпо-

чтений P, если для каждого множества клонов X профиля P верно, что суще-

ствуют вершина и множество вершинно-индуцированных поддеревьев, в кор-

ни которых ведут последовательные исходящие дуги этой вершины, такие,

m - 1

Рис. 1. Иерархическое дерево для линейного порядка 12 . . . m.

что множеством листьев поддеревьев является множество X. Для каждой

вершины определен порядок исходящих дуг и, соответственно, порядок до-

черних вершин и вершинно-индуцированных поддеревьев, для которых дан-

ные вершины являются корневыми.

Планарное представление иерархического дерева отображает не только

дуги и вершины, но и порядок дуг. К примеру, рис. 1 представляет иерар-

хическое дерево для профиля предпочтений, состоящего из одного линейно-

го порядка 12 . . . m. Полукруглая стрелка отображает порядок дуг. В дан-

ном профиле предпочтений все множества вида {i, . . . , j}, где i < j, явля-

ются множествами клонов. Каждое множество клонов образует последова-

тельность терминальных вершин. Таким образом, для каждого множества

клонов существует множество вершинно-индуцированных поддеревьев, в кор-

ни которых ведут последовательные исходящие дуги, такое, что множеством

листьев поддеревьев является данное множество клонов. Инверсия поряд-

ка исходящих дуг не нарушает возможность нахождения нужной последо-

вательности исходящих дуг для каждого множества клонов. Способность

иерархического дерева и его планарного представления представлять про-

филь предпочтений инвариантна к операции инверсии порядка исходящих

дуг. Произвольная перестановка дуг может привести к невозможности на-

хождения множества последовательных дуг для некоторого множества кло-

нов. Рассматриваемый вид деревьев является частным случаем PQ-деревьев,

см. [78].

Классу бинарных иерархических деревьев со всевозможными порядками

исходящих дуг однозначно соответствует бинарное дерево с неупорядоченны-

ми дугами. Поэтому каждому максимальному сепарабельному домену соот-

ветствует бинарное дерево с неупорядоченными дугами. Построить это де-

рево для заданного домена можно следующим образом. Берется произволь-

ный линейный порядок из домена. Последовательно строятся иерархические

деревья для двух, трех и т.д. лучших альтернатив выбранного линейного

порядка. Алгоритм останавливается после построения иерархического дере-

ва для m альтернатив. Для двух альтернатив иерархическое дерево состоит

из корня и двух листьев. На каждом шаге это дерево дополняется новой

нетерминальной вершиной и новой терминальной вершиной следующим об-

разом. В дереве, построенном на предыдущем шаге, находятся вершина и

соответствующее ей вершинно-индуцированное поддерево такое, что множе-

ство листьев (альтернатив) этого поддерева соседствует с новой альтернати-

вой во всех сужениях линейных порядков домена на множество альтернатив

D₁

D₂

Рис. 2. Пример реализации алгоритма построения иерархического дерева аль-

тернатив для домена D1 и домена D2.

строящегося дерева (множество альтернатив предыдущего шага, объединен-

ное с новой альтернативой). Если найденная вершина не является корневой,

то новая вершина делит входящую дугу найденной вершины на две дуги, ина-

че к дереву достраиваются новый корень и дуга, соединяющая новый корень

со старым. Дополнительная дуга соединяет новую нетерминальную вершину

с новой терминальной вершиной.

Иллюстрация к алгоритму построения иерархических деревьев для доме-

нов D₁ и D₂, определенных в начале данного раздела, приведена на рис. 2.

В данном примере за основу взят линейный порядок 1234.

По иерархическому дереву можно восстановить максимальный сепара-

бельный домен. Для выбранного планарного представления дерева линейный

порядок, принадлежащий домену, можно построить рекурсивно, выполняя

поиск в глубину, начав от корня (согласно порядку исходящих дуг перебира-

ем исходящие дуги; для вершины, в которую ведет дуга, запускаем тот же

алгоритм; при нахождении терминальной вершины добавляем ее в линейный

порядок и возвращаемся к вершине, у которой еще остались нерассмотренные

дуги). Далее необходимо перебрать все инверсии интервалов построенного

линейного порядка, соответствующих всем вершинно-индуцированным под-

деревьям, и все построенные таким образом линейные порядки будут принад-

лежать сепарабельному домену. Каждый максимальный домен сепарабель-

ных предпочтений соответствует последовательному разбиению альтернатив

на два подмножества.

Для профиля сепарабельных предпочтений и для немаксимального домена

итеративный алгоритм построения иерархического дерева модифицируется.

Для описания алгоритма введем новое понятие. Минимальным покрытием

множества клонов X для профиля P является множество клонов C(X), ко-

торое содержит множество X, не совпадает с множеством X и не содержит в

качестве подмножества другое нетривиальное множество клонов, содержащее

множество X. Минимальное покрытие может быть не единственным, но ко-

личество минимальных покрытий не может превышать двух [77]. Например,

для профиля предпочтений, состоящего из одного линейного порядка 123,

имеем C ({1}) = {1, 2}, а для множества {2} минимальных покрытий будет

два: {1, 2} и {2, 3}.

Алгоритм построения иерархического дерева начинается с выбора одного

(произвольного) линейного порядка из профиля предпочтений или из немак-

симального домена и построения иерархического дерева для сужения про-

филя предпочтений на множество из двух лучших альтернатив выбранно-

го предпочтения. Для двух альтернатив иерархическое дерево состоит из

корня и двух листьев. Порядок дуг для данного дерева выбирается произ-

вольно. Далее на каждом шаге строится сужение профиля предпочтений

на новое подмножество альтернатив, добавляя следующую по предпочте-

нию альтернативу в выбранном линейном порядке. Таким образом, постро-

ен сепарабельный профиль предпочтений на некотором множестве альтерна-

тив, в котором одна из альтернатив является новой (альтернатива x). Эта

альтернатива является худшей в одном из линейных порядков. Существу-

ет единственное минимальное покрытие множества, состоящего из альтер-

нативы x.

Согласно определению сепарабельных предпочтений построенное мини-

мальное покрытие C({x}) можно разбить на два множества клонов. В силу

построения минимального покрытия данным разбиением являются множе-

ства {x} и C({x})\x.

Количество минимальных покрытий множества C({x})\x может быть рав-

но одному или двум. В первом случае верно, что C ({x}) = C (C ({x}) \x).

В этом случае дерево достраивается новой нетерминальной вершиной, но-

вой терминальной вершиной (альтернатива x) и новыми дугами способом,

описанным в алгоритме построения иерархического дерева для максималь-

ного сепарабельного домена. Порядок исходящих дуг новой нетерминаль-

ной вершины выбирается произвольно. Если дерево было бинарным, то оно

останется бинарным. Во втором случае дерево достраивается новой терми-

нальной вершиной и новой дугой таким образом, что новая терминальная

вершина является дочерней к той же вершине, что и вершина, являющая-

ся корневой для вершинно-индуцированного поддерева, листьями которо-

го является множество C ({x}) \x. Кроме того, новая терминальная вер-

шина будет одновременно соседней к вершине, являющейся корневой для

вершинно-индуцированного поддерева, листьями которого является множе-

ство C ({x}) \x, и крайней (первой или последней) в соответствующем поряд-

ке дочерних вершин. В этом случае итоговое иерархическое дерево не будет

бинарным.

Алгоритм останавливается после выполнения шага для наихудшей альтер-

нативы в выбранном линейном порядке.

Напитки

Холодные

Горячие

Мин. вода Сок

Чай

Кофе

Зеленый

Черный

Рис. 3. Иерархическое дерево альтернатив, взято из [79].

Разные профили сепарабельных предпочтений, как и разные немаксималь-

ные домены сепарабельных предпочтений, могут иметь одинаковые иерархи-

ческие деревья. В работе П. Фалишевского и др. [79] найдено количество про-

филей сепарабельных предпочтений с фиксированным количеством агентов

и альтернатив, приводящих к заданному иерархическому дереву, и описан

алгоритм равновероятной генерации таких профилей.

Пример иерархического дерева альтернатив представлен на рис. 3. Мно-

жество альтернатив соответствует множеству листьев дерева. Вершины де-

рева соответствуют категориям альтернатив, которые далее делятся на под-

категории. Согласно рис. 2 все множество напитков делится на холодные и

горячие. Каждый агент предпочитает все холодные напитки всем горячим,

или, наоборот, все горячие напитки всем холодным. Для каждого после-

дующего разбиения альтернатив одна подкатегория лучше другой того же

уровня.

Каждый из (2m - 3)! максимальных сепарабельных доменов содержит

2m-1 предпочтений. Каждый максимальный сепарабельный домен содержит

такое же количество линейных порядков, как и максимальный домен однопи-

ковых предпочтений, но так как количество сепарабельных доменов больше

количества однопиковых, то количество сепарабельных профилей предпочте-

ний превышает количество однопиковых профилей предпочтений.

Теорема 6 [29]. Количество сепарабельных профилей предпочтений

асимптотически равно

#GS(m, n) ≈ (2m - 3)!2^(m-1)n.

Конфигурация 7. Существуют три агента i, j, k ∈ N и три альтернативы

a, b, c ∈ A такие, что выполнено (aP_ibP_ic или cP_ibP_ia), (bP_j cP_j a или aP_j cP_j b),

(bP_kaP_kc или cP_kaP_kb).

Конфигурация 7 обеспечивает разнообразие медианных альтернатив. За-

прет на конфигурацию 7 ограничивает двумя количество альтернатив в

любой тройке, что соответствует одному из способов реализации ограниче-

ния (ii) из теоремы 1.

Конфигурация 8. Существуют два агента i, j ∈ N и четыре альтернативы

a, b, c, d ∈ A такие, что выполнено aP_ibP_icP_id и (bP_j dP_j aP_j c или cP_j aP_j dP_j b).

Конфигурация 8 задает паттерн перестановок, называемый сепарабельны-

ми перестановками (подробнее о сепарабельных перестановках см. в [80]).

Теорема 7 [54]. Профиль предпочтений является сепарабельным тогда

и только тогда, когда он не содержит конфигураций 7 и 8.

Конфигурация 9. Существуют два агента i, j ∈ N и четыре альтернативы

a, b, c, d ∈ A такие, что выполнено aP_ibP_icP_id и (bP_j aP_j dP_j c или cP_j dP_j aP_j b).

Конфигурация 9 используется в определении усиленно сепарабельных

предпочтений, чья характеризация представлена в теореме 9.

Теорема 8 [81]. Профиль предпочтений является усиленно сепарабель-

ным тогда и только тогда, когда он не содержит конфигураций 7, 8 и 9.

Усиленно сепарабельные предпочтения представляют интерес прежде все-

го с точки зрения их комбинаторных свойств [81].

Сепарабельные предпочтения упрощают классические задачи теории кол-

лективного выбора только в случае иерархических деревьев ограниченной

высоты [79]. Сепарабельные предпочтения создают условия для существова-

ния решения задачи случайного распределения неделимых объектов [82]. При

ограничении домена до лестничных предпочтений решение задачи становит-

ся единственным [83].

Домен предпочтений является лестничным, если существует слабый по-

рядок на множестве альтернатив, такой что каждый класс эквивалентности

состоит из одной или двух альтернатив, и предпочтения, входящие в домен,

являются линеаризацией данного слабого порядка. Лестничный домен мак-

симального размера содержит 2⌊

⌋ предпочтений. Лестничный домен пред-

почтений не является максимальным доменом Кондорсе, но в задаче рас-

пределения неделимых объектов не строится предпочтение коллектива и от-

ношение, порождаемое правилом простого большинства, не играет никакой

роли.

3.3. Предпочтения со свойством единственного пересечения

Домен предпочтений со свойством единственного пересечения характе-

ризуется линейным порядком (осью) на множестве агентов. Для каждой па-

ры альтернатив подмножества агентов, имеющие одинаковые предпочтения

на этой паре, составляют интервал на исходном линейном порядке агентов.

Таким образом, для каждой пары альтернатив при движении вдоль оси аген-

тов предпочтения меняются не более одного раза.

Домен предпочтений со свойством единственного пересечения естествен-

ным образом возникает при моделировании предпочтений относительно на-

логовых ставок [25, 26]. Домен предпочтений со свойством единственного пе-

ресечения упрощает решение некоторых задач пропорционального предста-

вительства [84].

Примерами доменов предпочтений со свойством единственного пересече-

ния являются



















D₃ =

D₄ =





 4 4 3 3 1 1 1

 4 4 4 1 1 1 1

Как и домены сепарабельных предпочтений, домены предпочтений со

свойством единственного пересечения разнообразны и структурно отличают-

ся друг от друга.

Конфигурация 10. Существуют три агента i, j, k ∈ N и не обязательно раз-

личные альтернативы a, b, c, d, e, f ∈ A такие, что выполнено bP_ia, cP_id, eP_if,

aP_j b, dP_j c, eP_j f, aP_kb, cP_kd, fP_ke.

Конфигурация 11. Существуют четыре агента i, j, k, l ∈ N и не обязательно

различные альтернативы a, b, c, d ∈ A такие, что выполнено aP_ib, cP_id, aP_jb,

dP_j c, bP_ka, cP_kd, bP_la, dP_lc.

Теорема 9 [85]. Профиль предпочтений обладает свойством единствен-

ного пересечения тогда и только тогда, когда он не содержит конфигура-

ций 10 и 11.

Запрещенные подпрофили содержат трех или четырех агентов, поэтому

все профили предпочтений с двумя агентами являются профилями предпо-

чтений со свойством единственного пересечения.

Каждый домен предпочтений со свойством единственного пересечения со-

ответствует максимальной цепи в слабом порядке Брухата, построенном на

множестве линейных порядков с отношением вложенности множеств пар аль-

тернатив, которые имеют обратный порядок по отношению к минимальному

элементу. Таким образом, слабый порядок Брухата имеет два обратных друг

другу линейных порядка в качестве минимального и максимального элемен-

та. Каждый домен предпочтений со свойством единственного пересечения

содержит линейные порядки, образующие цепь от минимального до макси-

мального элемента в слабом порядке Брухата. Каждый домен предпочте-

ний со свойством единственного пересечения содержит^m(m-1)2 + 1 предпо-

чтений [85]. Согласно [86], количество максимальных цепей в слабом порядке

Брухата равно

(m)

1m-13^m-25^m-3 . . . (2m - 3)¹

Далеко не все домены предпочтений со свойством единственного пересе-

чения являются максимальными доменами Кондорсе. Для каждого числа

альтернатив только два домена являются одновременно доменами предпо-

чтений со свойством единственного пересечения и максимальными доменами

Кондорсе [87].

Для трех альтернатив количество профилей предпочтений со свойством

единственного пересечения выше количества однопиковых профилей пред-

почтений и количества сепарабельных профилей предпочтений, но для боль-

шего числа альтернатив верно обратное. Теорема 11 раскрывает причины

большого количества профилей предпочтений со свойством единственного

пересечения для трех альтернатив.

Теорема 10. Профиль предпочтений с тремя альтернативами являет-

ся профилем предпочтений со свойством единственного пересечения тогда

и только тогда, когда он является однопиковым или однолунковым.

Предпочтения со свойством единственного пересечения имеют много рас-

ширений: предпочтения со свойством единственного пересечения на дере-

ве [88], на графах [89], предпочтения, близкие к предпочтениям со свойством

единственного пересечения [63, 90-92], это предпочтения, которые сводятся к

предпочтениям со свойством единственного пересечения после удаления либо

k альтернатив, либо k агентов, либо разбиения множества агентов или аль-

тернатив на k частей, либо трансформация предпочтений через k парных за-

мен стоящих последовательно альтернатив в некоторых предпочтениях и т.д.,

предпочтения со свойством единственного пересечения при неполной инфор-

мации [93].

Предпочтения со свойством единственного пересечения фиксируют неко-

торое упорядочение агентов, которое можно сравнить с распределением аген-

тов (избирателей) по уровню дохода, образования и т.д., тем самым можно

найти объяснение существующим предпочтениям. Исследованию корреляция

предпочтений со свойством единственного пересечения и экзогенных атрибу-

тов посвящена работа [94].

Конфигурация 12 (минимальное разнообразие). Для каждой альтернати-

вы существует порядок предпочтений с данной альтернативой в качестве мак-

симальной.

Теорема 11 [95]. Профиль предпочтений со свойством единственного

пересечения, содержащий конфигурацию 12, является однопиковым.

Теорема 12 [95]. Профиль предпочтений со свойством единственного

пересечения является однопиковым, если и только если он может быть

дополнен предпочтениями, при которых дополненный профиль будет про-

филем предпочтений со свойством единственного пересечения и будет со-

держать конфигурацию 12.

Теорема 12 характеризует домены, являющиеся пересечением однопико-

вого домена предпочтений и домена предпочтений со свойством единствен-

ного пересечения. Интерес к этому домену возник, потому что он близок к

домену евклидовых предпочтений, которому посвящен следующий раздел.

3.4. Одномерные евклидовые предпочтения

Если не оговорено иное, то в данном разделе под евклидовыми предпо-

чтениями подразумеваются одномерные евклидовые предпочтения. Профиль

предпочтений является евклидовым, если существует ось, на которой распо-

ложены альтернативы и идеальные точки агентов такие, что предпочтения

агентов формируются исходя из геометрической близости альтернатив. Каж-

дый агент предпочитает более близкие к его идеальной точке альтернати-

вы более отдаленным. Не для каждого профиля однопиковых предпочтений

можно найти координаты альтернатив и агентов таким образом, чтобы он

стал евклидовым [96].

Именно евклидовые предпочтения используются во многих моделях про-

странственной экономики, в том числе в модели линейного города Г. Хо-

теллинга [97], и моделях политической конкуренции, берущих свое начало

из модели Э. Даунса [98].

Теорема 13 [99]. Для числа альтернатив, не превышающего пяти, про-

филь предпочтений является евклидовым тогда и только тогда, когда он

является одновременно однопиковым и профилем предпочтений со свой-

ством единственного пересечения.

Начиная с шести альтернатив, все евклидовые профили предпочтений яв-

ляются одновременно однопиковыми и профилями предпочтений со свой-

ством единственного пересечения, но существуют примеры, когда обратное

неверно. Для примера достаточно трех агентов.

Теорема 14 [99]. Для двух агентов профиль предпочтений является ев-

клидовым тогда и только тогда, когда он является однопиковым.

Теорема 15 [100]. Не существует конечного числа запрещенных подпро-

филей, характеризующих евклидовые профили предпочтений.

Теорема 15 не запрещает характеризацию через бесконечное количество

запрещенных подпрофилей. Такая характеризация могла бы быть достаточно

компактна и применима в прикладных исследованиях, как, например, харак-

теризация матриц со свойством последовательных единиц [101]. Несмотря на

отсутствие характеризации через конечное число запрещенных подпрофилей

существует алгоритм полиномиальной сложности для распознавания евкли-

довых профилей предпочтений [102, 103].

Естественным обобщением евклидовых предпочтений являются многомер-

ные евклидовые предпочтения, в которых альтернативы и идеальные точки

агентов представлены точками в многомерном евклидовом пространстве, но

задача распознавания профиля k-мерных евклидовых предпочтений стано-

вится NP-трудной для любого k > 1 [104].

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

Данные предпочтения нашли применение в теории отраслевых рынков [105]

и политической конкуренции [106].

4. Структурированные предпочтения в задаче о марьяже

Рассмотрим два конечных и непересекающихся множества: множество

женщин W = {w₁, . . . , w_n} и множество мужчин M = {m₁, . . . , m_n}. Каждый

агент i ∈ W ∪ M имеет предпочтение на множестве агентов другого пола

(предпочтения являются линейными порядками). Проблема состоит в том,

чтобы создать такие пары мужчина-женщина, которые агенты хотели бы со-

хранить.

Задача о марьяже это кортеж (W, M, P), который состоит из множе-

ства женщин, множества мужчин и профиля предпочтений, состоящего из 2n

линейных порядков. Паросочетанием называется отображение µ : W ∪ M →

→ W ∪ M такое, что ∀w ∈ W имеем µ(w) ∈ M и µ(µ(w)) = w, и ∀m ∈ M

имеем µ(m) ∈ W и µ (µ (m)) = m. Паросочетание µ называется устойчивым,

если не существует блокирующей пары, т.е. пары (X, x) ∈ W × M такой, что

XP_xµ(x) и xP_Xµ(X). Устойчивое паросочетание является решением задачи

о марьяже. Доказательство существования решения задачи о марьяже и ал-

горитм построения устойчивого паросочетания были получены Д. Гейлом и

Л. Шепли в [107].

Пара, которая предпочитает друг друга всем остальным агентам проти-

воположного пола, называется фиксированной парой. В любом устойчивом

паросочетании агенты из каждой фиксированной пары будут сопоставлены

друг другу. Я. Экхоут [108] сформулировал условие последовательных пред-

почтений: существуют перестановка женщин σ и перестановка мужчин τ

такие, что

∀i, j ∈ {1, . . . , n} таких, что j > i, имеем m_τ(i)Pwσ(i) m_τ(j),

∀i, j ∈ {1, . . . , n} таких, что j > i, имеем w_σ(i)Pmτ(i) w_σ(j).

Из условия последовательных предпочтений следует существование фик-

сированной пары (w_σ(1), m_τ(1)).

Теорема 16 [108]. Условие последовательных предпочтений является

достаточным условием единственности устойчивого паросочетания.

Перестановки из условия последовательных предпочтений определяют па-

(

)

росочетание µ

m_τ(i)

= w_σ(i). Условие последовательных предпочтений до-

пускает, что агент предпочитает кого-либо своей паре из паросочетания, но

только если предпочитаемые находятся ¾выше¿ в соответствующем переста-

новке линейном порядке. Представим, что мужчины и женщины упорядо-

чены по росту и каждый агент стоит в паре с агентом противоположного

пола такого же ранга по росту. Если для каждого агента среди агентов, ко-

торые лучше его/ее пары из паросочетания, только агенты выше ростом, то

построенное по рангам паросочетание является единственным устойчивым

паросочетанием. Докажем следующую теорему.

Теорема 17. Вероятность появления профиля, удовлетворяющего усло-

вию последовательных предпочтений, удовлетворяет следующему рекур-

рентному соотношению:

∑

(n)2 (n - i)!

s (n) =

(-1)^n-i+1

s (i) ,

n^2(n-i)

i=0

где

s (0) = 1.

Доказательство. Все профили предпочтений, удовлетворяющие усло-

вию последовательных предпочтений, можно разделить на множества рав-

ной мощности с профилями предпочтений, различающиеся итоговым паро-

сочетанием. Все профили предпочтений с данным паросочетанием можно

разделить на множества с разным количеством фиксированных пар. Су-

(_n)

ществует

способов выбрать i пар. После исключения данных i пар

получается профиль предпочтений с n - i парами и этот профиль будет

удовлетворять условию последовательных предпочтений. Для данного про-

(_n)2(n-i)

филя предпочтений меньшего размера существует

i!^2(n-i) способов

добавить i пар в профиль и (n - 1)!²ⁱ способов определить предпочтения

i пар агентов. Применяя принцип включения-исключения, получим количе-

ство профилей предпочтений, удовлетворяющих условию последовательных

предпочтений,

∑

)_2(n-i)

(n)(n

SPC (n) = n!

(-1)ⁱ⁺¹

i!^2(n-i)(n - 1)!²ⁱSP C(n - i),

i=1

где

SPC (0) = 1.

Вычисляя вероятность

SPC (n)

s (n) =

n!²ⁿ

и вводя новый индекс суммирования i^′ = n - i, получим итоговый резуль-

тат. ■

Карпов [109] предложил более общее условие единственности устойчивого

паросочетания: α-условие. Существуют устойчивое паросочетание µ, переста-

новка женщин σ и перестановка мужчин τ такие, что

∀i, j ∈ {1, . . . , n} таких, что j > i, имеем µ(w_σ(i))Pwσ(i) m_τ(j),

и перестановка женщин σ^′ и перестановка мужчин τ^′ такие, что

∀i, j ∈ {1, . . . , n} таких, что j > i, имеем µ(m_τ′_(i))Pmτ′(i) w_σ′_(j).

Пример из [109]. Данный профиль предпочтений

w₁ : m₁Pw1 m₃Pw1 m₂, m₁ : w₃Pm1 w₁Pm1 w₂;

w₂ : m₁Pw2 m₂Pw2 m₃, m₂ : w₂Pm2 w₁Pm2 w₃;

w₃ : m₂Pw3 m₃Pw3 m₁, m₃ : w₂Pm3 w₃Pm3 w₁;

нарушает условие последовательных предпочтений, так как не имеет

фиксированной пары, но имеет единственное устойчивое паросочетание

w₁ ↔ m₁, w₂ ↔ m₂, w₃ ↔ m₃. Данный профиль удовлетворяет α-условию при

σ = τ = 123 и σ^′ = τ^′ = 231.

Теорема 18 [109]. α-Условие является достаточным условием един-

ственности устойчивого паросочетания.

α-Условие позволяет иметь различные критерии для построения упорядо-

чений. Пусть кроме профиля предпочтений агентов, имеются два упорядо-

чения, выражающие соответственно ¾женский взгляд¿ и ¾мужской взгляд¿.

Например, женщины упорядочивают всех по росту, а мужчины по возрас-

ту. В α-условии первое упорядочение определяет перестановки σ и τ, второе

упорядочение перестановки σ^′ и τ^′. Представим, что мужчины и женщины

упорядочены по данным критериям и каждый агент стоит в паре с агентом

противоположного пола такого же ранга согласно критерию своего пола. Если

для каждого агента среди агентов, которые лучше его/ее пары согласно па-

росочетанию, только агенты выше по критерию для соответствующего пола,

то построенное по рангам паросочетание является единственным устойчивым

паросочетанием. α-Условие находит применение для создания децентрализо-

ванных алгоритмов на рынках соответствия [110, 111].

5. Дихотомические предпочтения

Дихотомические предпочтения задаются разбиением множества альтер-

натив на два подмножества: поддерживаемые альтернативы и неприемлемые

альтернативы.

Дихотомические предпочтения используются в одобряющем голосовании

[112], в задаче пропорционального представительства [113], в задаче нахож-

дения паросочетаний [114], в задаче распределения ресурсов [115, 116], в ге-

донических играх [117] и других приложениях.

Несмотря на простую структуру многие вычислительные задачи, связан-

ные с дихотомическими предпочтениями, оказываются NP-трудными, что

привело к созданию теории доменов дихотомических предпочтений ограни-

чений на множество возможных предпочтений. Э. Элкинд и М. Лакнер [118]

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

приводят к упрощению вычислительных задач пропорционального предста-

вительства.

Как и прежде, имеем множество альтернатив A = {1, . . . , m} и множество

агентов N = {1, . . . , n}. Каждый агент i ∈ N одобряет множество A_i ⊆ A. Со-

ставим матрицу X размера m на n, в которой x_ij = 1, если агент i одобряет

альтернативу j, и x_ij = 0, если агент j не одобряет альтернативу i. Матри-

ца X_m×n представляет собой профиль предпочтений. Множество всех воз-

можных бинарных матриц размера m × n будем обозначать как M_m×n. Су-

ществуют 2^mn различных матриц и, соответственно, различных профилей

предпочтений. Доменом предпочтений называется подмножество возможных

столбцов в бинарной матрице.

Будем говорить, что матрицы X и Y эквивалентны с обозначением,

X ≡ Y , если матрица X равна матрице Y после перестановки строк и столб-

цов:

X ≡ Y тогда и только тогда, когда x_ij = y_σ(i)τ(j), σ(i) ∈ S_m, τ(j) ∈ S_n, где

S_k множество всех перестановок на множестве {1,... ,k}.

Матрица Q_k×l является паттерном в матрице A_m×n, если существует под-

матрица B_k×l матрицы A_m×n такая, что Q_k×l ≡ B_k×l. Паттерны играют роль

конфигураций в ординальных предпочтениях.

Для каждого линейного порядка можно определить множество дихотоми-

ческих предпочтений, которые могут быть достигнуты при некотором уровне

одобрения агентом.

Для однопиковых предпочтений множества одобрения (некоторое количе-

ство наилучших альтернатив) обязательно образуют интервал на оси альтер-

натив (понятие оси однопиковых предпочтений введено в разделе 3.1). Та-

ким образом, получим домен предпочтений с последовательными единицами

в столбцах (интервалы кандидатов).

Паттерн 1.





























∈ M_k+2×k+2, k ≥ 1.















···



Паттерн 2.







1

























∈ M_k+2×k+3, k ≥ 1.











···

1









Паттерн

































∈ M_k+3×k+2, k ≥ 1.





















Паттерн























.









Паттерн















.









Теорема 19 [101]. Профиль дихотомических предпочтений удовлетво-

ряет свойству последовательных единиц в столбцах тогда и только тогда

профиль не содержит паттернов 1-5.

Характеристика из теоремы 21 содержит бесконечное число паттернов, но

так как паттерны схожи друг с другом, задача поиска паттерна минималь-

ного размера решается за полиномиальное время [119]. Существует простой

алгоритм для тестирования свойства последовательных единиц в матрице,

основанный на PQ-деревьях [78].

Транспонированные паттерны 1-5 дадут характеристику домена с после-

довательными единицами в строках (интервалы агентов), рассмотренного

в [118]. В литературе можно найти характеризации бинарных матриц с кру-

говым свойством последовательных единиц [120] со свойством последователь-

ных единиц на дереве [121].

З. Терзопулу и др. [122] исследовали домены предпочтений с ограничен-

ными интервалами агентов. Данные интервалы образуются только у краев

оси (домен предпочтений с внешними интервалами агентов, далее ВИА) или

только у одного края оси (домен предпочтений с одним внешним интервалом

агентов, далее ОВИА). В случае голосования за кандидатов от политических

партий избиратели могут быть упорядочены по степени лояльности к одной

из двух партий. Наиболее лояльные избиратели будут одобрять всех канди-

датов своей партии, менее лояльные избиратели могут одобрять некоторое

количество кандидатов обеих партий. Примером профиля предпочтений с

ВИА является























.









Каждый кандидат получает одобрение от интервала агентов, находящего-

ся у края оси.

Паттерн





1

.

Паттерн





0

.

Паттерн





1

.

Паттерн





0

.

Паттерн

10.

[

]

Теорема 20 [122]. Профиль дихотомических предпочтений удовлетво-

ряет свойству ВИА тогда и только тогда профиль не содержит паттер-

нов 6-10.

Паттерн 11.

[

]

Теорема 21 [122]. Профиль дихотомических предпочтений удовлетво-

ряет свойству ОВИА тогда и только тогда профиль не содержит пат-

терна 11.

Матрицы, не содержащие паттерна 11, могут быть однозначно восстанов-

лены по их суммам строк и столбцов [123].

Теорема 22 [123]. Количество профилей дихотомических предпочте-

ний, удовлетворяющих свойству ОВИА, равно

min(m,n)∑

#SV EI (m,n) =

k!²S (n + 1,k + 1) S (m + 1,k + 1),

k=1

где S (a, b)

число Стирлинга второго рода (см. [124]).

В [122] рассмотрены также достаточные и необходимые условия нахож-

дения структурированных дихотомических предпочтений в случае неполной

информации, когда не имеется информации о некоторых ячейках в профиле

предпочтений. В [125] расширено возможное применение интервальных на

оси предпочтений до интервальных на деревьях.

Другим примером структурированных дихотомических предпочтений яв-

ляется разбиение. Профиль дихотомических предпочтений удовлетворяет

свойству разбиения, если множество одобрения каждого агента совпадает с

одним из множеств, принадлежавших некоторому разбиению множества аль-

тернатив.

Паттерн 12.

[

]

Теорема 23 [122]. Профиль дихотомических предпочтений удовлетво-

ряет свойству ОВИА тогда и только тогда профиль не содержит пат-

терна 12.

Теорема 24 [126]. Количество профилей дихотомических предпочте-

ний, удовлетворяющих свойству ОВИА, равно

min(m,n)∑

#PART (m,n) =

k!S (n, k) S (m, k),

k=1

где S (a, b)

число Стирлинга второго рода (см. [124]).

Свойство разбиения является очень ограничивающим и количество про-

филей, удовлетворяющих этому свойству меньше, чем количество профилей,

удовлетворяющих свойству ОВИА.

6. Заключение

С одной стороны, структурированные профили предпочтений представля-

ют собой очень ограниченное сочетание предпочтений и не могут отражать

разнообразие мнений в реальных проблемах агрегирования. С другой сторо-

ны, модели, основанные на структурированных предпочтениях, обычно дают

решения с хорошими свойствами. Задача расширения доменов структуриро-

ванных предпочтений с целью повышения числа охватываемых профилей при

сохранении нужных свойств остается открытой. Множество попыток расши-

рения сталкиваются как с вычислительными сложностями, так и с пробле-

мами в интерпретации.

Перспективными, но мало затронутыми областями моделирования пред-

почтений являются исследования неполных предпочтений, а именно предпо-

чтений, представимых слабыми или частичными порядками, предпочтений,

имеющих линейный порядок на подмножестве альтернатив и т.д. Анализ ди-

хотомических предпочтений, представленный в обзоре, является первым ша-

гом в этом направлении.

Естественным направлением исследований является анализ реальных

данных по профилям предпочтений. Библиотеки профилей предпочтений

[127, 128] являются отправной точкой для многих исследований в этой об-

ласти.

Автор благодарит Ф.Т. Алескерова, участников Общемосковского семина-

ра “Экспертные оценки и анализ данных” 11 марта 2020 г. в ИПУ РАН, участ-

ников семинара “Математическая экономика” ЦЭМИ РАН 9 ноября 2021 г.

и анонимного рецензента за ценные комментарии.

СПИСОК ЛИТЕРАТУРЫ

1. Aleskerov F.T. Arrovian aggregation models. Dordrecht: Kluwer Academic Pub-

lisher, 1999.

2. Arrow K.J. Social Choice and Individual Values. New York: Wiley, 1951.

3. Gibbard A. Manipulation of voting schemes: a general result // Econometrica. 1973.

V. 41. No. 4. P. 587-601.

4. Satterthwaite M.A. Strategy-proofness and Arrow’s conditions: Existence and cor-

respondence theorems for voting procedures and social welfare functions // J. Econ.

Theory. 1975. V. 10. No. 2. P. 187-217.

5. Dasgupta P., Maskin E. On the robustness of majority rule // J. Eur. Econ. Assoc.

2008. V. 6. No. 5. P. 949-973.

6. Xefteris D. How robust is majority voting as a social choice rule? // Oxf. Econ.

Pap. 2014. V. 66. No. 4. P. 1006-1018.

7. Asan G., Sanver M.R. Another characterization of the majority rule // Econ. Lett.

2002. V. 75. No. 3. P. 409-413.

8. Campbell D.E., Kelly J.S. A simple characterization of majority rule // Econ. The-

ory. 2000. V. 15. No. 3. P. 689-700.

Dasgupta P., Maskin E. Strategy-proofness, independence of irrelevant alternatives,

and majority rule // Amer. Econ. Rev. Insights. 2020. V. 2. No. 4. P. 459-474.

10.

May K.O. A set of independent necessary and sufficient conditions for simple ma-

jority decisions // Econometrica. 1952. V. 20. No. 4. P. 680-684.

11.

Woeginger G.J. A new characterization of the majority rule // Econ. Lett. 2003.

V. 81. No. 1. P. 89-94.

12.

Gehrlein W.V. Condorcet’s paradox. Heidelberg: Springer, 2006.

13.

Xefteris D. A necessary and sufficient single-profile condition for transitivity of the

majority rule relation // Econ. Lett. 2012. V. 116. No. 3. P. 516-518.

14.

Aleskerov F. Categories of Arrovian voting schemes / Arrow K., Sen A., Suzu-

mura K., Eds. Handbook of Social Choice and Welfare, Amsterdam: Elsevier Sci-

ence. 2002. P. 95-129.

15.

Dittrich T. Eine vollständige Klassifkation von Condorcet Domains für kleine Al-

ternativenmengen. Karlsruher Instituts für Technologie (KIT), Dissertation, 2018.

16.

Li G., Puppe C., Slinko A. Towards a classification of maximal peak-pit Condorcet

domains // Math. Soc. Sci. 2021. V. 113. P. 191-202.

17.

Galambos

Á., Reiner V. Acyclic sets of linear orders via the Bruhat orders // Soc.

Choice Welf. 2008. V. 30. P. 245-264.

18.

Danilov V.I., Koshevoy G.A. Maximal Condorcet domains // Order. 2013. V. 30.

No. 1. P. 181-194.

19.

Danilov V.I., Karzanov A.V., Koshevoy G.A. Condorcet domains of tiling type //

Discrete Appl. Math. 2012. V. 160. P. 933-940.

20.

Karpov A., Slinko A. Constructing large peak-pit Condorcet domains // Theory

Decis. 2022. https://doi.org/10.1007/s11238-022-09878-9

21.

Поляков Н.Л., Шамолин М.В. Теоремы о редукции в теории коллективного

выбора // Итоги науки и техн. Сер. Соврем. мат. и ее прилож. Темат. обзор.

2020. Т. 174. С. 46-51.

22.

Danilov V.I., Karzanov A.V., Koshevoy G.A. Majority rule on rhombus tilings and

Condorcet super-domains // Discrete Appl. Math. 2021. V. 292. P. 85-96.

23.

Inada K. A Note on the simple majority decision rule // Econometrica. 1964. V. 32.

No. 4. P. 525-531.

24.

Inada K. The simple majority decision rule // Econometrica. 1969. V. 37. No. 3.

P. 490-506.

25.

Sen A.K. A Possibility theorem on majority decisions // Econometrica. 1966. V. 34.

No. 2. P. 491-499.

26.

Mirrlees J. An exploration in the theory of optimal income taxation // Rev. Econ.

Stud. 1971. V. 38. P. 175-208.

27.

Roberts K. Voting over income tax schedules // J. Public Econ. 1977. V. 8. No. 3.

P. 329-340.

28.

Elkind E., Lackner M., Peters D. Structured preferences / Endriss U. (ed), Trends

in computational social choice. 2017. P 187-207.

29.

Karpov A. On the number of group-separable preference profiles // Group Decis.

Negot. 2019. V. 28. No. 3. P. 501-517.

30.

Chen J., Finnendahl U.P. On the number of single-peaked narcissistic or single-

crossing narcissistic preference profiles // Discrete Math. 2018. V. 341. P. 1225-

1236.

31.

Durand S. Finding sharper distinctions for conditions of transitivity of the majority

method // Discrete Appl Math. 2003. V. 131. P. 577-595.

32.

Karpov A. The likelihood of single-peaked preferences under classical and new prob-

ability distribution assumptions // Soc. Choice Welf. 2020. V. 55. P. 629-644.

33.

Lackner M.L., Lackner M. On the likelihood of single-peaked preferences // Soc.

Choice Welf. 2017. V. 48. No. 4. P. 717-745.

34.

Kim K.H., Roush F.W. Special domains and nonmanipulability // Math. Soc. Sci.

1980. V. 1. P. 85-92.

35.

Sato S. Circular domains // Rev. Econ. Des. 2010. V. 14. P. 331-342.

36.

Achuthankutty G., Roy S. Dictatorship on top-circular domains // Theory Decis.

2018. V. 86. P. 479-493.

37.

Peters D., Lackner M. Preferences single-peaked on a circle // J. Artif. Intel. Res.

2020. V. 68. P. 463-502.

38.

Ozdemir U., Sanver M.R. Dictatorial domains in preference aggregation // Soc.

Choice Welf. 2007. V. 28. P. 61-76.

39.

Monjardet B. Acyclic domains of linear orders: a survey / Brams S., Gehrlein W.V.,

Roberts F.S., Eds. The mathematics of preference, choice and order, Essays in honor

of Peter C. Fishburn, Heidelberg: Springer. 2009. P. 139-160.

40.

Fishburn P.C. Acyclic sets of linear orders // Soc. Choice Welf. 1996. V. 14.

P. 113-124.

41.

Данилов В.И., Карзанов А.В., Кошевой Г.А. Области Кондорсе и ромбические

паркеты // Экономика и математические методы. 2010. Т. 46. № 4. С. 55-68.

42.

Labbe J.-P., Lange C. Cambrian acyclic domains: Counting c-singletons // Order.

2020. V. 37. P. 571-603.

43.

Kreweras G. Les décisions collectives // Math. Sci. hum. 1963. V. 2. P. 25-35.

44.

Bartholdi J., Trick M. Stable matching with preferences derived from a psycholog-

ical model // Oper. Res. Lett. 1986. V. 5. No. 4. P. 165-169.

45.

Escoffier B., Lang J., Ozturk M. Single-peaked consistency and its complexity /

Ghallab M., Spyropoulos C.D., Fakotakis N., Avouris N., Eds. Proc. of 18th Eur.

Conf. on Artif. Intel. (ECAI 2008), 2008. P. 366-370.

46.

Black D. On the rationale of group decision-making // J. Polit. Econ. 1948. V. 56.

P. 23-34.

47.

Brandt F., Brill M., Hemaspaandra E., Hemaspaandra L.A. Bypassing combina-

torial protections: Polynomial-time algorithms for single-peaked electorates // J.

Artif. Intel. Res. 2015. V. 53. P. 439-496.

48.

Faliszewski P., Hemaspaandra E., Hemaspaandra L.A., Rothe J. The shield that

never was: Societies with single-peaked preferences are more open to manipulation

and control // Inf. Comput. 2011. V. 209. No. 2. P. 89-107.

49.

Веселова Ю.А. Вычислительная сложность манипулирования: обзор пробле-

мы // АиТ. 2016. № 3. С. 7-32.

Veselova Y.A. Computational complexity of manipulation: A survey // Autom.

Remote Control. 2016. V. 77. No. 3. P. 369-388.

50.

Puppe C. The single-peaked domain revisited: A simple global characterization //

J. Econ. Theory. 2018. V. 176. P. 55-80.

51.

Slinko A. Condorcet domains satisfying Arrow’s single-peakedness // J. Math. Econ.

2019. V. 84. P. 166-175.

52.

Liversidge G. Counting Condorcet domains. arXiv:2004.00751, 2020.

53.

Weisstein E.W. Permutation pattern. From MathWorld-A Wolfram Web Resource.

2020. https://mathworld.wolfram.com/PermutationPattern.html

54.

Ballester M.A., Haeringer G. A characterization of the single-peaked domain //

Soc. Choice Welf. 2011. V. 36. P. 305-322.

55.

Demange G. Single-peaked orders on a tree // Math. Soc. Sci. 1982. V. 3. No. 4.

P. 389-396.

56.

Nehring K., Puppe C. The structure of strategy-proof social choice part i: General

characterization and possibility results on median spaces // J. Econ. Theory. 2007.

V. 135. No. 1. P. 269-305.

57.

Escoffier B., Spanjaard O., Tydrichová M. Recognizing single-peaked preferences on

an arbitrary graph: Complexity and algorithms / Harks T., Klimm M. Eds. Proc.

of the 13th Internat. Symposium, SAGT 2020, Augsburg, 2020. P. 291-306.

58.

Trick M.A. Recognizing single-peaked preferences on a tree // Math. Soc. Sci. 1989.

V. 17. No. 3. P. 329-334.

59.

Sliwinski J., Elkind E. Preferences single-peaked on a tree: Sampling and tree recog-

nition / Kraus S. Ed. Proc. of the Twenty-Eighth Internat. Joint Conf. on Artif.

Intel. (IJCAI-19). P. 580-586.

60.

Peters D., Elkind E. Preferences single-peaked on nice trees / Proc. of the 30th

AAAI Conf. on Artif. Intel. (AAAI 2016), 2016. P. 594-600.

61.

Peters D., Yu L., Chan H., Elkind E. Preferences single-peaked on a tree: Multiwin-

ner elections and structural results // J. Artif. Intel. Res. 2022. V. 73. P. 231-276.

62.

Duchi E. A code for square permutations and convex permutominoes // Discrete

Math. Theor. Comput. Sci. 2019. V. 21. No. 2. #2.

63.

Erdelyi G., Lackner M., Pfandler A. Computational aspects of nearly single-peaked

electorates // J. Artif. Intel. Res. 2017. V. 58. P. 297-337.

64.

Sui X., Nienaber A., Boutilier C. Multidimensional single-peaked consistency and

its approximations / Rossi F. Ed. Proc. of the Twenty-third Internat. Joint Conf.

on Artif. Intel. (IJCAI-13), pp. 367-374, Beijing, 2013. P. 375-382.

65.

Faliszewski P., Hemaspaandra E., Hemaspaandra L.A. The complexity of manip-

ulative attacks in nearly single-peaked electorates // Artif. Intell. 2014. V. 207.

P. 69-99.

66.

Menon V., Larson K. Reinstating combinatorial protections for manipulation and

bribery in single-peaked and nearly single-peaked electorates / Proc. of the 30th

AAAI Conf. on Artif. Intel. (AAAI. 2016), 2016. P. 565-571.

67.

Yang Y. Manipulation with bounded single-peaked width: A parameterized study /

Bordini R.H., Elkind E., Weiss G., Yolum P. Eds. Proc. of the 13th Internat. Joint

Conf. on Autonomous Agents and Multiagent Systems, 2015. P. 77-85.

68.

Yang Y. Complexity of controlling nearly single-peaked elections revisited / Das-

tani M., Sukthankar G., Andrй E., Koenig S. Eds. Proc. of the 17th Internat. Conf.

on Autonomous Agents and Multiagent Systems (AAMAS 2018), 2018. P. 2139-

2141.

69.

Yang Y. On the complexity of constructive control under nearly single-peaked pref-

erences / Proc. of the 24th Eur. Conf. on Artif. Intel. (ECAI 2020), Santiago de

Compostela, 2020.

70.

Yang Y., Guo J. Controlling elections with bounded single-peaked width / Lomuscio

A., Scerri P., Bazzan A., Huhns M. Eds. Proc. of the 13th Internat. Conf. on Au-

tonomous Agents and Multiagent Systems (AAMAS 2014), Paris, 2014. P. 629-636.

71.

Yang Y., Guo J. The control complexity of r-approval: From the single-peaked case

to the general case // J. Comput. Syst. Sci. 2017. V. 89. P. 432-449.

72.

Yang Y., Guo J. Parameterized complexity of voter control in multi-peaked elec-

tions // Theory Comput. Syst. 2018. V. 62. No. 8. P. 1798-1825.

73.

Cornaz D., Galand L., Spanjaard O. Bounded single-peaked width and proportional

representation / Proc. of the 24th Eur. Conf. on Artif. Intel. (ECAI 2020), 2012.

P. 270-275.

74.

Cornaz D., Galand L., Spanjaard O. Kemeny elections with bounded single-peaked

or single-crossing width / Proc. of the Twenty-Third Internat. Joint Conf. on Artif.

Intel. (IJCAI-2013), 2013. P. 76-82.

75.

Fitzsimmons Z., Lackner M. Incomplete preferences in single-peaked electorates //

J. Artif. Intell. Res. 2020. V. 67. P. 797-833.

76.

Tideman T.N. Independence of clones as a criterion for voting rules // Soc. Choice

Welf. 1987. V. 4. No. 3. P. 185-206.

77.

Elkind E., Faliszewski P., Slinko A. Clone structures in voters’ preferences / Proc. of

the 13th ACM Conf. on Electronic Commerce (EC-12), Valencia, 2012. P. 496-513.

78.

Booth K.S., Lueker G.S. Testing for the consecutive ones property, interval graphs,

and graph planarity using PQ-tree algorithms // J. Comput. Syst. Sci. 1976. V. 13.

P. 335-379.

79.

Faliszewski P., Karpov A., Obraztsova S. The complexity of election problems with

group-separable preferences // Auton. Agents Multi-Agent Syst. 2022. V. 36. Arti-

cle 18.

80.

Kitaev S. Separable permutations / Patterns in permutations and words. Mono-

graphs in Theoretical Computer Science. Berlin: Springer-Verlag, 2011. P. 57-66.

81.

Ferrari L. Enhancing the connections between patterns in permutations and forbid-

den configurations in restricted elections // J. Discrete Math. Sci. Cryptography.

2020. https://doi.org/10.1080/09720529.2020.1776932

82.

Liu P. Random assignments on sequentially dichotomous domains // Games Econ.

Behav. 2020. V. 121. P. 565-584.

83.

Liu P., Zeng H. Random assignments on preference domains with a tier structure //

J. Math. Econ. 2019. V. 84. P. 176-194.

84.

Skowron P., Yu L., Faliszewski P., Elkind E. The complexity of fully proportional

representation for single-crossing electorates // Theor. Comput. Sci. 2015. V. 569.

No. 2. P. 43-57.

85.

Bredereck R., Chen J., Woeginger G.J. A characterization of the single-crossing

domain // Soc. Choice Welf. 2013. V. 41. No. 4. P. 989-998.

86.

Stanley R.P. On the number of reduced decompositions of elements of Coxeter

groups // Eur. J. Combinatorics. 1984. V. 5. P. 359-372.

87.

Slinko A., Qinggong Wu, Xing Zheng Wu. A characterization of preference domains

that are single-crossing and maximal Condorcet // Economics Letters. 2021. V. 204.

N 109918.

88.

Puppe C., Slinko A. Condorcet domains, median graphs and the single-crossing

property// Econ. Theory. 2019. V. 67. No. 1. P. 285-318.

89.

Constantinescu A.C., Elkind E. Proportional representation under single-crossing

preferences revisited / Proc. of The Thirty-Fifth AAAI Conference on Artificial

Intelligence (AAAI-21), 2021. P. 5286-5293.

90.

Bredereck R., Chen J., Woeginger G.J. Are there any nicely structured preference

profiles nearby? // Math. Soc. Sci. 2016. V. 79. P. 61-73.

91.

Jaeckle F., Peters D., Elkind E. On recognising nearly single-crossing preferences /

Proc. of the 32nd AAAI Conf. on Artif. Intel. (AAAI-2018), 2018. P. 1079-1086.

92.

Cohen N., Elkind E., Lakhani F. Single-crossing implementation. arXiv:1906.09671,

2019.

93.

Elkind E., Faliszewski P., Lackner M., Obraztsova S. The complexity of recognizing

incomplete single-crossing preferences / Proc. Twenty-Ninth AAAI Conf. on Artif.

Intel. (AAAI-2015), Austin, 2015. P. 865-871.

94.

Lakhani F., Peters D., Elkind E. Correlating preferences and attributes: Nearly

single-crossing profiles / Proc. of the Twenty-Eighth Internat. Joint Conf. on Artif.

Intel. (IJCAI-19). P. 414-420.

95.

Elkind E., Faliszewski P., Skowron P. A characterization of the single-peaked single-

crossing domain // Soc. Choice Welf. 2020. V. 54. P. 167-181.

96.

Berg S., Perlinger T. Single-peaked compatible preference profiles: Some combina-

torial results // Soc. Choice Welf. 2006. V. 27. No. 1. P. 89-102.

97.

Hotelling H. Stability in competition // Econ. J. 1929. V. 153. No. 39. P. 41-57.

98.

Downs A. An economic theory of democracy. New York: Harper and Row, 1957.

99.

Chen J., Grottke S. Small one-dimensional Euclidean preference profiles // Soc.

Choice Welf. 2021. V. 57. P. 117-144.

100.

Chen J., Pruhs K.R., Woeginger G.J. The one-dimensional Euclidean domain:

finitely many obstructions are not enough // Soc. Choice Welf. 2017. V. 48.

P. 409-432.

101.

Tucker A. A structure theorem for the consecutive 1’s property // J. Comb. The-

ory B. 1972. V. 12. No. 2. P. 153-162.

102.

Knoblauch V. Recognizing one-dimensional Euclidean preference profiles // J.

Math. Econ. 2010. V. 46. P. 1-5.

103.

Elkind E., Faliszewski P. Recognizing 1-euclidean preferences: An alternative ap-

proach / Lavi R. Ed. Proc. of the 13th Internat. Symposium (SAGT 2014), Haifa,

2014. P. 146-157.

104.

Peters D. Recognising multidimensional Euclidean preferences. In Proc. of the 31st

AAAI Conf. on Artif. Intel. (AAAI-2017), 2017. P. 642-648.

105.

Salop S. Monopolistic Competition with Outside Goods // Bell J. Econ. 1979. V. 10.

P. 141-156.

106.

Peeters R., Saran R., Yuksel A.M. Strategic party formation on a circle and

Durverger’s law // Soc. Choice Welf. 2016. V. 47. P. 729-759.

107.

Gale D. Shapley L.S. College admissions and the stability of marriage // Amer.

Math. Month. 1962. V. 69. No. 1. P. 9-14.

108.

Eeckhout J. On the uniqueness of stable marriage matchings // Econ. Lett. 2000.

V. 69. No. 1. P. 1-8.

109.

Karpov A. A necessary and sufficient condition for uniqueness consistency in the

stable marriage matching problem // Econ. Lett. 2019. V. 178. P. 63-65.

110.

Sankararaman A., Basu S., Sankararaman K.A. Dominate or Delete: Decentral-

ized Competing Bandits in Serial Dictatorship / Proc. of the 24th International

Conference on Artificial Intelligence and Statistics (AISTATS 2021), San Diego,

2021.

111.

Basu S., Sankararaman K.A., Sankararaman A. Beyond log²(T) regret for decen-

tralized bandits in matching markets / Proc. of the 38 th International Conference

on Machine Learning, PMLR 139, 2021.

112.

Brams S.J., Fishburn P.C. Approval voting // Amer. Polit. Sci. Rev. 1978. V. 72.

P. 831-847.

113.

Aziz H., Brill M., Conitzer V., Elkind E., Freeman R., Walsh T. Justified represen-

tation in approval-based committee voting // Soc. Choice Welf. 2017. V. 48. No. 2.

P. 461-485.

114.

Bogomolnaia A., Moulin H. Random matching under dichotomous preferences //

Econometrica. 2004. V. 72. P. 257-279.

115.

Bogomolnaia A., Moulin H., Stong R. Collective choice under dichotomous prefer-

ences // J. Econ. Theory. 2005. V. 122. No. 2. P. 165-184.

116.

Duddy C. Fair sharing under dichotomous preferences // Math. Soc. Sci. 2015.

V. 73. P. 1-5.

117.

Aziz H., Harrenstein P., Lang J., Wooldridge M. Boolean hedonic games / Proc.

of the 15th Internat. Conf. on the Principles of Knowledge Representation and

Reasoning (KR-2016), 2016, 166-175.

118.

Elkind E., Lackner M. Structure in dichotomous preferences / Proc. of the 24th

Internat. Joint Conf. on Artif. Intel. (IJCAI-2015), 2015. P. 2019-2025.

119.

Blin G., Rizzi R., Vialette S. A faster algorithm for finding minimum Tucker sub-

matrices. Proceedings of the 6th Conf. on Computability in Europe (CiE’10), Ponta

Delgada, 2010. P. 69-77.

120.

Safe M.D. Circularly compatible ones, D-circularity, and proper circular-arc bi-

graphs // SIAM J. Discrete Math. 2021. V. 35. No. 2. P. 707-751.

121.

Pe’er I., Pupko T., Shamir R., Sharan R. Incomplete directed perfect phylogeny //

SIAM J. Comput. 2004. V. 33. No. 3. P. 590-607.

122.

Terzopoulou Z., Karpov A., Obraztsova S. Restricted domains of dichotomous pref-

erences with possibly incomplete information / Proc. of the 35th AAAI Conference

on Artificial Intelligence (AAAI 2021), 2021. P. 5726-5733.

123.

Brewbaker C. A combinatorial interpretation of the poly-Bernoulli numbers and two

Fermat analogues // Integers. 2008. V. 8. No. 1. A2.

124.

Weisstein E.W. Stirling number of the second kind/ MathWorld-A Wolfram Web

Resource. https://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html

125.

Yang Y. On the tree representations of dichotomous preferences / Kraus S. Ed.

Proc. of the Twenty-Eighth International Joint Conference on Artificial Intelligence

(IJCAI-2019), 2019. P. 644-650.

126.

Ju H.-K., Seo S. Enumeration of (0, 1)-matrices avoiding some 2× 2 matrices //

Discrete Math. 2012. V. 312. No. 16. P. 2473-2481.