Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Пермский национальный исследовательский политехнический университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

ТЕОРИЯ ИГР.doc

Скачиваний:

Добавлен:

01.05.2025

Размер:

1 Мб

Скачать

☆

<<< < Предыдущая 12 / 102 3 4 5 6 7 8 9 10 > Следующая >>>

Глава I. Антагонистические игры §2. Седловые точки и антагонистические игры

Пусть функция F(x,y) определена на декартовом произведении XY, где X,Y - множества произвольной природы.

Определение. Пара (x⁰, y⁰)  X  Y называется седловой точкой функции F(x,y) на X  Y, если F(x, y⁰)  F(x⁰, y⁰)  F(x⁰, y)  x  X,  y  Y (2.1)

или, эквивалентно,

Понятие седловой точки используется в определении решения антагонистической игры.

Опишем антагонистическую игру. В ней принимают участие два игрока 1 и 2 (первый и второй). Игрок 1 выбирает стратегию x из множества стратегий X, игрок 2 выбирает стратегию y из множества стратегий Y. Нормальная форма игры подразумевает, что каждый игрок выбирает свою стратегию независимо, не зная выбора партнера. Задана функция выигрыша F(x,y) первого игрока, определенная на XY. Выигрыш F(x,y) первого игрока является проигрышем для второго. Цель первого игрока состоит в увеличении своего выигрыша F(x,y), а цель второго - в уменьшении F(x,y).

Таким образом, антагонистическая игра задается набором Г = <X, Y, F(x, y)>. Термины "выигрыш" и "игрок" сложились исторически, когда анализировались преимущественно азартные игры. Эти термины не совсем точные. Например, если значение F(x,y)<0, то "выигрыш" первого игрока является фактически его проигрышем. Кроме того, рассматривают игры, где F(x,y) является не денежным выигрышем, а, скажем, вероятностью поражения цели. Игрок 2 может не быть интеллектуальным противником. Часто рассматривают игры против "природы".

Вернемся к определению седловой точки, которой можно придать следующий игровой смысл. Если игроки выбрали в качестве стратегий компоненты x⁰,y⁰ седловой точки, то каждому из них невыгодно отклоняться от выбранной стратегии. Поэтому седловая точка является формализацией концепции равновесия в игре.

Определение. Говорят, что антагонистическая игра Г имеет решение, если функция F(x, y) имеет на XY седловую точку. Пусть (x⁰, y⁰) - седловая точка функции F(x, y). Тогда тройка (x⁰, y⁰, v = F(x⁰, y⁰)) называется решением игры, x⁰, y⁰ - оптимальными стратегиями игроков, а v - значением игры.

Покажем, что значение игры не зависит от выбора седловой точки.

Лемма 2.1. Если (x⁰, y⁰), (x*, y*) - две седловые точки функции F(x, y) на XY, то F(x⁰, y⁰) = F(x*, y^*).

Доказательство. Наряду с (2.1), выпишем аналогичные неравенства для седловой точки (x*, y^*)

(2.2)

Имеем

Здесь все неравенства выполнены как равенства.

Важнейший класс антагонистических игр образуют матричные игры.

Определение. Антагонистическая игра Г называется матричной, если множества стратегий игроков конечны: X = {1, ...,m}, Y = {1, ..., n}. При этом принято обозначать стратегию первого игрока через i, стратегию второго через j, а выигрыш первого F(i, j) через a_ij . Матрица A = (a_ij)_m__n называется матрицей игры. Первый игрок выбирает в ней номер строки i, а второй - номер столбца j.

В обозначениях матричной игры (i⁰, j⁰) - седловая точка матрицы A, если

Пример 2.1.

, ,

Здесь (1,1) и (2,1) - две седловые точки и значение игры  равно нулю. Заметим, что a₁₂ = , но (1,2) не является седловой точкой матрицы.

Пример 2.2. Игра "орлянка". Первый игрок закладывает монету орлом (О) или решкой (Р), а второй пытается отгадать. Если второй игрок отгадает, то первый платит ему единицу, если не отгадает, то - наоборот.

Здесь Нетрудно видеть, что эта матрица не имеет седловой точки:

, , , ,

Вернемся к общему определению седловой точки и антагонистической игры. Возникают два вопроса. Когда антагонистическая игра имеет решение, т.е. когда функция F(x, y) имеет седловую точку на X  Y ? Как искать седловые точки, если известно, что они существуют?

Рассмотрим игру Г с точки зрения первого игрока. Пусть он выбрал стратегию x. Ясно, что его выигрыш будет не меньше, чем . Величину назовем гарантированным результатом (выигрышем) для первого игрока. Наилучший гарантированный результат для первого игрока называется нижним значением игры.

Определение. Стратегия x⁰ первого игрока называется максиминной, если .

Рассмотрим игру Г с точки зрения второго игрока. Если он выбрал стратегию y, то для него естественно считать гарантированным результатом величину . Проигрыш второго игрока будет не больще, чем эта величина. Наилучший гарантированный результат для второго игрока называется верхним значением игры.

Определение. Стратегия y⁰ второго игрока называется минимаксной, если .

Лемма 2.2. В любой антагонистической игре Г справедливо неравенство

Доказательство. Возьмем произвольные стратегии игроков x и y. Тогда

Левая часть последнего неравенства зависит от x, а правая часть - нет. Поэтому

Теперь сформулируем необходимое и достаточное условие существования седловой точки для функции двух переменных.

Теорема 2.1.

1) Для того чтобы функция F(x, y) на X  Y имела седловую точку, необходимо и достаточно, чтобы было выполнено равенство

. (2.3)

2) Пусть выполнено равенство (2.3). Пара (x⁰, y⁰) тогда и только тогда является седловой точкой, когда x⁰ - максиминная, а y⁰ – минимаксная стратегии игроков.

Доказательство. Утверждения 1) и 2) будем доказывать одновременно.

Необходимость. Пусть (x⁰, y⁰) - седловая точка функции F(x, y). Покажем, что выполнено равенство (2.3), а x⁰, y⁰ - максиминная и минимаксные стратегии. Имеем

Но неравенство верно в силу леммы 2.2. Поэтому и в последних неравенствах всюду можно поставить знаки равенств. Из полученных равенств следует, что x⁰ - максиминная, а y⁰ – минимаксная стратегии игроков.

Достаточность. Пусть равенство (2.3) выполнено. Возьмем x⁰,y⁰ - максиминную и минимаксную стратегии и покажем, что они образуют седловую точку. Имеем

Во всех неравенствах можно поставить знаки равенств и получаем, что (x⁰,y⁰) - седловая точка функции F(x, y).

Замечание. Если выполнено равенство (2.3), то множество всех седловых точек прямоугольно и совпадает с X⁰Y⁰, где X⁰ и Y⁰ – множества всех максиминных и минимаксных стратегий игроков.

Упражнение 2.1. Докажите, что 33-матрица не может иметь ровно 7 седловых точек.

Пример 2.3. Найдем все седловые точки матрицы

Здесь и

Отсюда = = 2, X⁰ = {2, 3}, Y⁰ = {2, 4}. Четыре седловые точки образуют множество X⁰  Y⁰.

Пример 2.4. Пусть X = Y = [0, 1], F(x, y) = 2x² - 3xy + 2y². Найдем величины и . При фиксированном x минимум по y функции F(x, y) достигается в точке y(x) = 3x/4  Y. Поэтому функция минимума –

Отсюда = 7/8 и x⁰ = 1 – максиминная стратегия. Зафиксируем y. Максимум функции F(x, y) по x достигается в концах отрезка [0, 1] и равен

Минимум функции M(y) достигается при y⁰ = 2/3 и = M(y⁰) = 8/9 > = 7/8. Следовательно, функция F(x, y) не имеет седловой точки.

Упражнение 2.2. Найдите максиминную и минимаксную стратегии, а также нижнее и верхнее значения игры

Иногда в выражениях

внешние sup и inf не достигаются, но

(2.4)

Тогда максиминная (или минимаксная) стратегия не существует и седловой точки нет.

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

Определение. Пусть задано  > 0. Пара (x^, y^)  X  Y называется -седловой точкой функции F(x, y) на XY , если

Упражнение 2.3. Пусть x⁰, y⁰ - максиминная и минимаксная стратегии, а . Доказать, что (x⁰, y⁰) - -седловая точка функции F(x, y).

Определение. Пусть задано  > 0.

Стратегия первого игрока x^ называется -максиминной, если .

Стратегия второго игрока y^ называется -минимаксной, если .

Эти стратегии обеспечивают игрокам получение своих наилучших гарантированных результатов с точностью до . Сформулируем аналог теоремы 2.1.

Теорема 2.1’.

1) Для того чтобы при любом  >0 функция F(x, y) на XY имела -седловую точку, необходимо и достаточно, чтобы было выполнено равенство (2.4).

2) Пусть равенство (2.4) выполнено. Тогда компоненты -седловой точки являются 2-максиминной и 2-минимаксной стратегиями. Обратно, -максиминная и -минимаксная стратегии образуют 2-седловую точку.

Упражнение 2.4. Докажите теорему 2.1’.

Представляют интерес условия топологического характера, при которых существуют максиминные и минимаксные стратегии.

Теорема 2.2. Пусть функция F(x, y) непрерывна на XY , где X, Y - компакты метрических пространств. Положим Тогда

1) Функция минимума непрерывна на X.

2) Предположим дополнительно, что при каждом x  X множество Y(x) состоит из единственного элемента y(x). Тогда функция y(x) непрерывна на X.

Доказательство. 1) Возьмем произвольную последовательность {x^k} элементов из X, сходящуюся к x⁰. Покажем, что существует и равен W(x⁰). Предположим противное. Тогда найдется такая подпоследовательность {k_l}, что . Возьмем последовательность . В силу компактности множества Y можно считать, что . Покажем, что y⁰  Y(x⁰). Действительно, по определению y^kl

Переходя в этом неравенстве к пределу при l и используя непрерывность функции F(x, y), получим

Наконец, (противоречие).

2) Покажем, что функция y(x) непрерывна на X. Предположим, что она разрывна в некоторой точке x⁰X. Тогда найдется такая последовательность {x^k} элементов из X, сходящаяся к x⁰, что соответствующая последовательность {y(x^k)} не сходится к y(x⁰). Поэтому существует окрестность U точки y(x⁰), вне которой находится бесконечное число членов последовательности {y(x^k)}. В силу компактности множества Y \U из этой последовательности можно выделить подпоследовательность {y(x^kl)}  Y \U, сходящуюся к некоторому элементу y’ y(x⁰). Но, как и в части 1), нетрудно доказать, что y’  Y (x⁰). Получили противоречие с тем, что множество Y(x⁰) состоит из единственного элемента.

Замечание. В процессе доказательства теоремы мы также установили замкнутость множества {(x, y) | xX, yY(x)}. Отметим также, что в теореме 2.2 компактность множества Y существенна.

$3. Смешанные расширения антагонистических игр

В предыдущем параграфе приводился пример антагонистической игры, не имеющей решения ("орлянка"). Играть в подобные игры весьма непросто. Проигравшему игроку каждый раз хочется сменить свою стратегию, но он будет бояться это сделать (а вдруг партнер догадается?). Теория игр предлагает игрокам использовать смешанные стратегии.

Определение. Смешанной стратегией первого игрока в игре Г называется вероятностное распределение  на множестве стратегий X.

Для первого игрока применить смешанную стратегию  - это выбрать стратегию xX как реализацию случайной величины, имеющей закон распределения . Далее рассматриваются три вида смешанных стратегий.

Пусть X = {1, ...,m}, как это имеет место в матричной игре. Тогда вместо  для обозначения смешанной стратегии будем использовать "вероятностный" вектор p = (p₁, ..., p_m), удовлетворяющий ограничениям , p_i0, i=1,…,m. Если применяется p, то стратегия i выбирается с вероятностью p_i. Например, в игре "орлянка"опытные игроки используют смешанную стратегию p⁰ = (1/2, 1/2), подбрасывая монету и выбирая "орел" или "решку"в зависимости результата бросания. Вообще, одна из возможных реализаций смешанной стратегии – это бросание монет. С помощью одного бросания одной монеты можно осуществить только вероятность 1/2. С помощью двух монет или двукратного бросания одной монеты можно уже реализовать вероятности 1/2, 1/4 и 3/4. Ясно, что бросанием нескольких монет или многократным бросанием одной монеты можно реализовать широкий спектр вероятностей. Другой возможный и более удобный способ реализации смешанной стратегии - использовать рулетку. Делим круг рулетки на сектора с площадями, пропорциональными заданным вероятностям использования чистых стратегий. Затем вращаем стрелку и используем ту стратегию, в секторе которой она остановится.
Пусть X = [a, b], как это имеет место в непрерывной игре на прямоугольнике. Здесь смешанная стратегия - функция распределения  на отрезке [a, b].

Пример 3.1. Пусть X = [0, 1], c(x) - неубывающая дифференцируемая функция, определенная на отрезке [1/2, 1] и удовлетворяющая условиям c(1/2) = 1/2, c(1) = 1. Определим функцию распределения

Интеграл Стилтьеса от непрерывной функции h(x) по функции распределения ₀(x) вычисляется по формуле

Пусть X - выпуклый компакт евклидова пространства. Здесь примером смешанной стратегии может служить вероятностная мера, сосредоточенная в конечном числе точек:

где

Отметим, что для любого борелевского множества B .

При использовании меры  стратегия x(i) выбирается с вероятностью p_i. Интеграл от непрерывной функции h(x) по рассматриваемой мере имеет вид

Обозначим через {} - множество всех смешанных стратегий первого игрока на множестве X. Можно считать, что X  {}. Действительно, в последнем случае стратегию x можно отождествить с вероятностной мерой I_x. Если множество X конечно, то выбор i эквивалентен выбору смешанной стратегии p = (0, ...,0, 1, 0,...,0), где единица стоит на i-м месте, а при X = [a, b] стратегию x  [a, b] можно отождествить с функцией распределения, имеющей скачок 1 в точке x.

Множество X будем называть множеством чистых стратегий первого игрока (в противовес смешанным).

Займемся построением смешанного расширения антагонистической игры

Г = <X, Y, F(x,y)>. Мы определили множество {} смешанных стратегий первого игрока. Аналогично, пусть {} - множество смешанных стратегий второго игрока, т.е. вероятностных распределений  на множестве Y его чистых стратегий. При заданных стратегиях  и  математическое ожидание выигрыша первого игрока определяется формулой

Здесь предполагается, что двойной интеграл существует.

Определение. Антагонистическая игра называется смешанным расширением игры Г.

Определение. Решение игры называется решением исходной игры Г в смешанных стратегиях. При этом ⁰, ⁰ называются оптимальными смешанными стратегиями игроков, а  - значением игры Г.

Далее будут построены смешанные расширения матричных и непрерывных игр и будет показано, что эти игры всегда имеют решение в смешанных стратегиях.

Напомним, что матричная игра Г задается матрицей A = (a_ij)_m__n. Множество смешанных стратегий первого игрока –

множество смешанных стратегий второго игрока -

а математическое ожидание выигрыша первого игрока -

Таким образом, - смешанное расширение матричной игры Г.

Теорема 3.1 (Основная теорема матричных игр). Всякая матричная игра имеет решение в смешанных стратегиях.

Доказательство. Достаточно доказать ,что функция A(p, q) имеет седловую точку на PQ. Множества P, Q - многогранники евклидовых пространств, а функция A(p, q) билинейна и поэтому непрерывна на PQ, вогнута по p и выпукла по q. По теореме 2.3 функция A(p, q) имеет на PQ седловую точку.

Упражнение 3.1. Покажите, что тройка (p⁰, q⁰, ) = ((1/2, 1/2), (1/2, 1/2), 0) - решение в смешанных стратегиях игры "орлянка".

Отметим типичные случаи, когда применяются смешанные стратегии.

1) Игра повторяется много раз. В этом случае за большое число повторений игры средний выигрыш первого игрока, использующего оптимальную смешанную стратегию, будет близок к значению игры или будет превышать его.

2) Смешанная стратегия реализуется в виде "физической смеси" чистых стратегий. Что это означает, поясним на примерах.

Пример 3.2. Игра против природы. Фермер (игрок 1 ) имеет участок земли, который можно засеять тремя сельскохозяйственными культурами. Год может быть нормальным, засушливым и дождливым (это три стратегии игрока 2 - природы). Пусть H = (h_ij)₃_₃ - матрица урожайности, а b_i - цена за единицу продукции i-го вида. Тогда A = (b_ih_ij)₃_₃ - матрица игры, где выигрыш фермера - стоимость произведенной продукции. Пусть p⁰ = (1/2, 1/4, 1/4) - оптимальная смешанная стратегия первого игрока. Реализовать ее можно, засеяв половину участка первой культурой, а оставшиеся две четверти - второй и третьей культурами.

Пример 3.3. Некоторая страна (игрок 1) использует три типа истребителей для борьбы с самолетами противника (игрока 2). Если истребитель типа i первого игрока встречается с самолетом типа j второго игрока, то он побеждает противника с вероятностью a_ij . Смешанная стратегия p⁰ = (1/2, 1/4, 1/4) первого игрока может быть реализована в виде парка

истребителей с пропорциями типов 2:1:1.

Смешанные стратегии можно применять и при однократном повторении игры, когда игрок действует в условиях риска. При этом необходимо выигрыши заменить на их "полезности", учитывающие отношение игрока к риску.

Пример 3.4. Пусть игрок вынужден один раз сыграть в игру с матрицей . Выигрышам 10 и 0 припишем полезности 1 и 0. Определим полезность выигрыша 5. Пусть в некоторой лотерее выигрыш 10 ожидается с вероятностью 0<a<1. Первому игроку предлагается выбрать такое значение a, при котором игрок согласен купить лотерейный билет по цене 5. Выбранное значение a и будет полезностью выигрыша 5. Если a = 1/2, то отношение игрока к риску нейтральное, если a > 1/2, то игрок осторожен, а если a < 1/2, то игрок азартен.

**************************

Элементы теории полезности см. в конце данного параграфа.

Займемся смешанным расширением непрерывной игры Г. Ограничимся игрой на прямоугольнике XY = [a, b]  [c, d]. При заданных стратегиях  и  - функциях распределения на отрезках X и Y - ожидаемый выигрыш F(, ) первого игрока равен

Здесь двойной интеграл от непрерывной функции F(x, y) существует. Более того, по теореме Фубини он равен повторному

где

Итак, построено cмешанное расширение непрерывной игры Г на прямоугольнике. Наша ближайшая цель – доказать существование решения игры .

Нам потребуется известный результат.

Теорема 3.2. Множество смешанных стратегий {} на отрезке [a, b] является слабым компактом. Это означает, что из любой последовательности смешанных стратегий {^k} можно выделить подпоследовательность {^kl}, слабо сходящуюся к некоторой стратегии ⁰, т.е. такую, что для любой непрерывной на отрезке [a, b] функции h(x) выполнено

Лемма 3.1. В непрерывной игре Г на прямоугольнике существуют максиминная и минимаксная смешанные стратегии игроков.

Доказательство. Рассмотрим выражения

и докажем, что внешние sup и inf в них достигаются. По определению верхней грани найдется такая последовательность смешанных стратегий {^k}, что

или

(3.1)

Выделим из {^k } подпоследовательность {^kl}, слабо сходящуюся к смешанной стратегии ⁰. Заметим, что при фиксированной стратегии  функция F(x,) непрерывна по x. Переходя в (3.1) к пределу по подпоследовательности {k_l}, получим неравенство F(⁰, )     {}.