Матрица выигрышей. Представление игр в нормальной форме 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Матрица выигрышей. Представление игр в нормальной форме



Игрой в нормальной форме называется совокупность , где N - множество всех игроков; Ui - множество стратегий i— го игрока; gi - функция выигрыша i — го игрока, которую он стремится максимизировать.

Обычно игроков нумеруют в произвольном порядке от 1 до n (n — число игроков), поэтому N={1,2,...,n}. Стратегия i— го игрока для игры в нормальной форме сводится к одноактному выбору любой точки из множества Ui. Функция выигрыша ставит в соответствие каждому элементу и=(u1,...,un) из множества называемому исходом или ситуацией игры, действительное число. Таким образом, gi есть однозначное отображение множества U→R.

Исходная постановка игры в нормальной форме не предполагает никакой дополнительной информации у игроков о действиях друг друга. Поэтому можно считать, что все игроки одновременно и независимо осуществляют выбор своих стратегий, т.е. элементов ui ∈ Ui. В результате складывается ситуация и, однозначно определяющая выигрыши всех игроков g1(u),...gn(u).

Рассмотрим парную игру с игроками А и В. Пусть игрок А имеет т стратегий ={А1, A2,..., Ат}, а (противник) игрок В - п стратегий ={В1, B2,..., Вп}. Натуральные числа т и п в общем случае никак не связаны между собой.

Если каждый из игроков А и В сознательно определенным образом выбирает стратегии Аi и Вj соответственно, то сложившаяся ситуация (в чистых стратегиях) (Аi,Bj) однозначно определяет выигрыш игрока А, выражающийся действительным числом аij, которое одновременно является и проигрышем игрока В. А число (- aij) выражает проигрыш игрока А и выигрыш игрока В. Если число aij отрицательно, то в принятой нами формализованной терминологии оно будет представлять отрицательный выигрыш игрока А, а по сути - его проигрыш. Числа аij - это значения функции выигрыша FA игрока A: FA(i, j) = FA(Ai, Bj) = аij. Ходы игроков с сознательным выбором одной из возможных своих чистых стратегий называют иногда личными ходами.

Выигрыши aij, i = 1,..., m, j = 1,..., n, можно расположить в виде матрицы, номера строк которой соответствуют номерам стратегий игрока А, а номера столбцов - номерам стратегий игрока В.

Bj
A =
Ai

B 1 B 2 Bn
A 1 a 11 a 12 a 1 n
A 2 a 21 a 22 a 2 n
Am am 1 am 2 amn

Матрица А называется матрицей выигрышей игрока A.

Обозначим через bij значения функции выигрыша FB игрока В, т. е. FB(j, i) = FBj, Ai) = bji, j = 1,..., n, i = 1,..., т. Тогда матрица выигрышей игрока В будет иметь вид

Ai Bj
B =

A 1 A 2 Am
B 1 b 11 b 12 b 1 n
B 2 b 21 b 22 b 2 n
Bn bn 1 bn 2 bnm

Если рассматриваемая игра - антагонистическая (т.е. с нулевой суммой выигрышей), то функции выигрышей FA и FB игроков А и В связаны между собой равенством F B(Bj, Ai) = - FA(Ai, Bj), i = 1, …, m, j = 1,..., n и, следовательно,

bji = FB(Bj, Аi) = -FA(A i , Bj) = -аij, i = 1,..., т, j = 1,..., n.

Эти равенства означают, что матрица выигрышей В игрока В является противоположной транспонированной матрице A: B = - A T.

Таким образом, матрица В вполне определяется матрицей А. Матрицу А также называют матрицей игры, или платежной матрицей. Матрица А имеет размер т × п, где первая компонента размера т указывает на число строк (т.е. число стратегий игрока А), а вторая п - на число столбцов (число стратегий игрока В). Поэтому часто такую игру называют т × п - игрой.

Отметим, что матрица игры существенно зависит от упорядочений множеств и стратегий игроков А и В. При другой нумерации стратегий этих множеств мы получим, вообще говоря, другую матрицу игры. Так что одна и та же игра может описываться различными матрицами. Но при всевозможных матрицах игры функция FA выигрыша игрока А остается одной и той же, определенной на декартовом произведении × с множеством значений в множестве действительных чисел R. Это замечание относится и к функции FB выигрыша игрока В.

Всякую конечную антагонистическую игру можно привести к матричной форме.

Матрица игры А формируется в зависимости от значений функции выигрыша FA, которая может задаваться таблично, аналитически (в виде формулы) или словесно-описательным способом.

Максиминный принцип игры

Рассмотрим матричную т × п - игру с игроками А и В,в кото­рой игрок А обладает т чистыми стратегиями ={А1,..., Ат}, a игрок В - п чистыми стратегиями ={В1,..., Вп}. Значения функции выигрыша игрока A обозначим через аij,т. е. FA (i, j) = аij, и тогда матрица игры будет иметь вид

Bj
A =
Ai

B 1 B 2
(1)
Bn

A 1 a 11 a 12 a 1 n
A 2 a 21 a 22 a 2 n
Am am 1 am 2 amn

Перед игроком А стоит задача выбора чистой стратегии из множества , эффективной в определенном смысле, в результате применения которой он получит максимально возможный гарантированный выигрыш. Если игрок А выбрал стратегию Аi (i =1, …, m),, то его выигрышем может быть один из выигрышей

аi 1, аi 2, …, аin,

расположенных в i -й строке матрицы выигрышей, в зависимости от выбранной игроком В стратегии. Предполагая поведение игрока А крайне осмотрительным, необходимо считать, что игрок В сыграет наилучшим для себя образом и на выбор игроком А стратегии Аi выберет ту стратегию Bj, при которой выигрыш игрока А окажется минимальным. Обозначим минимальный среди выигрышей аi 1, аi 2, …, аin через α i:

и назовем его показателем эффективности стратегии Аi. Продолжая действовать разумно, игрок А должен выбрать ту стратегию, которая максимизирует показатель эффективности, т.е. для которой число α i максимально. Если обозначить это максимальное число через α:

то по формуле

Описанный принцип выбора эффективной стратегии игроком А называется максиминным принципом, а выигрыш α - максимином.

Пусть игрок А выбрал максиминную стратегию а игрок В - какую-то произвольную стратегию Bl, l = 1,..., п. Тогда в создавшейся ситуации ( Bl) выигрыш игрока А в чистых стратегиях будет для которого в силу равенств и будет справедливо неравенство

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

 

Минимаксный принцип игры

Рассмотрим матричную т × п - игру с игроками А и В,в кото­рой игрок А обладает т чистыми стратегиями ={А1,..., Ат}, a игрок В - п чистыми стратегиями ={В1,..., Вп}. Значения функции выигрыша игрока A обозначим через аij,т. е. FA (i, j) = аij, и тогда матрица игры будет иметь вид

Bj
A =
Ai

B 1 B 2
(1)
Bn

A 1 a 11 a 12 a 1 n
A 2 a 21 a 22 a 2 n
Am am 1 am 2 amn

 

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

а 1 j , а 2 j , …, аmj, (1)

выигрышей, стоящих в j -м столбце матрицы выигрышей, в зависимости от того, какой стратегии будет придерживаться игрок А. Но так как игрок В предполагает, что игрок А играет наилучшим для себя образом, то выигрышем игрока А будет максимальное из чисел (1); обозначим его через βj:

и назовем показателем неэффективности стратегии Вj. Таким образом, для любой стратегии Bj игрока В наибольший его проигрыш равен β j. В интересах игрока В - выбрать стратегию с минимальным показателем неэффективности. Наименьшее из чисел (2) обозначим β:

Отсюда в силу формулы (2) получим для β выражение:

Критерий выбора эффективной стратегии для игрока В называется минимаксным принципом, а выигрыш β называется минимаксом.



Поделиться:


Последнее изменение этой страницы: 2017-01-27; просмотров: 931; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.222.175.73 (0.134 с.)