назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [ 29 ] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90]


29

венства, описьюающего ограничения прямой задачи, должно быть

(X-aU)A=XA+aUAB, а на основании (25.19) и неотрицательности вектора X

X + aU 0.

Следовательно, X -aUявляется одним из допустимых решений сформулированной прямой задачи. Но при неограниченном возрастании а произведение

(X + af/)C = XC+af/C

также неограниченно возрастает. Таким образом, в этом случае прямая задача не имеет оптимального решения.

Ввиду того, что левая часть (25.13) может стать больше любого наперед заданного числа, не найдется и такого Y, для которого это неравенство выполнялось бы при всехХ Следовательно, и двойственная задача не имеет даже допустимого (и тем более оптимального) решения.

Если предположить, что BV < О, то аналогичные рассуждения покажут отсутствие оптимального решения у двойственной задачи и отсутствие допустимого решения у прямой.

3) Пусть теперь X н У - оптимальные решения нашей пары двойственных задач. Возьмем / и Z в соответствии с (26.17) и (26.18). Очевидно, Z> OhZJ = 1, так что Z есть стратегия в игре Г. Кроме того,

О -АТ

А О -В

в о

= Г(ГЛ-С,-Х4+Д ХС-УБ).

На основании (25.9), (25.7) и (25.13) все компоненты вектораZAf неотрицательны, т.е. не меньше значения игры. Поэтому Z есть оптимальная стратегия рассматриваемой игры, и требуемое установлено. Теорема доказана. □

Из нее следует, что любой метод решения задач линейного программирования может быть без труда приспособлен для решения матричных игр.

§ 26. СИММЕТРИЯ в ИГРАХ

26.1. При анализе и решении игр, в том числе матричных, существенную пользу может принести учет тех или иных комбинаторных свойств игр. Одним из них является симметрия игры, т.е. наличие у нее зеркального автоморфизма (см. п. 1.6).

Для симметричных игр отпадает надобность в специальном нахождении значения игры: оно согласно п. 5.5 равно нулю. Также согласно п. 5.5 для таких игр достаточно находать оптимальные стратегии лишь для одного из игроков.

Вместе с тем класс симметричных игр можно считать универсальным в том смысле, что по всякой игре Г можно построить такую симметричную игру Г, что решение игры равносильно решению игры Г. Именно, каждое решение игры Г получается элементарным образом из некоторого



решения симметричной игры Г, а применение этого процесса переработки к любому из решений игры дает некоторое решение игры Г.

Процесс переработки игр в симметричные им назьшается симметризацией. Мы опишем здесь один прием симметризации. Другой, принципиально иной вариант симметризации будет приведен в п. 26.7. Оба эти варианта симметризации в действительности применимы к произвольным антагонистическим играм, но будут сформулированы и доказаны только для матричных игр.

26.2.Рассуждения предьщущего параграфа фактически уже содержат некоторый прием симметризации игры. В самом деле, согласно сказанному в пп. 25.1 - 25.2 решение всякой матричной игры может быть сведено к решению пары двойственных друг другу задач линейного программирования. А на основе сказанного в пп. 25.3 - 25.6 решение такой пары задач сводится к решению некоторой симметричной игры. Опишем в явном виде последовательное проведение этих двух приемов.

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

Именно, пусть Z - мера на произведении х X у, где х = { , . . . , } и у ={ ji,..., j„ }. Ее можно описать системой неотрицательных чисел ij=Z(xi,yj), XjGx, j/Gy, составляющих в сумме елтацу- Проекцией меры Z на сомножитель х назьшается мера X на х, для которой

а ее проекцией на у - мера Уна у, для которой

26.3.Опишем следующий прием симметризации матричных игр. Пусть Г = < X, у, Я > = - матричная т X «-игра. Положим

Г=<хХу,уХх,Я>=Г, где

Нфс. У(Л )) = у) - Н(х \у),

т.е. есть тп X дгт-матрица- = \\bJ, II (/, = 1,.. . ,т;/;/ = 1,. .. ,«), причем = aij - aij. Симметричность игры Г* очевидна.

Симметризацию игры Г игры Г можно интерпретировать следующим образом. Пусть два лица, А и В, разыгрьшают одновременно две партии игры Г, причем в одной партии А выступает в роли игрока 1, а в другой партии - в роли игрока 2, тогда как Б выступает в противоположных ролях. Тем самым множество всех стратегий А в этой паре игр есть множество всех пар вида (х, у), где х G х G у, т.е. декартово произведение х X у. Множеством всех стратегий Б будет по тем же причинам произведение у X х. Общим вьшгрышем А в обеих партиях является, очевидно, алгебраическая сумма его вьшгрышей в этих партиях. Так описанные множества стратегий и функция вьшгрыша А, очевидно, и задают игру .



26.4.Во введенных обозначениях имеет место следующая теорема. Теорема. Пусть Z - смешанная стратегия игрока 1 в игре Г, а X

и Y - ее проекции на хи у. Тогда ZG § (А)= S{A) равносильно тому, чтобы былохе 8 (A)uZe(A).

Доказательство. Включение Z G § (А) равносильно тому, что при любой чистой стратегии (у, х) = (/, /) игрока 2 в Г* имеет место соотношение Я (Z, (у, х)) = Z5.(y/) 0. Это в свою очередь означает, что при любых /Gx и /Gy будет

2 ..,(a,j-a,y)= 2 Г,у« - 2 ,ау = hiW

= 2(2 r,y0«i7-(f=

= 2Г,-,у -IjVjati =XA,j-Ai,Y 0.

Bee это можно переписать какXv4.уv4. при любых / G х, G у. Но согласно теореме п. 15.10 последнее означает, что X G § (Л) и FG ffiA).

Требуемая равносильность доказана. □

26.5.Можно указать еще на один способ симметризации матричных игр, основанный на иной идее.

Пусть Г = < X, у,Я) = - матричная т X «-игра. Возьмем какой-нибудь объект в , не являющийся стратегией какого-либо из игроков в , и

ПОЛОЖИМ

r=<xUyU(9, xUyU6>, Н) = Т{А), где значения функции Н описьшаются следующей таблицей:

-Н{х, у)

Щу, X)

(26.1)

т.е. матрица А есть (т + w + 1) X (т + « + 1)-матрица: О А -/I

(26.2)

Игра Т{А), очевидно, является симметричной. В терминах исходной игры игра Т{А ) поддается простой интерпретации. Пусть два лица, А и Б, договариваются о разыгрьшании партии игры следующим образом. Сначала они независимо друг от друга выбирают либо свои роли, игрока 1 или игрока 2 в игре Г, либо же нейтральную "стратегию неучастия" в. При этом если А и В выбирают различные роли, то они после этого фактически разыгрьшают игру в соотвегствии с выбранными ролями. Если А вы&1рают роль игрока 1, а Б - стратегию , то А вьшгрывает у Б единицу; если А выбирает роль игрока 2, а Б - стратегию 0 , то А проигрывает единицу; если стратегию Q выбирает А, то получается симметричная карти-

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [ 29 ] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90]