Строго выпуклые игры на единичном квадрате

Функция φ(x) называется выпуклой, если для любых двух точек z₁ и z₂ из множества Z выполняется неравенство:

φ(λz₁ + (1-λ)z₂ ) λφ(z₁) + (1- λ)φ(z₂),

Если неравенство строгое, то и функция строго выпуклая (если неравенство выполняется строго, то вторая производная φ˝(z)>0).

Опр. Игра Г=<X,Y,a> называется игрой на единичном квадрате, если X=[0,1] и Y=[0,1], а целевая функция a(x,y) определена для каждой точки этого квадрата.

Опр. Игра Г на единичном квадрате называется непрерывной, если функция платежей a(x,y) непрерывна в каждой точке единичного квадрата по обеим переменным.

Опр. Непрерывная антагонистическая игра на единичном квадрате называется выпуклой, если функция a(x,y) строго выпукла по Y для всех x X. Иными словами, для функции платежей в строго выпуклой игре имеет место неравенство:

a(x, λy₁ + (1-λ)y₂) < λ a(x,y₁) + (1- λ) a(x,y₂), .

Исходя из свойств строгой выпуклости, .

Теорема. В строго выпуклой игре на единичном квадрате 2-ой игрок имеет единственную оптимальную стратегию, которая является чистой. Цена игры в этом случае v(a), где v(a) — функция платежей.

v(a) = = , где y* — оптимальная чистая стратегия 2-го игрока.

Х* — множество стратегий 1-го игрока, состоящее из тех х* Х*, для которых выполняется условие a(x*,y*) = v(a).

х* — тоже чистые стратегии, они называются существенными стратегиями, а остальные – несущественными.

Нахождение существенных стратегий 1-ого игрока основано на выполнении следующих свойств.

1. Если y*=1, то у 1-го игрока существует стратегия х₁, для которой

.

Геометрическое истолкование:

При уменьшении y a(x,y) возрастает.

 

2. Если y*=0, то среди стратегий 1-го игрока существует такая стратегия х₂, что , y=y*.

 

3. Если имеется значение стратегии 0<y*<1, то у 1-го игрока найдутся 2 существенные стратегии х₁ и х₂,для которых имеет место условие

, y=y* , y=y*

Наиболее оптимальной стратегией 1-ого игрока является вероятностная смесь стратегий х₁ и х₂, причем х₁ — с вероятностью р, х₂ — с вероятностью (1-р).

— уравнение, позволяющее определить р.

Доказывается, что решение этого уравнения единственно и принадлежит интервалу .

 

Пример. Пусть имеется игра Г=<X,Y,a>, x,y [0,1], функция выигрыша a(x,y) = (x-y)².

1). Рисуем график функции платежей (выигрыша):

 

2). Проверим функцию платежей на выпуклость.

 

Функция платежей строго выпукла по у. Имеем дело со строго выпуклой игрой на единичном квадрате.

Найдем v=v(a). Для этого рассмотрим функцию:

.

Построим таблицу:

y		0.25	0.5	0.75
Ψ(y)		0.5625	0.25	0.05625

y*=0.5

v(a)=0.25

Отсюда видим, что в нашем случае 0<y*<1, а следовательно, у 1-го игрока есть две существенные стратегии: х₁ и х₂. Для их нахождения рассмотрим зависимость

v(a)=a(x,y*)=(x-y*)²=(x-0.5)²=0.25

x₁=0, x₂=1 — две существенных чистых стратегии 1-го игрока.

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

следовательно, оптимальная стратегия 1-го игрока есть вероятностная смесь по стратегиям х=х₁ и х=х_2. Найдем эти вероятности.

p=0.5

Покажем, что найденное решение является точкой равновесия. Рассмотрим проигрыши 2-ого игрока при оптимальной стратегии 1-ого:

a(x*,y) = p*(x₁ - y)² + (1-p*)(x₂ - y)² = 1/2(-y)² + 1/2(1-y)² , y, следовательно минимум 1/4.

a(x,y*) — выигрыш 1-ого игрока при условии, что 2-ой примет свою оптимальную чистую стратегию.

 

Неантагонистические игры

N={1,2,…,N} — число игроков (больше двух).

Возможны следующие ситуации:

1) совместные действия игроков (коалиции) запрещены по условиям игры, и тогда игра называется бескоалиционной;

2) совместные действия не запрещены, игроки могут образовывать коалиции и действовать совместно. Такие игры называются кооперативными.

 

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

В таких играх каждый игрок действует самостоятельно.

Игра Г=<N, {x_i}, i N, {H_i}, i N>,где N — множество игроков, x_i-множество стратегий i-го игрока, H_i — множество функций выигрыша для каждой ситуации.

Каждый игрок выбирает некоторую стратегию из множества Х_i:

i x⁽ⁱ⁾ X_i, получаем ситуацию (x⁽¹⁾,x⁽²⁾,…,x^(N)). В результате каждый из игроков получает выигрыш H_i(x⁽¹⁾,x⁽²⁾,…,x^(N)), i N.

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

Простейшей бескоалиционной игрой является игра двух лиц. Они могут не только выигрывать или проигрывать, но и делать это совместно (одновременно выигрывать или проигрывать).

Опишем такую игру (бескоалиционную) в нормальной форме:

Г=<x₁,x₂,H₁,H₂>, где {x₁,x₂}-множество стратегий, H₁,H₂— функции выигрыша.

(x⁽¹⁾,x⁽²⁾) H₁(x⁽¹⁾,x⁽²⁾), H₂(x⁽¹⁾,x⁽²⁾)

Ясно, что если игра конечна, то матрицу Н можно рассмотреть как

H₁=(a_ij) m*n A

H₂=(b_ij) m*n B

Такую игру называют биматричной: Г=<A,B>; a_ij= -b_ij, , , следовательно, игра антагонистическая.

 

Библиографический список

 

1. Петросян Л.А., Зенкевич Н.А., Семина Е.Н. Теория игр.-М.: В.Ш. 1998.

2. Коршунов Ю.М. Математические основы кибернетики. –М.: Энергоатом-

издат, 1987.

3. Интрилигатор М. Математические методы оптимизации и математическая теория.- М.: Прогресс, 1975.

4. Карлин С. Математические методы в теории игр, программировании и экономике.- М. Мир.1964.

5. Дюбин Г.Н., Суздаль В.Г. Введение в прикладную теорию игр.- М.: Наука,

1984.

6. Нейман Д., Моргенштерн О. Теория игр и экономическое поведение. М.:

Наука, 1970.

7. Гегечкори Е.Т. Математические модели принятия решений в экономике и

технике.- Омск, Изд-во ОмГТУ, 2004.

8. Адамчук А.С. и др. Математические модели и игры в экономике: Уч. Пособие, Ставрополь: Сервисшкола, 2004.