Лекция 2. Биматричные игры Биматричная игра - это бескоалиционная игра двух игроков, каждый из которых имеет конечное множество стратегий. Пусть первый. - презентация

1 Лекция 2. Биматричные игры Биматричная игра - это бескоалиционная игра двух игроков, каждый из которых имеет конечное множество стратегий. Пусть первый игрок имеет m стратегий : А 1, А 2,…, А m. Второй игрок имеет n стратегий : В 1, В 2,…, В n. Игра имеет mxn возможных ситуаций вида ( А i, В j). Выигрыши игроков зависят от ситуации : 1 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

2 Лекция 2. Биматричные игры Формальная запись биматричной игры : Но обычно говорят, что биматричная игра задана матрицами выигрышей первого и второго игроков - А и В соответственно, размерности mxn. 2 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

3 Лекция 2. Биматричные игры Ситуация равновесия в биматричной игре также определяется по Нэшу : Решить биматричную игру – найти все ситуации равновесия и указать выигрыши каждого игрока в них. 3 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

4 Лекция 2. Биматричные игры Пример 6. Конкурс на реализацию проекта. Две фирмы, борющиеся за заказ на определенную работу, могут выбрать два варианта - подать развернутую программу (1- я стратегия ) или простую заявку (2- я стратегия ). Согласно правилам при одинаковом выборе конкурентов заказ и доход делятся пополам, а в другом случае предпочтение отдается фирме, подавшей подробную заявку. На реализацию проекта победителям ( одному или двоим ) выделяется 10 тысяч долларов. Технические затраты на простую заявку - 1 тысяча долларов, на развернутую программу - 3 тысячи долларов. 4 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

5 Лекция 2. Биматричные игры 0 5 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций 1- й игрок развернутая про - грамма простая заявка 2- й игрок развернутая про - грамма простая заявка развернутая про - грамма 27 2 простая заявка 4 простая заявка 74

6 Лекция 2. Биматричные игры Смешанное расширение биматричной игры Смешанной стратегией игрока называется набор вероятностей применения его чистых стратегий : X – множество всех смешанных стратегий первого игрока. Y – множество всех смешанных стратегий второго игрока. Эта система называется смешанным расширением биматричной игры. 6 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

7 Лекция 2. Биматричные игры Смешанное расширение биматричной игры Смешанной стратегией игрока называется набор вероятностей применения его чистых стратегий : X – множество всех смешанных стратегий первого игрока. Y – множество всех смешанных стратегий второго игрока. Эта система называется смешанным расширением биматричной игры. 7 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

8 Лекция 2. Биматричные игры Выигрыш первого игрока в смешанном расширении игры : Выигрыш второго игрока в смешанном расширении игры : 8 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций В1В1 … ВnВn y1y1 … ynyn А1А1 х 1 х 1 а 11 … а 1mа 1m :: :: АmАm хmхm аm1 аm1 … а mn В1В1 … ВnВn y1y1 … ynyn А1А1 х 1 х 1 b 11 … b1mb1m :: :: АmАm хmхm bm1bm1 …b mn

9 Лекция 2. Биматричные игры Ситуация (x*,y*) является ситуацией равновесия по Нэшу в смешанном расширении биматричной игры, если Решить игру в смешанном расширении – найти оптимальные смешанные стратегии (x*,y*), удовлетворяющие (6), (7). Теорема Нэша. Биматричная игра всегда имеет решение. Все ситуации, которые удовлетворяют (6), являются приемлемыми для первого игрока. Все ситуации, которые удовлетворяют (7), являются приемлемыми для второго игрока. 9 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

10 Лекция 2. Биматричные игры Метод решения биматричной игры 2 х 2 x = ( х 1, х 2) = ( х 1, 1- х 1), у = ( у 1, у 2) = ( у 1, 1- у 1) 10 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций В1В1 В2В2 y1y1 y2y2 А1А1 х 1 х 1 а 11 а 12 А2А2 х 2 х 2 а 21 а 22 В1В1 В2В2 y1y1 y2y2 А1А1 х 1 х 1 b 11 b 12 А2А2 х 2 х 2 b 21 b 22

11 Лекция 2. Биматричные игры Условия (6) примут вид : Условия (7) примут вид : Неравенства (8) описывают множество всех приемлемых для первого игрока ситуаций ( х, у ). Неравенства (9) - множество всех приемлемых ситуаций для второго игрока. 11 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

12 Лекция 2. Биматричные игры Для первого игрока построим множество приемлемых для него ситуаций K: Обозначим Тогда неравенства (8) перепишем в виде Система неравенств (10),(11) описывает ситуации вида : 1) (0, у 1), где 2) ( х 1, у 1), где 3) (1, у 1), где 12 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

13 Лекция 2. Биматричные игры Если, то множество K – весь единичный квадрат Если, то при х 1= 0, при х 1= 1, 13 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

14 Лекция 2. Биматричные игры Если, то множество K Если, то множество K 14 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

15 Лекция 2. Биматричные игры Аналогично для второго игрока построим множество приемлемых для него ситуаций L: Обозначим Тогда неравенства (9) описывает ситуации вида : 1) ( х 1,0), где 2) ( х 1, у 1), где 3) ( х 1,1), где 15 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

16 Лекция 2. Биматричные игры Если, то множество L – весь единичный квадрат Если, то при у 1= 0, при у 1= 1, 16 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

17 Лекция 2. Биматричные игры Если, то множество L Если, то множество L 17 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

18 Лекция 2. Биматричные игры Пересечение множеств K и L – это множество ситуаций, приемлемых для обоих игроков, т. е. это ситуации равновесия. Если точка, то оптимальная смешанная стратегия первого игрока оптимальная смешанная стратегия второго игрока Выигрыши каждого игрока в ситуации равновесия вычисляются по формулам : Если точка пересечения попадает в угол единичного квадрата, т. е. имеет координаты (0,0),(0,1),(1,0),(1,1), то ситуации равновесия в чистых стратегиях. 18 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

19 Лекция 2. Биматричные игры Решение Примера 6. т. е. каждый игрок выбирает свою первую стратегию – обе фирмы подают развернутую программу, потратив по 3 тыс. долларов, поэтому из выделенных 10 тысяч осталось только 4 тысячи, которые по правилам конкурса поделили пополам, и выигрыш каждой составил 2 тыс. В этом примере четко видно наличие противоречия между выгодностью и устойчивостью : если бы каждая фирма исключила свои доминируемые стратегии, то получила бы выигрыш 4 тыс., что не совпадает с устойчивой по Нэшу ситуацией. 19 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

20 Лекция 2. Биматричные игры Пример 7. Семейный спор. Два экономических партнера договариваются о совместном проведении одного из двух действий : D1 ( предложенного первым партнером ) и D2 ( предложенного вторым партнером ), каждое из которых требует необходимого совместного участия обоих партнеров. Если осуществляется D1, то первый получает 2 ед. полезности, а второй 1 ед., если осуществляется D2, то первый получает 1 ед., а второй 2 ед. полезности О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

21 Лекция 2. Биматричные игры Домашнее задание : Составить матрицы выигрышей и решить игру : Завод выпускает автомобили партиями по 100 шт. За каждую а / м завод получает от концерна 1.3 ден. ед. оплаты, из которых 1 ед. составляют премиальные, а 0.3 ден. ед. предназначены для операций технического контроля ( ОТК ). Завод может выпускать партию а / м с ОТК либо без ОТК, увеличивая сумму премиальных ( до 1.3 ден. ед.). Чтобы уменьшить производственный брак, концерн решил привлечь независимую фирму осуществляющую технический контроль за качеством продукции. Стоимость проверки одной а / м составляет 0.12 ден. ед. Если ОТК заводом не проводится, то а / м неисправен с вероятностью 4/5. В случае обнаружения неисправностей завод обязан их устранить, затратив 0.3 ден. ед. и дополнительно заплатить фирме - эксперту 0.2 ден. ед. из своих премиальных. Фирма - эксперт может проверить партию а / м или не проверить ее. Выигрыш завода – сумма оставшихся премиальных, а выигрыш фирмы - эксперта - заработанные на проверке деньги. Решить биматричную игру : 21 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

22 Лекция 2. Биматричные игры Выводы : Биматричная игра – модель конфликта, в котором интересы игроков не противоположны : каждый – сам за себя. Биматричными играми можно моделировать решение ситуации в условиях неопределенности, когда достоверно не известно, какое действие выберет соперник. Известны методы эффективного решения игр 2 х 2 в смешанных стратегиях, для биматричных игр общего вида методы решения не разработаны. В моделях биматричных игр присутствует противоречие между выгодностью и устойчивостью : устойчивые решения не всегда являются выгодными для игроков. Поведение игроков в биматричных играх направлено не на повышение своего выигрыша, а на понижение выигрыша соперника. 22 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций