10.5 — Ordinal Games in Strategic Form (কৌশলগত রূপে ordinal গেম)

এই অধ্যায়ে কী শিখব: এবার game theory-র আনুষ্ঠানিক ভিত্তি গড়ব — একদম শূন্য থেকে, লাইন ধরে। প্রথমে শিখব একটা কৌশলগত পরিস্থিতিকে কীভাবে game frame (খেলার কাঠামো) ও তারপর game (খেলা) হিসেবে গণিতের ভাষায় লিখি: player, strategy, outcome, আর ordinal utility (ক্রমসূচক উপযোগ)। তারপর দুটো মৌলিক তুলনা — strict dominance (কঠোর প্রাধান্য) ও weak dominance (দুর্বল প্রাধান্য) — আর তা থেকে dominant-strategy solution (প্রভাবশালী-কৌশল সমাধান)। শিখব বিখ্যাত Prisoner's Dilemma (বন্দীর দ্বিধা), দুটো সত্যিকারের mechanism — second-price auction (দ্বিতীয়-দাম নিলাম) ও pivotal mechanism (পিভটাল প্রক্রিয়া) — যেখানে সত্য বলা weakly dominant (Vickrey ও Clarke-এর উপপাদ্য, প্রমাণসহ)। তারপর দুটো iterated deletion (পুনরাবৃত্ত অপসারণ) পদ্ধতি IDSDS ও IDWDS, গেম থিওরির কেন্দ্রীয় ধারণা Nash equilibrium (ন্যাশ ভারসাম্য) — সংজ্ঞা, চারটি ব্যাখ্যা, best-reply underlining পদ্ধতি, তিন-খেলোয়াড় খেলা, আর Matching Pennies যার কোনো Nash equilibrium নেই। সবশেষে infinite strategy set (অসীম কৌশল-সমষ্টি) ও Cournot competition। ৫৩টা মূল ছবি, নিজের আঁকা ছবি, tested Python, আর Bonanno-র পূর্ণ সমাধানসহ ১০টা অনুশীলনী।

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

---

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

আগের তিন অধ্যায়ে (10.1–10.3) আমরা গল্পে-গল্পে game theory-র স্বজ্ঞা গড়েছি — Hotelling, Prisoner's Dilemma, Nash equilibrium, chicken, commitment। কিন্তু "গল্প" আর "গণিত" এক নয়। একজন গণিতবিদ জিজ্ঞাসা করবে: "Nash equilibrium"-এর সংজ্ঞাটা ঠিক কী? "একটা কৌশল আরেকটার চেয়ে ভালো" — এটা কি পরিমাপযোগ্য বাক্য? "সত্য বলা সবচেয়ে ভালো কৌশল" — এটা কি প্রমাণ করা যায়? এই অধ্যায় থেকে আমরা সেই কঠোর, আনুষ্ঠানিক পথে হাঁটব।

মূল যাত্রাটা এমন: কাঠামো → পছন্দ → খেলা → সমাধান।

• একটা কৌশলগত পরিস্থিতির কাঠামো (কে খেলছে, কার কী পছন্দ-বিকল্প, কোন বিকল্প-জোড়া কোন ফল দেয়) — এটাই game frame।
• এর ওপর প্রতিটা খেলোয়াড়ের পছন্দক্রম (preferences) যোগ করলে হয় game।
• তারপর প্রশ্ন: এই খেলায় যুক্তিবাদী খেলোয়াড় কী করবে? উত্তর খুঁজতে আমরা তিন স্তরের হাতিয়ার ব্যবহার করব — dominance (সবচেয়ে শক্তিশালী, বিরল), iterated deletion (মাঝারি), আর Nash equilibrium (সবচেয়ে সাধারণ)।

মূল স্বজ্ঞা — এক লাইনে

এই পুরো অধ্যায়ের কেন্দ্রীয় সুর: "payoff-এর আসল সংখ্যা গুরুত্বপূর্ণ নয়, শুধু ক্রমটাই গুরুত্বপূর্ণ।" এটাই "ordinal" শব্দের অর্থ। utility \(10\) বনাম \(5\) মানে শুধু "প্রথমটা ভালো" — "দ্বিগুণ ভালো" নয়। তাই আমরা যেকোনো সংখ্যা (যেমন \(0,1,2,3\)) বসাতে পারি, যতক্ষণ ক্রমটা ঠিক থাকে। dominance, iterated deletion আর Nash equilibrium — এই তিনটে ধারণাই কেবল ক্রমের ওপর নির্ভরশীল, তাই এগুলো ordinal খেলাতেই কাজ করে, কোনো "পরিমাপ" ছাড়াই।

---

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

এই অংশে Bonanno-র আট‑টা section একে একে ঘুরে দেখব — সহজ উদাহরণ থেকে শুরু করে ধীরে গভীরে। আনুষ্ঠানিক সংজ্ঞা ও প্রমাণ আসবে পরের অংশে (৩ নং)।

২.১ Game frame ও game — কাঠামো বনাম পছন্দ

শুরু করি একটা টিভি game show দিয়ে — Golden Balls। দুই খেলোয়াড় Sarah ও Steven, প্রত্যেকে গোপনে একটা বল বাছে যাতে লেখা "Split" বা "Steal"। দুজন একসাথে (simultaneously) সিদ্ধান্ত নেয়। ফলাফল টাকায়:

চিত্র ১: Golden Balls খেলার কাঠামো। প্রতিটা সারি Sarah-র একটা পছন্দ, প্রতিটা কলাম Steven-এর একটা পছন্দ; প্রতিটা ঘরে সংশ্লিষ্ট ফল (কে কত টাকা পায়) লেখা।

চার সম্ভাব্য ফল (outcome):

• \(o_1\): Sarah $50,000, Steven $50,000 (দুজনেই Split)
• \(o_2\): Sarah কিছুই না, Steven $100,000 (Sarah Split, Steven Steal)
• \(o_3\): Sarah $100,000, Steven কিছুই না (Sarah Steal, Steven Split)
• \(o_4\): Sarah কিছুই না, Steven কিছুই না (দুজনেই Steal)

একটা প্রলুব্ধকর কিন্তু ভুল যুক্তি। অনেকে বলে: "Steven Steal করলে Sarah যা-ই করুক কিছুই পায় না; Steven Split করলে Sarah Steal করে $100,000 (বনাম Split-এ $50,000) — তাই Sarah-র Steal করা উচিত।" কিন্তু এই যুক্তি ভুল, কারণ এটা একটা লুকোনো ধারণা করে নিচ্ছে — Sarah selfish and greedy (স্বার্থপর ও লোভী), অর্থাৎ শুধু নিজের টাকা নিয়ে ভাবে, বেশি টাকা মানেই ভালো। কিন্তু Sarah হয়তো fair-minded (ন্যায়পরায়ণ) — দুজনে সমান $50k পাওয়াকেই সবচেয়ে ভালো মনে করে। তখন তার Split করাই যুক্তিযুক্ত। মূল শিক্ষা: পছন্দ না জানলে "যুক্তিসংগত পছন্দ কী" — এই প্রশ্নের উত্তর দেওয়া যায় না। ছবি ১-এ যা আছে তা কোনো game নয়, এটা একটা game frame — কারণ এতে খেলোয়াড়দের পছন্দের কোনো তথ্য নেই।

কাঠামোতে পছন্দ যোগ করলে তবেই game পাই। ধরা যাক দুজনেই selfish and greedy। তাহলে Sarah-র ক্রম \(o_3 \succ o_1 \succ o_2 \sim o_4\) আর Steven-এর ক্রম \(o_2 \succ o_1 \succ o_3 \sim o_4\)। এই ক্রম সংখ্যায় (utility) লিখলে — যেকোনো ক্রম-রক্ষাকারী সংখ্যা চলবে:

চিত্র ২: একই কাঠামো থেকে পাওয়া একটা game — দুজনেই selfish ও greedy। প্রতিটা ঘরে প্রথম সংখ্যা Sarah-র payoff, দ্বিতীয়টা Steven-এর।

এবার ধরা যাক Sarah fair-minded ও benevolent (ক্রম \(o_1 \succ o_3 \succ o_2 \succ o_4\)), Steven আগের মতোই selfish। তাহলে ভিন্ন একটা game পাই — যদিও কাঠামো এক:

চিত্র ৩: একই কাঠামো, ভিন্ন পছন্দ → ভিন্ন game। এখানে Sarah-র জন্য Split-ই যুক্তিসংগত, অথচ চিত্র ২-এ ছিল Steal। একই কাঠামোয় ভিন্ন খেলোয়াড় ভিন্ন আচরণ করে, কারণ তাদের প্রণোদনা (ranking) আলাদা।

২.২ Strict ও weak dominance

এবার একটা খেলোয়াড়ের দুটো কৌশলের মধ্যে তুলনা করার হাতিয়ার। মন দিই Player 1-এর দিকে; শুধু তার payoff দেখানো একটা খেলা:

চিত্র ৪: শুধু Player 1-এর payoff দেখানো একটা খেলা। সারি \(A,B,C,D\) Player 1-এর কৌশল; কলাম \(E,F,G\) Player 2-এর কৌশল।

সংখ্যাগুলো টেবিলে (Player 1-এর payoff):

	Player 2: \(E\)	Player 2: \(F\)	Player 2: \(G\)
\(A\)	\(3\)	\(2\)	\(1\)
\(B\)	\(2\)	\(1\)	\(0\)
\(C\)	\(3\)	\(2\)	\(1\)
\(D\)	\(2\)	\(0\)	\(0\)

Strict dominance। \(A\) কৌশল \(B\)-কে strictly dominates (কঠোরভাবে প্রাধান্য দেয়) — কারণ Player 2 যা-ই করুক, \(A\) সবসময় \(B\)-এর চেয়ে কড়া বেশি payoff দেয়: \(E\)-তে \(3>2\), \(F\)-তে \(2>1\), \(G\)-তে \(1>0\)। একইভাবে \(A\) ও \(C\) দুজনেই \(D\)-কে strictly dominates।

Weak dominance। \(B\) কৌশল \(D\)-কে weakly dominates (দুর্বলভাবে প্রাধান্য দেয়) — সবখানে \(\ge\), আর অন্তত এক জায়গায় \(>\): \(E\)-তে \(2=2\) (সমান), \(F\)-তে \(1>0\) (কড়া বেশি), \(G\)-তে \(0=0\) (সমান)। যেহেতু একটা জায়গায় সমান, \(B\) কিন্তু \(D\)-কে strictly dominate করে না।

চিত্র ৫: একই খেলা (চিত্র ৪-এর অনুলিপি)। এখানে সব সম্পর্ক: \(A\) strictly dominates \(B\); \(A\) ও \(C\) সমতুল্য (equivalent); \(A\) strictly dominates \(D\); \(B\) strictly dominated by \(C\); \(B\) weakly (কিন্তু strictly নয়) dominates \(D\); \(C\) strictly dominates \(D\)।

নিজের আঁকা একটা ছবিতে দুই ধরনের প্রাধান্যের পার্থক্য চোখে দেখা যাক:

চিত্র ৬: (নিজের আঁকা) বাঁয়ে strict dominance — \(A\) প্রতিটা কলামে \(B\)-এর চেয়ে কড়া উঁচু (তীর সবসময় নিচে নামছে)। ডানে weak dominance — \(B\) সবখানে \(D\)-এর সমান বা উঁচু, কিন্তু কড়া উঁচু কেবল \(F\)-এ (লাল); বাকি দুই জায়গায় সমান। "সব \(>\)" বনাম "সব \(\ge\) ও অন্তত এক \(>\)" — এই ছোট পার্থক্যই strict বনাম weak।

Dominant strategy। যদি একটা কৌশল Player-এর অন্য সব কৌশলকে dominate করে, তাকে বলি dominant (প্রভাবশালী) — যেন "সেরা"। "\(a\) dominates" বললে অর্থহীন (কাকে dominate করে?); কিন্তু "\(a\) is dominant" মানে "\(a\) সবচেয়ে ভালো"। চিত্র ৫-এ \(A\) ও \(C\) দুজনেই weakly dominant।

দেখা যাক Golden Balls-এর দুই game-এ dominant strategy আছে কিনা:

চিত্র ৭: চিত্র ২-এর অনুলিপি। এখানে প্রত্যেকের জন্য Steal একটা weakly dominant strategy, তাই (Steal, Steal) একটা weak dominant-strategy profile।

চিত্র ৮: চিত্র ৩-এর অনুলিপি। এখানে Player 1-এর জন্য Split একটা strictly dominant strategy, আর Player 2-এর জন্য Steal weakly (strictly নয়) dominant — তাই (Split, Steal) একটা weak dominant-strategy profile।

Prisoner's Dilemma। dominance-এর সবচেয়ে বিখ্যাত উদাহরণ। Doug ও Ed একই কোম্পানিতে, দুজনেই "best worker" পুরস্কারের প্রার্থী, এখন সমতায়। প্রত্যেকে বাছে Normal effort নাকি Extra effort (overtime)। কাঠামো:

চিত্র ৯: Prisoner's Dilemma-র কাঠামো। ফল: \(o_1\) কেউ পুরস্কার পায় না, কেউ family time হারায় না; \(o_2\) Ed পুরস্কার পায় (family time হারিয়ে), Doug নয়; \(o_3\) Doug পুরস্কার পায়, Ed নয়; \(o_4\) কেউ পুরস্কার পায় না, দুজনেই family time হারায়।

দুজনেই পুরস্কারের জন্য family time ত্যাগে রাজি কিন্তু নয়তো family time-ই পছন্দ, আর দুজনেই ঈর্ষাকাতর (অন্যে পুরস্কার পাওয়ার চেয়ে কেউ না পাক)। ক্রম: \(o_3 \succ_{\text{Doug}} o_1 \succ_{\text{Doug}} o_4 \succ_{\text{Doug}} o_2\) ও \(o_2 \succ_{\text{Ed}} o_1 \succ_{\text{Ed}} o_4 \succ_{\text{Ed}} o_3\)। utility \(\{0,1,2,3\}\)-এ:

চিত্র ১০: Prisoner's Dilemma-র reduced game। প্রথম সংখ্যা Doug-এর, দ্বিতীয়টা Ed-এর payoff।

টেবিলে:

	Ed: Normal	Ed: Extra
Doug: Normal	\((2,\ 2)\)	\((0,\ 3)\)
Doug: Extra	\((3,\ 0)\)	\((1,\ 1)\)

এখানে Extra effort প্রত্যেকের জন্য strictly dominant (Ed Normal নিলে Doug: \(3>2\); Ed Extra নিলে Doug: \(1>0\))। তাই \((\text{Extra}, \text{Extra}) = (1,1)\) একটা strict dominant-strategy profile। অথচ \((\text{Normal}, \text{Normal}) = (2,2)\) দুজনের কাছেই ভালো — একে বলি \((1,1)\)-এর চেয়ে strictly Pareto superior। ব্যক্তিগত যুক্তি দুজনকে \((1,1)\)-এ টেনে নেয়, যদিও \((2,2)\) সম্ভব ছিল। এটাই ব্যক্তি-যুক্তি বনাম দল-যুক্তির চিরন্তন দ্বন্দ্ব।

২.৩ Second-price auction (Vickrey নিলাম)

এখন এমন একটা খেলা যেখানে সত্য বলাই সেরা কৌশল — গাণিতিকভাবে প্রমাণযোগ্য। second-price auction (দ্বিতীয়-দাম নিলাম) বা Vickrey auction একটা "sealed-bid" নিলাম: সবাই গোপনে দাম হাঁকে, সর্বোচ্চ দরদাতা জেতে, কিন্তু সে দেয় দ্বিতীয়-সর্বোচ্চ দাম (নিজের নয়)। tie হলে নিয়ম আগেই ঠিক করা থাকে।

উদাহরণ: দুই তেল কোম্পানি একটা তেলক্ষেত্রের অধিকারের জন্য দর হাঁকে (\(10M, 20M, \dots, 50M\))। tie হলে জেতে Player 2। Player 1-এর জরিপ বলছে ক্ষেত্রটা তার কাছে $30M মূল্যের। Player 1-এর net gain (মুনাফা − দাম) দেখানো হলো (শুধু Player 1-এর payoff):

চিত্র ১১: দ্বিতীয়-দাম নিলাম (মূল্য $30M, tie-তে জেতে Player 2)। ঘরে শুধু Player 1-এর payoff। যেমন Player 1 $30M হাঁকে ও Player 2 $10M হাঁকলে — Player 1 জেতে, পায় $30M মূল্যের জিনিস, দেয় প্রতিপক্ষের $10M, তাই net \(= 30-10 = 20\)।

টেবিলে (সারি Player 1-এর দর, কলাম Player 2-এর দর; Player 1-এর payoff):

	P2 $10M	P2 $20M	P2 $30M	P2 $40M	P2 $50M
P1 $50M	\(20\)	\(10\)	\(0\)	\(-10\)	\(0\)
P1 $40M	\(20\)	\(10\)	\(0\)	\(0\)	\(0\)
P1 $30M	\(20\)	\(10\)	\(0\)	\(0\)	\(0\)
P1 $20M	\(20\)	\(0\)	\(0\)	\(0\)	\(0\)
P1 $10M	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)

লক্ষ করো: $30M (= নিজের মূল্য) হাঁকা weakly dominant — Player 2 যা-ই হাঁকুক, এই দর সবসময় সম্ভাব্য সর্বোচ্চ payoff দেয় ($50M সারিতে \(-10\) পর্যন্ত নেমে যাওয়ার ঝুঁকি নেই)। এটাই Vickrey-র উপপাদ্যের সারকথা। নিজের আঁকা ছবিতে ব্যাপারটা আরও স্পষ্ট:

চিত্র ১২: (নিজের আঁকা) দ্বিতীয়-দাম নিলামে Player 1-এর payoff বনাম নিজের দর (মূল্য \(=30\))। প্রতিপক্ষ কম হাঁকলে (নীল, \(20\)) দর \(=30\) জিতিয়ে দেয় payoff \(10\); প্রতিপক্ষ বেশি হাঁকলে (কমলা, \(40\)) দর \(=30\) হার মেনে payoff \(0\) রাখে — অতিরিক্ত হাঁকলে জিতে গিয়ে \(-10\) গুনতে হতো। দুই ক্ষেত্রেই সবুজ ভাঙা রেখা (দর = মূল্য) সেরা বা সমান-সেরা — এটাই weak dominance।

২.৪ Pivotal mechanism (Clarke প্রক্রিয়া)

Vickrey-র ভাবনায় অনুপ্রাণিত হয়ে Clarke একটা "public goods" সমস্যার সমাধান দেন। একটা পার্ক বানানো হবে কিনা — খরচ $C, ব্যক্তি \(i\) দেবে $\(c_i\) (যোগফল \(C\))। পার্ক হলে ব্যক্তি \(i\) পায় $\(v_i\) মূল্যের সুবিধা (\(v_i\) ঋণাত্মকও হতে পারে — কারও ক্ষতি)। সামাজিকভাবে দক্ষ (Pareto efficient) সিদ্ধান্ত: পার্ক বানাও যদি এবং কেবল যদি

\[\sum_{i=1}^{n} v_i > C.\]

সমস্যা: সরকার \(v_i\) জানে না, আর সরাসরি জিজ্ঞাসা করলে মানুষ মিথ্যা বলবে (যে চায় সে বাড়িয়ে বলবে, যে চায় না সে ক্ষতি বাড়িয়ে বলবে)। Clarke-এর চাল: প্রত্যেকে একটা সংখ্যা \(w_i\) ঘোষণা করবে (তার দাবি করা সুবিধা)। সিদ্ধান্ত — পার্ক হবে যদি \(\sum_j w_j > C\)। তারপর প্রত্যেকে pivotal (নির্ণায়ক) কিনা দেখা হয়: ব্যক্তি \(i\)-কে বাদ দিলে যদি সিদ্ধান্ত বদলে যায়, সে pivotal। pivotal না হলে কর নেই; pivotal হলে কর \(= \left|\sum_{j\neq i} w_j - \sum_{j\neq i} c_j\right|\)।

একটা উদাহরণ (\(n=3\), \(C=10\), \(c=(3,2,5)\), ঘোষণা \(w=(-1,8,3)\))। মোট \(\sum_i w_i = 10 = C\), তাই "যদি এবং কেবল যদি \(\sum w > C\)" নিয়মে পার্ক হবে না (সবার জন্য "with \(i\)" সিদ্ধান্ত = No)। এবার প্রত্যেককে বাদ দিলে সিদ্ধান্ত বদলায় কিনা দেখি (এটাই Bonanno-র Figure 2.11):

ব্যক্তি \(i\)	\(\sum_{j\neq i} w_j\)	\(\sum_{j\neq i} c_j\)	\(i\) বাদে সিদ্ধান্ত	pivotal?	কর
\(1\)	\(8+3=11\)	\(2+5=7\)	Yes (build)	হ্যাঁ	\(\lvert 11-7\rvert = 4\)
\(2\)	\(-1+3=2\)	\(3+5=8\)	No	না	\(0\)
\(3\)	\(-1+8=7\)	\(3+2=5\)	Yes (build)	হ্যাঁ	\(\lvert 7-5\rvert = 2\)

চিত্র ১৩ (টেবিল): pivotal mechanism-এর উদাহরণ। ব্যক্তি \(1\) ও \(3\) pivotal (তাদের বাদ দিলে সিদ্ধান্ত No → Yes বদলায়), কর যথাক্রমে \(4\) ও \(2\); ব্যক্তি \(2\) pivotal নয়, কর \(0\)।

Clarke-এর উপপাদ্য (Theorem 2.4.1): এই প্রক্রিয়ায় সত্য বলা (\(w_i = v_i\)) প্রত্যেকের জন্য weakly dominant। মিথ্যা বলে কেউ কখনো লাভবান হতে পারে না — এমনকি মিথ্যায় pivotal হওয়া (কর দেওয়া) এড়ানো গেলেও নয়। প্রমাণ ৩ নং অংশে।

২.৫ Iterated deletion — IDSDS ও IDWDS

যদি খেলোয়াড়ের dominant strategy থাকে, তবে সে সেটাই খেলবে। কিন্তু বেশির ভাগ খেলায় dominant strategy থাকে না। তখন? দুটো পুনরাবৃত্ত (iterative) পদ্ধতি কিছু খেলা "সমাধান" করতে পারে।

IDSDS — Iterated Deletion of Strictly Dominated Strategies (কঠোরভাবে অপ্রাধান্য কৌশলের পুনরাবৃত্ত অপসারণ)। যুক্তি: যুক্তিবাদী খেলোয়াড় কখনো strictly dominated কৌশল খেলবে না। তাই সেগুলো মুছে ফেলো; নতুন (ছোট) খেলায় আবার নতুন strictly dominated কৌশল তৈরি হতে পারে — সেগুলোও মোছো; এভাবে চলতে থাকো।

চিত্র ১৪: IDSDS-এর উদাহরণ। মূল খেলা \(G\) থেকে ধাপে ধাপে মোছা হয়: \(h\) (Player 2, \(g\) দিয়ে dominated) → \(D\) (Player 1, \(C\) দিয়ে) → \(g\) (Player 2, \(f\) দিয়ে) → \(C\) (Player 1, \(A\) দিয়ে)। শেষে থাকে \(G^\infty\) — সারি \(\{A,B\}\), কলাম \(\{e,f\}\), অর্থাৎ output \(\{(A,e),(A,f),(B,e),(B,f)\}\)। মজার তথ্য: finite খেলায় কোন ক্রমে মোছা হলো তা গুরুত্বহীন — ফল একই।

output একটামাত্র profile হলে তাকে বলি iterated strict dominant-strategy solution; একাধিক হলে শুধু "IDSDS-এর output"। তাৎপর্য: পরে দেখানো হবে — যদি rationality common knowledge (সর্বজনবিদিত) হয়, তবে কেবল IDSDS-এ টিকে থাকা profile-ই খেলা যেতে পারে।

IDWDS — Iterated Deletion of Weakly Dominated Strategies (দুর্বলভাবে অপ্রাধান্য কৌশলের পুনরাবৃত্ত অপসারণ)। এটা IDSDS-এর দুর্বলতর রূপ — weakly dominated কৌশলও মোছে। কিন্তু এখানে একটা বিপদ: মোছার ক্রম গুরুত্বপূর্ণ। দেখা যাক:

চিত্র ১৫: একটা খেলা যেখানে IDWDS-এর ক্রম ফল বদলে দেয়। সারি \(A,T,M,B\) (Player 1), কলাম \(L,R\) (Player 2)।

টেবিলে:

	\(L\)	\(R\)
\(A\)	\((4,0)\)	\((0,0)\)
\(T\)	\((3,2)\)	\((2,2)\)
\(M\)	\((1,1)\)	\((0,0)\)
\(B\)	\((0,0)\)	\((1,1)\)

পথ ১: \(M\) strictly dominated by \(T\) → মোছো:

চিত্র ১৬: \(M\) মোছার পর। এবার Player 2-এর \(L\) weakly dominated by \(R\)।

\(L\) মোছো (weakly dominated by \(R\)):

চিত্র ১৭: \(L\) মোছার পর কেবল কলাম \(R\) থাকে। এখন \(A\) ও \(B\) strictly dominated by \(T\) — মোছার পর টেকে \((T,R)\), payoff \((2,2)\)।

পথ ২: একই মূল খেলায় শুরুতে \(B\) strictly dominated by \(T\) → মোছো:

চিত্র ১৮: \(B\) মোছার পর। এবার Player 2-এর \(R\) weakly dominated by \(L\)।

\(R\) মোছো:

চিত্র ১৯: \(R\) মোছার পর কেবল কলাম \(L\)। এখন \(T\) ও \(M\) strictly dominated by \(A\) — টেকে \((A,L)\), payoff \((4,0)\)।

দুই পথে দুই ভিন্ন ফল: \((T,R)=(2,2)\) বনাম \((A,L)=(4,0)\)! তাই IDWDS-কে সাবধানে সংজ্ঞায়িত করতে হয়: প্রতি ধাপে সব খেলোয়াড়ের সব weakly (বা strictly) dominated কৌশল একসাথে চিহ্নিত করে সব একবারে মোছো। এই নিয়মে চিত্র ১৫-এর খেলার IDWDS-output:

চিত্র ২০: IDWDS-এর সঠিক প্রয়োগে output \(\{(A,L),(A,R),(T,L),(T,R)\}\) — একটামাত্র profile নয়, তাই এই খেলার কোনো iterated weak dominant-strategy solution নেই। সতর্কতা: IDWDS-এর ব্যাখ্যা IDSDS-এর মতো সরল নয়; এর জন্য rationality ছাড়াও একধরনের "caution" লাগে যা আবার মোছার সঙ্গে সাংঘর্ষিক।

২.৬ Nash equilibrium (ন্যাশ ভারসাম্য)

যেসব খেলা IDSDS/IDWDS দিয়ে একক সমাধানে পৌঁছায় না, তাদের জন্য চাই আরও সাধারণ ধারণা — Nash equilibrium। স্বজ্ঞা: এমন একটা কৌশল-জোড়া যেখান থেকে কেউ একা সরে গিয়ে লাভবান হতে পারে না (প্রত্যেকে অন্যের কৌশল ধরে নিয়ে নিজের best reply খেলছে)।

চিত্র ২১: দুটো Nash equilibrium-সহ একটা খেলা। সারি \(T,M,B\), কলাম \(L,C,R\)।

টেবিলে:

	\(L\)	\(C\)	\(R\)
\(T\)	\((3,2)\)	\((0,0)\)	\((1,1)\)
\(M\)	\((3,0)\)	\((1,5)\)	\((4,4)\)
\(B\)	\((1,0)\)	\((2,3)\)	\((3,0)\)

এখানে \((T,L)\) ও \((B,C)\) দুটোই Nash equilibrium। যাচাই \((T,L)\): Player 1 — \(L\) ধরে \(T\) দেয় \(3\), যা \(M\)-এর \(3\)-এর সমান ও \(B\)-এর \(1\)-এর বেশি (সরে লাভ নেই); Player 2 — \(T\) ধরে \(L\) দেয় \(2 > C\)-এর \(0\), \(R\)-এর \(1\) (সরে লাভ নেই)। best-reply underlining পদ্ধতিতে খুঁজে বের করা সহজ — প্রতি কলামে Player 1-এর সর্বোচ্চ payoff আর প্রতি সারিতে Player 2-এর সর্বোচ্চ payoff-এর নিচে দাগ; দুটোই দাগানো ঘর = Nash equilibrium:

চিত্র ২২: (নিজের আঁকা) underlining পদ্ধতি। লাল সংখ্যা Player 1-এর payoff (কলামে সর্বোচ্চ = best reply, দাগানো), নীল Player 2-এর (সারিতে সর্বোচ্চ, দাগানো)। দুই সংখ্যাই দাগানো (হলুদ ঘর) হলে সেটা Nash equilibrium — এখানে \((T,L)\) ও \((B,C)\)।

best reply ধারণাটা আলাদা করে দেখা যাক আরেকটা (আসলে একই) খেলায়:

চিত্র ২৩: best reply-র উদাহরণ (চিত্র ২১-এর একই খেলা)। Player 1-এর \(L\)-এর বিরুদ্ধে দুটো best reply (\(M\) ও \(T\), দুজনেই \(3\)), \(C\)-এর বিরুদ্ধে একমাত্র \(B\), \(R\)-এর বিরুদ্ধে একমাত্র \(M\)। Nash equilibrium-এর বিকল্প সংজ্ঞা: \(s\) হলো Nash equilibrium যদি প্রত্যেক খেলোয়াড়ের \(s_i\) হয় \(s_{-i}\)-এর একটা best reply।

underlining পদ্ধতিতে একটামাত্র Nash equilibrium-সহ একটা উদাহরণ:

চিত্র ২৪: এখানে একমাত্র Nash equilibrium \((B,E)\)। প্রতি কলামে Player 1-এর সর্বোচ্চ ও প্রতি সারিতে Player 2-এর সর্বোচ্চ দাগিয়ে খুঁজে বের করা হয়।

তিন-খেলোয়াড় খেলায় Player 3 "টেবিল" বাছে; পদ্ধতি একই, Player 3-এর payoff একই ঘরে ভিন্ন টেবিল জুড়ে সর্বোচ্চ হলে দাগাও:

চিত্র ২৫: তিন-খেলোয়াড় খেলা, একমাত্র Nash equilibrium \((B,R,W)\)। Player 1 সারি, Player 2 কলাম, Player 3 টেবিল (\(W\) বা \(E\)) বাছে।

Player 3-এর টেবিল দুটো (প্রতি ঘরে \((\pi_1,\pi_2,\pi_3)\)):

Player 3 chooses \(W\):

	\(L\)	\(R\)
\(T\)	\((0,0,0)\)	\((2,8,6)\)
\(B\)	\((5,3,2)\)	\((3,4,2)\)

Player 3 chooses \(E\):

	\(L\)	\(R\)
\(T\)	\((0,0,0)\)	\((1,2,5)\)
\(B\)	\((1,6,1)\)	\((0,0,1)\)

সব খেলায় Nash equilibrium থাকে না! ordinal খেলার কোনো নিশ্চয়তা নেই। ক্লাসিক প্রতি-উদাহরণ Matching Pennies: দুজন গোপনে H/T দেখায়; দুটো একই হলে Player 1 জেতে, নাহলে Player 2।

চিত্র ২৬: Matching Pennies। কোনো (pure-strategy) Nash equilibrium নেই — যে-ই জিতুক, হেরে-যাওয়া খেলোয়াড় সবসময় সরে গিয়ে লাভবান হতে চায়, তাই কোনো ঘর স্থিতিশীল নয়।

টেবিলে:

	\(H\)	\(T\)
\(H\)	\((1,0)\)	\((0,1)\)
\(T\)	\((0,1)\)	\((1,0)\)

একটা মজার বড় উদাহরণ (Bonanno-র Example 2.1): ৫০ জন খেলোয়াড় গোপনে $10-এর গুণিতক ($10 থেকে $100) চায়; ১০%-এর বেশি (৬ বা তার বেশি) যদি $100 চায় তবে সবাই কিছুই পায় না, নাহলে সবার দাবি মঞ্জুর। এর একাধিক Nash equilibrium আছে — যেমন ঠিক ৫ জন $100 আর বাকিরা $90 চাইলে (কেউ একা সরে লাভ করতে পারে না)।

২.৭ Infinite strategy set (অসীম কৌশল-সমষ্টি)

কৌশল-সমষ্টি অসীম হলে টেবিল আঁকা যায় না, কিন্তু সব ধারণা তবু খাটে। একটা সুন্দর উদাহরণ: দুজন প্রত্যেকে একটা বাস্তব সংখ্যা \(\ge 1\) লেখে (\(S_1=S_2=[1,\infty)\))। payoff:

\[\pi_1(x,y) = \begin{cases} x-1 & \text{if } x < y \\ 0 & \text{if } x \ge y \end{cases} \qquad \pi_2(x,y) = \begin{cases} y-1 & \text{if } x > y \\ 0 & \text{if } x \le y \end{cases}\]

এর একমাত্র Nash equilibrium \((1,1)\), payoff \((0,0)\) — অথচ মজার ব্যাপার, এখানে প্রত্যেকের কৌশল \(x=1\) weakly dominated (যেকোনো \(\hat{x}>1\) কিছু ক্ষেত্রে বেশি payoff দেয়, বাকিতে সমান)! অর্থাৎ একমাত্র Nash equilibrium-এ দুজনের কৌশলই weakly dominated।

Cournot competition (calculus সহ)। দুই ফার্ম একই পণ্য বানায়, পরিমাণ \(q_1,q_2\), খরচ \(c\) প্রতি একক, দাম \(P = a - b(q_1+q_2)\)। মুনাফা \(\pi_1 = (a-c)q_1 - b q_1^2 - b q_1 q_2\)। Nash equilibrium পেতে \(\frac{\partial \pi_1}{\partial q_1}=0\) ও \(\frac{\partial \pi_2}{\partial q_2}=0\) সমাধান করি:

\[a - c - 2b q_1 - b q_2 = 0, \qquad a - c - 2b q_2 - b q_1 = 0.\]

সমাধান \(q_1 = q_2 = \dfrac{a-c}{3b}\)। (যেমন \(a=25,b=2,c=1\) হলে \((4,4)\), প্রতি ফার্মের মুনাফা \(32\)।) এই \((q_1,q_2)\)-ই Cournot equilibrium — আসলে Nash-ই এটা আবিষ্কার করেছিলেন Cournot-এর আগেই।

২.৮ Proofs of theorems — প্রমাণের ভূমিকা

উপরের দুই "সত্য বলা সেরা" উপপাদ্য (Vickrey ও Clarke) এবং Nash equilibrium ও iterated deletion-এর সম্পর্ক-বিষয়ক দুই উপপাদ্যের আনুষ্ঠানিক প্রমাণ পরের অংশে (৩ নং) দিচ্ছি — প্রতিটা \(\square\) দিয়ে শেষ।

---

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

এবার আনুষ্ঠানিক ভাষায়। প্রথমে notation: \(S = S_1 \times \cdots \times S_n\) হলো strategy profile-এর সমষ্টি; একটা profile \(s = (s_1,\dots,s_n)\)। একজন Player \(i\)-কে আলাদা করতে লিখি \(s = (s_i, s_{-i})\), যেখানে \(s_{-i}\) হলো বাকি সবার কৌশল, আর \(S_{-i}\) তাদের profile-সমষ্টি।

৩.১ Game frame ও ordinal game

সংজ্ঞা ৩.১ (game frame in strategic form)

একটা game frame in strategic form হলো একটা চতুষ্টয় \(\langle I, (S_1,\dots,S_n), O, f\rangle\) যেখানে —

• \(I = \{1,2,\dots,n\}\) খেলোয়াড়ের সমষ্টি (\(n \ge 2\));
• প্রতিটি Player \(i\)-এর জন্য \(S_i\) হলো তার strategy set (কৌশল-সমষ্টি); \(S = S_1 \times \cdots \times S_n\);
• \(O\) হলো outcome (ফল)-এর সমষ্টি;
• \(f : S \to O\) একটা ফাংশন যা প্রতিটি profile \(s\)-কে একটা outcome \(f(s)\)-এর সঙ্গে জোড়ে।

পছন্দ প্রকাশ করি \(\succsim_i\) (at least as good), \(\succ_i\) (better), \(\sim_i\) (indifferent) দিয়ে। আমরা ধরে নিই প্রতিটি \(\succsim_i\) complete (যেকোনো \(o_1,o_2\)-এর জন্য \(o_1 \succsim_i o_2\) বা \(o_2 \succsim_i o_1\)) ও transitive (\(o_1 \succsim_i o_2\) ও \(o_2 \succsim_i o_3\) হলে \(o_1 \succsim_i o_3\))।

সংজ্ঞা ৩.২ (ordinal utility function)

complete ও transitive ক্রম \(\succsim\)-এর জন্য একটা ফাংশন \(U : O \to \mathbb{R}\) হলো একটা ordinal utility function যা \(\succsim\)-কে represent করে যদি প্রতিটি \(o,o'\)-এর জন্য: \(U(o) > U(o')\) ঠিক তখনই যখন \(o \succ o'\), এবং \(U(o) = U(o')\) ঠিক তখনই যখন \(o \sim o'\)।

গুরুত্বপূর্ণ: সংখ্যাগুলো নিছক ক্রম বহন করে। "Mexican-এর utility \(10\)" অর্থহীন; "Mexican \(10\), Japanese \(5\)" মানে শুধু "Mexican বেশি পছন্দ" — "দ্বিগুণ পছন্দ" নয়। একই ক্রম অসীম উপায়ে সংখ্যায় লেখা যায় (যেমন \(o_3 \succ o_1 \succ o_2 \sim o_4\) লিখতে \((4,2,10,2)\) বা \((1,0.7,100,0.7)\) — যেকোনোটা)।

সংজ্ঞা ৩.৩ (ordinal game ও reduced game)

একটা ordinal game in strategic form হলো পঞ্চক \(\langle I, (S_1,\dots,S_n), O, f, (\succsim_1,\dots,\succsim_n)\rangle\) — একটা game frame + প্রতিটি খেলোয়াড়ের complete ও transitive ক্রম। প্রতিটি \(\succsim_i\)-কে utility function \(U_i\) দিয়ে replace করে payoff function \(\pi_i : S \to \mathbb{R}\) পাই, যেখানে \(\pi_i(s) = U_i(f(s))\)। তখন \(\langle I, (S_1,\dots,S_n), (\pi_1,\dots,\pi_n)\rangle\)-কে বলি reduced ordinal game ('reduced' কারণ outcome-এর তথ্য হারিয়ে যায়)।

৩.২ Dominance

সংজ্ঞা ৩.৪ (strict/weak dominance ও equivalence)

Player \(i\)-এর দুই কৌশল \(a,b \in S_i\)-এর জন্য —

• \(a\) strictly dominates \(b\) যদি প্রতিটি \(s_{-i} \in S_{-i}\)-এর জন্য \(\pi_i(a, s_{-i}) > \pi_i(b, s_{-i})\);
• \(a\) weakly dominates \(b\) যদি প্রতিটি \(s_{-i}\)-এর জন্য \(\pi_i(a,s_{-i}) \ge \pi_i(b,s_{-i})\), এবং অন্তত একটা \(s_{-i}\)-এর জন্য \(\pi_i(a,s_{-i}) > \pi_i(b,s_{-i})\);
• \(a\) equivalent to \(b\) যদি প্রতিটি \(s_{-i}\)-এর জন্য \(\pi_i(a,s_{-i}) = \pi_i(b,s_{-i})\)।

strict dominance সবসময় weak dominance-ও মেটায়। প্রচলিত রীতি: "\(a\) weakly dominates \(b\)" মানে "weakly কিন্তু strictly নয়"।

সংজ্ঞা ৩.৫ (dominant strategy ও dominant-strategy profile)

• \(a\) একটা strictly dominant strategy যদি \(a\) অন্য প্রতিটি কৌশলকে strictly dominate করে (সর্বোচ্চ একটাই থাকতে পারে)।
• \(a\) একটা weakly dominant strategy যদি অন্য প্রতিটি \(x\)-এর জন্য হয় \(a\) weakly dominates \(x\), নয়তো \(a\) equivalent to \(x\)। সমতুল্যভাবে: প্রতিটি \(s_{-i}\) ও প্রতিটি \(s_i\)-এর জন্য \(\pi_i(a,s_{-i}) \ge \pi_i(s_i, s_{-i})\)।
• একটা profile \(s\) হলো strict (resp. weak) dominant-strategy profile যদি প্রতিটি খেলোয়াড়ের \(s_i\) strictly (resp. weakly) dominant হয় (weak ক্ষেত্রে অন্তত একজনের strictly নয়)।

সংজ্ঞা ৩.৬ (Pareto superiority)

\(o\) হলো \(o'\)-এর চেয়ে strictly Pareto superior যদি প্রতিটি খেলোয়াড় \(o\)-কে \(o'\)-এর চেয়ে বেশি পছন্দ করে (\(o \succ_i o'\) সবার জন্য)। weakly Pareto superior যদি সবাই \(o \succsim_i o'\) এবং অন্তত একজন \(o \succ_j o'\)।

Prisoner's Dilemma-তে \((\text{Extra},\text{Extra})\) strict dominant-strategy profile, অথচ \((\text{Normal},\text{Normal})\) তার চেয়ে strictly Pareto superior — এটাই "দ্বিধা"।

৩.৩ Second-price auction ও Vickrey-র উপপাদ্য

selfish and greedy Player \(i\)-এর ক্রম: শুধু জেতা-হারা ও দাম নিয়ে ভাবে, জিতলে কম দাম ভালো, আর জেতা-কে না-জেতার চেয়ে বেশি পছন্দ করে ঠিক তখনই যখন দাম \(< v_i\) (তার প্রকৃত মূল্য), আর \(p = v_i\)-তে উদাসীন। একটা utility function:

\[U_i(j,p) = \begin{cases} v_i - p & \text{if } i = j \\ 0 & \text{if } i \neq j \end{cases}\]

উপপাদ্য ৩.১ (Vickrey, 1961)

second-price auction-এ selfish and greedy Player \(i\)-এর জন্য নিজের প্রকৃত মূল্য হাঁকা (\(b_i = v_i\)) একটা weakly dominant strategy।

প্রমাণ (\(n=2\); Player 1-এর জন্য দেখাই, Player 2 একইভাবে)। payoff:

\[\pi_1(b_1,b_2) = \begin{cases} v_1 - b_2 & \text{if } b_1 \ge b_2 \\ 0 & \text{if } b_1 < b_2 \end{cases}\]

দেখাতে হবে: Player 2 যা-ই হাঁকুক, \(v_1\)-এর চেয়ে ভালো কোনো bid নেই। দুই ক্ষেত্র (এখানে \(b_2\) = Player 2-এর প্রকৃত bid, Player 1-এর অজানা)।

• ক্ষেত্র ১: \(b_2 \le v_1\). \(v_1\) হাঁকলে Player 1 জেতে, payoff \(v_1 - b_2 \ge 0\)। অন্য কোনো \(b_1\): যদি \(b_1 \ge b_2\) তবু জেতে, একই payoff \(v_1 - b_2\) (ভালো নয়); যদি \(b_1 < b_2\) তবে হারে, payoff \(0\) (ভালো নয়)। তাই \(v_1\)-এর চেয়ে ভালো কিছু নেই।
• ক্ষেত্র ২: \(b_2 > v_1\). \(v_1\) হাঁকলে Player 2 জেতে, Player 1-এর payoff \(0\)। অন্য \(b_1 < b_2\): একই ফল, \(0\)। কিন্তু \(b_1 \ge b_2\): Player 1 জেতে, payoff \(v_1 - b_2 < 0\) — অর্থাৎ \(v_1\)-এর চেয়ে খারাপ।

দুই ক্ষেত্রেই \(v_1\) সমান-বা-ভালো, আর ক্ষেত্র ২-এ কড়া ভালো (কোনো bid \(\ge b_2\)-এর তুলনায়) — তাই \(v_1\) weakly dominant। \(\square\)

৩.৪ Pivotal mechanism ও Clarke-র উপপাদ্য

উপপাদ্য ৩.২ (Clarke, 1971)

pivotal mechanism-এ (ধরা-নেওয়া পছন্দে) সত্য প্রকাশ (\(w_i = v_i\)) প্রত্যেক Player-এর জন্য weakly dominant।

প্রমাণের কাঠামো। একজন ব্যক্তি \(i\) ও অন্যদের ঘোষণা \(w_j\) (\(j\neq i\)) স্থির ধরো। চার ক্ষেত্র — \(\sum_{j\neq i} w_j\) বনাম \(\sum_{j\neq i} c_j\) (বড়/ছোট) এবং \(v_i + \sum_{j\neq i} w_j\) বনাম \(C\) (বড়/ছোট)। প্রতিটি ক্ষেত্রে \(i\)-এর সিদ্ধান্ত-কর-utility একটা টেবিলে সাজিয়ে দেখানো হয় যে সত্য বলা (\(w_i=v_i\))-এর utility অন্তত যেকোনো মিথ্যার সমান। যেমন ক্ষেত্র ১ (\(\sum_{j\neq i} w_j > \sum_{j\neq i} c_j\) ও \(v_i + \sum_{j\neq i}w_j > C\)): সত্য বললে প্রকল্প হয়, কর \(0\), utility \(m_i + v_i - c_i\)। কোনো মিথ্যা যদি প্রকল্প আটকায় তবে \(i\) pivotal হয়, utility \(m_i - (\sum_{j\neq i}w_j - \sum_{j\neq i}c_j)\); মিথ্যায় লাভ নেই ঠিক যখন

\[m_i + v_i - c_i \ge m_i - \left(\sum_{j\neq i} w_j - \sum_{j\neq i} c_j\right) \iff v_i + \sum_{j\neq i} w_j \ge C,\]

যা এই ক্ষেত্রের অনুমানেই সত্য। বাকি তিন ক্ষেত্রেও একইভাবে অসমতা অনুমান থেকেই বেরোয়। সব ক্ষেত্র ঢাকা পড়ায় প্রমাণ সম্পূর্ণ। \(\square\)

৩.৫ Nash equilibrium

সংজ্ঞা ৩.৭ (Nash equilibrium)

\(n\)-খেলোয়াড় ordinal game-এ একটা profile \(s^* \in S\) হলো Nash equilibrium যদি প্রতিটি Player \(i\)-এর জন্য

\[\pi_i(s^*) \ge \pi_i(s^*_1,\dots,s^*_{i-1}, s_i, s^*_{i+1},\dots,s^*_n) \quad \text{for all } s_i \in S_i.\]

সমতুল্যভাবে: প্রতিটি \(i\)-এর \(s^*_i\) হলো \(s^*_{-i}\)-এর একটা best reply (\(\pi_i(s_i, s_{-i}) \ge \pi_i(s'_i, s_{-i})\) সব \(s'_i\)-এর জন্য)।

চারটি ব্যাখ্যা (সবই একই আনুষ্ঠানিক সংজ্ঞার মৌখিক অনুবাদ): (১) No regret — প্রতিপক্ষের চাল দেখেও কেউ নিজের চাল বদলাতে চায় না। (২) Self-enforcing agreement — অ-বাধ্যতামূলক চুক্তি থেকে কেউ সরতে চায় না (যদি বিশ্বাস করে অন্যে মানবে)। (৩) Viable recommendation — তৃতীয় পক্ষের প্রকাশ্য সুপারিশ থেকে কেউ সরতে চায় না। (৪) Rationality with correct beliefs — সঠিক বিশ্বাস ও যুক্তিবাদী পছন্দ মিললে ফল Nash equilibrium।

উপপাদ্য ৩.৩ (Nash equilibrium ও IDSDS)

প্রতিটি ordinal strategic-form game \(G\)-এর জন্য \(\mathrm{NE}(G) \subseteq \mathrm{IDSDS}(G)\)। অন্যদিকে এমন হতে পারে যে \(\mathrm{NE}(G) \neq \varnothing\) অথচ \(\mathrm{NE}(G) \cap \mathrm{IDWDS}(G) = \varnothing\)।

প্রমাণ (প্রথম অংশ)। ধরো \(s^* \in \mathrm{NE}(G)\) কিন্তু \(s^* \notin \mathrm{IDSDS}(G)\) — অর্থাৎ IDSDS-এর কোনো ধাপে \(s^*_i\) মোছা পড়ে। প্রথম যে ধাপে কোনো \(s^*_i\) মোছে, সেই ধাপের আগের খেলায় এমন কৌশল \(\hat{s}_i\) আছে যা \(s^*_i\)-কে strictly dominates; বিশেষত \(\pi_i(s^*_i, s^*_{-i}) < \pi_i(\hat{s}_i, s^*_{-i})\) — যা \(s^*\) Nash equilibrium হওয়ার সঙ্গে সাংঘর্ষিক। তাই \(\mathrm{NE}(G) \subseteq \mathrm{IDSDS}(G)\)।

দ্বিতীয় অংশ (প্রতি-উদাহরণ)। নিচের খেলায় একমাত্র Nash equilibrium \((C,F)\); কিন্তু Player 1-এর \(C\) weakly dominated by \(A\) (ও \(B\)), Player 2-এর \(F\) weakly dominated by \(D\) (ও \(E\)), তাই IDWDS-output \(\{(A,D),(A,E),(B,D),(B,E)\}\) — \((C,F)\)-এর সঙ্গে শূন্য ছেদ।

চিত্র ২৭: একটা খেলা যার একমাত্র Nash equilibrium \((C,F)\) — অথচ IDWDS সেটাকেই মুছে দেয়। এটাই দেখায় IDWDS Nash equilibrium ধ্বংস করতে পারে (IDSDS পারে না)। \(\square\)

উপপাদ্য ৩.৪ (একক deletion-solution ও Nash equilibrium)

ordinal game \(G\)-এ profile \(s\)-এর জন্য: (A) \(\mathrm{IDSDS}(G) = \{s\}\) হলে \(s\) একটা strict Nash equilibrium (\(\pi_i(s^*_i, s^*_{-i}) > \pi_i(s_i, s^*_{-i})\) সব \(s_i \neq s^*_i\)-এর জন্য)। (B) \(\mathrm{IDWDS}(G) = \{s\}\) হলে \(s\) একটা Nash equilibrium।

প্রমাণ (A-এর সারাংশ)। ধরো \(\mathrm{IDSDS}(G)=\{s^*\}\)। যেকোনো Player \(i\) ও তার যেকোনো \(s_i \neq s^*_i\)-এর জন্য দেখাতে হবে \(\pi_i(s^*_i, s^*_{-i}) > \pi_i(s_i, s^*_{-i})\)। যে ধাপে \(i\)-এর সব কৌশল একটিমাত্র \(s^*_i\)-তে নেমে আসে, সেখানে \(s^*_i\) বাকি সব অবশিষ্ট কৌশলকে strictly dominate করে; আগের ধাপগুলোতে মোছা প্রতিটি কৌশলও অবশিষ্ট কোনো কৌশল দিয়ে strictly dominated। transitivity ও \(s^*_{-i}\)-এ মান বসিয়ে ধাপে ধাপে পিছিয়ে গেলে সব \(s_i \neq s^*_i\)-এর জন্য কড়া অসমতা পাই। (B) একই যুক্তি, শুধু কড়া \(>\)-এর জায়গায় দুর্বল \(\ge\)। \(\square\)

---

৪. উদাহরণ ও Analogy (সংখ্যাসহ)

৪.১ একই কাঠামো, ভিন্ন খেলা — Golden Balls

কাঠামো এক, ফল ভিন্ন। দুজনেই selfish হলে (চিত্র ২):

	Steven: Split	Steven: Steal
Sarah: Split	\((3,\ 3)\)	\((2,\ 4)\)
Sarah: Steal	\((4,\ 2)\)	\((2,\ 2)\)

Steal প্রত্যেকের weakly dominant (Steven Split নিলে Sarah: \(4>3\); Steven Steal নিলে Sarah: \(2=2\)) → \((\text{Steal},\text{Steal})\)। কিন্তু Sarah fair-minded হলে (চিত্র ৩):

	Steven: Split	Steven: Steal
Sarah: Split	\((4,\ 3)\)	\((2,\ 4)\)
Sarah: Steal	\((3,\ 2)\)	\((1,\ 2)\)

এখন Sarah-র জন্য Split strictly dominant (\(3<4\)... থুড়ি: Steven Split নিলে \(4>3\), Steven Steal নিলে \(2>1\) — হ্যাঁ Split strictly dominant), Steven-এর Steal weakly dominant → \((\text{Split},\text{Steal})\)। payoff-এর সংখ্যা নয়, ক্রমই সব।

৪.২ Prisoner's Dilemma — dominance বনাম Pareto

	Ed: Normal	Ed: Extra
Doug: Normal	\((2,\ 2)\)	\((0,\ 3)\)
Doug: Extra	\((3,\ 0)\)	\((1,\ 1)\)

Extra strictly dominant (Normal-এর বিপরীতে \(3>2\); Extra-র বিপরীতে \(1>0\)) → \((1,1)\)। কিন্তু \((2,2)\) Pareto-উন্নত। Analogy: অস্ত্র প্রতিযোগিতা, ডোপিং, দাম-যুদ্ধ — সবই এই ছাঁচ।

৪.৩ Second-price auction — truthfulness সংখ্যায়

মূল্য \(v_1 = 30\); প্রতিপক্ষ \(b_2 = 20\) হাঁকলে: দর \(30\) জেতে, payoff \(30-20 = 10\) (সেরা)। \(b_2 = 40\) হাঁকলে: দর \(30\) হারে, payoff \(0\) — কিন্তু \(45\) হাঁকলে জিতে \(30-40 = -10\)! তাই সত্য দর \(30\) সবসময় সমান-বা-সেরা (চিত্র ১১–১২)।

৪.৪ Nash equilibrium — underlining

চিত্র ২১-এর খেলায় (উপরের টেবিল) কলামে Player 1-এর ও সারিতে Player 2-এর সর্বোচ্চ দাগিয়ে পাই দুই Nash equilibrium \((T,L)\) ও \((B,C)\) (চিত্র ২২)।

Analogy সংক্ষেপে

• game frame vs game = মঞ্চ বনাম অভিনয়: মঞ্চ (নিয়ম) এক, অভিনেতার প্রেরণা (ranking) বদলালে নাটক বদলায়।
• strict vs weak dominance = "সবসময় কড়া ভালো" বনাম "কখনো সমান, কখনো ভালো"।
• second-price auction / pivotal = "সত্য বলাই সেরা নীতি" — গণিতে প্রমাণিত (weakly dominant)।
• Nash equilibrium = এমন থিতু-বিন্দু যেখান থেকে কেউ একা সরে লাভ করে না।

---

৫. Python-এ করো

numpy দিয়ে দুটো মূল হাতিয়ার বানাই: iterated deletion of (strictly) dominated strategies (IDSDS) আর Nash equilibrium finder (best-reply পদ্ধতিতে)। নিচের কোড উপরের সব উদাহরণে পরীক্ষিত।

import numpy as np

# একটা 2-খেলোয়াড় ordinal game দুটো payoff matrix দিয়ে বর্ণনা করি:
# A[i, j] = Player 1-এর payoff (row i, col j),  B[i, j] = Player 2-এর payoff
# উদাহরণ: চিত্র ২১-এর খেলা (সারি T,M,B ; কলাম L,C,R)
A = np.array([[3, 0, 1],
              [3, 1, 4],
              [1, 2, 3]])          # Player 1-এর payoff
B = np.array([[2, 0, 1],
              [0, 5, 4],
              [0, 3, 0]])          # Player 2-এর payoff
rows = ['T', 'M', 'B']
cols = ['L', 'C', 'R']


def nash_equilibria(A, B, rows, cols):
    """best-reply underlining: দুই খেলোয়াড়ই একসাথে best reply দিলে সেটা Nash equilibrium।"""
    ne = []
    nR, nC = A.shape
    for i in range(nR):
        for j in range(nC):
            p1_best = A[i, j] == A[:, j].max()   # Player 1: কলাম j ধরে সেরা সারি?
            p2_best = B[i, j] == B[i, :].max()    # Player 2: সারি i ধরে সেরা কলাম?
            if p1_best and p2_best:
                ne.append((rows[i], cols[j]))
    return ne


def idsds(A, B, rows, cols):
    """Iterated Deletion of Strictly Dominated Strategies (finite খেলায় ক্রম গুরুত্বহীন)।"""
    R = list(range(len(rows)))       # টিকে থাকা সারি-index
    C = list(range(len(cols)))       # টিকে থাকা কলাম-index
    changed = True
    while changed:
        changed = False
        # Player 1: R-এর কোনো সারি কি অন্য সারি দিয়ে strictly dominated (C কলামের ওপর)?
        for b in list(R):
            if any(a != b and np.all(A[np.ix_([a], C)][0] > A[np.ix_([b], C)][0]) for a in R):
                R.remove(b); changed = True; break
        if changed:
            continue
        # Player 2: C-এর কোনো কলাম কি অন্য কলাম দিয়ে strictly dominated (R সারির ওপর)?
        for b in list(C):
            if any(a != b and np.all(B[np.ix_(R, [a])][:, 0] > B[np.ix_(R, [b])][:, 0]) for a in C):
                C.remove(b); changed = True; break
    return [rows[i] for i in R], [cols[j] for j in C]


print("Nash equilibria:", nash_equilibria(A, B, rows, cols))
print("IDSDS survivors:", idsds(A, B, rows, cols))
# আউটপুট:
# Nash equilibria: [('T', 'L'), ('B', 'C')]
# IDSDS survivors: (['T', 'M', 'B'], ['L', 'C', 'R'])   # এই খেলায় কিছুই মোছে না

Prisoner's Dilemma-তে চালিয়ে দেখা যাক (Extra strictly dominant হওয়ায় IDSDS একক সমাধান দেবে):

# Prisoner's Dilemma: সারি/কলাম = [Normal, Extra]
A_pd = np.array([[2, 0],
                 [3, 1]])          # Doug
B_pd = np.array([[2, 3],
                 [0, 1]])          # Ed
names = ['Normal', 'Extra']
print(idsds(A_pd, B_pd, names, names))      # (['Extra'], ['Extra'])  -> strict dominant-strategy solution
print(nash_equilibria(A_pd, B_pd, names, names))  # [('Extra', 'Extra')]

আর চিত্র ১৪-এর খেলায় IDSDS ঠিক চিত্রের মতোই \(\{A,B\}\times\{e,f\}\)-এ নামে:

rows12, cols12 = ['A', 'B', 'C', 'D'], ['e', 'f', 'g', 'h']
A12 = np.array([[6, 4, 4, 3], [5, 6, 0, 5], [5, 3, 6, 4], [2, 2, 3, 6]])
B12 = np.array([[3, 4, 1, 0], [4, 3, 2, 1], [0, 2, 1, 0], [0, 3, 3, 1]])
print(idsds(A12, B12, rows12, cols12))     # (['A', 'B'], ['e', 'f'])

---

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

1. game frame আর game গুলিয়ে ফেলা। পছন্দ (ranking) ছাড়া "যুক্তিসংগত চাল কী" বলা যায় না। চিত্র ১-এর কাঠামোয় Sarah selfish না fair — জানা না থাকলে উত্তরই নেই।
2. utility-র সংখ্যাকে "পরিমাণ" ভাবা। ordinal utility-তে \(10\) বনাম \(5\) মানে শুধু "প্রথমটা ভালো", "দ্বিগুণ ভালো" নয়। যেকোনো ক্রম-রক্ষাকারী সংখ্যা সমান বৈধ।
3. "\(a\) dominates" বলা। dominance দুই কৌশলের সম্পর্ক — কাকে dominate করে বলতে হবে। তবে "\(a\) is dominant" (= সেরা) অর্থপূর্ণ।
4. strict ও weak গুলিয়ে ফেলা। একটাও সমতা (=) থাকলে সেটা weak, strict নয়। second-price auction-এ সত্য দর weakly dominant (strictly নয়) — কারণ প্রতিপক্ষ অনেক নিচে হাঁকলে বহু দর সমান।
5. IDWDS-এ যেকোনো ক্রমে মোছা। weakly dominated মোছার ক্রম ফল বদলে দেয় (চিত্র ১৫–১৯)! তাই প্রতি ধাপে সব weakly dominated একসাথে মুছতে হয়। IDSDS-এ (strict) ক্রম গুরুত্বহীন — এই দুটো মিলিয়ো না।
6. "Nash equilibrium সবসময় থাকে" ধরে নেওয়া। ordinal খেলায় নাও থাকতে পারে — Matching Pennies-এর কোনো (pure) Nash equilibrium নেই (চিত্র ২৬)।
7. IDWDS Nash equilibrium ধ্বংস করতে পারে না — এই ভুল ধারণা। পারে (চিত্র ২৭); তাই \(\mathrm{NE}(G) \cap \mathrm{IDWDS}(G)\) ফাঁকা হতে পারে। তবে \(\mathrm{NE}(G) \subseteq \mathrm{IDSDS}(G)\) সবসময় সত্য।
8. best reply "সর্বোচ্চ উভয়-payoff" ভাবা। best reply মানে নিজের payoff সর্বোচ্চ (প্রতিপক্ষের কৌশল ধরে), যৌথ কিছু নয়। underlining-এ Player 1-এরটা কলামে, Player 2-এরটা সারিতে খোঁজো।
9. dominant-strategy solution আর Nash equilibrium আলাদা ভাবা। strict dominant-strategy solution আসলে একটা (strict) Nash equilibrium (উপপাদ্য ৩.৪) — dominance শুধু আরও কড়া শর্ত।

---

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

নিচের ১০টা অনুশীলনী Bonanno-র 2.9-এর মূল সমস্যা (কিছু বাড়তি "নিজে ভাবো" অংশসহ)। সমাধান পরের অংশে।

অনুশীলনী ১ (game frame → game)। Antonia (Player 1) লেখে \(2,4\) বা \(6\); Bob (Player 2) লেখে \(1,3\) বা \(5\)। যোগফল \(\le 5\) → Mexican, \(=7\) → Italian, \(\ge 9\) → Japanese। (ক) সংজ্ঞা ৩.১-এর চতুষ্টয় লিখে এবং একটা টেবিলে game frame উপস্থাপন করো। (খ) পছন্দ: Antonia \(M \succ I \succ J\); Bob \(I \succ M \succ J\)। utility \(1,2,3\) দিয়ে reduced game আঁকো।

চিত্র ২৮: অনুশীলনী ১(ক)-এর game frame — প্রতিটি ঘরে কোন রেস্তোরাঁ।

চিত্র ২৯: অনুশীলনী ১(খ)-এর reduced game (এটাই অনুশীলনী ৫-এও লাগবে)।

অনুশীলনী ২ (card game + Nash equilibrium)। Antonia-র কার্ড \(2,4,6\); Bob-এর \(0,1,2\)। যোগফল \(s\): \(s\ge 5\) হলে Antonia পায় $\((10-s)\), নাহলে $0; \(s\) বিজোড় হলে Bob পায় $\(s\), \(s\) জোড় ও \(\le 6\) হলে Bob পায় $2, নাহলে $0। (ক) game frame টেবিলে আঁকো। (খ) দুজন selfish and greedy ধরে reduced game আঁকো। (গ) নিজে ভাবো: সব Nash equilibrium খুঁজে বের করো।

চিত্র ৩০: অনুশীলনী ২(ক)-এর game frame (টাকার অঙ্কসহ)।

চিত্র ৩১: অনুশীলনী ২(খ)-এর reduced game। এটাই অনুশীলনী ২(গ)-তে Nash equilibrium খোঁজার খেলা।

অনুশীলনী ৩ (তিন-খেলোয়াড় + Nash equilibrium)। Alice, Bob, Charlie আলাদা ঘরে; প্রত্যেকে key চাপবে কিনা ঠিক করে। Alice জেতে যদি key-চাপা লোকসংখ্যা বিজোড়; Bob জেতে যদি ঠিক দুজন চাপে; Charlie জেতে যদি কেউ না চাপে। (ক) game frame আঁকো (টেবিল-সমষ্টি)। (খ) সবাই জেতা পছন্দ করে, না-জেতা ফলে উদাসীন; utility \(\{0,1\}\)। (গ) একই কিন্তু: Bob না-জিতলে Charlie-র জেতা চায় (Alice-এর নয়), Charlie না-জিতলে Bob-এর জেতা চায়; utility \(\{0,1,2\}\)। (ঘ) নিজে ভাবো: (খ) ও (গ)-এর Nash equilibrium।

চিত্র ৩২: অনুশীলনী ৩(ক)-এর তিন-খেলোয়াড় game frame (কে জেতে)।

চিত্র ৩৩: অনুশীলনী ৩(খ)-এর reduced game (utility \(0/1\))।

চিত্র ৩৪: অনুশীলনী ৩(গ)-এর reduced game (utility \(0/1/2\))।

অনুশীলনী ৪ (envelope + referee)। দুজন প্রত্যেকে খামে \(0\), $300 বা $600 রাখে; referee সব টাকা তুলে ৫০% যোগ করে সমান দুই ভাগে বিলি করে। (ক) দুটো টেবিল: (i) প্রত্যেকে বিলি-পাওয়া টাকা, (ii) net পরিবর্তন (পাওয়া − রাখা)। (খ) Player 1 চায় referee যত বেশি হারায় (তত ভালো), Player 2 selfish (নিজের net gain)। game আঁকো। (গ) strict dominant-strategy profile আছে কি? (ঘ) নিজে ভাবো: Nash equilibrium?

চিত্র ৩৫: অনুশীলনী ৪(ক)-এর দুই টেবিল।

চিত্র ৩৬: অনুশীলনী ৪(খ)-এর game। এটাই ৪(ঘ)-তে Nash equilibrium খোঁজার খেলা।

অনুশীলনী ৫ (dominance + iterated deletion)। অনুশীলনী ১(খ)-এর খেলায় (চিত্র ২৯) — (ক) প্রতিটি খেলোয়াড়ের strictly dominated কৌশল আছে কি? (খ) weakly dominated? (গ) IDSDS প্রয়োগ করো। (ঘ) IDWDS প্রয়োগ করো।

চিত্র ৩৭: অনুশীলনী ৫-এর খেলা (চিত্র ২৯-এর একই খেলা, dominance বিশ্লেষণের জন্য)।

অনুশীলনী ৬ (তিন-খেলোয়াড় envelope + Nash)। তিনজন প্রত্যেকে খামে \(0\), $3 বা $6 রাখে; referee সব তুলে দ্বিগুণ করে সমান তিন ভাগে বিলি করে। প্রত্যেকে selfish (net change)। (ক) game আঁকো (টেবিল-সমষ্টি)। (খ) প্রতি জোড়া কৌশলে dominance (weak/strict)? (গ) strict dominant-strategy profile? (ঘ) নিজে ভাবো: Nash equilibrium?

চিত্র ৩৮: অনুশীলনী ৬-এর তিন-খেলোয়াড় খেলা (net change payoff, তিনটি টেবিল)।

অনুশীলনী ৭ (second-price auction, Player 2-সহ + Nash)। চিত্র ১১-এর নিলামে এবার Player 2-এর মূল্য $50M ধরে, সে-ও net gain-এ ranking করে — Player 2-এর payoff যোগ করে সম্পূর্ণ টেবিল আঁকো। (খ) নিজে ভাবো: সব Nash equilibrium।

চিত্র ৩৯: অনুশীলনী ৭-এর সম্পূর্ণ নিলাম-খেলা (দুই খেলোয়াড়ের payoff)।

অনুশীলনী ৮ (IDSDS)। নিচের খেলায় IDSDS প্রয়োগ করো। iterated strict dominant-strategy profile আছে কি?

চিত্র ৪০: অনুশীলনী ৮-এর খেলা। সারি \(a,b,c\); কলাম \(d,e,f\)।

অনুশীলনী ৯ (voting + IDWDS + Nash)। ক্লাবে তিন সদস্য Ann, Bob, Carla পরবর্তী president বাছে (বর্তমানে Ann)। প্রত্যেকে একজনকে ভোট দেয় (নিজেকেও দেওয়া যায়); দুই-বেশি ভোট পেলে সে president; সম্পূর্ণ মতভেদ (তিনজনে তিন) হলে Ann যাকে ভোট দিয়েছে সে-ই। (ক) game frame আঁকো। (খ) পছন্দ: \(\text{Ann}\succ_{\text{Ann}}\text{Carla}\succ_{\text{Ann}}\text{Bob}\), \(\text{Carla}\succ_{\text{Bob}}\text{Bob}\succ_{\text{Bob}}\text{Ann}\), \(\text{Bob}\succ_{\text{Carla}}\text{Ann}\succ_{\text{Carla}}\text{Carla}\); utility \(0,1,2\)। (গ) IDWDS প্রয়োগ করো। (ঘ) Ann-এর বাড়তি ক্ষমতা (tie-break) কি তার উপকার করে? (ঙ) নিজে ভাবো: Nash equilibrium।

চিত্র ৪১: অনুশীলনী ৯(ক)-এর game frame (কে নির্বাচিত)।

চিত্র ৪২: অনুশীলনী ৯(খ)-এর reduced game (তিনটি টেবিল; ঘরে \((\pi_{\text{Ann}},\pi_{\text{Bob}},\pi_{\text{Carla}})\))। এটাই ৯(ঙ)-তে Nash equilibrium খোঁজার খেলা।

অনুশীলনী ১০ (IDSDS, IDWDS ও Nash একসাথে)। নিচের খেলায় (ক) IDSDS প্রয়োগ করো — iterated strict solution আছে কি? (খ) IDWDS প্রয়োগ করো — iterated weak solution আছে কি? (গ) সব Nash equilibrium খোঁজো।

চিত্র ৪৩: অনুশীলনী ১০-এর খেলা। সারি \(a,b,c\); কলাম \(D,E,F\)।

---

৮. সমাধান (ব্যাখ্যাসহ)

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

(ক) \(I=\{1,2\}\), \(S_1=\{2,4,6\}\), \(S_2=\{1,3,5\}\), \(O=\{M,I,J\}\)। profile-সমষ্টি \(S=\{(2,1),\dots,(6,5)\}\) (৯টি)। outcome function: \(f(2,1)=f(2,3)=f(4,1)=M\); \(f(2,5)=f(4,3)=f(6,1)=I\); \(f(4,5)=f(6,3)=f(6,5)=J\)। টেবিল (চিত্র ২৮):

	Bob \(1\)	Bob \(3\)	Bob \(5\)
Antonia \(2\)	\(M\)	\(M\)	\(I\)
Antonia \(4\)	\(M\)	\(I\)	\(J\)
Antonia \(6\)	\(I\)	\(J\)	\(J\)

(খ) utility: Antonia \(M{=}3,I{=}2,J{=}1\); Bob \(M{=}2,I{=}3,J{=}1\)। reduced game (চিত্র ২৯; প্রথম Antonia, দ্বিতীয় Bob):

	Bob \(1\)	Bob \(3\)	Bob \(5\)
Antonia \(2\)	\((3,2)\)	\((3,2)\)	\((2,3)\)
Antonia \(4\)	\((3,2)\)	\((2,3)\)	\((1,1)\)
Antonia \(6\)	\((2,3)\)	\((1,1)\)	\((1,1)\)

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

(ক,খ) যোগফল অনুযায়ী হিসাব করে reduced game (চিত্র ৩১; প্রথম Antonia, দ্বিতীয় Bob):

	Bob \(0\)	Bob \(1\)	Bob \(2\)
Antonia \(2\)	\((0,2)\)	\((0,3)\)	\((0,2)\)
Antonia \(4\)	\((0,2)\)	\((5,5)\)	\((4,2)\)
Antonia \(6\)	\((4,2)\)	\((3,7)\)	\((2,0)\)

যেমন \((4,1)\): যোগফল \(5\) (বিজোড়, \(\ge 5\)) → Antonia \(10-5=5\), Bob \(5\) → \((5,5)\)।

(গ) underlining: Player 1-এর কলাম-সর্বোচ্চ — কলাম \(0\): Antonia \(6\) (\(4\)); কলাম \(1\): Antonia \(4\) (\(5\)); কলাম \(2\): Antonia \(4\) (\(4\))। Player 2-এর সারি-সর্বোচ্চ — প্রতি সারিতে Bob-এর সর্বোচ্চ কলাম \(1\)-এ (\(3,5,7\))। দুটোই দাগানো একমাত্র ঘর \((4,1)\), payoff \((5,5)\) — এটাই একমাত্র Nash equilibrium (চিত্র ৩১-ই এখানে reproduced):

চিত্র ৪৪: অনুশীলনী ২(গ)-এর খেলা (Nash equilibrium \((4,1)\), payoff \((5,5)\))।

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

(ক) তিন-খেলোয়াড় frame (চিত্র ৩২): Charlie টেবিল (\(P\)/not \(P\)) বাছে, ঘরে কে জেতে।

(খ) utility \(0/1\) (জিতলে \(1\))। reduced game চিত্র ৩৩। (গ) utility \(0/1/2\) চিত্র ৩৪।

(ঘ) Nash equilibrium: (খ)-এর খেলায় একমাত্র Nash equilibrium (not \(P\), \(P\), not \(P\)) (চিত্র ৩৫); (গ)-এর খেলায় কোনো Nash equilibrium নেই (চিত্র ৩৬)।

চিত্র ৪৫: অনুশীলনী ৩(খ)-এর খেলা; একমাত্র Nash equilibrium (not P, P, not P)।

চিত্র ৪৬: অনুশীলনী ৩(গ)-এর খেলা; কোনো Nash equilibrium নেই।

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

(ক) referee মোট টাকা \(\times 1.5\) করে দুই ভাগ করে। দুই টেবিল চিত্র ৩৫-এ (বিলি-পাওয়া ও net)।

(খ) Player 1-এর payoff = referee-র মোট লোকসান, Player 2-এর = নিজের net gain (চিত্র ৩৬)।

(গ) Player 1-এর জন্য $600 রাখা strictly dominant (referee সবচেয়ে বেশি হারায়), Player 2-এর জন্য $0 রাখা strictly dominant (নিজে সবচেয়ে বেশি net পায়)। তাই strict dominant-strategy profile ($600, $0)।

(ঘ) strict dominant-strategy profile সবসময় (strict) Nash equilibrium (উপপাদ্য ৩.৪) — তাই একমাত্র Nash equilibrium ($600, $0) (চিত্র ৪৭):

চিত্র ৪৭: অনুশীলনী ৪-এর খেলা; একমাত্র Nash equilibrium (600, 0)।

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

খেলা চিত্র ৩৭ (= অনুশীলনী ১খ)।

(ক) strictly dominated: Player 1-এর \(6\) strictly dominated by \(2\) (\(2\) দেয় \((3,3,2)\), \(6\) দেয় \((2,1,1)\); সব \(>\))। অন্য কোনো strict নেই; Player 2-এর কোনো strictly dominated কৌশল নেই।

(খ) weakly dominated: Player 1-এর \(6\) weakly dominated by \(4\) (এবং \(2\)); \(4\) weakly dominated by \(2\) (\(2{=}(3,3,2)\), \(4{=}(3,2,1)\): \(3{=}3, 3{>}2, 2{>}1\))। Player 2-এর কোনোটা নয়।

(গ) IDSDS: প্রথম ধাপে Player 1-এর \(6\) মোছে (strictly dominated by \(2\)), তারপর থেমে যায় → output সারি \(\{2,4\}\), কলাম \(\{1,3,5\}\) (চিত্র ৪১):

চিত্র ৪১-সহায়ক: এই খেলার IDSDS/IDWDS-এর জন্য reproduced game।

চিত্র ৪২-সহায়ক: প্রথম ধাপ শেষে অবস্থা (সারি \(6\) মোছা)।

(ঘ) IDWDS: প্রথম ধাপে Player 1-এর \(4\) ও \(6\) (দুটোই weakly dominated by \(2\)), Player 2-এর কিছুই নয়। দ্বিতীয় ধাপে সারি কেবল \(2\) থাকায় Player 2-এর payoff (সারি \(2\)): কলাম \(1{=}2\), \(3{=}2\), \(5{=}3\) → কলাম \(1,3\) weakly dominated by \(5\) → মোছে। output একক profile \((2,5)\) — iterated weak dominant-strategy profile।

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

(ক) তিন-খেলোয়াড় খেলা চিত্র ৩৮ (net change payoff; যেমন সবাই \(0\) দিলে সবাই \(0\); একজন \(6\) দিলে referee \(6\) যোগ করে মোট \(12\), তিন ভাগে \(4\) করে — দাতার net \(4-6=-2\))।

(খ,গ) প্রত্যেক খেলোয়াড়ের জন্য \(0\) strictly dominates \(3\) ও \(6\), আর \(3\) strictly dominates \(6\)। তাই \(0\) strictly dominant; strict dominant-strategy profile \((0,0,0)\) (সবাই কিছু দেয় না)।

(ঘ) Nash equilibrium: strict dominant-strategy profile হওয়ায় একমাত্র Nash equilibrium \((0,0,0)\) (চিত্র ৪৪):

চিত্র ৪৪-সহায়ক: অনুশীলনী ৬-এর খেলা; একমাত্র Nash equilibrium (0,0,0)।

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

Player 2-এর মূল্য $50M; তার payoff = জিতলে \(50 - (\text{Player 1's bid})\), নাহলে \(0\) (tie-তে Player 2 জেতে)। সম্পূর্ণ টেবিল চিত্র ৩৯।

(খ) Nash equilibrium: এই নিলামে ১৫টি Nash equilibrium: \((10,30),(10,40),(10,50),(20,30),(20,40),(20,50),(30,30),(30,40),(30,50),(40,40),(40,50),(50,10),(50,20),(50,30),(50,50)\) — এখানে দর মানে (Player 1, Player 2)। এত বেশি কারণ weak dominance অনেক সমান-payoff তৈরি করে (চিত্র ৪৬):

চিত্র ৪৬-সহায়ক: অনুশীলনী ৭-এর সম্পূর্ণ খেলা; ১৫টি Nash equilibrium।

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

খেলা (সারি \(a,b,c\); কলাম \(d,e,f\)):

	\(d\)	\(e\)	\(f\)
\(a\)	\((8,6)\)	\((0,9)\)	\((3,8)\)
\(b\)	\((3,2)\)	\((2,1)\)	\((4,3)\)
\(c\)	\((2,8)\)	\((1,5)\)	\((3,1)\)

ক্রমে মোছা: \(c\) strictly dominated by \(b\) (Player 1: \(3{>}2,2{>}1,4{>}3\)) → মোছো; এবার \(d\) strictly dominated by \(f\) (Player 2: \(f\) দেয় \(8,3\); \(d\) দেয় \(6,2\)) → মোছো; এবার \(a\) strictly dominated by \(b\) (Player 1: \(2{>}0,4{>}3\)) → মোছো; এবার \(e\) strictly dominated by \(f\) (Player 2: \(3{>}1\)) → মোছো; থাকে একক profile \((b,f)\) — iterated strict dominant-strategy profile (চিত্র ৪৮):

চিত্র ৪৮: অনুশীলনী ৮-এর খেলা reproduced; iterated strict solution \((b,f)\)।

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

(ক) frame চিত্র ৪১; Carla টেবিল বাছে, ঘরে নির্বাচিত প্রার্থী।

(খ) reduced game চিত্র ৪২ (ঘরে \((\pi_{\text{Ann}},\pi_{\text{Bob}},\pi_{\text{Carla}})\); যেমন Ann জিতলে Ann-এর utility \(2\))।

(গ) IDWDS: ধাপ ১ — Ann-এর \(B,C\) weakly dominated by \(A\); Bob-এর \(A\) weakly dominated by \(C\); Carla-র \(C\) weakly dominated by \(B\) → সব মোছো। বাকি খেলায় (চিত্র ৫১-সহায়ক) Bob-এর \(C\) weakly dominated by \(B\), Carla-র \(A\) weakly dominated by \(B\) → ধাপ ২-তে মোছো। থাকে একক profile (A, B, B) — Ann নিজেকে, Bob ও Carla Bob-কে ভোট দেয় → Bob president।

চিত্র ৫১-সহায়ক: অনুশীলনী ৯(গ)-এর IDWDS-এর প্রথম ধাপের পরের খেলা।

(ঘ) নির্বাচিত হয় Bob — Ann-এর সবচেয়ে অপছন্দের! তাই tie-break-এর বাড়তি ক্ষমতা Ann-এর ক্ষতি করে (কৌশলগত খেলায় বেশি ক্ষমতা সবসময় সুবিধা নয়)।

(ঙ) Nash equilibrium: ৫টি — (A,A,A), (B,B,B), (C,C,C), (A,C,A), (A,B,B) (চিত্র ৫২):

চিত্র ৫২: অনুশীলনী ৯-এর খেলা; ৫টি Nash equilibrium।

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

খেলা (সারি \(a,b,c\); কলাম \(D,E,F\)):

	\(D\)	\(E\)	\(F\)
\(a\)	\((2,3)\)	\((2,2)\)	\((3,1)\)
\(b\)	\((2,0)\)	\((3,1)\)	\((1,0)\)
\(c\)	\((1,4)\)	\((2,0)\)	\((0,4)\)

(ক) IDSDS: প্রথমে \(c\) strictly dominated by \(b\) (Player 1: \(2{>}1,3{>}2,1{>}0\)) → মোছো; তারপর \(F\) strictly dominated by \(E\) (Player 2: \(E\) দেয় \(2,1\); \(F\) দেয় \(1,0\)) → মোছো। থাকে সারি \(\{a,b\}\), কলাম \(\{D,E\}\) (চিত্র ৫৪) — একক profile নয়, তাই iterated strict solution নেই।

চিত্র ৫৫-সহায়ক: অনুশীলনী ১০-এর IDSDS-output (সারি \(a,b\); কলাম \(D,E\))।

(খ) IDWDS: ধাপ ১ — \(c\) ও \(F\) মোছো (\(F\) weakly dominated by \(D\)); ধাপ ২ — \(a\) মোছো; ধাপ ৩ — \(D\) মোছো। থাকে একক profile \((b,E)\) — iterated weak dominant-strategy profile।

(গ) Nash equilibrium: underlining-এ দুটো — \((a,D)\) ও \((b,E)\) (চিত্র ৫৬):

চিত্র ৫৪-সহায়ক: অনুশীলনী ১০-এর খেলা reproduced (IDSDS চলাকালীন)।

চিত্র ৫৬: অনুশীলনী ১০-এর খেলা; দুই Nash equilibrium \((a,D)\) ও \((b,E)\)।

---

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

এই অধ্যায়ে game theory-র আনুষ্ঠানিক ভিত্তি এক জায়গায়:

• game frame → game: কাঠামো (\(I, S_i, O, f\)) + পছন্দ (\(\succsim_i\)) = ordinal game; utility বসিয়ে reduced game। সংখ্যা নয়, ক্রমই সব (ordinal)।
• dominance: strict ("সব \(>\)"), weak ("সব \(\ge\), অন্তত এক \(>\)"), equivalent। dominant strategy = সেরা; dominant-strategy profile = সমাধান। Prisoner's Dilemma-তে strict dominant profile Pareto-নিকৃষ্ট।
• second-price auction ও pivotal mechanism: সত্য বলা weakly dominant — Vickrey ও Clarke-এর উপপাদ্য, প্রমাণসহ।
• iterated deletion: IDSDS (strict; ক্রম গুরুত্বহীন) ও IDWDS (weak; ক্রম গুরুত্বপূর্ণ, তাই একসাথে মোছো)।
• Nash equilibrium: কেউ একা সরে লাভ করে না; best-reply underlining; চারটি ব্যাখ্যা; \(\mathrm{NE}\subseteq\mathrm{IDSDS}\); IDWDS Nash ধ্বংস করতে পারে; Matching Pennies-এর কোনো (pure) Nash নেই।
• infinite strategy set: টেবিল ছাড়াই সব ধারণা খাটে; Cournot equilibrium \(q_1=q_2=\frac{a-c}{3b}\)।

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

• [ ] একটা পরিস্থিতিকে game frame (\(\langle I,(S_i),O,f\rangle\)) ও তারপর ordinal game হিসেবে লিখতে পারি।
• [ ] ordinal utility-র সংখ্যা কেন arbitrary (শুধু ক্রম গোনে) — ব্যাখ্যা করতে পারি।
• [ ] strict ও weak dominance আলাদা করে dominant-strategy profile খুঁজতে পারি।
• [ ] second-price auction-এ সত্য দর কেন weakly dominant — Vickrey-র প্রমাণ দিতে পারি (\(\square\))।
• [ ] pivotal mechanism-এ কে pivotal ও তার কর হিসাব করতে পারি, আর Clarke-র উপপাদ্য বলতে পারি।
• [ ] IDSDS ও IDWDS চালাতে পারি এবং কেন IDWDS-এ ক্রম গুরুত্বপূর্ণ বোঝাতে পারি।
• [ ] best-reply underlining-এ দুই- ও তিন-খেলোয়াড় খেলার সব Nash equilibrium বের করতে পারি।
• [ ] \(\mathrm{NE}(G)\subseteq\mathrm{IDSDS}(G)\) কেন সত্য এবং IDWDS কেন Nash ধ্বংস করতে পারে — ব্যাখ্যা করতে পারি।
• [ ] Matching Pennies-এ কেন কোনো pure-strategy Nash equilibrium নেই — দেখাতে পারি।
• [ ] Python-এ IDSDS ও Nash-equilibrium finder চালাতে পারি।

---

➡️ পরের অধ্যায়: 10.6 — Perfect-information Games — এবার ক্রমিক (sequential) খেলা, game tree ও backward induction। Part 10 সূচি।