Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Конспект_САиПР_2012_2013_к зачету.doc
Скачиваний:
30
Добавлен:
01.03.2025
Размер:
2 Мб
Скачать
☆

14.2. Формальное описание матричной антагонистической игры

Важными и хорошо изученными играми являются парные антагонистические игры.

Тройка G=<X,Y,A>, где X, Y - множества чистых стратегий 1-го и 2-го игроков соответственно, A(x,y) x X, y Y – функция выигрыша первого игрока, или просто функция выигрыша, называется антагонистической игрой с нулевой суммой.

Если X и Y конечны, то G называется конечной антагонистической игрой. Пары стратегий вида (x,y) называются ситуациями в игре G. Цель каждого из игроков в игре – получить максимальный выигрыш. Игрок 1, изменяя x X, старается максимизировать A(x,y), а игрок 2 выбирает y Y так, чтобы минимизировать A(x,y), но каждый из игроков в отдельности не контролирует полностью значение A(x,y). Задача теории игр состоит в определении наиболее рационального поведения каждого игрока.

Процесс разыгрывания конечной антагонистической игры состоит в следующем.

  1. 1-й игрок выбирает чистую стратегию x X;

  2. Независимо от первого игрока 2-й игрок выбирает чистую стратегию y Y;

  3. Возникает ситуация (x,y), в которой 1-й игрок получает от 2-го игрока выигрыш A(x,y), при этом 2-й игрок столько же проигрывает, т.е. его выигрыш составляет - A(x,y).

Так как число возможных действий каждого из игроков конечно, а содержательная сущность стратегии определяется вне математической модели, можно предполагать, что 1-й игрок имеет m стратегий, т.е. X={1,2,…,m, }, а 2-й игрок имеет n стратегий, т.е. Y={1,2,…,n}. Пусть из своих m стратегий 1-й игрок выберет i-ю стратегию (i=1,…m), а 2-й игрок выберет j-ю стратегию (j=1,…n), тогда значения функции A(x,y) естественно представить в виде матрицы A размерности m×n

где в i-й строке расположены выигрыши 1-го игрока в ситуациях (i,1),…,(i,n), а в j-м столбце – проигрыши 2-го игрока в ситуациях (1,j),…,(m,j).

Примеры матричных игр

Игра в орлянку.

Игроки выбирают ход{орел, решка}. Если ходы совпали, то выиграл первый, иначе второй.

II игрок

I игрок

орел

решка

орел

1

– 1

решка

– 1

1

Прорыв обороны. Первый игрок выбирает систему зенитного вооружения. Второй игрок выбирает самолет. Элементы aij задают вероятность поражения самолета j системой i. Цель второго игрока — прорвать оборону.

Самолеты

Зенитки

0,5

0,6

0,8

0,9

0,7

0,8

0,7

0,5

0,6

В первом примере все ходы одинаково плохи или хороши. Во втором примере ход (2, 2) в некотором смысле лучший для обеих сторон: если взять самолет 2, то зенитка 2 — лучшая для первого игрока; если взять зенитку 2, то самолет 2 лучший для второго. В матрице есть седловая точка!

Определение. Седловой точкой матрицы (aij) называют пару (i0j0) такую, что

aij0≤ai0jo≤ai0j

Принцип минимакса (осторожности).

Предположим, что противник всеведущ и угадывает все ходы! Первый игрок предполагает, что второй все знает и для хода i первого игрока выберет j(i): aij(i)  aij, j = 1,…, n. Обозначим αi=aij(i)=min aij, j=1,…,n; i=1,...,m

Тогда лучшей стратегией для первого игрока является выбор i0 такой, что

α=maxiai=maxi minjaij=αi0

Величину назовем нижней ценой игры в чистых стратегиях.

Второй игрок из соображений осторожности считает, что первый  j выберет i(j) так, что aij (j)  aij,  i, т.е. βj=max aij,j=1,…,m и выбирает j с минимальным j, т.е.

Β=minj maxi aij=βj0

Величину назовем верхней ценой игры в чистых стратегиях.

Пример 1. = –1, = +1,

Пример 2. α=max{0.5, 0.7, 0.5}=0.7;

β=min{0.9, 0.7, 0.8}=0.7.

α=β.

Лемма. Для любой функции f(x,y), xX, yY, справедливо неравенство

в предположении, что эти величины существуют.

Доказательство. Введем обозначения:

Тогда

Теорема. Необходимым и достаточным условием равенства верхней и нижней цен игры в чистых стратегиях является существование седловой точки в матрице (aij).

Доказательство. Необходимость. Пусть = . По определению

т.е. α≤αi0j0≤β. Так как = , то αij0≤αi0j0≤ αi0j, , т.е. является седловой точкой.

Достаточность. Пусть седловая точка (i0j0) существует, т.е.

то αij0≤αi0j0≤ αi0j, .

Тогда но по лемме верно обратное, т.е. . Следовательно = .