Файл: прикладная математика учебное пособие московский автомобильнодорожный.docx

Прежде чем определить термин «игра», рассмотрим стандартную ситуацию. Пусть имеется два игрока или более, соблюдающих неко- торые правила при принятии того или иного решения. Каждый из игро- ков старается извлечь наибольшую пользу для себя из всех возмож- ных вариантов. При этом, естественно, между игроками возникает конфликт, при разрешении которого и определяется оптимальная стратегия поведения всех участников конфликта. Рассмотренная си- туация и называется игрой. Оптимальная стратегия поведения игро- ков называется выигрышнойстратегией. Стратегия игрока называ- ется оптимальной, если при

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

Рассмотрим парную игру с нулевой суммой. Это значит, что в игре

будут участвовать только два игрока, а ее результатом будет выиг- рыш одного из них с платежом равным проигрышу другого. Пусть у

^{первого}^игрока^{имеется}^k^{возможных}^{стратегий}^,^а^у^{второго}^ихn, ^и

они, не зная выбора соперника, выбирают i-ю и j-ю стратегию соответ-

ственно. Очевидно, что 1  i k

и 1

j n.

В результате применения

соответствующих стратегий получаем платеж, равный

a_ij.

Причем, ес-

ли a_ij

то выигрывает первый из игроков либо второй.

1 ... 8 9 10 11 12 13 14 15 ... 42

Понятия задачи теории игр

Из чисел

^aij

составим матрицу

A, строки которой соответствуют

стратегиям первого игрока, а столбцы – стратегиям второго. Такая матрица называется платежной матрицей игры, а сама игра – конеч-

ной игрой размерностью

k n:

 ^a¹¹^a^{12 ...}^a¹ⁿ

^a a ... a ^

A ^

21 22 2n__.

(2.1)

^... ... ... ... ^

^a a ... a ^

 k1 k2 kn

Введем два понятия – нижняяиверхняяценыигры. Число

  max(mina_ij)

называется нижнейценойигры, а

  min(max a_ij) –

1ik1 jn

1 jn1ik

верхнейценойигры.

Утверждение 1. Нижняя цена игры всегда не превосходит верх- нюю цену игры.

Если для игры нижняя и верхняя цены игры равны одному и тому

^же^числу, ^то^она^{называется}^ценой^игры^,^а^сама^игра^{называется}

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

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

шанную стратегию первого игрока как вектор

u (u₁,u₂,...,u_k),

а второ-

го игрока как вектор v

 (v₁,v₂,...,v_n),

где

u_i,v_j 0

и 1  i k

и 1

j n.

Очевидно, что для компонентов этих векторов должно выполняться условие (2.2):

k n

^^ui

i1

 _v_jj1

 1,

(2.2)

и, если

u^, v^ – оптимальные стратегии первого и второго игроков со-

ответственно, то

__auv  .
k n

 

ij i j

(2.3)

i1 j1

Процесс нахождения решения игры состоит в определении опти- мальных стратегий и нахождении цены игры.

Утверждение 2. Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.

Утверждение 3. Выполнение условий: