Нэшийн тэнцвэр

Та өөрийгөө зун хүн их цугладаг нуурын эргийн зурвас газар мөхөөлдөсний явуулын мухлаг ажиллуулдаг байжээ гэж төсөөл. Энэ зурвас газар эргийнхээ дагуу 1км урттай бөгөөд, хүмүүсийн нягт ерөнхийдөө жигд.

Эргийн дагуу мөхөөлдөс зарахыг зөвшөөрсөн 3 цэг байдаг бөгөөд та аль ч цэгийг нь сонгон ажиллах боломжтой. Эдгээр цэгүүд нь эргийн зүүн захаас эхлэн 250, 500, 750 метрт байрладаг.

Ийм үед та хүмүүсийн ая тухыг болон өөрийн ашгийг бодон 2-р цэгт мухлагаа байрлуулах нь зүйн хэрэг. Одоо нэг өдөр гэнэт танд өрсөлдөгч гарч ирлээ гэж бодъё. Бага ангиас хойш тантай байнга өрсөлддөг байсан Батцагаан дүүрэн мөхөөлдөстэй хөлдөөгч ачаад нэг өдөр нуурын захад буух нь тэр. Түүнийг хараад та очиж уулзан, хоёулаа худалдан авагчдаа яг хуваах үүднээс 1 ба 3-р цэгүүд дээр байрлая, тэгвэл хүмүүс ч гэсэн мөхөөлдөс авах гэж хол алхах хэрэггүй болно гэж гэнэн цагаанаар ятгах гэж оролдоно. Батцагаан дуртай дургүй мушилзаад, 3-р цэг дээр очин зогсоно.

Таны өдрийн орлого мэдээж тал дундуураа хуваагдах боловч Батцагаан бас л тантай адилхан бизнес хийх гэж ядаж яваа амьтан тул түүнийг буруутгах арга байхгүй. Энэ байдлаар эхний өдөр таны орлого

a=50\%

Батцагааны орлого

b=50\%

гэж дүгнэж болно. Дараагийн өдөр нь та эртхэн ирээд 1-р цэг дээрээ мухлагаа зоон ажиллуулж эхэлнэ. Хэдэн минутын дараа Батцагаантан морилох ба, таны бодсоноор 3-р цэг рүү чиглэсэн ч үгүй, шууд 2-р цэг дээр очиж маасайтал инээн мөхөөлдөсөө зарж эхлэх нь тэр. Та уураа барин барин хэсэг ажиллахад санаа дагаад ч юм уу орлого тань илт багасч ирэв. Таны санаанд дараах зураг төсөөлөгдөнө:

Эндээс таны орлого

a=37.5\%

Батцагааны орлого

b=62.5\%

болох нь ойлгомжтой. Одоо Батцагааныг яаж ч хөшөөд хөдөлгөхөөсөө өнгөрсөн гэдгийг та мэдэх тул, боломжит ганц нүүдлийг хийх л үлдэнэ. Та мухлагаа түрж очин Батцагааны мухлагтай зэрэгцүүлэн байрлуулаад, юу ч болоогүй юм шиг маасайтал инээн мөхөөлдөсөө зарж эхэлнэ. Та хоёрын орлого эргээд 50% / 50% гэж хуваагдана. Ийм нөхцөлд Батцагаан мухлагаа хааш нь ч зөөсөн гэсэн орлогоо ихэсгэж чадахгүй. Таны хувьд ч мөн адил. Нэшийн тэнцвэр гэгчийн үндсэн санаа нь бол энэ л юм.

Худалдан авагчдын хувьд энэ хоёр тарж байрлахгүй яагаад нэг дор зоочихов оо гэж гайхах боловч аргагүйн эрхэнд өмнө нь ганц мухлагтай байхад ямар зайд алхаж мөхөөлдөс авдаг байсан яг тэр зайнд алхсаар л байх болно. Сумын төвийн дэлгүүрүүд яагаад нэг газар шавааралдсан байдаг нь үүгээр тайлбарлагдана. Түүнчлэн, 1, 2, 3 гэсэн сонголтуудыг орон зайн байрлал биш, өөр зүйл гэж үзсэнээр улс төрийн намууд сонгогчдыг татахын тулд яагаад бие биентэйгээ адилхан юм яриад байдаг, өрсөлдөгч компаниудын бүтээгдэхүүний үнэ, чанар, хийц яагаад төстэй болж ирдгийг иймэрхүү загвараар тайлбарлах боломж харагдана.

Дээрх жишээг хоёр тоглогч хоорондоо тодорхой дүрмээр тоглож байгаа тоглоом гэж үзэж болохыг ажиглаарай. Тэгвэл Нэшийн тэнцвэрийн тухай ойлголт нь дээрх жишээнээс хамаагүй илүү өргөн цар хүрээтэй тоглоомуудыг хамардаг. Үүнд

  • Тоглоом нь зөвхөн 2 тоглогчтой биш, хэдэн ч тоглогчтой байж болно.
  • Тоглогчид хоорондоо тэгш эрхтэй байх албагүй (тэгшхэмт биш).
  • Нэг тоглогчийн алдсан оноо нөгөө тоглогчид заавал хожоо болж ирдэг байх албагүй (тэг нийлбэрт биш).
  • Урьдчилсан тогтсон магадлалтайгаар олон сонголтоос санамсаргүйгээр сонгодог стратегийг зөвшөөрнө (холимог стратеги).

Нэшийн онолын гарааны цэг нь фон Нейманы тэг нийлбэрт тоглоомын онол юм. Иймд бид эхлээд фон Нейманы онолын зарим ухагдахууныг авч үзнэ. Юуны өмнө математикийн ганц хоёр тэмдэглэгээ оруулъя. Дээрх жишээнд 1-р тоглогчийн (таны) орлогыг

A=\begin{pmatrix}50&37.5&50\\62.5&50&62.5\\50&37.5&50\end{pmatrix}

гэсэн матрицаар илэрхийлж болно: 1-р тоглогч i-р байрлалыг, 2-р тоглогч k-р байрлалыг сонгосон үед 1-р тоглогчийн орлого ямар байх вэ гэдгийг A матрицын i-р мөр, k-р багананд байх тоо заана. Жишээлбэл i = 1 ба k = 2 үед 1-р тоглогчийн орлого

a_{1,2}=37.5.

Тэгвэл 2-р тоглогчийн (Батцагааны) орлого

B=\begin{pmatrix}50&62.5&50\\37.5&50&37.5\\50&62.5&50\end{pmatrix}

гэсэн матрицаар илэрхийлэгдэх нь тодорхой. Хэрэв A матрицын  i-р мөр k-р баганын элементийг a_{ik}, түүнчлэн B матрицын  i-р мөр k-р баганын элементийг b_{ik} гэвэл

a_{ik}+b_{ik}=100

байгаа. Өөрөөр хэлбэл, нэг тоглогч хичнээн хэмжээгээр алдана, нөгөө тоглогч төчнөөн хэмжээгээр хожно. Ийм тоглоомыг тэг нийлбэрт тоглоом гэдэг. Яагаад тэг нийлбэрт гэж байгаа юм бэ гэвэл, дээрх бидний жишээнд орлогыг тооцохдоо орлогын жинхэнэ хэмжээг биш, харин 50%-аас зөрөх зөрүүгээр нь тооцож болох байсан. Тэгвэл A, B матрицууд

A=\begin{pmatrix}0&-12.5&0\\12.5&0&12.5\\0&-12.5&0\end{pmatrix},\qquad B=\begin{pmatrix}0&12.5&0\\-12.5&0&-12.5\\0&12.5&0\end{pmatrix}

болж хувирах ба эдгээрийн элементүүд нь

a_{ik}+b_{ik}=0

нөхцлийг хангана. Мэдээж орлогыг жинхэнэ хэмжээгээр нь тооцох, 50%-аас зөрөх зөрүүгээр нь тооцох хоёр хоорондоо яг адилхан тоглоомуудыг тодорхойлно.

Цаашилбал, A, B матрицын элементүүд

b_{ik}=a_{ki}

нөхцлийг хангана. Өөрөөр хэлбэл,

B=A^\top.

Энэ нь хоёр тоглогч хоорондоо тэгш эрхтэй гэсэн үг бөгөөд, ийм тоглоомуудыг тэгшхэмтэй тоглоомууд гэж ярьдаг.

Фон Нейман

Хоёр тоглогчтой, тэг нийлбэрт тоглоомын онолыг, ингэснээрээ тоглоомын онол гэгч салбарыг ерөнхийд нь, 1928 онд бичсэн өгүүллээрээ суут математикч Жон фон Нейман эхлүүлсэн бөгөөд энэ онолоо эдийн засагч Оскар Моргенштернтэй хамтаар өргөжүүлэн 1944 онд ном болгож хэвлүүлжээ. Тоглогчдын хамгийн оновчтой стратеги ямар байх вэ гэдгийг фон Нейман дараах маягаар задлан шинжилсэн байгаа. Тоглоом маань тэг нийлбэртэй (B = –A) тул, зөвхөн A матрицаар бүх зүйл өгөгдөнө. Нэгдүгээр тоглогч, нөгөө тоглогчийнхоо ямар стратегиар тоглохыг мэдэхгүйгээр, өөрөөр хэлбэл A матрицын аль баганыг нөгөө тоглогч сонгохыг мэдэхгүйгээр, тэр баганан дахь хамгийн их элементийг сонгох зорилготой. Жишээлбэл,

A=\begin{pmatrix}0&-12.5&0\\12.5&0&12.5\\0&-12.5&0\end{pmatrix}

бол, 1-р тоглогч i = 2 гэсэн мөрийг сонговол аль ч баганын хамгийн их элементийг авна. Харин 2-р тоглогчийн хувьд, A матрицын аль мөрийг нөгөө тоглогч сонгохыг мэдэхгүйгээр, тэр мөрөн дэх хамгийн бага элементийг сонгох зорилготой. Дээрх жишээнд, 2-р тоглогч k = 2 гэсэн баганыг сонговол аль ч мөрийн хамгийн бага элементийг авна (энэ нь 1-р тоглогчид хамгийн бага хожоо авчрах тул 2-р тоглогчид хамгийн их хожоо авчирна гэсэн үг). Тэгэхээр эцэстээ, хоёр тоглогчийн маань оновчтой стратеги (i,k) = (2,2) болох ба, аль стратеги оновчтой вэ гэсэн бодлого шийдэгдэнэ. Одоо эргээд ерөнхий тохиолдол руугаа оръё. Нэгдүгээр тоглогчийн зүгээс харахад, тэр i-р мөрийг сонголоо гэж бодоход, нөгөө тоглогч нь тухайн мөрийн хамгийн бага элементийг сонгочихсон байхыг үгүйсгэж чадахгүй. Өөрөөр хэлбэл,

\displaystyle a_{ik^*}=\min_k a_{ik}

байх k^* гэсэн баганыг сонгочихсон байж мэднэ. Иймд дээрх минимумыг хамгийн их болгодог, ө.х.

\displaystyle \alpha=\max_i\min_k a_{ik}

максимумыг хэрэгжүүлдэг i гэсэн индексийг 1-р тоглогч сонгож авбал, 2-р тоглогч аль ч баганыг сонголоо гэсэн, 1-р тоглогчийн оноо хамгийн багадаа \alpha (буюу 2-р тоглогчийн оноо хамгийн ихдээ -\alpha) байх болно. Энэ \alpha утга нь 1-р тоглогчийн найдвартай авч чадах хамгийн их оноо юм. Үүнтэй төстэйгөөр,

\displaystyle \beta=\min_k\max_i a_{ik}

минимумыг  хэрэгжүүлдэг k гэсэн индексийг 2-р тоглогч сонгож авбал, 1-р тоглогч аль ч мөрийг сонголоо гэсэн, 2-р тоглогчийн оноо хамгийн багадаа -\beta (буюу 1-р тоглогчийн оноо хамгийн ихдээ \beta) байх болно. Энэ -\beta утга нь 2-р тоглогчийн найдвартай авч чадах хамгийн их оноо юм. Тэгэхээр хэрвээ \alpha=\beta буюу

\displaystyle \max_i\min_k a_{ik}=\min_k\max_i a_{ik}

байдаг бол, зүүн гар талынх нь максимумд хүргэдэг нэг i индексийг 1-р тоглогч, баруун гар талынх нь минимумд хүргэдэг нэг k индексийг 2-р тоглогч сонгон авах ба, тус тусынх нь оноо нэг утгатай тодорхойлогдоно. Ийм (i,k) гэсэн хосыг фон Нейман минимакс шийд (эсвэл минимакс стратеги) гэж нэрлэсэн. Мөхөөлдөс зардаг жишээний хувьд (2,2) нь минимакс стратеги юм.

Минимакс шийд гэсэн ойлголтыг тодорхойлонгуут, фон Нейманд тулгарсан хүндрэл нь, зарим тоглоомонд минимакс шийд байдаггүйд оршино. Жишээлбэл, бидний сайн мэдэх «хурууцах» тоглоомын матрицууд

A=\begin{pmatrix}0&1&0&0&-1\\-1&0&1&0&0\\0&-1&0&1&0\\0&0&-1&0&1\\1&0&0&-1&0\\\end{pmatrix},\qquad B=\begin{pmatrix}0&-1&0&0&1\\1&0&-1&0&0\\0&1&0&-1&0\\0&0&1&0&-1\\-1&0&0&1&0\\\end{pmatrix}

гэж өгөгдөнө. Үүнд эрхий хуруу 1, долоовор хуруу 2, гэх мэтчилэн чигчий хуруу 5 гэсэн сонголтонд харгалзах юм. Нэг хүн хожиход нөгөө нь хожигдох тул хурууцах нь тэг нийлбэрт тоглоом бөгөөд тоглоомын дүрэм хоёр тоглогчийн хувьд яг адилхан тул энэ нь тэгшхэмтэй тоглоом болно:

A+B=0,\qquad A^\top=B.

Түүнчлэн «алх, хайч, даавуу» тоглоом нь

A=\begin{pmatrix}0&1&-1\\-1&0&1\\1&-1&0\end{pmatrix},\qquad B=\begin{pmatrix}0&-1&1\\1&0&-1\\-1&1&0\end{pmatrix}

хэлбэртэй. Эдгээр тоглоомуудад A матрицын аль ч мөр –1 гэсэн элемент агуулах тул

\displaystyle \max_i\min_k a_{ik}=-1

ба уг матрицын аль ч багана +1 гэсэн элемент агуулах тул

\displaystyle \min_k\max_i a_{ik}=1.

Тэгэхээр

\displaystyle \max_i\min_k a_{ik}<\min_k\max_i a_{ik}

болж, минимакс шийд байхгүй нь харагдана. Энэ нь мэдээж аль ч тоглогч ямар ч хурууг сонгосон гэсэн нөгөө тоглогч нь түүнийг хожих хурууг сонгосон байж болно гэдгийн илэрхийлэл юм.

Энэ хүндрэлээс гарахын тулд, санамсаргүй буюу холимог стратегийн тухай ойлголтыг фон Нейман авч үзсэн. Үүнд, тоглогч бүр сонголтоо хийхдээ санамсаргүй байдлаар, сонголт бүрийг тодорхой магадлалтайгаар хийх боломжтой. Жишээлбэл, хурууцаж тоглоход аль ч хурууг ижил 20%-ийн магадлалтай гаргах стратеги нь холимог стратеги болно. Холимог стратегитай харьцуулахад, сонгож авсан нэг л хуруугаа байнга гаргадаг стратегийг цэвэр стратеги гэж нэрлэдэг. Холимог стратегийг оруулж ирснээр цэвэр стратегиас татгалзаж буй хэрэг биш, харин сонгож болох стратегийн тоог нэмж байгааг анхаараарай. Жишээ нь долоовор хуруугаа байнга гаргадаг цэвэр стратеги нь долоовор хуруун дээр 100%-ийн магадлалтай, бусад хуруун дээр 0%-ийн магадлалтай холимог стратеги болно. Тэгэхээр холимог стратегийг зөвшөөрсөн ч гэсэн, анхнаасаа цэвэр стратегиар шийдэгдэх байсан бодлого тэр цэвэр стратегиараа шийдэгдсэн хэвээрээ л байна (гэхдээ холимог стратегитай нэмэлт шийдүүд гарч ирж болзошгүй).

Одоо холимог стратегитай тоглогчийн зорилго юу байх вэ гэсэн асуулт гарч ирнэ. Нэгдүгээр тоглогчийн (холимог) стратегийг x_1+x_2+\ldots+x_n=1 байх x_1\geq0,\ldots,x_n\geq0 гэсэн тоонуудаар, хоёрдугаар тоглогчийн (холимог) стратегийг y_1+y_2+\ldots+y_m=1 байх y_1\geq0,\ldots,y_m\geq0 гэсэн тоонуудаар илэрхийлж болно. Үүнд n нь 1-р тоглогчийн цэвэр стратегийн тоо, m нь 2-р тоглогчийн цэвэр стратегийн тоо бөгөөд, тоглоомны онооны матриц A=[a_{ik}] нь m хэмжээтэй байна гэсэн үг.  Жишээлбэл, манай мөхөөлдөс зардаг жишээний хувьд n = m = 3 ба,  аль ч тоглогчийнх нь бүх холимог стратегийн олонлог

\Delta_3=\{(x_1,x_2,x_3):x_1+x_2+x_3=1,x_i\geq0\}\subset\mathbb{R}^3

нь 3 хэмжээстэй \mathbb{R}^3 огторгуйд зөв гурвалжин үүсгэнэ. Ингээд тоглолт маш олон удаа давтагдсан гэж үзвэл,

  • Бүх тоглолтын x_i хувьд нь 1-р тоглогч i-р мөрийг сонгоно.
  • Эдгээр тоглолт дотроос y_k хувьд нь 2-р тоглогч k-р баганыг сонгоно.

Тэгэхээр 1-р тоглогчийн (2-р тоглогчийн) нэг тоглолтонд дунджаар хожих (алдах) оноо

x_1(a_{11}y_1+a_{12}y_2+a_{13}y_3)+x_2(a_{21}y_1+a_{22}y_2+a_{23}y_3)+x_3(a_{31}y_1+a_{32}y_2+a_{33}y_3)

байна. Холимог стратегийн x=(x_1,x_2,x_3) ба y=(y_1,y_2,y_3) векторуудыг багана векторууд гэж үзсэнээр дээрх томъёог

E(x,y)=x^\top\!Ay

гэж бичих боломжтой. Тэгвэл 1-р тоглогчийн зорилго нь E(x,y) хэмжигдэхүүнийг их байлгах, 2-р тоглогчийн зорилго нь үүнийг бага байлгах явдал юм. Мэдээж энэ томъёо ерөнхий тохиолдолд хүчинтэй. Цаашилбал, цэвэр стратегийн талаар дээр хэлэлцсэний адилаар, хэрвээ

\displaystyle \max_{x\in\Delta_n}\min_{y\in\in\Delta_m} E(x,y)=\min_{y\in\Delta_m}\max_{x\in\Delta_n} E(x,y)

байдаг бол, зүүн гар талынх нь максимумд хүргэдэг нэг x стратегийг 1-р тоглогч, баруун гар талынх нь минимумд хүргэдэг нэг y стратегийг 2-р тоглогч сонгон авах ба, тус тусынх нь (дундаж) оноо нэг утгатай тодорхойлогдоно. Ийм (x,y) гэсэн хосыг минимакс шийд (эсвэл минимакс стратеги) гэж нэрлэнэ.

Хурууцах тоглоомын хувьд бүх хурууг адил магадлалтайгаар гаргадаг (x_i=0.2, y_k=0.2) стратеги нь минимакс стратеги болохыг амархан харж болно. Үнэндээ, аль нэг тоглогч нь энэ тэнцвэрээс гажсан стратеги хэрэглэвэл нөгөө тоглогч нь үүнд нь тохирсон эсрэг стратеги хэрэглэх замаар хожлоо ихэсгэх боломжтой. Одоо үүнийг бодвол арай төвөгтэй жишээ авч үзье. Тоглоомонд 2 хүн оролцох ба, хоёул гарынхаа ар талыг, эсвэл алган талыг бие биендээ зэрэг харуулна. Хэрэв хоёр тоглогчийн сонголт эсрэг (ө.х. нэг нь алгаа, нөгөөх нь гарынхаа ар талыг харуулсан) бол 1-р тоглогч 2 төгрөг хожно. Хэрэв хоёул алгаа харуулбал 2-р тоглогч 1 төгрөг хожих ба, хоёул гарынхаа ар талыг харуулбал 2-р тоглогч 4 төгрөг хожно. Тоглоомын матрицуудыг нь бичвэл

A=\begin{pmatrix}-1&2\\2&-4\end{pmatrix},\qquad B=\begin{pmatrix}1&-2\\-2&4\end{pmatrix}.

Энэ тоглоом тэг нийлбэрт тоглоом боловч тэгшхэмтэй биш:

A+B=0,\qquad A^\top\neq B.

Юуны түрүүнд тоглогчид цэвэр стратеги хэрэглэвэл юу болохыг авч үзье.

  • 1-р тоглогч дандаа алгаа (x = (1,0)) харуулаад байвал, 2-р тоглогч нь бас алгаа байнга харуулах (y = (1,0)) замаар тоглолт болгоноос 1 оноо хожоод байна.
  • 1-р тоглогч дандаа гарынхаа ар талыг (x = (0,1)) харуулаад байвал 2-р тоглогч мөн гарынхаа ар талыг (y = (0,1)) байнга харуулаад тоглолт болгоноос 4 оноо хожно.
  • Нөгөө талаас, 2-р тоглогч дандаа алгаа (y = (1,0)) эсвэл гарынхаа ар талыг (y = (0,1)) харуулах стратеги хэрэглэвэл, 1-р тоглогч нь яг эсрэг сонголтыг нь хийх замаар тоглолт болгоноос 2 оноо хожно.

Эндээс харахад хэрэв энэ тоглоомд минимакс шийд байвал тэр нь цэвэр стратеги биш, холимог стратеги байх ёстой. Нэгдүгээр тоглогчийн стратеги мэдэгдэж байгаа үед, y_1+y_2=1 гэдгийг ашиглан 1-р тоглогчийн нэг тоглолтын дундаж оноог зөвхөн y_1 хувьсагчаар илэрхийлэх боломжтой. Жишээлбэл, x=(1,0) үед

E(x,y)=-y_1+2y_2=2-3y_1,

x=(0,1) үед

E(x,y)=2y_1-4y_2=-4+6y_1,

x=(0.5,0.5) үед

E(x,y)=\frac12y_1-y_2=-1+\frac12y_1

байна. Ингээд 1-р тоглогчийн хэд хэдэн стратегийн хувьд түүний дундаж оноо y_1 хувьсагчаас хэрхэн хамаарахыг зурж үзье.Ягаан (цэнхэр) шугам нь 1-р тоглогчийн дандаа алгаа (ар талаа) харуулах стратегид харгалзана. Тэгвэл 2-р тоглогч нь y = (0,1) эсвэл y = (1,0) стратегийг хэрэглэн тоглолт болгоноос 4 эсвэл 1 оноо харгалзан хожно. Харин 1-р тоглогч холимог стратегийг хэрэглэснээр алдагдлаа багасгаж болох нь харагдаж байна. Жишээ нь

  • x = (0.5,0.5) үед (улаан шугам) дундаж алдагдал E = –1,
  • x = (0.8,0.2) үед (цийлэн цэнхэр шугам) дундаж алдагдал E ≈ –0.5

байгаа. Түүнчлэн, шугамнууд зүүн тийшээ хэлбийсэн байж байгаад сүүлдээ баруун тийшээ хэлбийсэн болж байна. Тэгэхээр шугам яг хэвтээ болдог тийм параметр (буюу 1-р тоглогчийн стратеги) олдох ёстой. Энэ стратегийг олоход амархан: x=(a,b) гэж бичээд, a+b=1 ба y_1+y_2=1 гэдгийг ашиглавал

E(x,y)=(-a+2b)y_1+(2a-4b)y_2=(2-3a)y_1+(6a-4)y_2=6a-4+(6-9a)y_1

гэж гарах ба, эндээс 6-9a=0 буюу

\displaystyle a= \frac23

үед E(x,y)\equiv0 байх нь илэрнэ. Өөрөөр хэлбэл, 1-р тоглогч 2/3 магадлалтайгаар алгаа, 1/3 магадлалтайгаар гарынхаа ар талыг харуулах стратеги хэрэглэснээр өөрийгөө алдагдлаас сэргийлж чадах нь. Үүнийг арай өөрөөр илэрхийлбэл, E функц

\displaystyle\max_x\min_y E(x,y)=0

тэнцэтгэлийг хангах ба, максимумаа x=(\frac23,\frac13) цэг дээр авна.

Одоо 2-р тоглогчийн зүгээс юу болохыг сонирхоё. Дорх зурагт 2-р тоглогчийн хэд хэдэн стратегийн хувьд түүний дундаж оноо x_1 хувьсагчаас хэрхэн хамаарахыг үзүүлэв.

Жишээ нь, 2-р тоглогч y = (0.5,0.5) гэсэн стратеги хэрэглэвэл, 1-р тоглогч x = (1,0) стратегийг хэрэглэн тоглолт болгонд дунджаар 0.5 оноо авч чадна. Мөн дээрхтэй адилаар, алдагдалгүй болгодог тийм стратеги олдох ёстой нь харагдана. Ингээд y=(\alpha,\beta) гэж бичээд, \alpha+\beta=1 ба x_1+x_2=1 гэдгийг ашиглавал

E(x,y)=(-\alpha+2\beta)x_1+(2\alpha-4\beta)x_2=6\alpha-4+(6-9\alpha)x_1

гэж гарах ба, эндээс

\displaystyle \alpha= \frac23

үед E(x,y)\equiv0 байх нь олдоно. Өөрөөр хэлбэл, 2-р тоглогч 2/3 магадлалтайгаар алгаа, 1/3 магадлалтайгаар гарынхаа ар талыг харуулах стратеги хэрэглэснээр өөрийгөө алдагдлаас сэргийлж чадна. Үүнийг арай өөрөөр илэрхийлбэл, E функц

\displaystyle\min_y\max_x E(x,y)=0

тэнцэтгэлийг хангах ба, минимумаа y=(\frac23,\frac13) цэг дээр авна. Дээр өгүүлсэнтэй нэгтгэн дүгнэвэл,

\displaystyle\min_y\max_x E(x,y)=\max_x\min_y E(x,y)

болох тул, бодлого минимакс шийдтэй ба шийд нь x=(\frac23,\frac13), y=(\frac23,\frac13) гэсэн хосоор өгөгдөнө.

Фон Нейманы онолын гол үр дүн нь минимакс теорем гэж нэрлэгдсэн дараах теорем юм.

Минимакс теорем (Фон Нейман 1928). Хоёр тоглогчтой, тэг нийлбэрт тоглоом бүр минимакс шийдтэй.

Минимакс шийд цор ганц байх уу (үнэндээ цор ганц байх албагүй), ийм шийдийг яаж олох вэ гэдэг асуултуудад фон Нейманы теорем хариу өгөхгүй. Бид эдгээр асуултыг энд нь үлдээгээд постныхоо гол асуудал руу шууд оръё.

Наш

Фон Нейманы тоглоомын онолыг шинэ өндөрлөгт гаргасан хүн бол Жон Наш (бид Наш, Нэш гэсэн бичилтүүдийг ичиж зоволгүйгээр хольж хэрэглэнэ) юм. 1951 онд хэвлүүлсэн докторын ажилдаа тэр фон Нейманы минимакс стратегийн тухай ойлголтыг олон тоглогчтой тоглоомын хувьд өргөтгөж, Нэшийн тэнцвэр гэсэн ухагдахууныг тодорхойлсон ба, ийм тэнцвэр үргэлж оршин байхыг баталсан. Олон тоглогчтой тоглоомын ерөнхий онолд тоглоом тэг нийлбэртэй эсэх нь тийм ч чухал зүйл биш юм. Учир нь ямар ч тоглоомонд бүх тоглогчдын нийлбэр алдаа оноог «шингээж» тэг болгодог нэг хийсвэр тоглогч нэмснээр тоглоомыг тэг нийлбэртэй болгож болно. Тэгэхээр Нашийн онол нь 2 тоглогчтой, тэг биш нийлбэрт тоглоомуудыг агуулах тул 2 тоглогчтой үед ч гэсэн фон Нейманы онолоос илүү өргөн хүрээтэй онол юм. Бид энд зөвхөн 2 тоглогчтой тоглоомуудыг авч үзнэ.

Хоёр тоглогчтой тоглоомын дүрэм нь m хэмжээтэй A=[a_{ik}] ба B=[b_{ik}] гэсэн 2 матрицаар өгөгдөнө. Энд тоглоом нь тэг нийлбэртэй байх албагүй тул A+B\neq0 байж болно. Түүнчлэн 1-р тоглогчийн стратеги x_1+\ldots+x_n=1 байх x_1\geq0,\ldots,x_n\geq0 гэсэн тоонуудаар, хоёрдугаар тоглогчийн стратегийг y_1+\ldots+y_m=1 байх y_1\geq0,\ldots,y_m\geq0 гэсэн тоонуудаар өгөгдөх ба, хоёр тоглогч тус бүрийн нэг тоглолтын дундаж оноо харгалзан

E_1(x,y)=x^\top\!Ay,\qquad E_2(x,y)=x^\top\!By

байна. Тухайлбал, 1-р тоглогчийн стратеги нь

\Delta_n=\{x\in\mathbb{R}^n:x_1+\ldots+x_n=1,x_i\geq0\}

гэсэн (компакт гүдгэр) олонлогийн элемент бол, 2-р тоглогчийн стратеги нь \Delta_m олонлогийн элемент болно.

Тодорхойлолт. Хоёр тоглогчийн x^*\in\Delta_n ба y^*\in\Delta_m гэсэн стратеги дараах нөхцлүүдийг хангадаг бол энэ хос стратегийг Нэшийн тэнцвэр гэнэ:

  • Дурын x\in\Delta_n стратегийн хувьд E_1(x,y^*)\leq E_1(x^*,y^*).
  • Дурын y\in\Delta_m стратегийн хувьд E_2(x^*,y)\leq E_2(x^*,y^*).

Өөрөөр хэлбэл, Нэшийн тэнцвэрт орсон тоглоомонд аль ч тоглогч нь өөрийн стратегийг яаж ч өөрчлөөд өөрийн нөхцөл байдлыг сайжруулж чадахгүй. Нэшийн тэнцвэрийн тухай ойлголтыг анх Францын математикч Антуан Курно 1838 онд хэвлүүлсэн номондоо цэвэр стратегийн хувьд тодорхой жишээнүүд дээр хэрэглэсэн байдаг. Энэ чиглэлээр Нашийн хийсэн шинэ зүйлүүд юу вэ гэвэл:

  • Нэшийн тэнцвэрийг холимог стратегийн хувьд тодорхойлсон.
  • Нэшийн тэнцвэр үргэлж оршин байхыг баталсан.
  • Тоглогчид Нэшийн тэнцвэр лүү хэрхэн татагдахыг тайлбарласан юм.

Нэшийн тэнцвэр нь минимакс стратегийг тэг биш нийлбэрт тоглоомуудад өргөтгөсөн өргөтгөл гэдгийг харъя.

Лемм. Тэг нийлбэрт тоглоомын хувьд Нэшийн тэнцвэр нь минимакс шийд болно. Тодруулбал, хэрэв (x^*,y^*) нь Нэшийн тэнцвэр бол 

\displaystyle E_1(x^*,y^*)=\max_{x\in\Delta_n}\min_{y\in\Delta_m} E_1(x,y)=\min_{y\in\Delta_m}\max_{x\in\Delta_n} E_1(x,y).

Баталгаа. Хэрэв (x^*,y^*) нь Нэшийн тэнцвэр бол

E_1(x,y^*)\leq E_1(x^*,y^*),\qquad E_2(x^*,y)\leq E_2(x^*,y^*).

Тоглоом маань тэг нийлбэрт тоглоом E_1(x,y)+E_2(x,y)=0 гэдгийг санавал сүүлийн тэнцэл биш

E_1(x^*,y)\geq E_1(x^*,y^*)

болж хувирах тул

E_1(x,y^*)\leq E_1(x^*,y^*)\leq E_1(x^*,y)

буюу

\displaystyle\max_x E_1(x,y^*)\leq E_1(x^*,y^*)\leq \min_y E_1(x^*,y)

гэж гарна. Эндээс шууд

\displaystyle\min_y\max_x E_1(x,y)\leq E_1(x^*,y^*)\leq \max_x\min_y E_1(x,y)

болно. Нөгөө талаас,

\displaystyle E_1(x',y')\geq \min_yE_1(x',y)

гэсэн тривиал тэнцэл бишээс эхлэн,

\displaystyle \max_xE_1(x,y')\geq\max_x\min_yE_1(x,y)

гэж шууд мөрдөх ба, үүний зүүн гар тал нь y'-ийн функц, баруун гар тал нь тогтмол тул хоёр талаас нь минимум авснаар

\displaystyle \min_y\max_xE_1(x,y)\geq\max_x\min_yE_1(x,y)

болно. Ингээд лемм батлагдлаа.

Тэг биш нийлбэрт тоглоомуудын хувьд минимакс теоремын өргөтгөл нь дараах теорем юм.

Теорем (Наш 1950). Хоёр тоглогчтой ямар ч тоглоомын хувьд Нэшийн тэнцвэр оршин байна.

Нэшийн теоремыг батлахын тулд бид Брауэрийн бэхлэгдсэн цэгийн теоремыг ашиглана.

Брауэрийн теорем (Боль 1904, Адамар 1910, Брауэр 1910). U\subset\mathbb{R}^n нь зааглагдсан битүү гүдгэр олонлог, f:U\to U нь тасралтгүй функц байг. Тэгвэл f(x)=x байх x\in U цэг оршин байна.

Юуны түрүүнд, e_1=(1,0,\ldots,0)e_2=(0,1,0,\ldots,0), гэх мэтчилэн, \mathbb{R}^n огторгуй дахь i-р стандарт векторыг (ө.х. i-р цэвэр стратегийг) e_i гэж тэмдэглэн,

G_i(x,y)=\max\{0,E_1(e_i,y)-E_1(x,y)\}

ба

H_k(x,y)=\max\{0,E_2(x,e_k)-E_2(x,y)\}

гэсэн 2 функц тодорхойлъё. Үүнд G_i(x,y) нь 1-р тоглогч өөрийн стратегийг i-р цэвэр стратегиар сольсноор хожоо гарах уу, гарвал хэр их хожоо гарах вэ гэдгийг идэрхийлнэ. Нөгөө H_k функцийн хувьд үүнтэй төстэй, 2-р тоглогч стратегиа өөрчилбөл юу болохыг илэрхийлнэ. Дээрх функцүүд нь \Delta_n\times\Delta_m муж дээр тодорхойлогдсон, сөрөг биш утга авдаг тасралтгүй функцүүд болох нь ойлгомжтой. Одоо f:(x,y)\mapsto(x',y') функцийг

\displaystyle x_i'=\frac{x_i+G_i(x,y)}{1+\sum_{j=1}^nG_j(x,y)},\qquad y_k'=\frac{y_k+H_k(x,y)}{1+\sum_{j=1}^mH_j(x,y)}

гэж тодорхойлъё. Тэгвэл x_i'\geq0 ба y_k'\geq0. Түүнчлэн, \sum_{i=1}^nx_i=1 гэдгээс

\displaystyle \sum_{i=1}^nx_i'=\frac{\sum_{i=1}^nx_i+\sum_{i=1}^nG_i(x,y)}{1+\sum_{j=1}^nG_j(x,y)}=1,

мөн \sum_{k=1}^my_k=1 гэдгээс

\displaystyle \sum_{k=1}^my_k'=\frac{\sum_{k=1}^my_k+\sum_{k=1}^mH_k(x,y)}{1+\sum_{j=1}^mH_j(x,y)}=1

гэж гарах тул

(x,y)\in\Delta_n\times\Delta_m\qquad\Longrightarrow\qquad f(x,y)\in\Delta_n\times\Delta_m.

Ингээд f нь тасралтгүй функц ба \Delta_n\times\Delta_m\subset\mathbb{R}^{n+m} нь зааглагдсан, битүү, гүдгэр олонлог учир Брауэрийн теорем ёсоор

f(x^*,y^*)=(x^*,y^*)\qquad\qquad(*)

байх (x^*,y^*)\in\Delta_n\times\Delta_m хос оршин байна. Одоо бид үүнийг Нэшийн тэнцвэр гэж харуулна. Дээрх (*) нөхцлийг задалж бичвэл

\displaystyle x_i^*=\frac{x_i^*+G_i(x^*,y^*)}{1+\sum_{j=1}^nG_j(x^*,y^*)},\qquad y_k^*=\frac{y_k^*+H_k(x^*,y^*)}{1+\sum_{j=1}^mH_j(x^*,y^*)}

буюу

\displaystyle x_i^*\sum_{j=1}^nG_j(x^*,y^*)=G_i(x^*,y^*),\qquad y_k^*\sum_{j=1}^mH_j(x^*,y^*)=H_k(x^*,y^*)\qquad\qquad(**)

болно. Эндээс хэрэв

\displaystyle \sum_{j=1}^nG_j(x^*,y^*)>0\qquad\qquad(\dagger)

бол,

 \displaystyle x_i^*>0\qquad\Longrightarrow\qquad G_i(x^*,y^*)>0

болох нь харагдана. Сүүлийн {}G_i(x^*,y^*)>0 тэнцэл биш нь

E_1(e_i,y^*)>E_1(x^*,y^*)

гэсэн үг. Тэгэхээр (\dagger) нөхцөл биелж байгаа үед

 \displaystyle x_i^*>0\qquad\Longrightarrow\qquad E_1(e_i,y^*)>E_1(x^*,y^*).

Одоо нэг талаас

\displaystyle E_1(x^*,y^*)=\sum_{i=1}^nx_i^*E_1(e_1,y^*)

гэдгийг, нөгөө талаас x_i^*\geq0 ба \sum_{i=1}^nx_i^*=1 учраас бүгд x_i^*=0 байх боломжгүйг санавал

\displaystyle E_1(x^*,y^*)=\sum_{i=1}^nx_i^*E_1(e_1,y^*)>\sum_{i=1}^nx_i^*E_1(x^*,y^*)=E_1(x^*,y^*)

гэсэн зөрчилд хүрнэ. Иймд (\dagger) нөхцөл биелдэггүй, ө.х.

\displaystyle\sum_{j=1}^nG_j(x^*,y^*)=0

болох нь батлагдана. Мөн үүнтэй яг адилаар

\displaystyle\sum_{j=1}^mH_j(x^*,y^*)=0

гэж гарна. Эдгээр үр дүнгүүдээ (**) томъёонд орлуулбал

G_i(x^*,y^*)=0,\qquad H_k(x^*,y^*)=0

болох ба, энэ нь G_i, H_k функцүүдийн тодорхойлолт ёсоор

E_1(e_i,y^*)\leq E_1(x^*,y^*),\qquad E_2(x^*,e_k)\leq E_2(x^*,y^*)

гэсэн үг. Эцэст нь, дурын x\in\Delta_n стратегийн хувьд

\displaystyle E_1(x,y^*)=\sum_{i=1}^nx_iE_1(e_1,y^*)\leq \sum_{i=1}^nx_iE_1(x^*,y^*)=E_1(x^*,y^*)

ба, дурын y\in\Delta_m стратегийн хувьд

\displaystyle E_2(x^*,y)=\sum_{k=1}^my_kE_2(x^*,e_k)\leq \sum_{k=1}^my_kE_2(x^*,y^*)=E_2(x^*,y^*)

тул (x^*,y^*) хос маань Нэшийн тэнцвэр болох нь харагдана. Нэшийн теорем батлагдав.

Жон фон Нейман (1903–1957), Жон Форбс Наш (1928–2015)

This entry was posted in Анализ and tagged , , , , . Bookmark the permalink.

1 Response to Нэшийн тэнцвэр

  1. odbayar хэлдэг:

    bayarlalaa

Хариу Үлдээх

Fill in your details below or click an icon to log in:

WordPress.com Logo

Та WordPress.com гэсэн бүртгэлээрээ сэтгэгдэл бичиж байна. Гарах /  Өөрчлөх )

Google photo

Та Google гэсэн бүртгэлээрээ сэтгэгдэл бичиж байна. Гарах /  Өөрчлөх )

Twitter picture

Та Twitter гэсэн бүртгэлээрээ сэтгэгдэл бичиж байна. Гарах /  Өөрчлөх )

Facebook photo

Та Facebook гэсэн бүртгэлээрээ сэтгэгдэл бичиж байна. Гарах /  Өөрчлөх )

Connecting to %s