Вопрос 9.7. Можно ли сказать, что в примере из вопроса 9.3 предпочтения Дейва, Майка и Пита являются сепарабельными? По- чему?

Вопрос 9.8. Предположим, что на референдуме один избиратель проранжировал возможные результаты выборов таким образом:

ДДД у ДНД у ДНН >- ДДН >- ННН >- НДД у НДН >- ННД

Сепарабельны ли предпочтения этого избирателя? Почему?

Как вы могли заметить в вопросе 9.8, бывает сложно определить, сепарабельны ли предпочтения избирателя на референдуме. Это про-

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

Вопрос 9.9*. Предположим, что вы хотите узнать, сепарабельны ли предпочтения некоторого избирателя на референдуме.

(а) Если на референдуме только три предложения, то какое наи- большее число наборов предложений вам придется рассматривать?

(б) Если на референдуме только пять предложений, то какое наи- большее число наборов предложений вам придется рассматривать?

(в) Если на референдуме только десять предложений, то какое наибольшее число наборов предложений вам придется рассматри- вать?

(г) Как вы думаете, почему в пунктах (а)—(в) вопрос стоял о наи- большем числе наборов предложений, которое вам придется рас- сматривать? Может ли сложиться так, что вам достаточно будет рассмотреть меньшее число наборов предложений? Четко объясните ваш ответ.

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

Бинарные матрицы предпочтений

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

Вопрос 9.10*. Рассмотрим в очередной раз референдум о пар- ковке КМД из вопроса-разминки 9.1. Для этого референдума бинар- ные матрицы предпочтений, соответствующие Дейву, Майку и Питу, показаны в табл. 9.2.

Таблица 9.2

Бинарные матрицы предпочтений на референдуме КМД

о ix

ⁱ i i

I^I ° {о о)

Майк

/о о

0. i

1. о

Пит

Как вы думаете, как матрицы из табл. 9.2 могли быть построены на основании предпочтений из табл. 9.1? (Замечание. Если вы ответи- те правильно, то найдете общее правило для построения и интерпре- тации бинарных матриц предпочтений.)

Вопрос 9.и. Какие из следующих массивов нулей и единиц яв- ляются бинарными матрицами предпочтений? Иначе говоря, какие из них могут быть использованы для представления предпочтений из- бирателей на референдуме с двумя предложениями?

Вопрос 9.12. Выпишите бинарную матрицу предпочтений, пред- ставляющую предпочтения из вопроса 9.8. Какой набор предложений на соответствующем референдуме будет сепарабельным относитель- но избирателя, который придерживается таких предпочтений? Какой набор предпочтений не будет сепарабельным? Можно ли сказать, что с использованием бинарной матрицы предпочтений легче опреде- лить — какие наборы предпочтений сепарабельны, а какие нет? Четко объясните ваши ответы

Проверка сепарабельности

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

Метод i. Симметрия

Определение 9.13.

• Побитовое дополнение строки в бинарной матрице предпочтений образуется перестановкой всех нулей и единиц в строке (т. е., за- меной всех нулей единицами, а всех единиц —нулями.)

• Бинарная матрица предпочтений называется симметричной, ес- ли i-я, считая сверху, строка матрицы является побитовым допол- нением i-й строки снизу.