Определение

Пример 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).

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

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

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