Матричные игры (110
..pdfМИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
В.П. Орлов
МАТРИЧНЫЕ ИГРЫ
Учебно-методическое пособие для вузов
Издательско-полиграфический центр Воронежского государственного университета
2012
Утверждено научно-методическим советом математического факультета 25 октября 2012 г., протокол № 0500-07
Рецензент д-р физ.-мат. наук И.Я. Новиков
Учебно-методическое пособие подготовлено на кафедре математического моделирования математического факультета Воронежского государственного университета.
Рекомендуется для студентов 3-го курса дневного отделения и 1-го курса магистратуры математического факультета Воронежского государственного университета.
Для направлений: 010100 – Математика; 010200 – Математика. Прикладная математика
Содержание
1 |
Введение. |
4 |
|
2 |
Основные понятия. |
7 |
|
|
2.1 |
Бескоалиционные игры. . . . . . . . . . . . . . . . . . . . . . . . |
7 |
3 |
Основные понятия теории антагонистических игр |
9 |
|
|
3.1 |
Общие понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . |
9 |
4 |
Mатричныe игры |
10 |
4.1Основные понятия теории матричных игр . . . . . . . . . . . . . 10
4.2Решение матричной игры на примере задачи о разорении двух фирм. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5 Бесконечные антагонистические игры. |
21 |
5.1Основные определения . . . . . . . . . . . . . . . . . . . . . . . . 21
5.2Решение задачи о разорении фирмы для непрерывного случая . 24
3
1.Введение.
Настоящее пособие посвящено одному из основных разделов теории игр - антагонистическим играм. Антагонистические игры можно разделить на конечные ( матричные) игры и бесконечные. Маричные игры являются основой для изучения как теории антагонистических игр, так и более общей теории бескоалиционных игр. Антагонистические игры возникают в различных сферах жизнедеятельности человека.
В природе и обществе часто встречаются явления, в которых те или иные участники имеют несовпадающие интересы, причём каждый из участников располагают своими путями для достижения своих целей. Эти ситуации называются конфликтами, и они являются предметом изучения теории игр. Ход событий в конфликте зависит от решений, принимаемых каждой из сторон конфликта. Поэтому поведение любого из участников, если оно разумно, должно определяться с учётом возможного поведения всех его участников, хотя ни один из участников заранее не знает решений, принимаемых остальными участниками.
Одним из наиболее интересных и исследуемых разделов теории игр являются матричные игры. Участниками матричной игры являются два игрока с противоположными интересами.
Задачи, возникающие в теории матричных игр, заключаются в том, чтобы рекомендовать каждому из игроков наилучший для него ход обеспечивающий «наибольший» в некотором смысле выигрыш. Это приводит к необходимости формализации понятий игры, наилучшего хода и наибольшего выигрыша. В данном случае наилучший ход обеспечивает игроку наибольший гарантированный выигрыш, то есть максимальный выигрыш, который игрок может получить независимо от ходов других участников игры.
4
Данное пособие состоит из введения и четырёх разделов.
Впервом разделе «Основные понятия» даются определения бескоалиционной игры, равновесия по Нэшу, оптимальности по Парето и приводятся соответствующие примеры. Также в этом разделе сформулированы правила нахождения ситуаций равновесия по Нэшу и ситуаций, оптимальных по Парето в биматричной игре.
Вразделе «Смешанное расширение бескоалиционной игры» определяются понятия смешанной стратегии игрока, спектра смешанной стратегии, ситуации в смешанных стратегиях, функции выигрыша игрока, заданной на множестве ситуаций в смешанных стратегиях, приводятся с доказательствами теорема о существовании ситуации равновесия по Нэшу в конечной бескоалиционной игре n лиц и свойства ситуаций равновесия по Нэшу. Кроме того, в этом разделе решена задача о построении множества всевозможных векторов выигрышей в смешанных стратегиях в игре «Семейный спор».
Вразделе «Равновесие в совместных смешанных стратегиях» рассматривается новый класс игр, в которых участникам игры разрешается принимать совместные решения. Здесь определяются понятия совместной смешанной стратегии, ситуации равновесия в совместных смешанных стратегиях и понятие слабого равновесия в совместных смешанных стратегиях. Также в этом разделе будут сформулированы и доказаны утверждения, которые характеризуют множество ситуаций равновесия в совместных смешанных стратегиях
имножество ситуаций слабого равновесия в совместных смешанных стратегиях и отражают взаимосвязь равновесия в смешанных стратегиях, равновесия в совместных смешанных стратегиях и слабого равновесия в совместных сме-
шанных стратегиях. В качестве приложения теории, изложенной в разделе
5
будет решена задача, в которой рассматривается одна из модификаций игры «Музыкальные стулья».
В разделе «Арбитражная схема Нэша» вводится новый класс игр
(N; S; v0) (так называемые игры с переговорами) где N - множество игроков, S - переговорное множество, v0 - вектор максиминных выигрышей игроков. и исследуется принцип оптимальности, позволяющий найти арбитражное решение (вектор выигрышей) одной из таких игр. В качестве приложения данного принципа будет найдено арбитражное решение биматричной
(2 × 2)-игры.
6
2.Основные понятия.
2.1.Бескоалиционные игры.
Пусть заданы непустые множества Xi; где i = 1; |
: : : ; |
n: Рассмотрим |
|||
множество X |
= X1 × : : : × Xn; то есть X |
= {x |
= (x1; |
: : : ; xn)| xi |
|
Xi; i = 1; |
: : : ; n}: Для каждого i = 1; |
: : : ; |
n |
определим функцию |
Hi : X1 × X2 × : : : × Xn → R1:
Процесс бескоалиционной игры кратко можно описать следующим образом. Участники игры независимо друг от друга выбирают стратегии xi
Xi; i = 1; : : : ; n: В результате в игре складывается набор стратегий x = (x1; x2; : : : ; xn) X; называемый ситуацией, и i-й игрок получает выигрыш Hi(x): В качестве исхода игры рассматривается вектор H(x) = (H1(x); : : : ; Hn(x)): При этом игрок i предпочитает ситуации x ситуацию x′
тогда и только тогда, когда Hi(x′) > Hi(x): Если Hi(x′) = Hi(x); то ситуации x и x′ для игрока i равноценны.
Определение 2.1. Система
= (N; {Xi}i N ; {Hi}i N );
вкоторой N = {1; 2; 3; : : : ; n} - множество игроков, Xi - множество
стратегий игрока i, Hi - функция выигрыша игрока i; определённая на декар-
∏n
товом произведении множеств стратегий игроков X = Xi (множество
i=1
ситуаций игры), называется бескоалиционной игрой.
Рассмотрим теперь частные случаи бескоалиционной игры n лиц.
Определение 2.2. Если множества стратегий игроков Xi; где i
{1; : : : ; n} конечны, то игра называется конечной бескоалиционной игрой n лиц.
7
Определение 2.3. Бескоалиционная игра ; в которой принимают участие два игрока, называется игрой двух лиц ( = (X1; X2; H1; H2)).
Определение 2.4. Конечная бескоалиционная игра двух лиц называется биматричной.
При этом удобно считать, что (X1 = {1; : : : ; m}; X2 = {1; : : : ; n}), а функции H1 и H2 записываются в виде матриц
A = |
11 |
: : : 1n |
|
и |
B = |
11 |
|||
|
: : : |
: : : |
: : : |
|
|
: : : |
|||
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
m1 |
: : : |
mn |
|
|
m1 |
:: : 1n
:: : : : :
:: : mn
:
Здесь элементы ij = H1(i; j) и ij = H2(i; j) матриц A и B являются соответственно выигрышами игроков 1 и 2 в ситуации (i; j); i X1; j X2:
Биматричную игру удобно представлять так: игрок 1 выбирает номер i- й строки матрицы A, а игрок 2 (одновременно и независимо) - номер j-го столбца матрицы B. В результате в игре образуется ситуация (i; j); причём игрок 1 получает выигрыш ij; а игрок 2 - выигрыш ij:
Часто биматричную игру записывают в виде
( 11; 11)
(A; B) = : : :
( m1; m1)
:: : ( 1n; 1n)
:: : : : :
:: : ( mn; mn)
:
Если H2 = −H1, или, что то же, B = −A, то игра становится антагонистической и называется матричной. Матричная игра целиком определяется матрицей A.
Перейдем к изложению основных понятий теории матричных игр.
8
3.Основные понятия теории антагонистических игр
3.1.Общие понятия
Определение 1. Тройка = (X; Y; K), где X; Y – непустые множества, и функция K : X ×Y → R1; называется антагонистической игрой в нормальной форме. Элементы x X, y Y называются чистыми стратегиями игроков 1, 2 соответственно. Пары стратегий (x; y) X × Y называются ситуациями. Функция K называется функцией выигрыша игрока 1, а выигрыш игрока 2 в ситуации (x; y) полагается равным (−K(x; y)).
Определение 2. Величины
= sup inf K(x; y); |
|
= inf sup K(x; y) |
||
|
||||
x |
y |
|
y |
x |
|
|
|
называются нижним и верхним значением игры соответственно.
Если sup в достигается, то называется максимином, а стратегия, на которой этот sup достигается, называется максиминной стратегией игрока 1. Если inf в достигается, то называется минимаксом, а стратегия, на которой этот inf достигается, называется минимаксной стратегией игрока 2. По смыслу видно, что это гарантированный выигрыш игрока 1, а это гарантированный проигрыш игрока 2.
Теорема 3.1. В антагонистической игре всегда не превосходит :
Доказательство теоремы приведено в [1], стр. 16.
Определение 3. В антагонистической игре = (X; Y; K) ситуация
(x ; y ) называется ситуацией равновесия или седловой точкой, если
K(x; y ) 6 K(x ; y ) 6 K(x ; y)
для всех x X и y Y .
9
Определение 4. Пусть (x ; y ) – ситуация равновесия в игре . Тогда число = K(x; y ) называется значением игры .
Определение 5. Стратегия игрока 1 называется оптимальной, если существует стратегия игрока 2 y , в паре с которой они образуют ситуацию равновесия x ; y .
Множество оптимальных стратегий игрока 1 (2) в игре обозначается через X (Y ).
Теорема 3.2. Для того, чтобы в игре = (X; Y; K) существовала ситуация равновесия, необходимо и достаточно, чтобы существовали максимин и минимакс и = :
Доказательство теоремы приведено в [1], стр. 19.
Определение 6. Тройка (x ; y ; ) называется решением игры = (X; Y; K).
4.Mатричныe игры
4.1.Основные понятия теории матричных игр
Определение 7. Антагонистические игры, в которых оба игрока имеют конечные множества стратегий, называются матричными.
Матричную игру удобно представлять так: игрок 1 выбирает номер i-й строки матрицы A, а игрок 2 (одновременно и независимо) - номер j-го столбца матрицы A. В результате в игре образуется ситуация (i; j); причём игрок 1 получает выигрыш ij; а игрок 2 - проигрывает ij:
Матричные игры - это самые простые антагонистической игры. Но даже в них не всегда максимин и минимакс совпадают. Поэтому приходится "расширять"игру.
10