Game Theory Foundations

অনুপ্রেরণা

ধরো তুমি আর তোমার বন্ধু দুজনে কফি শপে বসে আছো, পরে কোথায় যাবে সেটা ঠিক করবে। তুমি বিরিয়ানি খেতে চাও, তোমার বন্ধু পিৎজা খেতে চায়। দুজনের কাছেই একসাথে থাকা যেকোনো খাবারের চেয়ে বেশি গুরুত্বপূর্ণ — কিন্তু কেউই কথা বলতে পারছে না। যাই করো, ফলাফল মেনে নিতে হবে। দুটি মন, দুটি সিদ্ধান্ত, একটি ফলাফল — এবং কেউই পিছিয়ে আসতে পারবে না।

এই ছোট মুহূর্তটিই একটি গেম। গেম থিওরি হলো সেই বিদ্যা যেটা এই ধরনের পরিস্থিতি — যেখানে তোমার পেওয়াফ অন্য কেউ কী করে তার উপর নির্ভর করে — একটা সুনির্দিষ্ট গাণিতিক ভাষায় রূপান্তর করে। এটা ১৯৪০ ও ৫০-এর দশকে জন ভন নিউম্যান ও জন ন্যাশ আনুষ্ঠানিকভাবে তৈরি করেন, আর এখন এটি অর্থনীতি, বিবর্তনীয় জীববিদ্যা, রাষ্ট্রবিজ্ঞান, নেটওয়ার্ক ডিজাইন, নিলাম তত্ত্ব এবং এমনকি AI সিস্টেম ডিজাইনেও ব্যবহৃত হয়।

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

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

একটা ফ্রিল্যান্স মার্কেটপ্লেসের কথা ভাবো। দুইজন বিক্রেতা — ধরো A ও B — একই প্রজেক্টের জন্য বিড করছে। প্রত্যেকে উচ্চ বা নিম্ন বিড দিতে পারে। ক্লায়েন্ট সবচেয়ে কম বিড গ্রহণ করে এবং সেই পরিমাণ পেমেন্ট করে। টাই হলে কয়েন টস হয়। দুজনেই উচ্চ বিড করলে দুজনেই ভালো মুনাফা পায়। দুজনেই নিম্ন বিড করলে দুজনেই অল্প লাভে থাকে। একজন নিম্ন ও অন্যজন উচ্চ বিড করলে নিম্ন বিডদাতা সবকিছু জিতে যায়।

এখন A-এর দৃষ্টিকোণ থেকে ভাবো। যদি B উচ্চ বিড করে, তাহলে A জিততে পারে নিম্ন বিড করে — এটা উচ্চ বিড করার চেয়ে কঠোরভাবে ভালো। যদি B নিম্ন বিড করে, তাহলে A এখনও নিম্ন বিড করে জিতবে। তাই B যাই করুক, নিম্ন বিড করাই A-এর জন্য সেরা। B-এর জন্যও একই যুক্তি। দুজনেই নিম্ন বিড করে, দুজনেই প্রায় কিছুই লাভ করে না, এবং দুজনেই চায় উচ্চ বিড করতে। এটা একটা সাধারণ শিক্ষা: যুক্তিসঙ্গত স্বার্থ, যখন সবাই যুক্তিসঙ্গত, তখন এমন ফলাফল তৈরি করতে পারে যা কেউ চায়নি। এটাই প্রিজনার্স ডাইলেমার বীজ — যেটা আমরা পরের অধ্যায়ে দেখব।

সহজাত ধারণা তৈরি

কোনো আনুষ্ঠানিক সংজ্ঞার আগে, একটা মানসিক ছবি মাথায় রাখি। একটি গেম-এ আছে মাত্র চারটি উপাদান:

• খেলোয়াড় (Players)। সিদ্ধান্ত গ্রহণকারীরা। বিড-এর উদাহরণে দুজন — বিক্রেতা A ও B। দাবায় দুজন। নির্বাচনে অনেকে। বাস্তুতন্ত্রে লক্ষ লক্ষ "খেলোয়াড়" থাকতে পারে।
• কৌশল (Strategies)। প্রতিটি খেলোয়াড় কী করতে পারে। একটি কৌশল শুধু একটি পদক্ষেপ নয় — এটি একটি সম্পূর্ণ পরিকল্পনা। এককালীন গেমে কৌশল মানে একটি পছন্দ। দাবায় কৌশল মানে শর্তসাপেক্ষ পরিকল্পনা।
• পেওয়াফ (Payoffs)। শেষে প্রতিটি খেলোয়াড় যে সংখ্যাটা পায়। অর্থ, উপযোগিতা, পয়েন্ট, টিকে থাকা, সুখ — যেকোনো কিছু যা র‍্যাঙ্ক করা যায়। গুরুত্বপূর্ণভাবে, পেওয়াফ নির্ভর করে সবার বেছে নেওয়া কৌশলের সমন্বয়ের উপর।
• নিয়ম (Rules)। প্রতিটি খেলোয়াড় কী করতে পারে, কখন, এবং কী জানে। পদক্ষেপ কি একসাথে না ধারাবাহিক? কিছু কি লুকানো? পদক্ষেপ কি প্রকাশ্য?

এই চারটি থাকলে গেম তৈরি। এই অধ্যায়ের পরের সবকিছু — পেওয়াফ ম্যাট্রিক্স, ডমিন্যান্ট স্ট্র্যাটেজি, ন্যাশ ইকুইলিব্রিয়াম — একই সেটআপ বিশ্লেষণের ভিন্ন ভিন্ন উপায়।

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

ছোট গেমের জন্য যেখানে দুই খেলোয়াড় একসাথে পদক্ষেপ নেয় এবং প্রত্যেকের মাত্র কয়েকটি কৌশল থাকে, আমরা পুরো জিনিসটি একটি টেবিলে — একটি পেওয়াফ ম্যাট্রিক্স-এ লিখতে পারি। এই কোর্সে ব্যবহৃত প্রথা:

• সারি (Rows) হলো খেলোয়াড় A-এর কৌশল।
• কলাম (Columns) হলো খেলোয়াড় B-এর কৌশল।
• প্রতিটি ঘরে দুটি সংখ্যা থাকে: প্রথমে A-এর পেওয়াফ, তারপর B-এর পেওয়াফ।

এখানে বিডিং গেমটি ম্যাট্রিক্স আকারে:

একটি পেওয়াফ ম্যাট্রিক্স হলো একটি সসীম একসাথে-পদক্ষেপ গেমের সম্পূর্ণ বর্ণনা। একবার এটা পেলে, এখান থেকে প্রতিটি ধারণা — বেস্ট রেসপন্স, ডমিন্যান্ট স্ট্র্যাটেজি, ন্যাশ ইকুইলিব্রিয়াম — শুধু ঘরের সংখ্যা দেখে উত্তরযোগ্য প্রশ্ন।

বেস্ট রেসপন্স

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

উপরের বিডিং ম্যাট্রিক্সে, ধরো B খেলে উচ্চ। "B: উচ্চ" কলামটি দেখো। A-এর পেওয়াফ হলো 4 (A: উচ্চ) এবং 6 (A: নিম্ন)। B উচ্চ খেললে A-এর বেস্ট রেসপন্স হলো নিম্ন। এখন ধরো B খেলে নিম্ন। "B: নিম্ন" কলামটি দেখো। A-এর পেওয়াফ হলো 0 (A: উচ্চ) এবং 2 (A: নিম্ন)। A-এর বেস্ট রেসপন্স এখনও নিম্ন। তাই নিম্ন হলো A-এর জন্য যেকোনো কিছুর বেস্ট রেসপন্স।

শেষোক্ত ধারণাটির একটি বিশেষ নাম আছে: ডমিন্যান্ট স্ট্র্যাটেজি।

গাণিতিক দিক

ডমিন্যান্ট স্ট্র্যাটেজি

খেলোয়াড় $i$-এর একটি কৌশল $s_i^*$ অন্য একটি কৌশল $s_i$-কে কঠোরভাবে ডমিনেট করে যদি, অন্য খেলোয়াড়দের প্রতিটি কৌশল-প্রোফাইল $s_{-i}$-এর জন্য,

$$u_i(s_i^*, s_{-i}) \;>\; u_i(s_i, s_{-i}).$$

সহজ ভাষায়: $s_i^*$ প্রতিটি ক্ষেত্রে $s_i$-এর চেয়ে কঠোরভাবে বেশি পেওয়াফ দেয়, অন্য কেউ যাই করুক।

যদি একজন খেলোয়াড়ের এমন একটি কৌশল থাকে যা তার অন্য সব কৌশলকে কঠোরভাবে ডমিনেট করে, আমরা এটিকে কঠোরভাবে ডমিন্যান্ট স্ট্র্যাটেজি বলি। যদি প্রতিটি খেলোয়াড়ের এমন একটি থাকে এবং সবাই সেটা খেলে, তাহলে ফলাফল হলো ডমিন্যান্ট স্ট্র্যাটেজি ইকুইলিব্রিয়াম (DSE)।

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

পুনরাবৃত্ত ডমিন্যান্স দ্বারা DSE ডেরাইভ

পুনরাবৃত্ত ডমিন্যান্স পদ্ধতির একটি পরিষ্কার বীজগাণিতিক রূপ আছে। $m$ সারির কৌশল এবং $n$ কলামের কৌশল সহ একটি ২-খেলোয়াড় গেমের জন্য, Col কলাম $c$ খেললে সারি $r$-এর জন্য Row-এর পেওয়াফ $u_1(r, c)$ হিসেবে লেখো। সারির কৌশল $r^*$ সারির কৌশল $r$-কে কঠোরভাবে ডমিনেট করে যদি এবং শুধুমাত্র যদি

$$u_1(r^*, c) \;>\; u_1(r, c) \quad \text{প্রতিটি } c \in \{1, \dots, n\}\text{-এর জন্য।}$$

পুনরাবৃত্ত ডমিন্যান্স তারপর রাউন্ডে এগোয়:

1. প্রতিটি খেলোয়াড়ের জন্য, প্রতিটি কঠোরভাবে ডমিনেটেড কৌশল খুঁজে বের করো এবং কেটে দাও।
2. হ্রাসকৃত গেমে মনোযোগ সীমাবদ্ধ করো।
3. কোনো ডমিনেটেড কৌশল না থাকা পর্যন্ত — অথবা গেমটি একটি একক প্রোফাইলে পতন না হওয়া পর্যন্ত — পুনরাবৃত্তি করো।

যদি গেমটি একটি একক প্রোফাইলে পতিত হয়, সেই প্রোফাইল হলো DSE। (যদি এটি পতিত না হয় — ধরো, কোনো কৌশলই কঠোরভাবে ডমিনেটেড নয় — পদ্ধতিটি DSE তৈরি না করেই থেমে যায়; তারপর তোমার ন্যাশ ইকুইলিব্রিয়াম দরকার।)

ন্যাশ ইকুইলিব্রিয়াম

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

$$u_i(s_i^*, s_{-i}^*) \;\geq\; u_i(s_i, s_{-i}^*) \quad \text{সব } s_i\text{-এর জন্য।}$$

সহজ ভাষায়: কোনো খেলোয়াড়ই একতরফাভাবে তার কৌশল পরিবর্তন করে নিজের পেওয়াফ উন্নত করতে পারে না, অন্যদের কৌশল যা-ই হোক।

এই সংজ্ঞাটি তিনটি কারণে নীরবে বিপ্লবাত্মক:

1. এটি একটি স্ব-ধারাবাহিকতার শর্ত। ন্যাশ ইকুইলিব্রিয়ামে, প্রত্যেকের পছন্দ প্রত্যেকের অন্যের পছন্দের বেস্ট রেসপন্স।
2. এটি একতরফা। একজন খেলোয়াড় শুধুমাত্র নিজের বিচ্যুতি পরীক্ষা করতে পারে। আমরা জিজ্ঞেস করি না "দুজন একসাথে পরিবর্তন করলে কী হবে?"
3. এটি সসীম গেমে সর্বদা বিদ্যমান। এটি জন ন্যাশের ১৯৫০ সালের উপপাদ্য।

ডমিন্যান্ট স্ট্র্যাটেজি ইকুইলিব্রিয়াম ⊂ ন্যাশ ইকুইলিব্রিয়াম

এটি পুরো কোর্সের সবচেয়ে গুরুত্বপূর্ণ সম্পর্কগুলোর একটি:

প্রতিটি ডমিন্যান্ট স্ট্র্যাটেজি ইকুইলিব্রিয়াম একটি ন্যাশ ইকুইলিব্রিয়াম, কিন্তু প্রতিটি ন্যাশ ইকুইলিব্রিয়াম একটি ডমিন্যান্ট স্ট্র্যাটেজি ইকুইলিব্রিয়াম নয়।

প্রথম অর্ধেক সহজ: যদি একটি কৌশল অন্য সবকিছুকে কঠোরভাবে ডমিনেট করে, তাহলে বিশেষভাবে এটি প্রতিটি একতরফা বিচ্যুতিকে কঠোরভাবে ডমিনেট করে। তাই একজন খেলোয়াড় যে ডমিন্যান্ট কৌশল খেলছে সে সুইচ করে উন্নতি করতে পারে না। সংজ্ঞা অনুযায়ী, এটি একটি ন্যাশ ইকুইলিব্রিয়াম।

দ্বিতীয় অর্ধেকের একটি উদাহরণ দরকার। ব্যাটল অফ দ্য সেক্সেসের (পরের অধ্যায়) দুটি বিশুদ্ধ ন্যাশ ইকুইলিব্রিয়াম আছে কিন্তু কোনো ডমিন্যান্ট স্ট্র্যাটেজি নেই। আমরা সেখানে পৌঁছে দেখব কেন।

কাজের উদাহরণ: একটি 3×2 গেমে সব ইকুইলিব্রিয়াম খোঁজা

ধরো নিম্নলিখিত পেওয়াফ ম্যাট্রিক্স আছে (A সারি বাছাই করে, B কলাম বাছাই করে):

ধাপ ১ — A-এর জন্য বেস্ট রেসপন্স। প্রতিটি কলামে B যা খেলে, A-এর বেস্ট সারি খোঁজো:

• B L খেলে → A-এর পেওয়াফ (3, 2, 0) → সেরা U।
• B R খেলে → A-এর পেওয়াফ (0, 1, 4) → সেরা D।

ধাপ ২ — B-এর জন্য বেস্ট রেসপন্স। প্রতিটি সারিতে A যা খেলে, B-এর বেস্ট কলাম খোঁজো:

• A U খেলে → B-এর পেওয়াফ (1, 0) → সেরা L।
• A M খেলে → B-এর পেওয়াফ (2, 3) → সেরা R।
• A D খেলে → B-এর পেওয়াফ (1, 2) → সেরা R।

ধাপ ৩ — ন্যাশ ইকুইলিব্রিয়াম। একটি ন্যাশ ইকুইলিব্রিয়াম এমন একটি ঘর যেখানে দুই খেলোয়াড়ই বেস্ট রেসপন্স করছে:

• (U, L): A বেস্ট রেসপন্স করছে (L-এর বিরুদ্ধে U সেরা)। B বেস্ট রেসপন্স করছে (U-এর বিরুদ্ধে L সেরা)। ✓ ন্যাশ ইকুইলিব্রিয়াম।
• (D, R): A বেস্ট রেসপন্স করছে (R-এর বিরুদ্ধে D সেরা)। B বেস্ট রেসপন্স করছে (D-এর বিরুদ্ধে R সেরা)। ✓ ন্যাশ ইকুইলিব্রিয়াম।

তাই দুটি বিশুদ্ধ-কৌশল ন্যাশ ইকুইলিব্রিয়াম আছে: (U, L) এবং (D, R)। কোনো কৌশলই কঠোরভাবে ডমিনেট করে না। তাই এই গেমের একাধিক ন্যাশ ইকুইলিব্রিয়াম আছে কিন্তু কোনো ডমিন্যান্ট স্ট্র্যাটেজি নেই। এটি পরবর্তী অধ্যায়ের জন্য চমৎকার সেগুয়ে: ব্যাটল অফ দ্য সেক্সেস ও প্রিজনার্স ডাইলেমা, যেগুলো এই ধরনের ঘটনার আদর্শ উদাহরণ।

সাধারণ ভুল

• "কোনো ডমিন্যান্ট স্ট্র্যাটেজি নেই" কে "কোনো ইকুইলিব্রিয়াম নেই" এর সাথে গুলিয়ে ফেলা। একটি গেমে সহজেই ন্যাশ ইকুইলিব্রিয়াম (এক বা একাধিক) থাকতে পারে কোনো ডমিন্যান্ট স্ট্র্যাটেজি ছাড়াই। ডমিন্যান্স একটি ছুরি, ন্যাশ একটি স্ক্যাল্পেল — ভিন্ন হাতিয়ার।
• পেওয়াফের ক্রম ভুলে যাওয়া। এই কোর্সের প্রথা হলো (খেলোয়াড় A, খেলোয়াড় B)। কিছু পাঠ্যবই এটি উল্টে দেয়। ইকুইলিব্রিয়াম গোনা শুরু করার আগে সবসময় চেক করো।
• ন্যাশ ইকুইলিব্রিয়াম খুঁজতে গিয়ে শুধু নিজের কৌশল চেক করা। দুই খেলোয়াড়কেই একসাথে বেস্ট রেসপন্স করতে হবে।
• পুনরাবৃত্ত ডমিন্যান্স ≠ ন্যাশ ইকুইলিব্রিয়াম। ডমিনেটেড কৌশল বাদ দিলে কিছু ন্যাশ ইকুইলিব্রিয়াম হারাতে পারো।

সারসংক্ষেপ

• একটি গেম-এ খেলোয়াড়, কৌশল, পেওয়াফ ও নিয়ম থাকে।
• একটি পেওয়াফ ম্যাট্রিক্স প্রতিটি কৌশল সমন্বয়ের পেওয়াফ তালিকাভুক্ত করে।
• একটি ডমিন্যান্ট স্ট্র্যাটেজি অন্যরা যাই করুক তাতে সেরা। প্রতিটি খেলোয়াড়ের এমন একটি থাকলে এবং সবাই সেটা খেললে সেটা DSE।
• একটি ন্যাশ ইকুইলিব্রিয়াম হলো এমন একটি কৌশল প্রোফাইল যেখানে কেউ একতরফাভাবে বিচ্যুত হয়ে উন্নতি করতে পারে না।
• প্রতিটি DSE একটি NE, কিন্তু প্রতিটি NE একটি DSE নয়।
• DSE পাওয়া যায় পুনরাবৃত্ত ডমিন্যান্স দ্বারা; NE পাওয়া যায় বেস্ট-রেসপন্স সম্পর্ক দ্বারা।

পরবর্তী কী?

এখন ভিত্তি তৈরি হয়েছে, পরবর্তী অধ্যায় এটিকে কাজে লাগায়। আমরা দুটি সবচেয়ে বিখ্যাত 2×2 গেম অধ্যয়ন করব: ব্যাটল অফ দ্য সেক্সেস, যেটিতে দুটি বিশুদ্ধ ন্যাশ ইকুইলিব্রিয়াম এবং কোনো ডমিন্যান্ট স্ট্র্যাটেজি নেই ("অনেক ইকুইলিব্রিয়াম" সমস্যার উদাহরণ), এবং প্রিজনার্স ডাইলেমা, যেটিতে একটিমাত্র ন্যাশ ইকুইলিব্রিয়াম আছে যা উভয় খেলোয়াড়ের জন্য কঠোরভাবে আরেকটি ফলাফলের চেয়ে খারাপ ("যুক্তিসঙ্গত খেলা কেন সম্মিলিতভাবে ভয়াবহ হতে পারে" তার উদাহরণ)।