Теория игр - презабавная штука

Теория игр - презабавная штука. Игривое название приводит к любопытным казусам. Так, одно время - когда интернет был дорог и небезлимитен - на серверах Института стояли фильтры, которые сурово пресекали попытки зайти на сайты или провести запросы со словами "игры" или "games". Оно бы ничего, но добрая половина Института занималась как раз математической теорией игр.

А однажды ваш покорный слуга отыскал в интернет-библиотеке серьезную монографию по теории игр в разделе lohotron.

Теория игр, или игровая теория, как ее называют вне математики - это разновидность оптимизации. Только если обычно у вас есть функия или функционал на каком-то множестве и вам надо найти минимум или максимум в каком-то смысле (локальный, глобальный), то в теории игр таких функций по меньшей мере две. И переменных тоже не меньше двух. Но х выбирается из соображений максимизации F(x,y), а y выбирается из соображений максимизации G(x,y).

В простом случае игры с нулевой суммой G=-F.

То есть выигрыш каждого зависит от выбора обоих, но выбирать каждый может только свои переменные.

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

В играх вроде шахмат или го информация "прячется" за сложностью расчета. А в карточных играх просто скрыта правилами игры.

Вообще же не всегда понятно, что вообще считать решением. Один из вариантов - это равновесие Нэша: ситуация, отклонение от которой никому из игроков невыгодно. То есть никто не может сделать себе лучше, отклонившись "в одно лицо".

Я записываю число и ты записываешь число. Если четность одинакова, я выиграл; если нет - ты.

Понятно, что ты сам не знаешь своего хода, но вероятность выбрать четное равна 50%. Если слишком часто выбирать чёт, я смогу этим воспользоваться. Оба мы наугад выбираем чёт-нечет. Если один решил уклониться, ему лучше не будет - а вот хуже может стать, если противник заметит тенденцию.

Пока всё хорошо, но проблемы возникают, если равновесий два или больше. Вот игра "семейный спор" с эротичным названием "the battle of the sexes". Каждый из супругов выбирает, на футбол или к маме. Пойти на футбол даёт =100 мужу и +10 жене, а к маме наоборот. Выбрав разное, они получают нули.

Равновесий два, и они очевидны. Если жена "к маме и точка!" то мужу невыгодно отклоняться. Но какое из двух равновесий выбрать? Тут начинаются сложности: и Штакельберг и с его лидерством (кто первый крикнул "к маме и точка!" тот и навяжет своё равновесие мужу), и переговорное множество (договорившись ходить в среднем одинаково они будут иметь в среднем 55, тогда как попытка настоять на своем приведет к серии нулей).

Равновесие может быть и одно, но - плохое.

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

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

И партнер это знает, и ты знаешь, и он знает, что ты знаешь, и ты знаешь, что он знает, что ты знаешь.

И нет нужды запирать их в разные камеры. Они вполне могут общаться. Всё равно выгоднее предать.

Правда, здесь игра идет один раз, а если повторы и есть (для вероятности надо), то с забыванием результатов. Если же помнить результаты, то тут аналитически не решить. Численно много пробовали, и выигрывает такая стратегия: зеркалить ходы противника, начиная с честности, и порой делая "жесты доброй воли", если что-то пошло не так.

Парадоксы в теории на каждом шагу. Вот Брайесс, например: есть две дороги, каждая из А в В, и каждая из двух кусков. Время проезда по одному куску пропорционально числу машин (N), по второму постоянно и равно 100 минут. На одной дороге сначала идет первый кусок, на второй сначала второй.

Сто водителей одновременно выезжают из А в В. Как они поедут?

Ясно, что выберут дорогу случайно с вероятностью 50%. Половина будет ехать 100 минут, потом еще 50, другая половина будет ехать 50 минут, потом еще 100.

Отклоняться никому не выгодно: тот, кто поехал "с ними" пятьдесят первым, проедет 100 минут, потом 51, проиграв своей "команде". Либо проедет 51 минуту и потом 100 с тем же результатом.

Если же посередине дороги соединили, то происходит странное: теперь все поедут по дороге с переменной пропускной способностью (100 минут), потом перестроятся на второй кусок переменной пропускной способности и потратят еще 100 минут.Всего 200, что куда хуже, чем 150 без новой дороги (!)

И это равновесие, ведь тот один, кто помчится по пустой трассе с постоянной пропускной способностью - он потратит на нее 100 минут, а потом либо еще один такой же кусок (всего 200), либо придется вливаться в поток и ехать те же 100 минут (опять 200).

Да, этот один не ухудшил результат, но остальные за его счет улучшили: ведь без него им ехать всего-то 99 минут, а потом еще 100 (если он их догонит), что всё-таки 199, а не 200.

Получается, что новая дорога может ухудшить ситуацию.

(Если заставить водителей поделиться на две "команды" и ехать по двум дорогам, то к перекрестку одна из команд приедет за 50 минут, там перестроится на вторую трассу и завершит путь еще за 50, всего 100. А вторая команда потратит 100 на первый кусок и 50 на второй, а они что же - глупее, что-ли?! Она поедут как те, и всем будет хуже.)

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

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

Источник: vk.com

Комментарии: