Коалиционные игры и жлобы на Привозе
Sep. 3rd, 2019 04:08 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
xaxam
Rational choice
Давно я что-то про математику не писал. А тут как раз повод представился.Математическая экономика во многом основана на теории игр. А теория игр - в свою очередь, - такой странноватый матан про то, как искать максимум функции. В отличие от обычного матана, где функция одна и искатель тоже один, в теории игр искателей несколько, и у каждого своя функция.
Если функции независимы друг от друга, то никакой новой задачи не появляется: каждый искатель-игрок перебирает возможные значения аргумента-стратегии и останавливается на том, который приносит максимальный выигрыш. В такой игре игрок может даже не подозревать о наличии других, ничего в поведении не изменится.
Но если выигрыш игрока зависит не только от того, какой ход сделает он, но и какой ход сделают другие игроки, - всё немедленно меняется. В своём наиболее общем варианте мы имеем набор из N игроков, у каждого из которых есть конечное множество из m_i ходов, i=1,...,N, так что в совокупности количество возможных исходов есть произведение m_1*m_2*...*m_N. Это такая очень многомерная таблица Т, и в каждой клетке такой таблицы написано, какой выигрыш ожидает каждого игрока, если реализовался именно такой вариант. В общем случае эти выигрыши могут быть какими угодно, так что количество различных игр очень велико.
Никакой "справедливости" игры априорно нет: например, в моём детстве популярна была игра "Занзибар", при которой любой ход любого из двух игроков означал, что второй платит первому копейку.
В "Занзибар", конечно, лучше не играть, но есть более справедливые игры, скажем, "камень-ножницы-бумага" (КНБ). У каждого игрока есть три варианта на выбор, и в зависимости от хода противника он выигрывает или проигрывает копейку. Специфика этой игры - нулевая сумма: выигрыш одного в точности равен проигрышу другого, общее состояние игроков не меняется. "Занзибар", кстати, тоже с нулевой суммой, но КНБ в отличие от него не вызывает ощущения несправедливой игры. Однако понять это можно только после определённых расчётов.
Все думают, что в игры играют, чтобы выиграть? Ошибка. Уж если вас усадили играть в "Занзибар" вторым игроком, ваш "выигрыш" всегда отрицательный. Но зато есть "выигрышная стратегия": она тривиальная. Как бы вы ни ходили, вы выиграете -1 копейку, и лучшего результата не сможет достичь даже гроссмейстер "Занзибара". Игра КНБ в этом смысле поинтереснее, хотя там выиграть тоже невозможно. Почему? да потому, что "платёжная таблица" не зависит от того, какой игрой первый, а какой второй (они делают ходы одновременно), так что если может выиграть положительную сумму первый, то точно так же может её выграть и второй, а это невозможно, поскольку сумма нулевая.
Ну хорошо, невозможно выиграть, а в ноль-то выйти можно? Оказывается, это сильно непросто. Какой бы из трёх ходов я не сделал, противник (если он за долю секунды догадался, как я собираюсь пойти) всегда "ответит" ходом, при котором он выиграет, а я проиграю. Единственное спасение - в одновременности: я сам не должен заранее знать, как я пойду, тогда и противник не узнает. А вот если у меня в кармане хороший датчик случайных чисел, - при любой стратегии противника я "останусь в нуле". Такая вот загогулина: нужно бежать изо всех сил, чтобы остаться на месте, а любая "сложная" стратегия, будучи разгадана, приведёт к гарантированному проигрышу.
Не самая очевидная теорема теории игр состоит в том, что в играх двух участников с нулевой суммой, даже если число вариантов ходов и больше, чем 3, всегда есть оптимальная "случайная" (на техническом жаргоне - смешанная, в отличие от чистых стратегий выбора одного из вариантов) стратегия: надо случайным образом (но с определёнными вероятностями!) выбирать один из ходов. Если так будут поступать оба игрока, каждый может себе гарантировать "в среднем" определённый выигрыш, улучшить который не получится никаким честным способом (сумма выигрышей, разумеется, будет нулевая).
Такая (относительная) простота игры двух игроков с нулевой суммой (совершенных антагонистов) связана с тем, что "платёжная таблица" - на самом деле не две, а всего одна функция с вещественными значениями, между которыми есть естественный порядок "чем больше, тем лучше". В более сложных случаях могут быть ходы, одновременно выгодные всем игрокам (одним в большей степени, чем другие). Вопрос в том, как "правильно играть" и что называть "решением игры", или равновесием (отдельный вопрос, как его искать). В одномерном случае решение игры - та стратегия (чистая или смешанная), которая доставляет наибольшее значение выигрыша каждому игроку. Наивное ожидание, - это такой выбор клетки в таблице ходов T, что ни один из участников не может улучшить своё положение, выбрав другую стратегию и не оглядываясь на других игроков*.
"Дилемма заключённого" - пример игры, при которой такое равновесие есть, но оно не оптимально в смысле выигрыша. Напомню: у каждого из двух игроков-обвиняемых по одному и тому же делу есть два хода: "сознаться" и "отрицать". Если оба сознаются - получают по десятке (-10), если оба отпираются - по году (-1 за переход улицы на красный свет). Если один сознаётся, а другой отпирается - сознавшегося отпускают, как госсвидетеля, а отпирающемуся лепят двадцать. При такой прокурорской ставке вне зависимости от того, что делает один игрок, другому - прямой резон расколоться: он либо вместо года тюрьмы получит свободу, либо вместо 20 лет - десяточку. Такое вот наказание за эгоистичное поведение и поощрение коллективизма.
И наоборот, есть игры, в которых равновесия нет вовсе, и добавление смешанных ("случайных") стратегий не спасает дело.
Но это всё в пределах теории рационального выбора, когда каждый игрок оглядывается только на свою строчку в платёжной таблице. Сплошь да рядом бывает совершенно не так: в анекдотичной форме это цитата про "отрежу себе нос, чтоб у тёщи зять безносый был", а в реаллайфе - вот, пожалуйста, свежайшее подтверждение, что нагадить тому, кого считаешь своим врагом, многим важнее, чем добиться выгоды для себя. Нобелевский лауреат Ауманн любит приводить в пример "парадокс шантажиста". Двум участникам предлагается поделить между собой 100 долларов как им угодно, но чтоб на делёж согласились оба. Если же согласия достичь не удалось, то ни один не получает ни копейки. "Справедливый вариант" поделить пополам, конечно, первое, что приходит в голову. А что, если один из игроков шантажист, и предлагает: мне 90, тебе 10? Должен ли "правильный" честный игрок на такое соглашаться? С точки зрения собственной выгоды - несомненно, ибо всяко 10 лучше, чем ноль. С другой стороны, эксперименты на людях показывают, что большинство в такой ситуации предпочитает "хлопнуть дверью". Что не так в консерватории, почему "оптимальное" решение не нравится?
Тут несколько ответов. Во-первых, бОльшая часть "абстрактных игр" (платёжных таблиц) не имеет никакого смысла (да, гнать математиков в шею!). Осмысленная теория возникает только там, где платёжные функции имеют какую-то дополнительную структуру. Например, очень красива и хорошо развита теория кооперативных (они же коалиционные, но без всякой связи с парламентами и кнессетами) игр.
Во-вторых (некое философское уже наблюдение) в парадоксе Ауманна явно присутствует "халява", т.е., игроки изначально не обладают никакими начальными условиями (например, ситуация могла бы измениться, если б один из игроков был миллионер, а второй - нищий).
Наконец, в этом парадоксе "некорректно" определена функция полезности (выигрыш). Помимо собственно суммы, которая может играть разную роль (см. выше), в функцию полезности надо ввести что-то типа чувства собственного достоинства каждого игрока. Его, конечно, долларом не померишь, но если тебе эта сотня, в общем, не слишком нужна, а обосранным чувствовать себя не хочется, то как-то надо это учитывать. Кстати, к другому игроку это тоже относится: чтоб заниматься таким шантажом, надо иметь не только желание получить побольше денег, но и садистские наклонности, за удовлетворение которых не жалко заплатить отказом от части суммы.
В общем, очень эти штуки интересны, даже безотносительно к выборам.
_________________________________________________________________
*Бытовой пример, - есть два магазина, в каждом из которых каждый из игроков покупает одну и ту же свою потребительскую корзину и, естественно, идёт в тот магазин, где цены ниже. Магазин же устанавливает цены на каждый товар в зависимости от числа покупателей: скажем, владелец хочет заработать шекель на продаже картошки, поэтому он к оптовой цене добавляет столько, чтоб этот шекель "отбить". Если есть всего один покупатель, с него запросят этот добавочный шекель целиком, а если покупателей будет 10, цена на картошку будет всего на 10 агорот выше оптовой. В этом месте есть возможность покупателям организоваться в кооператив и переходить из магазина в магазин всем вместе, но это уже будет другая игра: равновесие для отдельного покупателя - это выбор, обеспечивающий минимальную стоимость именно его корзины.
no subject
Date: 2019-09-03 02:24 pm (UTC)no subject
Date: 2019-09-03 02:35 pm (UTC)На самом деле, безотносительно к склонностям Биби к интригам, он всякий раз показывает мастер-класс.
В данном случае - тайминг: переговоры с микропартиями, чтобы не утекли в никуда голоса их избирателей, он ведёт уже после закрытия списков. Соответственно, все вопросы о том, куда поставят свежекупленного и кому из своих придётся подвинуться, убраны с повестки дня. Микропартийцы имеют дело с типичной дилеммой шантажиста: либо пролететь, не получив ничего, либо выторговать себе хоть что-то под слово Биби, известно сколько стоящее. Но с точки зрения лидеров микропартий, легче свалить вину на Биби (подманул и бросил), чем отвечать партбилетом, почему не вытянул избирательный ценз, и есть ли кто поблизости, кто вытянул бы.
От Моше до Моше не было никого, подобного Моше (с). Интриган Перес ворочается в гробу от зависти.