Игры с квадратичными функциями

6

Б. Вергеём

или вправо от себя. Их мастерство отражено в таблице *): если игрок

Игры
с квадратным функциями

Можно ли изучать математку игра? Оказывается, можно, так как в математике есть много задач, описывающих «игровые ситуации».

Мы займемся играми, связанными с поиском наиболее и наиболее значений функций. Искусство такого поиска важно во многих задачах экономики, военноного дела, биологии, спорта,…

Решающее десять одинаковатиметровых

Мы — на футбольном поле. Игрок А и вратарь В готовятся к серии из 10 одинаковатиметровых ударов. Игрок будет вправо или влево; вратарь, пытаясь угадать направление удара, готовится к прыжку влево

бет вправо (это его стратегия № 1), а вратарь готовится к прыжку влево от себя (это стратегия № 1 для B), то в среднем вворотах будет 7 мячей из 10; если же B готовился к прыжку вправо, то вляется 10 мячей и т. д.

Оба игрок будутередовать свой выбор случайным образом. Если каждый из них выбирает каждую из своих стратегий примерно в половине случайев (как говорят, с вероятностью 1/2), то в среднем будет забито (7+10+9+6):4=8 мячей.

Если же А будет применять свою первую стратегию с вероятностью 0,6 (в 60% случайе), а вторую — с вероятностью 0,4 (в 40% случайе),

*) В теории игри и в экономике подобные таблицы называются плательными матрицами.

7

a вратарь — своего первую стратегию с вероятностью 0,8, а вторую — с вероятностью 0,2, то в среднем будет забито $(7 \cdot 0,6 + 9 \cdot 0,4) \times 0,8 + (10 \cdot 0,6 + 6 \cdot 0,4) \cdot 0,2 = 7,92$ мяча, что меньше 8. Конечно, говорить о том, что в данной конкретиной серии будет забито 7,92 мяча бессмысленно. Здесь имеется в виду, что при многократном повторении серий, удовлетворяющих поставленным условиям, среднее количество забитых мячей (отношение объщего количества мячей к числу серий) будет близко к числу 7,92.

Пусть вообще $A$ выбирает свои первую и вторую стратегии с вероятностью $x$ и $1-x$ ($0 \leq x \leq 1$), а $B$ — с вероятностью $y$ и $1-y$ ($0 \leq y \leq 1$). В этом случае говорят, что числа $x$ и $y$ определяют смешанные стратегии игроков. тогда среднее число забитых мячей равно $m = (7x + 9(1-x))y + (10x + 6(1-x)) \times (1-y) = -6xy + 4x + 3y + 6$. (*)

Естественно возникает вопрос: каковы наиболее значения $x$ для $A$, $y$ — для $B$? Наилучшее значение $x^*$ для $A$, размещается, должно гарантировать минимальное число забитых мячей (в среднем), независимо от тактики вратара. Наилучшее значение $y^*$ для $B$ должно гарантировать минимальное количество забитых мячей (в среднем), независимо от стратегии игрока, былошего пеналы.

Оказывается (вы в этом убедитесь, решив упражнение 1), $x^* = 1/2$, $y^* = 2/3$; в этом случае будет забито (в среднем) $m^* = 8$ мячей. Легко проверить (обязательно сделать это!), что если хотя бы один из играющих будет придерживаться указанной «наилучшей» стратегии, то независимо от стратегии другого будет забито $m^* = 8$ мячей (в среднем). Если же один из играющих от указанной стратегии, то он уже не может ничего гарантировать — результат будет зависеть от действия правилника.

Так, если вратарь будет одинаково часто прыгать вправо и вплево (то есть $y = 1/2$), а игрок все время быть в правый угол ($x = 0$), то будет забито в среднем меньше мячей ($m = 7,5$). Но если игрок $A$ охитtee, он будет всегда быть влевый угол ($x = 1$) и тогда станет забивать чаше ($m = 8,5$).

А теперь отдохнем от футбола, отверяностей и займемся «просто» функциями, причем без ограничений на $x$ и $y$ — это облегчит первые шаги.

Выиграш, проигрыш, ничья

Пусть две игроков играют в такую игру: $A$ выбирает действительное число $x$, $B$ — число $y$, причем каждый делает свой выбор, не зная выбора противника. Оба числа сообщаются судьбе, после чего по заранее известному игрокам правли подсчитывается выиграш первого $v = f(x, y)$, равный проигрышу второго; точнее говоря, при $v > 0$ А выиграшает у $B$ величины $v$, при $v < 0$ А проигрышает $B$ величины $|v|$; если же $v = 0$, то в игре — ничья; символ $f(x, y)$ означает, что $v$ — это заданная функция двух переменных ($x, y$).

Пусть, например, правило подсчитета выиграша в игре таково:

$$v = y^2 - x^2.$$

Попробуйте сыграть несколько раз по правлу (1). После нескольких «партей» игрок заметят, что каждому из них лучше выиграть нулявые значения: при $x = y = 0$ получается ничья, причем ни одному из игроков невыгодно отклоняться от этого выбора, даже зная выбор противника.

Действительно, поскольку при $x = 0$ $v = y^2$, наилучший ответ игрока $B$ — это выбор $y = 0$. Аналогично, при $y = 0$ $v = -x^2$ и наилучший ход $A$ — это $x = 0$.

Теперь ужеясно, что играть с плагежной функцией $v = y^2 - x^2$ не интересно: ничья обеспечена как тому, так и другому игроку. Труднее и интереснее играть со следующей плагежной функцией:

$$v = y^2 - x^2 + 8x - 10y + 9.$$

Существуют ли в этом случае такие числа $x$ и $y$, которые можно рекомендовать игрокам и от которых им будет «накладно» отклоняться?

Простой ключ к игре (2) дает разложение

8

Рис. 1.

$$v = (9 - x - y)(x - y + 1).$$

Составив систему уравнения
$$\begin{cases} 9 - x - y = 0, \\ x - y + 1 = 0, \end{cases}$$

имеющий единственное решение $x^* = 4, y^* = 5$, заключаем, что игра (2) имеет ничейный исход $v^* = v(x^*, y^*) = 0$ при $x = x^* = 4, y = y^* = 5$.

Геометрическое объяснение здесь таково (рис. 1): пара чисел $(x^*; y^*) \in R^2$ определяется точкой пересечения прямых, соответствующих уравнением системы; если точка с координатами $(x; y)$ лежит на одной из них, то $v = 0$; для точек, лежащих внутри углов, образованных на шимми прямыми, величины $v$ имеет знак, указанный на рисунке. Этот рисунок дополяют следующие вычисления и рассуждания; если $x = 4$, то $v = (5 - y)^2 \geq 0$; $v_{\min} = 0$ при $y = 5$ (в точках вертикали $x = 4$ всегда $v \geq 0$); если $y = 5$, то $v = -(x - 4)^2 \leq 0$; $v_{\max} = 0$ при $x = 4$ (вдоль горизонтали $y = 5$ имеем $v \leq 0$).

Таким образом, если $A$ выберет $x = 4$, то игрок $B$ при любом выборе, кроме $y = 5$, проиграает. Аналогично, если $A$ выберет $x \neq 4$, игрок $B$ выиграет взяв $y = 5$.

Итак, у первого игрок есть ход, сделав который он заведomo не проиграет. Такой же ход есть и у второго игрок. Поэтому в этой игре тот, кто рискнет сыгать не «по теории», тот и проиграает (если, конечно, и его противник не идет на риск отказа от теории).

Приведем для примера результаты пятки партий нашей игры (в каждой тройке первого число — это $x$, второе — $y$, третье — $v$): $(0,0,9), (0,7, -12), (4,7,4), (4,5,0), (5,5, -1)$.

Изучение этих партий подсказывает еще один путь решения (к сожалению, не всегда пригодный). Пробуем рассудать за первого игрок: «Если $B$ выберет $y = y_0$, то тогда получается квадратный треугольен $v(x, y_0) = (9 - y_0 - x)(x - y_0 + 1)$ относительно $x$, который я должен сделать как можно большем, выбрав подходящие $x$; но у этого треугольена максимум при $x = 4$, поэтому я хочу $x = 4!$. Рассудя аналогично, второй игрок обеспечит себе минимальный проигрывший $y = 5$ (при любом ходе $x = x_0$ приводого).

Седловая точка и решение игры

Мы видели, что в игре с функцией (2) каждой игрок может гарантировать себя от проигрыша, так как удалость найти такую пару чисел (4:5), что $f(4,5) = 0$ и для всех остальных $x$ и $y$ значения функции $f$ удовлетворяют неравенству
$$f(x, 5) \leq f(4, 5) \leq f(4, y).$$

Отсюда видно, что первый игрок выбирая $x = 4$, во всяком случае, не проигравает (это вытекает из последнего неравенства), как не проигравает и второй, выбирая $y = 5$.

Дадим общее определения.

Определение седловой точки.

Пусть задана функция $f$, определенная на некотором множество $G$ точек плоскости. Точка $(x^*; y^*) \in G$ называется седловой точкой функции $f$ или точкой равновесия, если при $(x, y^*) \in G, (x^*, y) \in G,$
$$f(x, y^*) \leq f(x^*, y^*) \leq f(x^*, y).$$

Из этих неравенств следует, что $\max f(x, y^*) = f(x^*, y^*) =$
$$= \min f(x^*, y)$$
(влевой части максимум по переменной $x$ при функционином $y = y^*$, в правой части — минимум по $y$ при функционином $x = x^*$).

В теории игрок седловую точку $(x^*; y^*)$ часто называют решением игры (с платежной функцией $v = f(x, y)$), число $v^* = f(x^*, y^*)$ называют ценой игры, а числа $x^*, y^*$ — оптимальные стратегии первого и второго игроков соответственно.

9

Рис. 2.

Туристы и альпинисты

Туристы, желая пройти из долины $D_1$ в долину $D_2$, идут через перевал (седловину) — при этом максимальная высота на пути из $D_1$ в $D_2$ (рис. 2) оказывается минимальной по сравнению со всеми близкими маршрутами, не проходящими через седло. Альпинисты, желая совершить траверс от вершины $V_1$ к вершине $V_2$, проходят то же седло по другой причине — чтобы не «терять высоту», то есть чтобы была максимально возможной минимальная высота на пути от $V_1$ к $V_2$.

Рисунок 1 показан на карту, где высота перевала принята за нуль, а $x$ и $y$ — это долота и широта. Будем рассматривать прямые, параллельные осями, как возможности пути для туристов и альпинистов. Подобно маршрутам в горах, основные прямые рисуна 1 ($y=5$ и $x=4$) выделены тем, что
$$f(x^*, y^*) = \min_{y} \max_{x} f(x, y) = \max_{x} \min_{y} f(x, y),$$
и это очень полезно при анализе игра. Здесь max $f(x, y)$ — наиболее значение $f$ при заданном $y$ и переменном $x$, то есть это нахождение исход для $B$ при выбранном значении $y$; очевидно, это велича минимальная при $y=5$. Истолкуйте аналогично выбор $x=4$ для играка $A$.

Рассмотрим теперь игра с платежной функцией $v=x^2-y^2$, у которой нет седловой точки (убедитесь в этом). Анализ игра с подобной функцией сильно осложняется. В данном примере противники будут заинтересованы выбирать самые большие числа, как им достичьы. Если ввести ограничения на переменные $x$ и $y$ вида $|x| \leq a, |y| \leq b$, что передко встречается на практике, появятся 4 седловые точки: $x^* = \pm a, y^* = \pm b, (v^* = a^2 - b^2)$.

Однако при такого рода ограничения седловая точка может и не появиться (см. упр. 3).

Решение игры с квадратной платежной функцией

Итог нашим теоретическим рассмотрением подводит следующая теорема. Пусть дана цера с платежной функцией
$$v = ax^2 + 2bxy + cy^2 + 2px + 2qy + r.$$
Эта функция имеет седловую точку, а цера — решение в следующих семи случаях и только в них:

1. $a < 0, c > 0$;
2. $a < 0, c = 0 \neq b$;
3. $a < 0, c = b = q = 0$;
4. $a = 0 \neq b, c > 0$;
5. $a = b = p = 0, c > 0$;
6. $a = c = 0, b \neq 0$;
7. $a = b = c = p = q = 0$.

Седловая точка является решение системы уравнений
$$\begin{cases} ax + by + p = 0, \\ bx + cy + q = 0. \end{cases}$$

Это решение $(x^*, y^*)$ во всех этих случаях, кроме цера, читатель: разбор предыдуших конкретных примеров помогет ему.

Уражнения

1. а) Расмотите игра с платежной функцией $m = 6 + 4x + 3y(1-2x)$ и найдите значение $x$, при котором $m$ не зависит от $y$, а также значение $y$, при котором $m$ не зависит от $x$. Дает ли эта пара значений решения игры?

2. Найти решение и цены игра со следующими платежными функциями:
   a) $v = -x^2 + 6xy + y^2 - 10x - 10y + 15$;
   b) $v = (x + y - a)(y - x - b)$;
   c) $v = 10\ln x - x^2 + 2xy + y^2 + 10x - 8y - 40, x > 0$;
   d) $v = k(\sqrt{x}, -\sqrt{y}) + \sqrt{a-x} - \sqrt{b-y}$;
   d) $v = k(-x^2 + 2pxy + y^2) - x_0^2 - 2px_0y + y_0^2$, где $x_0 = a - x, y_0 = b - x$;