Об одной модификации метода брауна



Дата25.09.2018
өлшемі27 Kb.
#47171

ОБ ОДНОЙ МОДИФИКАЦИИ МЕТОДА БРАУНА
А.В. Баркалов, Н.В. Шестакова
Нижегородский государственный университет им. Н.И. Лобачевского

факультет вычислительной математики и кибернетики

кафедра математического обеспечения ЭВМ

Россия, 603950, г. Нижний Новгород, пр. Гагарина, 23

тел.: (8312) 658510, факс: (8312) 658592

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



i(t+1) = arg max E1(i, Q(t)), t>0, (1)

1 i m

где i – чистая стратегия первого игрока, Q(t) – смешанная стратегия партнера, E1(i,Q(t)) – математическое ожидание выигрыша первого игрока.

Сходимость последовательностей P(t), Q(t) к решению игры установлена для матричных игр 1, некоторых классов биматричных игр. Одним из примеров, демонстрирующих отсутствие сходимости последовательностей стратегий, является биматричная игра – игра Шепли 2 вида (a,b) (0,0) (b,a)

(A,B) =  (b,a) (a,b) (0,0) , a>b>0. (2)

(0,0) (b,a) (a,b) 

Для решения игры (2) итерационным методом предлагается модификация метода Брауна, состоящая в замене в соотношении (1) смешанной стратегии Q(t) на стратегию Q(t+1) = (с Qj(t)+ Q(t)) / (с+t) , где с>0, Qj(t) − смешанная стратегия второго игрока, соответствующая его наилучшему выбору в момент времени t.

Как показал вычислительный эксперимент, описанная модификация обеспечивает сходимость итерационного метода для игры (2), а в матричных играх ускоряет сходимость по сравнению с классическим вариантом.


Литература

1. Робинсон Дж. Итеративный метод решения игр. В сб.: Матричные игры. – М.: Физматгиз, 1961. – С. 110-118.



2. Воробьев Н.Н. Основы теории игр. Бескоалиционные игры. – М.: Наука, 1984. – 495 с.






Достарыңызбен бөлісу:




©kzref.org 2022
әкімшілігінің қараңыз

    Басты бет