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


[Старт] [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] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


41

Xl > О, /= 1,

где V является значением игры.

Для второго игрока задача записывается в виде

min max X а..у.,

1</т=1 IJ J п

У]> 0,7=Е>у = 1.

Запишем промежуточное соотношение

пппп

Тогда задача принимает вид

minv(5.10)

X a..yj<v, / = l,2,...,/w,

> 0, y= 1,

где V является значением игры.

Отметим, что задача для второго игрока (5.10) является двойственной к задаче для первого игрока (5.9). Задача для второго игрока может быть решена, например, стандартным симплекс-методом, а для первого игрока - двойственным симплекс-методом. Выбор метода определяется тем, какая из задач имеет меньше ограничений, что в свою очередь зависит от числа чистых стратегий каждого из игроков.

5.2.9. Определение бесконечной антагонистической игры. Естественным обобщением матричных игр являются бесконечные антагонистические игры (БАИ), в которых хотя бы один из игроков имеет



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

Напоминание. Пусть Е- некоторое множество вещественных

Естественным обобщением матричных игр являются бесконечные антагонистические игры, в которых

стратегий

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

чисел. Если существует число у та-хотя бы 0ДШ1 из игроков имеет бес- ое, что х < при всех хеЕ (при конечное количество возможных

этом у не обязательно принадлежит

£), то множество Е называется ограниченным сверху, а число у называется верхней границей множества Е. Аналогично определяется ограниченность снизу и нижняя граница множества Е. Обозначаются верхняя и нижняя границы соответственно через sup £ и inf £ соответственно.

Пример. Пусть множество Е состоит из всех чисел вида ~, « = 1,2,...

Тогда множество Е ограниченно, его верхняя грань равна 1, а нижняя О, причем О £, а 1 е Е.

Для дальнейшего изложения теории игр этого класса введем определения и обозначения: [0; 1] - единичный промежуток, из которого игрок может сделать выбор; х - число (стратегия), выбираемое игроком \\у - число (стратегия), выбираемое игроком 2; M(x, у) - выигрыш /-го игрока; G {XJMxMi)- игра двух игроков с ненулевой суммой, в которой игрок 1 выбирает число х из множества X, игрок 2 выбирает число у из множества 7, и после этого игроки 1 и 2 получают соответственно выигрыши Мх{х, у) и М2(х, у). Пусть G (X, Y,Kf) - игра двух игроков с нулевой суммой, в которой игрок 1 выбирает число х, игрок 2 - число у, после чего игрок 1 получает выигрыш М(х, у) за счет второго игрока.

Большое значение в теории БАИ имеет вид функции выигрышей М{х, у). Так, в отличие от матричных игр не для всякой функции Л/(х, у) существует решение. Будем считать, что выбоо огределенного числа иг-



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

= max inf М{х, у) или = max min М{х, у\

X уX у

а чистой верхней ценой игры величину

Fj = min sup М(х, у) или = min max М(х, у).

Ухух

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

Естественно считать, что если для какой-либо бесконечной игры величины Fl и Vi существуют и равны между собой (Fi = F2 = F), то такая игра имеет решение в чистых стратегиях, т.е. оптимальной стратегией игрока 1 есть выбор числаХо е Хи игрока 2 - числа>о е У, при которых Мо, У о) = F, в этом случае V называется ценой игры, а (х, у о) - седловой точкой в чистых стратегиях.

Пример. Игрок 1 выбирает число х из множества Х= [0; 1], игрок 2 выбирает число> из множества 7= [0; 1]. После этого игрок 2 платит игроку 1 сумму

М{х,у) = 2х-у\

Решение. Поскольку игрок 2 хочет минимизировать выигрыш игрока 1, то он определяет

min(2x-/) = 2x-1,

Т.е. при этому = 1. Игрок 1 желает максимизировать свой выигрыш и поэтому определяет

max(minM(x,>)) = max(2x -1) = 2 -1 = 1,

jcG X YjcG X

который достигается при х = 1.

Итак, нижняя цена игры равна Fi = 1. Верхняя цена игры

V, = min(min(2x -/)) = min(2- д;) = 2-1 = 1,

ДбУ XGxySY

Т.е. в этой игре Fi = F2= 1. Поэтому цена игры F= 1, а седловая точка

(1;1).

[Старт] [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] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]