Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
В играх, не имеющих седловой точки, нижняя цена игры a всегда меньше верхней b.
|
|
Установленный факт означает, что если игра одноходовая, то есть партнеры играют один раз, выбирая по одной чистой стратегии, то в расчете на разумно играющего противника они должны придерживаться принципа минимакса, это гарантирует выигрыш V ³ a игроку А и проигрыш V £ b игроку В. Следовательно, при применении минимаксных стратегий величина платежа V ограничена неравенством
a < V < b.
Если же игра повторяется неоднократно, то постоянное применение минимаксных стратегий становится неразумным. Например, если игрок В будет уверен в том, что на следующем ходу А применит прежнюю стратегию, то он несомненно выберет стратегию, отвечающую наименьшему элементу в этой строке, а не прежнюю.
Таким образом, мы приходим к выводу, что при неоднократном повторении игры обоим игрокам следует менять свои стратегии. Тогда возникает вопрос: каким образом их менять, чтобы в среднем выигрыш одного и проигрыш другого был аналогично одноходовой игре ограниченным снизу и сверху соответственно?
Интуитивно понятно, что такое чередование чистых стратегий должно быть случайным. Такое чередование чистых стратегий называется решением в смешанных стратегиях.
Смешанная стратегия состоит в том, что в ходе игры происходит случайный выбор стратегии из некоторого множества (набора) стратегий и для каждой из них вводится вероятность ее выбора.
Таким образом, смешанной стратегией SA игрока А называется применение чистых стратегий Al, А2,..., Ат с вероятностями p1, p2 ..., pm, причем сумма вероятностей равна 1, т.е.
Смешанные стратегии игрока А записываются в виде строки РA = (p1, p2,.., pт).
Аналогично смешанные стратегии игрока В обозначаются: QB = (q1, q2, …, qn).
Сумма вероятностей появления стратегий также равна 1, т.е.
Чистые стратегии можно считать частным случаем смешанных, и задавать строкой, в которой индекс i соответствует чистой стратегии.
Платежная матрица игры без седловой точки принимает вид, показанный в таблице 3.
Таблица 3 – Общий вид платежной матрицы игры без седловой точки
| Стратегии игрока А | Вероятность выбора стратегии | Стратегии игрока В | ||||
| S1 | S2 | S3 | … | Sn | ||
| q1 | q2 | q3 | … | qn | ||
| R1 | p1 | a11 | a12 | a13 | a1n | |
| R2 | p1 | a21 | a22 | a23 | a2n | |
| R3 | p1 | a31 | a32 | a33 | a3n | |
| … | … | … | … | … | … | … |
| Rm | pm | am1 | am2 | am3 | amn |
Игрок А выбирает стратегию Ri так, чтобы максимизировать наименьший ожидаемый максимум по столбцам платежной матрицы, а игрок В выбирает стратегию Sj с целью минимизировать наибольший ожидаемый проигрыш по строкам. Такой выбор стратегий отвечает принципу минимакса.
Математически критерий минимакса при смешанных стратегиях записывается следующим образом:
Игрок А выбирает стратегию Ri, дающую
(2)
Игрок В выбирает стратегию Sj, дающую
(3)
По существу игрок А стремится выбрать ту смешанную стратегию, которая обеспечивает максимум математического ожидания выигрыша, а игрок В – ту стратегию, которая обращает в минимум математическое ожидание проигрыша.
Если стратегии оптимальны Ri* и Sj*, то выполняется строгое равенство между максиминным ожидаемым выигрышем и минимаксным ожидаемым проигрышем, а результирующее значение равно оптимальному (ожидаемому) значению игры.
Этот вывод следует из теоремы фон Неймана и минимаксе. Основная теорема теории игр (доказана фон Нейманом в 1928году) утверждает:
каждая матричная игра с нулевой суммой имеет, по крайней мере, одно решение, возможно, в области смешанных стратегий, то есть существуют стратегии R* и S*, оптимальные для обоих игроков, причем max min M(R; S) = min max M(R; S) и равен M(R*; S*).
Примечание. Нулевая сумма означает, что выигрыш одного игрока равен проигрышу другого.
Данная теорема утверждает, что выражения (1) и (2) при оптимальных стратегиях получают одно и тоже значение (число) V = M(R*; S*), называемое ценой игры.
Если Ri* и Sj* - оптимальные решения для обоих игроков, то каждому элементу платежной матрицы aij соответствует вероятность, вычисляемая, как
pi* x qj*.
Следовательно, оптимальное ожидаемое значение игры
.
Из основной теоремы следует, что каждая конечная игра имеет цену и она лежит между нижней и верхней ценами игры
a ≤ V ≤ b.
Если один из игроков придерживается своей оптимальной стратегии, то выигрыш (проигрыш) его остается неизменным независимо от тактики другого игрока, если, конечно, последний не выходит за пределы своих «полезных» стратегий, иначе выигрыш (проигрыш) возрастает.
Пусть R А* = (p1, p2,..., Pт) И SВ* = (q1, q2,..., qn) - пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной.
Доказана теорема об активных стратегиях: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры V, если при этом второй игрок не выходит за пределы своих активных стратегий, иначе выигрыш (проигрыш) возрастает.
Эта теорема имеет большое практическое значение - она дает конкретные модели вычисления оптимальных стратегий при отсутствии седловой точки.
Решить конечную игру в смешанных стратегиях - получить векторы Р* = (p1, p2,..., Pт) и Q*= (q1, q2,..., qn) (получить оптимальные стратегии), удовлетворяющие теореме о минимаксе, и вычислить величину ожидаемого платежа M(R*; S*).,
Известно несколько методов решения задач без седловой точки, но наиболее употребительными из них являются:
- аналитический метод;
- графический метод;
- метод сведения к задаче линейного программирования.
Наиболее простое решение имеют игры с размерностью платежной матрицы 2 х 2.
|
|