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


[Старт] [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] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [ 220 ] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]


220

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

Оценка сходимости описанного процесса, данная Шапиро [1], показывает, что он сходится весьма медленно: погрешность в определении

1

значения п X етг-игры за t шагов имеет порядок t nm 2.

5. Как пишет Гейл [1], «одним из самых удивительных событий, связанных с появлением современной теории линейных экономических моделей, явилось одновременное, но независимое развитие теории линейного программирования, с одной стороны, и теории игр, с другой, и выявившаяся затем тесная связь между этими двумя предметами». По свидетельству Данцига [1], на связь между линейным программированием и теорией матричных игр указывал еще Дж. фон Нейман в 1947 г. Затем этими вопросами занимались Гейл, Кун и Таккер [1]. В наиболее естественной форме эквивалентность пары двойственных друг другу задач линейного программирования и матричной игры дается теоремой, принадлежащей Данцигу и Брауну и опубликованной Данцигом [2].

Рассмотрим пару двойственных задач линейного программирования

АХТВТУ YAC,

CXT->max, 75r-min

(ХО), (УО).

Для того чтобы векторы Х° и У0 являлись оптимальными решениями этих задач, необходимо и достаточно, чтобы вектор

(tX\ tY°, t)

был оптимальной стратегией одного из игрокоз в игре с матрицей

О -А Вт\ Ат О -Ст\ -В с о /

(поскольку эта матрица кососимметрична, неважно, о каком именно игроке идет речь), причем t > 0.

Эквивалентность решения матричной игры решению задач линейного программирования позволяет применять к решению первых все приемы, разработанные для решения вторых. В частности, оптимальные стратегии в матричных играх можно находить при помощи известного симплекс-метода. Весьма практичный способ решения матричной игры при помощи линейного программирования предложил Таккер [1].

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



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

Один такой пример был исследован фон Нейманом в статье [2]. Он состоит в следующем.

Пусть дана т х -матрица А = \\ аи . Игрок I имеет своими стратегиями клетки (ij) этой матрицы, а игрок II -ее строки (i) и столбцы (/). Если игрок I выбирает клетку (ij), то выигрыш его будет равен - при выборе игроком II строки i или столбца / и будет равен нулю в противном случае. В результате мы получаем матричную тп х (т + ?г)-игру.

Все игры такого типа можно интерпретировать следующим образом. Пусть игрок I «прячется» в одну из клеток матрицы А, а игрок II пытается угадать строку или столбец, на котором лежит эта клетка. Если игрок II угадывает, то он получает от игрока I число, стоящее в выбранной клетке матрицы.

Эта игра эквивалентна задаче линейного программирования, состоящей в максимизации суммы

2 VijXij 1

г, j

при неотрицательных х, подчиненных ограничениям

2 xtjl, 7 = 1, п,

2 хи<: 1, i = 1, ..., т.

Такая задача линейного программирования известна под названием «задачи о назначениях»: распределить оптимальным образом т лиц по п работам, если эффект, которого добивается лицо i на работе /, равен atj.

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

Получившаяся игра оказывается матричной, если исходные многогранники стратегий задаются своими вершинами. Если, однако, эти многогранники заданы своими гранями, то игра по-прежнему остается конечной антагонистической (т. е. матричной), но для того, чтобы выписать ее матрицу выигрышей в явном виде, необходимо потратить известные усилия, часто весьма значительные. Поэтому встает вопрос о решении полиэдральных игр без предварительного их приведения к традиционной матричной форме. Очевидно, мы здесь сталкиваемся с частным случаем проблемы, затронутой в II.4.2.

Связь матричных игр с линейным программированием позволяет решить поставленный вопрос, что и было сделано в работах Данцига [31, Чарнса [11 и Вульфа [1].



Пусть определяющая функцию выигрыша игры билинейная форма имеет т х гг-матрицу А (тем самым мы предполагаем, что многогранники стратегий игроков лежат соответственно в m-мерном и га-мерном векторных пространствах), а многогранники стратегий задаются своими гранями, т. е. системами неравенств вида ВХТ rg 6Г, YC с (здесь В есть к х ш-матрица, С - пХ /-матрица, а Ъ и с суть соответственно к- и Z-векторы; к и I, очевидно, означают числа граней в многогранниках стратегий). Тогда оптимальная стратегия игрока I получается как часть X оптимального решения (X, V) задачи линейного программирования

ВХТ г 5&г,

-AXT + CVT = 0,

и аналогично оптимальная стратегия игрока 2 -как часть У оптимального решения (У, U) задачи линейного программирования

YCc,

-YA-j-UB = 0,

£/ >0.

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

В качестве простого, но принципиально важного примера укажем на матричную игру, в которой игрок 1 по тем или иным соображениям, известным противнику, играет в любой своей смешанной стратегии первую чистую стратегию не реже, чем вторую, вторую не реже, чем третью, и т. д. Это значит, что всякая доступная для него смешанная стратегия X = . . ., хп) должна удовлетворять условиям

xt х2 .. . хп.

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

§ 2. БЕСКОНЕЧНЫЕ АНТАГОНИСТИЧЕСКИЕ ИГРЫ

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] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [ 220 ] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]