Библиографическое описание:

Ибрагимов А. А. Обобщенная марковская игра «Большой матч» // Молодой ученый. — 2016. — №13. — С. 22-26.



Марковская игра «Большой матч» изучена в обобщенной форме.

  1. Обобщенный большой матч. Марковская игра «Большой матч», как представитель марковской игры с конечным множеством состояний и конечными множествами решений игроков и критерием предельного среднего выигрыша первого игрока, изучена в работах [1–7]. Представляет интерес, так называемая, обобщенная марковская игра «Большой матч» или «обобщенный большой матч» (сокращенно ОБМ), задаваемой тремя игр-компонентами:

(1)

где матрица Гi (i = 1, 2, 3) представляет собой i-е состояние игры ОБМ; a, b. с  числа. В случае a = с = 1, b = 0 имеет место игра «Большой матч»

Процесс разыгрывания игры ОБМ состоит в следующем. На первом шаге в состоянии Г1 игроки I и II независимо друг от друга выбирают строку i и столбца j соответственно. В результате складывается ситуация (i, j). После чего согласно элементу γij формальной матрицы Г1 определяется выигрыш игрока I и следующее состояние игры. Так, например, при ситуации (1, 1) γ11 = a + Г1 и игрок II платит игроку I aединицу и следующим состоянием игры будет снова Г1. Состояния Г2 и Г3 являются поглощающими, ибо, попадая в одно из них, игра останется в нем навсегда. На каждом шаге игры игроки оглашают свои решения с помощью монеты. Показ герба (Г) означает, что игрок I (II) выбрал первую строку (первый столбец), а показ решетки (Р)— вторую строку (второй столбец).

Введем обозначения: ξnn) — решающая функция, представляющая собой вероятность выбора решения «герб» игроком I (II) на n-мшаге игры; π = (ξ1, ξ2, …, ξn, …) — стратегия игрока I; φ = (η1, η2, …, ηn, …) — стратегия игрока II; ξ = (ξ, ξ, …, ξ, …), η = (η, η, …, η, …) — стационарные стратегии игроков I и II, соответственно; — средний суммарный выигрыш игрока I за n шагов при стратегиях игроков π и φ и начальном состоянии Г1; — средний выигрыш игрока I за один шаг в nшаговом игре при π и φ и начальном состоянии Г1. Стратегии игроков π* и φ* оптимальны, если справедливо двойное неравенство для всех n≥ 1 и произвольных π и φ.

  1. Целевая функция игры ОБМ вклассе стационарных стратегий. Представим в явном виде целевую функцию . Согласно игр-компонентам (1) игра ОБМ, как марковская игра, характеризуется следующими данными

Состояние

Ситуация

Вероятность перехода

Выигрыш

i

(k, r)

1

(1, 1)

(1, 2)

(2, 1)

(2, 2)

1

0

1

1

0

1

0

0

0

0

0

1

a

0

0

0

2

(1, 1)

0

1

0

b

3

(1, 1)

0

0

1

c

Пусть игра ОБМ находится в состоянии 1. Иначе говоря, пусть разыгрывается игровая компонента Γ1. При стратегиях игроков (ξ, 1 ξ) и (η, 1 η) вероятность остаться в игровой компоненте Γ1 равна ξη + (1ξ)η = η. Вероятности перехода из Γ1 в Γ2 и Γ3 соответственно равны ξ(1η) и (1ξ)(1η). Следовательно, матрица P(ξ, η) имеет вид

Отсюда получим матрицу вероятностей перехода за n шагов и вектор ожидаемых выигрышей игрока I:

Отсюда следует, что

= σn [ξηa + ξ(1 — η)b + (1 — ξ)(1 — η)c] + ξ(1 — σn)b + (1 — ξ)(1 — σn)c,

где σn= (1 + η + η2 + … + ηn 1) / n.

Условимся обозначать через σ величину σn. Тогда, целевая функция игры ОБМ с бесконечным числом шагов в классе стационарных стратегий имеет вид

= σ [ξηa + ξ(1 — η)b + (1 — ξ)(1 — η)c] + ξ(1 — σ)b + (1 — ξ)(1 — σ)c. (2)

  1. Метод последовательных приближений. Оптимальные стратегии игроков π* и φ* и значение игры ОБМ с конечным числом шагов n могут быть определены с помощью модифицированного функционального уравнения преобразования цен(см. [4, 5]), которое для игр-компонент (1) принимает вид:

(3)

где i = 1, 2, 3; n≥ 1.

Из 2-го и 3-го уравнения получаем Подставив эти значения в 1-ое уравнение системы (3), имеем

(4)

Решая эту 22-игру (см. [8, c. 45]), находим значение игры ОБМ и оптимальные стратегии игроков для конечного n.

Рекуррентные соотношения (3) могут быть использованы для решения ОБМ с бесконечным числом шагов. Именно, при n (4) дает значения игры , а ε-оптимальные стационарные стратегии игроков достигаются за конечное число шагов n.

Между тем, специфическая особенность игры ОБМ позволяет решить данную задачу более простим путем. Так, положив в (4) ε = 1/n и записав вместо величины искомое ее предельное значение получим уравнение относительно

(5)

Решая эту 22-игру, находим значение игры ОБМ и ε-оптимальные стационарные стратегии игроков:

(6)

(7)

(8)

Заметим, что если в (2) подставить и , то получится

Следует отметить, что при a = с = 1, b = 0 получим результаты, соответствующие игру «Большой матч» (см. [47]):

  1. Метод аппроксимации ОБМ игрой спереоценкой. Для изучения и решения ОБМ с бесконечным числом шагов наиболее подходящим методом является аппроксимация ОБМ соответствующей игрой с переоценкой. В этом случае функция выигрыша имеет вид , где  [0, 1) коэффициент переоценки.

Исходя из результатов, изложенных в [9] для данных игр-компонент (1) имеют место следущие рекуррентные соотношения

(9)

где i = 1, 2, 3; n≥ 1.

Рекуррентные соотношения (9) позволяют решить игру ОБМ с переоценкой. Именно, при n (9) дает значения игры и -оптимальные стационарные стратегии игроков . Здесь, записав вместо величин искомые их предельные значения имеем

(10)

Из 2-го и 3-го уравнения получаем . Подставив эти значения в 1-ое уравнение системы (10), имеем

Здесь, если положить ε = 1 , то данное уравнение принимает вид

которое ничем не отличается от уравнения (4).

Эти факты показывают насколько тесно связаны рекуррентные соотношения (3) и (9).

  1. ОБМ принятия решений вусловиях риска. Вслучае, когда a и b больше с игра ОБМ имеет тривиальное решение. В этом случае, в игровой компоненте Γ1 1-я строка доминирует 2-ую строку и игрок I с вероятностью 1 принимает решение Г (ξ = 1). Тогда игрок II выбирает решение Г (η = 1) и цена игры , если ab;  решение Р (η = 0) и цена игры , если a>b. Так же тривиально решается случай, когда a и b меньше с.

Заслуживает внимание случай, когда одно из чисел а и b больше с, а другое меньше с. Пусть ac, а b<c. В этом случае решение Г игрока II связано с определенным риском. Здесь, игрок II может принимать решение Р и игра переходит во 2-ое состояние и игрок II платит игроку I b единиц (если b отрицательно, то игрок I платит игроку II b единиц) на каждом шаге игры.

Характерной особенностью игры ОБМ является то, что только при решении Р игрока II игра может покинуть состояние Γ1. При разыгрывании игры ОБМ этим обстоятельством игрок II может воспользоваться разумным образом. Играв достаточно длительное время «герб» игрок II сначала изучает поведение игрока I, т. е. следит за статистикой Wn = m/n, где m число «гербов» принимаемых игроком I за n шагов игры. Если Wn > (6), то игрок II наверняка будет выбрать «решетку» и выигрыш игрока будет меньше, чем цена игры (5). Если Wn, то решение «герб» остается неизменным на последующих шагах игры и выигрыш игрока II не больше, чем цена игры . Такая адаптивная стратегия игрока II вполне приемлема при разыгрывании игры ОБМ. При этом игроку II целесообразно воспользоваться методом принятия решений в условиях риска, изложенным в [10].

Конечно, лучше всего игроку II воспользоваться случайным механизмом, обеспечивающим ему проигрыш не больше, чем цена игры , аналогичным случайному механизму T(m, k), изложенному в [7]. Но этот вопрос является темой другой статьи. Здесь мы ограничиваемся рассмотрением двух частных случаев:

1) a = 2, b= 0, с = 1. Согласно (6)(8) .

Целевая функция (2) примет вид

= 2σξ + (1 — ξ)(1 — σ).

Здесь, при ξ = 1/3 независимо от значения σ, при σ = 1/3 независимо от значения ξ. Так что, в случайном механизме T(m, k) дробь m/k может быть выбрана так, что m/kln3 с любой точностью. Тогда обеспечивается равенство σ = 1/3 с заданной точностью и случайный механизм T(m, k) может быть использован игроком II при разыгрывании рассматриваемой игры ОБМ.

2) a = 1, b= 0, с = 2. Согласно (6)(8) .

Целевая функция (2) примет вид

= σξ + 2(1 — ξ)(1 — σ).

Здесь, при ξ = 2/3 независимо от значения σ, приσ = 2/3 независимо от значения ξ. Так что, в случайном механизме T(m, k) дробь m/k может быть выбрана так, что m/kln с любой точностью. Тогда обеспечивается равенство σ = 2/3 с заданной точностью и случайный механизм T(m, k) может быть использован игроком II при разыгрывании рассматриваемой игры ОБМ.

Литература:

  1. Gillette D. Stochastic games with zero stop probabilities // Contributions to the Theory of Games. V.III / Dresher M. Princeton, Univ. Press., 1957. Ann. Math. Studies № 39.
  2. Blackwell D. The big Matсh // STAM J. Appl / Math. 1970. № 19. Р. 473–476.
  3. ИбрагимовА. А. Омарковскойигре«большойматч» // РАН. Автоматикаителемеха-ника. 2000. № 11. С. 104–113.
  4. ИбрагимовА. А. Марковскиеигрыснесколькимиэргодическимиклассами // Укра-инскийматематическийжурнал. 2003. Т.55. № 6. С. 762–778.
  5. ИбрагимовА. А. Существованиезначениявобщихмарковскихиграх // ИзвестияРАН. Теорияисистемыуправления. 2004. № 2. С.5–15.
  6. ИбрагимовА. А. Оптимальныедействиясторонвбольшомматче // VI Междуна-роднаяконференция MMR 2009 —Математическиеметодывтеориинадежности (Москва, 22–29 июня 2009 г.). Расширенныетезисыдокладов. С. 256–260.
  7. ИбрагимовА. А. Марковскаяигра«Большойматч»вклассестационарнқхстратегий // Журнал«Молодойученый»№ 4 (84), март, 2015 г. Москва. С. 4–7.
  8. ДюбинГ. Н., СуздальВ. Г. Введениевприкладнуютеориюигр. М.: Наука, 1981. 336 с.
  9. ИбрагимовА. А. Решениеобщеймарковскойигрыпутемаппроксимацииееигройспереоценкой // Журнал«Молодойученый»№ 13 (117), июль-1, 2016 г. Москва.
  10. ИбрагимовА. А. Построениефункцииполезностидлястатистическойзадачире-шениясвходнойплатой // Узбекскийжурнал«Проблемыинформатикииэнергетики». 1997. № 5. С. 3–8.

Обсуждение

Социальные комментарии Cackle