Дележ, отвечающий аксиомам Нэша

Замечание 3.3 (о графическом определении точки $$(u^\circ, v^\circ)$$, доставляющей максимум функции g ). Согласно (15.9), (15.10), уравнение опорной прямой можно представить в виде$$v = v^\circ - K(u - u^\circ),\qquad K = \frac{v^\circ - v^\ast}{u^\circ - u^\ast}.$$ При этом уравнение прямой$$v = v^\ast + K(u - u^\ast),$$ проходящей через точки (u*,v*) и $$(u^\circ, v^\circ)$$, характеризуется тем же коэффициентом K, что и в (15.12) Таким образом, прямые линии (15.12) и (15.13) пересекаются в точке $$(u^\circ, v^\circ)$$. Кроме того, они образуют равные (по абсолютной величине) и противоположные (по знаку) углы с вертикалью, опущенной из этой точки (в качестве иллюстрации см. рис. 3.3). Отмеченное соотношение углов может быть использовано для графического определения точки $$(u^\circ, v^\circ)$$, соответствующей задаче (S,u*,v*).

Лемма 3.3. При выполнении условий (15.2) точка $$(u^\circ, v^\circ)$$ из (15.5) удовлетворяет всем аксиомам Нэша.

Доказательство Выполнение условий (14.15) и (14.16) является следствием определения (15.5). Допустим, что в множестве S существует точка (u',v'), доминирующая (т.е. улучшающая) отличную от нее точку $$(u^\circ, v^\circ)$$. Тогда должно выполняться неравенство$$g(u',v') = (u' - u^\ast)(v' - v^\ast) > (u^\circ - u^\ast) (v^\circ - v^\ast) = g(u^\circ, v^\circ),$$ противоречащее определению (15.5). Заметим, что из сделанного допущения $$(u', v') \ge (u^\circ, v^\circ)$$ вытекает включение $$(u', v') \in S_0$$. Т.е. аксиома (14.17) также должна выполняться.

Если $$(u^\circ, v^\circ) \in T \subset S$$, то максимум функции g(u,v) на множестве $$T \cap S_0$$ достигается в той же точке, что и на множестве S0. Т.е. пара $$(u^\circ, v^\circ)$$ из определения (15.5) удовлетворяет условию (14.19).

Проверим выполнение пятой аксиомы. Согласно (14.20) и (15.3),$$g(\tilde{u},\tilde{v}) = \alpha \beta g(u,v).$$ Теперь из (15.5) и (15.14) вытекает, что$$(\forall (\tilde{u}, \tilde{v}) \in T_0)\, g(\tilde{u}^\circ, \tilde{v}^\circ) =\alpha \beta g(u^\circ, v^\circ) \ge \alpha \beta g(u,v) = g(\tilde{u}, \tilde{v}),$$ где T0 есть образ S0 при соответствии (14.20). Следовательно,$$g(\tilde{u}^\circ, \tilde{v}^\circ) = \max\{g(\tilde{u}, \tilde{v})\colon (\tilde{u}, \tilde{v}) \in T_0\}$$ и справедливость (14.21) установлена.

Пусть множество S симметрично, т.е. из включения $$(u, v)\in S$$ следует включение $$(v, u) \in S$$, и пусть u*=v*. Тогда$$(u^\circ, v^\circ) \in S \to (v^\circ, u^\circ) \in S$$ и$$g(u^\circ, v^\circ) = (u^\circ - u^\ast)(v^\circ - v^\ast) = (v^\circ - u^\ast)(u^\circ - v^\ast) = g(v^\circ, u^\circ).$$ Теперь из единственности точки максимума вытекают следствия$$(u^\circ, v^\circ) = (v^\circ, u^\circ) \to u^\circ = v^\circ,$$ доказывающие справедливость аксиомы (14.22).

Лемма 3.4. При выполнении условий (15.2) точка $$(u^\circ, v^\circ)$$ из (15.5) есть единственная сделка, удовлетворяющая аксиомам Нэша.

Доказательство Определим множество$$W = \{(u,v) \in R^2\colon h(u,v) \le h(u^\circ, v^\circ)\},$$ лежащее под опорной к нему прямой (15.9) и содержащее допустимое множество S (см. рис. 3.4). Введем линейное преобразование$$\tilde{u} = \frac{u - u^\ast}{u^\circ - u^\ast}, \quad \tilde{v} = \frac{v - v^\ast}{v^\circ - v^\ast}$$ и определим множество T, являющееся образом W относительно преобразования (15.15).

Из (15.10) и определения W выводим неравенство$$(v^\circ - v^\ast)(u - u^\circ) + (u^\circ - u^\ast)(v - v^\circ)\le 0,$$ которое после использования обратного (15.15) отображения$$u = (u^\circ - u^\ast)\tilde{u} + u^\ast,\qquad v = (v^\circ - v^\ast)\tilde{v} + v^\ast$$ дает определение$$T = \{(\tilde{u},\tilde{v}) \colon \tilde{u} + \tilde{v} \le 2\}.$$ При этом, согласно (15.15), $$\tilde{u}^\ast = 0$$, $$\tilde{v}^\ast = 0$$.

Таким образом, линейное преобразование (15.15) переводит задачу (W,u*,v*) в задачу (T,0,0), удовлетворяющую условиям аксиомы симметрии. Простота этой задачи позволяет найти отвечающую ей сделку, руководствуясь непосредственно аксиомами Нэша. Требования рациональности, допустимости, не улучшаемости и вытекающее из шестой аксиомы условие $$\tilde{u}^\circ = \tilde{v}^\circ$$ удовлетворяются в единственной точке$$(\tilde{u}^\circ, \tilde{v}^\circ) = (1,1) \in T,$$ лежащей на границе множества T (см. рис. 3.5).

Отображая точку (15.18) на плоскость (u,v) в соответствии с преобразованием (15.16) и принимая во внимание пятую аксиому, получаем, что пара $$(u^\circ, v^\circ)$$ есть единственная отвечающая аксиомам сделка в задаче (W,u*,v*). Наконец, учитывая включения $$(u^\circ, v^\circ)\in S \subset W$$ и четвертую аксиому, выводим, что пара $$(u^\circ, v^\circ)$$ есть единственная удовлетворяющая аксиомам сделка в исходной задаче (S,u*,v*). Таким образом, единственная удовлетворяющая аксиомам сделка совпадает с точкой из определения (15.5).

Завершение доказательства теоремы. Остается рассмотреть случаи, когда не выполняются предположения (15.2). При этом возможны следующие три ситуации:$$(\exists (u,v) \in S)\ u > u^\ast,\ v = v^\ast,$$ $$(\exists (u,v) \in S)\ u = u^\ast,\ v > v^\ast,$$ $$(\forall (u,v) \in S)\ u \le u^\ast,\ v \le v^\ast.$$ Заметим, что ситуации (15.19) и (15.20) не могут иметь место одновременно. Допущение такой возможности ведет (в силу выпуклости множества S ) к выполнимости условий (15.2) для всех внутренних точек отрезка, соединяющего две произвольные точки из (15.19) и (15.20).

Рассмотрим случай (15.19) (случай (15.20) рассматривается аналогично). Решение для таких задач определяется оператором $$\varphi$$ вида$$u^\circ = \max\{u \colon (u,v) \in S_0, v = v^\ast\},\ v^\circ = v^\ast.$$ Рис. 3.6 иллюстрирует такой случай, заведомо не удовлетворяющий условиям симметрии из шестой аксиомы.

Решение (15.22) допустимо, рационально и неулучшаемо (для обеих сторон). Заметим также, что оно является единственным решением, удовлетворяющим первым трем аксиомам. Кроме того, правило (15.22) определяет пару $$(u^\circ, v^\circ)$$ как решение задачи $$(T, u^\circ, v^\circ)$$, если $$(u^\circ, v^\circ) \in T \subset S$$. Т.е. четвертая аксиома также выполняется.

Любые преобразования вида (14.20) переводят горизонтальный участок границы множества S, лежащий на прямой u=v*, в горизонтальный участок границы множества T, лежащий на прямой $$\tilde{v} = \beta v^\ast + b$$. Следовательно, правило (15.22) даст для задачи $$(T, \tilde{u}^\ast, \tilde{v}^\ast)$$ дележ $$(\tilde{u}^\ast, \tilde{v}^\ast)$$, согласующийся с пятой аксиомой.

В случае (15.21), когда кооперация не может улучшить выигрыши сторон, положим $$(u^\circ, v^\circ) = (u^\ast, v^\ast)$$. Соответствие такого решения аксиомам Нэша легко проверяемо.

Вернемся к рассмотренным выше примерам. Дележ $$(u^\circ{,} v^\circ){=} (10{,}14)$$, изображенный темным кружком в верхней части рис. 3.3, получен с помощью графического построения. Построение выполнено в соответствии с ранее описанным приемом. Этот дележ реализуется путем согласованного использования обеими сторонами пары чистых стратегий i=2, j=2 (см. табл. 3.1).

Допустимое множество $$S$$ для рассмотренной в лекции 8 задачи об ограничениях при ловле рыбы, представлено на рис. 3.7. Согласно (14.7)-(14.14), для содержащих седловые значения матриц этой задачи справедливы оценки:$$(u^\ast, v^\ast) = (u^\ast, v') = (u', v^\ast) = (\mu_1(p^\ast),\mu_2(p^\ast)) = (6,6).$$ Имеющее место совпадение всех указанных точек отражает то обстоятельство, что пара выигрышей (u*,v*) соответствует единственному в этой задаче устойчивому решению, реализуемому в чистых стратегиях при независимом поведении сторон.

Решение $$(u^\circ, v^\circ) = (10,10)$$, оцененное графическим способом (см. рис. 3.7), существенно превосходит выигрыши, достижимые односторонними действиями участников. Таким образом, введение (по взаимному согласию сторон) системы контроля за соблюдением соглашения (например, путем организации проверок в местах лова рыбы) могло бы повысить их доходы (и дать средства для содержания инспекторов).

Допустимое множество для задачи о строительстве с долевым участием (см. лекцию 11) уже рассматривал ось (см. рис. 3.2). Этому примеру соответствуют оценки$$\begin{gathered} x^\ast = y' = \left(\frac{1}{3}, \frac{2}{3}\right),\quad y^\ast = x' = \left(\frac{2}{3}, \frac{1}{3}\right),\\ (u^\ast, v^\ast) = (\mu_1(p^\ast), \mu_2(p^\ast)) = (\frac{2}{3}, \frac{2}{3}). \end{gathered}$$ Заметим, что указанная выше пара смешанных стратегий x* и y* не является равновесным решением задачи при независимом поведении сторон (см. табл. 2.9). Поэтому пары (u*,v*) и$$(u^\ast, v') = \left(\frac{2}{3},1\right),\quad (u', v^\ast) = \left(1,\frac{2}{3}\right)$$ являются различными (см. рис. 3.8). Сделка, отвечающая аксиомам Нэша, соответствует точке $$(u^\circ, v^\circ) = (3/2,3/2)$$, реализуемой уже обсуждавшейся рулеткой (14.5).

Сделки с побочными платежами

Согласно сделанному выше предположению (см. замечание в лекции 14, функции выигрышей сторон можно интерпретировать как линейно трансферабельные полезности. Однако в предшествующем рассмотрении (при определении допустимого множества S из (14.6)) было введено ограничение, запрещавшее обмен полезностями между сторонами. Теперь мы рассмотрим случай, когда такого ограничения нет. При этом передача полезностей от одного игрока к другому не изменяет их суммарной полезности.

Допустимость обмена полезностями расширяет круг возможных договоренностей игроков, поскольку становятся реализуемыми сделки $$(u, v) \not\in S$$, если они удовлетворяют условию$$u + v = \mu_1(p) + \mu_2(p),$$ где p и $$\mu_1(p)$$, $$\mu_2(p)$$ соответственно из (14.2)-(14.4). Т.е. получаемая сторонами суммарная полезность из правой части равенства (15.23) может быть перераспределена между ними в согласованную пару (u,v) за счет побочных платежей.

Это обстоятельство определяет заинтересованность сторон в согласованной реализации такой стратегии p+ из (14.2), которая максимизирует суммарную полезность:$$\pi = \mu_1(p^+) + \mu_2(p^+) = \max\{\mu_1(p) + \mu_2(p) \colon p \in S_{m \times n}\}.$$ Задача оценки величины $$\pi$$ (15.24) эквивалентна линейной программе вида$$\pi = u^+ + v^+ = \max\{u + v \colon (u,v) \in S\}.$$ При этом решению одной из задач (15.24), (15.25) можно сопоставить решение другой из этих задач таким образом, что будут выполняться условия$$u^+ = \mu_1(p^+),\qquad v^+ = \mu_2(p^+).$$

Заметим, что в случае, когда допустимое множество S представляет собой плоский многоугольник (как это имеет место в случае биматричных игр), решение задачи (15.25) достигается в одной из неулучшаемых вершин этого многоугольника. Т.е. максимальная возможная величина суммарной полезности $$\pi$$ может быть достигнута в чистых стратегиях.

Исходя из реализуемости максимального значения из (15.22) и руководствуясь основными идеями схемы Нэша, перейдем к вопросу об оценке сделки (u+,v+), которую будут готовы согласовать стороны P1 и P2 с учетом побочных платежей. При этом будем полагать, что$$u_{+} + v_{+} = \pi$$ и передача полезностей от одной стороны к другой характеризуется побочными платежами$$\pi_1 = u_{+} - u^{+},\qquad \pi_2 = v_{+} - v^{+}.$$ Первый из них соответствует части выигрыша, которую получает (или передает) сторона P1, а второй указывает аналогичную величину для стороны P2. Отметим, что согласно (15.25)-(15.27), $$\pi_1 + \pi_2 = 0$$.

При этих предположениях стороны могут согласовать любую сделку из множества$$S_{+} = \{(u,v) \in R^2 \colon u + v \le \pi,\ u \ge u^\ast,\ v \ge v^\ast\},$$ которое заведомо не пусто. В силу простоты треугольного множества S+, сделка$$(u_{+} + v_{+}) = \varphi(S_{+}, u^\ast, v^\ast),$$ удовлетворяющая аксиомам Нэша, может быть определена как решение системы двух уравнений$$u_{+} + v_{+} = \pi,\qquad u_{+} - u^\ast = v_{+} - v^\ast.$$ Отсюда$$u_{+} = \frac{1}{2} \left[\pi + (u^\ast - v^\ast)\right]\!,\quad v_{+} = \frac{1}{2} \left[\pi - (u^\ast - v^\ast)\right]\!,$$ что позволяет оценить также побочные платежи из (15.27).

Пример 3.2. Вернемся к задаче о строительстве с долевым участием (см. лекцию 11) и введем новые платежные функции сторон, представленные в табл. 3.2. Пары чистых стратегий ( i=1, j=1 ) и ( i=2, j=2 ), соответствующие двум возможным районам строительства гостиничного комплекса с долевым участием, по-прежнему обладают свойствами устойчивости и эффективности. Однако, как мы уже указывали, при этом нет механизма выбора конкретной пары. Матрицы отражают также, что в случае отказа от строительства комплекса стороны используют свои средства для развития системы предприятий обслуживания. При этом сторона P1 несет убытки, если она развивает предприятия в "своем" (достаточно насыщенном услугами) районе Р1.

Допустимое множество S для рассматриваемой задачи представлено на рис. 3.9.

Точка $$(u^\ast, v^\ast) = (2\frac{1}{3},1 \frac{3}{4})$$, оцененная в соответствии с выражениями (14.7), (14.10) и (11.10), также отмечена на рис. 3.9. Дележ$$(u^\circ, v^\circ) = \varphi (S, u^\ast, v^\ast) = (155/48, 170/48),$$ удовлетворяющий аксиомам Нэша в задаче без побочных платежей, определен с помощью приема из замечания 3.3 этой лекции (отмечен на рисунке). Этот дележ реализуем рулеткой вида$$p^\circ = (11/48,0,0,37/48).$$

Далее, (u+,v+)=(3,4), $$\pi = 7$$ и, согласно (15.30), (u+,v+)=(91/24,77/24). Т.е. (в случае договоренности) стороны согласованно реализуют пару чистых стратегий ( i=2, j=2 ), и затем вторая сторона выплачивает первой стороне часть своего выигрыша, которой соответствует полезность $$\pi_1 = 19/24$$.