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

Многие читатели, возможно, знакомы с равновесием Нэша по одному весьма распространённому его частному случаю — так называемой «дилемме заключённого». Его суть примерно в следующем.

В тюрьме находятся два заключённых, которых взяли с поличным по отдельности, но ещё подозревают в более тяжких преступлениях. Если участие докажут, то срок заключённых возрастёт до десяти лет. Сейчас же они отсиживают по году каждый. Следствие предлагает каждому из них пойти на сделку и дать показания против второго. В этом случае первому срок скостят до полугода, а второй сядет на десять. Однако заключённые понимают, что если они оговорят друг друга, то вряд ли их обоих пощадят — скорее добавят каждому ещё лет по пять.

Расклад можно отобразить при помощи следующей таблицы.

Первый хранит молчание Первый даёт показания
Второй хранит молчание Обоим по году Первому полгода
Второму десять лет
Второй даёт показания Первому десять лет
Второму полгода
Обоим по пять лет


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

Заключённый, разумеется, хочет наименьшего срока для себя. Но если он будет хранить молчание, то, возможно, его коллега даст против него показания, чем повысит ему срок до десяти лет. Если бы не обещанное снижение срока, то можно было бы тешить себя мыслью «а зачем мне это?», но соблазн снизить срок слишком вели́к. Кроме того, второй заключённый, как понимает первый, будет подозревать его, первого, в том, что он даст показания против второго и повысит тем самым ему срок.

«Обидно будет оказаться крайним и загреметь на десять лет», — думает первый. Но «и второй наверняка думает так же, и так же подозревает меня, — понимает он, — а потому шансов, что коллега меня не заложит, очень мало. Выходит, надо давать показания: если второй каким-то чудом промолчит, то будет полгода, проговорится — пять. Ну хоть не десять, которые я неизбежно получу из-за разоткровенничавшегося со следствием моего подельника!».

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

Можно сказать, что для каждого из заключённых он не так плох: всего пять лет против десяти в «зелёном» варианте в пользу подельника. Однако представим, что в «красном» варианте обоим дадут по десять. Логика в данном случае чуть-чуть поменяется: «если я его сдам, то хотя бы есть шанс отвертеться от десяти лет, а если промолчу — шансов нет, он меня наверняка заложит по тем же соображениям». Однако тут система подталкивает заключённых выбрать наихудший вариант из возможных. Действуя, что характерно, строго ради своей выгоды.

Рассмотрим теперь ещё одну ситуацию. Есть две фирмы — А и Б. Каждая из них может воспользоваться стратегией — Икс или Игрек. Однако на результаты оказывает влияние не только стратегия, выбранная самой фирмой, но и стратегия второй фирмы тоже. Выигрыш или проигрыш каждой из фирм мы представим в виде следующей таблицы.

А использует стратегию Икс А использует стратегию Игрек
Б использует стратегию Икс А: +100 рублей
Б: +100 рублей
А: +1000 рублей
Б: –110 рублей
Б использует стратегию Игрек А: –110 рублей
Б: +1000 рублей
А: –100 рублей
Б: –100 рублей


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

Запишем вышеприведённые матрицы в более общем виде, абстрагировавшись от «фирм», «заключённых», «сроков» и «рублей». Положим, что у нас просто есть два игрока А и Б, играющие в некоторую игру, где на каждом ходе можно совершить один из двух ходов — Икс или Игрек. Выигрышем являются просто некие «баллы», наибольшее число которых каждый игрок и стремится набрать.

А делает ход Икс А делает ход Игрек
Б делает ход Икс А: a0
Б: b0
А: a1 > a0
Б: b1 < b3
Б делает ход Игрек А: a2 < a3
Б: b2 > b0
А: b3
Б: a3


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

В частности, на выбор может влиять среднее арифметическое выигрышей при выборе каждой из стратегий, а также предположительная вероятность, с которой игрок сделает тот или иной ход (которая, кстати, может быть аппроксимирована частотой ходов, сделанных в предыдущих раундах). Так, в простейшем случае игрок А для оценки хода Икс складывает a0 и a2 и делит результат на два, полагая выбор хода со стороны Б равновероятным. То же самое он проделывает для хода Игрек — складывает a1 с a3, после чего делит результат на два — и сравнивает результаты. В более сложном случае игрок считает сумму a0*px + a2*py, где px и py — вероятности ходов Икс и Игрек, сделанных игроком Б. Результат сравнивается с a1*px + a3*py.

Можно было бы, конечно, снова поделить результат на два, но поскольку деление на два имеет место быть для обоих вариантов хода, для сравнения величин эта операция необязательна, как, впрочем, и в случае «равновероятных ходов».

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

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

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

Есть как бы «невидимая рука рынка», которая как бы невидимо подталкивает игроков… ну, вы знаете. Точнее, нет, может быть, и не знаете. В классическом варианте «рука рынка» как бы подталкивает куда всем надо, а тут она толкает совсем не туда. Не во всеобщее благо, а в перманентный кризис, которого при иных раскладах можно было бы избежать, что нам иллюстрирует и «дилемма заключённого», и гипотетический пример с конкуренцией фирм, и реальный пример с неизбежным завышением сроков разработки софта, о котором речь шла в предыдущей статье.

Рынок толкает игроков к равновесию Нэша, которое сколь угодно далеко может отстоять от их общего и личного блага.

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

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

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


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



Публикация в блоге автора
Публикация на «Однако»
doc-файл



Метки:

  • 1
Я смотрел на эти игры с котенком, а мне виделись другие люди и другие игры

Дилемма заключенного решается к обоюдной выгоде за счет передачи информации между преступниками и наличием контролирующего органа. Сдал своего - через пол года ноги в таз, цемент и море.

Ужель Вы ратуете за организованную преступность?

Edited at 2013-10-08 08:40 (UTC)

Ну, уж если лезть в грубую реальность, то на практике вариант "оба стучат друг на друга" может оказаться хуже, чем "один стучит, другой молчит". Дело в том, что для многих категорий преступлений существует такое отягчающее обстоятельство, как совершение преступления группой лиц (по предварительному сговору, или без). И тогда если оба заложат друг друга, они как соучастники пойдут по более тяжкой статье (части статьи) и, соответственно, получат большее наказание, чем получил бы любой из них, если бы его всего лишь сдал подельник. Это часто используется на практике: обвиняемым делают одного из банды, а соучастники идут как свидетели, максимум - как пособники, а не соисполнители. Выгода:
а) обвиняемый получает более "лёгкую" статью;
б) "свидетели" вообще освобождаются от наказания или же получают его условно или "ниже низшего";
в) следователь вместо "глухаря" получает раскрытое дело, которое не развалится в суде.

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

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

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

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

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

> Ужель Вы ратуете за организованную преступность?

# Не могу представить - что может подвигнуть к этому идиотскому предположению?

Так все очевидно. Как преступникам минимизировать проблемы?

> Так все очевидно.

# Что очевидно? Что автор ратует за организованную преступность? Покажи пальцем - где такое написано?

> Как преступникам минимизировать проблемы?

# Купи учебник логики - пригодится.

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

> Ладно попробую дать более развернутое объяснение,

# Сынок, что заставляет вести себя как мудак?

> Продолжать дальше?

# Сынок, купи учебник логики. Ибо ты сейчас несешь - иррациональную ахинею.

А почему бы А не договориться с Б о том, что бы Б реализовывал стратегию X за щедрую компенсацию в 555 рублей?

А об этом уже сказано: стихийно сложившееся положение может сломать только сговор.

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

> Собственно, равновесие Неша и иллюстрирует математически тот факт, что есть ситуации, в которых сговор дает явный выигрыш. За это его и любят сторонники централизации.

А я вспоминаю известный рассказ о эксперименте с обезьянами и бананом в клетке.

- Уже ни одной в клетке не осталось которую обливали водой, но банан брать нельзя.
- Почему?
- Потому что тут так принято, бля!

А где гарантия, что потом отдаст?

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

Трагедия общин

http://zakroiteduet.ru/all/tragediya-obschin/

Классическая задачка, когда ВЫГОДНАЯ ДЛЯ КАЖДОГО ИНДИВИДУАЛЬНАЯ стратеги ведёт К ОБЩЕЙ ТРАГЕДИИ.

Как бы ещё более общая и известная

Re: Трагедия общин

> Классическая задачка, когда ВЫГОДНАЯ ДЛЯ КАЖДОГО ИНДИВИДУАЛЬНАЯ стратеги ведёт К ОБЩЕЙ ТРАГЕДИИ.

Рассматривал Кравецкий это, на примере компьютерной игры.


Edited at 2013-10-08 13:56 (UTC)

Re: Трагедия общин

Годный пример.

Re: Трагедия общин

Следующий вопрос, несколько отстоящий от равновесия Неша, как поделить результаты выгодного управления?

Слова в предыдущей статье надо делать ссылкой на эту статью.

интересная теория

На практике есть простая линейная зависимость-
Меньше скажешь = Меньше будешь сидеть

Выше товарищи объяснили почему невыгодно сдавать подельников. Но это частный случай, общение с органами вообще не выгодно - 51 статья.

>>Со слов "Положим, что у нас просто есть два игрока А и Б, играющие в некоторую игру, где на каждом ходе можно совершить один из двух ходов — Икс или Игрек. Выигрышем являются просто некие «баллы», наибольшее число которых каждый игрок и стремится набрать" -- и до конца статьи.

Сейчас различных на бизнес-тренингах проводят вышеописанную игру, причем именно в понятиях: - "икс, игрек, ход, команда А, Б..." - без привязки к чему-то конкретному. Самому как-то доводилось принимать участие.

Участников разбивают на 4-5 команд, объясняют как отразится "ход" на их показателях (и показателях соперников), и дают возможность выбирать игреки или иксы. Бонусом идут ежеходные повышающие или понижающие коэффициенты, - усиливающие жажду наживы и стремление "кинуть" остальные команды в самый неподходящий момент.
Обычно все уходят в дикие минуса и начинают грызться друг с другом, - а гордый собой ведущий объявляет, дескать: - "А вот если бы вы все выбрали по +100 баллов каждый ход всем, а не +1100 для себя (и -500 остальным), -- то вы бы все выиграли, а не проиграли. В общем вы все лузеры, а я тут единственный стратег :)".

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

Edited at 2013-10-09 20:54 (UTC)

народ попер в комментариях явно не туда.

"Если в некоторой игре с произвольными количеством игроков и матрицей выигрышей существует такое состояние, что при выборе не соответствующего ему хода любым из игроков в отдельности его личный выигрыш уменьшится, то это состояние окажется «равновесным» для данной игры."
пойду, что ли почитаю доказательство, очень интересно.

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

Ну так же ж - http://lex-kravetski.livejournal.com/363345.html

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

  • 1
?

Log in

No account? Create an account