Материал: Теория_игр_УП_ЭК_ЭлРесурс
66
Мы
ограничимся
рассмотрением
одного
примера
данной
игры
,
теория
которой
,
хотя
и
разработана
,
но
достаточно
сложна
2
.
Пусть
игроки
1
и
2
выбирают
соответственно
числа
х
и
у
из
интервала
.
Эти
числа
будем
понимать
как
моменты
времени
выполнения
ими
требуемых
действий
.
Пусть
t –
время
появления
некоторого
объекта
,
который
достается
игроку
,
который
первый
после
t
совершил
требуемое
действие
.
Игрок
,
обладающий
объектом
,
получает
выигрыш
,
равный
1,
а
его
противник
эту
единицу
теряет
.
Если
ни
один
из
игроков
не
получит
объект
,
то
выигрыш
каждого
из
игроков
принимается
равным
нулю
.
Предполагается
,
что
время
появления
объекта
является
случайной
величиной
,
распределенной
на
интервале
по
равномерному
закону
.
Эту
игру
называют
также
борьбой
за
встречу
случайно
появляющегося
объекта
.
Запишем
математическое
выражение
функции
выигрыша
.
Рассмотрим
ситуацию
(
х
,
у
),
в
которой
х
у
.
В
этом
случае
игрок
1
выигрывает
единицу
,
если
t
х
; (4.7)
проигрывает
единицу
,
если
х
t
y; (4.8)
и
не
получает
ничего
,
если
y
t.
(4.9)
Вероятность
событий
(4.7), (4.8)
и
(4.9)
равны
соответственно
х
, (
у
-
х
)
и
(1-
у
)
.
Таким
образом
,
при
х
у
имеем
H x y
x
y x
x y
( , )
( )(
)
1
1
2
. (4.10)
Аналогичным
способом
находим
,
что
при
х
у
H x y
x y
y
x
y
( , )
(
) ( )
1
1
2
. (4.11)
Естественно
,
что
при
х
=
у
,
Н
(
х
,
у
)=0.
Схематическое
описание
Н
(
х
,
у
)
приведено
на
рис
. 4.3.
Решение
.
Заметим
,
что
игра
является
симметричной
.
Действительно
,
при
х
у
H x y
x y
H y x
y
x
( , )
( , )
(
)
2
2
.
Аналогично
,
при
х
у
H x y
y
x
H y x
y x
( , )
( , ) (
)
2
2
.
Наконец
,
при
х
=
у
H x y
H y x
( , )
( , )
0
.
y
2
x-y
1
1
x
x
-2
y
0
Рис
. 4.3.
67
Для
антагонистических
симметричных
игр
существует
теорема
,
утверждающая
для
этих
игр
цена
игры
= 0,
а
оптимальные
стратегии
игроков
1
и
2
совпадают
.
Поэтому
для
решения
данной
задачи
достаточно
найти
оптимальную
стратегию
игрока
1.
Пусть
оптимальная
стратегия
игроков
имеет
плотность
распределения
f
:
S x
f x
A
( )
( )
;
S y
f y
B
( )
( )
.
Если
игрок
2
применяет
эту
стратегию
,
то
H x f
H x y
f y dy
( , )
( , )
( )
0
1
.
С
учетом
формул
(4.10)
и
(4.11.).
перепишем
последний
интеграл
dy
y
f
y
x
dy
y
f
y
x
f
x
H
x
x
)
(
)
2
(
)
(
)
2
(
)
,
(
1
0
. (4.12)
Так
как
H x f
v
( , )
0
и
постоянна
,
то
все
производные
по
х
функции
Н
(
x,f
)
также
должны
обращаться
в
нуль
.
Дифференцируя
тождество
(4.12)
по
х
,
имеем
.
)
(
1
)
(
2
)
(
)
(
)
(
2
)
(
2
)
(
)
2
(
)
(
)
(
)
2
(
)
,
(
1
1
1
0
1
0
x
x
x
x
dy
y
f
x
xf
dy
y
f
dy
y
f
x
xf
dy
y
f
x
f
x
x
dy
y
f
x
f
x
x
x
f
x
H
(4.13)
Вторая
частная
производная
имеет
вид
,
0
)
(
)
(
2
)
(
2
)
,
(
2
2
x
f
x
f
x
x
f
x
f
x
H
т
.
е
.
f x
f x
x
' ( )
( )
3
2
1
.
Интегрируя
это
дифференциальное
уравнение
,
получаем
c
x
x
f
ln
2
3
)
(
ln
,
откуда
f x
c x
( )
3
2
. (4.14)
Полученная
плотность
распределения
f(x)
положительна
и
дифференцируема
.
Однако
интеграл
x
dx
3
2
0
1
расходится
.
Следовательно
,
плотность
f
не
может
быть
дифференцируемой
и
больше
нуля
на
всем
сегменте
.
Можно
доказать
,
что
плотность
распределения
может
обращаться
в
нуль
лишь
между
нулем
и
некоторым
.
Таким
образом
,
имеем
:
.
при
;
при
0
)
(
2
3
x
cx
x
x
f
Для
определения
неизвестных
параметров
и
с
воспользуемся
следующими
соображениями
.
Во
-
первых
,
f(x)
должна
удовлетворять
условию
нормировки
:
f x dx
f x dx
( )
( )
0
1
1
1
. (4.15)
Во
-
вторых
,
H f
v
( , )
1
0
. (4.16)
68
Из
уравнений
(4.15)
и
(4.16)
можно
определить
значения
и
с
.
С
этой
целью
перепишем
эти
уравнения
в
явном
виде
.
c x
dx
1
3
2
1
,
т
.
е
.
c
x
c
(
)
2
2
1
1
1
1
2
1
. (4.17)
Далее
на
основании
симметричности
игры
H f
H
f
c
y y
dy
( , )
( , )
(
)
1
1
1 2
0
1
3
2
.
Поскольку
с
0,
это
нам
дает
(
)
(
1
3
2
3
2
3
2
1
2
1
2
2
4
0
y
y
dy
y
y
.
Откуда
получаем
2
3
1 0
.
Это
квадратное
уравнение
имеет
два
корня
: 1
и
1
4
.
Корень
=1
противоречит
равенству
(4.17),
а
подстановка
1
4
в
это
равенство
дает
c
1
2
.
Таким
образом
,
искомая
оптимальная
стратегия
игрока
1
определяется
плотностью
распределения
.
4
1
при
2
1
;
4
1
при
0
)
(
2
3
x
x
x
x
f
График
f(x)
изображен
на
рис
. 4.4.
f
0
1
x
1
4
Рис
. 4.4.
Остается
проверить
,
что
найденные
стратегии
игроков
действительно
являются
оптимальными
.
Для
этого
достаточно
убедиться
в
том
,
что
для
любого
х
H x f
v
( , )
0
.
При
x
1
4
,
0
2
1
2
2
2
2
)
2
(
2
1
)
2
(
2
1
)
,
(
1
2
1
2
1
2
3
1
4
1
4
1
x
y
xy
dy
y
y
x
f
x
H
,
поскольку
в
рассматриваемом
случае
x
1
2
.
При
1
4
1
x
,
формула
(4.13)
дает
69
0
1
1
1
)
2
(
2
1
1
2
1
2
1
2
)
,
(
2
1
2
1
1
2
1
2
1
1
2
3
2
3
x
x
y
x
dy
y
x
x
x
f
x
H
x
x
.
Тем
самым
оптимальность
стратегии
с
плотностью
f
установлена
.
ТЕСТЫ
(
В
–
Верно
,
Н
–
Неверно
)
1.
Игры
называются
бесконечными
,
если
у
всех
игроков
множество
чистых
стратегий
бесконечно
.
2.
Бесконечные
антагонистические
игры
решать
труднее
,
чем
конечные
.
3.
В
бесконечной
антагонистической
игре
принципом
оптимальности
является
принцип
максимина
.
4.
Бесконечные
антагонистические
игры
решаются
только
в
чистых
стратегиях
.
5.
Играми
на
единичном
квадрате
называются
такие
бесконечные
антагонистические
игры
,
для
которых
возможные
стратегии
двух
игроков
Х
и
У
.
6.
Для
антагонистических
симметричных
игр
оптимальные
стратегии
игроков
1
и
2
совпадают
.
7.
Для
антагонистических
симметричных
игр
цена
игры
v>
0.
8.
В
строго
выпуклой
игре
игрок
2
имеет
единственно
оптимальную
стратегию
,
которая
является
чистой
.
(
Ответы
:
1-
Н
; 2-
В
; 3-
В
; 4-
Н
; 5-
В
; 6-
В
; 7-
Н
; 8-
В
).
ЗАДАЧИ
Найти
хотя
бы
одно
решение
бесконечной
антагонистической
игры
на
единичном
квадрате
со
следующей
функцией
выигрыша
:
1.
2
2
3
16
)
,
(
x
xy
y
y
x
H
;
2.
.
,
;
,
;
,
)
,
(
2
2
x
y
y
x
y
x
x
y
x
x
y
x
H
y
y
3.
.
,
1
;
,
;
,
;
,
)
,
(
2
1
2
2
1
2
2
2
x
x
x
y
y
x
y
x
x
y
x
x
y
x
H
y
y
y
y
4.
.
2
)
(
sin
)
,
(
y
x
y
x
H
5.
.
,
2
;
,
0
;
,
2
)
,
(
y
x
y
x
y
x
y
x
y
x
y
x
H
6.
.
1
1
;
max
)
,
(
y
x
y
x
y
x
H
70
5.
БЕСКОАЛИЦИОННЫЕ
ИГРЫ
5.1.
Общие
сведения
Антагонистические
игры
,
которые
рассматривались
в
предыдущих
главах
книги
,
описывают
конфликты
частного
вида
,
которые
не
всегда
адекватны
разным
ситуациям
или
вообще
не
могут
считаться
приемлемыми
.
В
частности
,
антагонистические
игры
не
затрагивают
конфликты
с
числом
игроков
больше
двух
.
Более
того
,
даже
в
конфликтах
с
двумя
игроками
интересы
сторон
не
всегда
противоположны
.
Во
многих
конфликтах
одна
из
ситуаций
может
оказаться
предпочтительнее
другой
для
обоих
игроков
.
Бескоалиционные
игры
являются
играми
более
общей
природы
.
Бескоалиционность
понимается
в
том
смысле
,
что
группам
игроков
(“
коалициям
”)
не
приписывается
ни
каких
-
либо
интересов
,
за
исключением
тех
,
которые
вытекают
из
интересов
отдельных
игроков
.
Целью
каждого
игрока
в
такой
игре
является
только
получение
по
возможности
наибольшего
индивидуального
выигрыша
.
Определение
1.
Бескоалиционной
игрой
называется
игра
N
игроков
(N
2),
каждый
из
которых
имеет
множество
стратегий
i
,
с
функцией
выигрыша
Н
i
(
x
),
N
i
,
1
,
где
x
–
ситуация
,
задаваемая
на
множество
декартового
произведения
стратегий
і
.
Определение
2.
Бескоалиционная
игра
называется
игрой
с
постоянной
суммой
,
если
существует
такое
постоянное
С
,
что
N
i
i
C
x
H
)
(
,
для
всех
ситуаций
x
.
Класс
антагонистических
игр
является
классом
игр
двух
лиц
с
нулевой
суммой
.
Определение
3.
Конечная
бескоалиционная
игра
двух
игроков
с
ненулевой
суммой
называется
биматричной
игрой
.
Как
и
в
случае
антагонистических
игр
необходимо
выработать
принципы
оптимального
поведения
игроков
в
бескоалиционных
играх
и
найти
решения
(
оптимальные
стратегии
каждого
из
игроков
).
Для
класса
антагонистических
игр
принципом
оптимальности
является
принцип
максимина
.
В
общих
бескоалиционных
играх
возможны
ситуации
одновременного
увеличения
выигрышей
всех
игроков
или
хотя
бы
их
одновременного
выигрыша
,
поэтому
в
этих
играх
необходимо
ввести
формализованное
описание
таких
понятий
,
как
выгодность
,
устойчивость
и
справедливость
того
или
иного
решения
игры
.
Определение
4.
Ситуация
х
в
игре
называется
приемлемой
для
игрока
і
,
если
для
любой
его
стратегии
i
x
)
(
)
/
(
x
H
x
x
H
i
, (5.1)
т
.
е
.
при
применении
і
-
м
игроком
в
данной
ситуации
всех
других
стратегий
,
его
выигрыш
не
может
увеличиться
.