Теория игр. Ч. 2. Биматричные игры. Арбитражная схема
Покупка
Издательство:
Издательский Дом НИТУ «МИСиС»
Год издания: 2016
Кол-во страниц: 39
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-906846-04-4
Артикул: 755316.01.99
Доступ онлайн
В корзину
Настоящее пособие является второй частью учебного пособия по теории игр и посвящено биматричным играм и арбитражным схемам. В пособии приводятся краткие теоретические сведения, решения типовых задач, а также дополнительный материал из других дисциплин. Для закрепления необходимых навыков предлагаются задания для самостоятельного решения. Предназначено для студентов, обучающихся по направлениям 38.03.01 «Экономика», 38.03.04 «Государственное и муниципальное управление».
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 38.03.01: Экономика
- 38.03.04: Государственное и муниципальное управление
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ «МИСиС» № 2772 Кафедра математики А.А. Закиров Т.Л. Майзенберг Н.В. Семенова Теория игр Часть 2. Биматричные игры. Арбитражная схема Учебное пособие Рекомендовано редакционно-издательским советом университета Москва 2016
УДК 51 З-18 Р е ц е н з е н т д-р экон. наук, проф. Ж.К. Галиев Закиров А.А. З-18 Теория игр. Ч. 2. Биматричные игры. Арбитражная схема : учеб. пособие / А.А. Закиров, Т.Л. Майзенберг, Н.В. Семенова. – М. : Изд. Дом МИСиС, 2016. – 39 с. ISBN 978-5-906846-04-4 Настоящее пособие является второй частью учебного пособия по теории игр и посвящено биматричным играм и арбитражным схемам. В пособии приводятся краткие теоретические сведения, решения типовых задач, а также дополнительный материал из других дисциплин. Для закрепления необходимых навыков предлагаются задания для самостоятельного решения. Предназначено для студентов, обучающихся по направлениям 38.03.01 «Экономика», 38.03.04 «Государственное и муниципальное управление». УДК 51 ISBN 978-5-906846-04-4 А.А Закиров, Т.Л. Майзенберг, Н.В. Семенова, 2016 НИТУ «МИСиС», 2016
ОГЛАВЛЕНИЕ Предисловие .............................................................................................. 4 1. Биматричные игры................................................................................ 5 1.1. Общие сведения ............................................................................. 5 1.2. Аналитическое решение игры (nn) ............................................ 8 1.3. Задание № 1 .................................................................................. 13 1.4. Графическое решение биматричной игры (22) ....................... 14 1.5. Задание № 2 .................................................................................. 23 2. Арбитражная схема ............................................................................ 25 2.1. Аксиомы Нэша ............................................................................. 25 2.2. Вторая теорема Нэша. Решение арбитражной схемы .............. 26 2.3. Задание № 3 .................................................................................. 33 Библиографический список ................................................................... 35 Приложения ............................................................................................ 36
Предисловие Во многих сферах жизнедеятельности человека возникают ситуации, в которых стороны-участники преследуют различные цели, а результат действия каждой стороны зависит от того, что предприняли другие участники. В большинстве случаев интересы участвующих сторон являются если и не противоположными, то, по крайней мере, несовпадающими. Таким образом, возникают задачи с элементами неопределенности. Примерами таких ситуаций являются партия игры в шахматы, взаимодействие хозяйствующих субъектов, задачи проектирования объектов различной природы, социальные отношения и т.д. Моделированию и изучению конфликтных ситуаций посвящен раздел математики, называемый теорией игр. Игрой называется математическая модель конфликтной ситуации; стороны, участвующие в конфликте, называются игроками; решением игры называется совокупность оптимальных действий (оптимальных стратегий) игроков и полученных ими выигрышей. Условие оптимальности для каждого типа игры определяется по-своему. Настоящее пособие является второй частью учебного пособия по теории игр и посвящено биматричным играм и арбитражным схемам. По традиции приводятся краткие теоретические сведения, а также необходимый материал из других дисциплин. Разобранные примеры позволяют понять алгоритм решения задач. Приводятся как аналитические, так и графические методы решения задач. Для закрепления необходимых навыков предлагаются задания для самостоятельного решения. Пособие предназначено для студентов, обучающихся по направлениям 38.03.01 «Экономика», 38.03.04 «Государственное и муниципальное управление». Вместе с тем очевидно, что при разработке, внедрении и реализации проектов и в других сферах человеческой деятельности приходится учитывать большое число случайных факторов, плохо управляемых и трудно прогнозируемых, что может привести к несовпадению интересов участвующих в производственной цепочке субъектов. Поэтому пособие может оказаться полезным не только студентам указанных профилей подготовки, но также школьникам, магистрам, аспирантам и преподавателям. ___________ Закиров А.А., Майзенберг Т.Л., Макаров П.В. Теория игр. Ч. 1. Антагонистические игры: Учеб. пособие. М.: МГГУ, 2013. 46 с.
1. БИМАТРИЧНЫЕ ИГРЫ 1.1. Общие сведения В некоторых случаях интересы участников конфликта не являются прямо противоположными, но они по-прежнему не имеют возможности договариваться, создавая какие-либо объединения. Конфликты такого рода моделируются бескоалиционными играми. В общем случае выигрыши игроков не являются противоположными (как в антагонистических играх, рассмотренных в первой части пособия), т.е. сумма выигрышей не только не равна нулю, но и не является постоянной для всех возможных ситуаций в игре (игра с переменной суммой). Если речь идет об игре двух лиц, при этом каждый из игроков имеет изначально конечное число стратегий (чистых стратегий), то выигрыши игроков могут быть записаны в виде двух матриц одинаковой размерности. По этой причине такие игры называются биматричными. Разыгрывание биматричной игры происходит следующим образом. Предположим, что игрок A имеет m чистых стратегий 1,..., ,..., i m A A A , игрок B – n чистых стратегий 1,..., ,..., j n B B B . То гда матрицы выигрышей игроков (обозначим их A и B соответственно) имеют размерность m n . При этом чистым стратегиям игрока A в обеих матрицах соответствуют строки, игрока B – столбцы. Пусть игроки одновременно и независимо выбирают свои чистые стратегии k A и lB . В сложившейся в игре ситуации выиг рыш игрока A составит kl a , выигрыш игрока B – k l b . На этом разыгрывание игры заканчивается. Таким образом, конечные игры двух лиц с переменной суммой полностью определяются двумя платежными матрицами. В качестве примера приведем прототипную игру, известную под названием «Семейный спор». Муж (игрок 1) и жена (игрок 2) могут выбрать одно из двух вечерних развлечений: футбольный матч или театр. Муж предпочитает футбол, а жена – театр. Однако обоим гораздо важнее провести вечер вместе, чем участвовать в развлечении (хотя и предпочтительном) одному. Таким образом, каждый игрок имеет две чистые стратегии: 1 1 , A В – пойти на футбол, 2 2 , A В – пой ти в театр. Эта игра может быть задана двумя матрицами:
4 0 0 1 A и 1 0 0 4 B . Укажем еще один способ задания конечной биматричной игры: 4 ;1 0 ; 0 0; 0 1; 4 . Естественно считать, что каждый из игроков стремится действовать таким образом, чтобы получить как можно больший выигрыш. Но функция выигрыша каждого игрока зависит не только от выбранной им стратегии, но и от выбора противника. Поэтому ситуация, дающая наибольший выигрыш одному игроку, может не оказаться таковой для второго игрока. Таким образом, понятия оптимального поведения и оптимальных стратегий игроков в биматричных (равно как и вообще в бескоалиционных) играх являются неоднозначными. В отличие от матричных игр здесь существует множество принципов оптимальности. Одним из подходов к понятию оптимальности является равновесие по Нэшу. Ситуация, сложившаяся в биматричной игре, является равновесной по Нэшу, если каждому игроку невыгодно отклоняться от нее в одностороннем порядке. В общем случае в биматричной игре может быть несколько ситуаций равновесия по Нэшу. Стратегия игрока, входящая хотя бы в одну ситуацию равновесия по Нэшу, называется равновесной стратегией. При этом помимо чистых стратегий игроки могут применять и смешанные стратегии. Напомним, что по теореме Нэша всякая бескоалиционная игра имеет хотя бы одну ситуацию равновесия в смешанных стратегиях. В игре «Семейный спор» имеется две равновесные по Нэшу ситуации: 1 1 , A В и 2 2 , A В . В отличие от матричных игр выигрыши игрока в различных ситуациях равновесие по Нэшу могут различаться. Найдем решение произвольной биматричной игры. Пусть первый игрок имеет m чистых стратегий, а второй – n чистых стратегий, тогда игра задается двумя матрицами размерности m n : 11 12 1 21 22 2 1 2 n n m m mn a a a a a a A a a a и 11 12 1 21 22 2 1 2 n n m m mn b b b b b b B b b b .
Обозначим смешанную стратегию первого игрока 1 2 , , , m p p p , 1 1 m k k p , смешанную стратегию второго – 1 2 , , , n q q q , 1 1 n k k q . Если игроки применили свои смешанные стратегии, то математические ожидания их выигрышей можно вычислить по формулам 1 1 2 1 2 1 1 , , , , , , m n m m i i j j i j H p p p A q q q p a q T , (1.1) 2 1 2 1 2 1 1 , , , , , , m n m m i i j j i j H p p p B q q q p b q T . (1.2) В векторной форме равенства (1.1), (1.2) можно записать так: 1 H p A q и 2 H p B q , где 1 2 , , , m p p p p , 1 2 , , , m q q q q T . Обозначим символами * * 1 1 , V H p q и * * 2 2 , V H p q мате матические ожидания игроков, соответствующие их оптимальным стратегиям * p и * q . Если игроки выбирают стратегии, отличные от оптимальных, их средние выигрыши окажутся не больше 1 V и 2 V соответственно. То есть для произвольных смешанных стратегий игроков справедливы неравенства * * * p A q p A q и * * * p B q p B q . (1.3) Неравенства (1.3) как и в случае антагонистической игры становятся равенствами, если в * p и * q все координаты положительны. Отметим также, что неравенства (1.3) справедливы для произвольных смешанных стратегий игроков p и q , в том числе и для чистых стратегий: * * * 1 1 2 2 1 * * * 1 1 2 2 2 , 1, , , , 1, , . i i in n j j m j m a q a q a q V i m b p b p b p V j n (1.4)
Получаем систему m n неравенств, решением которой явля ются оптимальные стратегии игроков * p и * q . 1.2. Аналитическое решение игры (nn) Рассмотрим биматричную игру, в которой количество чистых стратегий у игроков одинаковое, т.е. m n . В этом случае матрицы выигрышей игроков являются квадратными. Полагая, что все чистые стратегии игроков являются активными, получаем систему 2n линейных уравнений с 2n неизвестными: * * * 1 1 2 2 1 * * * 1 1 2 2 2 , , 1, , . i i in n i i n ni a q a q a q V p b p b p b V i n (1.5) Так как любая биматричная игра имеет хотя бы одно решение в смешанных стратегиях, систему (1.5) можно решить, используя правило Крамера, если, конечно, соответствующие матрицы являются невырожденными. Введем обозначения: A и B – определители платежных матриц A и B ; i A и i B – определители матриц, полученных из матрицы A за меной ее i-го столбца на столбец из единиц и из матрицы B при аналогичной замене ее i-й строки единичной строкой; 1 и 1 T – единичная строка и единичный столбец размерности n. Учитывая, что 1 m i i p = 1 n j j q =1, получаем следующие выражения для выигрышей игроков в ситуации равновесия и их равновесных стратегий: – выигрыши игроков (первого и второго соответственно) 1 1 n i i A V A , 2 1 ; n i i B V B , (1.6) – равновесные стратегии игроков (первого и второго соответственно) * 1 2 p V B 1 , * 1 1 q V A 1 T . (1.7)
Замечание 1.1. Очевидно, что в результате умножения матрицы 1 A на вектор-столбец 1 T получается вектор-столбец a , элементами которого являются суммы элементов соответствующих строк данной матрицы: 1 2 1 1 1 n n n k k nk k k k a a a a T . В результате умножения единичной вектор-строки 1 на матрицу 1 B получается вектор-строка b , состоящая из сумм элементов матрицы по столбцам: 1 2 1 1 1 n n n k k k n k k k b a a a . Отсюда следует другой вид формул (1.6), (1.7): 1 1 , 1 1 n i j i j V a , 1 2 , 1 1 n i j i j V b , (1.6а) где 1 i j a и 1 i j b – элементы матриц 1 A и 1 B ; * 2 p V b , * 1 q V a . (1.7а) Для того чтобы искомые вероятности были положительными, достаточно, чтобы у матриц A и B существовали обратные матрицы с положительными суммами элементов по столбцам для матрицы A и по строкам для матрицы B . Рассмотрим два примера решения биматричных игр с помощью формул (1.6), (1.7). Пример 1.1. Найти решение биматричной игры, заданной матри цами выигрышей игроков 3 1 1 4 A , 2 5 4 1 B . Решение. Выигрыши игроков в ситуации равновесия: 1 3 1 1 4 11 11 1 1 3 1 3 2 5 1 4 1 1 V , 2 2 5 4 1 18 18 3 1 1 2 5 3 3 6 4 1 1 1 V .
Равновесные стратегии игроков (правило нахождения обратной матрицы приведено в прил. 1): * 1 5 1 5 1 1 1 1 1 3 1 1 4 2 4 2 18 6 6 2 2 p , * 4 1 1 3 3 / 5 11 1 1 1 3 1 2 2 / 5 5 11 5 q . Полученные решения должны удовлетворять равенствам * * * 1 0 p A q A q , * * * 0 1 p A q A q , * * * 1 0 p B q p B , * * * 0 1 p B q p B . Сделаем проверку для первого и четвертого условий: – для первого: 3 1 3 / 5 3 1 3 / 5 1 1 1 0 1 4 2 / 5 1 4 2 / 5 2 2 , 3 / 5 3 / 5 5 2 3 1 2 / 5 2 / 5 2 , 11 11 5 5 – верно; – для второго: 2 5 3 / 5 2 5 0 1 1 1 1 4 1 2 / 5 4 1 1 2 2 2 2 , 3 / 5 0 3 3 3 3 2 / 5 1 , 3 3 – верно. Пример 1.2. Найти решение биматричной игры с матрицами выигрышей игроков 2 3 2 0 2 1 0 0 1 A и 3 0 2 0 1 1 0 0 1 B .
Решение. Матрицы треугольного вида взяты для удобства вычислений определителей. Воспользуемся снова формулами (1.6) , (1.7): 1 2 3 2 0 2 1 0 0 1 4 2 1 1 1 2 3 2 2 3 2 2 1 1 0 2 1 1 1 1 0 2 1 0 0 1 0 0 1 1 1 1 V , 2 3 0 2 0 1 1 0 0 1 3 3 1 1 1 3 0 2 3 0 2 1 3 2 2 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 1 1 1 V , * 1 0 2 1 0 2 3 1 1 1 1 1 1 1 0 3 3 0 3 3 2 3 2 2 2 0 0 3 0 0 3 p 1 3 1 2 2 , * 1/ 2 3 / 4 1/ 4 1 1 2 0 1/ 2 1/ 2 1 0 0 0 1 1 2 q . Полученное решение не имеет смысла – вероятности не могут быть отрицательными. Возникает вопрос о причине подобной ситуации и условиях применимости формул (1.6), (1.7). Ответ на этот вопрос дает следующее замечание. Замечание 1.2. Очевидно, что столбцы свободных членов в каждой из систем n уравнений (1.5) состоят из одинаковых элементов ( 1 V и 2 V ). Поэтому в случае неотрицательности платежных матриц A и B равенства (1.5) не могут выполняться, если элементы одной строки
Доступ онлайн
В корзину