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


[Старт] [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]


227

В литературе рассматривалось довольно много игр такого рода. Одной из наиболее общих представляется схема рекурсивной игры, введенная Эвереттом [1].

Партия рекурсивной игры состоит из последовательности элементарных (например, матричных) игр, причем исходом каждой элементарной игры является снова элементарная игра либо окончание всей игры, сопро- * вождающееся расплатой. Говоря точнее, если в какой-то момент игралась элементарная игра Г\ причем игроки выбрали стратегии i, /, то с некоторыми определенными вероятностями (зависящими от выбранных стратегий) в следующий момент будет играться некоторая элементарная игра Т1 из того же набора или же вся партия закончится. Оказывается, если элементарные игры имеют значения, то и рекурсивные игры имеют значения в стационарных стратегиях и тем самым е-оптимальные стационарные стратегии при любом г > 0.

6, Близкими к рекурсивным играм являются игры на выживание, исследованные Милнором и Шепли [1]. В таких играх в каждый момент времени игроки обладают соответственно ресурсами riiR - r (0 <<**<#) и играют в матричную игру аи \\. Выигрыши в этой игре присоединяются к ресурсам игроков, с которыми они вступают в игру в следующий момент. Игра заканчивается при исчерпании всех ресурсов одного из игроков, причем победитель получает единицу (размерность которой, вообще говоря, никак не связана с размерностью ресурсов).

Если такая игра имеет значение, то оно является функцией начального количества ресурсов г0 у игрока 1, которая есть монотонное решение функционального уравнения ср (г) = val Ф (г + atj) при граничных условиях ф (г) = 0 для г 0 и ф (г) = 1 для г R.

Обобщение этой игры получается при переходе от матричных игр к произвольным бескоалиционным играм или, что, по существу, близко, к векторным ресурсам. Такого рода игры рассматривал И. В. Романовский [1].

Сходными с играми на выживание являются игры на истощение, о которых см. статью Исбелла и Марлоу [1].

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

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

- = fj(x{, . . ., хп\ t, ф, г)), / = 1, .. ., п. (5)

Здесь переменные Xj называются переменными состояния (или фазовыми координатами), а ф и г) - управляющими переменными (соответственно для первого и второго игрока), которые выбираются игроками из некоторого заранее заданного множества функций, зависящих от временного параметра t и от переменных состояния. Если выбор функций ф и г) приводит к разрешимости системы дифференциальных уравнений, то партия игры реализуется в виде некоторой траектории в множестве А. На множестве всех траекторий определяется функция выигрыша. Обычно считается, что игра заканчивается с выходом траектории на границу А,



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

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

Типичным примером дифференциальной игры является игра «преследования», в которой фазовые координаты определяют положения (а иногда и скорости) нескольких объектов, из которых одни называются преследователями, а другие - преследуемыми. Каждый игрок управляет координатами подчиненных ему объектов. Игра заканчивается в заранее указанный момент, причем выигрыш преследователей определяется «близостью» преследующих объектов к преследуемым в момент окончания игры. (Первая математическая постановка игры преследования принадлежит Вармусу [1].)

В качестве другого примера можно указать на игру «перетягивания»,, в которой два игрока прилагают к некоторой материальной точке силы, стремясь придать ей к концу игры желательные фазовые координаты. Очевидно, игры преследования можно рассматривать как частный случай игр «перетягивания» (в соответствующем фазовом пространстве).

Систематическое рассмотрение как отдельных примеров игр такого рода, так и общих теоретических соображений было предпринято Айзек-сом еще в начале 50-х годов. Его первые работы были изложены в неопубликованных Меморандумах корпорации РЭНД в 1954 и 1955 гг., а подробное изложение полученного материала было напечатано в виде монографии [1]. Свои результаты Айзеке фактически получает применением принадлежащего Беллману метода динамического программирования и поэтому сталкивается со всеми теми трудностями, которые этому методу присущи. Дальнейшие результаты на этом пути получил Л. А. Петросян [1, 2].

Более тонкий и мощный подход содержится в работах Л. С. Понтря-гина [1]. Этот подход основан на рассуждениях, близких к тем, которые приводят к принципу максимума. При этом решение дифференциальной игры сводится к решению системы обыкновенных дифференциальных уравнений.

Предпринимались попытки свести решение дифференциальной игры к решению игры с дискретным временем с последующим предельным переходом. Здесь следует назвать работы Скарфа [1] и Флеминга [1, 2, 3].

Обстоятельные исследования дифференциальных игр, основанные на использовании аппарата и результатов вариационного исчисления, были проведены Флемингом и Берковицем [1] и Берковицем [1].

Весьма подробные обзоры работ по теории дифференциальных игр содержатся в статьях Симаковой [1], а также Зеликина и Симаковой [1L

Октябрь 1967 г.



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

Айзеке (IsaaksR.)

[1] Differential games, J. Wiley, N.Y., 1965. Рус. пер.: Дифференциальные игры, «Мир», М., 1967. Ауман (A u m a n n R. J.)

[1] Linearity of unrestrictedly transferable utilities, Nav. Res. Log. Quart. 7 (1960), № 3, 281-284.

[2] A survey of cooperative games without side payments, Сборн. [14], 3-27. Ауман, Машлер (Aumann R. J., Maschler M.)

[1] An equilibrium theory for тг-person games cooperative, Amer. Math. Soc. Notices 8 (1961), 261.

[2] The bargaining set for cooperative games, Сборн. [13], 443-476. / "

Бак (Buck R. С.)

[1] Preferred optimal strategies, Proc. Amer. Math. Soc. № 2 (1958), 312-314. Рус. пер.: Предпочтительные оптимальные стратегии, Сборн. [12], 133-136. Б аут он (В о u t о п С. L.)

[1] Nim, a game with a complete mathematical theory, Ann. Math., Princeton 2, № 3 (1902), 35-39. Баше де Мезирак (Bachet de Meziriac)

[1] Problemes plaisants et delectables, qui se font par les nombres, Lyon, 1612. Б e p ж (В e r g e C.)

[1] Theorie generale des jeux a n personnes, Paris, Gauthier-Villars, 1957. Рус. пер.: Общая теория игр нескольких лиц, Физматгиз, М., 1961. Берковиц (Berkovitz D.)

[1] A variational approach to differential games, Сборн. [13], 127-174. [2] A differential game without pure strategy solutions on an open set, Сборн. [13], 175-194.

Берковиц, Флеминг (Berkovitz D., Fleming W. H.)

[1] On differential games with integral payoff, Сборн. [6], 413-435. Бертран (Bertrand J.)

[1] Calcul des probabilites, Paris, 1888. Б e p ч (Birch B. J.)

[1] On games with almost complete information, Proc. Cambridge Phil. Soc. 51, № 2 (1955), 275-287. Рус. пер.: Об играх с почти полной информацией, Сборн. [16], 72-93. Блекуэлл, Гиршик (Blackwell D., Girshick М.~ А.)

[1] Theory of games and statistical decisions, London, 1954. Рус. пер.: Теория игр и статистических решений, М., ИЛ, 1958. Бондарева О. Н.

[1] Некоторые применения методов линейного программирования и теории кооперативных игр, Проблемы кибернетики, 10 (1963), 119-139. Боненбласт, Карлин, Шепли (Bohnenblust Н. F., Karl in S., S h a p.l е у L. S.)

[1] Solutions of discrete two-person games, Сборн. [1], 51-72. Рус. пер.: Решение

дискретных игр двух лиц, Сборн. [10], 17-44. Борель ( В о г е 1 Е.)

[1] La theorie du jeu et les equations integrales a noyau symetrique, Comptes Rendus

de PAcademie des Sciences 173 (1921), 1304-1308. Англ. пер.: The theory of

play and integral equations with skew symmetric kernels, Econometrica 21, № 1

(1953), 97-100.

[2] Sur les jeux ou interviennent lhasard et lhabilete des joueurs, Theorie des probabilites, Paris, 1924, 204-224. Англ. пер.: On games that involve chance and the skill of the players, Econometrica 21, 1 (1953), 101-115.

[3] Sur les systemes de formes lineaires a determinant symetrique gauche et la theorie generale du jeu, Comptes Rendus de lAcademie des Sciences 184 (1927), 52-53.

[Старт] [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]