Один магазин на две деревни
Население деревни Вилларибо проживает равномерно1 на отрезке [0; 1], а деревни Виллабаджо –– равномерно на отрезке [2; 3]. В Вилларибо и Виллабаджо приехал владелец сети магазинов «Кукумбрикс», который объявил, что сеть построит первый и единственный магазин в окрестности, а в какой точке прямой (−\infty ; +\infty ) он будет построен –– решать жителям деревень. Конечно, каждый житель хочет, чтобы магазин был построен как можно ближе к его дому. Обычно все общие географические вопросы жители Вилларибо и Виллабаджо решают, используя механизм «Посередине между делегатами». А именно, сначала каждая деревня выбирает по одному делегату. Затем, если дом делегата Вилларибо находится в точке с координатой a, а дом делегата Виллабаджо имеет координату b, то решением вопроса является точка с координатами (a+b)/2. Делегатом a будем называть того, который живет в точке с координатой a.
а) (2 балла) Изобразите на прямой (−\infty ; +\infty ) множество всех точек, в которых хотя бы при какой-нибудь паре делегатов может быть построен магазин.
б) (2 балла) Докажите, что жителям Вилларибо для выбора делегата не нужна информация о делегате от Виллабаджо: если житель Вилларибо x предпочитает делегата от Вилларибо a1 делегату a2 при делегате от Виллабаджо b1, то житель Вилларибо x предпочтет делегата от Вилларибо a1 делегату a2 при любом другом делегате от Виллабаджо b2.
в) (3 балла) В этом и только в этом пункте считаем, что жители деревень выбирают в качестве делегата победителя по Кондорсе –– такого жителя деревни, что его предпочтет не менее половины жителей этой деревни при голосовании против любого другого жителя деревни (корректность определения следует из предыдущего пункта). Где будет построен магазин?
г) (3 балла) Говорят, что механизм принятия решений является манипулируемым, если существует такая пара делегатов от деревень, что хотя бы одному из делегатов выгодно скрыть настоящее место расположения своего дома и использовать для принятия решения какую-то другую координату. Докажите, что описанный механизм принятия решений является манипулируемым.
д) (2 балла) Предложите какой-нибудь механизм принятия решений, выдающий по паре делегатов a и b место для магазина и не являющийся манипулируемым.
1Это значит, что на любом отрезке длиной \alpha \leq 1 внутри отрезка [0; 1] проживает доля \alpha населения деревни.
а) По условию задачи 0 \leq a \leq 1 и 2 \leq b \leq 3. Следовательно,
1 \leq (a + b)/2 \leq 2
Любая точка x из интервала [1; 2] в действительности может быть получена в качестве места строительства магазина при паре делегатов a = x − 1 и b = x + 1. Таким образом, ответ в пункте а) –– интервал [1; 2].
б) Из пункта а) и условия задачи следует, что магазин всегда будет располагаться не левее любого из жителей Вилларибо. Следовательно, произвольный житель Вилларибо x, сравнивая двух кандидатов в делегаты от Вилларибо a1 и a2, предпочтет того из них, кто находится левее, чтобы разместить магазин как можно левее. Это верно при любом кандидате из Виллабаджо. Таким образом, предпочтения жителей Вилларибо на множестве возможных делегатов от Вилларибо не зависят от делегата от Виллабаджо.
в) В пункте б) мы доказали, что каждый житель Вилларибо из двух кандидатов в делегаты будет предпочитать того, кто живет левее. Следовательно, кандидат, живущий в точке 0, будет победителем по Кондорсе: за него проголосуют все жители против любого другого кандидата a. Аналогично, победителем по Кондорсе от Виллабджо является кандидат, живущий в точке 3. Значит, магазин будет построен в точке 1,5.
г) Рассмотрим, например, пару делегатов a = 1, b = 2. Тогда магазин будет построен в точке 1,5. Однако делегату a выгодно соврать и назвать a1 = 0: в этом случае при том же самом b магазин будет построен в точке 1. Следовательно, описанный механизм принятия решений является манипулируемым.
д) Например, рассмотрим функцию f(a, b) = 0. Она задает константный механизм принятия решений, при котором независимо от делегатов магазин строится в точке 0. Этот механизм неманипулируем: скрывать свое место проживания делегату не имеет смысла, ведь магазин все равно будет построен в точке 0.