Лекции в печатном виде (990087), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Для того, чтобы произвольная матрица удовлетворяла этому требованию ищется M=мах(|а_ij||a_ij0) и прибавляется ко всем элементам, получаем a_ij+M>0.

Пусть А выбирает смешанную(оптимальную) стратегию, а В чистую:

Введем величину 0, i=1,…,m

Тогда:

(*) x_i0 i=1,…,m

Т.к.

Получаем задачу линейного программирования:

при системе ограничений (*).

Решив ее, найдем (x_1, x_2,…, x_m) и

Зная V, найдем p_i=x_i*V.

Итерационный метод Брауна-Робинсона

Этот метод ориентирован на произвольную игру G(m,n).

Не требует условия a_ij>0.

Рассмотрим метод на примере игры G(3,3).

S_A=(p₁,p₂,p₃)

S_B=(q₁,q₂,q₃)

Строится следующая матрица:

где:

k – номер партии

i – номер стратегии, выбираемой игроком A

j – номер стратегии, выбираемой игроком В

B_i – накопленный игроком А выигрыш за k партий, при условии,

что в данной партии B выбирает стратегию B_i

А_j – накопленный игроком В проигрыш за k партий,

при условии, что в данной партии A выбирает стратегию А_j.

V – нижняя оценка игры = min (накопленный выигрыш)/k

V – верхняя оценка игры = max (накопленный проигрыш)/k

Доказано, что

V ^*=(V+V)/2, V^*  V при k   и

- cколько раз выбирается А_i стратегия

- cколько раз выбирается B_j стратегия

Пример. Задача о двух КБ

Объявлен конкурс на выполнение 2-х проектов.

На проект 1 выделено а денежных единиц.

На проект 2 выделено b денежных единиц.

В конкурсе участвуют 2 КБ:

КБ₁(А) – 4 отдела,

КБ₂(В) – 3 отдела.

Практика показывает, что если КБ выделяет больше отделов на проект, то оно и получает этот проект, если же они выделяют одинаковое количество отделов, то получения проекта КБ₁ и КБ₂ равновероятны.

Стратегии:

(,) -  - количество отделов, выделяемых под первый проект

 - количество отделов, выделяемых под второй проект

КБ₁(А):

А₁=(4,0); А₂=(3,1); А₃=(2,2); А₄=(1,3); А₅=(0,4).

КБ₂(В):

В₁=(3,0); В₂=(2,1); В₃=(1,2); В₄=(0,3);

Для того, чтобы свести парную игру к антагонистической, вычисляем средний выигрыш – (a+b)/2 и вычитаем его из V.

G(5,4):

Пусть а=b.

S_A=(0,1/2,0,1/2,0)

S_B=(1/2,0,0,1/2)

p₁=p₂=1/2

q₁=q₂=1/2

V=( a₁₁*p₁+a₂₁*p₂)*q₁+( a₁₂*p₁+a₂₂*p₂)*q₂=a/4

V_КБ1=a/4+a=5a/4

V_КБ2=3a/4

Парная игра с произвольной суммой.

(биматричная игра).

И

гра G(m,n)

Выигрыши игрока А Выигрыши игрока В

Д

ве данные матрицы объединяют в одну:

Нет общей теории решения биматричных игр.

В данном классе игр могут быть коалиции, договорённости.

Теория некооперативных игр Нэша.

Необходимо найти решение в виде:

S_A =( p₁, p₂…, p_N)

S_B =( q₁, q₂…, q_N)

Вводится понятие – ситуация равновесия:

S_A*=( p_i*) i=1..m

S_B*=( q_j*) j=1..n

Определение.

S_A* и S_B* является ситуацией равновесия, если онаудовлетворяет следующим условиям:

Для игрока А :

Для игрока В :

По Нэшу, решением биматричной игры является ситуация равновесия при условии, что они взаимозаменяемы.

Нэш доказал, что для любой биматричной игры существует ситуация равновесия, но нет общего метода её поиска.

Модели биматричных игр, к которым плохо применима теория Нэша.

1. Проблема узника.

Игра 2х2.

Два узника находятся в разных камерах,

Обвиняются в одном преступлении.

Интерпретация стратегий:

А₁ В₁ – кооперативная стратегия – молчать.

А₂ В₂ – некооперативная стратегия – давать показания на другого.

А₂ А₁ и В₂ В₁ вторые стратегии доминируют , и ситуацией равновесия будет А₂ В₂ = ( -6 , -6 ), но точка ( -1 , -1 ) более выгодна.

1. Конкурирующие фирмы.

А₁ В₁ – сохранение уровня цен.

А₂ В₂ – снижение цен.

По теории Нэша:

А₂ А₁ и В₂ В₁ , следовательно ситуацией равновесия будет

А₂ В₂ = ( 3 , 3 ), но лучше точка А₁ В₁ = ( 5 , 5 ).

1. Семейный спор.

А – муж.

Характеристики

Список файлов лекций