Теория игр. Оуэн (1971) (1186151), страница 10
Текст из файла (страница 10)
Допустим, что — а„~ С. Тогда существуют такие неотрицательнь!е числа р!, ..., р„, Хь ..., Х„!, что тг «-! — аы = ~~т! цетг+ ~г Лтаи для всех !', /=! ! ! а это означает, что а-! ~г Лгпт;+ аы — — — р, Я 0 для всех !. / ! Положим теперь ! = 1, ..., а — 1, ! + ~ л, ' ' '' ' ' " ! + н Л, ' Ясно, что у = (у!, ..., у„) является такой оптимальной стратегией для игрока П, что у„> О. П. б. Вычисление оптимальна»х стратегий Допустим теперь, что — а„4й С. Тогда существуют такие числа »7„..., »7, что ~д,еп ~ 0 для всех 1=1, ..., л», (2.4.8) ! ~~~~ »7»а»» ~ 0 для 1=1, ..., л — 1 (2.4.9) г ! Д»7»( — а,„) (О. » ! (2.4.!0) В силу (2.4.8) имеем йч ~ О, а по (2.4.10) не все д» равны нулю.
Поэтому можно положить 4» х.= —, »=1 ... и »»е Х47 и из (2.4.9) и (2.4.!0) непосредственно следует, что х является такой оптимальной стратегией для игрока 1, что ~~'., х»а»н> О. Предположим теперь, что п(А) = а ФО. Как и выше, построим матрицу В =(5»!), где (!»! = ам — й; доказательство дальше проводится так же, как в теореме П.4.!. П. 5. ВЫЧИСЛЕНИЕ ОПТИМАЛЬНЫХ СТРАТЕГИЙ ан ~ аг! длЯ всех 1' (2.5.1) и а»; > аи» по крайней мере для одного !. (2.5.2) Теорема П.4.1 (теорема о минимаксе) гарантирует, что каждая антагонистическая игра имеет оптимальные стратегии. К сожалению, приведенное доказательство является доказательством существования и не указывает, как следует вычислять эти оптимальные стратегии.
Мы опишем теперь методы решения простейших игр. В гл. 1П речь будет идти о более общем методе. П.5.1. Седловые точки. Простейшим является тот случай, когда существует седловая точка, т. е. когда существует элемент а»п являющийся максимальным в своем столбце и минимальным в своей строке. Тогда чистые стратегии ! и 1 (или, что равносильно, смешанные стратегии х и у, для которых х» = 1, у; = 1, а все остальные компоненты равны нулю) будут оптимальными стратегиями для игроков 1 и П соответственно. П.5.2.
Доминирование. Пусть дана матрица А; будем говорить, что »-я строка доминирует й-ю строку, если Гл. О, Антагонистические игры 48 Аналогично, будем говорить, что !'-й столбец доминирует (-й столбец„если ач Ыаи для всех ! (2.5.3) и ац~аи по крайней мере для одного !. (2,5.4) Короче, говорят, что одна чистая стратегия (представленная своей строкой или столбцом) доминирует другую чистую стратегию, если выбор первой (доминирующей) стратегии по крайней мере не хуже выбора второй (доминируемой) стратегии, а в некоторых случаях и лучше.
Отсюда следует, что игрок всегда может обойтись без доминируемых стратегий и использовать только недоминируемые стратегии. Это утверждение содержится в следующей приводимой без доказательства теореме. П53, Теорема, Пусть А — матричная игра, и пусть строки г'ь гь ..., !и матрицы А доминируются.
Тогда игрок 1 имеет такую оптимальную стратегию х, что хг = хг = ... = хг = О; кроме г ''' и того, любая оптимальная стратегия для игры, получающейся в результате удаления доминируемых строк, будет также оптимальной стратегией для первоначальной игры.
Аналогичная теорема справедлива и для доминирования столбцов; общий результат этих теорем состоит в том, что все доминируемые строки и столбцы могут быть отброшены, а это позволяет иметь дело с меньшей матрицей. П.5.4. Пример. Рассмотрим игру с матрицей Ясно, что второй столбец доминирует четвертый. Отсюда следует, что игрок !! никогда не будет использовать свою четвертую стратегию, а поэтому можно не обращать на нее внимания и рассматривать матрицу ( 1 2 г). В этой матрице третья строка доминирует первую, Удаляя ее, получаем 4 1 3 ' П. д Вычисление оптимальных стратегий 49 а в этой матрице третий столбец доминируется вторым.
Следова- тельно, исходная матрица сводится к матрице (4 !)' и нужно искать оптимальные стратегии только для малой матричной (2 Х 2)-игры. Такие игры рассматриваются в следующем пункте. П.5.5. (2 Х 2) - и г р ы. Пусть дана матричная (2 Х 2)-игра или х, (а ну, + а щ,) + х, (а„у, + амуе) = о. (2.5 5! Каждое из двух выражений в скобках в левой части (2.5.5) меньше или равно о, так как у, по предположению, является оптимальной стратегией.
Допустим, что одно из этих выражений меньше о, т. е. допустим, что пну~ + аиде < в, (2.5,6) аму1+амуе Я о. (2.5.7) Тогда, поскольку х, > 0 и х~ + хи = 1, левая часть в (2,5.5) будет строго меньше о. Отсюда следует, что оба выражения, заключенные в скобки в (2.5.5), должны быть равны о. Значит, ацу, + анде= о, (2.5.8) ам у~ + ааеуе = о. (2.5.9) Аналогично можно показать, что (2.5.!0) (2.5.11) апх, + амха — — о, амх~ + архе = в. нли в матричной форме: Аут кА=(о, о). (2.5.12) (2.5.!3) Может оказаться, что эта игра имеет седловую точку; если это так, то никакой проблемы нет.
Предположим, что игра не имеет седловой точки. Отсюда следует, что оптимальные стратегии х=(хьх,) и у=(дьу,) должны иметь положительные компоненты, Далее, если значение игры есть о, то а„х,у, + а,эх,у, + а„х,у, + амхеуэ = о, Гл. /Л Антагонистические игры Эти уравнения вместе с уравнениями х,+х,=1, У~+Уз=1 (2.5.14) (2.5.15) позволяют найти к, у и и. Действительно, если матрица А невы- рожденная, то х=оУА ', где У вЂ” вектор (1, 1). Теперь исключим о, замечая, что сумма компонент х, т. е. х7т, должна быть равна 1; отсюда получаем о1А 'а~=1, илп ! ~А-) т (2.5.16) 7А 7А — )т (2.5,!7) Аналогично А-'~г У= ~А-~ г.
(2.5.18» Если А — вырожденная матрица, то все это, конечно, лишено смысла. Но тогда легко видеть, что формулы 7А* х= —, ейГг (2.5.!9) А*те У= ~А тг (2.5.20) (где А* — присоединенная') матрица для А) дают оптимальные стратегии; заметим, что (2.5.!9) и (2.5.20) совпадают с (2.5.17) н (2.5.18), если матрица А невырожденная. Ясно также, что о=— 1А! 7А Хг (2.5.21) где !А~ — определитель матрицы А, дает значение игры как для вырожденной, так и для невырожденной матрицы А.
Объединим установленные правила в следующей теореме. П.5.6. Теорема. Если А — лгатричная (2 Х 2)-игра, не имею- и(ая седловой точки, то ее единственные оптилеальные стратегии и ') Ее алементы равны соответствующем алгебранческнм лополненням ллн трансноннрованной матрицы. — Прим. нерее.
!!. д Вычисление онтимальнмх стратегий (2.5.23) значение определяются формулами х = —. тл' (2.5.22) гл*тт ' л гт у !ятт о —— 1А1 (2.5.24) тг> где А' — присоединенная матрица для А, 1А( — определитель матрицы А, ! — вектор (1, 1). П.5.7. П р и м е р. Решить матричную игру — >)' Легко проверить, что эта йгра не имеет седловой точки. Далее, присоединенная матрица для А есть А'-( и !А(= 2, УА" =(3,!); А*!т =(2,2) и ХА*Ут = 4.
Таким образом, х =(е/и '/е), у =('/ъ '/т), о = '/т, Можно проверить, что эти стратегии х и у действительно гарантируют выигрыш '/,. П.5.8, (2Хп)- и (тХ2)-игры. Следующие простейшие игры, которые можно решить,— это игры, в которых один из игроков имеет только две стратегии ((2 Х п)- или (т Х 2)-игры). Мы рассмотрим здесь (2 Х и)-игры; аналогичный анализ может быть проведен и для (пт Х 2) -игр. Задача игрока ! состоит в максимизации о (х) = пип (а „.х, + а,тх,).
! Так как х~ = 1 — хм мы имеем о(х) =ппп((а,! — аы) хе+а>!). ! Таким образом, о(х) является минимумом и линейных функций одной переменной хт, можно вычертить графики этих функций и затем максимизировать их минимум о(х) графическими методами. П.5.9. П р и мер.
Рассмотрим игру с матрицей 2 3 1 5 Нетрудно построить графики функций (а„— ап)хе+ а>в если заметить, что они должны проходить через точки (О, аи) и (1, аа!). 52 Гл. П, Антагонистические игры Жирная ломаная линия представляет функцию о(х). Высшая точка этой линии Х находится на пересечении прямых, соответствующих второму и третьему столбцам. Абсцисса этой точки равна '/ь а ордината "/ь Следовательно, х = ('/ь'/з) и о = "/ь Эти величины могут быть вычислены также при помощи формул 6 (2.5.22) и (2.5.24) для (2Х2)-мат- рицы, состоящей из второго и 5 третьего столбцов исходной мат- 4 4 рицы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
