Теория игр

Дисциплина «Теория игр»

Учебно-методическое обеспечение
Для успешного освоения дисциплины Вам необходимо изучить следующие учебные материалы:
1. Салмина Нина Юрьевна. Теория игр. Учебное пособие. Томск: Эль Контент, 2012. - 92 с.
2. Салмина Нина Юрьевна. Теория игр. Методические указания к лабораторным работам для
студентов направления 080500.62 "Бизнес-информатика". Методические указания. Томск:
ФДО, ТУСУР, 2012. - 26 с.
3. Салмина Нина Юрьевна. Теория игр. Электронный курс. "электронный курс в СДО"
4. Салмина Нина Юрьевна, Ехлаков Юрий Поликарпович. Теория игр. Методические указания
по организации самостоятельной работы. Методические указания. Томск : ФДО, ТУСУР,
2018. – 23 с.

Примечание: Доступ к материалам осуществляется из вкладки "Учебные материалы".

Контрольные мероприятия
По дисциплине «Теория игр» в течение семестра предусмотрены следующие контрольные
мероприятия:

Контрольная работа:
1. Компьютерная контрольная работа № 1.

Лабораторные работы:
1. Текстовая лабораторная работа № 1 «Конечные антагонистические игры». Задание на
лабораторную работу № 1 размещено: Методические указания к лабораторным работам (стр.
5). Лабораторная работа состоит из 11 вариантов. Выбор варианта осуществляется по общим
правилам.
2. Текстовая лабораторная работа № 2 «Кооперативные игры». Задание на лабораторную
работу № 2 размещено: Методические указания к лабораторным работам (стр. 16).
Лабораторная работа состоит из 18 вариантов. Выбор варианта осуществляется по общим
правилам.

Примечание: Доступ к контрольным и лабораторным работам осуществляется из вкладки "Аттестация". С правилами выполнения и оформления контрольных и лабораторных работ Вы можете ознакомиться в Гиде студента. Обратите внимание, что с 11.07.2018 на титульном листе отчетов необходимо указывать новое наименование министерства: Министерство науки и высшего образования Российской Федерации.

01.09.2018


ЛАБОРАТОРНАЯ РАБОТА № 1
Конечные антагонистические игры
Цель работы
Изучение моделей принятия решений в конфликтных ситуациях для антагонистических игр в нормальной форме и решения их различными методами: аналитическим, итерационным и методом линейного программирования.
Методические указания
В качестве инструментального средства для выполнения лабораторной работы используется автоматизированная система «Антагонистические игры» (файл Ant_games.exe).
Первоначально, до работы с системой, необходимо представить игру в нормальной форме. Для этого внимательно прочитайте описание игры, определите количество чистых стратегий для каждого игрока. Помните, что любая чистая стратегия — это правило, определяющее поведение игрока от начала до конца игры.
Особенно внимательно определяйте стратегии в многоходовых играх.
После того, как стратегии определены, строится платежная матрица игры. После этого матрица вводится через опцию меню «Ввод данных». Если выигрыши первого игрока можно записать в виде функции выигрыша (либо функция выигрыша сразу определена в варианте), то платежная матрица вводится формулой.
При вводе формулы нужно помнить следующее:
1) обязательно введите выражение “F(x)=” либо просто не стирайте его с экрана. Примечание: не вводите “F(x,y)=”! Конечно, функция зависит от двух аргументов (стратегий первого и второго игроков), но в шаблоне распознавателя формул левая часть уравнения выглядит именно так, как она записана на экране по умолчанию;
2) все правое выражение заключается в скобки, все символы вводятся большими буквами; умножение обозначается через символ ‘*’, деление — через символ ‘/’, возведение в степень —
через символ ‘^’, например формула x y ( 1) (x y) + ? + должна быть введена следующим образом:
F(x)=((-1)^(X+Y)*(X+Y))
3) под название встроенных функций отводится четыре позиции. Если функция обозначается тремя буквами, то четвертая позиция определяется пробелом, например:
F(x)=(SIN (X+Y))
4) обращайте особое внимание на расстановку скобок в сложных функциях: скобки определяют приоритеты операций по стандартной схеме приоритетов.
Введенные вами данные можно запомнить в файл. При необходимости, записанные ранее в файл данные можно считать из файла.
Введенная вами платежная матрица может быть при необходимости сокращена, если вы воспользуетесь пунктом меню «Сокращение матрицы».
Внимание! Если вы сокращаете матрицу, обратите внимание на то, какие именно столбцы и строки будут сокращены. В окончательном варианте представления решения оптимальные стратегии должны быть даны для исходной (несокращенной матрицы)!
Пункт меню «Методы» позволит вам выбрать нужный метод для решения поставленной задачи. Решение может быть произведено одним из трех методов: аналитическим, итерационным, методом линейного программирования (симплекс-метод).
Аналитический метод. Для решения задачи данным методом платежная матрица должна иметь размерность 2х2. В случае, когда размерность матрицы больше, чем два на два, система предупреждает о некорректном вводе данных.
Итерационный метод. Для решения задачи методом итераций пользователь должен ввести либо точность вычисления, либо количество итераций. Для игр с плохой сходимостью при высокой точности может потребоваться очень большое количество итераций. Система предупреждает, что идет процесс расчета, и предлагает немного подождать. При решении игры методом итераций необходимо:
1) определить требуемую точность вычислений и решить задачу методом итераций;
2) исследовать игру на сходимость: получить решение для разного количества итераций (например, для 50, 100, 200, 500, 999) и посмотреть, насколько изменяются результаты решения при различном количестве итераций: насколько быстро сходится игра.
После окончания работы метода итераций вы можете посмотреть результаты на экране и/или записать данные в файл. В системе полную информацию с результатами решений можно посмотреть также, выбрав опцию меню «Результаты/Результат итерационного».
Метод линейного программирования (симплекс-метод). При выборе опции меню «Методы/Симплекс» ваша задача будет решаться двухэтапным симплекс-методом. После окончания работы метода на экран выдается сообщение об успешном завершении вычислений. Результаты расчетов по симплекс-методу вы можете посмотреть на экране, а также записать в файл. В системе полную информацию также можно посмотреть, выбрав опцию меню «Результат/Результат симплекс».
Внимание! Окончательное решение симплекс-метода содержит оптимальные планы, а не оптимальные стратегии игроков. Чтобы получить окончательное решение, необходимо:
1) из окончательной симплекс-таблицы выбрать оптимальные стратегии игроков. Здесь задача решается для второго игрока, поэтому оптимальный план первого игрока определяется по дополнительным переменным из строки целевой функции, а оптимальный план второго игрока определяется по значениям основных переменных в базисе. Будьте внимательны! При выборе значений основных переменных обращайте внимание на базис, который определяет порядок их расположения в таблице. Если какая-либо основная переменная в базисе отсутствует, значит ее значение равно нулю;
2) определить цену игры, как обратное значение целевой функции (-Z);
3) перейти от оптимальных планов к оптимальным стратегиям. Для этого необходимо умножить эти планы на цену игры;
4) откорректировать при необходимости цену игры: в связи с тем, что для решения игры симплекс-методом исходная матрица делается положительной, то и цена игры выдается увеличенной на соответствующее число. В результатах решения указывается число, на которое была увеличена цена игры.
После проведения расчетов всеми указанными методами необходимо провести сравнительный анализ результатов. Прежде всего, определите, одинаковы ли оптимальные стратегии, полученные симплекс-методом и методом итераций. Различие между полученными стратегиями может быть:
а) незначительное, вызванное тем, что итерационный метод выдает решение лишь с какой-то точностью;
б) принципиальное, когда два метода дают абсолютно разные оптимальные стратегии.
Проанализируйте, какая ситуация сложилась в вашем случае. Если два решения принципиально различны, то ответьте на вопрос: какое из полученных решений удобнее применять на практике. Какое из решений лучше с точки зрения каждого игрока. Обоснуйте ваши рекомендации.

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

Вариант 2
Два игрока имеют на руках по 5 карт: шестерку, семерку, даму, короля и туза. «Стоимость» дамы — 3 очка, короля — 4 очка, туза — 1 очко. Шестерка и семерка стоят по номиналу. По старшинству карты располагаются следующим образом: 6<7<Д<К<T, но при этом Т<6 (старшинство «по кругу»). Игроки одновременно выкладывают на стол по одной карте. Выигрывает тот, у кого карта старше, причем выигрыш определяется суммой очков выложенных карт. Если оба игрока выложили на стол карты одинакового номинала, то никто из них ничего не выигрывает.

Вариант 3
Два игрока имеют по две белых и по две красных фишки. Оба выкладывают на стол произвольное количество фишек (или ни одной). Функция выигрыша первого игрока (проигрыш другого) определяется по количеству выложенных белых и красных фишек:
1 1 (x y )
2 2 J(x, y) ( 1) (x y ) + =? + ,
где 1 x , 1 y — количество белых фишек выложенных соответственно первым и вторым игроками;
2 x , 2 y — количество красных фишек выложенных соответственно первым и вторым игроками.

Вариант 4
Игроки 1 и 2 выбирают по числу из множества {1, 2, 3, 4, 5}, не зная, что выбирает другой. Игрок 1 выигрывает, если сумма выбранных чисел четная, и проигрывает игроку 2, если сумма нечетная. При этом сумма выигрыша определяется по формуле:
J(x, y) (x y) /10 = + ,
где x,y — числа, выбранные, соответственно, 1-м и 2-м игроками.

Вариант 5
В распоряжении 1-го игрока имеются четыре вида вооружений: A1, A2, A3, A4; у противника — 5 видов самолетов: B1, B2, B3, B4, B5. Задача первого игрока — поразить самолет, задача противника — сохранить его непораженным. Вооружением Ai самолет Bj поражается с вероятностью J(i, j) cos(i j) = + .

Вариант 6
Две девочки прячут по выбору 0, 1 или 2 конфеты. Каждая из них пытается угадать общее число конфет, спрятанных ими, причем угадывают они одновременно. Угадавшая правильно получает от другой одну конфету. Если обе угадали, или не угадал никто, то считается ничья.
Будем считать, что девочки достаточно умны, чтобы не выбирать заведомо проигрышный вариант. Например, если первая девочка спрятала 1 конфету, то она никак не скажет, что вместе
они спрятали 0 конфет, зная, что уже получается не меньше единицы.

Вариант 7
Полковник Блотто и его противник пытаются занять две позиции, распределив надлежащим образом свои силы. Все полки должны быть выставлены на позиции, причем может быть ситуация, когда на одной позиции выставлены все полки, а на другой — ни одного. Полковник имеет 4 полка, а его противник — три полка. Если на позиции у полковника Блотто полков больше, чем у его противника, то он получает все полки противника на этой позиции. Если на данной позиции у полковника меньше полков, то он теряет полки на этой позиции. Общий выигрыш равен сумме приобретенных/потерянных полков на обеих позициях.

Вариант 8
Дана антагонистическая игра между игроками А и В, в которой А — один человек, а В — команда из двух человек В1 и В2. Эти три человека изолированы друг от друга в отдельных комнатах и во время игры не могут общаться между собой. В начале игры судья входит в комнату, в которой находится А, и предлагает ему выбрать одно из чисел {1, 2, 3, 4}. Затем судья обходит В1 и В2 и предлагает им выбрать по числу из множества {1, 2, 3}. Если сумма всех выбранных чисел оказывается четной, выигрывает игрок А. Если сумма нечетная — выигрывает команда В. Сумма выигрыша определяется суммой выбранных чисел.

Вариант 9
Два игрока одновременно называют по одному целому числу из диапазона [1,6]. Если разница между двумя названными числами оказывается четной, выигрывает первый игрок, если нечетной — выигрывает второй. Если игроки назвали одинаковые числа — ничья. Величина выигрыша при этом определяется по формуле:
J(x,y) x y x y =++? ,
где x,y — числа, названные первым и вторым игроками соответственно.

Вариант 10
Двум мальчикам подарили по две конфеты — шоколадной и карамели. Они решили сыграть в следующую игру. Каждый из них прячет по одной конфете, а потом пытается угадать, какую конфету спрятал противник. Если оба угадали, или оба не угадали, то каждый остается при своих (ничья). Если угадал только один из них, то он получает от противника спрятанную тем конфету. Мальчики оценивают конфеты следующим образом: шоколадная — 5 единиц, карамель — 1 единица (оба предпочитают шоколад).

Вариант 11
Играют два игрока. Первый игрок выбирает одно из чисел — 1, 2, 3, 4, 5, 6, 7. Второй игрок пытается угадать, какое из чисел выбрал первый игрок. Если второй угадывает, то он получает от первого 10 очков, если нет — то второй игрок платит первому разницу между выбранным и названным числами (абсолютную).


ЛАБОРАТОРНАЯ РАБОТА № 2
Кооперативные игры
Цель работы
Изучение способов представления кооперативных игр, переходов от одной формы представления к другой; изучение методов решения указанных игр по различным критериям оптимальности с проведением сравнительного анализа полученных решений.

Методические указания
В данной лабораторной работе рассматривается кооперативная игра трех лиц в нормальной форме. Необходимо найти решение игры. В качестве решения будем рассматривать: С-ядро
игры, вектор Шепли, N-ядро игры.
Для упрощения многих расчетов и проверки правильности выполнения задания используйте программу «Принятие кооперативных решений» (файл «Коопер_игры.exe»).
Для нахождения решения прежде всего необходимо перейти от нормальной формы игры к форме характеристической функции.
Для определения характеристических функций коалиций необходимо решить 6 антагонистических игр. Характеристическая функция коалиции V(S) определяется как цена антагонистической игры, где в качестве первого (максимизирующего) игрока выступает коалиция S, а в качестве второго (минимизирующего) игрока выступает коалиция N/S. Здесь множество чистых стратегий коалиции S — это множество всех совместных чистых стратегий игроков данной коалиции. Причем элементами платежной матрицы являются суммарные выигрыши игроков из коалиции S .
Характеристическая функция максимальной коалиции N определяется как максимальное значение функции выигрыша всех трех игроков, определенной на множестве всех возможных
стратегий.
Программа позволяет либо ввести характеристическую функцию игры (если вы определили ее самостоятельно), либо рассчитать в программе.
Для расчета характеристической функции вы должны задать количество стратегий для каждого игрока и запомнить размерность. После этого вы должны ввести числовые значения стратегий игроков. Затем вы вводите формулу для расчета характеристической функции какой-либо коалиции (правила записи формулы такие же, как и в Лабораторной работе «Решение антагонистических игр»). В правой стороне окна есть помощь по вводу формул.

Внимание!!! Формулы для двойных и тройной коалиций вы должны получить сами путем сложения функций выигрышей тех игроков, которые входят в рассматриваемую коалицию!
После определения формулы вы должны определить коалиции: в левом поле указывается коалиция, для которой определяется характеристическая функция, в правом — коалиция из оставшихся игроков. Затем вы нажимаете кнопку «Рассчитать» и получаете платежную матрицу, а в нижней строке появляется значение характеристической функции соответствующей коалиции.
Для получения характеристической функции игры вы должны повторить процесс ввода формулы, коалиций и расчета.
Когда вся нижняя строка будет заполнена (определена вся характеристическая функция игры), необходимо нажать кнопку «Записать», и только после этого выходить из данного окна и переходить к следующим этапам выполнения работы.
После представления игры в форме характеристической функции необходимо определить С-ядро игры (если оно существует). При выборе меню «С-ядро» открывается окно для определения С-ядра. Сначала вам необходимо перейти к новым переменным — для этого задайте новые ограничения и нажмите кнопку «Рисовать».
Если новые ограничения введены верно, будет нарисовано С-ядро игры, в противном случае система выдает сообщение об ошибке. Графическое изображение С-ядра поможет вам в определении количества точек (вершин с-ядра), а также в их расположении на симплекс-треугольнике.
После этого вы должны определить и ввести координаты нарисованного многоугольника. При вводе координат вершины можно вводить в любой последовательности. Если координаты введены правильно, то после нажатия кнопки «Проверить» будет выдано следующее окно. Здесь вы должны перейти к исходным переменным (проделать обратные преобразования) и записать
окончательный вариант С-ядра. После проверки правильности определения решения необходимо проверить игру на выпуклость и определить N-ядро игры. N-ядро игры определяется как центр С-ядра: для его определения просто сложите значение каждой координаты по всем точкам и разделите на количество точек.
Внимание!!! Если какое-то ограничение проходит через вершину симплекс-треугольника, то эта точка (вершина) должна учитываться в N-ядре 2 раза!
Кроме указанных решений, необходимо найти вектор Шепли. После нахождения всех решений необходимо найти вектора эксцессов для вектора Шепли и N-ядра. После проведения всех необходимых вычислений и нахождения всех решений нажмите кнопку «Все выполнено» — вам будет выдан итоговый отчет, включающий все найденные вами решения. После нахождения всех решений сравните и проанализируйте результаты. Дайте рекомендации по их дальнейшему применению. Выберите решение, лучшее с вашей точки зрения, обоснуйте.

Варианты заданий: Кооперативная игра трех лиц задана в нормальной форме...