Реферат: Игра состоит из последовательности ходов. Ходы бывают личные и случайные. (В шахматах все ходы личные. Рулетка содержит случайный ход). Результаты ходов оцениваются

Введение в матричные игры

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

Игра состоит из последовательности ходов. Ходы бывают личные и
случайные. (В шахматах все ходы личные. Рулетка содержит случайный ход).

Результаты ходов оцениваются функцией выигрыша для каждого игрока. Если сумма выигрышей равна 0, то игра называется игрой с нулевой суммой
(преферанс). Будем рассматривать только такие игры.

Стратегией называется набор правил, определяющих
поведение игрока, т.е. выбор хода.

^ Оптимальной стратегией называют такую стратегию, при которой достигается максимальный ожидаемый
средний выигрыш при многократном повторении игры.

^ Матричные игры — это игры, где два игрока играют в игру с нулевой суммой, имея конечное число «чистых» стратегий: {1,…, m} и {1,…, n} и  (ij) задан платеж aij второго игрока первому. Матрица (aij) задает выигрыш первого
игрока и проигрыш второго, aij≷ 0 !

Игра в орлянку.

Игроки выбирают ход{орел, решка}. Если ходы совпали, то выиграл первый, иначе второй.



II игрок

орел

решка

I игрок

орел

1

­– 1

решка

– 1

1



^ Прорыв обороны. Первый игрок выбирает систему зенитного вооружения. Второй игрок выбирает самолет. Элементы aij задают вероятность поражения самолета j системой i. Цель второго игрока — прорвать оборону.








Самолеты

Зенитки

0,5

0,6

0,8

0,9

0,7

0,8

0,7

0,5

0,6



В первом примере все ходы одинаково плохи или хороши. Во втором примере ход (2, 2) в некотором смысле лучший для обеих сторон: если взять самолет 2, то зенитка 2 — лучшая для первого игрока; если взять зенитку 2, то самолет 2 лучший для второго. В матрице есть седловая точка!

Определение. Седловой точкой матрицы (aij) называют пару (i0j0) такую, что

.

^ Принцип минимакса (осторожности).

Предположим, что противник всеведущ и угадывает все ходы! Первый игрок предполагает, что второй все знает и для хода i первого игрока выберет j(i):
aij(i)  aij, j = 1,…, n. Обозначим Тогда лучшей
стратегией для первого игрока является выбор i0 такой, что



Величину  назовем нижней ценой игры в чистых стратегиях.

Второй игрок из соображений осторожности считает, что первый  j выберет i(j) так, что ai(j)j  aij,  i, т.е. и выбирает j с минимальным j, т.е.

.

Величину  назовем верхней ценой игры в чистых стратегиях.

Пример 1.  = –1,  = +1,   

Пример 2. ,

Лемма. Для любой функции f(x,y), xX, yY, справедливо неравенство



в предположении, что эти величины существуют.

Доказательство. Введем обозначения:

,

.

Тогда



Теорема. Необходимым и достаточным условием равенства верхней и нижней цен игры в чистых стратегиях является существование седловой точки
в матрице (aij).

Доказательство. Необходимость. Пусть  = . По определению



т.е. Так как  = , то , т.е. является седловой точкой.

Достаточность. Пусть седловая точка (i0j0) существует, т.е.



Тогда но по лемме верно обратное, т.е. . Следовательно  = .

Смешанные стратегии и основная теорема матричных игр

Определение. Под смешанной стратегией будем понимать вероятностное распределение на множестве чистых стратегий.

Смешанная стратегия первого игрока: p = (p1,…, pm),



Смешанная стратегия второго игрока q = (q1,…, qn),



При многократном повторении игры игрок выбирает чистые стратегии
случайным образом с соответствующими вероятностями.

Платежная функция для смешанных стратегий p и q:



задает математическое ожидание выигрыша первого игрока при p,q.

Замечание. Добавлением большой положительной константы можно добиться того, что E(p,q) > 0,  p,q без изменения стратегий.

Из принципа осторожности:

Первый игрок ищет максимум и получает нижнюю цену игры

Второй игрок ищет минимум и получает верхнюю цену
игры

Теорема Фон–Неймана

В матричной игре существует пара смешанных стратегий, таких что

,  pPm, qQn.

 =  = .

Доказательство. Сначала покажем, как представить задачу о выборе
наилучших стратегий в виде ЛП, а затем докажем теорему.

Первый игрок: (p)  max



Пусть ui = pi/(p), i = 1,…, m, в предположении (p) > 0.

Тогда ui  0, i = 1,…, m, и Заметим, что и задача (p)  max может быть записана следующим образом:



,

.

Аналогичным образом получаем задачу второго игрока:







где vj = qj/(q), j = 1,…, n. Полученные задачи являются взаимодвойственными. Пусть — оптимальные решения этих задач.

Положим , . Из второй теоремы двойственности следует, что



Просуммировав, получим

.

Поделим на



Теперь докажем первое утверждение теоремы:



Аналогично



т.е.

Докажем второе утверждение теоремы.

Из предыдущего неравенства имеем:



т.е.

Но по лемме      =  =



^ Дилемма заключенных

Два преступника пойманы за совершение преступления.
У следствия не хватает доказательств их виновности и преступникам предлагают сделку:

^ Если сознаешься и подтвердишь участие товарища в преступлении, то выйдешь на свободу, а товарищ получит 7 лет лишения свободы.

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

Если оба преступника сознаются, то каждый получит 5 лет.

Если оба не сознаются, то каждый получит по 1 году.

^ Матричная игра двух лиц




2-й сознался

2-й не сознался

1-й сознался

5 : 5

0 : 7

1-й не сознался

7 : 0

1 : 1



Седловая точка — оба сознаются — существует и дает 5 лет каждому


Оптимальное решение — не сознаваться — дает только 1 год.

Оно не является седловой точкой!


Что будет, если дать преступникам посовещаться?

^ Вопросы к экзамену

3 курс, ФИТ, НГУ, Летняя сессия,  2008 г.

Метод динамического программирования на примере распределительной задачи.

Модель размещения капитала. Свойство дробных решений. Процедура
округления.

Алгоритмы для задачи о рюкзаке с гарантированной точностью 0.5 и 0.75.

Аппроксимационные схемы. Полиномиальные и полностью полиномиальные аппроксимационные схемы. Примеры таких схем для задачи о рюкзаке.

Задача замены оборудования с учетом дисконтирования затрат. Соотношения динамического программирования для случая конечного планового периода.

Задача упаковки в контейнеры. Нижние оценки целевой функции.

Задача двумерной прямоугольной упаковки. Алгоритм имитации отжига.

Задача календарного планирования. Критические работы, пути и критическое время проекта. Вероятность завершения проекта к заданному сроку

Постановка задачи календарного планирования с ограниченными ресурсами.

Т–поздние расписания. Алгоритм вычисления Т–поздних расписаний.

Доказательство оптимальности Т*–позднего расписания. Алгоритм Гимади.

Задачи календарного планирования с переменными длительностями работ. Сведение к линейному программированию.

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

Задача коммивояжера с неравенством треугольника. Алгоритм с гарантированной оценкой точности 2. Доказательство оценки и ее неулучшаемости.

Нижние оценки в задаче коммивояжера: примитивная оценка, оценка линейного программирования, оценка задачи о назначениях и минимальные 1-деревья.

Алгоритм решения задачи о назначениях.

Метод ветвей и границ для задачи коммивояжера.

Классификация задач теории расписаний.

Алгоритм Лаулера для задачи 1| prec| fmax

Алгоритм решения задачи 1| prec, pmtn, ri | fmax

Алгоритм решения задачи P | pmtn |Cmax

Алгоритм решения задачи P | pmtn, ri |Lmax

Алгоритм решения задачи Q | pmtn |Cmax

Алгоритм решения задачи F2 || Cmax

Задачи о покрытии, алгоритм Чватала, оценка его погрешности и экстремальный пример.

Задачи размещения. Генетический алгоритм для задачи размещения производства.

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

Матричные игры. Определение седловой точки.

Необходимые и достаточные условия равенства верхней и нижней цен игры в чистых стратегиях. Теорема Фон-Неймана. Дилемма заключенных.





Лекция 14. Матричные игры --