Лекция 6. Лекция 6. Введение в теорию игр. Основные понятия матричных игр.. Лекция Введение в теорию игр. Основные понятия матричных игр

• Название: Лекция Введение в теорию игр. Основные понятия матричных игр
• Анкор: Лекция 6
• Дата: 06.12.2020
• Размер: 190.95 Kb.
• Имя файла: Лекция 6. Введение в теорию игр. Основные понятия матричных игр..pdf
• Тип: Лекция; #157375

5
Лекция 1. Введение в теорию игр. Основные понятия матричных игр.
Ключевые слова. Игра, игрок, ход в игре, стратегия, парные, конечные, бесконечные, антагонистические игры, верхняя и нижняя цены игры, чистые, смешанные стратегии.
1.1.
Понятие игры
Теория игр анализирует принятие решений экономическими субъектами, которых называют, по традиции, игроками, в ситуациях, когда на результаты этих решений влияют действия, предпринимаемые другими экономическими субъектами. Такие ситуации принято называть
играми.
В свою очередь, игрок – это просто термин, который удобен для проведения аналогии изучаемой ситуации с салонной игрой с четко описанными правилами. Каждый игрок обладает определенной свободой выбора действий. Своими действиями игрок влияет не только на свой результат, но и на результаты всех остальных. Результат оценивается заданной для каждого игрока функцией выигрыша. Считается, что цель игрока – максимизировать свой выигрыш.
Определение. Игра – математическая модель конфликтной ситуации.
Определение. Ход в игре – выбор и осуществление игроком одного из предусмотренных правилами игры действий.
Определение. Стратегия – последовательность всех ходов до окончания игры.
1.2.
Классификация игр
В зависимости от числа стратегий:
-
конечные, если у игрока имеется конечное количество стратегий;
-
бесконечные (в противном случае).
По числу игроков:
-
парные (два игрока);
-
множественные (больше двух игроков).
В зависимости от взаимоотношенй игроков:
-
кооперативные, если в игре заранее определены коалиции;
-
коалиционные, если игроки могут вступать в соглашения;
-
бескоалиционные, если игрокам нельзя вступать в соглашения.
Определение. В играх с нулевой суммой одни игроки выигрывают за счет других, т.е. суммарный выигрыш всех игроков равен нулю.
Определение. Парные игры с нулевой суммой называются
антагонистическими.

6
Определение. Конечные антагонистические игры называются
матричными играми.
1.3.
Матричные игры
В общем случае матричная игра задается прямоугольной матрицей размера mxn:
Считается, что 1-й игрок имеет статегии , определяемые строками матрицы, а 2-й игрок – стратегии , определяемые столбцами. Каждый элемент матрицы представляет выигрыш 1-го игрока (может быть и отрицательным) у 2-го, если каждый использует свою одну соответствующую стратегию.
Если представить платежную матрицу игры в виде:
B
1
B
2
B
n
α
A
1
a
11
a
12
…
a
1n
α
1
A
2
a
21
a
22
…
a
2n
α
2
…
…
…
…
…
…
A
m
a
m1
a
m2
…
a
mn
α
m
β
β
1
β
2
…
β
n
то можно сделать следующие определения:
Нижняя цена игры (максимин):
i
i
ij
j
i
a
α
α
max min max
=
=
Верхняя цена игры (мимимакс):
j
j
ij
i
j
a
β
β
min max min
=
=
1.4.
Чистые и смешанные стратегии игроков
Определение. Чистая стратегия игрока – это возможный ход игрока, выбранный им с вероятностью, равной единице.
Определение. Смешанной стратегией первого (второго) игрока называется вектор
( )
mxn
ij
mn
m
m
n
n
a
a
a
a
a
a
a
a
a
a
A
=












=







2 1
2 22 21 1
12 11
m
A
A
A
,
,
,
2 1

n
B
B
B
,
,
,
2 1


7
(
)
(
)






=
=
≥
=
=
=
≥
=
∑
∑
=
=
1
,
,
1
,
0
,
,...,
,
1
,
,
1
,
0
,
,...,
,
1 2
1 1
2 1
n
j
j
j
n
m
i
i
i
m
y
n
i
y
y
y
y
y
x
m
i
x
x
x
x
x
Определение. Если x
i
>0, y
j
>0
, игра называется активной
Платежная функция игры:
( )
∑∑
=
=
=
n
j
m
i
j
i
ij
y
x
a
y
x
f
1 1
,
Определение.
Стратегии
(
)
(
)
*
*
2
*
1
*
*
*
2
*
1
*
,...,
,
,
,...,
,
n
m
y
y
y
y
x
x
x
x
=
=
называются оптимальными, если для произвольных стратегий
(
)
(
)
n
m
y
y
y
y
x
x
x
x
,...,
,
,
,...,
,
2 1
2 1
=
=
выполняется условие
( ) (
) ( )
y
x
f
y
x
f
y
x
f
,
,
,
*
*
*
*
≤
≤
Определение.
Решением
игры называется совокупность оптимальных стратегий и цены игры.
Теорема (об активных стратегиях). Если один игрок придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры, если другой игрок не выходит за пределы своих активных стратегий.
Теорема фон Неймана (основная теорема матричных игр). Любая матричная игра имеет по крайней мере одно решение в смешанных стратегиях – две оптимальные стратегии и соответствующую им цену:
(
)
*
*
*
*
,
,
,
y
x
f
v
y
x
=
Список литературы по лекции 1.
1.
Благодатских А.И., Петров Н.Н. Сборник задач и упражнений по теории игр. РХД, 2007. – 212 с.
2.
Громенко В.М. Теория игр. М., МГОУ, 2005, 142 с. (ссылка в ЭБС: www.knigafund.ru/books/19432
)
3.
Колобашкина Л.В. Основы теории игр: учебное пособие. М.,
БИНОМ, 2011, 163 с. (ссылка в ЭБС: www.knigafund.ru/books/68179)
4.
Невежин В.П. Теория игр. Примеры и задачи: учебное пособие.
М.:ФОРУМ, 2012. – 128 с.