ЗАДАЧА ДЛЯ ИИ
В новостях сообщения о том, что искусственный интеллект решил одну из "задач тысячилетия" - про гладкость решений уравнения Навье-Стокса, одной из самых важных и сложных математических задач. До этого ИИ решил проблему якобиана и далеко продвинулся в доказательстве гипотезы Римана, сложнейших математических задач, стоящих открытыми десятилетия.
Я уже писал, что ИИ, в умелых руках Fedor Sandomirskiy, специалиста по экономической теории из Принстона, доказал то, что я не смог доказать в своей диссертации по высшей алгебре тридцать лет назад (и с тех пор не пытался, но если бы пытался, то наверняка не смог бы). А вот ниже - пример задачи из нашей давней статьи по экономической теории, которую ИИ пока взять не может. Конечно, ресурсы, которые на неё пока что потрачены, не очень велики, но уже довольно большие.
Прикольность нашей задачи в том, что она совсем просто формулируется. Ниже, в этом посте, она сформулирована прямо с нуля. Простые примеры весело давать детям - тот же Арчи, 11, с удовольствием искал стабильные и нестабильные конфигурации этим летом.
Задача это из нашей статьи 2006 года, написанной с Дароном Асемоглу и Георгием Егоровым - причём была она только в рабочей версии (
https://papers.ssrn.com/sol3/papers.cfm?abstract_id=949759), а в финальный вариант статьи она не вошла. Конкретно Теорему 5 нам помогла доказать Ирина Хованская, мой друг детства и очень сильный математик.
Вот задача:
Есть N членов политбюро, у каждого есть сколько-то голосов X_i. Этими голосами они голосуют за то, чтобы убить кого-то из членов. Голоса убитых перераспределяются пропорционально среди тех, кто остался. После того, как убийства закончены (то есть конфигурация стала стабильной), оставшиеся получают долю пирога, пропорциональную голосам.
Чтобы убить, нужно чтобы за это проголосовало доля a голосов. Самый простой случай, конечно, если a= 1/2 (простое большинство).
Мы всегда будем предполагать, что ничьих не бывает (голоса распределены так, чтобы суммы голосов никаких коалиций ни на какой стадии не совпадали). Общая теория работает и без этого предположения, но оно сильно упрощает примеры.
Например, если a=1/2, то все конфигурации из двух человек неустойчивы (потому что тот, у кого больше голосов, убьет второго и получит всё). А если a>1/2, то есть устойчивые из двух.
Пусть а=1/2. Тогда
(3,4,5) - cтабильная конфигурация (потому что если кого-то убить, то убийства продолжатся - значит, кто-то из начальной коалиции, проголосовавшей за первое убийство, туда не пойдёт, и, значит, не проголосует);
(3,4,5,10) - нестабильная конфигурация (потому что 3, 4, и 5 объединятся, чтобы убить 10 и это стабильно);
(3,4,5,10,20) - стабильная конфигурация. Она называется "смерть Сталина". Сталин - 20 и пока он жив, всё стабильно. Берия - 10, Хрущев, Маленков, Булганин - 3, 4, 5. Когда Сталин умирает, 3, 4, и 5 убивают "Берию".
Ну и так далее. Стабильные коалиции есть любого размера. (Элементарная задачка.) Их можно искать рекурсивно. К сожалению, компьютерный перебор плохо помогает, потому что количество необходимых вычислений растёт экспоненциально.
Теперь, взять любую стабильную конфигурацию и внутри неё - "минимальную выигрывающую коалицию". То есть минимальную коалицию, у которой есть a голосов. Она, конечно, не стабильная. (Если бы она была стабильной, то она бы разрушила исходную.) Теорема 5 говорит, что голоса остальных можно перераспределить так, чтобы минимальная стала стабильной.
Так вот, эта Теорема 5 верна для a=1/2 и у неё простое прозрачное доказательство (хотя и неконструктивное, см. статью). А вот для а>1/2 ни доказать, ни опровергнуть не удаётся. На сегодня, 9 сентября 2026 года, не удаётся.
