Нетранзитивность — кладезь для изобретателей

Александр Поддьяков

Александр Поддьяков, профессор Департамента психологии Высшей школы экономики

В статье Натальи Резник «Камень, ножницы, бумага» [1] описаны многочисленные забавные — с человеческой точки зрения — взаимодействия самцов в борьбе за самок. У самых разных видов (ящериц, жуков и других) наблюдается сходный сценарий: есть самцы-агрессоры, вторгающиеся на чужие территории и отбивающие самок у тамошних обороняющихся самцов, и есть «тихушники», мимикрирующие под самок, — они не распознаются агрессорами и успешно делают свое черное дело. Зато «тихушников» успешно вычисляют обороняющиеся самцы. Этими очень понятными примерами дело не ограничивается — вопрос ставится значительно шире. Принцип взаимодействий «камень, ножницы, бумага» рассматривается в биологии как один из универсальных, поддерживающий биоразнообразие на самых разных уровнях. В журналах Science, Nature публикуются статьи со словами «камень, ножницы, бумага» в заголовках или списке ключевых слов. В этих текстах представлены живые примеры типа приведенных выше и предлагаются всё более продвинутые математические модели для описания, например, пространственно-временных распределений разных представителей животного и растительного мира (обзор дан в [2]).

Этот спектр явлений получил название нетранзитивной конкуренции — название происходит от логико-математического понятия «нетранзитивность» («непереходность»). Здесь превосходство, А над В и затем В над С не распространяется на пару, А — С: в ней С может доминировать (побеждать, превосходить А).

Интересна динамика развития разных наук. Изначально независимо, а сейчас всё более пересекаясь при обсуждении общего предмета интереса, на тему нетранзитивности превосходства вышли представители образцового по строгости типа мышления. Это математики — специалисты по теории вероятности, теоретики теории игр и изобретатели логико-математических головоломок. После статей Мартина Гарднера 1970-х годов о нетранзитивных игральных костях (числа на которых подобраны так, что кубик, А чаще показывает большее число, чем кубик В, кубик В чаще показывает большее число, чем С, а С чаще показывает большее число, чем А), о нетранзитивных рулетках, наборах игральных карт и так далее пошла широкая волна популяризации темы и ее активного научного исследования [3]. Математическая премия The Carl B. Allendoerfer Award этого года присуждена за статью «Нетранзитивные игральные кости», в которой выявлен еще один важный аспект парадоксальности этих объектов [4, 5]. Что касается популяризации, то в Интернете на слова «nontransitive dice» выпадают десятки видео, где разные люди — от профессоров математики и до школьников — рассказывают о нетранзитивных игральных костях и последствиях нетранзитивности для ошибок научного вывода и реальной жизни. Самая яркая история — о том, как догадливый Билл Гейтс не попал в ловушку с нетранзитивными игральными костями, предложенными ему Уорреном Баффеттом, — фигурирует в самых разных источниках, включая сайт Microsoft [6].

Особый интерес представляет придумывание, изобретение объектов, нетранзитивных по превосходству, то есть таких, что при сравнении по заданному признаку в паре, А — В надо выбрать, А (как превосходящее В по этому признаку), в паре В — С — выбрать В, а в паре, А — С — выбрать С.

Вот некоторые результаты, часть которых получена уже достаточно давно. Разработаны наборы игральных кубиков, в которых при удвоении набора (игроки берут не по одному кубику, а по два одинаковых) меняется направление «битья»: для одиночных кубиков A > B > C > A, а для «спаренных» AA < BB < CC < AA [7]. Также сконструированы наборы кубиков для игры втроем — такие, что, после того как двое игроков выбрали себе по кубику, третий игрок всегда может выбрать выигрышный по отношению к этим двум [7], и набор для игры вчетвером, что намного сложнее [8]. Задача разработки наборов для игры впятером, вшестером и c большим количеством игроков пока, видимо, не решена. Мое предположение: возможно, и здесь (как в ряде некоторых других задач) мы выходим на ключевой вопрос о равенстве классов сложности P—NP. В популярном изложении Лэнса Фортноу, одного из самых известных исследователей в этой области, «P — это класс задач, которые на компьютере решаются относительно быстро. NP — задачи, для которых мы хотим найти оптимальное решение. Равенство P и NP означает, что любую поставленную задачу можно быстро решить. <…> Неравенство P и NP, в свою очередь, означает, что для некоторых задач быстрое решение не найдется никогда» (из книги «Золотой билет. P, NP и границы возможного»). Но обсуждение этого аспекта применительно к нетранзитивных костям мне не встречалось — ни применительно к задаче построения набора костей для N игроков, ни применительно к задаче поиска нетранзитивных цепочек (хотя бы одной или множества цепочек с заданными свойствами) в наборе M костей (например, со случайно сгенерированными числами на гранях). А вот алгоритм генерации таких чисел на кубиках, чтобы те образовывали «простую» нетранзитивную цепочку произвольной длины для игры двух игроков, построен.

При всем интересе к нетранзитивным игральным костям, я занимаюсь изобретением и конструированием объектов, находящихся не в вероятностных, а в детерминистских отношениях непереходности превосходства: начиная с таких геометрических объектов, которые понятны и дошкольнику (в отличие все-таки от нетранзитивных игральных костей), и кончая всё более сложными и контринтуитивными [9]. Помимо забавных моделей, в которых игрушечная птица, А кланяется игрушечной птице В (в силу физического взаимодействия их элементов), птица В кланяется птице С, а та — А, здесь есть объекты более парадоксальные и сложные.

Так, создавая зубчатые передачи из двойных шестерен, можно построить такие, в которых двойная шестерня, А вращается быстрее В паре, А — В, В вращается быстрее С в паре В — С, а С — быстрее, А в паре, А — С (рис. 1). Иначе говоря, если бы мы играли в игру, в которой выигрывает тот, чья шестерня вращается быстрее, то у игрока, выбирающего вторым, всегда было бы однозначное преимущество; но для того чтобы понять это сразу, надо разбираться в механике.

Рис. 1. «Нетранзитивные» шестерни: при попарных соединениях синяя шестерня вращается быстрее зеленой, зеленая — быстрее красной, красная — быстрее синей

Рис. 1. «Нетранзитивные» шестерни: при попарных соединениях синяя шестерня вращается быстрее зеленой, зеленая — быстрее красной, красная — быстрее синей

Если же мы будем втыкать оси этих шестерен в расположенные рядом отверстия на вертикальной стенке и закрепим на каждой оси стандартный грузик, то получим кажущийся парадоксальным результат уже в терминах нетранзитивного силового взаимодействия. А именно: при попарных соединениях груз на шестерне, А поднимается («пересиливается») грузом на шестерне В, груз на шестерне В — грузом на шестерне С, но груз на шестерне С — грузом на шестерне, А (рис. 2). Эта модель может пригодиться для развития представлений учеников в области механики. Аналогично, можно построить нетранзитивные двойные рычаги, где правило рычага и принцип взаимодействия «камень, ножницы, бумага» иллюстрируют друг друга.
Рис. 2. Нетранзитивные шестерни с грузами: красный блок «сильнее» синего (перетягивает его), зеленый — красного, синий — зеленого (каждая двойная шестерня обозначена одинарной соответствующего цвета, зацепление — по схеме на рис. 1)

Рис. 2. Нетранзитивные шестерни с грузами: красный блок «сильнее» синего (перетягивает его), зеленый — красного, синий — зеленого (каждая двойная шестерня обозначена одинарной соответствующего цвета, зацепление — по схеме на рис. 1)

Видимо, один из наиболее сложных примеров детерминированной нетранзитивности — нетранзитивные по выигрышности позиции в логических играх на размеченном игровом поле. Это, например, нетранзитивные шахматные позиции: при попарном наложении на одну доску позиция A белых предпочтительнее позиции B черных (при возможности выбора за белых или за черных надо выбрать A), позиция B черных предпочтительнее позиции C белых, позиция C белых предпочтительнее позиции D черных, но позиция D черных предпочтительнее позиции A белых (белые начинают во всех вариантах) (рис. 3). Этот пример сконструирован в демонстрационных целях. Как материал для задачи он лишен шахматного изящества и нарочито прост, даже примитивен, — например, мат может ставиться одним ходом белых. Цель — только показ самой возможности нетранзитивных отношений между шахматными позициями как ранее неизвестного свойства самой шахматной среды (нетранзитивная сила игроков-шахматистов и шахматных программ известна давно).
Рис. 3. Нетранзитивные шахматные позиции (белые начинают во всех вариантах)

Рис. 3. Нетранзитивные шахматные позиции (белые начинают во всех вариантах)

Пояснение: то, что позиция черных может быть выигрышнее какой-то одной позиции белых и при этом проигрышнее другой, — факт очевидный. Но ранее не была известна возможность нетранзитивного закольцовывания таких позиций, составляющая существенную новизну: ни в каких списках примеров нетранзитивности не удалось обнаружить кольца шахматных позиций. После знакомства с такими позициями у некоторых игроков возникает ощущение очевидности задним числом («ясно, что так можно») — но именно задним.

На основе приведенного на рисунке примера специалист по теории игр А. Ю. Филатов показал, что число нетранзитивных цепочек в шахматах огромно, а сами цепочки могут быть астрономической длины. Также он построил минимальную — и при этом симметричную — цепочку из четырех позиций, где с каждой стороны участвуют только по две фигуры: белые и черные король и пешка [10].

Рис. 4. Нетранзитивные «гуляй-башни» (пластмассовые параллелепипеды с вырезанными передними фигурными профилями и вставленными в отверстия цветными маркерами). Гуляй-башня с красным маркером ставит метку на гуляй-башне с зеленым маркером, оставаясь для той неуязвимой; гуляй-башня с зеленым маркером ставит метку на гуляй-башне с синим маркером (но не наоборот), а гуляй-башня с синим маркером — на гуляй-башне с красным маркером (но не наоборот)

Рис. 4. Нетранзитивные «гуляй-башни» (пластмассовые параллелепипеды с вырезанными передними фигурными профилями и вставленными в отверстия цветными маркерами). Гуляй-башня с красным маркером ставит метку на гуляй-башне с зеленым маркером, оставаясь для той неуязвимой; гуляй-башня с зеленым маркером ставит метку на гуляй-башне с синим маркером (но не наоборот), а гуляй-башня с синим маркером — на гуляй-башне с красным маркером (но не наоборот)

Одно из теоретико-игровых следствий обнаружения нетранзитивных шахматных позиций таково. Получено короткое доказательство важного факта, пусть интуитивно понятного или известного опытным игрокам. В общем случае позиция белых не может быть описана фиксированной количественной оценкой, исчерпывающе характеризующей силу (потенциал) этой позиции — без учета позиции черных. Точно так же позиция черных не может быть описана фиксированной количественной оценкой, исчерпывающе характеризующей силу этой позиции, без учета позиции белых. Сила (потенциал) конкретной позиции белых относительна и определяется ее взаимодействием с конкретной позицией черных, и наоборот.

Это очевидно? Рассмотрим модельный пример. К опытному шахматисту приходит талантливый в шахматах и математике ребенок и говорит: «Я разработал формулу, которая позволяет оценивать по отдельности позицию белых и позицию черных и приписывать им однозначную, фиксированную количественную оценку, а затем сравнивать эти позиции — уже просто как числа, какое больше: у белых или у черных». Вместо ответа типа: «Вот сыграешь много партий и на опыте поймешь, что это не так; такая формула, я уверен, невозможна» теперь есть возможность ответа другого типа: «Есть такая штука, как нетранзивные шахматные позиции, и они означают, что позиция белых и позиция черных не могут иметь фиксированной количественной оценки без учета друг друга. В круге побед и поражений, где каждая позиция бьет соседку с одной стороны и бьется соседкой с другой, какие могут быть фиксированные численные оценки? Дать тебе готовый пример таких позиций или хочешь придумать свой пример сам?»

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

Что касается заинтересовавшегося взрослого (или ребенка тоже?), то здесь еще много задач: например, поискать ответ на вопрос, на какой минимальной доске (3×3? 4×4?) нетранзитивность позиций уже возможна; построить нетранзитивные позиции в других играх (шашках, го) и так далее. Изобретение объектов, нетранзитивных по превосходству, и придумывание задач с их участием — интересная, а для некоторых даже захватывающая деятельность, объединяющая самые разные области.

1. Н. Резник. Камень, ножницы, бумага // ТрВ-Наука, № 162 от 9 сентября 2014 года.

2. elibrary.ru/item.asp?id=21 630 164

3. www.nkj.ru/archive/articles/31 726/

4. arxiv.org/pdf/1311.6511.pdf

5. bit.ly/2gLbM3R

6. www.microsoft.com/en-us/research/project/non-transitive-dice

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Связанные статьи

Оценить: 
Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (4 оценок, среднее: 4,00 из 5)
Загрузка...
 
 

Метки: , , , , , , , , , , , , , , , , , ,

 

23 комментария

  • Иван:

    Интересная статья.
    Навела на полезные размышления.
    Спасибо.

  • Алексей В. Лебедев:

    Надо же, я 20 лет работаю в вероятности, а про нетранзитивные кубики не слышал. Потрясающая тема. Интересно, известны ли обобщения с дискретных (кубики) на непрерывные случайные величины?

  • Специально про непрерывные случайные величины раньше не искал.
    Нарыл сейчас такое — не знаю, насколько релевантно (искал на intransitivity continual continuous bivariate distribution, можно модифицировать). Bivariate distribution считается одним из условий нетранзитивности.

    Ulrich W. et al, (2015). Matrix models for quantifying competitive intransitivity.https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4407980/

    Gowers’s Weblog https://gowers.wordpress.com/2017/05/19/intransitive-dice-iii/

    Gehrlein W. (2006). Condorcet’s Paradox.
    http://bit.ly/2Bq0Ca3
    http://bit.ly/2i6z9Wi
    (О книге — http://www.springer.com/us/book/9 783 540 337 980)

    Klimenko A. Y/ (2015). Intransitivity in Theory and in the Real World
    http://www.mdpi.com/1099−4300/17/6/4364/html

  • Есть такое подозрение, что возможности нетранзитивности непрерывных (continuous) величин обсуждаются на английском здесь, особенно в комментариях: https://gowers.wordpress.com/2017/05/30/intransitive-dice-v-we-want-a-local-central-limit-theorem/

  • Станислав Жураховский:

    В шашках построить нетранзитивныий цикл намного легче, чем в шахматах. Причина в том, что в шахматах лишний темп — это обычно преимущество, а в шашках бывает по разному (важно соотношение темпов). Поэтому в шашках довольно часто бывает цугцванг и даже обоюдный (когда начинающий проигрывает). Из простейших таких позиций на занятие оппозиции и стороится нетранзитивный цикл (всюду ход белых): A: б. e3, ч. d6 — 1:0; A: б. d4, ч. d6 — 0:1; A: б. d4, ч. e7 — 1:0; A: б. e3, ч. e7 — 0:1. Кстати, эта четверка позиций является нетранзитивным циклом и в поддавки.

  • Алексей В. Лебедев: «Интересно, известны ли обобщения с дискретных (кубики) на непрерывные случайные величины?»

    Увидел, что эта проблема ставилась для будущих исследований: «One would expect that replacing discrete random variables with continuous ones requires a different methodology» https://www.researchgate.net/publication/287 263 681_Nontransitive_dice_sets_realizing_the_Paley_tournaments_for_solving_Schutte%27s_tournament_problem
    Решена ли с тех пор, непонятно.

    • Алексей В. Лебедев:

      Большое спасибо, посмотрю.

    • Алексей В. Лебедев:

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

      Я с моим учеником пробовал брать многочлены на отрезке [0,1], в качестве функций распределения, для трех величин. При степени 2 доказывается, что нетранзитивности не бывает. При степени 3 похоже, что не бывает, но пока не доказано. При степени 4 нетранзитивность обнаружена, и вероятность пока удалось довести до 0.53, что сопоставимо со случаем трех кубиков, где 5/9, но сильно меньше максимально возможной 0.618.

  • Мне кажется, уже прорыв, что удалось доказать саму возможность нетранзитивности для непрерывных величин (не предположить ее, а доказать — с конкретными значениями). Я таких работ не видел.

    Может, этот автор здесь что-то развивает http://mtasztaki.academia.edu/S%C3%A1ndorBoz%C3%B3ki - сюда я еще не забирался, но в ссылках никакой конкретный результат мне пока не выпадал.

    • Алексей В. Лебедев:

      Он дальше этим не занимался.

      Можно к целым числам, выпадающим на кубиках, прибавлять равномерно распределенные случайные ошибки, на интервале от -0,5 до 0,5 или от 0 до 1. Тогда соотношения между числами (больше-меньше) не изменятся, а распределение станет непрерывным. Другое дело, что этот пример выглядит искусственно.

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

  • С точки зрения поиска нетранзитивости непрерывных величин в реальности (в природе), лучше идти от известных непрерывных распределений — да, правда.

    Если же отталкиваться от кубиков, то можно, наверное, не добавлять случайно распределенные величины к числам на них, но попробовать другую вещь — построить функцию, проходящую через соответствующие значения (которые на кубиках).
    То есть, скажем, это (если отталкиваться от трех известных кубиков)
    — функция, проходящая через 2, 4, 9 (вогнутая)
    — функция, проходящая через 1, 6, 8 (выпуклая)
    — функция, проходящая через 3, 5, 7 (прямая).

    Или примерно это и было опробовано, когда вы писали о проверке степеней функции?
    Или это бред?

    • Алексей В. Лебедев:

      Эти кубики требуют 9 разных значений, у каждого по 3 разных, на самом деле достаточно 5 разных значений, у каждого не более 2 разных (см. таблицу 1 статьи С. Бозоки), и сами значения не важны, а только их соотношения между собой, и можно все уместить, например, на отрезок [0,1]. Для функции распределения желательно, чтобы при этих значениях аргумента она росла быстро (имела максимумы плотности), а при остальных медленнее. Наличие двух максимумов, разделенных минимумом, требует хотя бы степени 3 от плотности, и тогда степени 4 от функции распределения. Но это нестрогие рассуждения.

  • Алексей В. Лебедев:

    Причем что интересно, первоначально, в статье С. Трибулы (1961) ни о каких костях речь не шла. Была поставлена серьезная теоретико-вероятностная задача о произвольных случайных величинах. Было указано возможное приложение в теории прочности, когда в лаборатории сравниваются на прочность железные бруски с трех заводов. И теоретически может оказаться, что при попарных сравнениях бруски с первой фабрики чаще окажутся прочнее брусков с второй и т. д. по кругу. При этом понятно, что на самом деле прочность — не дискретная случайная величина, а непрерывная. И в принципе, интересны, конечно, условия на непрерывные распределения, когда это может быть, а когда нет. Но популяризация данной темы в форме «костей» с одной стороны привлекла к ней широкое внимание, но с другой стороны, на мой взгляд, слишком сузило задачу, сделало ее игровой и несерьезной, и увело исследования в какую-то не ту сторону.

    S. Trybula, «On the paradox of three random variables,» Zastos. Mat., vol. 5, pp. 321−332, 1961.

  • Я согласен, что постановка проблемы нетранзитивности произвольных случайных величинах (включая непрерывные) фундаментальнее, и интересен поиск соответствий в реальности (типа нетранзитивности прочности).

    М.Гарднер в своей колонке 1970 г. писал, что нетранзитивные кости — разработка Эфрона (вроде на тот момент прошло несколько лет с изобретения — то есть 60-е гг), на Трибулу у Гарднера ссылок не видно. Текстов самого Эфрона про кости найти не могу — может, не опознаю; глянул здесь
    https://en.wikipedia.org/wiki/Bradley_Efron
    http://statweb.stanford.edu/~ckirby/brad/
    http://statweb.stanford.edu/~ckirby/brad/EfronCV.pdf
    Знал ли Эфрон о Трибуле на момент изобретения, пока непонятно.

    А Трибула, судя по ссылкам в современных статьях про нетранзитивные кости, писал по этой теме с конца 50-х.
    H. Steinhaus, S. Trybuła. On a paradox in applied probabilities, Bull. Acad. Polon. Sci. 7 (1959) 67−69.

    О разных нетранзитивностях — объективных и (не очень точно) померенных

    Есть работы, к которых обосновывается, что нетранзитивность может быть следствием неточности измерений, в том числе многократных — при том, что на самом деле никакой нетранзитивности в природе быть не может (да, есть такие радикально настроенные люди).

    Раз в статье Трибулы 1961 г. прочность каждого бруска сравнивается относительно одного и того же внешнего стандарта (ввинчиваемого винта, шурупа), то речь, скорее, не об объективной нетранзитивности прочности — той нетранзитивности, когда при непосредственном механическом взаимодействии брусок, А ломает бы (истирает, еще как-то портит) брусок В больше, чем В портил А; В портит С больше, чем С — В; а С портит, А больше, чем, А — С.

    А кости Эфрона — это нетранзитивность, не связанная с неточностью измерения.

    Я когда-то задавал вопрос о возможности нетранзитивности твердости А. Р. Оганову и Л. А. Ашкинази; оба ответили отрицательно.

  • Уточнение
    У Трибулы речь идет о прочности брусков вроде бы и из одного и того же материала, но с разных фабрик и разного качества (где-то получше, где-то похуже). То есть это не три каких-то идеальных материала, а реальные, и их характеристики немного гуляют из-за особенностей изготовления на этих трех фабриках. Из-за этого, наверное, может быть и так, что гуляющие по качеству бруски с фабрики, А чаще прочнее гуляющих по качеству брусков с фабрики Б (при непосредственном взаимодействии этих брусков), гуляющие бруски с фабрики Б чаще прочнее брусков с В, а бруски с В чаще прочнее брусков с, А (слово «гуляющие» опускаю). И это интересный случай.

    Но интересна также принципиальная возможность (или невозможность) нетранзитивных по прочности материалов, у которых нет проблем с качеством и допусками прочности. Они в этом отношении идеальны, но «по самой своей природе» (по дизайну) таковы, что при непосредственном механическом взаимодействии (в попарных схватках, так сказать) материал, А прочнее Б, Б прочнее В, В прочнее А. Но такие невозможны…

    • Алексей В. Лебедев:

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

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

  • Да, спасибо за ссылку на эту статью Трибулы (не знал, а нетранзивность прочности интересовала давно) и за комментарий.

  • Вот еще исследование разных нетранзитивностей, в том числе при промышленном контроле качества; интересная статья
    West, L. J, Hankin, R. (2008). Exact tests for two-way contingency tables with structural zeros. Journal of Statistical Software. Vol. 28.
    https://www.researchgate.net/publication/46 515 707_Exact_Tests_for_Two-Way_Contingency_Tables_with_Structural_Zeros

  • Развитие идеи нетранзитивных шестерен (с первой картинки)

    Голландский изобретатель головоломок Oskar van Deventer (с несколькими рекордами Гиннеса) на основе этих нетранзитивных шестерен сделал головоломку Non-Transitive-Gears

    К исходной конструкции добавлены храповые механизмы (и, возможно, что-то еще). При вращении любой из трех рукояток одна из соседних с нею шестерен вращается в 2 раза быстрее, а другая — в 3 (в три, не в два!) раза медленнее. Если играть, как с черным ящиком, не зная устройства — впечатление парадоксальное.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Недопустимы спам, оскорбления. Желательно подписываться реальным именем. Аватары - через gravatar.com