что же тут сложного? в добровольной сделке теоретически результаты всегда положительны для участников. как минимум
ой, да с фига ли? сделка дарения вполне себе добровольная, при этом финансовый результат для одного из ее участников строго отрицательныйi
игра называется кооперативной, или коалиционной, если игроки могут объединяться в группы, взяв на себя некоторые обязательства перед другими игроками и координируя свои действия. этим она отличается от некооперативных игр, в которых каждый обязан играть за себя. развлекательные игры редко являются кооперативными, однако такие механизмы нередки в повседневной жизни
часто предполагают, что кооперативные игры отличаются именно возможностью общения игроков друг с другом. в общем случае это неверно. существуют игры, где коммуникация разрешена, но игроки преследуют личные цели, и наоборот
из двух типов игр, некооперативные описывают ситуации в мельчайших деталях и выдают более точные результаты. кооперативные рассматривают процесс игры в целом. попытки объединить два подхода дали немалые результаты. так называемая программа Нэша уже нашла решения некоторых кооперативных игр как ситуации равновесия некооперативных игр
гибридные игры включают в себя элементы кооперативных и некооперативных игр. например, игроки могут образовывать группы, но игра будет вестись в некооперативном стиле. это значит, что каждый игрок будет преследовать интересы своей группы, вместе с тем стараясь достичь личной выгоды
игра будет симметричной тогда, когда соответствующие стратегии у игроков будут равны, и имеют одинаковые платежи. иначе говоря, если игроки могут поменяться местами и при этом их выигрыши за одни и те же ходы не изменятся. многие изучаемые игры для двух игроков — симметричные. в частности, таковыми являются: "Дилемма заключённого", "Охота на оленя", "Ястребы и голуби". в качестве несимметричных игр можно привести "Ультиматум" или "Диктатор"
многие игры (в том числе "Дилемма заключённого"), иного рода: в играх с ненулевой суммой выигрыш какого-то игрока не обязательно означает проигрыш другого, и наоборот. исход такой игры может быть меньше или больше нуля. игрой с отличной от нуля суммой является торговля, где каждый участник извлекает выгоду. широко известным примером, где сумма (выгода) уменьшается, является война
в параллельных (статических) играх игроки ходят одновременно, или, по крайней мере, они не осведомлены о выборе других до тех пор, пока все не сделают свой ход. в последовательных (динамических) играх участники делают ходы в заранее установленном либо случайном порядке, но при этом они получают некоторую информацию о предшествующих действиях других. эта информация может быть даже не совсем полной, например, игрок может узнать, что его противник из десяти своих стратегий точно не выбрал пятую, ничего не узнав о других
различия в представлении параллельных и последовательных игр - первые обычно представляют в нормальной (матричной) форме, а вторые — в экстенсивной (древообразной)
важное подмножество последовательных игр составляют игры с полной информацией. в такой игре участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры. полная информация не доступна в параллельных играх, так как в них неизвестны текущие ходы противников. большинство изучаемых в математике игр — с неполной информацией. например, вся "соль" "Дилеммы заключённого" или "Сравнения монеток" заключается в их неполноте
в то же время есть интересные примеры игр с полной информацией: "Ультиматум", "Многоножка". сюда же относятся шахматы, шашки, го, манкала и другие
часто понятие полной информации путают с похожим - совершенной информацией. для последнего достаточно лишь знание всех доступных противникам стратегий, знание всех их ходов необязательно
в играх с полной информацией каждый из игроков имеет полную информацию о "платежных функциях" каждого игрока. в этом случае они могут исключить из рассмотрения заведомо проигрышные стратегии других игроков, а это, в свою очередь, может повлиять и на выбор собственной стратегии. в играх с неполной информацией некоторые из игроков (по крайней мере один) не располагают полной информацией о "платежных функциях" всех других игроков и тогда они ориентируются на свою функцию выигрыша и на вероятностное распределение на множестве возможных функций выигрыша других игроков. полезность информации приводит к вопросу о возможности ее приобретения, например покупки
в играх с совершенной информацией каждый игрок при осуществлении своего хода знает всю предысторию развития игры, т.е. всю последовательность осуществляемых игроками ходов от начала игры до текущего момента. в играх с несовершенной информацией хотя бы один из игроков при осуществлении какого-то своего хода не располагает полным знанием всей предыстории развития игры. например, игрок на четвертом ходе не знает, каков выбор сделал его противник на предыдущем ходе
игра в "чет-нечет". Саша и Маша одновременно загадывают числа: Саша выбирает x∈{1;2}, Маша — y∈{1;2}. если сумма s=x+y четная, то результат Саша/Маша равен (1;-1), т.е. выигрыш Саши равен 1, Маши равен -1. если сумма нечетная, то результат проитвоположен: (-1;1). очевидно, игра статическая (игроки делают выбор одновременно), с полной совершенной информацией (игра одноходовая, в ней не существует предыстории). но можно игру представить и в несколько ином в виде. Саша ходит первым - он выбирает число x и записывает его в конверт. на следующем шаге Маша, не зная x, выбирает y, после чего игра заканчивается и игроки получают свои выигрыши. дерево игры:
игры в реальном мире или изучаемые в экономике игры, как правило, длятся конечное число ходов. математика не так ограничена, и в частности, в теории рассматриваются игры, способные продолжаться бесконечно долго, причём победитель и его выигрыш не определены до окончания всех ходов - на описании одной такой игры основано определение аксиомы детерменированности в теории множеств
задача, которая обычно ставится в этом случае, состоит не в поиске оптимального решения, а в поиске хотя бы выигрышной стратегии
используя аксиому выбора, можно доказать, что иногда даже для игр с полной информацией и двумя исходами — "выиграл" или "проиграл" — ни один из игроков не имеет выйгрышной стратегии. существование выигрышных стратегий для некоторых - особенным образом сконструированных - игр имеет важную роль в дескриптивной теории множеств
большинство изучаемых игр дискретны: в них конечное число игроков, ходов, событий, исходов и т.п. однако эти составляющие могут быть расширены на множество вещественных чисел
дифференциальные игры - это игры, включающие множество вещественных чисел. они связаны с какой-то вещественной шкалой (обычно шкалой времени), хотя происходящие в них события могут быть дискретными по природе. дифференциальные игры рассматриваются в теории оптимизации
метаигры - это такие игры, результатом которых является набор правил для другой игры (называемой целевой или игрой-объектом). цель метаигр - увеличить полезность выдаваемого набора правил. теория метаигр связана с теорией оптимальных механизмов
игра в нормальной форме задаётся
игра в развернутой форме представлется в виде ориентированного дерева, где каждая вершина соответствует ситуации выбора игроком своей стратегии, а платежи записываются под каждой листовой (терминальной) вершиной
по теореме Кона обе эти формы задания игры - эквивалентны
игроки могут приписать ВЕРОЯТНОСТИ каждому своему возможному выбору. при этом игрок максимизирует МАТОЖИДАНИЕ своего выигрыша. подобные стратегии игроков называются СМЕШАННЫМИ
игры, в которых существенна многоходовость задаются в развернутой форме (при этом возможно, что ход делает Nature - т.е. вероятности заданы априори)
стратегия "x" игрока доминирует его же стратегию "y" ("x" называется доминирующей стратегией, а "y" называется доминируемой стратегией), если при любом фиксированном наборе стратегий остальных игроков выигрыш при использовании "x" больше, чем при использовании "y"
если игроки могут договариваться (так, чтобы договорённости нельзя было нарушить - так называемые "корпоративные игры"), то имеет смысл понятие "эффективности по Парето": набор стратегий игроков (по одной для каждого) эффективен по Парето, если нет никакого другого набора стратегий, который КАЖДОМУ игроку давал бы строго БОЛЬШИЙ выигрыш
набор стратегий игроков (по одной для каждого) называется "равновесием Нэша", если никакой игрок не может поменять свою стратегию и получить строго БОЛЬШИЙ выигрыш вне зависимости от действий других игроков
равновесий Нэша может быть несколько. равновесий Нэша может вообще не быть. любая строго доминируемая стратегия не может входить ни в какое равновесие Нэша
если последовательно вычеркивать строго доминируемые стратегии, то получим равновесие Нэша (когда вычеркивать будет уже нечего, так как все оставшиеся стратегии будут доминирующими), причем порядок вычеркивания не важен - результат будет всегда один и тот же
в любой конечной игре есть равновесие Нэша в смешанных стратегиях
смешанные стратегии - это симплекс, вершинами которого являются чистые доминирующие стратегии. для случая двух чистых стратегий - это отрезок; для трех - треугольник; для четырех - тетраэдр; и так далее (симплексом в ℝⁿ называется выпуклая оболочка множества из n+1 точек в ℝⁿ, каждая из которых имеет все нулевые координаты, кроме одной координата которой равна 1. иногда такой симплекс называют "натянутым на точки")
игра является симметричной, если
в любой конечной симметричной игре существует равновесие Нэша (чистое или смешанное). при этом если равновесие Нэша является смешанным, то ни одна из стратегий игроков не содержит доминируемых чистых стратегий. для конкретного игрока - это всегда грань симплекса смешанных стратегий, натянутая на ДОМИНИРУЮЩИЕ чистые стратегии игрока (а поскольку игра симметрична, то эта грань - общая для всех игроков)
Th Брауера: если Х есть конечномерный выпуклый компакт, а f:X→X непрерывное однозначное отображение, то существует "неподвижная точка" x из Х, такая что f(x)=x
Теорема Какутани: пусть Х есть конечномерный выпуклый компакт и есть многозначное обображение Ф:Х→Х (каждой точке x из Х может быть сопоставлено подмножество Х), такое что
(1) образ x замкнут в прямом произведении Х на Х и
(2) образ х есть непустой выпуклый компакт
тогда существует "неподвижная точка" х из Х, такая что х ∈ Ф(х)
игра с неполной информацией - это
({i}, {Si}, {Αi}, {ui})
{i} - множество игроков, M
{Si} - множество наборов стратегий игрокa i
{Αi} - множество типов игрока i
{ui} - множество функций выплат S ⨯ Α → ℝ
если агент не знает функции выйгрыша другого агента, то говорить о равновесии Нэша - бессмысленно
игра в развёрнутой форме с неполной информацией задаётся аналогично игре в развёрнутой форме, за исключением того, что некоторые вершины, в которых делает ход один и тот же игрок, объявлены неотличимыми, ходы из них поставлены во взаимно-однозначное соответствие (входящее в правила игры), и игрок обязан приписывать соответствующим ходам в разных копиях вершины равные вероятности. при этом в неотличимых вершинах список предыдущих действий игрока должен быть один и тот же, то есть игрок помнит, попадал ли он уже в некоторый класс эквивалентности и какие ходы он делал
примерами игр с неполной информацией, которые лучше задавать в развёрнутой форме, являются карточные игры: расклад карт известен игроку не полностью, а множество всех стратегий необозримо, хотя в каждый конкретный момент количество разрешённых ходов не так велико
Фундаментальная Теорема теории игр гласит:
"каждая конечная игра с нулевой суммой и двумя игроками имеет оптимальную смешанную стратегию"
рассмотрим три игры: спрятанная монетка, камень-ножницы-бумага и игра полковника
один игрок прячет в ладони монетку в 10 или же в 20 копеек. другой пытается угадать достоинство спрятанной монеты. матрица игры имеет вид:
|banker choose|
| 10 20 |
-------+-------------+---------
ponter win | 10 20 | ponter ritht guess
ponter loss | -15 -15 | ponter wrong guess
выигрышная смешанная стратегия банкира - ???, выиграшная смешанная стратегия понтера - ???
код здесь
таблица выплат имеет вид (где 0.00 это баш-на-баш) :
ponter says '10'
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0|banker hides 10
-----------------------------------------------------------------------------|
20.0 16.5 13.0 9.5 6.0 2.5 -1.0 -4.5 -8.0 -11.5 -15.0| 0.0
16.5 13.6 10.7 7.8 4.9 2.0 -0.9 -3.8 -6.7 -9.6 -12.5| 0.1
13.0 10.7 8.4 6.1 3.8 1.5 -0.8 -3.1 -5.4 -7.7 -10.0| 0.2
9.5 7.8 6.1 4.4 2.7 1.0 -0.7 -2.4 -4.1 -5.8 -7.5| 0.3
6.0 4.9 3.8 2.7 1.6 0.5 -0.6 -1.7 -2.8 -3.9 -5.0| 0.4
2.5 2.0 1.5 1.0 0.5 0.0 -0.5 -1.0 -1.5 -2.0 -2.5| 0.5
-1.0 -0.9 -0.8 -0.7 -0.6 -0.5 -0.4 -0.3 -0.2 -0.1 0.0| 0.6
-4.5 -3.8 -3.1 -2.4 -1.7 -1.0 -0.3 0.4 1.1 1.8 2.5| 0.7
-8.0 -6.7 -5.4 -4.1 -2.8 -1.5 -0.2 1.1 2.4 3.7 5.0| 0.8
-11.5 -9.6 -7.7 -5.8 -3.9 -2.0 -0.1 1.8 3.7 5.6 7.5| 0.9
-15.0 -12.5 -10.0 -7.5 -5.0 -2.5 0.0 2.5 5.0 7.5 10.0| 1.0
матрица игры "камень-ножницы-бумага" - антисимметрична:
| к н б
--+-------------
к | 0 1 -1
н | -1 0 1
б | 1 -1 0
в этой игре оптимальной смешанной стратегией является случайный выбор предмета с равными вероятностями. такая стратегия непобедима, если противник тоже выбрал такую же стратегию. но если противник выбрал неоптимальную стратегию (например - всегда выбирать камень), то существует более выгодная стратегия (в данном случае - всегда выбирать ножницы)
проверим (надо бы сделать Монте-Карло ващета - TODO)
в игре полковника Блотто (ставим на каждое имеющееся поле n своих солдат - если наших солдат больше - мы выйграли поле. кто выйграл больше полей - тот выйграл игру) при трех полях и трех солдатах у каждого игрока если один выбирает стратегию (1,1,1), то выбор другого уже ничего не изменит и ему нет смысла выбирать что-то другое кроме как (1,1,1)
таблица игры, когда первый выбрал стратегию "занять все поля" :
1/3 1/0 1/0 проигрыш второго
1/2 1/1 1/0 ничья
1/2 1/0 1/1 ничья
1/1 1/2 1/0 ничья
1/0 1/2 1/1 ничья
1/1 1/0 1/2 ничья
1/0 1/1 1/2 ничья
а любая другая стратегия первого игрока может быть побита противником. поэтому первому тоже нет нужды отходить от этой стратегии
(1,1,1) - это и есть равновесие Нэша
код доказательства Монте-Карлой здесь
выдача этого кода (количество побед/поражений при случайном выборе игроками той или иной стратегии из 10К попыток) :
$ ./BlottoGame ( 2945, (1,1,1)) ( 1033, (1,2,0)) ( 1029, (2,1,0)) ( 1008, (0,1,2)) ( 997, (2,0,1)) ( 971, (1,0,2)) ( 907, (0,2,1)) (-2943, (0,0,3)) (-3011, (0,3,0)) (-3031, (3,0,0))
Хочется начать с работы, за которую спустя много лет Нэшу дали премию шведского банка по экономике. Это была его диссертация, и весь результат (с доказательством!) изложен на одной (sic!) страничке в PNAS (1950). Невозможно удержаться и не привести здесь эту работу целиком:
Что сделано на этой одной страничке? Две вещи, обе предельно незаурядные.
Во-первых, Нэш понял, что такое "игра" в математическом смысле слова, и что надо считать "решением игры" (оптимальной стратегией игроков).
И во-вторых, - обнаружил естественный класс игр, в которых "решение" всегда существует.
Что такое игра? Это несколько (два и больше) игроков, и у каждого есть возможность выбирать один из нескольких (два и больше) имеющихся вариантов ("действий", у каждого - свои), которые все игроки совершают одновременно и независимо. По результатам совокупных действий каждый из игроков получает некую сумму (возможно, отрицательную) условных денег.
Пример (КНБ, камень, ножницы, бумага - все знают). Два игрока одновременно выбрасывают одну из трёх комбинаций пальцев (кулак, два пальца, ладонь), и смотрят, чья комбинация "сильнее": камень тупит ножницы, ножницы режут бумагу, а бумага оборачивает камень. Если комбинации совпали, то никто никому ничего не платит, а если они разные, то игрок, выбросивший более слабую комбинацию, получает щелбан по лбу, который и отвешивает победитель.
Другой пример. У каждого игрока на руках несколько карт (неважно, из одной и той же колоды или у каждого своя). Игрок выбирает одну из карт и кладёт её на стол рубашкой вверх. Потом выложенные карты переворачивают, и из толстенного справочника каждый вычитывает, что ему причитается при данном раскладе.
Математически игра, скажем, двух участников задаётся таблицей: строчки соответствуют вариантам действий первого игрока, столбцы - вариантам действий второго, а в каждой клетке таблицы написаны два числа (возможно, отрицательных) - первое число - выигрыш первого игрока, если реализовалась данная комбинация, второе число - выигрыш второго.
Целью каждого игрока является максимизация собственного выигрыша: до остальных игроков никому нет дела. Более того, платёжная матрица может быть номинирована в своей валюте для каждого игрока (это подчёркивает интерес только к собственному выигрышу), соответственно, сумма чисел в каждой клетке может быть ненулевой. Если игроков больше чем два (скажем, три), то вместо двумерной таблицы надо задавать трёхмерный массив уже не пар, а троек чисел.
Что следует считать "разумной стратегией" для каждого игрока? Напомним, что никто не знает, какой ход сделают противники (в той же игре КНБ если игрок за долю секунды угадывает ход противника, он будет всегда выигрывать). Картёжники по этому поводу вздыхают, - "Ах, знал бы прикуп - жил бы в Сочи!". Неизвестно, знал ли Нэш это присловье, но фактически он предложил определить "решение игры" как такую стратегию выбора хода, при которой игрок не пожалел бы о своих действиях после того, как ход сделан и все карты раскрыты.
Def : выбор ходов (x[1], x[2], ..., x[n]), где x[i] есть допустимый ход. выбор игрока с номером i, называется равновесием по Нэшу, если ни один из игроков не может, зная ходы остальных, "переиграть" и выиграть больше, поменяв свой ход на какой-то другой допустимый ход.
Это определение логически несложно, но психологически нетривиально. Попробуйте поразмыслить над аналогичной, но более классически выглядящей проблемой. Предположим, наша игра имеет очень специальный вид: есть хорошая (дифференцируемая) функция f(x[1], x[2], ..., x[n]) от n переменных, предположим даже, что она вогнутая. Пускай каждый игрок "отвечает" только за "свою" переменную, которая является просто вещественным числом, а целевые функции всех игроков совпадают: каждый хочет максимизировать значение одной и той же функции f.
Что считать "оптимальной групповой стратегией" в такой, с позволения сказать, игре? Если у функции f есть максимум (единственный в силу предположения о вогнутости), то ясно, что именно эта точка и должна быть "решением" (равновесием). Но как это условие сформулировать в терминах действий игроков, каждый из которых "контролирует" только свою переменную? Оказывается, что "равновесие по Нэшу" и даст нам правильный ответ. Равновесная точка - это такая точка, в которой, манипулируя только своей переменной, ни один из игроков не может увеличить выигрыш. Иными словами, ограниченная на ось переменной с номером i, функция f должна достигать максимума по этой переменной в точке равновесия. Функция одной переменной достигает максимума там, где её производная обращается в нуль. Но эта производная есть ни что иное, как частная производная от f по x[i]. Поскольку все игроки равноправны, в точке равновесия все частные производные функции f должны обращаться в нуль, а это и значит, что равновесие обязано быть экстремумом (глобальным) целевой функции f, общей для всех игроков.
Ну хорошо, определение на первый взгляд выглядит разумным. Но тогда возникает очевидный вопрос, - а почему таким образом определённое равновесие существует вообще хоть когда-нибудь? Пример игры КНБ - случай, когда его "очевидным образом" нет: что бы ни выкинул второй игрок, у первого всегда могут быть основания "передумать" и "перебросить". И это лишь самый простейший случай!
И тут на помощь приходит понятие овыпукления игры, или её стохастического расширения. В изначальной формулировке у каждого игрока с номером i было своё конечное множество вариантов выбора C[i], и надо было всего лишь "оставаться в рамках правил", выбирая x[i]∈C[i] (т.н. "чистая стратегия"). А давайте теперь на конечном множестве C[i] "посадим" распределение вероятностей (набор неотрицательных чисел, в сумме дающих единицу), и "ходом" будем считать не выбор одной из точек, а "случайную комбинацию", определяемую этим распределением. Придумавший эту гениальную конструкцию фон Нейман назвал её "лотерея": вместо честного хода игрок кладёт на стол "лотерейный билет" с написанным на нём распределением вероятностей отдельных чистых исходов. Остаётся вопрос, - какой выигрыш получит такой лотерейный билет, но тут ответ очевиден: надо посчитать математическое ожидание выигрышей от чистых ходов с учётом вероятностей, написанных на билете.
С математической точки зрения произошло вот что: вместо конечного набора вариантов C=C[i], доступного i-му игроку, мы предоставляем ему возможность выбирать между распределениями вероятностей на этом множестве, т.е., с геометрической точки зрения - точку на стандартном симплексе p=(p[1],p[2], ...,p[m]), где m=m[i] - число вариантов в C[i] (вершин симплекса), зависящее от игрока, а сам симплекс - выпуклое множество в ℝm
Тем самым пространство игры (совокупность возможных ходов всех игроков) расширяется с конечного произведения (декартова) C[1]×C[2]×...×C[n] до декартова произведения соответствующих разномерных симплексов, которое тем не менее является выпуклым телом в (очень) многомерном пространстве. "Платёжные" функции в этой новой игре станут линейными на соответствующих симплексах, и поэтому (нестрого вогнутыми). Рассмотрим (как предлагает Нэш) для каждого "расширенного" (стохастического) хода и каждого игрока i множество ходов, куда он мог бы захотеть "переходить", узнав, какие стохастические ходы сделали противники, с тем, чтобы повысить свой стохастический выигрыш. Это было бы выпуклое подмножество "его" симплекса.
Таким образом, мы построили "многозначное" отображение выпуклого множества в себя, принимающее значения в пространстве выпуклых множеств. Стандартная топологическая теорема Какутани утверждает, что у такого отображения есть "неподвижная точка", лежащая в своём образе. А это и есть определение равновесия по Нэшу.
Суммируя сказанное, - "мальчишка" Нэш (ему был 21 год на момент написания статьи, - не факт, что ему продали бы пиво!) совершил концептуальный прорыв, который оценили полностью спустя 44 года, дав Нэшу нобелевку по экономике. Что характерно, - появившийся примерно тогда же реферат статьи Нэша в Math Reviews демонстрирует полнейшее непонимание происходившего современниками: "так, ещё один вариант теоремы Какутани о неподвижной точке".
есть две дороги из А в В - одна через пункт 1 и другая через пункт 2. цена за проезд из А в 1 постоянна и равна 10. такая же цена за проезд из 2 в В. цены за проезд из 1 в В и из А в 2 зависят от текущего количества машин, выбравших то или иное направление и расчитывается по формуле:
p(1B) = 20 ⋅ x / (x + y)
p(A2) = 20 ⋅ y / (x + y)
где x - число машин выбравших путь через 1, а у - число машин, выбравших путь через 2
открыли дорогу из 1 в 2 и установили плату (от -2 до +22). как размер платы за новую дорогу повлияет на распределение потока машин?
код на Хаскеле
листинг графического интерфейса на Тикле
наиболее важным достижением экономической теории является демонстрация того факта, что индивиды с чисто эгоистическими мотивами могут получать взаимную выгоду от обмена
если А выращивает крупный рогатый скот, а В — кукурузу, они могут увеличить свое благосостояние, обменивая скот на кукурузу. при помощи ценовой системы процесс может быть расширен до огромного количества разнообразных товаров и услуг
варианты выбора, с которыми сталкиваются А и В, не сводятся к вариантам «торговать» или «не торговать», как неявно предполагается в этом примере: А может предпочесть украсть кукурузу у В, вместо того чтобы отдать за нее свой скот; В может поступить аналогичным образом. в отличие от торговли, которая является игрой с положительной суммой, приносящей выгоду обоим участникам обмена, воровство в лучшем случае является игрой с нулевой суммой: ведь то, что выигрывает А, проигрывает В
если воровство (и борьба с ним) уменьшают способность А и В выращивать кукурузу и скот, то получаем игру с отрицательной суммой. в то время как при торговле каждый стремится улучшить свое положение и обе стороны оказываются в выигрыше, при воровстве эгоистичные устремления каждого приводят к тому, что оба проигрывают:
оба выигрывают, если воздерживаются от воровства, но каждый по-прежнему в выигрыше, если он один ворует. в этой матрице воровство является доминантной стратегией для обоих игроков, так как преобладает над всеми остальными опциями, обещая выбравшему ее более высокий выигрыш, чем другие стратегии - независимо от выбора другого игрока
в условиях анархии можно ожидать, что независимый выбор обоих индивидов приведет к принятию обоими доминантной стратегии — воровства. и такое распределение представляет «естественное распределение» благ, а именно - распределение, которое возникло бы при состоянии вещей, описанном Гоббсом. по сравнению с таким «естественным» состоянием оба индивида выиграют, если молчаливо или формально согласятся не воровать, при условии, что исполнение подобного соглашения связано с меньшими затратами, чем их общий выигрыш от его реализации. такое перемещение является перемещением по Парето, которое выводит людей из «гоббсианского» состояния. соглашение о таком перемещении является разновидностью «договора», устанавливающего права собственности и поведенческие ограничения каждого индивида. существование этих прав является необходимым условием для создания «договоров», которые образуют систему добровольного обмена
некооперативная стратегия является доминантной для обоих игроков - это наилучшая стратегия для каждого при однократной игре независимо от стратегического выбора другого. исход в правой нижней ячейке представляет равновесие Курно–Нэша. беда заключается в том, что это единственный результат игры «дилемма заключенных», который не является оптимальным по Парето - перемещение из любой другой ячейки ухудшит положение по меньшей мере одного игрока
несмотря на очевидное преимущество кооперативного исхода с отсутствием воровства над исходом с взаимным воровством, доминирование стратегии воровства приводит к тому, что стратегии с отсутствием воровства не составляют равновесной пары, по крайней мере при однократной игре. однако кооперативное решение может возникнуть как исход "суперигры" из многих игр «дилеммы заключенных», повторяемых многократно одними и теми же игроками
кооперативное решение может возникнуть даже в отсутствие непосредственной коммуникации между игроками, если каждый игрок выбирает стратегию суперигры, которая эффективно связывает его выбор кооперативной стратегии в одной игре с выбором этой стратегии другим игроком
например, одна из таких стратегий суперигры для игрока — это "зуб за зуб, око за око" - действовать по той же стратегии в текущей игре, по которой другой игрок действовал в прошлой игре. если оба игрока принимают такую стратегию и начинают игру с кооперативной стратегии, кооперативный исход возникает в каждой партии
другая альтернативная стратегия, приводящая к такому же результату, заключается в том, что каждый игрок выбирает кооперативную стратегию, пока так же поступает соперник, и каждый наказывает другого игрока за обман, выбирая некооперативную стратегию в серии игр, следующих за обманом, прежде чем вернуться к кооперативной стратегии. опять-таки, если игроки начинают с кооперативной стратегии, этот результат сохраняется в течение всей игры
в этих обоих типах кооперативной стратегии, которые являются равновесными решениями суперигры «дилеммы заключенных», равновесие устанавливается через "наказание" (или его угрозу) за некооперативное поведение игрока. эту идею о том, что некооперативное (антиобщественное, аморальное) поведение должно быть наказано, чтобы обеспечить соответствие обычаям (нормам) группы, можно встретить в большинстве этических систем
если количество игроков в «дилемме заключенных» невелико, то проще предсказывать, будут ли они отвечать на выбор кооперативной стратегии аналогичным выбором. проще выявить некооперативное поведение и выдать наказание, тем самым стимулируя дальнейшее принятие кооперативных стратегий. когда же количество игроков велико, одному или нескольким игрокам проще принять некооперативную стратегию и остаться либо незамеченными, поскольку влияние на остальных невелико, либо безнаказанными - вследствие трудности выявления нарушения или слишком больших затрат по наказанию нарушителей со стороны придерживающихся кооперативной стратегии игроков. т.о., добровольное следование нормам поведения более вероятны в небольших сообществах, чем в крупных
почти все эту мантру произносящие, забывают что в игру с заведомо отрицательной суммой очень даже можно выиграть (при определенных раскладах - гарантированно) - но твой профит будет меньше убытков контрагентов. пример - наемники, грабящие захваченный город, очевидно в выигрыше, равно как и пират берущий на абордаж галеон с серебром, равно как и рэкетир, обирающий комерсов. проблема в том на сколько "вдолгую" мы собираемся играть: мальчики, игравшие "вкороткую" или мёртвые или вернулись на свои заводы/колхозы/конторы
во-первых, гребеж - это игра с нулевой суммой только если не учитывать возможность получить тяжкие увечья не совместимые с жизнью (для грабителя ессно)
а во-вторых, смотрим на примере заключенных, чего уж там:
"...заключенные подбирали щепу на строительной площадке, делали вязаночки и несли в лагерь. Носить дрова в лагерь было запрещено, однако охрана ничего не предпринимала, пока колонна не приближалась к самому лагерю. Здесь заключенным приказывали бросить дрова: охранники тоже нуждались в дополнительном топливе, а носить дрова своими силами, вместе с автоматами, не могли. Заключенные бросали вязаночки, но не все. ... заключенным удавалось пронести в зону некоторую долю своей топливной добычи. Это устраивало обе стороны — и заключенных и охрану. Ведь если бы дрова при входе в лагерь отбирались подчистую, то заключенным не было бы смысла собирать их в рабочей зоне и нести с собой; они перестали бы это делать, и охрана осталась бы без дополнительного топлива. Тем не менее никакого открытого соглашения на этот счет не существовало. Соглашение было вполне негласным."
гарантированнй результат для охранника в единичной игре - отобрать ВСЕ. гарантированнй результат для заключенного в единичной игре - НИЧЕГО: нет никаких средств оставить себе хоть что-нибудь. но на завтра все повторится вновь - и охранники выбравшие стратегию "отбирать ВСЕ" на следующий день неизбежно оказываются в том же положении, что и заключенные - без топлива
норот вообще не понимает, что такое "игра с положительной суммой". вот в начале есть Куздра и есть Бокр - у обоих по сто рублей. в конце у Куздры пятьсот рублей, а Бокр должен двести. это игра с положительной суммой? ещё бы: в начале у игроков 100 + 100 = 200, а в конце 500 - 200 = 300. но Бокру от этого не легче. однако в начале игры Бокр выбирает стратегию _своего_поведения_ в игре. и если при выборе одной стратегии у него долг 200, а другой - 500, и никаких иных стретегий нет - то первая стратегия для него предпочтительнее
строго говоря здесь все про игру с нулевой суммой (ИНС). термин очень неудачный. игрой с ненулевой суммой (ИННС) называют игру в которой СУММА ВЫИГРЫША МЕНЯЕТСЯ от взаимодействия игроков
например часть ставок казино забирает себе. но это не является ИННС: казино - еще один игрок, который по правилами игры всегда выигрывает некоторый процент, но общая сумма выйгрышей/проигрышей при этом именно что нулевая - просто казино никогда не проигрывает
также и конкистадоры - взяли золота на миллион, пожгли на 10. 11 млн. были в игре с самого начала, и они их выиграли, но 10 из 11 сожгли (или проиграли - неважно). можно разложить этот проигрыш в любых пропорциях, важно что сумма не изменилась. предположим город договорился - 2 млн. отступных и никто ничего не жжет, но это значит 9 млн. городу, 2 млн. пиратам. было 11, стало 11. вот можно мартицу игры нарисовать. и - сюрприз - а два исхода в условии задачи отстуствуют. что будет, если пираты решат договариваться, а город - нет? и наоборот, если город решит договариваться, а пираты - нет?
выбор Пиратов
|договорится|воевать
------------|-----------|----------
договорится | Г:9 П:2 | Г:? П:?
выбор Города ------------|-----------|----------
воевать | Г:? П:? | Г:0 П:1
-----------------------------------
для игры с нулевой суммой во всех клеточках матрицы игры Г+П были бы равны одному и тому же числу. если дополнить эту матрицу исходя из жизненных реалий, можно уже говорить и о варинтах стратегий. скорей всего оба случая когда один договаривается, а второй - нет, будут чрезвычайно печальны для того, решил договориться
выбор Пиратов
|договорится| воевать
------------|-----------|----------
договорится | Г:9 П:2 | Г:0 П:1
выбор Города ------------|-----------|----------
воевать | Г:1 П:0 | Г:0 П:1
-----------------------------------
так что при единичной игре придется обоим сторонам выбирать сражение и получить результат (Г:0,П:1), хотя (Г:9,П:2) явно предпочтителен для обоих
(Г:9,П:2) - это равновесие Нэша эффективное по Парето. ни одна другая стратегия не дает возможность увелчить результат одного игрока без того, чтобы не уменьшился результат второго игрока
в повторяющейся игре (викинги каждую осень приходят в город отбирать урожай) - таки есть очень большой смысл обоим сторонам доверится друг другу. а залогом добросовестности договора становится будущая выгода
есть мнение, что именно так и образуются государства...
how bad is it if everyone acts selfishly, compared to if a central coordinator tries to minimize global cost?
we can define the price of anarchy
let f∗ be the global param that minimizes global cost, and f be the Nash equilibrium (the one with the greatest global param if it is not unique). the "price of anarchy" is defined as
Price of Anarchy = cost(f) / cost(f∗)
a more general notion of equilibrium: given a probability distribution σ on vectors of strategies s, we say that σ is a "coarse-correlated equilibrium" (CCE) if for all players i, and for all strategies s’i, we have
Es∼σ [ci(s)] ≤ Es∼σ[ci ⋅ ( s’i , <s_−i> )]
this is exactly the same definition as for mixed Nash, but here we don’t have the condition that σ is a product of distributions σi
any mixed Nash is therefore a coarse-correlated equilibrium, but not vice-versa
in linear program for CCE, two problems arise
the Game of Chicken is a two agent game with the following cost matrix:
| D C
-----+------------------
D | 10,10 0,1
C | 1,0 1,1
you can imagine the game as two teenagers racing cars towards each other, daring each other to swerve out of the way. the player who swerves faces humiliation (cost 1) but when both players don’t swerve, there is a big cost (a crash, cost 10)
the two strategies are Chicken (swerve) and Dare (don’t swerve)
the pure Nash equilibria are clearly (D,C),(C,D)
the mixed Nash equilibrium is when each player Dares with probability 1/10 and Chickens with probability 9/10. this gets the expected cost for the opponent paying Dare to be
1/10 ⋅ 10 + 9/10 ⋅ 0 = 1
the same as the payoff for Chicken, so doing the same mixed strategy for both players is a Nash equilibrium
however, there are other CCE equilibria
for example a CCE in this game is to randomize uniformly between the two PNE, implementable with a traffic light: both players in this scenario will follow what the traffic light tells them to do because the alternative is worse:
математическая экономика во многом основана на теории игр. а теория игр - такой странноватый матан про то, как искать максимум функции. в отличие от обычного матана, где функция одна и искатель тоже один, в теории игр искателей несколько, и у каждого - своя функция. если функции независимы друг от друга, то никакой новой задачи не появляется: каждый искатель-игрок перебирает возможные значения аргумента-стратегии и останавливается на том, который приносит максимальный выигрыш. в такой игре игрок может даже не подозревать о наличии других, и ничего в его поведении не изменится. но если выигрыш игрока зависит не только от того, какой ход сделает он, но и какие ходы сделают другие игроки, - всё сильно меняется
в наиболее общем варианте мы имеем набор из N игроков, у каждого из которых есть конечное множество из m_i ходов, i=1,...,N, так что в совокупности количество возможных исходов есть произведение
m_1 ⋅ m_2 ⋅ .. ⋅ m_N
это такая многомерная таблица и в каждой клетке таблицы написано, какой выигрыш ожидает каждого игрока, если реализовался именно этот вариант
никакой "справедливости" игры априорно нет: например, в детстве популярна была игра "Занзибар", при которой любой ход любого из двух игроков означал, что второй платит первому копейку. в "Занзибар", конечно, лучше не играть, но есть более справедливые игры, скажем, "камень-ножницы-бумага" (КНБ). у каждого игрока есть три варианта на выбор, и в зависимости от хода противника он выигрывает или проигрывает копейку. специфика этой игры - нулевая сумма: выигрыш одного в точности равен проигрышу другого, общее состояние игроков не меняется. "Занзибар", кстати, тоже с нулевой суммой, но КНБ в отличие от него не вызывает ощущения несправедливой игры. однако понять это можно только после определённых расчётов
все думают, что в игры играют, чтобы выиграть? ошибка
уж если вас усадили играть в "Занзибар" вторым игроком, ваш "выигрыш" всегда отрицательный. но зато есть "выигрышная стратегия": она тривиальная. как бы вы ни ходили, вы выиграете -1 копейку, и лучшего результата не сможет достичь даже гроссмейстер "Занзибара"
игра КНБ в этом смысле поинтереснее, хотя там выиграть тоже невозможно. почему? да потому, что "платёжная таблица" не зависит от того, какой игрок - первый, а какой - второй (они делают ходы одновременно), так что если может выиграть положительную сумму первый, то точно так же может её выграть и второй, а это невозможно, поскольку сумма нулевая
ну хорошо, невозможно выиграть, а в ноль-то выйти можно?
оказывается, это сильно непросто. какой бы из трёх ходов я не сделал, противник всегда может ответить ходом, при котором он выиграет, а я проиграю. единственное спасение - в одновременности: я сам не должен заранее знать, как я пойду, тогда и противник не узнает. и если у меня в кармане хороший генератор случайных чисел, - при любой стратегии противника я "останусь в нуле". такая вот загогулина: любая "сложная" стратегия, будучи разгадана, приведёт к гарантированному проигрышу
не самая очевидная теорема теории игр состоит в том, что в играх двух участников с нулевой суммой всегда есть оптимальная "случайная" (на жаргоне - "смешанная", в отличие от "чистых" стратегий выбора одного из вариантов) стратегия: надо случайным образом (но с определёнными вероятностями!) выбирать один из ходов. если так будут поступать оба игрока, каждый может себе гарантировать "в среднем" определённый выигрыш, улучшить который не получится никаким честным способом (сумма выигрышей, разумеется, будет нулевая). такая (относительная) простота игры двух игроков с нулевой суммой (совершенных антагонистов) связана с тем, что "платёжная таблица" - на самом деле не две, а всего одна функция с вещественными значениями, между которыми есть естественный порядок "чем больше, тем лучше"
в более сложных случаях могут быть ходы, одновременно выгодные всем игрокам (одним в большей степени, чем другим). вопрос в том, как "правильно играть" и что называть "решением игры", или равновесием (отдельный вопрос, как его искать). в одномерном случае решение игры - та стратегия (чистая или смешанная), которая доставляет наибольшее значение выигрыша каждому игроку. наивное ожидание, - это такой выбор клетки в таблице ходов, что ни один из участников не может улучшить своё положение, выбрав другую стратегию и не оглядываясь на других игроков
бытовой пример, - есть два магазина, в каждом из которых каждый из игроков покупает одну и ту же свою потребительскую корзину и, естественно, идёт в тот магазин, где цены ниже. магазин же устанавливает цены на каждый товар в зависимости от числа покупателей: скажем, владелец хочет заработать всего рубль на продаже всей картошки, поэтому он к оптовой цене добавляет столько, чтоб этот рубль "отбить". если есть всего один покупатель, с него запросят этот добавочный рубль целиком, а если покупателей будет 10, цена на картошку будет всего на 10 копеек выше оптовой. в этом месте есть возможность покупателям организоваться в кооператив и переходить из магазина в магазин всем вместе, но это уже будет другая игра: равновесие для отдельного покупателя - это выбор, обеспечивающий минимальную стоимость именно его корзины
"Дилемма заключённого" - пример игры, при которой такое равновесие есть, но оно не оптимально в смысле выигрыша. у каждого из двух игроков-обвиняемых по одному и тому же делу есть два хода: "сознаться" и "отрицать". если оба "сознаются" - получают по десятке (-10), если оба "отпираются" - по году (-1 за переход улицы на красный свет). если один "сознаётся", а другой "отпирается" - сознавшегося отпускают, как госсвидетеля, а отпирающемуся лепят двадцать. при такой прокурорской ставке вне зависимости от того, что делает один игрок, другому - прямой резон "сознаться": он либо вместо года тюрьмы получит свободу, либо вместо двадцати лет - десяточку. такое вот наказание за эгоистичное поведение и поощрение коллективизма
и наоборот, есть игры, в которых равновесия нет вовсе, и добавление смешанных ("случайных") стратегий не спасает дело
но это всё в пределах теории рационального выбора, когда каждый игрок оглядывается только на свою строчку в платёжной таблице. сплошь да рядом бывает совершенно не так
лауреат премии шведского банка Ауманн любит приводить в пример "парадокс шантажиста".
двум участникам предлагается поделить между собой 100 долларов как им угодно, но чтоб на делёж согласились оба. если же согласия достичь не удалось, то ни один не получает ни цента
"справедливый вариант" поделить пополам, конечно, первое, что приходит в голову. а что, если один из игроков шантажист, и предлагает: мне 90, тебе 10? должен ли "правильный" честный игрок на такое соглашаться? с точки зрения собственной выгоды - несомненно, ибо всяко 10 лучше, чем ноль. с другой стороны, эксперименты на людях показывают, что большинство в такой ситуации предпочитает "хлопнуть дверью"
что не так в консерватории, почему "оптимальное" решение не нравится? тут несколько ответов
во-первых, бОльшая часть "абстрактных игр" (платёжных таблиц) не имеет никакого смысла (да, гнать математиков в шею!). осмысленная теория возникает только там, где платёжные функции имеют какую-то дополнительную структуру. например, очень красива и хорошо развита теория кооперативных игр
во-вторых (некое философское уже наблюдение) в парадоксе Ауманна явно присутствует "халява", т.е., игроки изначально не обладают никакими начальными условиями (например, ситуация могла бы измениться, если б один из игроков был миллионер, а второй - нищий)
наконец, в этом парадоксе "некорректно" определена функция полезности (выигрыш). помимо собственно суммы, которая может играть разную роль, в функцию полезности надо ввести что-то типа "чувства собственного достоинства" каждого игрока. его, конечно, долларом не померишь, но если тебе эта сотня, в общем, не слишком нужна, а обосранным чувствовать себя не хочется, то как-то надо это учитывать. кстати, к другому игроку это тоже относится: чтоб заниматься таким шантажом, надо иметь не только желание получить побольше денег, но и "гнусные наклонности", за удовлетворение которых не жалко заплатить отказом от части суммы
я всё-таки предположил бы, что у нас Байесовская игра :)
я для простоты только детерминированные игры обсуждаю. наворотить сверху можно что угодно, хоть вероятность, хоть динамику
в КНБ выиграть элементарно! если соперник проиграет - смайл. т.е. вы играете стохастически, но потеете, пейсы крутите, материтесь. а он против вас суперстратегию сочиняет
вот если приходится оптимизировать в реальном времени т.е. с ограниченными возможностями по памяти и ограничениях на время работы алгоритма оптимизации. значит оптимизационная задача должна включать и одновременно оптимизацию выбора решения задачи по сложности алгоритма решения как один из параметров оптимизации. какой-то такой селф-референс, такие примеры где рассматриваются?
готов съесть свою ермолку, если на этот счёт есть хоть какая-нибудь осмысленная "общая теория". есть конкретная задача, - сколько-то адекватная модель, плюс в реальном времени поступают результаты каких-то измерений, позволяющие уточнить состояние системы и/или какие-то параметры, - что с ними делать? единственная общая философия - "метод малого параметра". каждое следующее число input'a - малая поправка к тому, что мы знали до этого, соответственно, можно попытаться найти малую поправку к решению, чтобы немного улучшить критерий. если укладываетесь в реальное время и ограничения - повезло, нет - придётся упрощать модель, ничего не поделаешь
с шантажистом не столько "сидеть обосранным", сколько "Этому пидарасу - ни копейки! А то он и в следующий раз на голову сядет!". добавление (неявной) стратегической цели - не только оптимально выиграть этот конкретный ход, но и обеспечить изменение цф на будущее
фон Нойман был убежден, и с точки зрения теории он прав, что в игре двух ядерных сверхдержав выиграшная стратегия - ё...ть первым. это приведет к решению игры в точке равновесия Нэша. выгода небольшая (кое-кто и кое-что из твоих/твоего остнется существовать), но зато никакая контрстратегия партнера твое состояние не ухудшит. и писал отчаянные письма президенту. однако зажравшееся человечество уже 70 лет торчит в состоянии неустойчивой эффективности Парето, которое, строго говоря, решением игры не является
брульянты Киса с Осей в 12 стульях - по какой именно стратегии искали )? небось, неоптимальная была без математики-то?!
стохастически оптимально, т.е. выбирали вариант с максимальной вероятностью c гипотезой о равновероятном наличии брюлей в стульях
так надо было Кису-то - в Москве оставить )!
у Кисы надо было деньги отнять!
нет. там была огромная поправка на возможность эти стулья добыть. поменять на ситечко - запросто; присвоить путем женитьбы - можно; спереть, потратив заметное время и силы на путешествие за театром - реально; а единственный стул, уехавший в грузовой двор вокзала, как добывать - непонятно, цена процесса == бесконечность, ну и ну его нафиг значит
>> "стул, уехавший в грузовой двор вокзала, как добывать - непонятно"
вы смеетесь? "На такие шансы ловить можно. Играю девять против одного." но допустим один стул против другого. такой стала ситуация когда осталось два стула после всех неудач. для наглядности перетолкуем задачку: вы входите в здание в поисках туалета и успеваете спросить выбегающего: где здесь туалет? "В конце коридора" - полученный ответ. но концов два, и один - ближе. стохастически оптимально в смысле длины времени поиска пойти в близкий, а в случае ошибки - в дальний
путь в ошибочном : удачном случае
(2 ⋅ s + l) : s при другом выборе
(2 ⋅ l + s) : l
именно! даже если вероятности одинаковы, то цена вариантов может быть сильно разная. стрелять надо, разумеется, в дешевую сторону, и только потом заниматься дорогими
на самом деле рядом лежит довольно много небезынтересных сюжетов. например, много-критериальная оптимизация имени чл.коррa РАН Б.А.Березовского: есть не одна функция, которую хочется максимизировать, а как минимум две. скажем, выбирая невесту, хочется, чтоб и красивая, и обеспеченная была. а кому-то ещё и дети от прошлых браков мешают. легко сравнить две кандидатуры, одна из которых по всем показателям лучше другой. а что делать, когда приходится делать нетривиальный выбор?
ну, в случае невесты можно прикинуть по рыночной стоимости: сколько вам будет стоить разовая акция с моделью сопоставимых статей, на сколько лет в рассрочку вы подписываетесь, сколько будет стоить вырастить головастиков. но всё же не всегда деньги - мерило всего
или другая сфера: как организовать турнир по игре в "Занзибар"? олимпийская система "на вылет" имеет одни недостатки, круговая "каждый с каждым" - другие, смешанные должны как-то решать, кого с кем алгоритм сводит. то, что хорошо для футболистов, наверняка не понравится шахматистам, а почему? всё это - математика без всяких интегралов и даже почти без арифметических операций (ну, кроме сложения). а интересно же!
для начала можно обойтись парето-оптимальными вариантами
их слишком много, чтобы каждый из них считать оптимальным решением
обычно делаются какие-то предположения о структуре предпочтений игрока, которые среди прочих аксиом должны быть парето-монотонными (иначе странности пойдут, хотя сказка про горшок каши - урок модельерам)
конечно, их много, но они корректны. разве в много-критериальности есть место единственности? а уже на парето-оптимальных можно как-то решать. обычно это иерархии или свертки, так или иначе переход к единому критерию, но всегда ущербный. размытые критерии и fuzzy logic вероятно лучшая из техник. там еще вопрос скорости ...
любая модель, которая в качестве решения даёт НЕ парето-оптимальные варианты, должна вызвать поднятие бровей и объяснение, почему и как предмет с очевидной положительной полезностью (каша) становится нежелательной обузой, когда этой кашей заливает нижние этажи зданий. все теории много-критериальной оптимизации (не то, чтобы их много было, и они изрядно спекулятивны) направлены именно на то, чтобы парето-оптимальные варианты можно было по каким-то критериям упорядочить с тем, чтобы сузить множество оптимумов. один из путей - отбрасывать варианты, очень сильно несбалансированные (а где взять пороговые значения, Зин?). скажем, если я плавлю сталь, то нахрен мне затариваться углём (и хранить его за свой счёт на своих складах), когда узкое место у меня - руда
"все теории ... и спекулятивность" - это банальность, известная любому практику. а вот по поводу fuzzy - вы спешите, как мне кажется. есть примеры настолько удачные в т.ч. в задачах управления, что скорее забыть стоит принцип максимума (неработающий, сугубо теоретический отстой). мне он обошелся в месяц трудов не в самое лучшее время - перед защитой диплома. я тогда выкрутился (и в итоге - написал статью), но крови он мне попортил. [апропо: на защите диплома на мой неуспех с принципом махimum Ю.С.Осипов злорадно воскликнул: "- Я так и знал, не дает сходимости!"]
и еще по поводу парето-оптимальных: для ЛП метод эллипсоидов Шора-Хачияна-Кармаркара, с полиномиальной сложностью, игнорирует поиск по вершинам многогранника (необх.усл.). так что послать парето-оптимальные не так уж абсурдно, если умеючи! не встречал, правда, чтобы кто-то умел
давайте рассмотри простейший вариант покера - однокарточный покер один-на-один. игрок A ставит и игрок B должен или ответить или сбросить. какая стратегия будет выйгрышной для A?
поднимать ставку на Туза - очевидное решение. то же - для Короля или Дамы. а как насчет Двойки? если B имеет Тройку, что лучше для A - поставить, поднять или сбросить? стоит ли А блефовать? и если да, то как часто? если он зачастит c блефом, то В начнет ему отвечать даже с Шестеркой. Фундаметальная Теорема теории игр говорит о том, что наилучшая стратегия есть - но как ее найти!
вообще говоря, оптимальная смешнанная стратегия - это набор ходов с определенной частотой выбора для каждого хода и это замечательно, что такой гений как фон Нейман сумел доказать существование такой стратегии - несмотря даже на то, что он не сумел указать, как такую стратегию найти
аукцион - это способ продажи товара, ценность которого просто неизвестна - она разная для разных покупателей и она неизвестна продавцу, но продавец пытается продать товар как можно дороже, а покупатели никогда не заплатят больше их оценочной стоимости
задача теории - обьяснить, как будут себя вести игроки в зависимости от правил игры
два открытых формата - "английский" и "голландский" и два закрытых формата - "аукцион первой цены" и "аукцион второй цены"
если предпочтения игроков закрытого аукциона распределены одинаково, то говорят о "симметричном аукционе"
два (и только два) участника оспаривают обладание какой-либо ценностью делая на нее ставки value1 и value2 (не обязательно - одинаковые), причем игроки не знают размер ставок противника. в самом начале аукционист заряжает шестизарядный револьвер одним патроном и прокручивает барабан. после этого право первого голоса определяется жребием и последовательно происходит до шести раундов торговли с вероятносями завершения на текущем раунде соответственно 1/6 1/5 1/4 1/3 1/2 1 - с попеременным правом голоса на каждом этапе у одного из участников. участник, имеющий на данном этапе слово, может сказать "Пас", выйдти из торговли с потерей права на оспариваемую ценность, но с сохранением своей ставки и в этом случае ценность достается второму участнику, а ставка второго участника достается аукционисту. если же первый участник решает продолжить торговлю, то он говорит "Продолжаю" и аукционист производит попытку выстрела ("в потолок" - мы же в конце концов гумманисты) из револьвера - при произошедшем выстреле ценностью овладевает противник, а аукционисту достается и ставка проигравшего и ставка выйгравшего, при неудачной попытке выстрелить - начинается следующий раунд с правом голоса уже у другого участника аукциона
ситуация непростая: ценность выйгрыша для вас может не совпадать с ценностью выйгрыша для соперника - это раз. второе - с каждым раундом увеличивается вероятность проигрыша - и вся заковырка в том, что соперники чередуются - и вам страшно отвечать сейчас, но ему еще страшнее отвечать потом, однако если вы "застрелитесь" сейчас, то он будет свободен от трудного выбора!
итак, запилим Монте-Карлу!
результаты при 13 эмуляциях со ставками 10.03 и 20.02 :
$ runhaskell russrullete.hs 13 10.03 20.02 step 6: 2nd killed step 5: 1st killed step 3: 1st killed step 4: 2nd killed step 2: 2nd killed step 4: 2nd killed step 5: 1st killed step 5: 1st killed step 4: 2nd killed step 2: 2nd killed step 1: 1st killed step 3: 1st killed step 5: 1st killed
дана несимметричная монета, вероятность выпадения орла 60%, решки 40%. есть игрок и бюджет. игрок делает ставку вида {ставка, результат}, где результат орёл|решка, а ставка - часть бюджета. если по результатам подбрасывания монеты игрок выигрывает, то забирает себе две ставки (своя + чужая), если проигрывает, то теряет свою ставку. если бюджет кончился, то игрок проиграл. оптимальная стратегия - это такая, которая позволяет довести бюджет до произвольной величины, например увеличить его в 10 раз. довольно небольшое количество людей могут построить оптимальную стратегию игры в орлянку при таких вводных
> я очень сомневаюсь, что образованные люди не слышали про фон Неймана, отбеливание или, в крайнем случае, не могут самостоятельно нарисовать табличку два-на-два
как помогут табличка 2x2 и фон Нейман?
> ваша задача - это фон-Неймановский алгоритм отбеливания случайного потока битов: "берём два последовательных бита, если они одинаковые, выбрасываем, если разные - используем второй из них". и даже если не знать алгоритм, то можно нарисовать табличку с вероятностями после двух подбрасываний и найти в ней две ячейки с одинаковыми вероятностями. или нет? и я думаю что в поставленной формулировке задача строго говоря не решается - всегда есть ненулевой шанс проиграть. выбором стратегии его можно уменьшить, но нельзя сделать нулевым. тем не менее, легко придумать стратегию, которая позволяет выиграть ПОЧТИ всегда. например, каждый раз ставить четверть оставшегося бюджета на орла
>> думаю что в поставленной формулировке задача строго говоря не решается
решается. при выписанных условиях игрок должен ставить на орла 20% имеющегося бюджета. проиграть (лишиться начального бюджета) при такой стратегии невозможно, а выигрыш гарантирован большим количеством игр
> есть разница между "невозможно" и "маловероятно". если начальный бюджет b и по закону подлости решка выпадает n раз подряд, то после этого бюджет станет b·0.8^n, что может быть меньше одной копейки, которую придётся поставить и тоже проиграть. ничего особенного в цифре 20% нет, можно ставить 25% или 5%. меняется только среднее время игры и вероятность проиграть (которую можно сделать сколь угодно малой, но по прежнему ненулевой). тут геометрическое броуновское движение без сноса, то есть логарифм бюджета хорошо приближается нормальным распределёнием и снизу ничем не ограничен
>> ничего особенного в цифре 20% нет
есть. в частности, меняется матожидание времени игры для достижения заданного уровня, и если ставить как указано, то это время минимально. с одного рубля проиграться до копейки решка должна выпасть 20 раз подряд. потом - ниоткуда не следует что нельзя делать ставки меньше копейки
> не совсем понятно, почему я должен именно "максимизировать матожидание логарифма бюджета", а не, скажем, "минимизировать матожидание корня пятнадцатой степени из времени удесятерения начального бюджета". одного слова "орлянка" недостаточно для того, чтобы математически строго поставить задачу и определить критерий успеха, включающий в себя, да, и такие нюансы как "можно ли ставить меньше копейки". в условии ничего не было сказано про время, а было сказано, что "оптимальная стратегия это такая которая позволяет гарантированно выиграть". если можно делать ставки меньше копейки, то любая стратегия, при которой не ставится весь бюджет за раз, в этом плане оптимальна
согласен, да. оптимальность надо было по другому определить - увеличить бюджет в 10 раз за конечное и заранее оговоренное число шагов