10.6 — Perfect-information Games (পূর্ণ-তথ্য গেম)

এই অধ্যায়ে কী শিখব: এতদিন আমরা দেখেছি খেলোয়াড়েরা একসাথে (simultaneous) চাল দেয় — কেউ কারও চাল না জেনে। এবার আসছে ক্রমিক (sequential) খেলা, যেখানে একজন আগে চাল দেয় আর অন্যজন সেটা দেখে পরে সিদ্ধান্ত নেয়। যে ক্রমিক খেলায় চাল দেওয়ার সময় খেলোয়াড় আগের সব চাল জানে, তাকে বলে perfect-information game (পূর্ণ-তথ্য গেম) — দাবা, দাবার মতো। ধাপে ধাপে, একদম গোড়া থেকে শিখব: rooted directed tree (মূলযুক্ত দিকনির্দেশিত ট্রি) দিয়ে খেলা আঁকা; extensive form (বিস্তৃত রূপ) ও game-frame (গেম-ফ্রেম)-এর পার্থক্য এবং কীভাবে ranking যোগ করে frame-কে game বানানো হয়; backward induction (পশ্চাৎ-অনুমান) — শেষ থেকে শুরু করে খেলা সমাধানের অ্যালগরিদম; কেন কখনো একাধিক backward-induction solution থাকে; strategy (কৌশল)-এর সঠিক সংজ্ঞা (প্রতিটি decision node (সিদ্ধান্ত-নোড)-এ একটি করে চাল) এবং তার মধ্যকার redundancy; backward induction আর Nash equilibrium (ন্যাশ ভারসাম্য)-এর সম্পর্ক (উপপাদ্য ও প্রমাণসহ); incredible threat (অবিশ্বাসযোগ্য হুমকি) আর entry game; Selten-এর Chain-Store game ও reputation প্যারাডক্স; আর সবশেষে দুই-খেলোয়াড় win-lose ও তিন-ফলাফল (win/lose/draw) খেলার existence theorem — কে জিতবে তা আগেভাগেই কেন নির্ধারিত। প্রতিটা ধারণা ছবিসহ, সংখ্যাসহ, Python ও পূর্ণ সমাধানসহ এক্সারসাইজ দিয়ে।

উৎস (source): Game Theory — Giacomo Bonanno।

---

১. কেন শিখব? (Motivation)

Part 10-এর শুরুর দিকে খেলাগুলো ছিল একসাথে, একবার (simultaneous, one-shot) — Prisoner's Dilemma-তে দুই বন্দি আলাদা ঘরে বসে একই সাথে সিদ্ধান্ত নেয়, কেউ কারওটা জানে না। কিন্তু বাস্তবের বেশিরভাগ কৌশলগত পরিস্থিতি এমন নয়। দাবায় White আগে চাল দেয়, Black দেখে জবাব দেয়; দরকষাকষিতে একজন আগে দাম হাঁকে, অন্যজন শোনে; ব্যবসায় একটি firm আগে বাজারে ঢোকে, প্রতিযোগী দেখে প্রতিক্রিয়া দেখায়। এই ক্রমিক (sequential) খেলাগুলোকে বলে dynamic game (গতিশীল গেম) বা extensive-form game (বিস্তৃত-রূপ গেম)।

এই অধ্যায়ে আমরা dynamic game-এর একটা বিশেষ, সহজতম উপশ্রেণি নিয়ে কাজ করব — perfect information (পূর্ণ তথ্য) যেখানে যখনই কোনো খেলোয়াড়ের চাল দেওয়ার পালা, সে আগের সব চাল সম্পূর্ণ জানে। কোনো লুকানো তথ্য নেই, কোনো একসাথে-চাল নেই, কোনো এলোমেলো ঘটনা (dice/coin) নেই। দাবা, দাবা (checkers), tic-tac-toe — সবই এই শ্রেণির।

কেন এটা গুরুত্বপূর্ণ? কারণ ক্রমিকতা (sequencing) একটা নতুন, শক্তিশালী সমাধান-পদ্ধতি এনে দেয়: শেষ থেকে শুরু করে ভাবা। "যদি খেলা এই নোডে পৌঁছায়, তখন কে কী করবে?" — এই প্রশ্নের উত্তর গাছের প্রান্ত থেকে শুরু করে মূল পর্যন্ত পিছিয়ে আসতে আসতে গোটা খেলার সমাধান বেরিয়ে আসে। এটাই backward induction (পশ্চাৎ-অনুমান), এবং এটা এই অধ্যায়ের প্রাণ।

মূল স্বজ্ঞা

খেলা পড়তে হয় উপর থেকে নিচে (মূল থেকে প্রান্ত, ঘটনার ক্রম অনুসারে), কিন্তু সমাধান করতে হয় নিচ থেকে উপরে (প্রান্ত থেকে মূল)। যুক্তিটা সরল: সবচেয়ে শেষে যে চাল দেয়, তার সামনে আর কোনো অনিশ্চয়তা নেই — সে কেবল নিজের সবচেয়ে ভালো ফলটা বেছে নেবে। সেটা জানা হয়ে গেলে, তার আগের খেলোয়াড় নিশ্চিতভাবে জানে "আমি এটা করলে ও ওটা করবে" — তাই সে-ও নিজের সেরাটা বাছতে পারে। এভাবে অনিশ্চয়তা প্রান্ত থেকে মূলের দিকে গলে যায়। যে খেলোয়াড় শেষে চাল দেয়, সে-ই প্রথমে "সমাধান" হয়।

---

২. মূল ধারণা (Core idea)

এই অংশে আমরা Bonanno-র ধারা ধরে ধারণাগুলো একে একে গল্পে-ছবিতে বুঝব। আনুষ্ঠানিক সংজ্ঞা ও উপপাদ্য আসবে পরের অংশে (৩ নং)।

২.১ Trees, frames ও games — খেলা কীভাবে আঁকি

perfect-information game আঁকা হয় একটা গাছ (tree) দিয়ে। ভাবো একটা উল্টানো গাছ: উপরে একটা মূল (root), সেখান থেকে ডালপালা নিচে নামছে, প্রতিটা ডালের মাথায় হয় আরেকটা সিদ্ধান্ত-বিন্দু, নয়তো খেলার একটা সমাপ্তি। প্রতিটা নোড (node)-এ কোনো একজন খেলোয়াড় চাল দেয়; প্রতিটা প্রান্ত (edge) একটা action (ক্রিয়া); আর প্রতিটা terminal node (প্রান্ত-নোড)-এ খেলা শেষ হয়ে একটা outcome (ফলাফল) পাওয়া যায়।

Bonanno-র প্রথম উদাহরণ: Amy (Player 1) আর Beth (Player 2) একটা ব্যবসায়িক অংশীদারিত্ব ভাঙছে, যার সম্পদের মূল্য $100,000। নিয়ম অনুযায়ী জ্যেষ্ঠ অংশীদার Amy একটা ভাগের প্রস্তাব দেবে (হয় 50-50, নয় 70-30), তারপর কনিষ্ঠ Beth হয় Accept (মেনে নেওয়া) করবে, নয় Reject (প্রত্যাখ্যান) করবে। Reject করলে মামলা — প্রত্যেকের $20,000 আইনি খরচ, আর আদালত সম্পদের 60% জ্যেষ্ঠকে (Amy), 40% কনিষ্ঠকে (Beth) দেয়।

Figure 3.1 — Amy-Beth অংশীদারিত্ব-ভাঙার extensive-form game-frame (বিস্তৃত-রূপ গেম-ফ্রেম)। উপরের সংখ্যা Player 1 (Amy)-র প্রাপ্তি, নিচেরটা Player 2 (Beth)-র। প্রতিটি Reject-এ আদালতের ফল একই: Amy পায় 60% − $20,000 = $40,000, Beth পায় 40% − $20,000 = $20,000। তাই \(o_2\) ও \(o_4\) দুটোই মানে $40,000/$20,000।

লক্ষ করো — Figure 3.1-এ ফলাফলগুলো টাকার অঙ্কে দেওয়া, খেলোয়াড়দের পছন্দক্রম (ranking) দেওয়া নেই। তাই এটা এখনো একটা game (গেম) নয়, কেবল একটা game-frame (গেম-ফ্রেম)। কেন এই পার্থক্য জরুরি? কারণ বেশি টাকা মানেই বেশি সুখ — এটা সবসময় সত্য নয়। Beth হয়তো ন্যায্যতা নিয়ে এত সচেতন যে একটা অন্যায্য 70-30 প্রস্তাব পেলে সে $10,000 হারিয়েও Amy-কে "শিক্ষা দিতে" চাইবে — অর্থাৎ সে \(o_4\)-কে (reject, teach a lesson) \(o_3\)-এর (accept 70-30) ওপরে রাখতে পারে।

game-frame-কে game-এ পরিণত করতে প্রতিটি খেলোয়াড়ের জন্য একটা ranking (পছন্দক্রম) যোগ করতে হয়। ধরা যাক Player 1 স্বার্থপর ও লোভী (\(o_3 \succ_1 o_1 \succ_1 o_2 \sim_1 o_4\)), আর Player 2 ন্যায্যতা-সচেতন (\(o_1 \succ_2 o_2 \sim_2 o_4 \succ_2 o_3\))। ordinal utility-তে:

outcome	\(o_1\)	\(o_2\)	\(o_3\)	\(o_4\)
\(U_1\) (Player 1)	\(2\)	\(1\)	\(3\)	\(1\)
\(U_2\) (Player 2)	\(3\)	\(2\)	\(1\)	\(2\)

এবার প্রতিটি outcome-এর জায়গায় এই payoff-জোড়া বসিয়ে পাই একটা সত্যিকারের game (Figure 3.2)।

Figure 3.2 — Figure 3.1-এর frame-এর ওপর ভিত্তি করে একটা perfect-information game। double-করা প্রান্তগুলো backward-induction সমাধান দেখাচ্ছে। যুক্তি: 50-50 প্রস্তাবে Beth accept করবে (\(U_2 = 3 > 2\)); 70-30 প্রস্তাবে Beth reject করবে (\(2 > 1\))। এটা আগেভাগে বুঝে Amy 50-50 প্রস্তাব দেয় (\(U_1 = 2 > 1\)), Beth accept করে — ফল \(o_1 = (2,3)\)।

খেয়াল করো — স্বজ্ঞামূলকভাবে "লোভী Amy" 70-30 চাইবে বলে মনে হয়, কিন্তু ন্যায্যতা-সচেতন Beth সেটা reject করবে জেনে Amy বাধ্য হয়ে 50-50 দেয়। প্রতিপক্ষের ranking না জানলে সঠিক ভবিষ্যদ্বাণী অসম্ভব — এটাই game আর game-frame-এর পার্থক্যের মূল শিক্ষা।

২.২ Backward induction — শেষ থেকে সমাধান

উপরের যুক্তিটাকেই আনুষ্ঠানিক algorithm (অ্যালগরিদম)-এ রূপ দেওয়া যায়। ধারণাটা: একটা নোডকে "marked" বলি যদি তাতে একটা payoff-vector বসানো থাকে। শুরুতে কেবল terminal node-গুলো marked (তাদের payoff তো জানাই)। তারপর বারবার এমন একটা decision node বাছি যার সব immediate successor (তাৎক্ষণিক উত্তরসূরি) ইতিমধ্যে marked; সেই নোডের খেলোয়াড় তার নিজের payoff সর্বোচ্চ করে এমন উত্তরসূরি বাছে, আর সেই payoff-vector দিয়ে নোডটাকে mark করি। সব নোড marked না হওয়া পর্যন্ত চলে।

কিন্তু একটা সূক্ষ্ম ব্যাপার: কোনো নোডে একাধিক চাল যদি একই সর্বোচ্চ payoff দেয়, তাহলে অ্যালগরিদম যেকোনো একটা বাছতে বলে — আর এই স্বেচ্ছাচারী বাছাই একাধিক backward-induction solution তৈরি করতে পারে। Figure 3.3-এর তিন-খেলোয়াড় খেলা ঠিক এমন।

Figure 3.3 — একটা তিন-খেলোয়াড় খেলা যার একাধিক backward-induction solution আছে। Player 2-এর \(x\) নোডে \(c\) বাছাই হয় (Player 2-এর payoff \(1 > 0\)), তাই \(x\) marked হয় \((2,1,0)\)-তে। কিন্তু Player 3-এর নোডে \(g\) ও \(h\) দুটোই payoff-সর্বোচ্চ — এখান থেকেই দুটো সমাধান জন্ম নেয়।

Player 3-এর indifference-এর কারণে দুটো ভিন্ন পথে অ্যালগরিদম এগোতে পারে। Figure 3.4-এ \(g\) বেছে ধাপে ধাপে marking, Figure 3.5-এ \(h\) বেছে।

Figure 3.4 — Figure 3.3-এ backward-induction অ্যালগরিদমের একটা সম্ভাব্য ফলাফল (Player 3-এর নোডে \(g\) বাছাই)। STEP 1 → LAST STEP পর্যন্ত প্রতিটা নোড কীভাবে marked হয় দেখানো হয়েছে; বাছাই-করা প্রান্ত double-edge-এ।

Figure 3.5 — একই খেলার আরেকটা সম্ভাব্য ফলাফল (Player 3-এর নোডে \(h\) বাছাই)। দুই ফলাফলে Player 3-এর payoff একই থাকলেও অন্যদের চাল আলাদা হতে পারে — তাই দুটো ভিন্ন backward-induction solution।

২.৩ Strategies — সম্পূর্ণ, শর্তাধীন পরিকল্পনা

backward-induction solution আসলে কী জিনিস? এটা বোঝাতে দরকার strategy (কৌশল)-এর ধারণা। একটা strategy হলো খেলাটা কীভাবে খেলবে তার সম্পূর্ণ, শর্তাধীন (complete, contingent) পরিকল্পনা — প্রতিটি সম্ভাব্য পরিস্থিতির জন্য আগে থেকে ঠিক-করা জবাব।

Figure 3.6 — Figure 3.3-এর অনুলিপি, strategy-র ধারণা আলোচনার জন্য। খেলা শুরুর আগে Player 2 জানে না Player 1 কী করবে; তাই তার পরিকল্পনায় দুটোই থাকতে হবে — "Player 1 যদি \(a\) দেয় তবে আমি \(c\), আর \(b\) দিলে \(e\)" — সংক্ষেপে \((c,e)\)।

সংজ্ঞা: একটা strategy হলো ওই খেলোয়াড়ের প্রতিটি decision node-এর জন্য একটা করে চাল-এর তালিকা। কোনো খেলোয়াড়ের যদি তিনটে নোড থাকে যেখানে যথাক্রমে ৩, ২, ৪টা চাল, তবে তার মোট strategy সংখ্যা \(3 \times 2 \times 4 = 24\)।

এই সংজ্ঞায় একটা মজার redundancy (অপ্রয়োজনীয়তা) আছে: strategy সেই নোডের জন্যও চাল ঠিক করে যেখানে খেলা হয়তো কখনো পৌঁছাবেই না। নিচের নিজের-আঁকা ছবিতে ব্যাপারটা পরিষ্কার।

Figure (নিজের আঁকা) — একটা strategy খেলোয়াড়ের প্রতিটি decision node-এ চাল ঠিক করে। এখানে Player 1-এর দুটো নোড (root ও ডানের নোড)। strategy \((L, x)\) মানে root-এ \(L\) আর ডানের নোডে \(x\) — কিন্তু \(L\) খেললে ডানের নোডে কখনো পৌঁছানোই যায় না, তবু পরিকল্পনায় \(x\) থেকে যায়। এই "না-পৌঁছানো নোডের জন্যও পরিকল্পনা" — এটাই redundancy। যুক্তি: হয় খেলোয়াড় ভুল করে \(L\)-এর বদলে অন্যকিছু খেলতে পারে (সাবধানী পরিকল্পনা), নয়তো strategy আসলে অন্য খেলোয়াড়ের মনে "সে কী করত" সেই বিশ্বাস।

প্রতিটা strategy profile (সব খেলোয়াড়ের strategy একসাথে) একটা অনন্য terminal node-এ পৌঁছায়, তাই একটা অনন্য payoff-vector দেয়। এভাবে যেকোনো perfect-information game-এর সাথে একটা strategic-form game (কৌশল-রূপ গেম) জুড়ে দেওয়া যায়। Figure 3.7-এর খেলার strategic form হলো Figure 3.8।

Figure 3.7 — একটা perfect-information game। এখানে Player 1 দুবার চাল দিতে পারে (root-এ \(a/b\), আরেক নোডে \(g/h\)); Player 2-এর দুটো নোড (\(c/d\) ও \(e/f\))। তাই Player 1-এর strategy দুই অক্ষরের (\(ag, ah, bg, bh\)), Player 2-এরও (\(ce, cf, de, df\))।

Figure 3.8 — Figure 3.7-এর strategic form, পাঁচটি Nash equilibrium চিহ্নিত। redundancy-র কারণে উপরের দুই সারি অভিন্ন (কারণ Player 1 \(a\) খেললে \(g\) না \(h\) তাতে ফল বদলায় না)।

এবার backward-induction solution-এর অর্থ পরিষ্কার: অ্যালগরিদম প্রতিটি decision node-এ একটা চাল বাছে, তাই এটা গোটা খেলার জন্য একটা strategy profile দেয়।

Figure 3.9 — Figure 3.7-এর দুটো backward-induction solution। Panel (a): strategy profile \(((a,g),(c,f))\), যার backward-induction outcome হলো খেলা \(ac\), payoff \((2,1)\)। Panel (b): \(((b,h),(c,e))\), outcome \(be\), payoff \((3,1)\)। দুটোই strategic form-এর Nash equilibrium — কিন্তু Figure 3.8-এর পাঁচটা Nash equilibrium-এর সবগুলো backward-induction solution নয়।

solution বনাম outcome

backward-induction solution হলো একটা পুরো strategy profile (কে কোন নোডে কী করবে — না-পৌঁছানো নোডসহ)। আর backward-induction outcome হলো শুধু আসল চালগুলোর ক্রম (actual play)। যেমন \(((a,g),(c,f))\) solution-এর outcome হলো \(ac\), payoff \((2,1)\)।

২.৪ Backward induction বনাম Nash equilibrium — অবিশ্বাসযোগ্য হুমকি

আগের অধ্যায়ের সব খেলায় দেখা গেছে backward-induction solution সবসময় একটা Nash equilibrium-ও বটে — এটা সাধারণ সত্য (উপপাদ্য ৩ নং অংশে)। কিন্তু উল্টোটা নয়: সব Nash equilibrium backward-induction solution নয়। যেসব Nash equilibrium backward induction-এ টেকে না, সেগুলো প্রায়ই একটা incredible threat (অবিশ্বাসযোগ্য হুমকি)-র ওপর দাঁড়িয়ে থাকে।

ধ্রুপদী উদাহরণ — entry game (প্রবেশ-খেলা)। একটা শিল্পে একচেটিয়া incumbent $5 million মুনাফা করছে। এক সম্ভাব্য entrant ভাবছে ঢুকবে কি না।

• না ঢুকলে (Out) সে বিকল্প বিনিয়োগে $1 million পায়, incumbent একচেটিয়া $5 million রাখে।
• ঢুকলে (In) incumbent দুই পথ: Fight (মূল্যযুদ্ধ) — দুজনেরই $0; নয়তো Accommodate (বাজার ভাগ) — দুজনেই $2 million।

Figure 3.10 — entry game ও তার strategic form। backward-induction solution হলো \((\text{in},\ \text{accommodate})\), যা একটা Nash equilibrium-ও। কিন্তু আরেকটা Nash equilibrium আছে — \((\text{out},\ \text{fight})\) — যেটা "রাজি হও নাহলে যুদ্ধ করব" এই অবিশ্বাসযোগ্য হুমকির ওপর দাঁড়িয়ে।

খেলাটা payoff matrix-এও লেখা যায় (প্রথম সংখ্যা entrant, দ্বিতীয় incumbent):

	Incumbent: Fight	Incumbent: Accommodate
Entrant: Out	\((1,\ 5)\)	\((1,\ 5)\)
Entrant: In	\((0,\ 0)\)	\((2,\ 2)\)

কেন \((\text{out}, \text{fight})\)-কে বাতিল করা উচিত? কারণ entrant-এর বোঝা উচিত — সে সত্যিই ঢুকে পড়লে (fait accompli), incumbent-এর কাছে Fight (\(\$0\)) বনাম Accommodate (\(\$2M\)) — যুক্তিবাদী incumbent তখন Accommodate-ই বাছবে। তাই "Fight করব" হুমকিটা ফাঁপা; entrant-এর নির্ভয়ে ঢোকা উচিত। backward induction ঠিক এই ফাঁপা হুমকিকে ছেঁটে ফেলে।

এই যুক্তির একটা বিখ্যাত সম্প্রসারণ Reinhard Selten-এর Chain-Store game (তিনি ১৯৯৪-এ Nash ও Harsanyi-র সঙ্গে অর্থনীতিতে Nobel পান)। একটা chain store \(m\)টি শহরে একচেটিয়া; প্রতিটি শহরে একজন সম্ভাব্য entrant। স্বজ্ঞা বলে, প্রথম শহরে কঠোরভাবে Fight করে incumbent "reputation" গড়ে পরের entrant-দের ভয় দেখাতে পারে। backward induction কি এই স্বজ্ঞা ধরে? \(m=2\) ক্ষেত্রে খেলাটা আঁকা যায়:

Figure 3.11 — Selten-এর Chain-Store game (\(m=2\))। প্রতিটি terminal node-এ উপরের সংখ্যা incumbent-এর মোট মুনাফা (দুই শহরের যোগফল), মাঝেরটা Businesswoman 1-এর, নিচেরটা Businesswoman 2-এর — সবই million ডলারে। অনন্য backward-induction solution: দুই businesswoman-ই ঢোকে, incumbent দুই শহরেই accommodate করে।**

কেন reputation যুক্তি টেকে না? কারণ যা-ই ঘটুক, শহর ২-এর খেলা হলো শেষ খেলা — সেখানে কেউ আর তাকিয়ে নেই, তাই reputation গড়ার কোনো মানে নেই; incumbent তখন এক-শটের entry game-ই খেলছে, যেখানে accommodate-ই সেরা। এটা জেনে Businesswoman 2 যা-ই আগে ঘটুক ঢুকবে; তাই শহর ১-এ Fight করেও incumbent-এর কোনো লাভ নেই। reputation ধরতে হলে খেলোয়াড়দের মনে অনিশ্চয়তা থাকতে হবে — কিন্তু perfect-information game-এ অনিশ্চয়তা সংজ্ঞা-বলেই নিষিদ্ধ (সেটা পরের অধ্যায়ের বিষয়)।

২.৫ দুই-খেলোয়াড় খেলা — কে জিতবে তা কি আগেই ঠিক?

অধ্যায়ের শেষে একটা সুন্দর শ্রেণি: দুই-খেলোয়াড় খেলা যেখানে ফল কেবল "Player 1 জেতে" (\(W_1\)) বা "Player 2 জেতে" (\(W_2\))। এদের বলে win-lose game (জয়-পরাজয় খেলা)।

উদাহরণ: দুই খেলোয়াড় পালা করে \(\{1, 2, \dots, 10\}\) থেকে একটা সংখ্যা বাছে (Player 1 আগে)। যে প্রথম যোগফলকে \(100\) বা তার বেশি করে, সে জেতে। গাছ আঁকা অসম্ভব (প্রথম ৪ চালেই ১০,০০০ নোড!), কিন্তু backward induction-এর যুক্তি খাটে: কোন যোগফল একটা "হারা অবস্থান"? যে \(89\)-এ চাল দিতে বাধ্য, সে \(90\) থেকে \(99\)-এর মধ্যে যেতে বাধ্য (১০০-তে পৌঁছায় না), আর তখন প্রতিপক্ষ ঠিক \(100\)-এ পৌঁছে জেতে। তাই \(89\) একটা হারা অবস্থান; পিছিয়ে গেলে \(78, 67, 56, 45, 34, 23, 12, 1\) — সবই \(11\)-এর ব্যবধানে।

Figure (নিজের আঁকা) — sum-to-100 win-lose খেলার "হারা অবস্থান"গুলো লাল বিন্দুতে (\(1, 12, 23, \dots, 89\), সবই \(11\)-এর গুণিতক \(+1\))। যে খেলোয়াড় লাল অবস্থানে চাল দিতে বাধ্য, সঠিক খেলায় সে হারে: সে যোগফলকে পরের \(1\)–\(10\)-এ নিতে বাধ্য, আর প্রতিপক্ষ ঠিক \(+11\) ব্যবধান পুনরুদ্ধার করে। Player 1 প্রথমেই \(1\) বেছে Player 2-কে প্রথম হারা অবস্থানে ফেলে — তাই এখানে Player 1-এরই winning strategy আছে: শুরুতে \(1\), তারপর প্রতিবার প্রতিপক্ষের \(n\)-এর জবাবে \((11-n)\)।

এই খেলায় Player 1 সবসময় জেতে — তার একটা winning strategy (জয়ের কৌশল) আছে যা Player 2 যা-ই করুক জয় নিশ্চিত করে। এটা কাকতালীয় নয়; এটা একটা সাধারণ উপপাদ্যের ফল (৩ নং অংশে): প্রতিটি সসীম দুই-খেলোয়াড় win-lose perfect-information খেলায় কোনো-না-কোনো একজনের winning strategy থাকে। অর্থাৎ কে জিতবে তা খেলা শুরুর আগেই তাত্ত্বিকভাবে নির্ধারিত — যদিও সেই strategy বের করা কঠিন হতে পারে।

তিন-ফলাফল (win/lose/draw) খেলায় — যেমন tic-tac-toe, checkers, chess — একই ধারার একটা উপপাদ্য বলে খেলাটা তিন শ্রেণির একটায় পড়ে: (১) Player 1 জয় নিশ্চিত করতে পারে, (২) Player 2 জয় নিশ্চিত করতে পারে, বা (৩) দুজনেই অন্তত ড্র নিশ্চিত করতে পারে (তাই সঠিক খেলায় ড্র)। tic-tac-toe ও checkers তৃতীয় শ্রেণির (ড্র); chess কোন শ্রেণির — আজও অজানা।

---

৩. সংজ্ঞা ও উপপাদ্য (Definitions and theorems)

এবার আনুষ্ঠানিক ভিত্তি। প্রতীক: নোডের সেট \(X\), decision node-এর সেট \(D\), terminal node-এর সেট \(Z\), যেখানে \(X = D \cup Z\)।

সংজ্ঞা ৩.১.১ (rooted directed tree — মূলযুক্ত দিকনির্দেশিত ট্রি)

একটা rooted directed tree হলো কিছু নোড ও তাদের যোগকারী দিকনির্দেশিত প্রান্তের সমাহার, যেখানে:

• root (মূল)-এ কোনো প্রান্ত ঢোকে না (indegree \(0\)); অন্য প্রতিটি নোডে ঠিক একটা প্রান্ত ঢোকে (indegree \(1\))।
• root থেকে অন্য যেকোনো নোডে একটাই পথ (প্রান্তের অনন্য ক্রম) যায়।
• যে নোড থেকে কোনো প্রান্ত বের হয় না (outdegree \(0\)) সেটা terminal node; বাকি প্রতিটি decision node।

সংজ্ঞা ৩.১.২ (finite extensive form with perfect information)

একটা সসীম extensive-form game-frame with perfect information চারটি উপাদান নিয়ে:

1. একটা সসীম rooted directed tree।
2. খেলোয়াড়-সেট \(I = \{1, \dots, n\}\) এবং প্রতিটি decision node-এ একজন খেলোয়াড় বসানোর একটা ফাংশন।
3. একটা action-সেট \(A\) এবং প্রতিটি প্রান্তে একটা action বসানোর ফাংশন, এই শর্তে যে একই নোড থেকে বেরোনো দুটি প্রান্তে কখনো একই action নয়।
4. একটা outcome-সেট \(O\) এবং প্রতিটি terminal node-এ একটা outcome বসানোর ফাংশন।

সংজ্ঞা ৩.১.৩ (finite extensive game with perfect information)

একটা সসীম extensive game with perfect information হলো উপরের একটা frame এবং প্রতিটি খেলোয়াড় \(i \in I\)-এর জন্য outcome-সেট \(O\)-এর ওপর একটা ranking \(\succsim_i\)। সচরাচর এই ranking-কে একটা ordinal utility function \(U_i : O \to \mathbb{R}\) দিয়ে উপস্থাপন করা হয়।

সংজ্ঞা ৩.২.১ (backward-induction algorithm — পশ্চাৎ-অনুমান অ্যালগরিদম)

একটা সসীম perfect-information game স্থির করো। একটা নোডকে marked বলি যদি তাতে একটা utility-vector যুক্ত থাকে। শুরুতে কেবল ও কেবলমাত্র terminal node-গুলো marked। এরপর:

1. এমন একটা decision node \(x\) বাছো যার সব immediate successor marked। ধরো \(x\)-এ খেলোয়াড় \(i\) চাল দেয়। এমন একটা চাল বাছো যা \(x\)-এর immediate successor-দের মধ্যে \(i\)-এর জন্য সর্বোচ্চ utility-বিশিষ্ট নোডে নিয়ে যায়। বাছাই-করা চালের পরের নোডের utility-vector দিয়ে \(x\)-কে mark করো।
2. সব নোড marked না হওয়া পর্যন্ত ধাপ ১ চালিয়ে যাও।

খেলা সসীম বলে অ্যালগরিদম সুসংজ্ঞায়িত। কোনো নোডে একাধিক চাল সর্বোচ্চ payoff দিলে যেকোনো একটা বাছতে হয় — এই স্বেচ্ছাচারিতা থেকেই একাধিক backward-induction solution আসতে পারে।

একটা strategy profile \(s\) একটা অনন্য play (root থেকে একটা terminal node পর্যন্ত পথ) নির্ধারণ করে, তাই একটা অনন্য payoff দেয়; খেলোয়াড় \(i\)-এর payoff লিখি \(\pi_i(s)\)। অ্যালগরিদম যেহেতু প্রতিটি decision node-এ একটা চাল বাছে, backward-induction solution হলো একটা সম্পূর্ণ strategy profile।

সংজ্ঞা ৩.৩.১ (strategy — কৌশল)

perfect-information game-এ একজন খেলোয়াড়ের strategy হলো তার প্রতিটি decision node-এর জন্য একটা করে চাল-এর তালিকা। তাই খেলোয়াড় \(i\)-এর মোট strategy-সংখ্যা = তার প্রতিটি decision node-এর চাল-সংখ্যার গুণফল।

এখন মূল সম্পর্ক-উপপাদ্য।

উপপাদ্য ৩.৪.১ (backward induction \(\Rightarrow\) Nash equilibrium)

প্রতিটি perfect-information game-এর প্রতিটি backward-induction solution সংশ্লিষ্ট strategic form-এর একটা Nash equilibrium।

প্রমাণ। সহজ ক্ষেত্রটা আগে দেখি: ধরো খেলাটা এমন যে যেকোনো play বরাবর প্রতিটি খেলোয়াড় সর্বোচ্চ একবার চাল দেয় (যেমন Selten-এর Chain-Store game)। ধরো \(s^*\) একটা backward-induction solution; যেকোনো খেলোয়াড় \(i\) ও তার যেকোনো strategy \(s_i \neq s^*_i\) নাও। আমাদের দেখাতে হবে

\[ \pi_i(s^*_i, s^*_{-i}) \ge \pi_i(s_i, s^*_{-i}). \]

দুটো ক্ষেত্র। যদি \(s_i\) কেবল সেসব নোডে \(s^*_i\) থেকে আলাদা যেগুলো \(s^*\)-এর তৈরি play-এ পৌঁছানো যায় না, তাহলে \(i\)-এর \(s_i\)-তে বদল play বদলায় না — একই terminal node, তাই \(\pi_i(s_i, s^*_{-i}) = \pi_i(s^*_i, s^*_{-i})\)। এখন ধরো \(s^*\)-এর play-এ \(i\)-এর একটা decision node আছে যেখানে \(s^*_i\) বাছে \(a\) আর \(s_i\) বাছে \(b \neq a\)। যেহেতু প্রতিটি খেলোয়াড় ওই play বরাবর সর্বোচ্চ একবার চাল দেয়, এই একটামাত্র বিচ্যুতিই play বদলায়। যদি \(a\) থেকে \(b\)-তে সরে \(i\)-এর payoff বাড়ত, তবে backward-induction অ্যালগরিদম ওই নোডে \(a\) বাছতই না (\(b\) বেশি payoff দিত, তাই \(b\) বাছা হতো)। তাই সরে গিয়ে payoff বাড়ানো অসম্ভব — অসমতাটা সত্য।

সাধারণ ক্ষেত্রে (\(i\) একই play বরাবর একাধিকবার চাল দিতে পারে) একই যুক্তি ধাপে ধাপে প্রয়োগ করি। \(s_i\) ও \(s^*_i\) যেসব নোডে play-এ আলাদা, তাদের মধ্যে প্রথমটা (\(x_1\)) থেকে শুরু করে একটা মধ্যবর্তী strategy \(s^1_i\) বানাই যা \(x_1\) পর্যন্ত \(s_i\)-এর মতো, তারপর \(s^*_i\)-এর মতো; অ্যালগরিদম \(x_1\)-এ \(s^*_i\)-এর চাল বেছেছিল বলে

\[ \pi_i(s^*_i, s^*_{-i}) \ge \pi_i(s^1_i, s^*_{-i}). \]

এভাবে পরের বিচ্যুতি-নোডে \(s^2_i\), তারপর \(s^3_i, \dots\) বানাতে থাকি, প্রতিবার একটা অসমতা পাই। খেলা সসীম বলে সসীম ধাপে \(s^m_i\)-এ পৌঁছাই যা \(s_i\)-এর মতোই একই play দেয়, এবং

\[ \pi_i(s^*_i, s^*_{-i}) \ge \pi_i(s^1_i, s^*_{-i}) \ge \cdots \ge \pi_i(s^m_i, s^*_{-i}) = \pi_i(s_i, s^*_{-i}). \]

তাই মূল অসমতা প্রতিষ্ঠিত। যেহেতু \(i\) ও \(s_i\) যেকোনো, \(s^*\) একটা Nash equilibrium। \(\square\)

উপপাদ্য ৩.৫.১ (win-lose খেলায় winning strategy-র অস্তিত্ব)

প্রতিটি সসীম দুই-খেলোয়াড় win-lose perfect-information খেলায় দুই খেলোয়াড়ের কোনো-না-কোনো একজনের একটা winning strategy থাকে।

প্রমাণ (রূপরেখা)। \(W_1\)-এ payoff-vector \((1,0)\) আর \(W_2\)-এ \((0,1)\) বসাই (Player 1 চায় \(1\), Player 2 চায় \(1\))। backward-induction অ্যালগরিদম চালিয়ে প্রতিটি decision node-এ হয় \((1,0)\) নয় \((0,1)\) বসে। root-এর immediate successor-দের marking দেখো — দুটো ক্ষেত্র।

• ক্ষেত্র ১: অন্তত একটা immediate successor \((1,0)\) পেয়েছে। তখন Player 1-এর winning strategy আছে: প্রথম চালে এমন একটা \((1,0)\)-নোডে যাও, তারপর প্রতিবার কেবল \((1,0)\)-নোডে থাকো (backward induction নিশ্চিত করে এটা সম্ভব)।
• ক্ষেত্র ২: root-এর সব immediate successor \((0,1)\)। তখন Player 2-ই যেখানেই খেলা যাক জয় নিশ্চিত করতে পারে।

দুই ক্ষেত্রেই কোনো-না-কোনো একজনের winning strategy আছে। \(\square\)

উপপাদ্য ৩.৫.২ (তিন-ফলাফল খেলা: win/lose/draw)

প্রতিটি সসীম দুই-খেলোয়াড় perfect-information খেলা যার তিনটি ফলাফল \(W_1, W_2, D\) এবং পছন্দক্রম \(W_1 \succ_1 D \succ_1 W_2\) ও \(W_2 \succ_2 D \succ_2 W_1\), নিচের তিন শ্রেণির একটায় পড়ে:

1. Player 1-এর একটা strategy আছে যা \(W_1\) নিশ্চিত করে।
2. Player 2-এর একটা strategy আছে যা \(W_2\) নিশ্চিত করে।
3. Player 1 নিশ্চিত করতে পারে ফল \(W_1\) বা \(D\), এবং Player 2 নিশ্চিত করতে পারে ফল \(W_2\) বা \(D\) — তাই দুজনে এই strategy খেললে ফল \(D\)।

প্রমাণ (রূপরেখা)। \(W_1, W_2, D\)-তে যথাক্রমে \((2,0), (0,2), (1,1)\) বসিয়ে backward induction চালাও। root-এর immediate successor-দের marking দেখো: (ক) কোনোটা \((2,0)\) হলে Player 1 জেতে; (খ) সব \((0,2)\) হলে Player 2 জেতে; (গ) অন্তত একটা \((1,1)\) এবং বাকিরা \((1,1)\) বা \((0,2)\) হলে তৃতীয় শ্রেণি (ড্র)। tic-tac-toe ও checkers তৃতীয় শ্রেণির; chess-এর শ্রেণি অজানা। \(\square\)

---

৪. উদাহরণ ও Analogy — backward induction ধাপে ধাপে

তত্ত্বকে হাতে-কলমে দেখি একটা সরল দুই-খেলোয়াড় গাছে। Player 1 root-এ চাল দেয় (\(L\) বা \(R\)); দুই দিকেই Player 2 চাল দেয় (\(L\)-এর পর \(a/b\), \(R\)-এর পর \(c/d\))। payoff-জোড়া (Player 1, Player 2):

• \(L\) তারপর \(a \to (3, 1)\), \(\quad L\) তারপর \(b \to (1, 2)\)
• \(R\) তারপর \(c \to (2, 0)\), \(\quad R\) তারপর \(d \to (0, 3)\)

Figure (নিজের আঁকা) — একটা সরল perfect-information গাছে backward induction তিন ধাপে। Step 0: খেলা। Step 1: Player 2-এর দুই নোড সমাধান — বাঁয়ে \(b\) (\(2 > 1\)), ডানে \(d\) (\(3 > 0\)); নোড দুটো marked \((1,2)\) ও \((0,3)\)-তে। Step 2: root সমাধান — Player 1-এর কাছে \(L \to 1\) বনাম \(R \to 0\), তাই \(L\)। backward-induction solution: Player 1 খেলে \(L\); Player 2 খেলে \(b\) (বাঁয়ে) ও \(d\) (ডানে)। outcome: play "\(L\) তারপর \(b\)", payoff \((1,2)\)।

ধাপে ধাপে যুক্তি:

1. সবচেয়ে নিচ থেকে শুরু। Player 2-এর বাঁ নোডে: \(a\) দিলে সে পায় \(1\), \(b\) দিলে \(2\)। যুক্তিবাদী Player 2 বাছে \(b\)। তাই এই নোড "আসলে" মানে payoff \((1, 2)\)।
2. Player 2-এর ডান নোডে: \(c\) দিলে \(0\), \(d\) দিলে \(3\)। সে বাছে \(d\)। এই নোড মানে \((0, 3)\)।
3. এবার root। Player 1 জানে বাঁয়ে গেলে সে পাবে \(1\) (কারণ Player 2 \(b\) দেবে), ডানে গেলে \(0\) (কারণ Player 2 \(d\) দেবে)। \(1 > 0\), তাই Player 1 বাছে \(L\)।

analogy — দাবার শেষ কয়েক চাল। একজন ভালো দাবাড়ু শেষ চাল থেকে হিসাব করে: "যদি আমি এখানে কিস্তি দিই, ও কেবল এই ঘরে রাজা সরাতে পারবে, তারপর আমি এই চাল দেব..." — অর্থাৎ সে গাছের প্রান্ত থেকে পিছিয়ে এসে বর্তমান চাল ঠিক করে। backward induction ঠিক এই স্বজ্ঞাটাকেই যান্ত্রিক করে তোলে। খেয়াল করো একটা সূক্ষ্ম শিক্ষা: এখানে Player 1 সর্বোচ্চ \(3\) পেতে পারত (\(L\) তারপর \(a\)), কিন্তু Player 2 কখনো \(a\) দেবে না (তার \(2 > 1\))। প্রতিপক্ষের স্বার্থ হিসাব না করে "আমি সর্বোচ্চ কোথায় পাই" ভাবলেই ভুল।

---

৫. Python-এ করো — recursive backward induction

গাছটাকে nested dictionary দিয়ে উপস্থাপন করে backward induction-কে সরাসরি recursion-এ লেখা যায়। terminal node-এ payoff থাকে; decision node-এ কে চাল দেয় ও কোন action কোন সন্তানে যায় তা থাকে।

# পূর্ণ-তথ্য গেমে backward induction -- recursive বাস্তবায়ন।
# node দুই ধরনের:
#   terminal : {"payoff": (u1, u2, ...)}          -- payoff vector
#   decision : {"player": i, "children": {act: subnode, ...}}
# খেলোয়াড় index 0 থেকে (Player 1 = 0, Player 2 = 1, ...)।

def solve(node, name="root", strategy=None):
    """প্রতিটি node-এর BI payoff-vector ফেরত দেয়, আর
    strategy dict-এ প্রতিটি decision node-এ বাছাই-করা চাল ভরে।"""
    if strategy is None:
        strategy = {}
    if "payoff" in node:                 # terminal হলে সরাসরি payoff
        return node["payoff"], strategy
    i = node["player"]                   # এই node-এ কে চাল দেয়
    best_action, best_payoff = None, None
    for action, child in node["children"].items():
        payoff, strategy = solve(child, f"{name}-{action}", strategy)  # সন্তান recursively
        # খেলোয়াড় i নিজের payoff (index i) সর্বোচ্চ করে এমন action বাছে
        if best_payoff is None or payoff[i] > best_payoff[i]:
            best_action, best_payoff = action, payoff
    strategy[name] = (f"Player {i + 1}", best_action)   # এই node-এ BI চাল
    return best_payoff, strategy


# ৪ নং অংশের গাছ: Player 1 root-এ L/R; Player 2 দুই দিকে a/b ও c/d
game = {
    "player": 0,                                     # Player 1
    "children": {
        "L": {"player": 1, "children": {             # Player 2 (বাঁ নোড)
            "a": {"payoff": (3, 1)},
            "b": {"payoff": (1, 2)},
        }},
        "R": {"player": 1, "children": {             # Player 2 (ডান নোড)
            "c": {"payoff": (2, 0)},
            "d": {"payoff": (0, 3)},
        }},
    },
}

payoff, strategy = solve(game)
print("BI outcome payoff:", payoff)                  # (1, 2)
for node_name, (who, act) in strategy.items():
    print(f"  {node_name:10s}: {who} plays {act}")
# আউটপুট:
# BI outcome payoff: (1, 2)
#   root-L    : Player 2 plays b     <- বাঁ নোডে b (2 > 1)
#   root-R    : Player 2 plays d     <- ডান নোডে d (3 > 0)
#   root      : Player 1 plays L     <- root-এ L (1 > 0)

আউটপুট ঠিক আমাদের হাতে-কলমে করা সমাধানের সাথে মেলে: Player 1 খেলে \(L\); Player 2-এর সম্পূর্ণ strategy হলো \((b, d)\) — অর্থাৎ backward-induction solution হলো strategy profile \(\big(L,\ (b, d)\big)\), outcome payoff \((1, 2)\)। খেয়াল করো recursion নিচ থেকে উপরে কাজ করে: সন্তান-নোড আগে সমাধান হয়, তারপর মূল — ঠিক backward induction-এর মতো।

---

৬. সাধারণ ভুল (Common mistakes)

1. উপর থেকে সমাধান করা। perfect-information game পড়া হয় উপর থেকে নিচে, কিন্তু সমাধান নিচ থেকে উপরে। "প্রথম খেলোয়াড় প্রথমে কী চায়" ভেবে শুরু করলে ভুল; শেষ চাল আগে ঠিক করো।
2. প্রতিপক্ষের payoff উপেক্ষা করা। "আমি কোথায় সর্বোচ্চ পাই" ভাবা যথেষ্ট নয়; ওই terminal-এ পৌঁছাতে প্রতিপক্ষকে এমন চাল দিতে হবে যা তার নিজের স্বার্থবিরোধী — সে দেবে না। (৪ নং অংশে Player 1-এর \(3\) অধরা থাকে ঠিক এ কারণেই।)
3. game আর game-frame গুলিয়ে ফেলা। payoff = টাকা ধরে নেওয়া ভুল। frame-এ কেবল ফলাফল; ranking (utility) যোগ করলে তবেই game। ভিন্ন ranking-এ backward-induction ফল পুরো উল্টে যেতে পারে (Amy-Beth)।
4. strategy আর action গুলিয়ে ফেলা। strategy হলো প্রতিটি decision node-এর জন্য পরিকল্পনা — এমন নোডসহ যেখানে খেলা হয়তো পৌঁছাবেই না। তাই "Player 1 \(a\) খেলবে" একটা action; "\(a\) root-এ, \(g\) অন্য নোডে" একটা strategy।
5. backward-induction solution = outcome ভাবা। solution একটা পুরো strategy profile; outcome কেবল আসল চালগুলোর ক্রম। একই outcome-এর পেছনে একাধিক solution থাকতে পারে।
6. সব Nash equilibrium-কে "যুক্তিসংগত" ভাবা। entry game-এ \((\text{out}, \text{fight})\) একটা Nash equilibrium, কিন্তু এটা একটা incredible threat-এর ওপর দাঁড়িয়ে — backward induction এটা ছেঁটে ফেলে। Nash equilibrium ⊋ backward-induction solution।
7. একাধিক BI solution "থাকতে পারে না" ধরে নেওয়া। কোনো নোডে খেলোয়াড় দুই চালে indifferent হলে একাধিক solution জন্মায় (Figure 3.3–3.5, Cournot Ex, ইত্যাদি)।
8. win-lose উপপাদ্যকে "কে জিতবে সহজে বলা যায়" ভাবা। উপপাদ্য শুধু বলে winning strategy আছে; সেটা কী বা কার, তা বের করা (যেমন chess) ভয়ানক কঠিন হতে পারে।

---

৭. এক্সারসাইজ (Exercises)

নিচের ৮টা Bonanno-র মূল এক্সারসাইজ (কিছু জোড়া-বাঁধা) ও ২টা নিজের — মোট ১০টা। পূর্ণ সমাধান পরের অংশে।

১। (Bonanno 3.1 — tortoise-napper) কেউ তোমার প্রিয় কচ্ছপ Speedy-কে অপহরণ করেছে, $1,000 চাইছে, না দিলে মারবে। ফলাফল: \(o_1\) (না-দিয়ে Speedy মুক্ত), \(o_2\) (দিয়ে মুক্ত), \(o_3\) (না-দিয়ে Speedy নিহত), \(o_4\) (দিয়ে নিহত)। তোমার ranking: \(o_1 \succ o_2 \succ o_3 \succ o_4\)। (a) Mr T বলল সে দুই মাইল দূরে একই সময়ে আলাদাভাবে Speedy ছাড়বে কি না ঠিক করবে — তুমি কী করবে? (b) এবার Mr T আগে টাকা তুলে তারপর ছাড়বে/মারবে ঠিক করবে — extensive-form game-frame আঁকো। (c) দুই ধরনের Mr T-র (professional ও one-timer) জন্য দুটো game বানাও।

২। (Bonanno 3.2 — promotion board) তিন-সদস্যের বোর্ড (A, B, C) এক কর্মকর্তার ভাগ্য ঠিক করবে: PROMOTE, KEEP, নাকি FIRE। পছন্দ:

	PROMOTE	KEEP	FIRE
A	best (\(3\))	middle (\(2\))	worst (\(1\))
B	worst (\(1\))	best (\(3\))	middle (\(2\))
C	middle (\(2\))	worst (\(1\))	best (\(3\))

ভোট-পদ্ধতি: প্রথমে A একটা প্রস্তাব দেয়; B রাজি হলে সেটাই চূড়ান্ত; B রাজি না হলে C যেকোনো একটা (তিনটার) চূড়ান্ত করে। \(\{1,2,3\}\) utility দিয়ে extensive-form game-এ প্রকাশ করো।

৩। (Bonanno 3.3 + 3.4 — apply backward induction) এক্সারসাইজ ১(c)-এর দুটো game (professional ও one-timer Mr T) এবং এক্সারসাইজ ২-এর promotion game-এ backward-induction অ্যালগরিদম প্রয়োগ করো। প্রতিটিতে সমাধান কী?

৪। (Bonanno 3.5 + 3.6 — strategic form ও Nash equilibria) (a) Figure 3.2-এর খেলার strategic form লেখো, সব Nash equilibrium বের করো, দেখাও backward-induction solution একটা Nash equilibrium। (b) একইভাবে Figure 3.3-এর খেলার জন্য করো।

৫। (Bonanno 3.7 + 3.8) (a) এক্সারসাইজ ২-এর promotion game-এ Player B-র সব strategy লেখো এবং Player C-র কতগুলো strategy আছে বলো। (b) নিচের Figure 3.12-এর খেলার জন্য: backward-induction solution বের করো; Player 1 ও Player 2-এর সব strategy লেখো; strategic form লেখো; কার dominant/dominated strategy আছে; IDWDS (iterated deletion of weakly dominated strategies) কী দেয়; আর সব Nash equilibrium কী।

Figure 3.12 — এক্সারসাইজ ৫(b)-র perfect-information game। Player 1-এর দুই নোড (\(L/R\) এবং \(W/E\)), Player 2-এর নোড (\(a/b\) এবং \(c/d/e\))।

৬। (Bonanno 3.9 — sequential Cournot duopoly) দুই firm একই পণ্য বানায়। মূল্য \(P = 130 - 10Q\) যেখানে \(Q = x + y\); খরচ \(C(q) = 10q + 62.5\)। প্রথমে Firm 1 তার উৎপাদন \(x\) ঠিক করে commit করে, তারপর Firm 2 তা দেখে \(y\) বাছে। ধরো \(x \in \{6, 6.5\}\) ও \(y \in \{2.5, 3\}\)। (a) extensive-form game-এ আঁকো; (b) backward induction-এ সমাধান করো; (c) strategic form লেখো; (d) Nash equilibrium বের করো ও যাচাই করো BI solution তাদের অন্তর্ভুক্ত। [মুনাফা: \(\Pi_1(x,y) = x[130 - 10(x+y)] - (10x + 62.5)\), একইভাবে \(\Pi_2\)।]

৭। (Bonanno 3.10 + 3.11) (a) নিচের Figure 3.13-এর খেলায় (\(x\) একটা পূর্ণসংখ্যা) প্রতিটি \(x\)-মানের জন্য backward-induction solution ও সব Nash equilibrium বের করো। (b) দুই খেলোয়াড় পালা করে \(\{1, \dots, 7\}\) থেকে সংখ্যা বাছে (Player 1 আগে); যে প্রথম যোগফল \(48\) বা বেশি করে সে জেতে। কার winning strategy আছে ও সেটা কী?

Figure 3.13 — এক্সারসাইজ ৭(a)-র খেলা, যেখানে একটা terminal payoff \(x\) একটা পূর্ণসংখ্যা।

৮। (Bonanno 3.12 + 3.13) (a) নিচের Figure 3.14-এর "coin game": একটা মুদ্রা A1 (START) ঘরে; খেলোয়াড়েরা পালা করে এক ঘর উপরে, বাঁয়ে, বা কোনাকুনি বাঁ-উপরে সরায় (কালো ঘর নিষিদ্ধ); যে END-এ পৌঁছায় সে জেতে। প্রথম দুই চাল কভার করে গাছের শুরুটা আঁকো; দেখাও G4 থেকে Player 1 জিততে পারে; A1 থেকে শুরু করে কার winning strategy আছে ও কী। (b) ⋆চ্যালেঞ্জ⋆ Anna ও Bess একটা আংটির দাবিদার; জজ Sabio জরিমানা $F ঘোষণা করে খেলাটা চালান (Anna দাবি ছাড়ে/করে → Bess মানে/চ্যালেঞ্জ করে bid \(B\) দেয় → Anna match করে/করে না)। দুটো সম্ভাব্য bid \(B_1, B_2\) ধরে extensive game আঁকো; \(B_1 > C_A > C_B > B_2 > F > 0\) ক্ষেত্রে BI solution বের করো; আর দেখাও সাধারণভাবে BI-তে আংটি সবসময় প্রকৃত মালিকের কাছেই যায়।

Figure 3.14 — এক্সারসাইজ ৮(a)-র coin game। START = A1, END = উপরে-ডানে; কালো ঘর অগম্য; তীর দেখায় অনুমোদিত চাল।

৯। (নিজের — strategy গোনা ও BI) উপরের "নিজের আঁকা" strategy-figure-এর গাছটা ধরো: Player 1 root-এ \(L/R\) ও ডান নোডে \(x/y\); Player 2 বাঁ নোডে \(a/b\)। payoff (Player 1, Player 2): \(L{\to}a = (2,2)\), \(L{\to}b = (1,3)\), \(R{\to}x = (3,1)\), \(R{\to}y = (0,0)\)। (a) Player 1-এর ও Player 2-এর কতগুলো strategy? সব লেখো। (b) backward induction-এ সমাধান করো — BI solution (পূর্ণ strategy profile) ও outcome কী? (c) \(R\) খেললে কোন নোডে কখনো পৌঁছানো যায় না? তবু strategy-তে সেখানে চাল থাকা কেন জরুরি — এক লাইনে বলো।

১০। (নিজের — win-lose reasoning) দুই খেলোয়াড় পালা করে \(\{1, 2, 3, 4, 5\}\) থেকে সংখ্যা বাছে (Player 1 আগে); যে প্রথম যোগফল \(25\) বা বেশি করে সে জেতে। (a) "হারা অবস্থান"গুলো বের করো। (b) উপপাদ্য ৩.৫.১ অনুযায়ী কার winning strategy আছে, আর সেটা পুরোপুরি বর্ণনা করো। (c) সংক্ষেপে ব্যাখ্যা করো কেন এখানে প্রথমে চাল দেওয়া (Player 1) সুবিধাজনক, অথচ sum-to-48 (এক্সারসাইজ ৭b) খেলায় নয়।

---

৮. সমাধান (Solutions)

১-নং সমাধান দেখাও

(a) এখানে দুই পক্ষ একই সময়ে সিদ্ধান্ত নেয় (Mr T জানে না তুমি টাকা রেখেছ কি না) — তাই এটা perfect-information ক্রমিক খেলা নয়। তোমার কাছে "না-দেওয়া" একটা strictly dominant strategy: Speedy মুক্ত হলেও না-দিলে ভালো, নিহত হলেও না-দিলে ভালো (\(o_1 \succ o_2\) ও \(o_3 \succ o_4\))। তাই টাকা দিও না।

(b) এবার তুমি আগে টাকা রাখো, Mr T দেখে ছাড়ে/মারে — একটা perfect-information game-frame:

Figure 3.15 — এক্সারসাইজ ১(b)-র game-frame। তুমি প্রথমে pay/not pay; তারপর Mr T release/kill।

(c) Professional (reputation-সচেতন): \(o_2 \succ_{MrT} o_4 \succ_{MrT} o_3 \succ_{MrT} o_1\) — অর্থাৎ টাকা পেলে ছাড়ে, না পেলে মারে (হুমকি বিশ্বাসযোগ্য রাখে)। One-timer (একবারই আঘাত করে, প্রমাণ মোছে): \(o_4 \succ_{MrT} o_2 \succ_{MrT} o_3 \succ_{MrT} o_1\) — টাকা পাক বা না পাক, প্রমাণ মুছতে সে মারতেই চায়। utility:

outcome	\(o_1\)	\(o_2\)	\(o_3\)	\(o_4\)
\(U_{\text{you}}\)	\(4\)	\(3\)	\(2\)	\(1\)
\(U_{MrT}\) (professional)	\(1\)	\(4\)	\(2\)	\(3\)
\(U_{MrT}\) (one-timer)	\(1\)	\(3\)	\(2\)	\(4\)

এই payoff বসিয়ে দুটো game (Figure 3.16)।

Figure 3.16 — বাঁয়ে professional Mr T, ডানে one-timer Mr T।

২-নং সমাধান দেখাও

A প্রস্তাব দেয় (\(P\)/\(K\)/\(F\)); B accept করলে চূড়ান্ত, নাহলে C সিদ্ধান্ত নেয়। প্রতিটি (proposal, response)-এর জন্য C-র নোড, আর payoff utility \(\{1,2,3\}\)-এ বসানো (নিচে 'P'=promote, 'K'=keep, 'F'=fire):

Figure 3.17 — এক্সারসাইজ ২-এর game। A প্রথমে \(P/K/F\); B accept/reject; reject হলে C আবার \(P/K/F\) থেকে বাছে। প্রতিটি terminal-এ payoff-vector (A, B, C)।

৩-নং সমাধান দেখাও

Mr T (professional)-এর বিরুদ্ধে: BI দেখায় তুমি টাকা দেবে এবং Speedy ফিরে পাবে। যুক্তি: pay করলে Mr T release (\(U_{MrT}=4\)) বনাম kill (\(3\)) → release; তুমি পাও \(3\)। not pay করলে Mr T release (\(1\)) বনাম kill (\(2\)) → kill; তুমি পাও \(2\)। \(3 > 2\), তাই pay।

Figure 3.18 — professional Mr T; double-edge = BI solution (তুমি pay করো, Speedy মুক্ত)।

Mr T (one-timer)-এর বিরুদ্ধে: BI দেখায় তুমি টাকা দেবে না এবং Speedy-র জন্য শোকসভা করবে। যুক্তি: pay করলে Mr T kill (\(U_{MrT}=4 > 3\)); তুমি পাও \(1\)। not pay করলে Mr T kill (\(2 > 1\)); তুমি পাও \(2\)। \(2 > 1\), তাই not pay।

Figure 3.19 — one-timer Mr T; BI solution (তুমি না-দাও, Speedy নিহত)।

Promotion game (এক্সারসাইজ ২): BI-তে দুটো solution, পার্থক্য কেবল A যদি \(F\) প্রস্তাব করত তবে B কী করত — দুই ক্ষেত্রেই কর্মকর্তা KEEP (promotion ছাড়া রাখা) হয়। যুক্তি: C সবসময় \(F\) বাছে (C-র best); তাই reject মানে \(F\)। A \(P\) দিলে B: accept-\(P\) (\(U_B=1\)) বনাম reject→\(F\) (\(2\)) → reject। A \(K\) দিলে B: accept-\(K\) (\(3\)) বনাম \(F\) (\(2\)) → accept। A \(F\) দিলে B indifferent (\(F\) যেভাবেই আসুক \(2\))। A-র কাছে: \(P{\to}F\) (\(U_A=1\)), \(K{\to}K\) (\(2\)), \(F{\to}F\) (\(1\)) → A প্রস্তাব করে \(K\), ফল KEEP।

Figure 3.20 — promotion game-এর প্রথম BI solution।

Figure 3.21 — দ্বিতীয় BI solution (A যদি \(F\) দিত তবে B-র জবাব ভিন্ন, কিন্তু ফল একই: KEEP)।

৪-নং সমাধান দেখাও

(a) Figure 3.2: Player 2-এর strategy = (বাঁ নোডে চাল, ডান নোডে চাল) \(\in \{(A,A),(A,R),(R,A),(R,R)\}\)। BI solution: \(\big(\text{Offer 50-50},\ (\text{Accept}, \text{Reject})\big)\)।

Figure 3.22 — Figure 3.2-এর খেলা, double-edge-এ অনন্য BI solution।

Figure 3.23 — এর strategic form। দুটো Nash equilibrium: \((\text{Offer 50-50}, (\text{Accept},\text{Reject}))\) — যা BI solution — এবং \((\text{Offer 70-30}, (\text{Reject},\text{Reject}))\) — যা BI solution নয়।

(b) Figure 3.3: BI solutions \(\big(a, (c,f), g\big)\) ও \(\big(b, (c,e), h\big)\), দুটোই Nash equilibrium। এছাড়া আরও তিনটি Nash equilibrium আছে যেগুলো BI solution নয়: \(\big(b,(d,f),g\big),\ \big(a,(c,f),h\big),\ \big(b,(d,e),h\big)\)।

Figure 3.24 — Figure 3.3-এর দুটো BI solution।

Figure 3.25 — Player 3-এর \(g\) ও \(h\)-এর জন্য আলাদা matrix; Nash equilibria চিহ্নিত। BI solution ⊆ Nash equilibrium, কিন্তু সমান নয়।

৫-নং সমাধান দেখাও

(a) promotion game (এক্সারসাইজ ২): Player B-র তিনটি নোড (A-র \(P\), \(K\), \(F\) প্রস্তাবের পর), প্রতিটিতে accept/reject — তাই \(2^3 = 8\)টি strategy। এখানে B-র copy (Figure 3.26) ও ৮টি strategy-র তালিকা:

Figure 3.26 — এক্সারসাইজ ৫(a)-র জন্য promotion game-এর অনুলিপি।

#	A: \(P\) হলে	A: \(K\) হলে	A: \(F\) হলে
1	accept	accept	accept
2	accept	accept	reject
3	accept	reject	accept
4	accept	reject	reject
5	reject	accept	accept
6	reject	accept	reject
7	reject	reject	accept
8	reject	reject	reject

Player C-র তিনটি নোড, প্রতিটিতে তিনটি চাল (\(P/K/F\)) — তাই \(3 \times 3 \times 3 = 27\)টি strategy।

(b) Figure 3.12-এর খেলা: দুটো BI solution — \(\big((L,W),(a,e)\big)\) (outcome \(La\), payoff \((2,1)\)) ও \(\big((R,W),(a,d)\big)\) (outcome \(Rd\), payoff \((3,2)\))।

Figure 3.28 — একটি BI solution \(((L,W),(a,e))\), outcome \(La\), payoff \((2,1)\)।

Figure 3.29 — দ্বিতীয় BI solution \(((R,W),(a,d))\), outcome \(Rd\), payoff \((3,2)\)।

Player 1-এর \(4\)টি strategy: \(LW, LE, RW, RE\)। Player 2-এর \(6\)টি: \(ac, ad, ae, bc, bd, be\)। strategic form:

Figure 3.30 — এক্সারসাইজ ৫(b)-র strategic form।

বাকি উত্তর: Player 1-এর dominant strategy নেই; Player 2-এর \(ae\) একটা weakly dominant strategy; কোনো dominant-strategy profile নেই। Player 1-এর \(RE\) weakly dominated (\(RW\) দ্বারা)। Player 2-এর dominated: \(ac, ad, bc, bd, be\)। IDWDS প্রয়োগে টিকে থাকে \(((L,W),(a,e))\) — একটা BI solution — এবং \(((L,E),(a,e))\) যা BI solution নয়। মোট পাঁচটি Nash equilibrium: \((LW, ac), (LE, ac), (RW, ad), (LW, ae), (LE, ae)\)।

Figure 3.31 — চিহ্নিত কোষগুলো Nash equilibrium।

৬-নং সমাধান দেখাও

(a) \(x \in \{6, 6.5\}\), \(y \in \{2.5, 3\}\) বসিয়ে মুনাফা হিসাব করলে extensive form (Figure 3.32) — প্রতিটি terminal-এ (Firm 1-এর মুনাফা, Firm 2-এর মুনাফা)।

Figure 3.32 — sequential Cournot game। উপরে Firm 1, নিচে Firm 2-এর মুনাফা: \((6,2.5){\to}(147.5,25)\); \((6,3){\to}(117.5,27.5)\); \((6.5,2.5){\to}(132.5,12.5)\); \((6.5,3){\to}(100,12.5)\)।

(b) BI: Firm 2 \(x=6\)-এর পর \(y=3\) বাছে (\(27.5 > 25\)); \(x=6.5\)-এর পর \(y=2.5\) ও \(y=3\) সমান (\(12.5 = 12.5\)) — এই indifference থেকে দুটো BI solution।

• Solution 1 (Firm 2: \(x=6.5\)-এ \(y=3\)): তখন Firm 1-এর কাছে \(x=6 \to 117.5\) বনাম \(x=6.5 \to 100\) → \(x=6\)। outcome: \(x=6, y=3\), মুনাফা \((117.5, 27.5)\)।

Figure 3.33 — প্রথম BI solution: \(x=6, y=3\)।

• Solution 2 (Firm 2: \(x=6.5\)-এ \(y=2.5\)): তখন Firm 1-এর কাছে \(x=6 \to 117.5\) বনাম \(x=6.5 \to 132.5\) → \(x=6.5\)। outcome: \(x=6.5, y=2.5\), মুনাফা \((132.5, 12.5)\)।

Figure 3.34 — দ্বিতীয় BI solution: \(x=6.5, y=2.5\)।

(c)-(d) strategic form (Figure 3.35); এই খেলায় Nash equilibrium-এর সেট backward-induction solution-এর সেটের সাথে হুবহু মিলে যায়।

Figure 3.35 — Cournot game-এর strategic form, Nash equilibria চিহ্নিত।

৭-নং সমাধান দেখাও

(a) Figure 3.13-এর খেলা: Player 2-এর BI strategy \(x\) নির্বিশেষে একই — \((C, F)\)। তাই BI solution:

• \(x < 2\) হলে একটাই: \(\big(A, (C,F)\big)\)।
• \(x = 2\) হলে দুটো: \(\big(A, (C,F)\big)\) ও \(\big(B, (C,F)\big)\)।
• \(x > 2\) হলে একটাই: \(\big(B, (C,F)\big)\)।

Figure 3.36 — এক্সারসাইজ ৭(a)-র খেলা।

strategic form (Figure 3.37): \(\big(A, (C,E)\big)\) প্রতিটি \(x\)-এর জন্যই একটা Nash equilibrium। এছাড়া \(x\)-ভেদে: \(x<1 \Rightarrow (A,(C,F))\); \(1 \le x < 2 \Rightarrow (A,(C,F)), (B,(D,F))\); \(x=2 \Rightarrow (A,(C,F)), (B,(C,F)), (B,(D,F))\); \(x>2 \Rightarrow (B,(C,F)), (B,(D,F))\)।

Figure 3.37 — এক্সারসাইজ ৭(a)-র strategic form।

(b) sum-to-48 game (পিক \(1\)–\(7\)): হারা অবস্থান খুঁজি। যে \(40\)-এ পৌঁছাতে পারে সে জেতে (প্রতিপক্ষ \(41\)–\(47\)-এ যাবে, তারপর \(48\))। পিছিয়ে হারা অবস্থান: \(40, 32, 24, 16, 8, 0\) — সবই \(8\)-এর গুণিতক। Player 1 শুরু করে \(0\) থেকে — যা নিজেই একটা হারা অবস্থান! তাই Player 2-এর winning strategy আছে: Player 1-এর শেষ চাল \(n\) হলে Player 2 বাছে \((8 - n)\), যাতে যোগফল সবসময় পরের \(8\)-এর গুণিতকে থাকে।

৮-নং সমাধান দেখাও

(a) coin game. প্রথম দুই চালের গাছ (Figure 3.38):

Figure 3.38 — coin game-এর শুরুর অংশ (Player 1-এর প্রথম চাল, তারপর Player 2)।

G4 থেকে Player 1 জিততে পারে: মুদ্রা H5-এ সরাও; তারপর Player 2 বাধ্য H6-এ, Player 1 H7-এ, Player 2 H8-এ, শেষে Player 1 H9-এ (END) জেতে। একটা Player-1-জয়ী play: \(A1 \to B2 \to C3 \to D4 \to E5 \to F5 \to G6 \to H7 \to H8 \to H9\)। একটা Player-2-জয়ী play: \(A1 \to B2 \to C3 \to D4 \to E5 \to F5 \to G6 \to G7 \to H7 \to H8 \to H9\)।

A1 থেকে backward induction-এ প্রতিটি ঘরে \(W\) (এখানে যে চাল দেয় সে জিততে পারে) বা \(L\) (এখানে যে চাল দেয় তাকে হারানো যায়) লিখি: কোনো ঘর থেকে সব গম্য ঘর \(W\) হলে ঘরটা \(L\); কোনো গম্য ঘর \(L\) হলে ঘরটা \(W\) (Figure 3.39)। দেখা যায় Player 1-এর winning strategy আছে: মুদ্রা B1-এ সরাও, তারপর প্রতিবার Player 2-এর চালের পর একটা \(L\)-ঘরে (বা সম্ভব হলে সরাসরি END-এ) সরাও।

Figure 3.39 — coin game-এর সমাধান: প্রতিটি ঘরে \(W\)/\(L\) লেবেল। Player 1 শুরুতে B1-এ গিয়ে জয় নিশ্চিত করে।

(b) diamond ring (challenge). outcome-কে জোড়া \((\$x, \$y)\) ধরি (\(x\) = Anna-র সম্পদ-পরিবর্তন, \(y\) = Bess-এর), utility \(U_{\text{Anna}} = x\), \(U_{\text{Bess}} = y\)। দুই সম্ভাব্য bid \(B_1, B_2\) ধরে গাছ (Figure 3.40)।

Figure 3.40 — Anna দাবি ছাড়ে/করে; Bess accept/challenge (bid \(B_1\) বা \(B_2\)); Anna match/not match। জরিমানা \(F\), ring-মূল্য \(C_A, C_B\)।

ধরো \(B_1 > C_A > C_B > B_2 > F > 0\)। BI solution (double-arrow, Figure 3.40): Anna দাবি করে, Bess accept করে — ring যায় Anna-র কাছে, কারও জরিমানা লাগে না।

সাধারণ ক্ষেত্র (bid যেকোনো \(B \ge 0\))। শেষ নোডে Anna match করবে যদি \(C_A > B\), নাহলে না। তাই Bess challenge করে জিততে হলে তাকে \(B > C_A\) bid করতে হবে, কিন্তু তখন ring পেতে সে $B > C_A > $ (তার নিজের মূল্য যদি \(C_B < C_A\) হয়) দিতে হবে — লোকসান।

Figure 3.41 — সাধারণ bid \(B\)-র জন্য সরল গাছ (এক্সারসাইজ ৮(b)-র শেষ অংশ)।

• Case 1 (Anna প্রকৃত মালিক, \(C_A > C_B\)): শেষ নোডে Anna match (\(C_A > B\)) হলে Bess পায় \(-F\); not match (\(B > C_A\)) হলে Bess পায় \(C_B - B < 0\) (যেহেতু \(B > C_A > C_B\))। দুই ক্ষেত্রেই Bess-এর payoff ঋণাত্মক, তাই Bess accept করে। এটা বুঝে Anna দাবি করে — ring যায় Anna-র কাছে (payoff \(C_A\) ও \(0\)), কোনো টাকা হাতবদল হয় না।
• Case 2 (Bess প্রকৃত মালিক, \(C_B > C_A\)): শেষ নোডে Anna match (\(C_A > B\)) হলে Bess \(-F\); not match (\(B > C_A\)) হলে Bess \(C_B - B\), যা \(C_B > B\) হলে ধনাত্মক। তাই Bess challenge করে \(C_B > B > C_A\) এমন bid দেয়। এটা বুঝে Anna শুরুতেই দাবি ছাড়ে (দাবি করলে তার payoff ঋণাত্মক হতো) — ring যায় Bess-এর কাছে, কোনো টাকা হাতবদল হয় না।
• (e) দুই ক্ষেত্রেই কোনো টাকা হাতবদল হয় না; Sabio কিছুই আয় করে না, Anna ও Bess কিছুই দেয় না। অথচ ring সবসময় প্রকৃত মালিকের কাছেই যায় — Sabio-র চতুর নকশার সৌন্দর্য এখানেই।

৯-নং সমাধান দেখাও

(a) Player 1-এর দুটো decision node (root: \(L/R\); ডান নোড: \(x/y\)), তাই \(2 \times 2 = 4\)টি strategy: \((L,x), (L,y), (R,x), (R,y)\)। Player 2-এর একটাই নোড (\(a/b\)), তাই \(2\)টি strategy: \(a\) ও \(b\)।

(b) BI নিচ থেকে:

• Player 2-এর নোড (root-এ \(L\)-এর পর): \(a \to\) Player 2 পায় \(2\), \(b \to\) পায় \(3\) → \(b\), নোড marked \((1,3)\)।
• Player 1-এর ডান নোড (\(R\)-এর পর): \(x \to\) Player 1 পায় \(3\), \(y \to\) পায় \(0\) → \(x\), নোড marked \((3,1)\)।
• root-এ Player 1: \(L \to 1\) (কারণ Player 2 \(b\) দেবে) বনাম \(R \to 3\) → \(R\)।

তাই BI solution = strategy profile \(\big((R, x),\ b\big)\): Player 1 root-এ \(R\), ডান নোডে \(x\); Player 2 (অপৌঁছানো নোডে) \(b\)। outcome: play "\(R\) তারপর \(x\)", payoff \((3, 1)\)।

(c) \(R\) খেললে Player 2-এর বাঁ নোডে কখনো পৌঁছানো যায় না। তবু strategy-তে সেখানে চাল (\(b\)) থাকা জরুরি কারণ strategy সংজ্ঞা-বলেই প্রতিটি decision node কভার করে — আর ঠিক এই "অপৌঁছানো নোডে কী হতো" জেনেই Player 1 root-এ সিদ্ধান্ত নেয় (\(L\) দিলে Player 2 \(b\) দিত, তাই \(L \to 1\))।

১০-নং সমাধান দেখাও

(a) লক্ষ্য \(25\), সর্বোচ্চ চাল \(5\), তাই "নিরাপদ ব্যবধান" \(5 + 1 = 6\)। যে \(20\)–\(24\)-এ থাকে সে সরাসরি \(25\)-এ পৌঁছে জেতে; তাই \(19\) একটা হারা অবস্থান, এবং পিছিয়ে হারা অবস্থান: \(1, 7, 13, 19\) (সবই \(6\)-এর গুণিতক \(+1\); \(25\) = জয়)।

(b) যোগফল শুরু হয় \(0\) থেকে, যা হারা অবস্থান নয় (\(0\) কে \(6\) দিয়ে ভাগ করলে ভাগশেষ \(0\), \(1\) নয়)। তাই প্রথম চালকারী Player 1-এর winning strategy আছে: শুরুতে \(1\) বাছো (Player 2-কে প্রথম হারা অবস্থান \(1\)-এ ফেলে); তারপর প্রতিবার Player 2-এর চাল \(n\)-এর জবাবে \((6 - n)\) বাছো, যাতে যোগফল সবসময় পরের হারা অবস্থানে (\(7, 13, 19\)) পৌঁছায়। \(19\)-এর পর Player 2 বাধ্য \(20\)–\(24\)-এ যাবে, আর Player 1 \(25\)-এ পৌঁছে জেতে।

(c) এখানে \(0\) হারা অবস্থান নয় বলে প্রথম চালকারী প্রতিপক্ষকে হারা অবস্থানে ঠেলতে পারে — তাই Player 1 সুবিধায়। কিন্তু sum-to-48 (পিক \(1\)–\(7\)) খেলায় নিরাপদ ব্যবধান \(8\), আর \(0\) নিজেই \(8\)-এর গুণিতক অর্থাৎ হারা অবস্থান — তাই সেখানে প্রথম চালকারী (Player 1) নিজেই হারা অবস্থানে শুরু করে, সুবিধাটা চলে যায় Player 2-এর কাছে। কে জিতবে তা নির্ভর করে \(0\) হারা অবস্থান কি না তার ওপর।

---

৯. সারসংক্ষেপ ও Checklist

এই অধ্যায়ে perfect-information (ক্রমিক, পূর্ণ-তথ্য) খেলার পুরো কাঠামো এক জায়গায়:

• গাছ, frame, game: perfect-information game = rooted directed tree + খেলোয়াড় + action + outcome; এতে প্রতিটি খেলোয়াড়ের ranking (utility) যোগ করলে তবেই game (নাহলে কেবল game-frame)।
• backward induction: প্রান্ত থেকে মূলের দিকে প্রতিটি নোডে সেই খেলোয়াড়ের সর্বোচ্চ-payoff চাল বেছে mark করা। কোনো নোডে indifference থাকলে একাধিক BI solution।
• strategy: প্রতিটি decision node-এর জন্য একটা করে চাল (অপৌঁছানো নোডসহ — redundancy)। strategy profile → অনন্য outcome → strategic form।
• solution বনাম outcome: solution পূর্ণ strategy profile; outcome কেবল আসল চালের ক্রম।
• BI ⊆ Nash: প্রতিটি BI solution একটা Nash equilibrium (উপপাদ্য ৩.৪.১, প্রমাণসহ), কিন্তু উল্টোটা নয় — অতিরিক্ত Nash equilibrium প্রায়ই incredible threat-এ দাঁড়ানো (entry game, Chain-Store)।
• দুই-খেলোয়াড় উপপাদ্য: সসীম win-lose খেলায় কারও-না-কারও winning strategy থাকে (৩.৫.১); তিন-ফলাফল খেলা তিন শ্রেণির একটায় পড়ে (৩.৫.২) — tic-tac-toe/checkers ড্র, chess অজানা।

Checklist — নিজেকে যাচাই করো:

• [ ] একটা পরিস্থিতিকে rooted directed tree-তে extensive-form game হিসেবে আঁকতে পারি, আর game বনাম game-frame আলাদা করতে পারি।
• [ ] যেকোনো সসীম perfect-information game-এ backward-induction অ্যালগরিদম চালিয়ে solution বের করতে পারি।
• [ ] কখন একাধিক BI solution আসে (indifference) তা চিনতে পারি।
• [ ] একজন খেলোয়াড়ের strategy-সংখ্যা গুণফল দিয়ে বের করতে পারি এবং redundancy ব্যাখ্যা করতে পারি।
• [ ] backward-induction solution বনাম outcome আলাদা করতে পারি।
• [ ] দেখাতে পারি প্রতিটি BI solution একটা Nash equilibrium, এবং entry game-এ incredible threat-ভিত্তিক অতিরিক্ত Nash equilibrium চিহ্নিত করতে পারি।
• [ ] win-lose খেলায় "হারা অবস্থান" বের করে winning strategy বর্ণনা করতে পারি, এবং কে জেতে তা \(0\) হারা অবস্থান কি না দিয়ে বলতে পারি।
• [ ] Python-এ recursive backward induction লিখে একটা গাছের BI solution বের করতে পারি।

---

➡️ পরের অধ্যায়: 10.7 — General Dynamic Games — এবার তুলে নেব perfect information-এর শর্ত: information set, imperfect information, ও সাধারণ dynamic game।