Без темы
<<  Теория и практика учебного исследования Теория инволюции  >>
Теория игр
Теория игр
Литература Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр
Литература Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр
1. Основные понятия теории матричных игр
1. Основные понятия теории матричных игр
Теория игр – это совокупность математических методов анализа и оценки
Теория игр – это совокупность математических методов анализа и оценки
Содержание теории игр: установление принципов оптимального поведения в
Содержание теории игр: установление принципов оптимального поведения в
Моделями теории игр можно описать экономические, правовые, классовые,
Моделями теории игр можно описать экономические, правовые, классовые,
Игры можно классифицировать по различным признакам: стратегические и
Игры можно классифицировать по различным признакам: стратегические и
Рассмотрим простейшую модель – игру, в которой участвуют два игрока,
Рассмотрим простейшую модель – игру, в которой участвуют два игрока,
Такую игру (Г ) называют матричной
Такую игру (Г ) называют матричной
Пусть 1-й игрок имеет всего m стратегий, а 2-й – n стратегий: Х=М={1,2
Пусть 1-й игрок имеет всего m стратегий, а 2-й – n стратегий: Х=М={1,2
Пусть – платежная матрица игры Г. Если 1-й игрок выбрал стратегию i,
Пусть – платежная матрица игры Г. Если 1-й игрок выбрал стратегию i,
Второй игрок, выбрав стратегию j, в худшем случае проиграет , а значит
Второй игрок, выбрав стратегию j, в худшем случае проиграет , а значит
Схема:
Схема:
Например, Соответствующие стратегии: i0=1(максиминная), j0=1,2
Например, Соответствующие стратегии: i0=1(максиминная), j0=1,2
Справедливо неравенство:
Справедливо неравенство:
Ситуация (i*, j*) называется ситуацией равновесия, или седловой точкой
Ситуация (i*, j*) называется ситуацией равновесия, или седловой точкой
Ситуация равновесия существует тогда и только тогда, когда (это
Ситуация равновесия существует тогда и только тогда, когда (это
Например, (2,3)-ситуация равновесная, v =4 – цена игры, i*=2, j*=3 –
Например, (2,3)-ситуация равновесная, v =4 – цена игры, i*=2, j*=3 –
Смешанной стратегией для 1-го игрока называется упорядоченная система
Смешанной стратегией для 1-го игрока называется упорядоченная система
Функция выигрыша K(x,y) в ситуации (x,y) определяется как
Функция выигрыша K(x,y) в ситуации (x,y) определяется как
Если для некоторых и и для всех и выполняется неравенство , то x*, y*
Если для некоторых и и для всех и выполняется неравенство , то x*, y*
Свойства оптимальных стратегий
Свойства оптимальных стратегий
1. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА с ценой v
1. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА с ценой v
2. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА, v –
2. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА, v –
3. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА с ценой v
3. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА с ценой v
4. Если x*, y* – решение -игры ГА, то
4. Если x*, y* – решение -игры ГА, то
5. Пусть , , v – решение игры ГА
5. Пусть , , v – решение игры ГА
6 (Лемма о масштабе)
6 (Лемма о масштабе)
2. ( ) - Игры
2. ( ) - Игры
Пусть – платежная матрица игры Г. Если она не имеет седловой точки, то
Пусть – платежная матрица игры Г. Если она не имеет седловой точки, то
1) решив две системы:
1) решив две системы:
2) по формулам: или или
2) по формулам: или или
3) в матричном виде: где – определитель матрицы А, А* – присоединенная
3) в матричном виде: где – определитель матрицы А, А* – присоединенная
Найдем, например, решение игры с платежной матрицей , которая не имеет
Найдем, например, решение игры с платежной матрицей , которая не имеет
1) Составим системы: Решив системы, получим: то есть -решение игры
1) Составим системы: Решив системы, получим: то есть -решение игры
2) Найдем решение по формулам:
2) Найдем решение по формулам:
3) Найдем решение в матричном виде:
3) Найдем решение в матричном виде:
3. И – игры
3. И – игры
Рассмотрим игру с платежной матрицей
Рассмотрим игру с платежной матрицей
Если 1-й игрок применит смешанную стратегию , а 2-й игрок – чистую
Если 1-й игрок применит смешанную стратегию , а 2-й игрок – чистую
Аналогично при выборе 2-м игроком чистых стратегий , , (2) (3) (4)
Аналогично при выборе 2-м игроком чистых стратегий , , (2) (3) (4)
Теория игр
Теория игр
Точка A является точкой пересечения прямых (2) и (3), поэтому решение
Точка A является точкой пересечения прямых (2) и (3), поэтому решение
По формулам решения – игры получим:
По формулам решения – игры получим:
Тогда решение исходной игры имеет вид (номерам столбцов, не вошедших в
Тогда решение исходной игры имеет вид (номерам столбцов, не вошедших в
Аналогично решаются - игры
Аналогично решаются - игры
(1) (2) (3)
(1) (2) (3)
Теория игр
Теория игр
Точка B является точкой пересечения прямых (2) и (3)
Точка B является точкой пересечения прямых (2) и (3)
Тогда решение исходной игры:
Тогда решение исходной игры:
Пусть платежная матрица игры
Пусть платежная матрица игры
A – точка пересечения прямых (2) и (3), ее абсциссу найдем, решая игру
A – точка пересечения прямых (2) и (3), ее абсциссу найдем, решая игру
B – точка пересечения прямых (1) и (2), ее абсциссу найдем, решая игру
B – точка пересечения прямых (1) и (2), ее абсциссу найдем, решая игру
Решение исходной игры: , где , , то есть 1-й игрок имеет множество
Решение исходной игры: , где , , то есть 1-й игрок имеет множество
4. Доминирование стратегий
4. Доминирование стратегий
Иногда на основании простого рассмотрения матрицы игры можно сказать,
Иногда на основании простого рассмотрения матрицы игры можно сказать,
В результате вместо игры ГА с матрицей А можно рассмотреть игру с
В результате вместо игры ГА с матрицей А можно рассмотреть игру с
Легко найти решение игры Можно предположить, что решение игры ГА будет
Легко найти решение игры Можно предположить, что решение игры ГА будет
Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию,
Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию,
Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию,
Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию,
Стратегия может доминироваться также выпуклой линейной комбинацией
Стратегия может доминироваться также выпуклой линейной комбинацией
Если – некоторая смешанная стратегия, то ее расширением на i-ом месте
Если – некоторая смешанная стратегия, то ее расширением на i-ом месте
теорема: пусть ГА – -игра, в которой i-я строка доминируема, – игра с
теорема: пусть ГА – -игра, в которой i-я строка доминируема, – игра с
5. Множество решений матричной игры
5. Множество решений матричной игры
Чтобы найти множество всех решений игры с платежной матрицей А, нужно
Чтобы найти множество всех решений игры с платежной матрицей А, нужно
Множество всех решений каждого игрока является выпуклой линейной
Множество всех решений каждого игрока является выпуклой линейной
Решение игры, заданной квадратной подматрицей В, можно найти в
Решение игры, заданной квадратной подматрицей В, можно найти в
Найдем, например, множество всех решений игры ГА с платежной матрицей
Найдем, например, множество всех решений игры ГА с платежной матрицей
Подматрицы не дадут решений, так как матрица А не имеет седловых точек
Подматрицы не дадут решений, так как матрица А не имеет седловых точек
Для В: является решением игры ГА (убеждаемся в этом проверкой)
Для В: является решением игры ГА (убеждаемся в этом проверкой)
Для С: – является решением игры ГА
Для С: – является решением игры ГА
Таким образом, в игре ГА 1-й игрок имеет единственную оптимальную
Таким образом, в игре ГА 1-й игрок имеет единственную оптимальную
6. Сведение матричной игры к двойственной задаче линейного
6. Сведение матричной игры к двойственной задаче линейного
Пусть матрица игры имеет вид K=K(x,y)– функция выигрыша, , ,
Пусть матрица игры имеет вид K=K(x,y)– функция выигрыша, , ,
Тогда по свойству 2 оптимальных стратегий для любых , должно
Тогда по свойству 2 оптимальных стратегий для любых , должно
То есть
То есть
Теория игр
Теория игр
Пример
Пример
Решение
Решение
Составим двойственную задачу линейного программирования:
Составим двойственную задачу линейного программирования:
Решим задачу симплексным методом
Решим задачу симплексным методом
3
3
7/3
7/3
С0
С0
С0
С0
Получаем решение двойственной задачи:
Получаем решение двойственной задачи:
Тогда решение игры с матрицей Решение исходной игры:
Тогда решение игры с матрицей Решение исходной игры:
7. Приближенное решение матричных игр
7. Приближенное решение матричных игр
Где v – цена игры, k– номер партии, – максимальное значение суммарного
Где v – цена игры, k– номер партии, – максимальное значение суммарного
За приближенные оптимальные стратегии игроков принимают векторы,
За приближенные оптимальные стратегии игроков принимают векторы,
Пример
Пример
1
1
7
7
Приближенное решение игры за 12 партий: v =1,45,
Приближенное решение игры за 12 партий: v =1,45,

Презентация на тему: «Теория игр». Автор: oleg. Файл: «Теория игр.ppt». Размер zip-архива: 326 КБ.

Теория игр

содержание презентации «Теория игр.ppt»
СлайдТекст
1 Теория игр

Теория игр

2 Литература Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр

Литература Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр

– М., 1998. 2. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. – М.: Наука, 1985. 3. Дюбин Г.Н., Суздаль В.Г. Введение в прикладную теорию игр.– М.: Наука, 1981.

3 1. Основные понятия теории матричных игр

1. Основные понятия теории матричных игр

4 Теория игр – это совокупность математических методов анализа и оценки

Теория игр – это совокупность математических методов анализа и оценки

конфликтных ситуаций.

5 Содержание теории игр: установление принципов оптимального поведения в

Содержание теории игр: установление принципов оптимального поведения в

условиях неопределенности (конфликта), доказательство существования решений, удовлетворяющих этим принципам, указание алгоритмов нахождения решений, их реализация.

6 Моделями теории игр можно описать экономические, правовые, классовые,

Моделями теории игр можно описать экономические, правовые, классовые,

военные конфликты, взаимодействие человека с природой. Все такие модели в теории игр принято называть играми.

7 Игры можно классифицировать по различным признакам: стратегические и

Игры можно классифицировать по различным признакам: стратегические и

чисто случайные, бескоалиционные и коалиционные, игры 1, 2, …, n лиц (по числу игроков), конечные и бесконечные (по числу стратегий), игры в нормальной форме и динамические, с нулевой суммой («антагонистические») и с ненулевой суммой.

8 Рассмотрим простейшую модель – игру, в которой участвуют два игрока,

Рассмотрим простейшую модель – игру, в которой участвуют два игрока,

множество стратегий каждого игрока конечно, а выигрыш одного игрока равен проигрышу другого (бескоалиционная, конечная, антагонистическая игра двух лиц).

9 Такую игру (Г ) называют матричной

Такую игру (Г ) называют матричной

Она определяется тройкой Г=(X,Y,K), где Х – множество стратегий 1-го игрока, Y – множество стратегий 2-го игрока, K=K(x,y) – функция выигрыша (выигрыш 1-го игрока и соответственно проигрыш 2-го при условии, что 1-й игрок выбрал стратегию , а 2-й – стратегию ). Пару (x,y) называют ситуацией в игре Г.

10 Пусть 1-й игрок имеет всего m стратегий, а 2-й – n стратегий: Х=М={1,2

Пусть 1-й игрок имеет всего m стратегий, а 2-й – n стратегий: Х=М={1,2

…, m}, Y=N={1,2, …, n}. Тогда игра Г полностью определяется заданием матрицы , где aij=K(i,j) – выигрыш 1-го игрока при условии, что он выбрал стратегию (т.е. строку) i, а 2-й игрок – стратегию (т.е. столбец) j (эти стратегии называют чистыми). Матрица А называется матрицей игры или платежной матрицей.

11 Пусть – платежная матрица игры Г. Если 1-й игрок выбрал стратегию i,

Пусть – платежная матрица игры Г. Если 1-й игрок выбрал стратегию i,

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

12 Второй игрок, выбрав стратегию j, в худшем случае проиграет , а значит

Второй игрок, выбрав стратегию j, в худшем случае проиграет , а значит

может гарантировать себе проигрыш , обозначим его – верхняя цена игры, или минимакс, соответствующая стратегия 2-го игрока называется минимаксной.

13 Схема:

Схема:

14 Например, Соответствующие стратегии: i0=1(максиминная), j0=1,2

Например, Соответствующие стратегии: i0=1(максиминная), j0=1,2

(минимаксная).

15 Справедливо неравенство:

Справедливо неравенство:

16 Ситуация (i*, j*) называется ситуацией равновесия, или седловой точкой

Ситуация (i*, j*) называется ситуацией равновесия, или седловой точкой

если для любых , , выполняется неравенство Соответствующие стратегии i*, j* называются оптимальными чистыми стратегиями 1-го и 2-го игроков, а число называется ценой игры. Элемент является одновременно минимумом в своей строке и максимумом в своем столбце.

17 Ситуация равновесия существует тогда и только тогда, когда (это

Ситуация равновесия существует тогда и только тогда, когда (это

значение и является ценой игры v).

18 Например, (2,3)-ситуация равновесная, v =4 – цена игры, i*=2, j*=3 –

Например, (2,3)-ситуация равновесная, v =4 – цена игры, i*=2, j*=3 –

оптимальные стратегии 1-го и 2-го игроков. Выбрав их, 1-й игрок обеспечит себе выигрыш не менее 4 ед., а 2-й игрок проиграет не более 4 ед. при любом выборе другого игрока.

19 Смешанной стратегией для 1-го игрока называется упорядоченная система

Смешанной стратегией для 1-го игрока называется упорядоченная система

m действительных чисел x=(x1, x2, …, xm), , , которые можно рассматривать как относительные частоты (вероятности), с которыми 1-й игрок выбирает чистые стратегии i=1, 2, …, m. Аналогично определяется смешанная стратегия для 2-го игрока: y=(y1, y2, …, yn), , .

20 Функция выигрыша K(x,y) в ситуации (x,y) определяется как

Функция выигрыша K(x,y) в ситуации (x,y) определяется как

математическое ожидание выигрыша 1-го игрока при условии, что 1-й и 2-й игроки выбрали соответственно стратегии x=(x1, x2, …, xm) и y=(y1, y2, …, yn): .

21 Если для некоторых и и для всех и выполняется неравенство , то x*, y*

Если для некоторых и и для всех и выполняется неравенство , то x*, y*

называются оптимальными смешанными стратегиями игроков, число называется ценой игры, пара (x*, y*) – стратегической седловой точкой тройка x*, y*, v – решением игры.

22 Свойства оптимальных стратегий

Свойства оптимальных стратегий

23 1. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА с ценой v

1. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА с ценой v

Тогда, для того чтобы элемент был оптимальной стратегией 1-го игрока, необходимо и достаточно, чтобы для каждого элемента выполнялось неравенство Аналогично, для того чтобы был оптимальной стратегией 2-го игрока, необходимо и достаточно, чтобы для каждого выполнялось неравенство

24 2. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА, v –

2. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА, v –

действительное число, , . Тогда, для того чтобы v было ценой игры, а x* и y* были оптимальными стратегиями соответственно 1-го и 2-го игроков, необходимо и достаточно, чтобы для любых и выполнялось неравенство

25 3. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА с ценой v

3. Пусть K(x,y) – математическое ожидание выигрыша в игре ГА с ценой v

Тогда, для того чтобы элемент был оптимальной стратегией 1-го игрока, необходимо и достаточно, чтобы для каждого выполнялось неравенство . Аналогично, для того чтобы был оптимальной стратегией 2-го игрока, необходимо и достаточно, чтобы для каждого выполнялось неравенство .

26 4. Если x*, y* – решение -игры ГА, то

4. Если x*, y* – решение -игры ГА, то

27 5. Пусть , , v – решение игры ГА

5. Пусть , , v – решение игры ГА

Тогда для любого , при котором , выполняется неравенство xi=0, а для любого , при котором , выполняется неравенство yj=0.

28 6 (Лемма о масштабе)

6 (Лемма о масштабе)

Если ГА – игра с матрицей , а – игра с матрицей , где , где ?,?=const, ?>0, то множества оптимальных стратегий игроков в играх ГА и совпадают, а . Иначе говоря, две игры, отличающиеся лишь началом отсчета выигрышей и масштабом их измерения, стратегически эквивалентны.

29 2. ( ) - Игры

2. ( ) - Игры

30 Пусть – платежная матрица игры Г. Если она не имеет седловой точки, то

Пусть – платежная матрица игры Г. Если она не имеет седловой точки, то

единственное решение игры Г можно найти

31 1) решив две системы:

1) решив две системы:

32 2) по формулам: или или

2) по формулам: или или

33 3) в матричном виде: где – определитель матрицы А, А* – присоединенная

3) в матричном виде: где – определитель матрицы А, А* – присоединенная

к А матрица, , , , JT и yT – транспонированные матрицы J и y.

34 Найдем, например, решение игры с платежной матрицей , которая не имеет

Найдем, например, решение игры с платежной матрицей , которая не имеет

седловой точки.

35 1) Составим системы: Решив системы, получим: то есть -решение игры

1) Составим системы: Решив системы, получим: то есть -решение игры

36 2) Найдем решение по формулам:

2) Найдем решение по формулам:

37 3) Найдем решение в матричном виде:

3) Найдем решение в матричном виде:

38 3. И – игры

3. И – игры

39 Рассмотрим игру с платежной матрицей

Рассмотрим игру с платежной матрицей

40 Если 1-й игрок применит смешанную стратегию , а 2-й игрок – чистую

Если 1-й игрок применит смешанную стратегию , а 2-й игрок – чистую

стратегию , то .(1)

41 Аналогично при выборе 2-м игроком чистых стратегий , , (2) (3) (4)

Аналогично при выборе 2-м игроком чистых стратегий , , (2) (3) (4)

42 Теория игр
43 Точка A является точкой пересечения прямых (2) и (3), поэтому решение

Точка A является точкой пересечения прямых (2) и (3), поэтому решение

исходной игры можно найти, решив игру

44 По формулам решения – игры получим:

По формулам решения – игры получим:

45 Тогда решение исходной игры имеет вид (номерам столбцов, не вошедших в

Тогда решение исходной игры имеет вид (номерам столбцов, не вошедших в

матрицу , соответствуют нулевые координаты вектора ), .

46 Аналогично решаются - игры

Аналогично решаются - игры

Пусть, например, , – смешанная стратегия 2-го игрока, 1-й игрок выбирает чистые стратегии i=1,2,3.

47 (1) (2) (3)

(1) (2) (3)

48 Теория игр
49 Точка B является точкой пересечения прямых (2) и (3)

Точка B является точкой пересечения прямых (2) и (3)

Найдем решение игры

50 Тогда решение исходной игры:

Тогда решение исходной игры:

51 Пусть платежная матрица игры

Пусть платежная матрица игры

(3)

Рис.3

A

B

(2)

(1)

x

x1

x2

1

0

52 A – точка пересечения прямых (2) и (3), ее абсциссу найдем, решая игру

A – точка пересечения прямых (2) и (3), ее абсциссу найдем, решая игру

53 B – точка пересечения прямых (1) и (2), ее абсциссу найдем, решая игру

B – точка пересечения прямых (1) и (2), ее абсциссу найдем, решая игру

54 Решение исходной игры: , где , , то есть 1-й игрок имеет множество

Решение исходной игры: , где , , то есть 1-й игрок имеет множество

оптимальных стратегий, 2-й игрок – единственную оптимальную стратегию, это чистая стратегия j=2.

55 4. Доминирование стратегий

4. Доминирование стратегий

56 Иногда на основании простого рассмотрения матрицы игры можно сказать,

Иногда на основании простого рассмотрения матрицы игры можно сказать,

что некоторые чистые стратегии могут войти в оптимальную смешанную стратегию лишь с нулевой вероятностью.

57 В результате вместо игры ГА с матрицей А можно рассмотреть игру с

В результате вместо игры ГА с матрицей А можно рассмотреть игру с

матрицей

58 Легко найти решение игры Можно предположить, что решение игры ГА будет

Легко найти решение игры Можно предположить, что решение игры ГА будет

иметь вид:

59 Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию,

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию,

если для всех и хотя бы для одного j . В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.

60 Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию,

Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию,

если для всех и хотя бы для одного i В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой.

61 Стратегия может доминироваться также выпуклой линейной комбинацией

Стратегия может доминироваться также выпуклой линейной комбинацией

других стратегий. Так, i-я стратегия 1-го игрока доминируется выпуклой линейной комбинацией остальных стратегий, если ; j-я стратегия 2-го игрока доминируется выпуклой линейной комбинацией остальных стратегий, если

62 Если – некоторая смешанная стратегия, то ее расширением на i-ом месте

Если – некоторая смешанная стратегия, то ее расширением на i-ом месте

будем называть стратегию вида

63 теорема: пусть ГА – -игра, в которой i-я строка доминируема, – игра с

теорема: пусть ГА – -игра, в которой i-я строка доминируема, – игра с

матрицей , полученной из А вычеркиванием i-ой строки. Тогда 1) ; 2) всякая оптимальная стратегия 2-го игрока в игре является оптимальной и в игре ГА; 3) если x* – оптимальная стратегия 1-го игрока в игре , то – его оптимальная стратегия в игре ГА. Аналогичная теорема имеет место для доминируемого столбца.

64 5. Множество решений матричной игры

5. Множество решений матричной игры

65 Чтобы найти множество всех решений игры с платежной матрицей А, нужно

Чтобы найти множество всех решений игры с платежной матрицей А, нужно

рассмотреть все квадратные подматрицы матрицы А. Найдя решения игр, заданных подматрицами, нужно составить их расширения на соответствующих местах и проверить, являются ли полученные стратегии оптимальными для игры ГА.

66 Множество всех решений каждого игрока является выпуклой линейной

Множество всех решений каждого игрока является выпуклой линейной

комбинацией найденных решений.

67 Решение игры, заданной квадратной подматрицей В, можно найти в

Решение игры, заданной квадратной подматрицей В, можно найти в

матричном виде по формулам

68 Найдем, например, множество всех решений игры ГА с платежной матрицей

Найдем, например, множество всех решений игры ГА с платежной матрицей

69 Подматрицы не дадут решений, так как матрица А не имеет седловых точек

Подматрицы не дадут решений, так как матрица А не имеет седловых точек

Рассмотрим подматрицы :

70 Для В: является решением игры ГА (убеждаемся в этом проверкой)

Для В: является решением игры ГА (убеждаемся в этом проверкой)

71 Для С: – является решением игры ГА

Для С: – является решением игры ГА

Для D получим такое же решение, как для В.

72 Таким образом, в игре ГА 1-й игрок имеет единственную оптимальную

Таким образом, в игре ГА 1-й игрок имеет единственную оптимальную

стратегию 2-й игрок имеет множество оптимальных стратегий где , , цена игры v=1.

73 6. Сведение матричной игры к двойственной задаче линейного

6. Сведение матричной игры к двойственной задаче линейного

программирования

74 Пусть матрица игры имеет вид K=K(x,y)– функция выигрыша, , ,

Пусть матрица игры имеет вид K=K(x,y)– функция выигрыша, , ,

75 Тогда по свойству 2 оптимальных стратегий для любых , должно

Тогда по свойству 2 оптимальных стратегий для любых , должно

выполняться условие

76 То есть

То есть

77 Теория игр
78 Пример

Пример

Найти решение игры с матрицей

79 Решение

Решение

Перейдем к положительной матрице, прибавив 3 ко всем элементам матрицы А:

80 Составим двойственную задачу линейного программирования:

Составим двойственную задачу линейного программирования:

81 Решим задачу симплексным методом

Решим задачу симплексным методом

82 3

3

С0

С0

P0

P0

1

1

1

0

0

0

q1

q2

q3

q4

q5

q6

1-я итерация

1-я итерация

1-я итерация

1-я итерация

q4

0

1

1

1

3

1

0

0

q5

0

1

1

3

2

0

1

0

q6

0

1

2

2

0

0

1

0

-1

-1

-1

0

0

0

Базис

Базис

83 7/3

7/3

С0

С0

P0

P0

1

1

1

0

0

0

q1

q2

q3

q4

q5

q6

2-я итерация

2-я итерация

2-я итерация

2-я итерация

q4

0

2/3

0

1/3

7/3

1

0

-1/3

q5

0

2/3

0

4/3

0

1

-1/3

q1

1

1/3

1

2/3

2/3

0

0

1/3

0

0

-1/3

-1/3

0

0

1/3

Базис

Базис

84 С0

С0

С0

P0

P0

1

1

1

0

0

0

q1

q2

q3

q4

q5

q6

3-я итерация

3-я итерация

3-я итерация

3-я итерация

q4

0

4/7

0

0

15/7

1

-1/7

-2/7

q2

1

2/7

0

1

4/7

0

3/7

-1/7

q1

1

1/7

1

0

2/7

0

-2/7

3/7

3/7

0

0

-1/7

0

1/7

2/7

Базис

Базис

85 С0

С0

С0

P0

P0

1

1

1

0

0

0

q1

q2

q3

q4

q5

q6

4-я итерация

4-я итерация

4-я итерация

4-я итерация

q3

1

4/15

0

0

1

7/15

-1/15

-2/15

q2

1

2/15

0

1

0

-4/15

7/15

-1/15

q1

1

1/15

1

0

0

-2/15

-4/15

7/15

7/15

0

0

0

1/15

2/15

4/15

Базис

Базис

86 Получаем решение двойственной задачи:

Получаем решение двойственной задачи:

87 Тогда решение игры с матрицей Решение исходной игры:

Тогда решение игры с матрицей Решение исходной игры:

88 7. Приближенное решение матричных игр

7. Приближенное решение матричных игр

89 Где v – цена игры, k– номер партии, – максимальное значение суммарного

Где v – цена игры, k– номер партии, – максимальное значение суммарного

выигрыша 1-го игрока в k-ой партии при выборе различных стратегий, – минимальное значение суммарного проигрыша 2-го игрока в k-ой партии при выборе различных стратегий.

90 За приближенные оптимальные стратегии игроков принимают векторы,

За приближенные оптимальные стратегии игроков принимают векторы,

координатами которых являются относительные частоты выбора соответствующих чистых стратегий.

91 Пример

Пример

Найти приближенное решение игры, заданной матрицей

92 1

1

2

3

1

2

1

3

3

1

2

3

3

3

5

1

4

3

4

3

5

8

1

5

4

5

3

7

9

3

6

5

6

3

9

10

5

7

6

7

3

11

11

7

8

1,833

1,167

a

?

b

?

b

?

c

?

c

?

c

?

№ Партии k

№ Партии k

Выбор 1-го игрока

Выбор 1-го игрока

Выбор 2-го игрока

Выбор 2-го игрока

Суммарный выигрыш 1-го игрока при выборе стратегии

Суммарный выигрыш 1-го игрока при выборе стратегии

Суммарный выигрыш 1-го игрока при выборе стратегии

Суммарный проигрыш 2-го игрока при выборе стратегии

Суммарный проигрыш 2-го игрока при выборе стратегии

Суммарный проигрыш 2-го игрока при выборе стратегии

a

b

c

?

?

?

93 7

7

8

3

13

12

9

9

1,857

1,286

8

11

4

14

13

11

10

1,75

1,25

9

14

5

15

14

13

11

1,667

1,222

10

17

6

16

15

15

12

1,7

1,2

11

20

7

17

17

16

15

1,818

1,364

12

23

8

18

19

17

18

1,917

1,417

c

?

c

?

c

?

c

?

a

?

a

?

№ Партии k

№ Партии k

Выбор 1-го игрока

Выбор 1-го игрока

Выбор 2-го игрока

Выбор 2-го игрока

Суммарный выигрыш 1-го игрока при выборе стратегии

Суммарный выигрыш 1-го игрока при выборе стратегии

Суммарный выигрыш 1-го игрока при выборе стратегии

Суммарный проигрыш 2-го игрока при выборе стратегии

Суммарный проигрыш 2-го игрока при выборе стратегии

Суммарный проигрыш 2-го игрока при выборе стратегии

a

b

c

?

?

?

94 Приближенное решение игры за 12 партий: v =1,45,

Приближенное решение игры за 12 партий: v =1,45,

;

,

«Теория игр»
http://900igr.net/prezentacija/biologija/teorija-igr-249426.html
cсылка на страницу

Без темы

1004 презентации
Урок

Биология

136 тем
Слайды