Матричные игры.

Игроки-участники игры. N - множество игроков. Стратегии -решения, принимаемые игроками. В некоторых играх игрокам имеет смысл объединяться и действовать совместно, такие объединения называют коалициямидействий - Кд. Для каждого игрока должны быть определены возможные действия, которые определяют множество допустимых стратегий, которые принято называть чистымистратегиями. При произвольном выборе стратегий может сложиться ситуация, которая не разрешается правилами игры, т.е. запрещеннаяситуация. Ситуация, разрешаемая правилами игры, называется допустимой. S0 - мн-во допустимых исходов. В зависимости от предпочтительности исходов игрокам имеет смысл объединяться в коалиции интересов - Ки. Сравнивать исходы между собой в общем случае можно с помощью отношения предпочтения ≥. Удобнее использовать численную оценку каждого исхода, т.е. критерий эффективности, который в игре принято называть функцией выигрыша. {N, Кд, Ки, {Ui}i Î Ки, S0, {≥ }} ({Ui}i Î Ки - множество чистых стратегий i - го игрока). Оптимальная стратегия -стратегия, которая при многократном повторении игры обеспечивает данному игроку максимально возможный средний выигрыш. Смешанная стратегия - вероятностное распределение на множестве чистых стратегий. Совокупность смешанных стратегий определяет множество смешанных стратегий, которое является расширением множества чистых стратегий. Антагонистическая игра. Бескоалиционная игра двух лиц (т.е. не допускается каких-либо коалиций) с нулевой суммой (g1+g2=0, где g1, g2 - функции выигрыша игроков) в нормальной форме (т.е. в игре стратегии представляют собой разовый выбор) называется антагонистической игрой. {X, Y, F(x, y)}X - мн-во чистых стратегий 1-го игрока, Y - мн-во чистых стратегий 2-го игрока, F(x, y) - вещественно - значная функция выигрыша одного игрока в ситуации (x, y). Поведение игроков в антагонистической игре определяется принципом гарантированного результата. Границы возможностей игроков определяется значением нижней и верхней цен игры. = -нижняя цена игры. = - верхняя цена игры. Первый игрок гарантирует себе выигрыш не меньше цены игры, независимо от действий второго игрока. Второй игрок гарантирует себе проигрыш не больше верхней цены, не зависимо от действий первого игрока. Если игроки разумны, то выигрыш первого игрока лежит в отрезке [ , ]. В силу соотношения между minmax и maxmin ≤ . и могут быть " +" и " -". Возможны две ситуации: 1. Стратегии x0, y0, которые реализуют верхнюю и нижнюю цену называются оптимальными. (x0, y0) - седловая точка F(x, y). 2. , следовательно, решения в чистых стратегиях не существует. В этой ситуации решение ищется в смешанных стратегиях. Матричные игры. Конечная (т.е. все игроки имеют конечное число стратегий) антагонистическая игра называется матричной игрой.{X, Y, F(x, y)}X®N, Y®N; F(i, j) i=1, 2, …, n - номер чистой стратегии первого игрока; j=1, 2, …, m - номер чистой стратегии второго игрока; F(x, y)=A=(aij) - матрица выигрышей 1-го игрока.

= = ≤ 1. - цена i0, j0 - оптимальные стратегии игроков.{(i0, j0), V} - оптимальное решение матричной игры в чистых стратегиях.

-седловая точка матрицы (т.е. maxв строке и min в столбце)

2. , следовательно, решения в чистых стратегиях не существует. В этой ситуации решение ищется в смешанных стратегиях. Смешанной стратегией 1-го игрока называется n-мерный вектор p=(p1, p2, …, pn) с неотрицательными компонентами рi≥ 0, сумма которых = 1. рi - вероятность выбора первым игроком i-ой чистой стратегии. Совокупность этих векторов определяет множество смешанных стратегий 1-го игрока - Sn (выпуклое, замкнутое, ограниченное подмножество n-мерного евклидова пространства Еn). Смешанной стратегией 2-го игрока называется m-мерный вектор q=(q1, q2, …, qm) с неотрицательными компонентами qj≥ 0, сумма которых = 1. qj - вероятность выбора вторым игроком j-ой чистой стратегии. Совокупность этих векторов определяет множество смешанных стратегий 2-го игрока - Sm (выпуклое, замкнутое, ограниченное подмножество m-мерного евклидова пространства Еm). Функция выигрыша первого игрока h(p, q) на множестве смешанных стратегий определяется как мат. ожидание: h(p, q)=∑ ∑ aijpiqj { Sn, Sm, h(p, q)} - определяет смешанное расширение матричной игры. = = . Теорема фон Неймана. Любая матричная игра имеет цену в смешанных стратегиях, а игроки оптимальные смешанные стратегии. (*)Доказательство: Sn, Sm - выпуклые, замкнутые, ограниченные подмножества пространства Еm и Еn, h(p, q)- непрерывная и линейная по каждому аргументу функция, а, следовательно, вогнуто - выпуклая на Sn х Sm (прямом произведении). Тогда по теореме о существовании седловой точки у вогнуто - выпуклой функции существует такая точка (p0, q0), что выполняется: h(p, q0)≤ h(p0, q0)≤ h(p0, q), p принадлежит Sn, q принадлежит Sm, а по теореме о Н и Д условиях существования седловой точки, точка (p0, q0) реализует соотношение (*). Н и Д условия оптимальности стратегии. Th: пусть V - цена игры, чтобы стратегия р0 была оптимальной для 1-го игрока Н и Д выполнение условий: h(p0, q)≥ V, q принадлежит Sm; h(p, q0)≤ V, p принадлежит Sn - условие, при котором q0 является оптимальной стратегией для 2-го игрока. Следствие: пусть V - цена игры, тогда чтобы p0 была оптимальной стратегией первого игрока Н и Д, чтобы h(p0, j)≥ V, q0 была оптимальной стратегией второго игрока - h(i, q0)≤ V Th: для того чтобы V было ценой игры, а р0 и q0 - оптимальными стратегиями игроков Н и Д выполнение соотношения: h(p, q0)≤ V≤ h(p0, q) (q принадлежит Sm, p принадлежит Sn). Свойства оптимальных стратегий: пусть р0 и q0 - произвольные оптимальные стратегии игроков, а V - цена игры. pi0> 0 h(p0, j) = V, qj0> 0 h(i, q0) = V имеет место равенство: min h(p0, j) = max h(i, q0) = V Следствие: если существует цена игры в чистых стратегиях, то она совпадает с ценой игры в смешанных стратегиях, которая существует всегда. Вектор α (α 1, α 2, …, α n) доминирует вектор β (β 1, β 2, …,), если α i ≥ β i (i=1, 2, …, n) и строго доминирует, если α i > β i.Некоторая линейная комбинация α 1, α 2, …, α n доминирует (строго доминирует) вектор β, если существует λ i ≥ 0 (i=1, 2, …, k), ∑ λ i=1, что вектор ∑ α i λ i доминирует (строго доминирует) вектор β. Th: (доминирования) Если i-ая строка матрицы игры доминируется некоторой линейной комбинацией остальных строк, то существует такая оптимальная стратегия p0 для первого игрока, i-ая компонента которой = 0 (pi0=0). Если i-ая строка матрицы игры строго доминируется некоторой линейной комбинацией остальных строк, то для любой оптимальной стратегии первого игрока i-ая компонента = 0 (pi0=0).Если j-ый столбец доминирует (строго доминирует) некоторую линейную комбинацию остальных столбцов, то существует (для любого) q0, qj0=0. Преобразование матрицы выигрышей: преобразование основано на доминировании строк и столбцов матрицы, прибавление некоторого числа ко всем элементам матрицы A=(aij), i=1, 2, …, n, j=1, 2, …, m; A! =(aij+ α). Оказывается, что в этом случае V! =V+α, а оптимальные стратегии игроков совпадают (эта операция позволяет свести игру к положительно определенной матрице), 3. умножение элементов матрицы на одно и тоже число A=(aij), i=1, 2, …, n, j=1, 2, …, m; A! =(α aij), V! = α V, оптимальные смешанные стратегии игроков совпадают (эта операция позволяет избавиться от дробных элементов матрицы или уменьшить значение элементов). Th: пусть А и А! - матричные игры (n x m), причем А! = α А+В, В=(β) m x n, тогда V! = α V+ β, а оптимальные стратегии игроков совпадают. Графический метод. Рассмотрим игры 2 x m (n x 2). Оптимальная смешанная стратегия первого игрока может быть полностью описана вероятностью выбора первой чистой стратегии р, поэтому множество оптимальных стратегий для первого игрока - это точка, либо отрезок на [0, 1] (либо весь отрезок [0, 1]). В соответствии с теоремой о свойствах оптимальных стратегий Строим m линейных функций, затем выделяем нижнюю огибающую, что соответствует операции взятия min, на которой находим точку max. Абсцисса дает р0, а ордината - значение цены игры. Нижняя огибающая - кусочно - линейная функция, следовательно, для точки max возможны следующие ситуации:

1.

k1, k2-угловые коэффициенты

qj10=1

qj0=0, для любого j≠ j1

3. бесконечное множество решений для первого игрока, для второго - qj0=1

Для n х 2 аналогично (но находиться верхняя огибающая, ищется точка min).

Метод Шепли-Сноу. При решении игр 2 x m (n x 2) было обнаружено св-во: у второго игрока (у первого) существует оптимальная стратегия, которая также содержит не более двух четных. Это свойство в обобщенном виде справедливо и для игры n x m. Множество оптимальных смешанных стратегий игроков представляет собой выпуклые, замкнутые, ограниченные многогранники, а многогранник определяется конечным числом своих крайних точек, т.е. вершин, поэтому, чтобы определить мн-во оптимальных стратегий, Д найти крайние точки мн-ва оптимальных стратегий. Th Шепли-Сноу: все крайние оптимальные стратегии p0, q0 и цена игры с платежной матрицей А должны удовлетворять какому-либо из уравнений: S(s=1, r)aij+p⁰_i=V, t=1, r; S(t=1, r)aij+p⁰_j=V, s=1, r;

Матрица (aisjt) получается из матрицы А вычеркиванием некоторого количества строк и столбцов. Причем, р0i=0 (для вычеркнутых строк) для любого i принадл. 1, …, n\{i1, i2, …, ir}q0j=0 (для вычеркнутых столбцов) для любого j принадл. 1, …, m\{j1, j2, …, jr}.При этом, если V≠ 0, то матрица (aisjt) невырожденная.

Алгоритм нахождения оптимальных стратегий методом Ш-С: целесообразно, если это возможно, уменьшить размерность матрицы, при этом, если ищется полное решение, то вычеркиваются только строгодоминируемые строки и столбцы в полученной матрице перебрать все квадратные подматрицы не ниже второго порядка, для каждой из них решить соответствующую систему уравнений, при этом, если V≠ 0, то соответствующая система имеет единственное решение, либо не имеет решений из 2-го пункта следует, что ситуация простая в случае невырожденности матрицы А, поэтому исходную игру следует свести к игре с заведомо ≠ 0 цене игры а! ij= аij+μ μ > max{| аij |: аij ≤ 0}4)полученное решение проверить на неотрицательность и на выполнение условия оптимальности h(p0, j)≥ V, h(I, q0)≤ V 5. найденные решения являются оптимальными, но не обязательно крайними, т.к. Th является Н условием крайности. Полный перебор квадратных подматриц приводит к нахождению оптимальных стратегий, включающих в себя и крайние 6.выпуклая оболочка всех найденных оптимальных стратегий дает нам множество оптимальных стратегий игроков. Метод Брауна. Метод дает приблизительное решение. Идеи метода: разыгрывается мысленный эксперимент, в котором игроки А и В применяют друг против друга свои стратегии. Начинается эксперимент с того, что один из игроков, скажем А, выбирает произвольно одну из своих чистых стратегий, например i1, противник отвечает той своей стратегией j1, которая уменьшает выигрыш игрока. дальше очередь А: он отвечает на стратегию игрока В той своей стратегией i2, которая дает максимальный средний выигрыш при стратегии j1. затем очередь В: он отвечает на стратегии i1 и i2 той стратегией j2, которая дает наименьший средний выигрыш при этих двух стратегиях и т.д. на каждом шаге итерационного процесса каждый игрок отвечает на каждый ход противника той своей стратегии, которая является оптимальной относительно всех его предыдущих шагов рассмотренных как смешанная стратегия, в которой чистые стратегии представляются в пропорциях соответствующих частоте их применения.V=(V*+V*)/2 - средний выигрыш; V*=(V*(k))/k - min накопленный выигрыш за n партий; V*=(V*(k))/k - max накопленный выигрыш за n партий; k - число шагов

При увеличении числа итераций V, V*, V* будут приближаться к цене игры. Преимущества метода: объем и сложность вычислений сравнительно слабо возрастают по мере увеличения числа стратегий. Сходимость данного итерационного процесса очень медленная, не монотонная, поэтому задают точность решения, т.е. выбирают " +" ε и прекращают процесс, если разность между min V*(k) и max V*(k)≤ 2ε. Связь матричных игр с линейным программированием. Прямая и двойственная задача, теорема двойственности. Решение матричной игры с платежной матрицей А=(аij) аij> 0, i=1, …, m, j=1, …, n эквивалентно решению пары двойственных ЗЛП следующего вида:

min∑ xi ­­­­xi≥ 0(i=1, …, m) ∑ a­­ijxi≥ 1 (j=1, …, n)

max∑ yj yj≥ 0(j=1, …, n) ∑ a­­ijyj≤ 1 (i=1, …, m)

Другими словами, если х0=(х01, х02, …, х0n), y0=(y01, y02, …, y0n) - решение соответствующей ЗЛП, то V=1/∑ x0i =1/∑ y0j; p0=Vx0, q0=Vy0 - решение матричной игры.

Если p0, q0- оптимальные стратегии игроков, V- цена игры, то x0=p0/V, y0=q0/V- решение двойственной задачи.Любой ЗЛП, которую будем считать прямой или исходной можно поставить в соответствие другую, которую двойственной. Обе эти задачи образуют пару двойственных задач.Th двойственности (она позволят установить взаимосвязь между оптимальными решениями пар двойственных задач, используя их можно решить любую задачу из пары и не решая вторую сразу указать ее оптимальное решение и оптимальное значение или установить отсутствие оптимального решения) если одна из пары двойственных задач имеет оптимальное решение, то и двойственная к ней также имеет оптимальное решение, причем значение целевых функций на обоих оптимальных решениях совпадают. Если одна из пары двойственных задач не имеет решения ввиду несовместности системы ограничений, то вторая задача не имеет решения в виду неограниченности целевой функции и наоборот.