Основные понятия и определения теории игр
Методические указания к контрольной работе №1 по дисциплине
Новочеркасск ЮРГТУ (НПИ) УДК 519.24 (076.5) Рецензент канд. техн. наук, доц. В.Ф. Петров
Гузыкина Т.Н. Матричные игры: Метод. указания к контрольной работе № 1 по дисциплине “Теория игр и исследование операций” / Юж.-Рос. гос. техн. ун-т (НПИ). Новочеркасск: ЮРГТУ (НПИ), 2003. 32 с. Указания содержат теоретический материал, примеры решения типовых задач, варианты заданий по дисциплине “Теория игр и исследование операций”.
Предназначены для студентов специальности 03210.00 - “Математика с дополнительной специальностью информатика” заочной формы обучения.
ã Южно-Российский государственный ã Гузыкина Т.Н., 2003 ОГЛАВЛЕНИЕ
1. ТРЕБОВАНИЯ К СОДЕРЖАНИЮ И ОФОРМЛЕНИЮ
Контрольная работа состоит из семи задач. Вариант задания выбирается студентом самостоятельно так, что последняя цифра номер зачетной книжки студента соответствует индексу платежной матрицы в задачах 1-7. Результатом решения матричной игры являются вектора оптимальных стратегий и цена игры; для задачи 1 указываются верхняя и нижняя чистая цена игры, максиминная и минимаксная стратегии, седловая точка. Алгоритм решения игры 2´2 предполагает, что обе стратегии игроков активные, поэтому прежде чем решать задачу 2 в смешанных стратегиях следует убедиться, что решение в чистых стратегиях отсутствует. Применение свойства доминирования для сокращения размерности матрицы допускается только в задаче 6. В задачах 3, 4 поле рисунка по горизонтальной оси определяется отрезком [0,1]; на рисунках указываются: оптимальные вероятности принятия игроками своих первых стратегий, цена игры. В задаче 6 приводятся задачи линейного программирования (ЗЛП) для обоих игроков; решение игры находится по ЗЛП для игрока А или для игрока В с использованием двойственных оценок.
ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ ИГР Определение 1. Теория игр – теория математических моделей принятия оптимальных решений в условиях конфликта интересов участников игры и неопределенности внешних условий. Определение 2. Конфликтная ситуация – ситуация в практической деятельности людей, когда два или несколько участников, имея различные цели и средства их достижения, пытаются достичь результата в условиях, когда никто из них полностью не влияет на ход событий. Замечание 1. Участник конфликта принимает решения не на основании объективных обстоятельств, а на основании своих субъективных представлений о них, т.е. имеет место неполное представление об обстановке к моменту принятия решения. Замечание 2. Участник конфликта располагает только набором вариантов обстоятельств, в которых следует принимать решения. При этом ему не известны ни вероятностные характеристики факторов, влияющих на обстоятельства, ни их вероятностное распределение на множестве вариантов; таким образом, он действует в условиях неопределенности.
Определение 3. Игровая модель – формальная модель принятия решений в условиях неопределенности, когда у принимающего решения субъекта имеется некоторый противник, уточняющий неизвестные варианты таким образом, чтобы поставить субъекта в наихудшее положение. Определение 4. Понятие оптимальности в теории игр (ТИ) интерпретируется как объективная разумность, выгодность, целесообразность, справедливость, осуществимость, устойчивость. Выбор принципа оптимальности производится в соответствии с конкретной постановкой задачи, формализуемой игровой моделью; принцип оптимальности должен быть реализуем. Предметом формального моделирования ТИ являются разумные действия лиц и коллективов, объединенных по какому-либо признаку, имеющих различные интересы и преследующих различные цели в условиях конфликта и неопределенности. Определение 5. Совокупность правил и условий, оговоренных игроками, называется игрой, каждая их конкретная реализация – партией. Определение 6. Сумма, которую получает каждый игрок в результате игры, называется выигрышем;в случае, если выигрыш отрицательный, он интерпретируется как проигрыш. Определение 7. Набор правил, однозначно определяющих действия игрока во всех возможных случаях развития игры называется стратегией. Определение 8. Принятие игроком в процессе игры того или иного решения и его реализация называется ходом; если ход выбирается случайным образом, то он называется случайным, в противном случае – личным. Определение 9. Формализованное правило, согласно которому можно определить выигрыш каждого игрока в конкретной ситуации, т.е. в зависимости от стратегий, выбранных игроками, называется платежной функцией игры. Основные признаки, по которым производится классификация игр, следующие: количество игроков, количество стратегий, характер взаимоотношений, характер выигрышей, вид функции выигрыша, количество ходов, состояние информации.
Определение 10. Игра, в которой принимают участие два игрока(n =2) называется парной, при n >2 – множественной (игры одного игрока в ТИ не рассматриваются). Определение 11. Если в игре каждый из игроков имеет конечное число стратегий, то игра – конечная, если хотя бы один из игроков имеет бесконечное число стратегий – бесконечная. Определение 12. Игры, в которых игроки не могут вступать в коалиции, называются бескоалиционными, в противном случае – коалиционными; если коалиции определены априори, игра называется кооперативной. Определение 13. Если сумма выигрышей всех игроков в каждой партии игры равна нулю, то такая игра называется игрой с нулевой суммой. Частный случай при n =2: парная игра с нулевой сумой называется антагонистической, т.к. выигрыш А равен проигрышу В. Определение 14. Конечная парная игра с нулевой суммой называется матричной игрой; функция выигрыша первого игрока задается в виде матрицы, у которой строки – стратегии первого игрока, столбцы – стратегии второго. Такая матрица называется платежной матрицей игры. Определение 15. Конечная игра двух игроков с ненулевой суммой называется биматричной; функции выигрышей задаются для обоих игроков в виде их платежных матриц. Выделяются и другие классы игр по виду функции выигрыша. Определение 16. Игры, оканчивающиеся после одного хода – одношаговые, иначе – многошаговые. Определение 17. Если игроку известны все предыдущие ходы, то игра называется с полной информацией; иначе – с неполной. Перечисленные виды игр и приведенные признаки их классификации не являются полными; существуют и другие виды игр и системы их классификации. МАТРИЧНЫЕ ИГРЫ
3.1. Принцип максимина; решение игры в чистых стратегиях
Теория игр обосновывает выбор принципов оптимальности поведения игроков и разрабатывает алгоритмы нахождения оптимальных стратегий и выигрышей игроков. Признаками игровой ситуации являются: наличие конфликта интересов, неполнота и неопределенность информации. Такие условия вынуждают участника игры действовать по логике расчета на наихудшую реализацию неизвестных условий, выбирая из наихудших реализаций лучшую. В качестве принципа оптимальности поведения игроков в матричных играх, выработанного теорией игр, служит принцип устойчивости, когда отклонение от оптимального поведения невыгодно ни одному игроку при условии, что другой действует оптимальным образом.
Пример 1. Рассмотрим следующую игровую ситуацию: два игрока выбрасывают 1, 2, 3, 4, 5 пальцев руки.Если сумма нечётная, первый игрок выигрывает сумму очков, равную количеству пальцев, выброшенных обоими игроками; если сумма чётная – второй выигрывает такую же сумму очков. Решение Количество стратегий игроков n = m = 5. Запишем стратегии игроков: Ai = {игрок А выбросил i пальцев}, Bj = {игрок B выбросил j пальцев}, Платежная матрица игры имеет следующий вид:
Опишем логику поведения игроков, учитывая антагонизм интересов игроков, вынуждающий каждого из них рассчитывать на сильное противодействие другого. Первый игрок старается максимизировать свой выигрыш в условиях неопределённости, создаваемой антагонистическими действиями второго игрока. В этом случае игрок А для каждой своей стратегии i определяет свой гарантированный выигрыш, т.е. выигрыш в худшей для себя ситуации
Т.к. выбор любой стратегии в его распоряжении, чтобы максимизировать свой гарантированный выигрыш игрок А из гарантированных выигрышей по стратегиям выбирает максимальный:
Определение 18. Величина Определим нижнюю чистую цену игры и максиминные стратегии для примера 1: максиминные стратегии - А1, А2. Второй игрок старается минимизировать свой проигрыш в условиях противодействия игрока А. Поэтому игрок В для каждой своей стратегии j определяет свой гарантированный проигрыш, т.е. то, что он вынужден будет заплатить при самом неблагоприятном поведении А:
Т.к. он волен выбирать любую свою стратегию, он, естественно, выбирает ту, что минимизирует его проигрыш:
Определение 19. Величина β, рассчитанная по (2), называется верхней чистой ценой игры и интерпретируется как минимальный гарантированный проигрыш В;cтратегия Определим верхнюю чистую цену игры и минимаксные стратегии для примера 1:
Определение 20. Решением игры называется процесс нахождения оптимальных стратегий игроков и цены игры и ценой матричной игры называется выигрыш игрока А (или проигрыш В). Определение 21. Если для чистых максиминной и минимаксной стратегий выполняется равенство α = β при - стратегии - точка (iо, jо) называется седловой точкой; - элемент Пусть игроки А и В в матричной игре с платёжной матрицей Образуем векторы Определение 22. Вектора Определение 23. Формализованное правило, согласно которому можно определить выигрыш каждого игрока в конкретной ситуации, т.е. в зависимости от стратегии, выбранной данным игроком и остальными участниками игры, называется платежной функцией игры. Определим платёжную функцию матричной игры по схеме: 1. Введем случайные величины ξ, η такие, что
2. Образуем систему случайных величин ξ и η - (ξ, η) или вектор, компонентами которого являются значения случайных величин ξ и η. 3. Введем функцию системы случайных величин ν такую, что она принимает значение элемента платежной матрицы, если случайная величина ξ=i и случайная величина η=j:
Таким образом, значение случайной функции ν есть величина выигрыша игрока А (проигрыша игрока В) при различных стратегиях игроков. 4. Найдем средний выигрыш игрока А как математическое ожидание функции двух случайных аргументов:
Игроки А и В выбирают стратегии тайно и независимо друг от друга, следовательно, случайные величины ξ и η независимы, поэтому можно записать:
Тогда (4) запишется в виде
Определение 24. Функция вида Определение 25. Стратегии
Условие (5) означает, что при каждой неоптимальной стратегии игрока Примем без доказательства теорему, показывающую связь седловой точки с ценой игры и оптимальными стратегиями. Теорема 1. Для того чтобы точка (i0, j0) была седловой, необходимо и достаточно, чтобы чистые стратегии Следствие из теоремы 1: если платёжная матрица А имеет седловую точку, то обязательно существуют оптимальные чистые стратегии; если седловой точки нет, то оптимальные стратегии могут быть только смешанными.
3.2. Решение матричной игры в смешанных стратегиях Определение 26. Стратегии Исходя из того, что стратегии представляют собой полную группу событий, выполняется условие нормировки: Примем без доказательства следующую теорему. Теорема 2. Для того чтобы смешанные стратегии игроков были оптимальными, необходимо и достаточно выполнение условий:
Т.е. выигрыш игрока А при его оптимальной стратегии Определение 27. Чистые стратегии называются активными, если в оптимальной смешанной стратегии их вероятности не равны нулю. Пусть, например, оптимальная стратегия игрока А имеет вид
Примем без доказательства следующую теорему. Теорема 3. Если первый из игроков придерживается своей оптимальной смешанной стратегии, а второй игрок выбирает любую активную стратегию, то выигрыш первого игрока равен цене игры; аналогично для второго игрока:
Здесь 3.2.1. Решение игры 2 Найдем оптимальную стратегию игрока А. В соответствии с теоремой 3 применение игроком А оптимальной стратегии
Здесь s – количество активных стратегий игрока В. Рассмотрим игру, в которой m = n =2 с платежной матрицей Очевидно, что число активных стратегий игрока B – s = 2. С учетом этого (6) запишется в виде для для Из (7) получим
Тогда
Здесь r – количество активных стратегий игрока А. Запишем условие (8) для случая игры 2´2, когда n = r = 2. Будем иметь при для для Из (9) получим
Тогда
3.3. Графоаналитический метод решения матричных игр 3.3.1. Решение игры 2 ´ n Для игры 2´n имеем платежную матрицу вида Количество стратегий игрока А – m = 2 и вектор стратегий имеет вид
Графически х* будет наивысшей точкой ломанной Тогда вектор оптимальных стратегий игрока В имеет вид по правилу игры 2´2:
Графическая иллюстрация рассуждений приведена на рис. 1. Рис.1 Пример 2. Для игры с платежной матрицей
Решение 1. Запишем lj (x) = a1j · x + a2j ·(1 -x), l1 (x) = 1· x - 1· (1 -x) = 2· x- 1, l2 (x) = 4· x - 2 · (1 -x) = 6· x- 2, l3 (x) = 0· x + 1· (1 -x) = -x+ 1, l4 (x) = -1· x + 5· (1 -x) = -6· x+ 5. 2. верхняя точка нижней огибающей x * есть точка пересечения 3. Найдём численное значение вероятности принятия игроком А первой стратегии, т.е. точку пересечения l3 (x) и l4 (x)из условия 2 x* -1 = -x* + 1, x* = 2/3,тогда 4. Найдём цену игры V* = l3 (x*) = l4 (x*) = 2 · 2/3 – 1 = 1/3. 5. По активным стратегиям игрока В для платёжной матрицы А '=
Ответ:
Случай 1. Рассмотрим случай, когда
Цена игры j (x*) = V ( Случай 2: Если
3.3.2 Решение игры m´2 Для игры m´2 платёжная матрица имеет вид
Положим q1= y, q2 = 1-y, тогда если игрок А выбрал чистую стратегию Аi, то проигрыш игрока В является линейной функцией у; для фиксированного i имеем
Таким образом, каждой стратегии игрока А - Аi, соответствует прямая hi Введём в рассмотрение функцию Y(у) вида Y(у) = Игрок В стремится минимизировать свой проигрыш, поэтому он должен выбирать свою оптимальную стратегию
Графически у* будет наинизшая точка ломаной
Решение игры m´2 аналогично решению игры 2´n: 1) 2) точка у* есть точка пересечения стратегий s и r; значения у* находятся из соотношения 3) активные стратегии игрока А - Аs и Аr; по формулам (11) находим ps*, pr* и
Случай 1. Точек минимума на [ a,b ] – множество (рис. 7), тогда для игрока В имеет множество решений
a)
Пример 3. Для игры с платёжной матрицей
Решение 1. Запишем hi (у) = ai 1· у + ai 2· (1 -у), h 1(у) = 4· у + 3· (1- у) = у + 3, h 2(у) = 2· у + 4· (1- у) = -2· у+ 4, h 3(у) = 0· у + 5· (1- у)= -5· у+ 5, h 4(у) = -1· у + 6· (1- у) = -7· у+ 6.
Нижняя точка верхней огибающей у* есть точка пересечения hi (у) = hi (у), поэтому активными стратегиями игрока А являются А 1 и А 4, т.е. s =1, r =4. 3. Найдем из соотношения h 1(у*) = h 4(у*)или у*+ 3 = -7 у* + 6: у* = 3/8; 4. Найдем цену игры 5. По активным стратегиям игрока А для платежной матрицы А'= Ответ: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
12 |