Игры с полной/неполной информацией

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

Любая игра в экстенсивной форме может быть представлена игрой в нормальной форме (не обязательно эквивалентной). Представление игры в нормальной форме может быть использовано для нахождения доминируемых стратегий.

Формальное представление

— множество игроков

У каждого игрока имеется конечный набор чистых стратегий S_i

Исход игры — это комбинация чистых стратегий каждого игрока:

где

Функция полезности i -го игрока (функция платежа):

Def.: В нормальной форме игра представляется как множество:

где:

— множество множеств чистых стратегий каждого игрока,

— множество функций платежей для каждого игрока

Решение матричных игр: доминирование строк и столбцов.

Матричную игру можно упростить, выявив доминирование одних стратегий над другими. Рассмотрим такую ситуацию.

Для игры с платёжной матрицей рассмотрим две стратегии игрока А – и такие, что

Стратегия называется доминирующей, а стратегия − доминируемой.

Если для той же матричной игры рассмотреть две стратегии игрока В - и такие, что

то стратегия называется доминирующей, а стратегия − доминиру-емой.

Если в платёжной матрице есть одинаковые строки (столбцы), то соответствующие стратегии игрока А (игрока В) называются дублирующими.

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

45. Решение матричных игр: аффинные преобразования.

Определение. Преобразование плоскости называется аффинным, если

· оно взаимно однозначно;

· образом любой прямой является прямая.

Преобразование называется взаимно однозначным, если

· разные точки переходят в разные;

· в каждую точку переходит какая-то точка.

Однородные координаты

Определение. Однородные координаты — координаты, обладающие тем свойством, что определяемый ими объект не меняется при умножении всех координат на одно и то же число.

Однородными координатами вектора (х, у) является тройка чисел (x', y', h), где х = х' / h, у = y'/h, а h — некоторое вещественное число (случай, когда h = 0 является особым).

Прим. Данные координаты не позволяют однозначно задать точку плоскости. Например, (1, 1, 1) и (2, 2, 2) задают одну и ту же точку (1, 1). Предлагается взять набор (x, y, 1), который будет описывать все точки плоскости.

Матрица преобразования для однородных координат имеет размер 3х3. Рассмотрим некоторые преобразования в однородных координатах.

Сжатие/растяжение

Это преобразование умножает соответствующие координаты точек на коэффициенты масштабирования по осям: (x, y) -> (a_x * x, a_y * y). Матрица преобразования запишется следующим образом:

[ a_x 0 0 ]

[ 0 a_y 0 ]

[ 0 0 1 ]

Где a_x – растяжение по оси x,

a_y – растяжение по оси y.

Прим. Можно заметить, что при отрицательных значениях коэффициентов сжатия/растяжения происходит отражение относительно соответствующих осей. Этот случай можно включить в данное преобразование, а можно вынести в отдельное, сказав, что коэффициенты масштабирования принимают только положительные значения.

Поворот

Матрица поворота 2x2 была подробно разобрана ранее. Теперь она дополняется строкой и столбцом:

[ cos(phi) sin(phi) 0 ]

[ -sin(phi) cos(phi) 0 ]

[ 0 0 1 ]

Прим. При угле phi = п эта матрица задает центральную симметрию относительно начала координат, которая является частным случаем поворота. Можно заметить, что такую симметрию можно задать с помощью преобразования сжатия/растяжения (допуская отрицательные коэффициенты масштабирования).

Параллельный перенос

Исходный вектор (x, y) переходит в (x + tx, y + ty). Матрица преобразования запишется следующим образом:

[ 1 0 0 ]

[ 0 1 0 ]

[ t_x t_y 1 ]

Отражение

Как говорилось в примечании к преобразованию сжатия/растяжения, отражения получаются следующим образом:

[ -1 0 0 ]

[ 0 1 0 ]

[ 0 0 1 ]
отражение относительно оси x

[ 1 0 0 ]

[ 0 -1 0 ]

[ 0 0 1 ]
отражение относительно оси y

Общий вид аффинного преобразования

Матрица 3x3, последний столбец которой равен (0 0 1)^T, задает аффинное преобразование плоскости:

[ * * 0 ]

[ * * 0 ]

[ * * 1 ]

По одному из свойств, аффинное преобразование можно записать в виде:

f(x) = x * R + t,

где R – обратимая матрица 2x2, а t – произвольный вектор. В однородных координатах это запишется следующим образом:

[ R_1,1 R_1,2 0 ]

[ R_2,1 R_2,2 0 ]

[ t_x t_y 1 ]

Если умножить вектор-строку на эту матрицу получаем результат преобразования:

[ x y 1 ] * [ R_1,1 R_1,2 0 ]

[ R_2,1 R_2,2 0 ]

[ t_x t_y 1 ]

=

[ x’ y’ 1 ] + [ t_x t_y 1 ]

При этом [ x’ y’ ] = R * [ x y ]

Прим. При аффинном преобразовании площади всех фигур изменяются в |R|. Т.о. аффинное преобразование представляется в виде композиции некоторого преобразования, задаваемого матрицей R, и параллельного переноса.

Матрица R определяет новый базис плоскости. Т.е. вектор (1, 0) переходит в (R_1,1, R_1,2), вектор (0, 1) переходит в (R_2,1, R_2,2). Новый базис это строки матрицы R.

Пример.

При отражении относительно оси y, базисный вектор по оси ординат сохраняется, а по оси абсцисс переходит в (-1, 0). Т.о. матрица R будет выглядеть следующим образом:

[ -1 0 ]

[ 0 1 ]

Теперь становится ясно, что кроме вышеперечисленных преобразований, с помощью аффинного преобразования можно получить скос: