Zero-Sum Games & Mixed Strategies

অনুপ্রেরণা

গত অধ্যায় শেষ হয়েছিল একটি ধাঁধা দিয়ে: ম্যাচিং পেনিজে কোনো বিশুদ্ধ-কৌশল ন্যাশ ইকুইলিব্রিয়াম নেই। যদি দুই খেলোয়াড়কেই অন্যজনের পদক্ষেপ দেখার আগে হেড বা টেইলে কমিট করতে হয়, তাহলে বিশুদ্ধ কৌশলের প্রতিটি সমন্বয় একজনকে সুইচ করতে চায়। তাই যদি ইকুইলিব্রিয়াম সঠিক সমাধান ধারণা হয়, এবং ইকুইলিব্রিয়াম অবশ্যই বিদ্যমান থাকতে হবে (ন্যাশের উপপাদ্য অন্তত একটির গ্যারান্টি দেয়), তাহলে আমাদের বিশুদ্ধ কৌশলের বাইরে তাকাতে হবে।

সেই বাইরে হলো মিশ্র কৌশল — সম্ভাব্যতা বিতরণ অনুসারে বিশুদ্ধ কৌশলের উপর র‍্যান্ডমাইজ করা। মিশ্র কৌশল ন্যাশ ইকুইলিব্রিয়াম (MSNE) হলো গেম থিওরির সবচেয়ে মার্জিত ধারণাগুলোর একটি: প্রতিটি খেলোয়াড় এমনভাবে র‍্যান্ডমাইজ করে যা অন্য খেলোয়াড়কে তার সব বিশুদ্ধ কৌশলের মধ্যে নিরপেক্ষ করে তোলে। একবার নিরপেক্ষ হলে, প্রতিপক্ষের কোনো লাভজনক বিচ্যুতি নেই — ইকুইলিব্রিয়াম।

বাস্তব জীবনের দৃশ্য: পেনাল্টি কিক

ফুটবলে একটি পেনাল্টি কিক হলো মিশ্র-কৌশল ইকুইলিব্রিয়ামের সবচেয়ে পরিষ্কার বাস্তব-বিশ্বের উদাহরণ। কিকার বাম, ডান বা মাঝখানে শট নিতে পারে। গোলরক্ষক বামে, ডানে ঝাঁপ দিতে পারে বা কেন্দ্রে থাকতে পারে। কিকার গোল করতে চায়; গোলরক্ষক সেভ করতে চায়। বিশুদ্ধ কৌশল ব্যর্থ: যে কিকার সবসময় বামে শট নেয় তাকে প্রতিটি দক্ষ গোলরক্ষক পড়ে ফেলবে।

এলিট ফুটবলে আসলে কী ঘটে? উভয় খেলোয়াড়ই র‍্যান্ডমাইজ করে। পেশাদার কিকাররা প্রতিটি দিকে প্রায় এক-তৃতীয়াংশ সময় শট নেয়। গোলরক্ষকরা প্রতিটি দিকে প্রায় এক-তৃতীয়াংশ সময় ঝাঁপ দেয়। ১/৩-১/৩-১/৩ মিশ্রণ ঠিক সেই রক-পেপার-সিজার্স ইকুইলিব্রিয়াম যা আমরা এই অধ্যায়ের শেষে ডেরাইভ করব। শীর্ষ ইউরোপীয় লিগের তথ্য এটি নিশ্চিত করে।

গাণিতিক দিক: শূন্য-সমষ্টি গেম

পেওয়াফ ফাংশন $u_1, u_2, \dots, u_n$ সহ একটি গেম শূন্য-সমষ্টি যদি, প্রতিটি কৌশল প্রোফাইলের জন্য,

$$\sum_{i=1}^{n} u_i(s) \;=\; 0 \quad \text{(বা সমতুল্যভাবে, কিছু ধ্রুবক } c\text{)।}$$

দুই-খেলোয়াড় শূন্য-সমষ্টি গেমে এটি সরলীকৃত হয়

$$u_1(s) + u_2(s) = 0 \quad \Leftrightarrow \quad u_2(s) = -u_1(s).$$

সহজ ভাষায়: একজন খেলোয়াড় যা জিতবে, অন্যজন তা হারাবে।

শূন্য-সমষ্টি গেমের বেশ কিছু সুন্দর বৈশিষ্ট্য আছে:

• এগুলো কঠোরভাবে প্রতিযোগিতামূলক। কোনো পারস্পরিক লাভের সম্ভাবনা নেই।
• বিশ্লেষণ প্রতিটি খেলোয়াড়ের দৃষ্টিকোণ থেকে প্রতিসম: নিজের পেওয়াফ সর্বোচ্চ করা প্রতিপক্ষের পেওয়াফ সর্বনিম্ন করার সমতুল্য।
• মিনিম্যাক্স উপপাদ্য (ভন নিউম্যান, ১৯২৮) বলে প্রতিটি সসীম দুই-খেলোয়াড় শূন্য-সমষ্টি গেমের একটি মান আছে এবং উভয় খেলোয়াড়ের সর্বোত্তম মিশ্র কৌশল আছে যা এটি অর্জন করে।

গাণিতিক দিক: মিশ্র কৌশল

বিশুদ্ধ কৌশল সেট $S_i$ সহ খেলোয়াড় $i$-এর জন্য একটি মিশ্র কৌশল হলো সম্ভাব্যতা বিতরণ $\sigma_i \in \Delta(S_i)$, যেখানে $\Delta(S_i)$ হলো $S_i$-এর উপর সম্ভাব্যতা ভেক্টরের সিমপ্লেক্স:

$$\sigma_i(s) \geq 0 \text{ সব } s \in S_i\text{-এর জন্য}, \qquad \sum_{s \in S_i} \sigma_i(s) = 1.$$

কৌশল প্রোফাইল $(\sigma_1, \dots, \sigma_n)$ হলে খেলোয়াড় $i$-এর প্রত্যাশিত পেওয়াফ হলো

$$U_i(\sigma_1, \dots, \sigma_n) \;=\; \sum_{s_1 \in S_1} \dots \sum_{s_n \in S_n} \left[ \prod_{j=1}^n \sigma_j(s_j) \right] u_i(s_1, \dots, s_n).$$

কেন মিশ্র করব?

একটি বিশুদ্ধ কৌশল হলো একটি অবক্ষয় মিশ্র কৌশল যা একটি পদক্ষেপে সম্ভাব্যতা 1 রাখে। তাই মিশ্র কৌশল বিশুদ্ধ কৌশলকে বিশেষ ক্ষেত্রে অন্তর্ভুক্ত করে। কিন্তু কিছু গেমে (ম্যাচিং পেনিজ, রক-পেপার-সিজার্স) কোনো বিশুদ্ধ প্রোফাইল স্থিতিশীল নয়। প্রতিটি খেলোয়াড় অপ্রত্যাশিত হওয়া থেকে উপকৃত হয়। মিশ্রণ অপ্রত্যাশিততা অর্জন করে।

মিশ্র কৌশল ন্যাশ ইকুইলিব্রিয়াম (MSNE)

একটি কৌশল প্রোফাইল $(\sigma_1^*, \dots, \sigma_n^*)$ হলো মিশ্র কৌশল ন্যাশ ইকুইলিব্রিয়াম যদি, প্রতিটি খেলোয়াড় $i$-এর জন্য,

$$U_i(\sigma_i^*, \sigma_{-i}^*) \;\geq\; U_i(\sigma_i, \sigma_{-i}^*) \quad \text{সব } \sigma_i \in \Delta(S_i)\text{-এর জন্য।}$$

নিরপেক্ষতা নীতি ২-খেলোয়াড় গেমে MSNE গণনার ব্যবহারিক চাবিকাঠি:

দুই-খেলোয়াড় গেমের মিশ্র কৌশল ন্যাশ ইকুইলিব্রিয়ামে, প্রতিটি খেলোয়াড়ের মিশ্র কৌশল অন্য খেলোয়াড়কে তার বিশুদ্ধ কৌশলগুলোর মধ্যে নিরপেক্ষ করে তোলে যেগুলো ইতিবাচক সম্ভাব্যতা পায়।

এটি ইকুইলিব্রিয়াম-খোঁজাকে বীজগণিতে রূপান্তর করে: প্রতিটি বিশুদ্ধ কৌশলের প্রত্যাশিত পেওয়াফ সমান করো, প্রতিপক্ষের সম্ভাব্যতা সমাধান করো, তারপর অন্য পক্ষের জন্যও তাই করো।

ডেরাইভেশন: সাধারণ ২×২ নিরপেক্ষতা সমীকরণ

নিম্নলিখিত পেওয়াফ ম্যাট্রিক্স সহ একটি সাধারণ ২×২ গেম বিবেচনা করো (শুধু Row পেওয়াফ — Col পেওয়াফ সামঞ্জস্যতা অনুসারে):

Row সম্ভাব্যতা $p$-তে U এবং Col সম্ভাব্যতা $q$-তে L খেলে। প্রতিটি বিশুদ্ধ পদক্ষেপ থেকে Row-এর প্রত্যাশিত পেওয়াফ:

$$\mathbb{E}[u_{\text{Row}} \mid U] \;=\; a \cdot q + b \cdot (1 - q) \;=\; b + (a - b)q$$ $$\mathbb{E}[u_{\text{Row}} \mid D] \;=\; c \cdot q + d \cdot (1 - q) \;=\; d + (c - d)q$$

Row-কে নিরপেক্ষ করতে (যাতে Row র‍্যান্ডমাইজ করতে ইচ্ছুক হয়), এগুলো সমান করো:

$$b + (a - b)q \;=\; d + (c - d)q$$

$q$-এর জন্য সমাধান:

$$q^* \;=\; \frac{d - b}{(a - b) - (c - d)} \;=\; \frac{d - b}{(a + d) - (b + c)}.$$

Col-এর প্রত্যাশিত পেওয়াফ থেকে প্রতিসম ডেরাইভেশন $p^*$ দেয়। $q^*$ কে $p^* = \ldots$-এ প্লাগ করো এবং তুমি MSNE পুনরুদ্ধার করবে। ম্যাচিং পেনিজে, $(a, b, c, d) = (1, -1, -1, 1)$, তাই লব $1 - (-1) = 2$ এবং হর $(1+1) - (-1-1) = 4$, যা দেয় $q^* = 2/4 = 1/2$ — ঠিক সেই ৫০-৫০ মিশ্রণ যা আমরা হাতে পেয়েছিলাম।

ম্যাচিং পেনিজে MSNE

পেওয়াফ ম্যাট্রিক্স মনে রাও:

A সম্ভাব্যতা $p$-তে হেড এবং $1-p$-তে টেইল খেলে। B সম্ভাব্যতা $q$-তে হেড এবং $1-q$-তে টেইল খেলে।

ধাপ ১ — B-এর নিরপেক্ষতা শর্ত।

B $q$ বেছে নিতে চায় যাতে A হেড ও টেইলের মধ্যে নিরপেক্ষ হয়।

• A-এর হেড থেকে প্রত্যাশিত পেওয়াফ: B হেড খেললে, A +1 জিতে; B টেইল খেললে, A −1 হারায়। প্রত্যাশিত পেওয়াফ = $q \cdot 1 + (1-q) \cdot (-1) = 2q - 1$।
• A-এর টেইল থেকে প্রত্যাশিত পেওয়াফ: B হেড খেললে, A −1 হারায়; B টেইল খেললে, A +1 জিতে। প্রত্যাশিত পেওয়াফ = $q \cdot (-1) + (1-q) \cdot 1 = 1 - 2q$।

সমান করো: $2q - 1 = 1 - 2q \Rightarrow 4q = 2 \Rightarrow q = 1/2$।

তাই B-কে অবশ্যই সম্ভাব্যতা $1/2$-এ হেড খেলতে হবে যাতে A নিরপেক্ষ থাকে।

ধাপ ২ — A-এর নিরপেক্ষতা শর্ত।

সামঞ্জস্যতা অনুসারে, A-কে অবশ্যই সম্ভাব্যতা $p = 1/2$-এ হেড খেলতে হবে।

ধাপ ৩ — MSNE।

$$p^* = q^* = \tfrac{1}{2}.$$

উভয় খেলোয়াড় হেড ও টেইলের মধ্যে ৫০-৫০ মিশ্রণ করে। এটি গেমের একমাত্র MSNE।

রক-পেপার-সিজার্সে MSNE

পেওয়াফ ম্যাট্রিক্স:

A রক সম্ভাব্যতা $p_R$, পেপার সম্ভাব্যতা $p_P$, সিজার্স সম্ভাব্যতা $p_S$ খেলে, যেখানে $p_R + p_P + p_S = 1$। B-এর জন্যও একইভাবে $q_R, q_P, q_S$।

ধাপ ১ — B-এর নিরপেক্ষতা শর্ত।

B $q_R, q_P, q_S$ বেছে নেয় যাতে A তিনটি বিশুদ্ধ কৌশলের মধ্যে নিরপেক্ষ হয়।

• A-এর রক থেকে প্রত্যাশিত পেওয়াফ: $q_R \cdot 0 + q_P \cdot (-1) + q_S \cdot 1 = q_S - q_P$।
• A-এর পেপার থেকে প্রত্যাশিত পেওয়াফ: $q_R \cdot 1 + q_P \cdot 0 + q_S \cdot (-1) = q_R - q_S$।
• A-এর সিজার্স থেকে প্রত্যাশিত পেওয়াফ: $q_R \cdot (-1) + q_P \cdot 1 + q_S \cdot 0 = q_P - q_R$।

তিনটিকে সমান করতে হলে:

$$q_S - q_P = q_R - q_S = q_P - q_R.$$

এই সিস্টেম, $q_R + q_P + q_S = 1$ শর্তসহ, এর একমাত্র সমাধান:

$$q_R = q_P = q_S = \tfrac{1}{3}.$$

ধাপ ২ — সামঞ্জস্যতা অনুসারে, A-এর মিশ্রণও ১/৩-১/৩-১/৩।

$$p_R^* = p_P^* = p_S^* = q_R^* = q_P^* = q_S^* = \tfrac{1}{3}.$$

প্রতিটি খেলোয়াড় তিনটি পদক্ষেপের উপর সমানভাবে র‍্যান্ডমাইজ করে। এটি একমাত্র MSNE।

সাধারণ ভুল

• "মিশ্র কৌশল" কে "মিশ্র-কৌশল ইকুইলিব্রিয়াম" এর সাথে গুলিয়ে ফেলা। একটি মিশ্র কৌশল হলো বিশুদ্ধ কৌশলের উপর যেকোনো র‍্যান্ডমাইজেশন। একটি MSNE হলো একটি বিশেষ র‍্যান্ডমাইজেশন যা কেউ বিচ্যুত হতে চায় না।
• হাতে সমাধান করতে গিয়ে নিরপেক্ষতা নীতি ভুলে যাওয়া। সঠিক সমীকরণ স্থাপন করা কাজের ৮০%।
• র‍্যান্ডমাইজেশন অযৌক্তিক বলে বিশ্বাস করা।
• প্রতিসম গেমের MSNE গণনা করা এবং উত্তর প্রতিসম বলে ধরে নেওয়া।
• শূন্য-সমষ্টি গেমই একমাত্র যেগুলোতে মিশ্র ইকুইলিব্রিয়াম আছে বলে ভাবা।

সারসংক্ষেপ

• একটি শূন্য-সমষ্টি গেম হলো যেখানে একজনের লাভ ঠিক অন্যজনের ক্ষতি।
• একটি মিশ্র কৌশল হলো বিশুদ্ধ কৌশলের উপর সম্ভাব্যতা বিতরণ।
• একটি মিশ্র কৌশল ন্যাশ ইকুইলিব্রিয়াম (MSNE) হলো মিশ্র কৌশলের এমন একটি প্রোফাইল যেখানে কোনো খেলোয়াড়ই বিচ্যুত হতে চায় না।
• নিরপেক্ষতা নীতি: MSNE-তে, প্রতিটি খেলোয়াড়ের মিশ্রণ প্রতিপক্ষকে ইতিবাচক সম্ভাব্যতা পাওয়া বিশুদ্ধ কৌশলগুলোর মধ্যে নিরপেক্ষ করে।
• ম্যাচিং পেনিজ MSNE: উভয় খেলোয়াড় হেড ও টেইলের মধ্যে ৫০-৫০ মিশ্রণ করে।
• রক-পেপার-সিজার্স MSNE: উভয় খেলোয়াড় রক, পেপার, সিজার্স জুড়ে ১/৩-১/৩-১/৩ মিশ্রণ করে।
• সমান মিশ্রণ প্রতিটি গেমে একমাত্র অব্যাখ্যেয় র‍্যান্ডমাইজেশন।

পরবর্তী কী?

এতদিন আমরা বিশ্লেষণ করেছি এমন প্রতিটি গেমে খেলোয়াড়রা একসাথে পদক্ষেপ নিয়েছে। পরবর্তী অধ্যায় থেকে আমরা ধারাবাহিক গেমে সুইচ করি: খেলোয়াড়রা একে একে পদক্ষেপ নেয়, প্রায়ই পূর্ববর্তী পদক্ষেপ পর্যবেক্ষণ করে, এবং বিশ্লেষণ সম্পূর্ণভাবে পরিবর্তিত হয়।