Это база: Зачем нужна математика в повседневной жизни - Йэн Стюарт
Шрифт:
Интервал:
Закладка:
В этом протоколе, слишком сложном для подробного описания, задействован независимый агент, который предлагает способ деления штата на две части. Затем партиям предоставляется возможность изменить карту агента, разделив одну из половин еще надвое, при условии, что другая партия разделит вторую половину. Или они могут выбрать вариант, при котором партии меняются ролями. Это вариант принципа «я режу, ты выбираешь» с более сложными последовательностями резов. Ландау, Рейд и Ершова доказывают, что их протокол справедлив с точки зрения любой партии. По существу, две партии играют одна против другой. Но игра организована так, чтобы заканчиваться ничьей, а каждый участник был уверен в получении максимально возможного результата. Если это не так, то ему следовало играть лучше.
В 2017 году Ариэль Прокачча и Уэсли Пегден усовершенствовали этот протокол, исключив из него независимого агента, так что теперь все вопросы решаются двумя противоборствующими сторонами. Если коротко, одна политическая партия делит карту штата на требуемое по закону число округов с равным (насколько возможно) числом избирателей в каждом. Затем вторая партия «замораживает» один округ, то есть делает дальнейшее изменение его границ невозможным, и перерисовывает, как считает нужным, границы остальных. Затем первая партия замораживает на новой карте еще один округ и перерисовывает оставшиеся. Так партии по очереди замораживают и перерисовывают округа, пока все они не окажутся замороженными. Это и есть окончательная карта избирательных округов. Если всего округов, скажем, 20, процесс займет 19 циклов. Пегден, Прокачча и приглашенный студент-компьютерщик Юй Динли математически доказали, что этот протокол не дает первому игроку преимущества и что ни один из игроков не сможет сосредоточить в одном округе определенную часть населения, если второй игрок этого не захочет.
* * *
В настоящее время математика выборов – очень обширный предмет, а манипуляции при разбивке на округа лишь один из изучаемых аспектов. Немало работы проделано по разным системам голосования – мажоритарной системе, системе единого передаваемого голоса, пропорциональному представительству и т. д. Один из выводов, вытекающих из этих исследований, заключается в том, что если составить короткий список свойств, желательных для любой разумной демократической системы, то в определенных обстоятельствах они неизменно противоречат друг другу.
Прабабушкой подобных результатов можно считать теорему Эрроу о невозможности, которую экономист Кеннет Эрроу опубликовал в 1950 году и объяснил в своей книге «Коллективный выбор и индивидуальные ценности» (Social Choice and Individual Values)[3] годом позже. Эрроу рассмотрел рейтинговую систему голосования, при которой каждый избиратель присваивает серии вариантов численные рейтинги: 1 – самому лучшему с его точки зрения варианту, 2 – следующему и т. д. Он объявил три критерия справедливости такой системы голосования:
• Если каждый избиратель предпочитает одну из альтернатив, то это верно и для группы.
• Если ни у одного из избирателей предпочтения в отношении двух конкретных вариантов не меняются, не меняются они и у группы, даже если предпочтения в отношении остальных вариантов меняются.
• Не существует такого диктатора, который может всегда определить, какой вариант предпочитает группа.
Все это прекрасно и очень желательно, но, как далее доказывает Эрроу, логически противоречиво. Это не значит, что такая система обязательно несправедлива: это означает лишь, что при некоторых обстоятельствах результат будет нелогичным.
У избирательных манипуляций имеются собственные потомки теоремы Эрроу. В одной из таких теорем, опубликованной Борисом Алексеевым и Дастином Миксоном{18} в 2018 году, изложены три принципа справедливой разбивки на округа:
• Один человек, один голос: все округа включают в себя примерно равное число избирателей.
• Компактность по Полсби – Попперу: все округа имеют тест Полсби – Поппера, превышающий определенное законом значение.
• Ограниченный разрыв в эффективности: более формальный параметр. Грубо говоря, если население любых двух округов не превышает некоторой фиксированной доли полного населения всех округов, то разрыв в эффективности составляет меньше 50 %.
Затем они доказывают, что никакая система нарезки избирательных округов не может во всех случаях удовлетворять этим трем критериям.
Демократия не может быть идеальной. Поразительно, что она вообще работает, если учесть, что ее цель – убедить миллионы людей, имеющих собственное мнение, согласиться по какому-то важному вопросу, затрагивающему всех. Диктаторские режимы намного проще. Один диктатор – один голос.
3
Пусть голубь ведет автобус
Водителя автобуса может беспокоить, что голубь не способен безопасно вести автобус. Еще больше его может беспокоить то, что голубь не сумеет выбрать маршрут, позволяющий подобрать всех пассажиров на остановках города.
БРЕТТ ГИБСОН, МЭТТЬЮ УИЛКИНСОН И ДЕББИ КЕЛЛИ.
Animal cognition
Мо Виллемс рисовал забавные картинки с трехлетнего возраста. Опасаясь, что взрослые могут хвалить его не от чистого сердца, он начал писать смешные истории. Ему казалось, что фальшивый смех легче распознать. В 1993 году он присоединился к команде сценаристов и мультипликаторов классической «Улицы Сезам», что принесло ему за 10 лет шесть премий «Эмми». Главным героем его детского мультсериала «Баран в большом городе» стал баран по имени Баран, чья идиллическая жизнь на ферме рушится, когда тайная военная организация начинает гоняться за ним и ловить для создания лучевой пушки на бараньей силе. Первым опытом Виллемса в жанре детской книги стала книжка «Не позволяйте голубю вести автобус!», продолжавшая тему животных. Мультфильм по этой книге принес автору медаль Карнеги, а сама книга – премию Калдекотта, которую получают те, кто попадает в шорт-лист претендентов на медаль Калдекотта. Главный герой книги – голубь – использует все возможное и невозможное, пытаясь убедить читателя, что ему можно доверить управление автобусом, когда обычному водителю внезапно приходится покинуть транспортное средство.
В 2012 году книга Виллемса получила неожиданное научное продолжение – солидную статью в уважаемом журнале Animal Cognition, авторами которой стали заслуживающие доверия исследователи Бретт Гибсон, Мэттью Уилкинсон и Дебби Келли. Они экспериментально доказали, что голуби способны находить решения, близкие к оптимальным, для простых случаев известной математической диковинки – задачи коммивояжера. Их статья называлась «Позвольте голубю вести автобус: голуби способны планировать маршруты в помещении»{19}.
И пусть никто не говорит, что у ученых нет чувства юмора. Или что остроумные заголовки не помогают добиться популярности.
Задача коммивояжера – не просто любопытная диковинка. Это хороший пример целого класса задач, имеющих громадное практическое значение и известных как задачи комбинаторной оптимизации. У математиков есть привычка формулировать глубокие и значительные вопросы тривиальным на первый взгляд языком. Американские конгрессмены осудили напрасное расходование бюджетных денег на теорию узлов, не понимая, что эта область математики принципиально важна для понимания топологии
