Игры двух лиц с произвольной суммой

Бескоалиционные игры.

В конечной бескоалиционной игре двух игроков (КБИДИ)каждый из них делает один ход – выбирает одну стратегию из имеющегося у него конечного числа стратегий, и после этого он получает свой выигрыш согласно определённым для каждого из них матрицами выигрышей. Другими словами КБИДИ полностью определяется двумя матрицами выигрышей для двух игроков. Поэтому такие игры называются биматричными. Пусть у игрока 1 имеется m стратегий, i = , у игрока 2 имеется n стратегий, j = . Выигрыши игроков 1 и 2 соответственно задаются матрицами

А = , В =

Будем по-прежнему считать полный набор вероятностей x = (x₁,..., x_m) применения 1 игроком своих чистых стратегий смешанной стратегией игрока 1, и у = (y₁,..., y_n) – смешанной стратегией игрока 2. тогда средние выигрыши игроков 1 и 2 соответственно равны

Ситуация равновесия для биматричной игры составляет пару (x,y) таких смешанных стратегий игроков 1 и 2, которые удовлетворяют неравенствам:

или

Для определения ситуаций равновесия необходимо решить систему неравенств (1) и (2) ( и ) относительно неизвестных x = (x₁,..., x_m) и у = (y₁,..., y_n) при условиях

, , x_i ³ 0 (i = ), y_j ³ 0 (j = ).

Теорема (Нэша). Каждая биматричная игра имеет по крайней мере одну ситуацию равновесия.

В качестве примера рассмотрим случай, когда каждый игрок имеет две чистые стратегии. В этом случае матрицы A и B равны:

A = , B = .

Смешанные стратегии для игроков 1 и 2 имеют вид:

(x, 1– x), (y, 1– y) 0 £ x £ 1; 0 £ y £ 1,

а средние выигрыши равны:

E₁(A,x,y) = xA = (x; 1- x) =

= (a₁₁ – a₁₂ – a₂₁ + a₂₂) xy + (a₁₂ - a₂₂) x + (a₂₁ - a₂₂) y + a₂₂.

E₂(B,x,y) = xB = (x; 1- x) =

= (b₁₁ - b₁₂ - b₂₁ + b₂₂) xy + (b₁₂ - b₂₂) x + (b₂₁ - b₂₂) y + b₂₂.

Условия и будут выглядеть

£ E₁(A,x,y),

(x; 1- x) £ E₂(B,x,y),

или

Преобразовав (3) и (4), получим

(1- x) y + (1- x) £ 0

(a₁₁ - a₁₂ - a₂₁ + a₂₂) xy + (a₁₂ - a₂₂) x ³ 0

или

Т. о., множество всех приемлемых стратегий для игрока 1 удовлетворяет условиям (5) и (6), 0 £ x £ 1; 0 £ y £ 1. Чтобы найти x рассмотрим 3 случая:

1. Если x = 0, то (6) справедливо " y, а (5) имеет вид:

a₁y - a₂ £ 0.

2. Если x = 1, то (5) справедливо " y, а (6) имеет вид:

a₁y - a₂ ³ 0.

3. Если 0 < x < 1, то (5) разделим на (1 - x), а (6) – на x и получим

Итак, множество К решений системы (5) – (6) состоит из

всех ситуаций вида (0; y), если a₁y - a₂ £ 0; 0 £ y £ 1;

всех ситуаций вида (x; y), если a₁y - a₂ = 0; 0 < x < 1;

всех ситуаций вида (1; y), если a₁y - a₂ ³ 0; 0 £ y £ 1.

Если a₁ = a₂ = 0, то решением является xÎ[0; 1], yÎ[0; 1], т. к. все неравенства (7) – (8) выполняются при всех x и y, т. е. множество приемлемых для игрока 1 ситуаций покрывает весь единичный квадрат.

Если a₁ = 0, a₂ ¹ 0, то выполняется либо (7), либо (8), и поэтому решением является либо x = 0, либо x=1 при 0 £ y £ 1 (приемлемой стратегии в игре не существует).

Если a₁ > 0, то из (7) получаем решение

x = 0; y £ := a,

Из (8) следует ещё решение x = 1, y ³ a, из (9) следует ещё решение

0 < x < 1, y = a.

Если a₁ < 0, то решение следующее:

x = 0, y ³ a; x = 1, y £ a; 0 < x < 1, y = a.

При этом необходимо учитывать, что дополнительно должно быть

0 £ y £ 1.

Геометрически это выглядит следующим образом:

·

y ¥ y ¥ y ¥

1 1 1

a₁>0 a₁>0 a₁>0

a<0 a=0 1< a<1

(x, a)

0 1 x 0 1 x 0 1 x

– ¥ – ¥ – ¥

·

·

·

y ¥ y y

¥ ¥

1 a₁>0 1 a₁>0 1 a₁< 0

(x, 1) a=1 a >1 (x, a) 0< a<1

(0, b)

x x x

0 – ¥ 1 0 – ¥ 1 0 – ¥ 1

Для игрока 2 исследования аналогичны. Если ввести обозначения

b₁:= b₁₁ - b₁₂ - b₂₁ + b₂₂

b₂:= b₂₂ -

то множество L приемлемых для него ситуаций состоит из:

всех ситуаций вида (x, 0), если b₁x - b₂ < 0; 0 £ x £ 1,

всех ситуаций вида (x, y), если b₁x - b₂ = 0; 0 £ x £ 1; 0 < y < 1,

всех ситуаций вида (x, 1), если b₁x - b₂ > 0; 0 £ x £ 1.

Результаты следующие:

если b₁ = b₂ = 0, то решение 0 £ x £ 1; 0 £ y £ 1;

если b₁ = 0; b₂ ¹ 0, то решение либо y = 0, либо y = 1 при 0 £ x £ 1 (приемлемой стратегии в игре не существует);

если b₁ > 0, то решения следующие:

y = 0, x < = b; y = 1, x > b; 0 < y < 1; x = b;

если b₁ < 0, то решения следующие:

y = 0, x > b; y = 1, x < b; 0 < y < 1; x = b

При этом необходимо учитывать, что 0 £ x £ 1.

·

·

y y

1 1

(b,y) (b,y)

x x

0 1 0 1

b₁ > 0 b₁ < 0

0 < b < 1 0 < b < 1

Решением игры является пересечение множеств K и L, т.е. те значения x и y, которые являются общими для множеств K и L.

y y

1 1

x x

0 1 0 1

а) б)

При этом зигзаги K и L могут быть не только одинаковой, но и противоположной направленности. В первом случае зигзаги имеют одну точку пересечения, а во-втором – три. Средние выигрыши при этом определяются по формулам (*), если в них подставить полученное решение x и y (рис.а)). Очевидно a входит в смешанную стратегию игрока 2, хотя зависит только от выигрышей 1 игрока; b входит в смешанную стратегию игрока 1, хотя зависит только от выигрышей игрока 2. Сравнение этих результатов с результатами решения матричных игр с нулевой суммой показывает, что a совпадает с оптимальной стратегией игрока 1 в матричной игре с матрицей A, а b – с оптимальной стратегией игрока 2 в матричной игре с матрицей B. Отсюда можно сделать вывод, что равновесная ситуация направляет поведение игроков не только на максимизацию своего выигрыша, сколько на минимизацию выигрыша противника.

С другой стороны, естественно также рассматривать подходящим поведение игроков в конечных бескоалиционных играх, направленное на максимизацию своего выигрыша с учётом максимального противодействия игрока, т.е. подходящей стратегией игрока 1 считать оптимальную смешанную стратегию игрока 1 в матричной игре с матрицей A, а подходящей стратегией игрока 2 считать оптимальную смешанную стратегию игрока 2 в матричной игре с матрицей B, если в ней рассматривать решение с позиций максимизации выигрыша игрока 2, т.е. решать её, как для игрока 1, с матрицей .

Задача1

Составим матрицу из коэффициентов

расширенная матрица

прямой ход Гаусса

поменяем местами (1) и (2) строки

Получим

Когда элементы под главной диагональю станут равными нулю применим обратный ход Гаусса

Составим уравнения и из них найдем значения x1 x2 x3

Задача2

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

Текстовый файл в котором содержатся сведения имеет такую структуру записи

Петров Луганск Буденного Иванов Луганск Советская Сидоров Ровеньки Буденного

Dim t(1 To 5, 1 To 100) As String ‘Объявляем массив

Dim c As Integer

Dim i, i2 As Integer ‘ счетчики

Open "C:\Program Files\Microsoft Visual Studio\VB98\DB\.txt" For Input As #1 ‘ Откроем файл для чтения

c = 0 ‘ Количество прочитанных записей (каждая запись состоит из 5 строк)

Do While Not EOF(1) ‘ Делаем пока не конец файла

c = c + 1 ‘ Переходим на следующую запись

For i = 1 To 5

Line Input #1, t(i, c) ‘ Читаем из файла строку и помещаем ее в массив

Next i

Loop

For i = 1 To ‘ Перебираем все считанные элементы и затем сравниваем строки отвечающие за адресс. Если города различны, но оставшийся адрес одинаков, то выводим фамилии людей

For i2 = i + 1 To c

If t(2, i) <> t(2, i2) And t(3, i) = t(3, i2) And t(4, i) = t(4, i2) And t(5, i) = t(5, i2) Then

Print t(1, i), t(1, i2)

End If

Next i2

Next i

End Sub

Результат работы

Петров

Сидоров