Редактирование: Тигры, 02 лекция (от 11 сентября)

Материал из eSyr's wiki.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

* '''Аудиозапись:''' http://esyr.org/lections/audio/game_theory_2008_winter/GT_08_09_11.ogg

Осталось доказать, что ...

x &isin; X, y &isin; Y, t &isin; (0,1)

K((1-t)x*+tx+y) &gt; (1-t)k(x*,y) + tK(x, y) &ge; (1-t)_w_(x*) + tK(x,y)

ỹ = y((1-t)x* + tx) --- это верно при фикс. ...

_w_(x*) &ge; _w_((1-t)x* + tx) &gt; (1-t)_w_(x*) + tk(x, ỹ) --- мыр списли эт сотн. при y=ỹ

t_w_(x*) &gy; tK(x,ỹ)

_w_(x*) &gt; K(x, y((1-t)x* + tx))

Это соотношение справедливо  &forall;t &isin; (0,1). Устремим t к 0. Что получится:

_w_(x*) &ge; K(x,y(x*)) (здесь мы используем доказанную в начале непр.)

Левая величина _w_(x*) = K(x*, y(x*))

То есть показано, что это — седловая точка.

Теперь откажется от строгости выпуклости/вогнутости.

Введём функцию K_&epsilon;(x,y) =  K(x,y) - &epsilon; &sum_{i=1}^n x_i^2 + &epsilon; &sum_{j=1}^m y_j^2, &epsilon; &gt; 0

Так как каждое из слагаемых строго выпукло по x/y, то и сумма тоже строго выпукла по x и y. Следовательно, для неё верно только что доказанное утверждение: (x_&epsilon;, y_&epsilon;) — седловая точка. K_&epsilon;(x,y)

K_&epsilon;(x,y_&epsilon;) &le; K_&epsilon;(x_&epsilon;,y_&epsilon;) &lt; K_&epsilon;(x_&epsilon;,y), &forall; x &isin; X, y &isin; Y

K(x, y_&epsilon;) — &epsilon; &sum_{i=1}^n x_i^2 &le; K_&epsilon;(x,y_&epsilon;) &le; K_&epsilon;(x_&epsilon;,y_&epsilon;) &le; K(x_&epsilon;,y) + &epsilon; &sum_{j=1}^m y_j^2

Итог следующий:

K(x, y_&epsilon;) — &epsilon; &sum_{i=1}^n x_i^2 &le; K_&epsilon;(x_&epsilon;,y_&epsilon;) &le; K(x_&epsilon;,y) + &epsilon; &sum_{j=1}^m y_j^2, &forall; x &isin; X, y &isin; Y

Теперь &epsilon;_n &rarr; 0, n &rarr; &infin;, &epsilon;_n &gt; 0. Тогда эти слагаемые устремляются к нулю, из ограниченной последовательности можно выделить сходящуюся, соответственно, без ограничения общности y_{&epsilon;_n} &rarr; y*, x_{&epsilon;_n} &rarr; x*, и получаем

K(x, y*) &le; K(x*, y),  из этого условия мы доказывали ранее, что K(x*, y*) — седловая точка.

Важно отметить, что эти условия являются достаточными, но не необходимыми.

Пример (условие не является необходимым):

K(x,y) = x^e + 0&times;y, x, y &isin; [0,1]. (1,1) — седловая точка. (доказать дома)

Пример:

K(x,y) = y ln(x+3) + xy^2, x, y &isin; [0,1]

Условия теоремы фон Неймана выполняются:

K_{x}' = y/(x+3) + y^2

K_{xx}'' = –y/(x+3)^2 &le; 0 — вогнута по x

K_{y}' = ln(x+3) + 2xy

K_{yy}'' = 2x &ge; 0 — выпукла по y.

Условие теоремы фон Неймана выполнено, и есть седловая точка (показать дома, чт это (1,0))

Теорема конструктивная и вообще говоря, ей можно пользоваться для нахождения седловой точки.

Сейчас рассмотрим частный случай платёжной функции, для которой есть простой алгоритм. Он позволяет свести поиск седловой точки к решению системы уравнений и решению матричной игры.

Раздел: необходимое условие для седловой точки

Рассмотрим следующий случай: множество стратегий X имеет следующий вид: X={x=(x_1, ..., x_n), 0 &le; a_i &le; x_i &le; b_i, i = 1..n}, Y={y=(y_1, ..., y_m), 0 &le; c_i &le; y_j &le; d_j, j = 1..m}

Предполагаем, что K(x, y) непрерывно на X&times; Y и имеет частную производную K_{x_i}', K_{y_j}', i=1..n, j=1..m.

Прежде, чем вып. след. деёств, рассмотрим систему: 
 K_{x_i}'(x, y)(x_i - a_i)(x_i - b_i) = 0, i=1..n
 K_{y_j}'(x, y)(y_j - c_j)(y_j - d_j) = 0, j=1..m (*)
Предположим, что эта система имеет решение и множество решений конечно. Тогда пр. следующие множества: те x из X, что:

X^c = {x &isin; X: &exist;y &isin; Y, (x,y) &isin; X}

....

'''Теорема'''. Если (x_0, y^0) — седловая точка K(x,y) на X&times;Y, то (x_0, y^0) &isin; C, (x_0, y^0) — c.т. K на X^c&times;Y^c

Эта теорема даёт нам алгоритм поиска седловой точки. Пусть есть такая функция и выполнены все условия мы выписываем систему уравнений (*), решаем её, получаем, что множество решений конечно. Выписываем мн-во  X^c&times;Y^c, и получаем матричную игру, и тут уже искать просто.

Еcли с.т. у K есть, то она обязательно войдёт в число точек матричной игры. То есть решаем матричную игру и проверяем, будет ли каждая из седловых точек для исходной игры.

Доказательство.

K(x,y^0) &le; K(x^0, y^0) &le; K(x^0, y), &forall; x &isin; X, y &isin; Y

max_{x_i &isin; [a_i, b_i]} K(x^0_1_j, ..., x^0_i, ..., x&0_n, y^0_1, y^0_m) = K(x^0, y^0)

K'_{x_i}(x^0, y^0) = 0 либ x_i^n=a_i, либ x^0_i=b_i

Таким образом мы доказали первую часть.

Втрая часть: если мы берём первое соотношение, и оно верно при &forall; x &isin; X, y &isin; Y, то оно верно и при &forall; x &isin; X^c, y &isin; Y^c

Таким образом мы получили алгоритм.

Пример.

K(x,y)=8(4xy^2-2x^2-y), x,y&isin;[0,1]

Сначала проверим, выполнены ли условия теоремы фон Неймана. По x она вогнута и по y она выпукла. Отсюда по теореме фон Неймана существует седловая точка.

Теперь будем строить систему уравнений (*):

K'_x=8(4y^2-4x), K'_y=8(8xy-1)

(y^2-x)(x-0)(x-1) = 0
 (8xy-1)(y-0)(y-1) = 0
решаем эту систему: (0,0), (0,1), (1,0), (1,1), (1, 1/8), (1/4, 1/2) --- построили множество C

X^c = {0, 1/4, 1}, Y^c = {0, 1/8, 1/2, 1}

Теперь строим матричную игру:
 x^c \ y^c  0   1/8  1/2   1
  0         0    -1   -4  -8
 1/4       -1 -15/8   -3   1
  1       -16 -33/2  -12   8

седловая точка --- (1/4, 1/2). Дальше надо, вообще говоря, проверить все полученные седловые точки.

Но поскольку мы установили, что по теореме фон Неймана есть одна седловая точка, а получили мы их максимум одну, то их ровно одна.

== Смешанные стратегии в антагонистических играх ==

Когда рассматривается игра с платёжной матрицей A = ||a_ij||, i=1..n, j=1..m. Каждый выбирает i/j соответственно, и один получает a_ij, другой -a_ij

Игра обычно разыгрывается много раз. При этом возникает понятие p=(p_1, ..., p_n), p_i &gt; 0, &sum;_{i=1}^n p_i=1 --- вектор вероятности выбора стратегии i --- смешанная стратегия первого игрока. Множество этих стратегий P_n = {p=(p_1, ..., p_n), p_i &gt; 0, &sum;_{i=1}^n p_i=1}. Аналогично для второго игрока: Q_m = {q=(q_1, ..., q_m), q_j &gt; 0, &sum;_{j=1}^m q_j=1}.

Пусть p&isin; P_n, q &isin; Q_n. Как считается результат? считается матожидание платежа. Платёж a_ij первый игрок получает при выборе стратегии i и выборе стратегии j вторым игроком. Но первый игрок выбирает с вероятностью p_i, а второй — q_j. Вероятность данного выбора --- p_i&times;q_j. Тогда выигрыш равен A(p,q) = &sum_{i=1}^n &sum;_{j=1}^m a_ij p_i q_j. Это показывает, какой выигрыш получат игроки, если выбрали стратегии p, q.

От игры с платёжной матрицей A мы перешли к игре с платёжной функцией A(p,q).

A(p,j) = &sum_{i=1}^n a_ij p_i, A(i, q) = &sum;_{j=1}^m a_ij q_j

A(p,q) = &sum;_{j=1}^m A(p,j) q_j = &sum_{i=1}^n A(i, q) p_i

Каждый игрок по прежнему действует по принципу максимальной выгоды, тогда получим:

max_{p&isin;P_n} min_{q&isin;Q_m} A(p,q) = min_{q&isin;Q_m} A(p^0,q)

min_{q&isin;Q_m} max_{p&isin;P_n} A(p,q) = max_{p&isin;P_n} A(p,q^0)

В такой игре всегда существует седловая точка.

Л1. P_n, Q_m — выпуклые компакты.

1) p^1, p^2 &isin; P_n, &alpha; &isin; (0,1)
Рассмотрим &alpha;p^1 + (1-&alpha;)p^2
Тогда
 &alpha;p^1 + (1-&alpha;)p^2 &ge; 0
 &sum;_{i=1}^n(&alpha;p_i^1 + (1-&alpha;)p_i^2) = &alpha; &sum;_{i=1}^n p_i^1 + (1-&alpha;) &sum;_{i=1}^n p_i^2 = 1

2) p^k &larr;_{k &larr; &infin;} p^0, p^k &isin; P_n
 p_i^k &ge; 0 &rArr; p_i^0 &ge; 0
 &sum;_i=1^n p_i^k = 1
 lim_{k &rasrr; &infin;} &sum;_i=1^n p_i^k = 1
 &sum;_i=1^n lim_{k &rasrr; &infin;} p_i^k = &sum;_i=1^n p_i^0

Из определений P и Q. Мы делаем вывод, что A(p,q) непрерывна, и является линейной. Значит, она и выпукла, и вогнута по любой переменной. То есть, она вогнута по p и выпукла по q. По теореме фон Неймана существует седловая точка. Т.о., мы доказали теорему "в матричной игре всегда существует смешанная стратегия". Ну и поскольку мы отметили, что функция A(p,q) — непрерывна, а множества смешанных стратегий являются компактными, то это позволяло писать max/min.

Ну и вообще, мы делаем какой вывод: max min и min max равны. Это следствие из теоремы.

Как решать матричные игры в смешанных стратегиях: нужно найти любую седловую точку.

Отметим ещё раз, что если p*, q* --- оптимальные стратегии, то (p*, q*) — седловая точка.

Отметим свойства оптимальных смешанных стратегий. Тройкой (p*, q*, V) будем называть решение игры. V = max_p nim_q A(p,q) = min_q max_p A(p,q) = A(p*, q*) Когда нам будет дана со смешанной стратегией, то целью будет являться решение игры. Таких троек может быть много. Для поиска таких троек небходимо знать свойства оптимальных смешанных стратегий.

1. Если (p*, q*, V) — решение игры с матрицей A, то (p*, q*, V+c) — решение игры с матрицей Ã = ||a_ij + c||, c=const. Мы прибавили константу ко всем элементам матрицы. Что меняется? Множество решений не меняется, меняется только значение игры. Докажем:

A(p,q) + c = A(p,q) + c(&sum;_i=1^n p_i)(&sum;_i=j^m q_j) = &sum_{i=1}^n &sum;_{j=1}^m (a_ij + c) p_i q_j = Ã(p,q)

Пусть выполнено условие, и A(p*, q*) — седловая точка. Тогда

A(p,q*) &le; A(p*, q*) &le; A(p*, q)
 Прибавим константу c:
 A(p,q*) + c &le; A(p*, q*) + c &le; A(p*, q) + c
 Ã(p,q*) &le; A(p*, q*) + с &le; Ã(p*, q)

Теперь из утверждения, доказанного на прошлой лекции, следует, что (p*, q*) обращает седловую точку и (p*, q*, V+с) — решение игры

2. Тройка (p*, q*, V) является решением игры тогда и только тогда, когда A(i, q*) &le; V &le; A(p*,j), &forall; i=1..n, j=1..m

Доказательство. 1)Пусть (p*, q*, V) — решение. Тогда:

A(p,q*) &le; A(p*, q*) = V &le; A(p*, q), &forall; p &isin; P_n, q &isin; Q_m

Т.к. оно верно для всех p, q, то можно взять p=(0...0, 1 (i-е место), ..., 0) &isin; P_n, q=(0...0, 1 (j-е место), ..., 0) &isin; Q_m, и сразу получаем эти соотношения.

2)Пусть выполнены соотношения:
A(p,q*) &le; A(p*, q*) = V &le; A(p*, q), &forall; p &isin; P_n, q &isin; Q_m

Возьмём произвольным p, q. Возьмём соотношение A(i, q*) &le; V, i=1..n

&sum;_{i=1}^n p_i A(i, q*) &le; &sum;_{i=1}^n V p_i
 A(p, q*) &le; V

В итоге получится, что A(p,q*) &le; V &le; A(p*, q). Это означает, что (p*, q*, V) — решение.

Пример.

1 0
 0 1

Решение: ((1/2, 1/2), (1/2, 1/2), 1/2)

Можно доказать, что _I_ &le; V &le; ~I~ (доказать дома)

3. Справедливы следующие равенства:
 1) &forall; p &isin; P_n min_q A(p,q)=min_j A(p,j)
 2) &forall; q &isin; Q_m max_p A(p,q)=max_i A(i,q)

Докажем первую часть, вторая доказывается аналогично. Покажем сначала, что лч&le; пч, потом что лч&ge;пч.

a) min_{j=1..m} A(p, j) = min_j A(p, q^j), q^j = (0..., 1(j-е место), ..., 0)
 min_j A(p, q^j) &ge; min_q A(p, q)

b) min_q A(p,q) = min_q &sum;_{j=1}^n &le; min_q &sum_j q_j (min_j &sum; a_ij p_j) = min_j &sum; a_ij p_j (min_q &sum_j q_j (=1)) = min_j &sum; a_ij p_j = A(p, j)
 min_j A(p, q^j) &le; min_q A(p, q)

Отсюда равенство.

Следствия.

Сл1. V = max_p min_q A(p,q) = max_p min_j A(p,j)
     V = min_q max_p A(p,q) = min_q max_i A(i,q)

Cл2. (доказать самостоятельно) (p*, q*, V) — решение тогда и только тогда, когда min_ A(p*, j) = max_i A(i, q*) = V

В этом свойстве тоже заложен некий алгоритм поиска решения.

Св4. (p*, q*, V) — решение
 1) p*_{i_0} &gt; 0 &larr; A(i_0, q*) = V
 1) q*_{j_0} &gt; 0 &larr; A(p*, j_0) = V

Докажем первую часть.

пусть p*_{i_0} &gt; 0, A(i_0, q*) &le; V

V=A(p*, q*) = &sum;_i A(i,q*) (&le; V) p_i* + A(i_0, q*) {<V} p*_i (>0) &lt; V(1-p*_{i_0}) + Vp*_i_0 = V — противречие

Св5. P*, Q* — компакты.

Доказательство. Выпуклость: p_1, p62 &isin; P*, &alpha; &isin; (0,1)
~p = &alpha;p^1 + (1-&alpha;)p^2 &isin; P_n
Осталось доказать, что это оптимальная стратегия. Все линейности можно записать следующим образом: A(~p, j) = &alpha;A(p^1, j) + (1-&alpha;)A(p^2,j) &ge; &alpha;V + (1-&alpha;)V=V

A(~p, j) &ge; V, &forall; j=1..m

P* — огр, p* &larr;_{k &larr; &infin;} p^0
 p_k &isin; P*, p^0 &isin; P_n

A(p^k, ) &ge; V, &orall; j=1..m

lim_{k &larr; &infin;} A(p^k+) &ge; V

A(lim_{k &larr; &infin;} p*, ) &ge; V

A(p^0, j) &ge; V, J=1..m

p^0 &isin; P*

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

Раздел: доминирование матричных строк и столбцов

Предположим, что одна из строк оказалась меньше других, то первому игроку выгоднее её вычеркнуть и не рассматривать. Аналогично для второго игрока.

Теорема. Если некоторая строка матрицы A = ||A_ij|| доминируется (строго доминируется) выпуклой линейной комбинацией остальных строк, то эта строка входит с нулевой вероятностью в некоторую (любую) оптимальную смешанную стратегию первого игрока (и её можно вычеркнуть).

Теорема. Если некоторый столбец матрицы A = ||A_ij|| доминирует (строго доминирует) выпуклую линейную комбинацию остальных столбцов, то этот столбец входит с нулевой вероятностью в некоторую (любую) оптимальную смешанную стратегию второго игрока (и его можно вычеркнуть).

Нестрогое доминирование. Пусть некоторая строка матрицы нестрого доминируется. Что это значит:

Возьмём &alpha;+i &ge; 0, &sum_{i&ne;i_0} &alpha;_i = 1, &sum; &alpha;_i a_i — выпуклая линейная комбинация

Доминируется: a_ij &le; &sum;_{i&ne;i_0} &alpha;a_ij, j=1..m --- нестрогое доминирование
 a_ij &lt; &sum;_{i&ne;i_0} &alpha;a_ij, j=1..m --- строгое доминирование

p* &isin; P*

~p_i = 0, i=i_0
        p*_i + &alpha;_i p*_{i_0}, i &ne; i_0i &ne; i_0

~p_i &ge; 0

&sum;_i ~p_i = &sum;_{} (p*_i+&alpha;_i p*_{i_0}) = &sum;_{i &ne; i_0}p*_i + p*_{i_0} &sum_{i &ne; i_0} &slphs;_i = &sum;_i p*_i = 1

~p &isin; P_n

Осталось показать, что это оптимальная смешанная стратегия

A(~p, ) = &sum;_{i &ne; i_0} (p*_i + &alpha;_i p*_{i_0}) a_ij = &sum;_{i &ne; i_0} p*_i a_ij + p*_{i_0} &sum;_{i &ne; i_0} ....

A(~p, ) &ge; V

Случай строгого доминирования:

Надо доказать, что p*_{i_0} = 0. Пусть p*_{i_0} &ge; 0. Тогда V=A(i_0, q*) = &sum;_j a_{{i_0}j} q*_j &lt; &sum;_j (&sum;_{i&ne;i_0} &alpha;_i a_ij) q*_i = &sum;_j &alpha;_i &sum;_j a_ij q*_i = ... V &lt; V — противоречие.

Пример
 3 2 4 0
 3 4 2 4
 4 2 4 0
 0 4 0 8
Первая строка меньше третьей, следовательно, она доминируется, но нестрого. Но если мы ищем хотя бы одно решение, то мы её можем вычеркнуть.
 3 4 2 4
 4 2 4 0
 0 4 0 8
Сравним 1 и 3 столбцы. 1 &ge; 3. Имеет место доминирование столбцов, и его можно вычеркнуть.
 4 2 4
 2 4 0
 4 0 8
Первый столбец доминирует линейную комбинацию 2 и 3 столбцов с коэффициентом 0.5. Опять первый столбец вычёркиваем.
 2 4
 4 0
 0 8
Здесь доминирование строк. доминируется 1 строчка линейной комбинацией 2 и 3 с коэффициентом 0.5
 4 0
 0 8
Не объясняя, как мы ищем решение, то для последней игры решение такое: p*' = (2/3, 1/3), q*' = (2/, 1/3), w=8/3.

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.org/wiki/%D0%A2%D0%B8%D0%B3%D1%80%D1%8B%2C_02_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_11_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29

Редактирование: Тигры, 02 лекция (от 11 сентября)

Материал из eSyr's wiki.

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 7: / Строка 7: @@
 K((1-t)x*+tx+y) &gt; (1-t)k(x*,y) + tK(x, y) &ge; (1-t)_w_(x*) + tK(x,y)
-ỹ = y((1-t)x* + tx) --- это верно при фиксированном ...
+ỹ = y((1-t)x* + tx) --- это верно при фикс. ...
-_w_(x*) &ge; _w_((1-t)x* + tx) &gt; (1-t)_w_(x*) + tk(x, ỹ) --- мы расписали это соотношение при y=ỹ
+_w_(x*) &ge; _w_((1-t)x* + tx) &gt; (1-t)_w_(x*) + tk(x, ỹ) --- мыр списли эт сотн. при y=ỹ
 t_w_(x*) &gy; tK(x,ỹ)
@@ Строка 17: / Строка 17: @@
 Это соотношение справедливо  &forall;t &isin; (0,1). Устремим t к 0. Что получится:
-_w_(x*) &ge; K(x,y(x*)) (здесь мы используем доказанную в начале непрерывность)
+_w_(x*) &ge; K(x,y(x*)) (здесь мы используем доказанную в начале непр.)
@@ Строка 62: / Строка 62: @@
 K_{yy}'' = 2x &ge; 0 — выпукла по y.
-Условие теоремы фон Неймана выполнено, и есть седловая точка (показать дома, что это (1,0))
+Условие теоремы фон Неймана выполнено, и есть седловая точка (показать дома, чт это (1,0))
 Теорема конструктивная и вообще говоря, ей можно пользоваться для нахождения седловой точки.
@@ Строка 85: / Строка 85: @@
 '''Теорема'''. Если (x_0, y^0) — седловая точка K(x,y) на X&times;Y, то (x_0, y^0) &isin; C, (x_0, y^0) — c.т. K на X^c&times;Y^c
-Эта теорема даёт нам алгоритм поиска седловой точки. Пусть есть такая функция и выполнены все условия мы выписываем систему уравнений (*), решаем её, получаем, что множество решений конечно. Выписываем множество  X^c&times;Y^c, и получаем матричную игру, и тут уже искать просто.
+Эта теорема даёт нам алгоритм поиска седловой точки. Пусть есть такая функция и выполнены все условия мы выписываем систему уравнений (*), решаем её, получаем, что множество решений конечно. Выписываем мн-во  X^c&times;Y^c, и получаем матричную игру, и тут уже искать просто.
 Еcли с.т. у K есть, то она обязательно войдёт в число точек матричной игры. То есть решаем матричную игру и проверяем, будет ли каждая из седловых точек для исходной игры.
-'''Доказательство'''.
+Доказательство.
 K(x,y^0) &le; K(x^0, y^0) &le; K(x^0, y), &forall; x &isin; X, y &isin; Y
@@ Строка 99: / Строка 99: @@
 Таким образом мы доказали первую часть.
-Вторая часть: если мы берём первое соотношение, и оно верно при &forall; x &isin; X, y &isin; Y, то оно верно и при &forall; x &isin; X^c, y &isin; Y^c
+Втрая часть: если мы берём первое соотношение, и оно верно при &forall; x &isin; X, y &isin; Y, то оно верно и при &forall; x &isin; X^c, y &isin; Y^c
 Таким образом мы получили алгоритм.