| Об эгоизме без политики |
[Sep. 11th, 2025|06:46 am] |
Что такое альтруизм с точки зрения математикиПочтеннейший  lazybiker мне прислал ссылку на замечательный видеоклип, посвящённый тому, что с эволюционной точки зрения выгоднее, эгоизм или альтруизм. Теоретически каждый сам может посмотреть этот клип (он на русском), не читая нижеприведённый текст. Но мне кажется, что этот текст может послужить полезным предисловием для тех, кто никогда не сталкивался вообще с теорией игр и принятия решений. По техническим причинам он будет разбит на несколько постов.
 Теория игр: почём за вист?Давайте поговорим о том, что есть вся наша жизнь — игра.
Понятие игры выросло из понятия максимизации (ну, или минимизации), которую человечеству приходилось решать со времён царя Гороха. Есть несколько вариантов, каждый из которых имеет свою цену (ну, или наоборот, выгоду, полезность), надо выбрать наилучший вариант. Если вариант всего один, то задачи нет. Выбор из двух вариантов учатся делать младенцы, а из конечного (небольшого) числа — младшеклассники, которых учат сравнивать числа. Сложность возникает тогда, когда вариантов слишком много, чтобы их перебирать. Например, классическая "задача Дидоны" (она же изопериметрическая задача) — имея замкнутую верёвку длиной 100 метров, выложить её на землю так, чтобы огородить наибольшую площадь. Другая задача (описывающая преломление света) — скорейший путь. Есть пустошь и вспаханное поле, граница между которыми — прямая линия. Человек идёт по пустоши быстрее, чем по полю (скорости известны). Вбиваем два колышка: один на пустоши, другой на поле. Как проложить самый быстрый путь между колышками? Хорошо если колышки вбиты на одном перпендикуляре к границе между пустошью и полем: иди по прямой, и уж сколько понадобится, столько и потратишь времени, меньше никак не получится (почему?). А если нет? Если прямая линия между колышками пересекает границу под острым углом? Очевидный ответ: надо наметить себе точку на границе, и идти вдоль прямых отрезков, соединяющих эту точку с двумя колышками. Но где выбрать эту точку? Все сказанные задачи сводятся к поиску минимума/максимума функции одной переменной, таким задачам учат первокурсников.
Богатство выбора может быть ещё больше. Представим себе "водную горку", по которой дети с определённой высоты скатываются и плюхаются в бассейн с водой. Стартовая и финишная точки фиксированы, но собственно форма горки — в нашем распоряжении. Как выбрать эту форму так, чтобы ребёнок скатывался за кратчайшее время? (Задача была поставлена в 1696 году и решена независимо всей плеядой тогдашних великих математиков — братьями Бернулли, Лопиталем, Ньютоном и Лейбницем). С математической точки зрения задача сводится к минимизации "функции бесконечного числа переменных", т.н. вариационной задаче, решению которых учат уже на старших курсах. Но идейно все такие задачи различаются только техникой максимизации.
Игры — принципиально иной класс задач. В теории игр есть не одна-единственная функция, которую нужно максимизировать, а несколько разных функций, по числу игроков. Если каждая функция задана на своей области определения и они никак не связаны между собой, то игроки не обращают друг на друга внимания и каждый решает свою задачу оптимизации. Движуха возникает, когда функции определены на общей области определения. В простейшей ситуации, когда у нас два игрока и минимальная область определения, возникает следующая задача. Пусть первый игрок "управляет" переменной икс, принимающей значения, скажем, на отрезке [a,b], а второй управляет игреком, который можно выбрать из отрезка [c,d]. Первый игрок хочет максимизировать некую функцию f, второй — свою функцию g. Если бы f зависела только от x, a g — только от y, мы бы имели две не связанные оптимизационные задачи. Но мы хотим исследовать именно движуху, когда обе функции зависит каждая от обеих переменных, f = f(x,y), g = g(x,y). Обе функции известны обоим игрокам, но свой выбор (икс и игрек) они делают независимо и одновременно друг от друга.
Почему это важно? Предположим, что функция g на самом деле не зависит от икса. Тогда стратегия второго игрока очевидна: он максимизирует свою функцию g, выбирая нужный игрек, y0. Зная это, первый игрок будет рассматривать функцию только одной переменной, f(x,y0), и выберет значение икса, дающего максимум. Никакой интриги нет.
Альтернативная игра (кажется, простейшая возможная) — каждый из двух игроков кладёт на стол монету, орлом или решкой вверх. Первый игрок получает рубль, если две монеты легли одинакого, и ничего не получает, а второй получает рубль, если монеты легли разными сторонами (и ничего, если одинаково). В этой ситуации если один из игроков положит свою монету на долю секунды раньше — он не получит ничего, а второй получит свой рупь. Никакой "оптимизации" и близко не просматривается. Чуть более сложный вариант той же игры — "камень, ножницы, бумага". В обоих случаях каждый из игроков выбирает один из двух (или трёх) возможных ходов, так что никаких технических проблем с нахождением максимумов нет, есть исключительно концептуальные.
Можно ли хоть в каких-то ситуациях предсказать "оптимальное поведение" игроков? Один тривиальный случай мы уже разобрали, не найдя в нём ничего интересного. Оказывается, можно найти чуть менее тривиальный, но всё ещё полностью обозримый случай. Это так называемые игры с седловой точкой.
Определение. Седловой точкой игры называется такая (допустимая, разумеется) пара, "совместный" выбор двух игроков (x0, y0), который ни один из игроков не хочет менять ни на что другое. Это значит, что выгода первого игрока f(x,y0), рассматриваемая как функция одной переменной ("своей", икса) достигает максимума "как раз" в точке x0, и одновременно с этим выгода второго игрока g(x0, y) как функция "своего" игрека тоже достигает максимума "как раз" в точке y0.
Такая седловая точка приносит одновременный максимум обоим игрокам. При одном условии: если она существует. Каждый из игроков, зная функции выгоды (свою и противника) может (в случае конечного числа возможных ходов) перебрать все возможные пары исходов, и если среди них найдётся седловая точка, то каждый из игроков выберет именно её за неимением лучшего варианта.
Но вот беда. Даже самая простая игра "в две монетки" не имеет седловой точки! В самом деле, все многообразие возможных ходов сводится к четырём: (О,О),(О,Р), (Р,О) и (Р,Р). Проверьте, что (одномерная) максимизация выгоды, скажем, первого игрока зависит от выбора второго (и наоборот), поэтому универсального выигрышного варианта тут нет (это, впрочем, и так очевидно). Что же делать?
Ответ угадал один из самых гениальных и разносторонних математиков 20 века, Джон (Янош, Янчи) фон Нойман сто лет назад, в 1928-м году. Он придумал понятие смешанной стратегии, расширения игры, включающего генератор случайных чисел. Пафос в том, что показания датчика случайных чисел неизвестны никому, включая того игрока, который им пользуется. Стратегия состоит в настройке датчика.
Проще всего объяснить понятие смешанной стратегии в случае, когда множество допустимых ходов каждого игрока — конечное множество вариантов x1, x2, ... , xn и y1, y2, ... ym соответственно.
Определение. Смешанная стратегия игрока, контролирующего иксы, есть распределение вероятностей на пространстве ходов, приписывающее ходу xi неотрицательную вероятность pi, i = 1, ..., n, так, чтобы сумма вероятностей была единичной. Соответствующей смешанной стратегии xp приписывается "расширенная функция выгоды" f(xp,y) = ∑ pi f(xi,y) (обычное математическое ожидание, никаких сюрпризов). Аналогично определяются смешанные стратегии второго игрока.
Какое радикальное изменение с точки зрения математики произошло при рандомальном расширении игры, допускающем смешанные стратегии?
Гигантское.
В исходной постановке пространства допустимых ходов были конечными множествами без всякой дополнительной структуры. Функции выгоды каждого из игроков задавались таблицами ("платёжными матрицами"), тоже априори не несущими никакой структуры. С введением смешанных стратегий мы фактически заменяем дискретное конечное пространство допустимых ходов геометрической фигурой, называемой симплексом: множеством точек в ℝⁿ с неотрицательными координатами, в сумме дающими единицу. Это — топологическое пространство, "непрерывное" (без разрывов, дыр и скачков), и рандомально расширенная функция выгоды будет автоматически непрерывна по всем переменным. Это обстоятельство, в свою очередь, позволяет "интерполировать" конкретные допустимые ходы, заменяя их "лотереей", исход розыгрыша которой неизвестен никому, пока ход не сделан.
Фон Нойман доказал (очень несложными рассуждениями), что в одном, но практически очень важном классе игр с нулевой суммой (когда выигрыш одного игрока равен проигрышу другого, т.е., цели игры абсолютно антагонистичны) рандомально расширенная игра, допускающая смешанные стратегии, всегда имеет седловую точку. Иными словами, каждый игрок имеет выигрышную беспроигрышную стратегию. В случае игры в две монетки достаточно бросать свою монетку случайным образом. (Технически эта игра с ненулевой суммой, но её можно свести к чисто антагонистической, когда при совпадении второй платит первому полтинник, и наоборот, получает от первого полтинник, когда монетки легли разными сторонами).
Следующий ключевой шаг в теории игр сделал гениальный безумец Джон Форбс Нэш, получивший нобелевку по экономике за свою кандидатскую (Ph.D.) диссертацию. Он обобщил понятие седловой точки в игре двух игроков с нулевой суммой до понятия "равновесия по Нэшу". Глобально идея та же самая: есть несколько игроков, каждый выбирает из конечного множества доступных ему ходов, все игроки вместе определяют "коллективный ход". Такой ход называется "равновесным по Нэшу", если ни один игрок не имеет причины сменить свой выбор (увеличив свою личную выгоду) при условии, что остальные его не поменяют.
Теорема Нэша утверждает, что равновесие по Нэшу всегда существует в классе смешанных стратегий (т.е., при описанной выше рандомизации игры). В отличие от конструктивного доказательства фон Ноймана, доказательство Нэша опирается на самые общие топологические теоремы анализа (типа теорем о невозможности причесать круглого ежа).
Что мы имеем с игривого гуся? Парето-оптимальностьМы имеем попытку определить, что такое "решение игры", т.е., аналог понятия мульти-максимума, одновременного максимума нескольких функций, описывающих выгоду. Такие попытки предпринимались сотни лет назад. В частности, Вильфредо Парето (сто лет назад) явно сформулировал концепцию, которая была очевидна всем на свете. Что такое "максимум векторнозначной функции"? Например, каждой точке из допустимого множества вариантов сопоставим точку на плоскости "оценок" ℝ² с координатами x,y. Как определить одновременный максимум обеих координат на множестве М допустимых вариантов? Проще объяснить, что не является максимумом. Допустимая точка (x0,y0) не является одновременным максимумом, если существует другая допустимая точка (x1,y1) такая что x0 ≤ x1 и y0 ≤ y1, причём хотя бы одно из неравенств является строгим. Мы будем называть такое отношение порядка "слабым улучшением" за неимением лучшего слова ("кому-то приятно, а остальным всё равно", как в анекдоте). Если мы выбросим все точки, которые остаются, то мы получим "северо-восточную границу" множества М на плоскости. Такие точки на границе называются оптимальными по Парето (или парето-оптимальными). Плюс такого понятия — парето-оптимум существует в разумных технических предположениях (например, когда множество М компактно). Минус, — таких оптимумов обычно слишком много, если мы хотим определённости, то надо как-то сравнивать между собой независимые критерии оценки x, y. Но главное, "ключевое" свойство парето-оптимальности — любое "разумное" определение решения игры должно быть парето-оптимальным, т.е., не допускать слабого улучшения.
В самом деле, если есть две пары ходов, (x0,y0) и (x1,y1) (ахтунг: икс и игрек теперь обозначают допустимые ходы двух игроков), и при этом f(x0,y0) ≤ f(x1,y1) и g(x0,y0) ≤ g(x1,y1), где f, g — функции выгоды этих игроков и хотя бы одно из неравенств является строгим, то оба участника заинтересованы в том, чтобы променять (x0,y0) на (x1,y1): это будет слабым улучшением, ни один из них от такой смены не проиграет, а один даже выиграет (мы считаем, что "злорадство" не является фактором в игре, каждый смотрит только на свою выгоду).
Понятие парето-оптимальности кажется совпадающим с понятием равновесия. И равновесие по Нэшу, и парето-оптимальность состояния (x0,y0) "неформально" означают, что ни один игрок не может улучшить своё состояние, избрав альтернативный вариант своего хода. Но как всегда, тонкости в деталях. Равновесие по Нэшу означает, что ни один из игроков не может в одиночку увеличить свой выигрыш при условии, что второй игрок сохраняет свой выбор (если игроков больше двух, то в предположении, что свой выбор сохраняют все остальные игроки). Напротив, парето-оптимальность подразумевает, что, даже действуя вскладчину (кооперируясь, согласовывая свои ходы), игроки не смогут слабо улучшить свои результаты.
 Дилемма заключённогоИз приведённого описания следует, что парето-оптимальное решение будет равновесием по Нэшу: если его нельзя слабо улучшить коллективными усилиями, значит, усилиями каждого игрока его и подавно нельзя слабо улучшить.
Но может быть, по каким-то причинам, по крайней мере для не слишком сложных игр верно и обратное, и равновесие по Нэшу будет парето-оптимальным? Увы, всего спустя всего 6 лет после выхода эпохальной монографии фон Ноймана и Моргенштерна "Теория игр и экономическое поведение" в 1944 году, двое сотрудников RAND Corporation описали игру (не антагонистическую), когда равновесие по Нэшу не является парето-оптимальным. В привычном виде под названием "Дилемма заключённого" её сформулировал Альберт Таккер.
Если вдруг кто-то случайно не слышал про этот шедевральный пример, вот в чём состоит игра. Прокурор посадил в КПЗ двух подозреваемых в совершении преступления, они сидят в разных камерах и не могут общаться между собой. Прокурор пытается "расколоть" их, каждого по отдельности, признаться в совершении преступления. У каждого из двух есть две опции: говорить или молчать. Прокурор сочетает кнут и пряник и говорит каждому из подозреваемых: если вы оба сознаетесь, я дам вам по "двушечке", просто чтоб не оставлять преступление безнаказанным. Если один из вас сознается, а второй будет молчать — сознавшийся получает прощение за сотрудничество с прокуратурой, а упрямцу я вкачу червонец. Наконец, если вы оба будете молчать — я посажу вас обоих на полгода каждого за нарушение общественного порядка.
В этой игре, как и следовало ожидать, есть равновесие по Нэшу, и даже в чистых (а не в смешанных, рандомизированных) стратегиях. Но оно "парадоксально": обоим подозреваемым есть смысл расколоться и признаться. Почему? Рассмотрим первого игрока. Если он выбирает "говорить", то в зависимости от того, что сделает второй, первый получит либо двушечку, либо вообще помиловку. Если же он будет упираться, то получит либо червонец (вместо двушечки), либо полгода (вместо помиловки). В обоих случаях первому выгодно расколоться. Поскольку ситуация симметрична, те же аргументы справедливы и в отношении второго игрока. Итак, вариант "расколоться" выгоден обоим с точки зрения равновесия Нэша, и оба присядут на двушечку. Но это же глупость: если б они смогли скооперироваться и оба отпирались бы, то каждый получил бы по полгода, что как ни крути лучше двушечки. Тем самым равновесие по Нэшу не парето-оптимально.
Вопрос можно переформулировать в несколько иной форме. У игроков есть кооперативная "альтруистская" стратегия (оба молчат), и при этом у каждого есть "эгоистическая" стратегия обеспечить себе лучший из вариантов при любом действии партнёра. Парадокс заключённого обычно интерпретируется как дилемма между альтруизмом и эгоизмом: альтруизм выгоден "коллективу" (обоим игрокам), а эгоизм - каждому по отдельности.
Положение скверное. Мы (ну, не мы, а Нэш, конечно) придумали понятие решения игры, которое прекрасно тем, что всегда существует. Но беда в том, что оно "плохое", а мы за всё хорошее, в частности, за то, чтобы лучше было всем. Можно ли что-нибудь сделать в такой ситуации?
Чтобы сделать альтруистический выбор, надо иметь "доверие к партнёру", какую-то уверенность, что он будет руководствоваться общей выгодой, а не своей личной. Но понятие доверия не входит в лексикон теории игр, значит, его надо чем-то заменить. Но чем? Ответ — послужным списком. А как именно — я расскажу в следующий раз. |
|
|
sick
sleepy
![11949546_1648478322099168_6847280136997309962_n[1].jpg](https://ic.pics.livejournal.com/iris_sibirica/2965997/3570126/3570126_600.webp "11949546_1648478322099168_6847280136997309962_n[1].jpg")
