Кооперативные стохастические игры

Кооперативные стохастические игры— разделтеории игр, изучающий конфликтно-управляемые системы с недетерминированными переходами из состояния в состояние, в которых возможна кооперация игроков.Стохастические игры— динамические игры, в которых переход из одного состояния (одновременной игры) в другое происходит с некоторой вероятностью, зависящей от стратегий, выбранных игроками в данном состоянии. Под выигрышами игроков в стохастических играх принято понимать математическое ожидание их выигрышей. Впервые стохастические игры были рассмотреныЛ. Шеплив 1953 году. Он изучалантагонистическиестохастические игры двух лиц и доказал существованиеситуации равновесияв стационарных стратегиях в таком классе игр.

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

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

Марковский процесс принятия решений

Марковский процесс принятия решений(англ.Markov decision process (MDP)) — спецификация задачипоследовательного принятия решенийдля полностью наблюдаемой среды с марковской моделью перехода и дополнительными вознаграждениями. Назван в честьАндрея Маркова, служит математической основой для того, чтобы смоделировать принятие решения в ситуациях, где результаты частично случайны и частично под контролем лица, принимающего решения. Сегодня эта спецификация используются во множестве областей, включая робототехнику, автоматизированное управление, экономику и производство.

Определение

Пример MDP с 3 состояниями и 2 действиями

Чтобы определить марковский процесс принятия решений нужно задать 4-кортеж, где

• конечное число состояний,

• конечное число действий (часто представляется в виде,конечное число действий доступных из состояния),

• вероятность, что действиев состоянииво времяперейдет в состояниеко времени,

• вознаграждение получаемое после перехода в состояниеиз состонияс вероятностью перехода.

Линейная частичная информация в теории игр

Общее описание

Теория линейной частичной информации(англ. Linear Partial Information — LPI), применяемая для принятия решений на основаниинечёткой логики(англ. fuzzy logic) при неполной или неаккуратной доступной информации. ШвейцарскийматематикЭдуард Кофлеризобрёл эту теорию в 1970 году.

Определение

Любая стохастическая частичная информация SPI(p)которую можно считать решением системы линейныхнеравенств, называется линейной частичной информациейLPI(p)описывающейапостериорную вероятностьp. Эту информацию считаем нечёткостью линейной частичной информации об апостериорной вероятностиp, соответствующей представлению линейной нечёткой логики.

Дилемма заключённого

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

Диле́мма заключённого(англ.Prisoner's dilemma, реже употребляется название «дилемма банди́та») — фундаментальная проблема втеории игр, согласно которойигрокине всегда будут сотрудничать друг с другом, даже если это в их интересах. Предполагается, что игрок («заключённый») максимизирует свой собственный выигрыш, не заботясь о выгоде других.

Суть проблемы была сформулирована Мерилом Фладом (Merrill Flood) и Мелвином Дрешером (Melvin Dresher) в 1950 году. Название дилемме дал математик Альберт Такер (Albert W. Tucker).

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

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

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