19. Решение игр 2xn и mx2.

Решение игры mx2

Рассмотрим показатель не эффективности игрока В B(Q)= max(1-qi)ai1-q*ai2

Q=(1-q1,q2) min B(Q)=B(Qопт)=max((ai2-ai1)*qопт+ai1)

По теореме ДЖона Фон Неймана V=B(Qопт)

Алгоритм «В»

1. Cтроим отрезок 0,1

2. Откладываем перпендикуляры слева и справа

3. от точки ноль откладываем значения первого столбца

4. от точки 1 откладываем значения второго столбца

5. соединяем элементы с одинаковым первым индексом ai1 и ai2

H(Ai, Q) =(ai2-ai1)*q+ai1 q Є [0, 1]

6. если отрезок ai1 и ai2 имеют не отрицательный наклон стратегия В1 доминирует В2, если ai1 и ai2 больше нуля то В1 строго доминирует В2

7. если все отрезки ai1 и ai2 имеют не положительный наклон к=0 или k<0 все отрезки не возрастающие тогда В2 доминирует В1

8. Если какой-либо отрезок ai1 и ai2 лежит не ниже отрезка, чем отрезок ai1 и ai2 то стратегия ai1 доминирует ai2

9. выделим верхнюю огибающую

10. находим наинизшую точку (min)

11. находим абсцисс и ординат опуская перпендикуляр

12. ищим ординату низшей точки

13. Верхний из нижних концов отрезка ai1 и ai2 в нижней ценой в чистых стратегиях

14. выбираем нижний конец верхней огибающей она характеризует верхнюю цену в чистых стратегиях (В)

15. Элемент матрицы А изображающие точки, которые являются нижним концом отрезка и одновременно на перпендикуляре накотором она лежит является седловой точкой игры.

Решение игры 2xn

Алгоритм

1. строим отрезок 0,1

2. откладываем перпендикуляры на обоих концах отрезка

3. на левом перпендикуляре откладываем элементы первой строки

4. на правом перпендикуляре откладываем все элементы второй строки

5. соединяем элементы одного столбца

H(Pi, Bj)= (a2j-a1j)*p+aij

Первый игрок выбирает свою смешанную стратегию,

Второй игрок выбирает чистую стратегию

6. a1j, a2j не убывают тогда А2доминирует А1

7. a1j, a2j возрастает тогда А2 строго доминирует А1

8. Если [a1j, a2j] не возрастает тогда А1 доминирует А2

9. Если [a1j, a2j] убываеттоггда А1 строго доминирует А2

10. Если [a1j, a2j] лежит не ниже отрезка [a1j, a2j] тогда Bj2 доминирует Bj1

11. Если [a1j, a2j]выше [a1j, a2j] то Bj2 строго доминирует Bj1

12. Нижняя огибающая семейства отрезков

13. Наивысшая точка N

14. Перпендикуляр к (0, 1) от N, абсцисса Ропт = (1-р2, р2)

15. Ордината N-V

16. Верхний конец нижней огибающей дает нижнюю цену игры( альфа)

17. Из оставшихся отрезков ( верхней огибающей) дает верхнюю цену игры (бетта)

18. Элемент матрицы А, образ которого является нижним на перпендикуляре, где эта точка лежит и одновременно верхним концом отрезка, где она лежит, будет седловой точкой игры

20. Решение игр mхn. Эквивалентные задачи линейного программирования.

Пусть задана игра   с платежной матрицей   . Пусть 1-ый задался целью выиграть не менее   при любо стратегии противника. Причем   должно быть максимальным. Тогда его задача состоит в определении оптимального решения в смешанных стратегиях  , для которого выполнялось бы    Все   можно считать положительными, в противном случае можно добиться этого, прибавив ко всем элементам матрицы положительную константу. Такая прибавка никак не влияет на стратегию игроков. Установите игроков с положительной платежной матрицей нижняя цена игры положительна. Мы можем прейти к новым переменным   , а задача 1-го игрока сводится к нахождению вектора  Мы применим к задаче линейного программирования с n переменными и m стратегиями.  Второй игрок стремится проиграть не более, чем   . Причем   нужно минимизировать. Можно показать, что задача сводится к нахождению вектора        Если сопоставить задачи первого и второго игрока, то можно увидеть, что они образуют двойственную пару задач линейного программирования. Из свойств решения двойственных задач следует   – цена игры

Решение игр (aij)mxn с помощью линейного программирования

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

Для первого игрока математическая модель задачи записывается в виде

при ограничениях:

Математическую модель можно упростить, разделив все (п + 1) ограничений на v. Это возможно при v ≠ 0. При v = 0 рекомендуется прибавить любое положительное число ко всем элементам платежной матрицы, что гарантирует положительность значения модифицированной игры. Действительное значение игры получается вычитанием из модифицированного значения этого положительного числа. Если v < 0, то надо сменить знаки неравенств. Полагая v > 0, систему ограничений можно записать так:

• Дифференциальные уравнения второго порядка (модель рынка с прогнозируемыми ценами) Рассмотрим модель рынка с прогнозируемыми ценами. В простых моделях рынка спрос и предложение обычно полагают зависящими только от текущей цены на товар. Однако спрос и предложение в реальных ситуациях зависят еще и от тенденции ценообразования и темпов изменения цены. В моделях с непрерывными и дифференцируемыми по времени t функциями эти характеристики описываются соответственно первой и второй производными функции цены P(t). Теорема о разложении: Определитель равен сумме парных произведений элементов какого-либо ряда (строки или столбца) его на их алгебраические дополнения.

Положим Хi = xi/v. Так как v → max, то 1 / v → min. Получим задачу линейного программирования вида

при ограничениях:

Для второго игрока математическая модель записывается в виде

при ограничениях:

где S( ) = 1 / v, Yj = уj / v.

Задача второго игрока является двойственной по отношению к задаче первого игрока. Можно найти решение одного из игроков, а затем по теоремам двойственности — решение другого.