Игровые задачи исследования операций

Предмет теории игр Теория игр представляет собой математическую теорию конфликтных ситуаций и математически объясняет явления, возникающие в условиях столкновения сторон Такие ситуации изучаются психологией, политологией, социологией, экономикой Цель теории игр выработка рекомендаций по разумному поведению участников конфликта

Каждая непосредственно взятая из практики конфликтная ситуация очень сложна, и ее анализ затруднен наличием привходящих, несущественных факторов конфликтующие стороны называются игроками, одно осуществление игры - партией, исход игры - выигрышем или проигрышем Чтобы сделать возможным математический анализ конфликта, строится его математическая модель, называемая игрой Человечество издавна пользуется такими формализованными моделями конфликтов - «играми» в буквальном смысле слова (шашки, шахматы, карточные игры и т. п) Отсюда и терминология теории игр:

Неформальное описание игры Всякая игра предполагает наличие некоторого числа n участвующих в ней лиц (игроков) наличие функции выигрыша: когда игра заканчивается, каждый игрок получает доход (если нет - значит, игрок проиграл), зависящий от его поведения и поведения других игроков чередование ходов, которые одновременно или последовательно делают игроки возможную недостаточность информации

Классификация игр По количеству игроков: игры с одним игроком (пасьянс) игра двух лиц (шахматы, муж с женой, две конкурирующие фирмы) игра трех лиц(преферанс, три фирмы на рынке) и т.д. По составу игроков: Бескоалиционные игры; Коалиционные игры. По выигрышу: антагонистические игры игры с нулевой суммой По количеству стратегий: Конечные игры; Бесконечные игры. По характеру получения информации: Игры в нормальной форме (игроки получают всю информацию до начала игры) Динамические игры (информация поступает в процессе игры)

Развитие игры во времени представляет собой ряд последовательных ходов участников При личном ходе игрок сознательно выбирает и осуществляет тот или другой вариант действий (пример любой ход в шахматах) При случайном ходе выбор осуществляется не волей игрока, а каким-то механизмом случайного выбора (бросание монеты, игральной кости, вынимание карты из колоды и т. п.) Ход - выбор игроком одного из предусмотренных правилами игры действий и его осуществление Ходы бывают личные и случайные: Некоторые игры (чисто азартные) состоят только из случайных ходов ими теория игр не занимается

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

Описание игры как последовательности ходов носит название позиционной формы игры С позиционной игрой связывают понятие топологического дерева или дерева игры: оно представляет собой конечную совокупность узлов, называемых вершинами, соединенных ребрами, притом так, что получается связанная фигура, не содержащая простых замкнутых фигур А – начальная вершина (позиция) В,С – промежуточные вершины (позиции) Х - окончательная

Под позиционной игрой n лиц понимают следующее: 1) топологическое дерево Г с выделенной вершиной А, называемой начальной позицией игры; 2) функция выигрыша, которая ставит в соответствие каждый окончательной позиции дерева некоторый n-мерный вектор (для n игроков); 3) разбиение множества всех неокончательных вершин (позиций) дерева Г на n+1 множество S 0, S 1, …, S n, которые называют множествами очередности. Множество S 0 соответствует началу (может быть связано со случайностью), S 1 – множество очередности для 1-го игрока и т.д; 4) вероятное распределение для каждой позиции из S 0 на множестве непосредственно следующих за ней позиций (т.е. из каждой позиции S 0 следуют варианты позиций с некоторой вероятностью); 5) разбиение множества S i для каждого i =1,n на подмножества S i j, называемые информационными множествами; при этом позиции из одного и того же информационного множества имеют одинаковое число непосредственно следующих за ними позиций (альтернатив), и никакая позиция не может следовать за другой позицией из того же самого информационного множества; 6) для каждого информационного множества S i j задано множество индексов I i j, взаимно однозначно отображающее множество альтернатив (возможных ходов) для каждой позиции из S i j Условие (1) устанавливает, что имеется начальная позиция. Условие (2) задает функцию выигрыша. Условие (3) разделяет множество неокончательных позиций на позиции с ходом случая ( S 0 ) и личные позиции, соответствующие каждому из n игроков ( S 1, …, S n ). Условие (4) задает схему рандомизации в каждой позиции случая. Условие (5) разбивает позиции каждого игрока на информационные множества (игрок знает лишь, в каком информационном множестве он находится, но не знает, в какой именно позиции этого множества).

Игра называется парной, если количество сторон (игроков) равно 2 Игра называется игрой с нулевой суммой, если проигрыш одного игрока равен выигрышу другого. В противном случае она называется игрой с ненулевой суммой Игра называется игрой с полной информацией, если результаты случайных ходов и предыдущих личных ходов полностью известны каждому игроку (например, шахматы, шашки – это игры с полной информацией, а карты – с неполной) Игра называется конечной, если число стратегий всех игроков является конечным

Нормальная форма игры С точки зрения максимизации доли каждого игрока в выигрыше i- й игрок стремится максимизировать i -ю компоненту функции выигрыша. Описание математического ожидания функции выигрыша при условии, что i- й игрок применяет стратегию x i, выражается в виде n-мерной таблицы n-мерных векторов В случае n=2 эта запись сводится к матрице, элементами которой являются пары вещественных чисел Такая n-мерная таблица называется нормальной формой игры

Пример 1. Игра в Орлянку 1-ый игрок выбирает решку P или орла O. Игрок 2, не зная выбора игрока 1, также выбирает P или O. Если оба противника совершают одинаковый выбор, то игрок 2 выигрывает у 1-го игрока очко, в противном случае игрок 1 выигрывает очко у игрока 2 Для игры в Орлянку нормальной формой игры является матрица Здесь каждая строка соответствует стратегии игрока 1, а столбец стратегии игрока 2

Ситуация равновесия Говорят, что ситуация (т.е. какой-нибудь n-набор стратегий) равновесна, если ни один игрок не имеет никаких разумных оснований для изменения своей стратегии при условии, что все остальные игроки собираются придерживаться своих стратегий В этом случае, если каждый игрок знает, как будут играть остальные, он имеет основания придерживаться той стратегии, которая соответствует этой ситуации равновесия Справедлива следующая теорема: Любая конечная игра n лиц с полной информацией имеет ситуацию равновесия

Пример 2 Для игры в нормальной форме как (α 1, β 1 ), так и (α 2, β 2 ), являются ситуациями равновесия Не каждая игра обладает ситуациями равновесия. Например, игра в Орлянку такой ситуации не имеет

Антагонистические игры Игры с нулевой суммой Игра с нулевой суммой представляет собой замкнутую систему: все то, что кто-нибудь выиграл, должно быть кем-то проиграно Игры двух лиц с нулевой суммой называются антагонистическими (строго конкурентными) В антагонистических играх нет никаких оснований для переговоров между игроками, так как если один выигрывает, то другой проигрывает Справедлива следующая теорема: Пусть (σ 1,σ 2 ) и ( τ 1, τ 2 ) – две ситуации равновесия антагонистической игры. Тогда (σ 1, τ 2 ) и ( τ 1,σ 2 ) также являются ситуациями равновесия.

Седловая точка Нормальная форма конечной антагонистической игры сводится к некоторой матрице А с числом строк, равным числу стратегий игрока 1 и с числом столбцов, равным числу стратегий игрока 2: A={a ij } mxn где а ij – величина выигрыша, если 1-й игрок выбирает стратегию i, а 2-й –стратегию j, m – число стратегий первого игрока, n – второго игрока. Ситуация (пара стратегий) будет равновесной тогда и только тогда, когда соответствующий ей элемент а ij является одновременно наибольшим в своем столбце и наименьшим в своей строке. Такая ситуация называется седловой точкой.

Пример 3 Матрица игры с седловой точкой: Матрица игры не имеет седловой точки

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

Смешанные стратегии Смешанная стратегия игрока есть вероятностное распределение на множестве его чистых стратегий. В случае, когда игрок имеет только конечное число m чистых стратегий, смешанная стратегия представляет собой m-мерный вектор х=(х 1,x 2,…х m ), удовлетворяющий условиям: Если игроки участвуют в игре с матрицей А и 1-й игрок выбирает смешанную стратегию x, а 2-й – y, то ожидаемый выигрыш будет равен или в матричных обозначениях Справедлива основная теорема матричных игр: Любая матричная игра имеет решение в смешанных стратегиях

Теорема о минимаксе Принцип минимакса: поступай так, чтобы при наихудшем для тебя поведении противника получить максимальный выигрыш, т.е. надо выбрать ту стратегию, при которой минимальный выигрыш максимален Справедлива теорема о минимаксе: Если игроки участвуют в игре с матрицей А, то где A j –столбец, а A i – строка матрицы A При использовании смешанных стратегий нижний выигрыш игрока 1 в точности равен верхнему проигрышу игрока 2 Общая величина этих двух чисел называется значением игры

Вычисление оптимальных стратегий Теорема о минимаксе гарантирует, что каждая антагонистическая игра имеет оптимальные стратегии. Она дает существование, но не определяет, как искать эти оптимальные стратегии

Вычисление оптимальных стратегий Доминирование: одна чистая стратегия (представленная своей строкой или столбцом) доминирует другую чистую стратегию, если выбор первой (доминирующей) стратегии, по крайней мере, не хуже выбора второй (доминируемой) стратегии, а в некоторых случаях и лучше. Простейшим является тот случай, когда существует седловая точка, т.е. когда существует элемент а ij, являющийся максимальным в своем столбце и минимальным в своей строке. Тогда чистые стратегии i и j (или, что равносильно, смешанные стратегии x и y, для которых х i =1и y i =1, а все остальные компоненты равны нулю) Отсюда следует, что игрок всегда может обойтись без доминируемых стратегий и использовать только недоминируемые стратегии.

Вычисление оптимальных стратегий Теорема. Значение симметричной игры равно нулю. Кроме того, если x есть оптимальная стратегия для игрока 1, то есть также оптимальная стратегия для игрока 2 Симметричные игры Квадратическая матрица А называется кососимметрической, если для каждого i и j а ij =- а ij Матричная игра называется симметричной, если ее матрица кососимметрическая

Игры с ограничениями Игра с ограничениями - игра, в которой допускаются не все смешанные стратегии (смешанные стратегии х и y соответственно должны выбираться из некоторых выпуклых многогранников) Если матрица игры А={a ij }, то задача игрока 1 - найти где множества Х и Y определяются неравенствами Аналогично, задача 2-го игрока – найти при тех же ограничениях на стратегии игроков Задача игрока 1 сводится к задаче максимизации: Задача игрока 2 сводится к задаче минимизации:

Бесконечные игры Смешанной стратегией игрока 1 будет последовательность (x 1,x 2,…), для которой. Смешанная стратегия игрока 2 - (y 1,y 2,…). Функция выигрыша при смешанных стратегиях (x,y): при условии, что ряд абсолютно сходится. Игры со счетным множеством стратегий Пусть а ij – выигрыш, получаемый 1-м игроком, при условии, что он выбирает i-ю чистую стратегию, а 2-й игрок - j-ю чистую стратегию.

Игры на квадрате Смешанная стратегия представляет собой вероятностное распределение на множестве чистых стратегий, которое может быть представлено функцией распределения: Каждый игрок имеет континуум чистых стратегий, обычно представляемых точками интервала [0,1]. Тогда чистая стратегия каждого игрока – число из этого интервала, а функция выигрыша A(x,y)определена на единичном квадрате.

Игры на квадрате Если игрок 1 использует F, а игрок 2 использует G, то имеем Если игрок 1 использует чистую стратегию x, а игрок 2 – смешанную стратегию F, то ожидаемый выигрыш равен интегралу Стильтьеса: Если игрок 2 использует чистую стратегию y, а игрок 1 смешанную стратегию F, то ожидаемый выигрыш В каждом случае считаем, что интегралы существуют

Игры с непрерывным ядром Для игр с непрерывным ядром оптимальные стратегии существуют Теорема 1. Если ядро А(х, y)– непрерывная функция, то sup inf и sup inf могут быть заменены на min max и max min соответственно. Теорема 2. Если ядро А(х, y)– непрерывно, то υ1=υ2

Вогнуто-выпуклые игры Говорят, что игра на квадрате вогнуто-выпукла, если ее ядро А(х, y) вогнуто по x при каждом значении y и выпукло по y при каждом значении x. Вогнуто-выпуклая игра должна иметь седлообразное ядро, и седловую точку в чистых стратегиях. Теорема. Пусть вогнуто-выпуклая игра А(х, y)непрерывна. Тогда она имеет оптимальные чистые стратегии.

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

Заключение Теория игр, как и всякая математическая модель, имеет свои ограничения Сознавая эти ограничения, можно разумно использовать аппарат теории игр как «совещательный» при выборе решения (подобно тому, как молодой, энергичный полководец может прислушаться к мнению умудренного опытом, осторожного старца)