В.А. Артамонов - Линейная алгебра для экономистов (1129135), страница 3
Текст из файла (страница 3)
Следовательно, K ∩N 0непусто.¤Предложение 1.13. Пусть заданы компактные подмножества N ⊆ An , M ⊆ Am и F (x, y) – непрерывная функция,где x ∈ N, y ∈ M . Тогдаmax min F (x, y) 6 min max F (x, y)x∈N y∈My∈M x∈NДоказательство. ИмеемF (x, y) 6min F (x, y) 6y∈Mmax F (x, y) =⇒x∈Nmin max F (x, y) =⇒y∈M x∈N22В. А. Артамоновmax min F (x, y) 6x∈N y∈Mmin max F (x, y).y∈M x∈N¤Теорема 1.14 (фон Нейман). ПустьXXXF (x, y) =aij xi , yj +li xi +rj yj + c,i,jijгдеx = (x1 , . . . , xn ) ∈ An , y = (y1 , .
. . , ym ) ∈ Am .Предположим, что заданы компактные выпуклые подмножества N ⊆ An , M ⊆ Am . Тогда1) maxx∈N miny∈M F (x, y) = miny∈M maxx∈N F (x, y);2) существуют такие точки x∗ ∈ N, y ∗ ∈ M , что для всехx ∈ N, y ∈ M выполнены неравенства F (x, y ∗ ) 6 F (x∗ , y ∗ ) 6F (x∗ , y).Доказательство. Положим e = maxx∈N miny∈M F (x, y).Без ограничения общности можно считать, что e = 0. По предложению 1.13 имеемmax min F (x, y) = 0 6 min max F (x, y).x∈N y∈My∈M x∈N0Обозначим через N множество всех линейных функций h(x) =−F (x, y), y ∈ M .
Это множество компактно. Следовательно, попредложению 1.11 найдется такая точка y ∗ ∈ M , что F (x, y ∗ ) 60 для всех x ∈ N . В частности,max F (x, y ∗ ) 6 0.x∈N(11)Отсюдаminy∈M maxx∈N F (x, y) 6 0 =maxx∈N miny∈M F (x, y) 6 miny∈M maxx∈N F (x, y),(12)и утверждение 1) доказано.Аналогичные рассуждения показывают, что существуетточка x∗ ∈ N , для которой F (x∗ , y) 6 0 при всех y ∈ M. По(11) и (12) получаем maxx∈N F (x, y ∗ ) = 0. Аналогично, заменяяF на −F получаем miny∈M F (x∗ , y) = 0. ПоэтомуF (x∗ , y ∗ ) ≤ maxx∈N F (x, y ∗ ) =Линейные неравенства23miny∈M F (x∗ , y) 6 F (x∗ , y);F (x∗ , y ∗ ) ≥ miny∈M F (x∗ , y) =maxx∈N F (x, y ∗ ) > F (x, y ∗ ).¤Определение. Точка (x∗ , y ∗ ) из теоремы фон Неймана называется седловой.2.1.
Конечные антагонистические игры. Рассмотримследующую игровую ситуацию. Имеются два игрока со стратегиями 1, . . . , n и 1, . . . , m, соответственно. Задана числоваяматрица A = (aij ) размера n × m. Если первый игрок выбираетi-ую стратегию, а второй j-ую, то результатом игры являетсячисло aij . Если это число положительно, то выигрывает первыйигрок и результат выигрыша равен aij . Если это число отрицательно, то выигрывает второй с результатом −aij .Предположим, что первый игрок выбрал стратегию i.
Тогда второй игрок, чтобы нанести первому наибольший урон выбирает стратегию j так, чтобы aij = mink aik . Вообще говоря,второй игрок не знает стратегии первого игрока. Поэтому первый игрок для безопасности и ограничения проигрыша снизудолжен выбрать i1 так чтобы ai1 ,j1 = maxi minj aij .
Соответственно, второй для ограничения нанесения первому наибольшего гарантированного урона должен выбрать j2 так, чтобыai2 ,j2 = minj maxi aij . Как показано в предложении 1.13 выполнено неравенство ai1 ,j1 6 ai2 ,j2 .Предположим, что игроки играют T раз, выбирая при этомразные стратегии. Смешанной стратегией первого игрока называется векторx = t (x1 , . . . , xm ) > 0,x1 + · · · + xm = 1.Величина xi означает вероятность того, что первый игрок выбрал i-ую стратегию.
Аналогичным образом, определяется смешанная стратегия y второго игрока. Таким образом, если игроки придерживались смешанных стратегий x, y,то результатомигры будет число F (x, y) = T t xAy. Следовательно, если первый игрок будет придерживаться стратегии x∗ из теоремы фон24В. А. АртамоновНеймана, то он будет иметь гарантированный выигрыш. В случае отклонения от x∗ , при выборе вторым игроком стратегииy ∗ первый игрок выиграет меньше. Те же рассуждения применимы и ко второму игроку.
Поэтому им рекомендуется придерживаться стратегий x∗ , y ∗ .2.2. Конечные бескоалиционные неантагонистические игры. Предположим, что в игре участвуют d игроков,у каждого из них имеется свое конечное множество стратегийXi и своя функция выигрыша Hi : X1 × · · · × Xd → R. Если i-ыйигрок выбрал стратегию xi ∈ Xi , 1 6 i 6 d, то в результате игры его выигрыш составит Hi (x1 , . . .
, xd ). Эта игра называетсябескоалиционной неантагонистической игрой. Если каждое Xiконечно, то игра конечна. В случае двух игроков игра называется биматричной. Действительно, пусть X1 = {1, . . . , m}, X2 ={1, . . . , n}. Составим матрицы H1 , H2 ∈ Mat(m × n, R), где в H1(соответственно, в H2 ) на месте (i, j) стоит число H1 (i, j) (соответственно, H2 (i, j)), равное выигрышу 1-го (соответственно,2-го) игрока. Таким образом, эта игра задается двумя матрицами. При этом всегда без ограничения общности можно считать,что H1 , H2 > 0.Как и выше рассматриваются смешанные стратегии pi ={pij | j ∈ Xi }, где pij – вероятность того, что i-ый игрок выбралj-ую стратегию.
ТогдаXpij > 0,pij = 1.j∈XiВ этом случае средним результатом или математическим ожиданием выигрыша i-го игрока являетсяXHi (p1 , . . . , pd ) =Hi (i1 , . . . , id )p1,i1 · · · pd,id .i1 ∈X1 ,...,id ∈XdОпределение. Набор смешанных стратегий p∗1 , . . . , p∗d называется ситуацией равновесия по Нэшу, если для каждогоi = 1, . . . , d выполнено условиеHi (p∗1 , . . . , p∗i−1 , p∗i , p∗i+1 , . . . , p∗d ) >Hi (p∗1 , . . . , p∗i−1 , pi , p∗i+1 , .
. . , p∗d )(13)Линейные неравенства25для любой смешанной стратегии pi . Стратегия p∗i называетсяравновесной, если она входит в некоторый набор ситуации равновесия по Нэшу.Набор смешанных стратегий p∗1 , . . . , p∗d называется ситуацией равновесия по Парето, если не существует такого набора(p1 , . .
. , pd ), что для каждого i = 1, . . . , d выполнено условиеHi (p1 , . . . , pd ) > Hi (p∗1 , . . . , p∗d ),(14)причем для некоторого i0 неравенство (14) строгое.Теорема 1.15 (Nash). Любая конечная бескоалиционнаяигра имеет ситуацию равновесия на Нэшу.Доказательство. Множества P1 , . . . , Pd смешанных стратегий игроков являются компактами. Следовательно, иP1 × · · · × Pd(15)является компактом.
Зададим отображение Ψ, сопоставляющеекаждое точке (p1 , . . . , pd ) из (15) множество Ψ(p1 , . . . , pd ) всехтаких (p01 , . . . , p0d ) из (15), чтоHi (p1 , . . . , pi−1 , p0i , pi+1 , . . . , pd ) =max Hi (p1 , . . . , pi−1 , y, pi+1 , . . . , pd )y∈Piдля каждого i = 1, . . . , d. Так как функции Hi , 1 6 i 6d, полилинейны, то Ψ(p1 , . . . , pd ) является компактом в (15).(t)(t)Если последовательность (p1 , . . .
, pd ) из (15) имеет предел(t)(t)(p1 , . . . , pd ), и существует последовательность (q1 , . . . , qd ) ∈(t)(t)Ψ(p1 , . . . , pd ) c предельной точкой (q10 , . . . , qd0 ), то (q10 , . . . , qd0 ) ∈Ψ(p1 , . . . , pd ).Лемма 1.16 (Теорема Какутани). Пусть S ⊂ Rm – компактное выпуклое множество и Ψ – отображение, сопоставляющее точкам из S компактные выпуклые подмножествав S. Предлположим, что если имеется последовательностьxt ∈ S, t > 1, сходящаяся к x, и набор элементов yt ∈ Ψ(xt ),сходящийся к y, то y ∈ Ψ(x).
Тогда найдется такая точкаx∗ ∈ S, что x∗ ∈ Ψ(x∗ ).Доказательство. См. [PR, Теорема 1.11.5, с. 38-39]¤26В. А. АртамоновЗавершим доказательство теоремы. По лемме найдется такая точка (p∗1 , . . . , p∗d ) ∈ Ψ(p∗1 , . . . , p∗d ) из (15), т. е. выполнено(13).¤Приведем без доказательства два результата.Теорема 1.17 ([LB], с.
137). Смешанная стратегия(p∗1 , . . . , p∗d ) является ситуацией равновесия по Нэшу тогда итолько тогда, когда для любого i и любой чистой стратегииxi ∈ Xi выполняется неравенствоHi (p∗1 , . . . , p∗i−1 , xi , p∗i+1 , . . . , p∗d ) 6 Hi (p∗1 , . . . , p∗d ).Теорема 1.18. Если равновесная стратегия p∗i входит вситуацию (p∗1 , . . . , p∗d ) и p∗i (xj ) > 0, тоHi (p∗1 , .
. . , p∗i−1 , xi , p∗i+1 , . . . , p∗d ) = Hi (p∗1 , . . . , p∗d ).Далее мы будет рассматривать биматричные игры. Положим p1 = p, p2 = q. Тогда ситуация p∗ , q ∗ является равновеснойпо Нэшу, еслиH1 (p∗ , q ∗ ) > H1 (p, q ∗ ),H2 (p∗ , q ∗ ) > H2 (p∗ , q)(16)для любых смешанных стратегий p, q.Теорема 1.19. Для того, чтобы (p∗ , q ∗ ) была бы ситуацией равновесия в биматричной игре с матрицами A = H1 , B =H2 > 0 необходимо и достаточно, чтобы существовали такиечисла a, b, чтобыA t q ∗ 6 a t e,P ∗ B 6 b e,p∗ (A + B) t q ∗ = a + b,где e = (1, .
. . , 1) – строка длины n или m.Доказательство. Если пара (p∗ , q ∗ ) является ситуациейравновесия, то положим a = p∗ A t q ∗ , b = p∗ B t q ∗ . Если взятьвектор p, в котором на месте i стоит 1, а все остальные координаты равны 1, то в силу (16)Xaij qj∗ = pA t q ∗ 6 p∗ A t q ∗ = a.jt ∗Поэтому A q 6 a t e. Аналогично t B t p∗ 6 b t e. Кроме того,p∗ (A + B) t q ∗ = p∗ A t q ∗ + p∗ B t q ∗ = a + b.Линейные неравенства27Обратно, пусть p∗ , q ∗ , a, b удовлетворяют условиям теоремы.Тогда для любых векторов x, y > 0 с условием x t e = e t y = 1имеемxA t q ∗ 6 ax e = a, p∗ By 6 be t y = b,xA t q ∗ + p∗ B t y 6 a + b = p∗ A t q ∗ + p∗ B t q ∗ .(17)∗t ∗В частности, беря x = p, y = q получаем, что p A q 6a, p∗ B t q ∗ 6 b, и a + b = p∗ A t q ∗ + p∗ B t q ∗ по (17). Поэтому p∗ A t q ∗ = a, p∗ B t q ∗ = b.
Отсюда xA t q ∗ 6 p∗ A t q ∗ , иp∗ B y 6 p∗ B t q ∗ . В силу (16) получаем ситуацию равновесия. ¤Теорема 1.20. Для того, чтобы (p∗ , q ∗ ) была бы ситуацией равновесия в биматричной игре с матрицами A = H1 , B =H2 > 0 необходимо и достаточно, чтобы p∗ , q ∗ , a, b из предыдущей теоремы являлись бы решением задачиx(A + B) t y − a − b → max,A t y 6 a t e, xB 6 b e, x, y > 0, x t e = y t e = 1.(18)Доказательство. Если выполнены ограничения из условия теоремы, то x(A + B) t y − a − b 6 0. Поэтому и максимум неположителен. Пусть (p∗ , q ∗ ) – ситуация равновесия иa = p∗ A t q ∗ , b = p∗ A t q ∗ .
Тогда это решение задачи (18).Обратно, если задано решение p∗ , q ∗ , a, b задачи (18), то всилу существования точки равновесия по Нэшу получаем, чтоp∗ (A + B) t q ∗ − a − b = 0. Отсюда следует утверждение теоремы.¤Рассмотрим выпуклые множестваS = {(x, b) | t Bx − b t e 6 0, e t x = 1},T = {(y, a) | Ay − b t e 6 0, e t y = 1}.Определение 1.21. Точка выпуклого множества M называется крайней, если она не лежит внутри любого отрезка,концы которого принадлежат M .Теорема 1.22. Всякая ситуация равновесия в биматричной игре является выпуклой комбинацией таких точек(p∗ , q ∗ ), что (p∗ , b) – крайняя точка в S, а (q ∗ , a) – крайняяточка T .28В. А.
АртамоновДоказательство. См. [PR, теорема 7.4.3. c. 186-187]. ¤3. ПолиэдрыОпределение. Полиэдром P называется множество всехточек x ∈ An , удовлетворяющих заданной системе аффинных неравенств (3). Размерностью полиэдра P называется размерность наименьшей плоскости, содержащей P . Другими словами, размерность P совпадает с рангом системы векторов−−→{ AB | A, B ∈ P }.Если f1 , . . . , fr – все аффинные функции из (3), обращающиеся в нуль в точке A ∈ P . Обозначим через Π плоскость,задаваемую уравнениями f1 = · · · = fr = 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
