10.7 — General Dynamic Games (সাধারণ গতিশীল গেম)¶

এই অধ্যায়ে কী শিখব: আগের অধ্যায়ে আমরা perfect-information (পূর্ণ তথ্য) খেলা দেখেছি — প্রতিটা খেলোয়াড় ঠিক জানে সে গাছের কোন node-এ আছে, আগে কে কী করেছে। বাস্তবে বেশিরভাগ সময় খেলোয়াড়ের কাছে আংশিক তথ্য থাকে। এই অধ্যায়ে সেই সাধারণ কাঠামোটা গড়ব। ধাপে ধাপে শিখব: imperfect information (অপূর্ণ তথ্য) এবং তা আঁকার হাতিয়ার information set (তথ্য-সেট); extensive-form game-frame (বিস্তৃত-রূপ খেলা-কাঠামো)-এর পূর্ণ সংজ্ঞা এবং perfect recall (পূর্ণ স্মৃতি) কী; সাধারণ খেলায় strategy (কৌশল) মানে কী (প্রতিটা information set-এ একটা করে পছন্দ) আর কীভাবে তা থেকে strategic form (কৌশলগত রূপ) পাই; subgame (উপ-গেম) — কোন অংশটা নিজেই একটা আস্ত খেলা, proper subgame (প্রকৃত উপ-গেম) ও minimal subgame (ন্যূনতম উপ-গেম); গেম থিওরির অন্যতম কেন্দ্রীয় ধারণা subgame-perfect equilibrium (উপ-গেম-পারফেক্ট ভারসাম্য) — যা perfect-information খেলায় backward induction (পশ্চাৎ-অনুমান)-এর সাধারণীকরণ, সঙ্গে তা বের করার পূর্ণ algorithm (অ্যালগরিদম); আর সবশেষে chance move (দৈব চাল) — কীভাবে Nature (প্রকৃতি) নামের কাল্পনিক খেলোয়াড় দিয়ে সম্ভাব্যতাকে খেলায় ঢোকাই, money lottery (অর্থ-লটারি), তার expected value (প্রত্যাশিত মান) এবং risk neutrality (ঝুঁকি-নিরপেক্ষতা)। প্রতিটা ধারণা ছবিসহ, সংজ্ঞাসহ, প্রমাণসহ (proof $\square$ ), Python-কোডসহ ও ১০টা এক্সারসাইজ-সমাধানসহ।

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

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

আগের অধ্যায়ের perfect-information খেলায় একটা লুকানো (এবং প্রায়ই অবাস্তব) ধরে-নেওয়া ছিল: যখন কোনো খেলোয়াড়ের চাল দেওয়ার পালা আসে, তখন সে হুবহু জানে ইতিমধ্যে কী কী ঘটেছে — আগের সব খেলোয়াড় ঠিক কোন কোন চাল দিয়েছে। কিন্তু ভাবো এই বাস্তব দৃশ্যগুলো:

পরীক্ষায় নকল। এক অধ্যাপক নকল ঠেকাতে দুই রঙের কাগজে (সাদা ও গোলাপি) পরীক্ষা ছাপান, যাতে পাশাপাশি বসা ছাত্রেরা ভিন্ন version পায়। এক দুর্বল ছাত্র পাশের ভালো ছাত্রের খাতা দেখে নকল করতে চায়। কিন্তু সে জানে না দুই version আসলে এক কিনা (অধ্যাপক bluff করছেন কিনা)। একই version হলে নকল করে A, ভিন্ন হলে ধরা পড়ে F, আর নকল না করে ফাঁকা খাতা দিলে C।
তাসের রং। Ann একটা লাল বা কালো তাস বেছে Bob-কে দেখায়; তারপর Bob, Carla-কে বলে তাসটার রং কী (সত্যি বা মিথ্যা)। Carla-কে শুধু Bob-এর কথা শুনে রং আন্দাজ করতে হয় — সে Ann-এর আসল তাস দেখেনি।
চাকরির প্রস্তাব। নিয়োগকর্তা প্রথমে এক প্রার্থীকে ফোন করেন; সে "না" বললে দ্বিতীয়জনকে ফোন করেন — কিন্তু কাউকে বলেন না এটা প্রথম প্রস্তাব নাকি "recycled" (ফিরে-আসা) প্রস্তাব। প্রার্থী জানে না সে প্রথম পছন্দ ছিল কিনা।

তিনটাতেই একজন খেলোয়াড়কে সিদ্ধান্ত নিতে হচ্ছে অথচ সে নিশ্চিত নয় সে খেলার গাছের ঠিক কোন জায়গায় আছে। এই "কোথায় আছি জানি না" অবস্থাটাকে আঁকতেই লাগবে নতুন হাতিয়ার — information set। আর যেই মুহূর্তে খেলোয়াড়দের তথ্য অপূর্ণ হলো, backward induction-এর সরল ঝাড়ু আর সরাসরি চলে না; তার জায়গায় আসে তার শক্তিশালী সাধারণীকরণ — subgame-perfect equilibrium।

মূল স্বজ্ঞা

গোটা অধ্যায় তিনটা বাক্যে:

information set — একই খেলোয়াড়ের এমন কতগুলো decision node একসাথে বাঁধা, যাদের মধ্যে সে আলাদা করতে পারে না সে কোনটায় আছে; তাই এদের সবগুলোয় তাকে একই কাজ করতে হবে।
subgame — খেলার এমন একটা টুকরো যা নিজেই একটা সম্পূর্ণ খেলা: শুরু হয় একটা singleton (একক) node থেকে আর কোনো information set-কে "কেটে" ফেলে না।
subgame-perfect equilibrium — এমন একটা strategy profile যা শুধু গোটা খেলায় নয়, প্রতিটা subgame-এও Nash equilibrium; অর্থাৎ প্রতিটা মোড়ে খেলোয়াড়ের পরিকল্পনা বিশ্বাসযোগ্য (credible), ফাঁপা হুমকিমুক্ত।

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

এই অংশে আমরা Bonanno-র ৫টা উপ-অধ্যায় (4.1–4.5) একে একে দেখব, প্রতিটা ছবিসহ। প্রথমে গল্পে-উদাহরণে স্বজ্ঞা গড়ব; আনুষ্ঠানিক সংজ্ঞা ও প্রমাণ আসবে পরের অংশে (৩ নং)।

২.১ Imperfect information — information set¶

নিজের আঁকা একটা সরল ছবি দিয়ে শুরু করি, যাতে information set-এর ধারণাটা চোখে গেঁথে যায়:

Kid figure: information set in the exam-copying game tree

চিত্র ২.১ (নিজের আঁকা) — নকলের খেলা। Professor আগে বাছেন identical (একই) নাকি different (ভিন্ন) version; তারপর Student বাছে Copy নাকি Blank। Student-এর দুটো node একটা information set-এ (লাল ভাঙা আয়তক্ষেত্র) বাঁধা: দুই node-এ একই action {Copy, Blank}, কিন্তু Student জানে না Professor কী করেছেন — তাই দুই node-এ তাকে একই সিদ্ধান্ত নিতে হবে।

এই একই খেলাটা Bonanno যেভাবে আঁকেন:

An extensive-form game-frame with imperfect information

Figure 4.1 — নকলের খেলার extensive-form game-frame। Professor-এর একটা node (root), Student-এর দুটো node একই information set-এ। এটা এখনো একটা game-frame (কাঠামো), game নয় — কারণ এখনো outcome-গুলোর উপর খেলোয়াড়দের পছন্দক্রম (ranking/payoff) বসাইনি। information set বোঝাতে node-গুলোকে একটা গোল-কোণা আয়তক্ষেত্রে ঘিরে দেওয়া হয়।

মূল কথাটা লক্ষ করো: information set মানে খেলোয়াড়ের মনের অনিশ্চয়তা। Student জানে সে চাল দিচ্ছে, কিন্তু জানে না কোন node-এ — বাঁ (identical) নাকি ডান (different)। এই জন্যই সে "identical হলে Copy, different হলে Blank" — এমন পরিকল্পনা করতে পারে না; কারণ সিদ্ধান্তের মুহূর্তে তার কাছে সেই তথ্যই নেই।

একটা সূক্ষ্ম কিন্তু জরুরি শর্ত: একই information set-এর সব node-এ available action একই হতে হবে। যদি বাঁ node-এ {Copy, Blank} আর ডান node-এ {Copy, Blank, Cheat-differently} থাকত, তাহলে action-সংখ্যা গুনেই Student বুঝে ফেলত সে কোন node-এ — অনিশ্চয়তা ভেঙে যেত।

আরও দুটো উদাহরণ, যাতে "কে কী জানে, কখন জানে" ব্যাপারটা পাকা হয়।

উদাহরণ ৪.১ (Ann, Bob, Carla)। Ann একটা লাল বা কালো তাস বেছে Bob-কে দেখায় (Carla তখন ঘরের বাইরে)। Carla ঢুকলে Bob তাকে বলে "Ann লাল বেছেছে" বা "Ann কালো বেছেছে" — সত্যি বা মিথ্যা। Carla তারপর রং আন্দাজ করে। ঠিক হলে Ann ও Bob দুজনে Carla-কে $1 করে দেয়; ভুল হলে Carla দুজনকে $1 করে দেয়।

The extensive form game-frame representing Example 4.1

Figure 4.3 — উদাহরণ ৪.১-এর কাঠামো। Bob-এর দুটো information set, প্রতিটা একটামাত্র node-এর (singleton) — কারণ Bob তাসের রং দেখেছে, তাই সে জানে কোন node-এ আছে। কিন্তু Carla-র প্রতিটা information set-এ দুটো node: সে Bob-এর কথা শোনে (তাই দুটো আলাদা information set — একটা "কালো শুনলে", একটা "লাল শুনলে"), কিন্তু Bob সত্যি না মিথ্যা বলছে তা জানে না (তাই প্রতিটা information set-এ দুই node)।

লক্ষ করো — Carla "কিছু" জানে (Bob যা বলল) আবার "কিছু" জানে না (Ann আসলে কী বেছেছে)। information set ঠিক এই আংশিক জ্ঞানটাই ধরে রাখে।

উদাহরণ ৪.২ (Yvonne ও Fran)। এক চাকরির জন্য দুজন প্রার্থী; নিয়োগকর্তা একজনকে আগে ডাকবেন, "না" বললে অন্যজনকে — কিন্তু জানাবেন না এটা প্রথম নাকি recycled প্রস্তাব।

The extensive form, or frame, representing Example 4.2

Figure 4.4 — উদাহরণ ৪.২-এর frame। Employer আগে বাছেন কাকে "First call" করবেন। প্রতিটা প্রার্থীর (Yvonne, Fran) একটামাত্র information set, যাতে দুটো node — "আমাকে প্রথমে ডাকা হয়েছে" আর "আমাকে recycled ডাকা হয়েছে" — প্রার্থী এদের আলাদা করতে পারে না, তাই দুটোতেই একই উত্তর (Yes/No) দিতে বাধ্য।

এবার frame-এ payoff বসিয়ে একে game বানাই। Employer: পদ পূরণ হলে $1$, নাহলে $0$। Yvonne: প্রথম প্রস্তাব গ্রহণ করলে $2$, hire না হলে $1$, recycled প্রস্তাব গ্রহণ করলে $0$ (সবচেয়ে খারাপ — কারণ তখন Fran খোঁটা দেবে)। Fran-এরও সমান-কিন্তু-প্রতিসম পছন্দ।

A game based on the extensive-form frame of Figure 4.4

Figure 4.5 — Figure 4.4-এর frame-এ payoff বসিয়ে পাওয়া game। প্রতিটা terminal node-এ তিনটা সংখ্যা: (Employer, Yvonne, Fran)। এই payoff-গুলোই পরের subgame ও equilibrium-বিশ্লেষণের কাঁচামাল।

২.২ Strategies — extensive থেকে strategic form¶

সাধারণ খেলায় strategy-র সংজ্ঞা perfect-information ক্ষেত্রের স্বাভাবিক সম্প্রসারণ: এটা একটা সম্পূর্ণ, শর্তসাপেক্ষ পরিকল্পনা (complete contingent plan) — খেলোয়াড় যত রকম পরিস্থিতিতে পড়তে পারে, প্রতিটার জন্য একটা করে পছন্দ। পার্থক্য শুধু "পরিস্থিতি" শব্দের অর্থে: perfect information-এ পরিস্থিতি = একটা decision node; সাধারণ ক্ষেত্রে পরিস্থিতি = একটা information set।

তাই Figure 4.5-এ Yvonne-এর মাত্র একটা information set, সুতরাং তার strategy কেবল "Yes" বা "No"। সে "প্রথমে ডাকলে Yes, recycled ডাকলে No" — এমন পরিকল্পনা করতে পারে না, কারণ ডাক পাওয়ার সময় তাকে বলা হয় না এটা কোন ধরনের ডাক।

প্রতিটা extensive-form game থেকে একটা strategic form (matrix) বানানো যায়: প্রতিটা খেলোয়াড়ের strategy-গুলো সারি/কলাম, প্রতিটা ঘরে outcome বা payoff।

The strategic form of the game of Figure 4.5 with the Nash equilibria highlighted

Figure 4.6 — Figure 4.5-এর strategic form, Nash equilibrium highlight করা। এটা তিন-খেলোয়াড়ের খেলা, তাই Employer-এর দুই পছন্দ (কাকে আগে ডাকা) অনুযায়ী দুটো matrix; সারি = Yvonne (Yes/No), কলাম = Fran (Yes/No)। মূল স্বজ্ঞা: যাকে ডাকা হয় সে সাধারণত Yes বলে (first offer-এ $2$ পায়), কারণ No বললে সে hire-ই হয় না ($1$)।

Figure 4.3-এর তাস-খেলারও strategic form বানানো যায়। এখানে Bob-এর strategy লিখি $(x,y)$ হিসেবে — "Ann কালো বেছে থাকলে বলি $x$, লাল বেছে থাকলে বলি $y$"; তাই $(R,B)$ মানে দুই ক্ষেত্রেই মিথ্যা বলা। একইভাবে Carla-র strategy $(x,y)$ মানে "Bob কালো বললে আন্দাজ করি $x$, লাল বললে $y$"।

The strategic form of the game of Figure 4.3

Figure 4.7 — Figure 4.3-এর তাস-খেলার strategic form। Bob ও Carla-র প্রত্যেকের $2 \times 2 = 4$টা strategy (দুই information set, প্রতিটায় দুই পছন্দ), Ann-এর $2$টা। এই matrix থেকেই Nash equilibrium খোঁজা যায়।

এখন প্রশ্ন: extensive খেলা "সমাধান" করতে আমরা কি শুধু strategic form বানিয়ে Nash equilibrium খুঁজব? আগের অধ্যায়ে দেখেছি perfect-information খেলায় সব Nash equilibrium "যুক্তিসঙ্গত" নয় — কিছু equilibrium ফাঁপা (non-credible) হুমকির উপর দাঁড়ানো, আর backward induction সেগুলো ছেঁটে ফেলে। সাধারণ খেলার জন্য দরকার backward induction-এর সাধারণ রূপ। সেটাই subgame-perfect equilibrium। তার আগে চাই subgame-এর সংজ্ঞা।

২.৩ Subgames — খেলার ভেতরের আস্ত খেলা¶

নিজের আঁকা ছবিতে আগে দেখে নিই কোনটা subgame, কোনটা নয়:

Kid figure: which part is a subgame and which is not

চিত্র ২.২ (নিজের আঁকা) — বাঁয়ে node $x$ একটা singleton, তার থেকে শুরু করে সব successor নিলে পাওয়া অংশ একটা subgame (সবুজ ডিম্বাকৃতি, OK)। ডানে Player 3-এর দুই node একই information set-এ; কেবল বাঁ node থেকে শুরু করতে চাইলে ডিম্বাকৃতিটা information set-কে "কেটে" ফেলে (একটা node ভেতরে, একটা বাইরে) — তাই ওটা subgame নয়।

স্বজ্ঞামূলকভাবে, subgame খুঁজতে দুই ধাপ:

এমন একটা decision node $x$ থেকে শুরু করো যার information set শুধু $\{x\}$ (singleton); $x$ ও তার সব successor-কে একটা ডিম্বাকৃতিতে ঘেরো।
যদি সেই ডিম্বাকৃতি কোনো information set না কাটে (অর্থাৎ এমন কোনো information set নেই যার একটা node ভেতরে আর আরেকটা বাইরে), তবে ভেতরের অংশটা একটা subgame; নাহলে নয়।

Bonanno-র উদাহরণে এটা স্পষ্ট:

An extensive-form game with two proper subgames

Figure 4.8 — চারটা সম্ভাব্য শুরুর বিন্দু: root এবং node $x$, $y$, $z$ (বাকি node-গুলো বড় information set-এর অংশ, তাই singleton নয়)। root থেকে পুরো খেলা (এটাও তুচ্ছার্থে subgame)। $x$ থেকে বাঁ ডিম্বাকৃতি — একটা proper subgame। $y$ থেকে ডান ডিম্বাকৃতি Player 3-এর উপরের information set কাটে — তাই subgame নয়। $z$ থেকে নিচের ডিম্বাকৃতি — আরেকটা proper subgame। মোট: পুরো খেলা + দুটো proper subgame।

"proper subgame" মানে পুরো খেলাটা বাদে বাকি subgame (যেমন set-এর proper subset)। আর minimal subgame হলো এমন subgame যার ভেতরে আর কোনো (ছোট) subgame নেই:

An extensive-form game with three proper subgames, two of which are minimal

Figure 4.9 — তিনটা proper subgame: $x$, $y$, $z$ থেকে। $x$ ও $z$ থেকে শুরু হওয়াগুলো minimal (ভেতরে আর subgame নেই)। $y$ থেকে শুরু হওয়াটা minimal নয় — কারণ তার ভেতরেই $z$-এর subgame ঢুকে আছে। এই খেলাটাই পরের অংশে subgame-perfect equilibrium বের করতে ব্যবহার করব।

২.৪ Subgame-perfect equilibrium — সাধারণীকৃত backward induction¶

সংজ্ঞা (স্বজ্ঞামূলক)। একটা strategy profile $s$ হলো subgame-perfect equilibrium যদি সে শুধু গোটা খেলার Nash equilibrium না হয়ে, প্রতিটা proper subgame-এও Nash equilibrium থাকে। অর্থাৎ খেলার যেকোনো মোড়ে "কেটে" আলাদা খেলা হিসেবে দেখলেও কেউ একা সরে গিয়ে লাভ করতে পারবে না — কোনো ফাঁপা হুমকি টেকে না।

কেন এটা জরুরি, তা Figure 4.9 দিয়ে বোঝা যায়। ওই খেলায় strategy profile $s = ((a,C),(d,f,E),(h,B))$ আসলে গোটা খেলার একটা Nash equilibrium — কেউ একা সরে লাভ করে না। কিন্তু এটা subgame-perfect নয়: $z$-থেকে-শুরু proper subgame-এ $s$-এর সীমাবদ্ধ রূপ $(C,E)$ ওই subgame-এর Nash equilibrium নয় (সেখানে $C$-এর বিরুদ্ধে Player 2-এর একমাত্র সেরা জবাব $F$, $E$ নয়)। তাই $s$-এ লুকানো একটা অবিশ্বাসযোগ্য পরিকল্পনা আছে।

সব Nash equilibrium বের করে তারপর প্রতিটা subgame যাচাই করা কষ্টকর। বদলে একটা algorithm আছে, যা perfect-information খেলার backward induction-এর সরাসরি সাধারণীকরণ — "ভেতর থেকে বাইরে" ভাঁজ করে করে খেলা ছোট করা:

Kid figure: subgame-perfect equilibrium as backward induction on subgames

চিত্র ২.৩ (নিজের আঁকা) — অ্যালগরিদমের মূল ধাপ। বাঁয়ে একটা minimal subgame-এর Nash equilibrium ($d$, payoff $(2,1)$) বের করি; ডানে সেই subgame-টা মুছে তার জায়গায় ওই payoff-vector বসাই। এবার ছোট খেলাটা সমাধান করি — Player 1 বাছে $b$ ($2 > 0$)। জোড়া লাগিয়ে SPE = $(b, d)$।

চলো Figure 4.9-এ পুরো অ্যালগরিদমটা চালাই। এটা ধাপে ধাপে minimal subgame ভাঁজ করে করে এগোয়:

ধাপ ১। $x$-থেকে-শুরু minimal subgame (Player 2 ও 3-এর মধ্যে)। এর strategic form থেকে একমাত্র Nash equilibrium $(d,h)$।

A minimal proper subgame of the game of Figure 4.9 and its strategic form

Figure 4.10 — $x$-এর minimal subgame ও তার strategic form। এখানে শুধু Player 2 ও 3-এর payoff দেখানো; একমাত্র Nash equilibrium $(d,h)$।

এই subgame মুছে $x$-কে terminal বানাই, বসাই history $adh$-এর payoff $(2,1,2)$:

The reduced game after replacing the minimal subgame with payoff (2,1,2)

Figure 4.11 — Figure 4.10-এর subgame-কে তার Nash equilibrium $(d,h)$-এর payoff $(2,1,2)$ দিয়ে প্রতিস্থাপন করে পাওয়া ছোট খেলা।

ধাপ ২। এবার ছোট খেলার একমাত্র minimal subgame — নিচের Player-1 node থেকে। তার একমাত্র Nash equilibrium $(C,F)$:

The minimal subgame of the game of Figure 4.11 and its strategic form

Figure 4.12 — Figure 4.11-এর minimal subgame ও strategic form; একমাত্র Nash equilibrium $(C,F)$।

মুছে বসাই history $beACF$-এর payoff $(1,1,1)$:

The reduced game after replacing the minimal subgame with payoff (1,1,1)

Figure 4.13 — Figure 4.12-এর subgame-কে $(C,F)$-এর payoff $(1,1,1)$ দিয়ে প্রতিস্থাপন।

ধাপ ৩। এবার Player 2-এর node থেকে subgame; একমাত্র Nash equilibrium $(f,A)$:

The minimal subgame of the game of Figure 4.13 and its strategic form

Figure 4.14 — Figure 4.13-এর minimal subgame ও strategic form; একমাত্র Nash equilibrium $(f,A)$।

মুছে বসাই history $bfA$-এর payoff $(3,2,1)$:

The reduced game after replacing the proper subgame with payoff (3,2,1)

Figure 4.15 — $(f,A)$-এর payoff $(3,2,1)$ বসিয়ে পাওয়া সবচেয়ে ছোট খেলা। এখানে Player 1-এর একমাত্র সেরা পছন্দ $b$ (payoff $3 > 2$)।

সব ধাপে বাছা পছন্দ জোড়া লাগালে Figure 4.9-এর subgame-perfect equilibrium:

\[ s^* = \big(\,(b,C),\ (d,f,F),\ (h,A)\,\big). \]

দ্বিতীয় উদাহরণ (Figure 4.8-এর নকল)। এবার এমন খেলা যেখানে ভাঁজ করতে করতে একাধিক Nash equilibrium পাওয়া যায় — তখন একাধিক subgame-perfect equilibrium মেলে।

Copy of the game of Figure 4.8

Figure 4.16 — Figure 4.8-এর হুবহু নকল। $x$-থেকে subgame-এর Nash equilibrium $c$ (payoff $(3,1,2)$), আর $z$-থেকে subgame-এর Nash equilibrium $(e,h)$ (payoff $(3,2,1)$)।

দুই subgame ভাঁজ করলে বাকি থাকে এই ছোট খেলা, যার strategic form-এ দুটো Nash equilibrium:

The game of Figure 4.16 reduced with its strategic form and highlighted Nash equilibria

Figure 4.17 — ভাঁজ করার পর বাকি খেলা ও তার strategic form (Player 3-এর $a$/$b$ অনুযায়ী দুই matrix), Nash equilibrium highlight করা। দুটো Nash equilibrium: $(L,D,a)$ ও $(R,U,b)$।

তাই Figure 4.16-এর দুটো subgame-perfect equilibrium — একটা

\[ \big(\,(L,c),\,(D,e),\,(a,h)\,\big), \]

আর অন্যটা

\[ \big(\,(R,c),\,(U,e),\,(b,h)\,\big). \]

চারটা মূল সিদ্ধান্ত মাথায় রাখো: (১) কোনো subgame-এ একাধিক Nash equilibrium থাকলে প্রতিটা বেছে আলাদা subgame-perfect equilibrium পাওয়া যায়; (২) কোনো subgame-এ (pure strategy-তে) Nash equilibrium না থাকলে খেলার কোনো subgame-perfect equilibrium নেই; (৩) perfect-information খেলায় subgame-perfect equilibrium ঠিক backward-induction সমাধানের সমান; (৪) কোনো proper subgame না থাকলে (যেমন Figure 4.3) Nash ও subgame-perfect equilibrium-এর সেট এক — সাধারণভাবে subgame-perfect equilibrium হলো Nash equilibrium-এর একটা refinement (পরিশোধন)।

২.৫ Games with chance moves — Nature ও প্রত্যাশিত payoff¶

এতক্ষণ outcome-এ কোনো অনিশ্চয়তা ছিল না। কিন্তু বাস্তবে তাস-শাফল, লটারি, দৈব ঘটনা লাগে। এদের আঁকতে একটা কাল্পনিক খেলোয়াড় ঢোকাই — Nature (বা Chance), যার "চাল"-গুলোয় একটা probability distribution (সম্ভাবনা-বণ্টন) বসানো থাকে। Nature-কে কোনো payoff দেওয়া হয় না; সে কেবল দৈব ঘটনা ঘটায়।

উদাহরণ। তিনটা তাস — একটা কালো, দুটো লাল — শাফল করে উপুড় করে রাখা। Adele উপরের তাস দেখে (Ben দেখে না), তারপর Ben-কে বলে "উপরের তাস কালো" বা "উপরের তাস লাল" (সত্যি বা মিথ্যা)। Ben আসল রং আন্দাজ করে; ঠিক হলে Adele-এর কাছ থেকে $9 পায়, নাহলে Adele-কে $9 দেয়। উপরের তাস কালো হওয়ার সম্ভাবনা $\tfrac{1}{3}$, লাল হওয়ার সম্ভাবনা $\tfrac{2}{3}$।

An extensive form with a chance move

Figure 4.18 — chance move-সহ extensive form। root-এ Nature: বাঁ edge (Black) সম্ভাবনা $\tfrac{1}{3}$, ডান edge (Red) সম্ভাবনা $\tfrac{2}{3}$। এরপর Adele বলে (সে রং দেখেছে, তাই তার node singleton), তারপর Ben আন্দাজ করে (Ben রং দেখেনি, তাই তার node-জোড়া information set-এ)। terminal-এর সংখ্যা ডলার-পরিমাণ।

chance move থাকলেও strategy-র ধারণা বদলায় না: Adele-এর $4$টা strategy (কালো দেখলে কী বলি, লাল দেখলে কী বলি), Ben-এরও $4$টা (Adele "Black" বললে কী আন্দাজ, "Red" বললে কী)। কিন্তু strategic form বানাতে গিয়ে সমস্যা: একটা strategy-জোড়ার outcome আর নির্দিষ্ট নয়, বরং সম্ভাব্য — একটা lottery। যেমন Adele সত্যবাদী ((B,R)) আর Ben সবসময় "Black" আন্দাজ করলে ((B,B)):

outcome	সম্ভাবনা
Adele Ben-কে $9 দেয়	$\tfrac{1}{3}$
Ben Adele-কে $9 দেয়	$\tfrac{2}{3}$

এই lottery-কে একটা payoff-এ নামাতে জানতে হয় খেলোয়াড় lottery কীভাবে র‍্যাঙ্ক করে। এখানে সরল ধরে-নেওয়া: খেলোয়াড়েরা selfish, greedy ও risk neutral — অর্থাৎ তারা একটা money lottery-কে ঠিক তার expected value (প্রত্যাশিত মান)-এর সমান গণ্য করে। তখন উপরের lottery-তে Adele-এর জন্য

\[ \tfrac{1}{3}\,(-9) + \tfrac{2}{3}\,(+9) = -3 + 6 = 3. \]

(এখানে Adele লাভ করে যখন Ben ভুল করে।) প্রতিটা ঘরে এভাবে expected value বসিয়ে পুরো strategic form বানানো যায়:

The strategic form of the game of Figure 4.18 for risk-neutral players

Figure 4.19 — risk-neutral ধরে-নিয়ে Figure 4.18-এর strategic form। প্রতিটা ঘরে দুটো সংখ্যা: প্রথমটা Adele-এর, দ্বিতীয়টা Ben-এর প্রত্যাশিত payoff (= money lottery-র expected value)। এই matrix Python-এ যাচাই করব ৫ নং অংশে।

দ্বিতীয় উদাহরণ (উদাহরণ ৪.৩ — খাম)। তিনটা অচিহ্নিত খামে $100, $200, $300। শাফল করে একটা Player 1-কে, একটা Player 2-কে দেওয়া হয় (তৃতীয়টা টেবিলে থাকে)। Player 1 নিজের খাম খুলে দেখে (Player 2-কে দেখায় না), তারপর "pass" বলে (দুজনে নিজের খাম রাখে) অথবা "trade" প্রস্তাব দেয়। Player 2 নিজের খাম না দেখেই Yes/No বলে। সবাই risk neutral।

The extensive-form game of Example 4.3

Figure 4.20 — উদাহরণ ৪.৩-এর খেলা। root-এ Nature $6$টা সমসম্ভাব্য ($\tfrac{1}{6}$) বণ্টন দেয় (কে কোন খাম পায়)। Player 1 নিজের অঙ্ক দেখে (P = pass, T = trade); Player 2 না দেখে (Y = Yes, N = No)। terminal-এ $(\text{Player 1}, \text{Player 2})$ ডলার।

The strategic form of the game of Figure 4.20

Figure 4.21 — Figure 4.20-এর strategic form (Nash equilibrium highlight করা)। Player 1-এর $8$টা strategy (তিন রকম অঙ্কের জন্য pass/trade — যেমন PTP = $100 হলে pass, $200 হলে trade, $300 হলে pass), Player 2-এর $2$টা (Y/N)। এই খেলায় কোনো proper subgame নেই, তাই সব Nash equilibrium-ই subgame-perfect।

একটা ঘর কীভাবে এল দেখি — উপরের-বাঁ ঘর, strategy জোড়া (PPP, Y): সব ক্ষেত্রে Player 1 pass করে, তাই কোনো trade হয় না, প্রত্যেকে নিজের খাম রাখে। Player 1-এর প্রত্যাশিত অর্থ $\tfrac{1}{6}(100+100+200+200+300+300) = 200$; Player 2-এরও তাই। এই খেলায় Player 1-এর দুটো weakly dominant strategy — TPP ও TTP; সেগুলো রাখলে Player 2-এর কাছে Y strictly dominated হয়ে পড়ে, তাই সবচেয়ে যুক্তিসঙ্গত equilibrium $(TPP,N)$ ও $(TTP,N)$ — দুটোতেই Player 2 trade-এ রাজি হয় না।

৩. মূল সংজ্ঞা ও উপপাদ্য¶

এবার স্বজ্ঞাগুলোকে আনুষ্ঠানিক ভিত্তি দিই। কিছু পরিভাষা আগে: directed tree-তে node $y$ হলো $x$-এর successor (উত্তরসূরি) (এবং $x$ হলো $y$-এর predecessor (পূর্বসূরি)) যদি $x$ থেকে $y$-তে directed edge-এর একটা ধারা থাকে; একটামাত্র edge হলে immediate (অব্যবহিত)। একটা set $H$-এর partition (বিভাজন) হলো $H$-এর কতগুলো অশূন্য, পরস্পর-বিচ্ছিন্ন উপসেটের সংগ্রহ যাদের মিলন $H$।

৩.১ Extensive-form game-frame ও information set¶

সংজ্ঞা ৩.১ (finite extensive-form game-frame)। এটা নিচের উপাদানগুলো নিয়ে গঠিত:

একটা finite rooted directed tree;
খেলোয়াড়-সেট $I = \{1, \dots, n\}$ এবং প্রতিটা decision node-এ একজন খেলোয়াড় বসানোর একটা function;
একটা action-সেট $A$ এবং প্রতিটা directed edge-এ একটা action বসানোর function, এই শর্তে যে একই node থেকে বেরোনো দুই edge-এ একই action বসে না;
একটা outcome-সেট $O$ এবং প্রতিটা terminal node-এ একটা outcome বসানোর function;
প্রতিটা খেলোয়াড় $i$-এর জন্য, তার decision node-সমষ্টি $D_i$-এর একটা partition $\mathcal{D}_i$। $\mathcal{D}_i$-এর প্রতিটা উপাদানকে খেলোয়াড় $i$-এর একটা information set বলে, এই শর্তে যে একই information set-এর দুই node-এ available action একই — অর্থাৎ প্রতিটা $D \in \mathcal{D}_i$ ও $x,y \in D$-এর জন্য $x$ ও $y$-এর outdegree সমান এবং তাদের থেকে বেরোনো edge-এ বসানো action-সেট অভিন্ন।

শেষ শর্তটাই নতুন (perfect-information-এ বাকি চারটা ছিল)। perfect information হলো সেই বিশেষ ক্ষেত্র যেখানে প্রতিটা information set singleton; তখন শেষ শর্ত তুচ্ছভাবে সত্য এবং সংজ্ঞা ৩.১ আগের অধ্যায়ের সংজ্ঞায় ফিরে যায়। অন্তত একটা খেলোয়াড়ের অন্তত একটা information set-এ দুই বা বেশি node থাকলে খেলাটা imperfect information-এর।

frame থেকে game পেতে প্রতিটা খেলোয়াড়ের জন্য outcome-গুলোর একটা ranking (ordinal utility) যোগ করি — প্রতিটা terminal node-এ একটা payoff-vector বসিয়ে।

৩.২ Perfect recall — খেলোয়াড় নিজের অতীত মনে রাখে¶

সাহিত্যের প্রায় সব খেলা perfect recall (পূর্ণ স্মৃতি) মানে; আমরাও তা-ই ধরব।

সংজ্ঞা ৩.২ (perfect recall)। একটা extensive form-এর perfect recall আছে যদি:

একই information set-এর দুই node-এর একটা আরেকটার predecessor না হয়; এবং
যদি node $x \in D \in \mathcal{D}_i$ হয় node $y \in D' \in \mathcal{D}_i$-এর predecessor (তাই $D \ne D'$), আর $x$ থেকে $y$-তে যাওয়ার পথে $x$-থেকে-বেরোনো edge-এ action $a$ বসানো থাকে, তবে $D'$-এর প্রতিটা node $z$-এর জন্য $D$-তে এমন একটা predecessor $w$ আছে যেখান থেকে $z$-এর দিকে যাওয়ার পথে $w$-থেকে-বেরোনো edge-এ ওই একই action $a$ বসানো।

সহজ কথায়: খেলোয়াড় সবসময় মনে রাখে সে অতীতে কী জানত এবং নিজে কী action নিয়েছিল।

Examples of violations of perfect recall

Figure 4.2 — perfect recall ভাঙার দুই উদাহরণ। Panel (i)-এ Player 1 আগে $a$/$b$ বাছে, পরে $c$/$d$ বাছার সময় ভুলে যায় সে আগে কী বেছেছিল (নিজের action ভুলে যাওয়া)। Panel (ii)-এ Player 2 যখন $e$/$f$ বাছে তখন নিশ্চিত নয় এটা তার প্রথমবার চাল নাকি দ্বিতীয়বার (নিজে আগে চাল দিয়েছিল কিনা তা ভুলে যাওয়া)।

৩.৩ Strategy¶

সংজ্ঞা ৩.৩ (strategy)। extensive-form game-এ একটা খেলোয়াড়ের strategy হলো একটা পছন্দের তালিকা — ওই খেলোয়াড়ের প্রতিটা information set-এর জন্য একটা করে পছন্দ।

তাই খেলোয়াড় $i$-এর strategy-সংখ্যা হলো তার information set-গুলোয় available action-সংখ্যার গুণফল: যদি তার information set $D_1, \dots, D_k$-এ যথাক্রমে $m_1, \dots, m_k$টা action থাকে, strategy-সংখ্যা $m_1 \cdot m_2 \cdots m_k$।

৩.৪ Subgame¶

কোনো decision node $x$-এর জন্য $S(x)$ = $x$ ও তার সব successor-এর সেট।

সংজ্ঞা ৩.৪ (subgame)। $S(x)$ হলো $x$-থেকে-শুরু একটা subgame যদি:

$x$-কে ধারণকারী information set singleton $\{x\}$, এবং
প্রতিটা information set $D$-এর জন্য, $D \cap S(x) \ne \varnothing$ হলে $D \subseteq S(x)$ (অর্থাৎ কোনো information set "কাটা" পড়ে না)।

$x$ root না হলে $S(x)$ একটা proper subgame। একটা subgame $S(x)$ minimal যদি তার ভেতরে আর কোনো subgame কঠোরভাবে না থাকে — অর্থাৎ $x$-এর এমন কোনো successor $y \ne x$ নেই যেখানে $S(y) \subset S(x)$ নিজেই একটা subgame।

৩.৫ Subgame-perfect equilibrium ও অ্যালগরিদম¶

কোনো strategy profile $s$ আর subgame $G$ দিলে, $s$-এর $G$-তে restriction (সীমাবদ্ধতা) $s|_G$ হলো $s$-এর সেই অংশ যা $G$-এর প্রতিটা (এবং কেবল সেই) information set-এ পছন্দ নির্দেশ করে। ($G$ পুরো খেলা হলে $s|_G = s$।)

সংজ্ঞা ৩.৫ (subgame-perfect equilibrium)। strategy profile $s$ হলো subgame-perfect equilibrium যদি প্রতিটা subgame $G$-এর জন্য $s|_G$ ওই $G$-এর একটা Nash equilibrium হয়।

যেহেতু পুরো খেলা নিজেই একটা subgame, তাই সরাসরি পাই একটা মৌলিক ফল।

উপপাদ্য ৩.৬। প্রতিটা subgame-perfect equilibrium গোটা খেলার একটা Nash equilibrium। অর্থাৎ $\text{SPE} \subseteq \text{NE}$।

প্রমাণ। ধরি $s$ একটা subgame-perfect equilibrium। গোটা খেলা $\Gamma$ নিজেই একটা subgame (root থেকে শুরু, সব information set ভেতরে, কিছু কাটে না)। সংজ্ঞা ৩.৫ অনুযায়ী প্রতিটা subgame $G$-তে $s|_G$ একটা Nash equilibrium — বিশেষ করে $G = \Gamma$-তেও। কিন্তু $s|_\Gamma = s$। সুতরাং $s$ গোটা খেলার একটা Nash equilibrium। $\square$

উপপাদ্য ৩.৭। যদি খেলার কোনো proper subgame না থাকে, তবে subgame-perfect equilibrium-এর সেট আর Nash equilibrium-এর সেট অভিন্ন।

প্রমাণ। proper subgame না থাকলে একমাত্র subgame গোটা খেলা $\Gamma$। তখন "$s$ subgame-perfect" মানে "প্রতিটা subgame $G$-তে $s|_G$ Nash equilibrium", কিন্তু একমাত্র $G = \Gamma$, আর $s|_\Gamma = s$। সুতরাং শর্তটা ঠিক "$s$ হলো $\Gamma$-এর Nash equilibrium"-এর সমতুল্য। তাই দুই সেট এক। $\square$

সাধারণভাবে (proper subgame থাকলে) $\text{SPE} \subsetneq \text{NE}$ হতে পারে — subgame-perfect equilibrium তখন Nash equilibrium-এর একটা কঠোর refinement, যা অবিশ্বাসযোগ্য-হুমকি-নির্ভর Nash equilibrium ছেঁটে ফেলে (যেমন Figure 4.9-এর $((a,C),(d,f,E),(h,B))$)।

সংজ্ঞা ৩.৮ (subgame-perfect equilibrium অ্যালগরিদম)। খেলা $\Gamma$-এর জন্য:

ধাপ ১। $\Gamma$-এর একটা minimal subgame $G$ চিহ্নিত করো।
- (i) $G = \Gamma$ হলে (কোনো proper subgame নেই), subgame-perfect equilibrium-এর সেট = Nash equilibrium-এর সেট।
- (ii) $G$ proper এবং তার কোনো Nash equilibrium না থাকলে, $\Gamma$-এর কোনো subgame-perfect equilibrium নেই।
- (iii) $G$ proper এবং তার এক বা একাধিক Nash equilibrium থাকলে, একটা বেছে ধাপ ২-এ যাও।
ধাপ ২। minimal proper subgame $G$ মুছে তার জায়গায় বেছে-নেওয়া Nash equilibrium-এর payoff-vector বসাও (কোন strategy বেছেছ তা টুকে রাখো)। এতে ছোট একটা খেলা মেলে।
ধাপ ৩। ছোট খেলায় ধাপ ১–২ পুনরাবৃত্তি করো, যতক্ষণ না খেলা এমন $\Gamma'$-এ নামে যার কোনো proper subgame নেই। $\Gamma'$-এর Nash equilibrium না থাকলে $\Gamma$-এর subgame-perfect equilibrium নেই; থাকলে একটা বেছে, টুকে-রাখা strategy-গুলো জুড়ে $\Gamma$-এর একটা strategy profile $s$ গড়ো — এটাই একটা subgame-perfect equilibrium।

কোনো ধাপে একাধিক Nash equilibrium থাকলে ভিন্ন ভিন্ন বেছে পুরো প্রক্রিয়া আবার চালিয়ে ভিন্ন subgame-perfect equilibrium পাওয়া যায়।

উপপাদ্য ৩.৯। perfect-information খেলায় subgame-perfect equilibrium ঠিক backward-induction সমাধানের সমান — তাই subgame-perfect equilibrium হলো backward induction-এর সাধারণীকরণ।

ন্যায্যতা। perfect-information-এ প্রতিটা decision node singleton information set, তাই প্রতিটা node থেকে শুরু হওয়া subtree একটা subgame; বিশেষ করে খেলার শেষের-দিকের প্রতিটা "শুধু terminal node-এ শেষ হওয়া" node একটা minimal subgame। সংজ্ঞা ৩.৮-এর অ্যালগরিদম তখন হুবহু backward induction: প্রতিটা শেষ-decision node-এ সেই খেলোয়াড়ের সেরা action বেছে payoff দিয়ে প্রতিস্থাপন করা, তারপর উপরে ওঠা। যেহেতু প্রতিটা singleton subgame-এ "Nash equilibrium" মানে ওই একক খেলোয়াড়ের payoff-সর্বোচ্চকারী পছন্দ, দুই প্রক্রিয়া একই সমাধান দেয়। $\square$

৩.৬ Chance moves, lottery ও risk neutrality¶

সংজ্ঞা ৩.১০ (chance move)। extensive form-এ একটা chance move হলো কাল্পনিক খেলোয়াড় Nature-এর একটা node, যার বেরোনো edge-গুলোয় একটা probability distribution বসানো (যোগফল $1$)। Nature-কে কোনো payoff দেওয়া হয় না; সে দৈব ঘটনা ঘটায় মাত্র।

chance move থাকলে একটা strategy profile-এর outcome একটা lottery (লটারি) — সম্ভাব্য outcome-এর একটা probability distribution।

সংজ্ঞা ৩.১১ (money lottery ও expected value)। যেসব lottery-র outcome অর্থ, তাদের money lottery বলি। একটা money lottery যেখানে $x_1, \dots, x_n$ ডলার আসে যথাক্রমে $p_1, \dots, p_n$ সম্ভাবনায় ($p_i \ge 0$, $\sum_i p_i = 1$), তার expected value

\[ x_1 p_1 + x_2 p_2 + \cdots + x_n p_n. \]

সংজ্ঞা ৩.১২ (risk neutrality)। একজন খেলোয়াড় risk neutral যদি সে একটা money lottery-কে তার expected value-এর ঠিক সমান-ভালো গণ্য করে — অর্থাৎ money lottery-গুলোকে সে expected value অনুযায়ী র‍্যাঙ্ক করে।

উদাহরণ: lottery $L_1$-এ $5, $15, $25 আসে $\tfrac{1}{5}, \tfrac{2}{5}, \tfrac{2}{5}$ সম্ভাবনায়; expected value $5(\tfrac{1}{5}) + 15(\tfrac{2}{5}) + 25(\tfrac{2}{5}) = 1 + 6 + 10 = 17$ ডলার। risk-neutral খেলোয়াড়ের কাছে এই lottery ঠিক নিশ্চিত $17-এর সমান। (সতর্কতা: risk neutrality ধরে-নেওয়া মানে এই নয় যে যুক্তিবাদী মানুষ risk neutral হওয়া উচিত; এটা কেবল সরলতম ক্ষেত্র, যাতে পরের অধ্যায়ের ভারী Expected Utility Theory ছাড়াই এগোনো যায়।)

৪. উদাহরণ ও Analogy¶

৪.১ তিনটা ধারণার তিনটা Analogy¶

information set = "চোখ-বাঁধা মোড়"। কল্পনা করো তুমি একটা গোলকধাঁধায় দুটো একই-দেখতে মোড়ে দাঁড়িয়ে, চোখ বাঁধা — জানো তুমি "কোনো একটা" মোড়ে, কিন্তু কোনটায় জানো না। যেহেতু দুই মোড় তোমার কাছে অভিন্ন, তোমাকে একই সিদ্ধান্ত (বাঁয়ে/ডানে) নিতে হবে। এটাই information set: একই খেলোয়াড়ের অভেদ্য কতগুলো node, তাই একই action।
subgame = "বাক্সের ভেতর ছোট আস্ত বাক্স"। subgame এমন একটা টুকরো যা তুলে এনে একা রাখলেও একটা পূর্ণ খেলা — তার নিজের root (singleton), নিজের গাছ, নিজের payoff। শর্ত: কোনো information set যেন অর্ধেক ভেতরে অর্ধেক বাইরে না থাকে; নাহলে "কে কী জানে" ভেঙে যায়, আর টুকরোটা একা দাঁড়াতে পারে না।
subgame-perfect equilibrium = "প্রতিটা মোড়ে বিশ্বাসযোগ্য পরিকল্পনা"। Nash equilibrium শুধু বলে "শুরু থেকে দেখলে কেউ একা সরে লাভ করবে না"; কিন্তু তা এমন হুমকির উপর দাঁড়াতে পারে যা খেলার মাঝপথে গিয়ে খেলোয়াড় নিজেই পালন করতে চাইবে না (non-credible)। subgame-perfect equilibrium সেই ফাঁকি বন্ধ করে — প্রতিটা subgame-এও পরিকল্পনা optimal, তাই কোনো ফাঁপা হুমকি টেকে না।

৪.২ Chance move-এ প্রত্যাশিত payoff — হাতে-কলমে¶

Figure 4.18-এর Adele/Ben খেলায় ধরি Adele সত্যবাদী (strategy $(B,R)$: কালো দেখলে "Black", লাল দেখলে "Red") আর Ben সবসময় "Black" আন্দাজ করে (strategy $(B,B)$)। Ben ঠিক হলে Adele $9 হারায়; ভুল হলে $9 পায়।

উপরের তাস কালো (সম্ভাবনা $\tfrac{1}{3}$): Adele বলে "Black", Ben আন্দাজ করে "Black" → Ben ঠিক → Adele-এর $-9$।
উপরের তাস লাল (সম্ভাবনা $\tfrac{2}{3}$): Adele বলে "Red", Ben আন্দাজ করে "Black" → Ben ভুল → Adele-এর $+9$।

তাই Adele-এর প্রত্যাশিত payoff

\[ \tfrac{1}{3}(-9) + \tfrac{2}{3}(+9) = -3 + 6 = 3, \]

আর Ben-এর $-3$ (খেলাটা অর্থে zero-sum)। ঠিক এই সংখ্যাই Figure 4.19-এর $(BR, BB)$ ঘরে বসে, এবং ৫ নং অংশে Python দিয়েও এটাই যাচাই করব।

৪.৩ খাম-খেলায় প্রত্যাশিত মান — হাতে-কলমে¶

Figure 4.20-এ strategy জোড়া (PPP, Y): Player 1 সবসময় pass করে, তাই কেউ খাম বদলায় না। Nature সমসম্ভাব্য ($\tfrac{1}{6}$) ভাগে Player 1-কে দেয় $100, $100, $200, $200, $300, $300 (ছয়টা সজ্জায়)। risk-neutral Player 1-এর কাছে এটা সমান

\[ \tfrac{1}{6}(100 + 100 + 200 + 200 + 300 + 300) = \tfrac{1}{6}(1200) = 200 \]

ডলার — অর্থাৎ নিশ্চিত $200। Player 2-এরও একই যুক্তিতে $200। যেহেতু এই খেলায় কোনো proper subgame নেই, তার সব Nash equilibrium-ই subgame-perfect।

৫. Python-এ করো¶

দুটো ছোট প্রোগ্রাম: (ক) chance-move খেলায় (Adele/Ben) risk-neutral expected payoff থেকে strategic form ও pure-strategy Nash equilibrium; (খ) perfect-information game tree-তে backward induction চালিয়ে subgame-perfect payoff।

(ক) Chance move — expected payoff, strategic form ও Nash equilibrium।

from itertools import product
from fractions import Fraction as F

# Nature: উপরের তাস Black সম্ভাবনা 1/3, Red সম্ভাবনা 2/3
prob = {"B": F(1, 3), "R": F(2, 3)}
# strategy = (কালো দেখলে/'B' শুনলে কী, লাল দেখলে/'R' শুনলে কী)
strats = ["BB", "BR", "RB", "RR"]

def adele_payoff(a, b):
    # a = Adele-এর strategy, b = Ben-এর strategy ; ফেরত Adele-এর expected money
    tot = F(0)
    for c in ("B", "R"):                        # আসল রং
        said  = a[0] if c == "B" else a[1]      # Adele কী বলল
        guess = b[0] if said == "B" else b[1]   # ওই কথা শুনে Ben-এর আন্দাজ
        money = 9 if guess != c else -9         # Ben ভুল করলে Adele +9
        tot += prob[c] * money
    return tot

# strategic form ছাপাই (সারি = Adele, কলাম = Ben)
print("      " + "  ".join(f"{b:>4}" for b in strats))
for a in strats:
    print(f"{a:>4}  " + "  ".join(f"{str(adele_payoff(a, b)):>4}" for b in strats))

# pure-strategy Nash equilibrium (zero-sum: Adele সর্বোচ্চ চায়, Ben সর্বনিম্ন)
nash = []
for a, b in product(strats, strats):
    v = adele_payoff(a, b)
    adele_ok = all(adele_payoff(a2, b) <= v for a2 in strats)  # Adele উন্নতি করতে পারে না
    ben_ok   = all(adele_payoff(a, b2) >= v for b2 in strats)  # Ben আরও নামাতে পারে না
    if adele_ok and ben_ok:
        nash.append((a, b, v))
print("pure-strategy Nash equilibria:", nash)

# আউটপুট:
#         BB    BR    RB    RR
#   BB     3     3    -3    -3
#   BR     3    -9     9    -3
#   RB     3     9    -9    -3
#   RR     3    -3     3    -3
# pure-strategy Nash equilibria: [('BB', 'RR', Fraction(-3, 1)), ('RR', 'RR', Fraction(-3, 1))]

লক্ষ করো — দুটো pure Nash equilibrium, দুটোতেই Adele পায় $-3$ আর Ben পায় $+3$। কারণ Ben-এর "সবসময় Red আন্দাজ" (RR) শক্তিশালী: Red বেশি সম্ভাব্য ($\tfrac{2}{3}$), তাই RR-এ Ben প্রত্যাশায় জেতে। (তুলনায়, নকলের খেলার মতো অনেক imperfect-info খেলায় কোনো pure Nash equilibrium থাকেই না — তখন mixed strategy লাগে, যা Part II-এর বিষয়।)

(খ) Backward induction — perfect-information game tree-তে subgame-perfect payoff।

# node = ("খেলোয়াড়", {action: child}) ; leaf = payoff-tuple (প্রতি খেলোয়াড় একটা)
game = ("1", {
    "a": (0, 0),                                   # a -> terminal
    "b": ("2", {"c": (2, 0), "d": (2, 1)}),        # b -> Player 2-এর minimal subgame
})

def backward_induction(node):
    # ফেরত (payoff_vector, বাছা_action_বা_None)
    if isinstance(node, tuple) and isinstance(node[0], str):
        player, moves = node
        idx = int(player) - 1                      # ওই খেলোয়াড়ের index
        best_act, best_pay = None, None
        for act, child in moves.items():
            pay, _ = backward_induction(child)     # subgame আগে সমাধান করো (ভেতর থেকে)
            if best_pay is None or pay[idx] > best_pay[idx]:
                best_pay, best_act = pay, act      # নিজের payoff সর্বোচ্চকারী action
        return best_pay, best_act
    return node, None                              # leaf: payoff নিজেই

pay, act = backward_induction(game)
print("Player 1 বাছে:", act, "; subgame-perfect payoff:", pay)
# আউটপুট:
# Player 1 বাছে: b ; subgame-perfect payoff: (2, 1)

এই ক্ষুদে solver ঠিক ২.৪-এর অ্যালগরিদম করে: ভেতরের (minimal) subgame আগে সমাধান করে, তার payoff দিয়ে উপরে ওঠে। এখানে Player 2 বাছে $d$ (payoff $(2,1)$), তাই Player 1 বাছে $b$ ($2 > 0$) — subgame-perfect equilibrium $(b, d)$, যা চিত্র ২.৩-এর সঙ্গে মেলে।

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

information set-এ ভিন্ন action রাখা। একই information set-এর সব node-এ available action অভিন্ন হতে হবে; নাহলে খেলোয়াড় action গুনেই বুঝে ফেলবে সে কোন node-এ — অনিশ্চয়তা ভেঙে যায়, সংজ্ঞাও লঙ্ঘিত হয়।
strategy-কে node-ভিত্তিক ভাবা। সাধারণ খেলায় strategy হলো প্রতিটা information set-এ একটা করে পছন্দ, প্রতিটা node-এ নয়। Yvonne "প্রথমে ডাকলে Yes, recycled ডাকলে No" পরিকল্পনা করতে পারে না — কারণ দুটো একই information set-এ।
যেকোনো node থেকে subgame শুরু করা। subgame কেবল singleton node থেকে শুরু হয় এবং কোনো information set কাটতে পারে না। বড় information set-এর ভেতরের কোনো node থেকে subgame হয় না (Figure 4.8-এর $y$)।
সব Nash equilibrium-কে subgame-perfect ভাবা। proper subgame থাকলে কিছু Nash equilibrium subgame-perfect নয় (Figure 4.9-এর $((a,C),(d,f,E),(h,B))$) — তারা অবিশ্বাসযোগ্য হুমকির উপর দাঁড়ানো। subgame-perfect equilibrium হলো Nash-এর refinement।
backward induction উপর থেকে করা। অ্যালগরিদম ভেতর থেকে বাইরে — minimal subgame আগে, তারপর ভাঁজ করে উপরে। উপর থেকে শুরু করলে ভুল হয়।
একাধিক subgame-equilibrium উপেক্ষা করা। কোনো subgame-এ একাধিক Nash equilibrium থাকলে প্রতিটা আলাদা subgame-perfect equilibrium দেয় (Figure 4.16-এর দুটো) — একটাতে থেমে যেয়ো না।
Nature-কে payoff দেওয়া। chance move-এ Nature-এর কোনো payoff নেই এবং সে কৌশলে চাল দেয় না — সে কেবল স্থির probability distribution অনুযায়ী দৈব ঘটনা ঘটায়।
lottery-কে সরাসরি সংখ্যায় নামানো, risk-attitude ছাড়া। money lottery থেকে payoff পেতে খেলোয়াড়ের risk-attitude লাগে; আমরা risk neutral ধরি বলেই expected value = utility। এটা একটা ধরে-নেওয়া, সর্বজনীন সত্য নয়।
"proper subgame নেই" মানে "সমাধান নেই" ভাবা। proper subgame না থাকলে subgame-perfect equilibrium-এর সেট কেবল Nash equilibrium-এর সেটের সমান হয়ে যায় (উপপাদ্য ৩.৭) — সমাধান আছে, শুধু refinement বাড়তি কিছু ছাঁটে না।

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

(সহজ, নিজের) একটা দৃশ্য: A আগে একটা লুকানো চাল দেয় (H বা T), তারপর B সেই চাল না দেখে নিজের চাল (h বা t) দেয়; মিললে A জেতে, নাহলে B। (ক) এটা perfect নাকি imperfect information? (খ) B-এর information set কী? (গ) A ও B-এর প্রত্যেকের কয়টা strategy? তোমার যুক্তি লেখো।
(সহজ, নিজের) একটা money lottery-তে $0, $30, $60 আসে যথাক্রমে $\tfrac{1}{2}, \tfrac{1}{3}, \tfrac{1}{6}$ সম্ভাবনায়। (ক) expected value বের করো। (খ) একজন risk-neutral খেলোয়াড় এটা বনাম নিশ্চিত $18 — কোনটা বাছবে? (গ) chance-move খেলায় এই হিসাব কেন লাগে, এক বাক্যে বলো।
(মাঝারি, Bonanno 4.1 ও 4.3) Amy ও Bill একসাথে কাগজে bid লেখে — শুধু $2 বা $3। referee সর্বনিম্ন bid ঘোষণা করে (কে দিয়েছে না বলে) এবং Amy-কে pass বা bid দ্বিগুণ করতে বলে। বেশি bidder বস্তু পায় ও নিজের bid দেয়; সমান হলে Bill পায়। (ক) দুটো ভিন্ন extensive-form frame-এ আঁকো (একবার Amy আগে, একবার Bill আগে)। (খ) frame-এর strategic form লেখো (ঘরে payoff-এর বদলে outcome) এবং দেখাও দুই version-এর strategic form অভিন্ন।
(মাঝারি, Bonanno 4.2 ও 4.4) এক incumbent (প্রতিষ্ঠিত) প্রথমে small নাকি large plant বানাবে ঠিক করে; entrant তা দেখে ঢুকবে (In) কি ঢুকবে না (Out) ঠিক করে; ঢুকলে $K$ ব্যয়; তারপর দুই firm একসাথে high/low output বাছে। (ক) extensive-form খেলা আঁকো। (খ) entrant-এর কয়টা strategy? (গ) strategic form লেখো। (ঘ) $K = 2$-এর Nash equilibrium-গুলো বের করো।
(মাঝারি, Bonanno 4.5–4.8) (ক) Figure 4.3-এর কয়টা proper subgame? (খ) Figure 4.5-এর কয়টা? (গ) নিচের Figure 4.22-এ কয়টা proper subgame, তার কয়টা minimal? (ঘ) Figure 4.23-এ কয়টা proper subgame, কয়টা minimal?

Figure 4.22 — প্রশ্ন ৫(গ)-এর খেলা।

Figure 4.23 — প্রশ্ন ৫(ঘ)-এর খেলা।
(মাঝারি, Bonanno 4.9) নিচের Figure 4.24-এর খেলার সব Nash equilibrium ও সব subgame-perfect equilibrium বের করো।

Figure 4.24 — প্রশ্ন ৬-এর খেলা।
(কঠিন, Bonanno 4.10) নিচের Figure 4.25-এর খেলার subgame-perfect equilibrium-গুলো বের করো।

Figure 4.25 — প্রশ্ন ৭-এর খেলা।
(কঠিন, Bonanno 4.11) নিচের Figure 4.26-এর নিলাম-খেলায় subgame-perfect equilibrium বের করো, ধরে-নিয়ে Amy ও Bill দুজনেই selfish-greedy (নিজের net gain-এ আগ্রহী), Amy বস্তুটিকে $5 আর Bill $4 মূল্য দেয়।

Figure 4.26 — প্রশ্ন ৮-এর নিলাম-খেলা।
(কঠিন, Bonanno 4.12 ও 4.13) (ক) উদাহরণ ৪.৩-এর খাম-খেলা বদলাও: Player 2-ও এবার নিজের খাম গোপনে দেখতে পায় সিদ্ধান্তের আগে — extensive-form frame আঁকো ও দুই খেলোয়াড়ের strategy-সংখ্যা বলো। (খ) তিন খেলোয়াড় Avinash, Brian, John: Brian তাস দেখে Avinash-এর কানে "Black"/"Red" ফিসফিস করে, Avinash John-কে "Black"/"Red" বলে, John চূড়ান্ত ঘোষণা করে; John ঠিক হলে Brian ও Avinash তাকে $2 করে দেয়, নাহলে John তাদের $2 করে দেয় — extensive-form frame আঁকো ও (risk-neutral ধরে) strategic form-এর গঠন ব্যাখ্যা করো।
(চ্যালেঞ্জ, Bonanno 4.14 ও 4.15) (ক) সরলীকৃত Poker: তিন তাস A>B>C, দুই খেলোয়াড় Yvonne ও Zoe প্রত্যেকে $1 pot-এ দেয়, প্রত্যেকে নিজের তাস দেখে; Yvonne pass/bet, bet করলে Zoe fold/see — extensive form আঁকো, প্রত্যেকের strategy-সংখ্যা বলো। (খ) সরকার একটা প্রাসাদ Chinese-এর কাছে $p-তে বেচবে নাকি $n \ge 2$ জনের second-price নিলাম করবে — $n=2$, bid $\in \{1,2\}$-এর extensive form আঁকো এবং সাধারণ $n$-এর জন্য একটা pure-strategy subgame-perfect equilibrium বের করো।

৮. সমাধান¶

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

(ক) এটা imperfect information — B, A-এর লুকানো চাল না দেখেই চাল দেয়, তাই B নিশ্চিত নয় সে গাছের কোন node-এ।

(খ) A-এর দুই সম্ভাব্য চাল (H, T) B-এর দুটো decision node তৈরি করে; B এদের আলাদা করতে পারে না, তাই এই দুটো node একটাই information set-এ (গোল-কোণা আয়তক্ষেত্রে ঘেরা)। শর্ত মানা: দুই node-এই action অভিন্ন {h, t}।

(গ) A-এর একটা decision node (root), তাই strategy $2$টা (H, T)। B-এর একটামাত্র information set, তাতে $2$টা action, তাই strategy $2$টা (h, t)। এটা আসলে matching-pennies-এর extensive রূপ — এর কোনো pure-strategy Nash equilibrium নেই।

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

(ক) expected value

\[ 0 \cdot \tfrac{1}{2} + 30 \cdot \tfrac{1}{3} + 60 \cdot \tfrac{1}{6} = 0 + 10 + 10 = 20, \]

অর্থাৎ $20।

(খ) risk-neutral খেলোয়াড় lottery-কে তার expected value $20-এর সমান গণ্য করে; যেহেতু $20 > 18$, সে lottery-ই বাছবে।

(গ) chance move থাকলে একটা strategy-জোড়ার outcome একটা money lottery হয়ে যায়; সেই lottery-কে একটা সংখ্যায় (payoff) নামাতেই expected value লাগে (risk-neutral ধরে)।

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

(ক) একটা সম্ভাব্য frame — Amy আগে চাল দেয়:

One possible game-frame for Exercise 4.1

Figure 4.27 — Amy আগে চাল দেওয়ার version। Amy-এর কেবল একটা non-trivial information set (বাঁয়ের দুই node), বাকি তিনটা singleton। কারণ: Amy $3 দিয়ে থাকলে referee "সর্বনিম্ন $2" ঘোষণা করলে Amy নিজের $3 জেনে বুঝে যায় Bill $2 দিয়েছে (তাই ওই node singleton); একইভাবে "সর্বনিম্ন $3" শুনলে বোঝে Bill-ও $3। কেবল Amy $2 দিয়ে "সর্বনিম্ন $2" শুনলে সে বুঝতে পারে না Bill $2 না $3 দিয়েছে — সেই দুই node এক information set-এ।

আরেকটা সম্ভাব্য frame — Bill আগে:

Another possible game-frame for Exercise 4.1

Figure 4.28 — Bill আগে চাল দেওয়ার version। গুরুত্বপূর্ণ হলো দ্বিতীয় খেলোয়াড় প্রথমজনের চাল সরাসরি দেখে না; দুই version আলাদা দেখালেও একই কৌশলগত পরিস্থিতি ধরে।

(খ) strategic form-এ (outcome সহ) — Amy-এর strategy $(x,y,w,z)$ মানে: শুরুতে $x bid, বাঁ non-trivial information set-এ $y$, মাঝের singleton-এ $w$, ডান singleton-এ $z$ (P = Pass)।

The strategic form for Exercise 4.3

Figure 4.30 — Exercise 4.3-এর strategic form (ঘরে payoff নয়, outcome)। Bill আগে-চালের version-এও ঠিক এই একই strategic form মেলে — কারণ দুই extensive frame একই কৌশলগত পরিস্থিতির দুই উপস্থাপন মাত্র।

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

(ক) খেলোয়াড়েরা selfish-greedy, তাই প্রতিটা outcome-এ payoff = সেই খেলোয়াড়ের মুনাফা:

The extensive-form game for Exercise 4.2

Figure 4.29 — Exercise 4.2-এর extensive-form খেলা। Incumbent আগে small/large plant বাছে; Entrant In/Out বাছে; In হলে দুই firm একসাথে (তাই information set-এ) high/low output বাছে। entry-খরচ $K$ Entrant-এর payoff থেকে বিয়োগ।

(খ) Entrant-এর চারটা information set (small-এ In/Out, large-এ In/Out, এবং দুই ক্ষেত্রে output), প্রতিটায় $2$ পছন্দ, তাই $2^4 = 16$টা strategy।

(গ)–(ঘ) strategic form ও $K=2$-এর ছয়টা Nash equilibrium:

The strategic form for Exercise 4.4

Figure 4.31 — Exercise 4.4-এর strategic form; highlight করা ঘরগুলো $K = 2$-এর ছয়টা Nash equilibrium।

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

(ক) Figure 4.3-এর কোনো proper subgame নেই (Carla-র information set-গুলো বহু-node, আর কোনো singleton-node থেকে শুরু করলে সেই information set কাটা পড়ে)।

(খ) Figure 4.5-এরও কোনো proper subgame নেই (একই কারণ — Yvonne/Fran-এর information set দুই-node)।

(গ) Figure 4.22-এ একটাই proper subgame — Player 2-এর node থেকে; যেহেতু এটাই একমাত্র, এটাই minimal (মোট: $1$টা proper, $1$টা minimal)।

(ঘ) Figure 4.23-এ তিনটা proper subgame: node $x$, node $y$ এবং Player 3-এর node থেকে।

The game considered in Exercise 4.8

Figure 4.32 — Exercise 4.8-এর খেলা। দুটো minimal: $x$-থেকে এবং Player 3-এর node থেকে (perfect-information-এ minimal subgame হলো সেই node যার পরে কেবল terminal)। $y$-থেকেরটা minimal নয়, কারণ তার ভেতরে Player 3-এর subgame ঢুকে আছে।

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

strategic form থেকে গোটা খেলার Nash equilibrium দুটো: $(A,(G,C),E)$ ও $(B,(H,C),F)$।

The strategic form for Exercise 4.9

Figure 4.33 — Exercise 4.9-এর strategic form (Player 3-এর $E$/$F$ অনুযায়ী দুই matrix)। দুটো Nash equilibrium: $(A,(G,C),E)$ ও $(B,(H,C),F)$।

কিন্তু খেলার দুটো proper subgame: বাঁয়েরটার একমাত্র Nash equilibrium $(G,E)$, ডানেরটার একমাত্র $C$। এই দুই subgame ভাঁজ করলে খেলা নামে:

The reduced extensive-form game for Exercise 4.9

Figure 4.34 — subgame দুটো ভাঁজ করার পর ছোট খেলা; এখানে Player 1-এর একমাত্র optimal পছন্দ $A$।

ভাঁজ-করা খেলায় $A$-ই একমাত্র সেরা। তাই একমাত্র subgame-perfect equilibrium $(A,(G,C),E)$ — অন্য Nash equilibrium $(B,(H,C),F)$ subgame-perfect নয় (subgame-এ $H$ বা $F$ optimal নয়)।

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

Player 1-এর $A$-এর পরের Player-2-node-থেকে subgame আগে দেখি; এর একমাত্র Nash equilibrium $(E,H)$:

The strategic form of the subgame after choice A (Exercise 4.10)

Figure 4.35 — $A$-এর পরের subgame-এর strategic form (কেবল Player 2 ও 3-এর payoff); একমাত্র Nash equilibrium $(E,H)$।

এবার $B$-এর পরের subgame; এর দুটো Nash equilibrium $(L,P)$ ও $(M,R)$:

The strategic form of the subgame after choice B (Exercise 4.10)

Figure 4.36 — $B$-এর পরের subgame-এর strategic form; দুটো Nash equilibrium $(L,P)$ ও $(M,R)$।

দুই subgame ভাঁজ করে root-এ Player 1-এর পছন্দ মিলিয়ে দুটো subgame-perfect equilibrium:

Player 1: $A$; Player 2: $A$-এর পরে $E$, $B$-এর পরে $L$; Player 3: $A$-এর পরে $H$, $B$-এর পরে $P$।
Player 1: $B$; Player 2: $A$-এর পরে $E$, $B$-এর পরে $M$; Player 3: $A$-এর পরে $H$, $B$-এর পরে $R$।

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

net gain-এর utility বসাই: Amy $3 দিয়ে জিতলে $2$, $4 দিয়ে $1$, $6 দিয়ে $-1$; Bill $2 দিয়ে জিতলে $2$, $3 দিয়ে $1$ (Amy জিতলে Bill-এর $0$, উল্টোটাও)।

দুটো proper subgame — Amy-এর ডানের দুই singleton node থেকে। দুটোতেই Amy pass করে (সে বস্তুকে $5 মূল্য দেয়, তাই $6 দিতে রাজি নয়)। এই দুই node-কে যথাক্রমে payoff $(2,0)$ ও $(0,1)$ দিয়ে প্রতিস্থাপন করে ছোট খেলা:

The reduced game for Exercise 4.11

Figure 4.37 — Amy-এর দুই singleton node-কে terminal বানিয়ে (pass-এর ফল বসিয়ে) পাওয়া ছোট খেলা।

ছোট খেলার strategic form-এ একমাত্র Nash equilibrium হলো Amy-এর ($2, $4) বনাম Bill-এর $3। তাই মূল খেলার একমাত্র subgame-perfect equilibrium: Amy-এর strategy ($2, $4, pass, pass), Bill-এর $3। ফল: Amy নিলাম জেতে এবং $4 দেয়।

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

(ক) Player 2-ও নিজের খাম দেখলে খেলাটা এই extensive form হয়:

The extensive-form game for Exercise 4.12

Figure 4.38 — Exercise 4.12-এর খেলা। Player 1-এর strategy আগের মতোই ($8$টা)। কিন্তু Player 2 এখন $8$টা strategy পায় — কারণ তার হাতে থাকা অঙ্ক ($100/$200/$300) অনুযায়ী Yes/No বলতে পারে (যেমন $100 হলে No, $200 হলে Yes, $300 হলে No)।

(খ) তিন খেলোয়াড়ের তাস-খেলার frame:

The extensive-form game for Part (a) of Exercise 4.13

Figure 4.39 — Exercise 4.13-এর extensive-form frame। Nature আগে Black/Red ($\tfrac{1}{2}$ করে) বাছে; Brian দেখে বলে; Avinash শোনে ও বলে; John শোনে ও ঘোষণা করে। প্রত্যেকের দুটো information set (কী শুনেছে অনুযায়ী), প্রতিটায় দুই পছন্দ — তাই চারটা করে strategy।

The strategic form for Part (b) of Exercise 4.13

Figure 4.40 — Exercise 4.13-এর strategic form (John-এর চার strategy অনুযায়ী চারটা matrix)। risk-neutral ধরে প্রতিটা ঘর expected value। মূল সরলীকরণ: John সবসময় একই রং (Black বা Red) আন্দাজ করলে সে $\tfrac{1}{2}$ সম্ভাবনায় ঠিক হয়, তাই সবার expected payoff $(0,0,0)$ — এজন্য দুটো গোটা matrix $(0,0,0)$-তে ভরা।

বাকি ঘরগুলোর দ্রুত হিসাব: প্রতিটা রঙের নিচে T (সত্য) বা F (মিথ্যা) বসিয়ে, Brian→Avinash→John-এর strategy অনুযায়ী T/F উল্টে-পাল্টে শেষ সারিতে T হলে payoff $(-2,-2,4)$, F হলে $(2,2,-4)$; ঘরের payoff = $\tfrac{1}{2}$(বাঁ কলাম) $+ \tfrac{1}{2}$(ডান কলাম)।

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

(ক) সরলীকৃত Poker-এর extensive form:

The extensive-form game for Exercise 4.14

Figure 4.42 — Exercise 4.14-এর Poker। Nature ছয়টা সমসম্ভাব্য ($\tfrac{1}{6}$) তাস-বণ্টন দেয়; উপরের সংখ্যা Yvonne-এর net, নিচেরটা Zoe-এর। Yvonne-এর তিন information set (A/B/C দেখে), প্রতিটায় pass/bet — তাই $2^3 = 8$টা strategy; একইভাবে Zoe-রও $8$টা (bet হলে A/B/C-তে fold/see)।

(খ) সরকার-বনাম-নিলাম খেলার $n=2$, bid $\in\{1,2\}$ extensive form:

The extensive form for Part (a) of Exercise 4.15

Figure 4.44 — Exercise 4.15 (Scenario 1)-এর extensive form ($n=2$, bid $1/$2, second-price)। payoff-ক্রম: G, তারপর 1, তারপর 2।

সাধারণ $n$-এর subgame-perfect equilibrium। নিলাম-subgame-এ প্রত্যেকের weakly dominant strategy নিজের মূল্য bid করা (second-price বলে)। ধরি $p_j = \max\{p_1,\dots,p_n\}$ সর্বোচ্চ, $p_k$ দ্বিতীয়-সর্বোচ্চ মূল্য। তাহলে নিলাম হলে Player $j$ জেতে ও $p_k$ দেয়। তিন ক্ষেত্র: $p > p_k$ হলে G Chinese-এর কাছে বেচে (payoff $p$, বাকিদের $0$); $p < p_k$ হলে G নিলাম করে (G পায় $p_k$, Player $j$ পায় $p_j - p_k$, বাকিদের $0$); $p = p_k$ হলে দুই equilibrium, G উদাসীন।

Scenario 2-এর (participation fee-সহ) সম্প্রসারিত রূপ ও তার সমাধান-চিত্র:

The extensive-form game for Part (c) of Exercise 4.15

Figure 4.45 — Scenario 2-এর extensive form: প্রথমে Player 2, পরে Player 1 নিলামে অংশ নেবে কিনা ($1 fee) বলে; দুজনেই Yes হলে second-price নিলাম, একজন হলে খামে $x, কেউ না হলে G Chinese-এর কাছে বেচে।

The extensive-form game for Part (d) of Exercise 4.15

Figure 4.46 — Scenario 2-এর ভাঁজ-করা রূপ (Panel A ও B)। fee sunk cost, তাই নিলামে সত্য-মূল্য bid weakly dominant: Player 1 জেতে ও $p_2$ দেয়। ভাঁজ করে দেখা যায় Player 2 শেষে No বলে; subgame-perfect equilibrium: $p>2$ হলে G Chinese-কে বেচে (payoff $(p,0,0)$), $p<2$ হলে G নিলাম করে, Player 2 No, Player 1 Yes বলে $1 offer দেয় (payoff $(2, p_1-2, 0)$), $p=2$ হলে দুই equilibrium।

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

imperfect information ও information set: খেলোয়াড় সবসময় জানে না সে গাছের কোন node-এ; একই খেলোয়াড়ের অভেদ্য node-গুলো এক information set-এ বাঁধা, তাই সেখানে একই action। singleton information set = perfect information।
extensive-form game-frame: tree + খেলোয়াড় + action + outcome + information-set partition (একই set-এ অভিন্ন action)। frame + payoff = game। সাহিত্যের খেলা perfect recall মানে।
strategy: প্রতিটা information set-এ একটা করে পছন্দ; strategy-সংখ্যা = information set-গুলোর action-সংখ্যার গুণফল। extensive → strategic form বানিয়ে Nash equilibrium খোঁজা যায়।
subgame: singleton node থেকে শুরু, কোনো information set কাটে না। proper (পুরো খেলা বাদে), minimal (ভেতরে আর subgame নেই)।
subgame-perfect equilibrium: প্রতিটা subgame-এ Nash equilibrium। $\text{SPE} \subseteq \text{NE}$ (উপপাদ্য ৩.৬); proper subgame না থাকলে $\text{SPE} = \text{NE}$ (উপপাদ্য ৩.৭); perfect information-এ = backward induction (উপপাদ্য ৩.৯)।
অ্যালগরিদম: minimal subgame-এর Nash equilibrium বের করো → তার payoff দিয়ে প্রতিস্থাপন করো → ছোট খেলায় পুনরাবৃত্তি। একাধিক NE থাকলে একাধিক SPE; কোনো subgame-এ NE না থাকলে SPE নেই।
chance moves: কাল্পনিক খেলোয়াড় Nature (payoff নেই, স্থির probability)। strategy-জোড়ার outcome হয় money lottery; risk-neutral খেলোয়াড় তাকে expected value দিয়ে র‍্যাঙ্ক করে, তাই expected value = utility।

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

[ ] একটা দৃশ্য দেখে বলতে পারি এটা perfect নাকি imperfect information, এবং সঠিক information set এঁকে দেখাতে পারি।
[ ] extensive-form game-frame-এর পাঁচটা উপাদান ও information set-এর "অভিন্ন action" শর্ত বলতে পারি; perfect recall-এর অর্থ বোঝাতে পারি।
[ ] একটা খেলোয়াড়ের strategy-সংখ্যা (information set-প্রতি action-এর গুণফল) হিসাব করতে পারি এবং extensive থেকে strategic form বানাতে পারি।
[ ] কোন অংশ subgame আর কোনটা নয় (singleton শুরু + information set না-কাটা) যাচাই করতে পারি; proper ও minimal আলাদা করতে পারি।
[ ] subgame-perfect equilibrium-এর সংজ্ঞা দিতে পারি এবং $\text{SPE} \subseteq \text{NE}$ ও "proper subgame নেই ⇒ SPE = NE" প্রমাণ করতে পারি।
[ ] SPE অ্যালগরিদম চালিয়ে (minimal subgame ভাঁজ করে) subgame-perfect equilibrium বের করতে পারি, একাধিক থাকলে সবগুলো।
[ ] chance move-সহ খেলায় Nature বসিয়ে, money lottery-র expected value নিয়ে (risk-neutral) strategic form বানাতে ও Nash equilibrium খুঁজতে পারি।

➡️ পরের অধ্যায়: 10.8 — Expected Utility Theory — money lottery-কে payoff-এ নামাতে risk-neutrality ছাড়িয়ে পূর্ণ তত্ত্ব (পরের batch-এ)। আপাতত Part 10 সূচি।

outcome	সম্ভাবনা
Adele Ben-কে $9 দেয়	\(\tfrac{1}{3}\)
Ben Adele-কে $9 দেয়	\(\tfrac{2}{3}\)