صفر حاصل جمع

آزاد دائرۃ المعارف، ویکیپیڈیا سے
:چھلانگ بطرف رہنمائی، تلاش
اصطلاح term

بازی
صفر حاصل جمع
کاٹھی نقطہ
خالص
آمیزی
حکمتِ عملی
صغیر کبیر
تصغیر
تکبیر

game
zero sum
saddle-point
pure
mixed
strategy
min max
minimize
maximize

"نظریہ بازی" اور اقتصادیات میں صفر حاصل جمع ایسی بازی کو کہتے ہیں جس میں بازی میں شریک ایک شخص کا منافع دوسرے شخص (یا اشخاص) کے نقصان کے برابر ہو۔ یعنی اگر بازی میں فائدہ اُٹھانے والوں کے منافع کو جمع کیا جائے اور اس میں سے نقصان اُٹھانے والوں کا کُل گھاٹا تفریق کر دیا جائے تو جواب صفر ہو۔ دو اشخاص کے کو ایک m \times n میٹرکس [r_{i,j}] پیش ہوتی ہے۔ بازی اس طرح لگتی ہے: پہلا شخص 1 سے 'm' تک کسی عدد i کا انتخاب کرتا ہے اور اسی وقت (آزادانہ طور پر) دوسرا شخص 1 سے 'n' تک کسی عدد j کا انتخاب کرتا ہے۔ اس بازی کے نتیجے میں دوسرے شخص کو r_{i,j} روپے پہلے شخص کو دینے پڑتے ہیں۔

مثال کے طور پر نیچے دی میٹرکس دیکھو۔ یاد رہے کہ میٹرکس کی قطاریں اوپر سے نیچے گنی جاتی ہیں، اور ستون بائیں سے دائیں۔

دوسرا شخص
پہلا شخص 
\begin{matrix}
0 & 10 & -4 \\
2 & 7  & 6 \\
1 & 3 & -3
\end{matrix}

پہلا شخص تین قطاروں میں سے کسی کا انتخاب کرتا ہے، جبکہ دوسرا شخص تین ستونوں میں سے کسی کا انتخاب کرتا ہے۔ اگر پہلا شخص قطار 1 کا انتخاب کرے اور دوسرا شخص ستون 2 کا انتخاب کرے، تو دوسرے شخص کو 10 روپے پہلے شخص کو دینے ہونگے۔ یعنی پہلا شخص 10 جیتے گا (اور دوسرا شخص 10 ہارے گا)۔ اگر پہلا شخص قطار 1 کا انتخاب کرے اور دوسرا شخص ستون 3 کا انتخاب کرے، تو دوسرے شخص کو ‎-4 روپے پہلے شخص کو دینے ہونگے۔ یعنی دوسرا شخص 4 جیتے گا (اور پہلا شخص 4 ہارے گا)۔ اس بازی کی ان پہلے شخص کے لیے کیا قیمت ہے؟ اگر پہلا شخص قطار 2 چنے، تو وہ یہ بات یقینی بناتا ہے کہا اس کا کم از کم منافع 2 ہو گا۔ دوسرا شخص (جو اپنا گھاٹا کم سے کم کرنا چاہتا ہے) اگر ستون 1 چنے تو اس کا زیادہ سے زیادہ تقصان 2 ہو گا۔ یہ چناؤ ان دونوں کے لیے بہترین حکمتِ عملی ہیں۔ اس مثال میں دیکھو کہ 2 اپنی قطار کی صغیر قدر ہے اور 2 اپنے ستون کا کبیر قدر ہے، یعنی میٹرکس کا کاٹھی نقطہ ہے۔ اگر میٹرکس کا "کاٹھی نقطہ" نہ ہو تو بازی کی قیمت آسانی سے نہیں نکل سکتی اور اس کے لیے احتمالی منطق کا استعمال مفید رہتا ہے۔ اگر کوئی شخص دی ہوئی میٹرکس کے لیے ایک ہی بازی استعمال کرے تو اسے "خالص حکمت عملی" کہتے ہیں۔ اگر پہلا شخص قطار 1,2,\cdots,m کا بالترتیب احتمال p=(p_1,p_2,\cdots,p_m) سے انتخاب کرے تو اسے "آمیزی حکمت عملی" کہیں گے۔ اگر دوسرا شخص خالص حکمت عملی ستون j استعمال کرتا ہے، تو پہلے شخص کے منافع کا اوسط  \sum_{i=1}^m p_i r_{i,j} ہو گا۔ چونکہ دوسرا شخص ستون j چننے میں آزاد ہے، اسلیے پہلا شخص کا منافع کم از کم

 \min_{1 \le j \le n} \sum_{i=1}^m p_i r_{i,j}

ہو گا۔ پہلا شخص ایسا احتمال سمتیہ p چنے گا جو اس کے متوقع منافع کی تکبیر کرے، یعنی

 V_1 = \max_{p} \min_{1 \le j \le n} \sum_{i=1}^m p_i r_{i,j}

اسی طرح دوسرا شخص بھی آمیزی حکمتِ عملی استعمال کر سکتا ہے۔ اگر یہ احتمال سمتیہ q=(q_1,q_2,\cdots,q_n) کے مطابق ستون 1,2,\cdots,n کا انتخاب کرے تو پہلے شخص کی خالص حکمت عملی قطار i کے لیے دوسرے شخص کا زیادہ سے زیادہ نقصان

 \max_{1 \le i \le m} \sum_{j=1}^n q_j r_{i,j}

ہو گا۔ اب دوسرا شخص اپنا احتمال سمتیہ q ایسے چنے گا کہ اس نقصان کی متوقع قدر کی تصغیر ہو، یعنی

 V_2=\min_{q} \max_{1 \le i \le m} \sum_{j=1}^n q_j r_{i,j}

تصغیر تکبیر مسلئہ اثباتی[ترمیم]

اس مسلئہ اثباتی کی رُو سے  V_1=V_2

اس کے ثبوت میں یہ دکھایا جاتا ہے کہ پہلے شخص کا مقصود اس مقدم لکیری برمجہ:

تکبیر w
زیرِ اطاعت (جبکہ یہ نامساوات پوری ہوں)
\sum_{i=1}^m x_i r_{i,j} \ge w \,\,,\, j=1,\cdots, n
\sum_{i=1}^m x_i =1
 x_i \ge 0

کا حل ہے۔ جبکہ دوسرے شخص کا مقصود اس کے ثنوی لکیری برمجہ:

تصغیر u
زیرِ اطاعت (جبکہ یہ نامساوات پوری ہوں)
\sum_{j=1}^n y_j r_{i,j} \le u \,\,,\, i=1,\cdots, m
\sum_{j=1}^n y_j =1
 y_j \ge 0

کا حل ہے۔ اور اس رشتہ سے پہلے مسلئہ کا حل دوسرے مسلئہ کا حل بھی ہے، یعنی u=w

E=mc2     اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے     ریاضی علامات