Subgame Perfect Equilibrium

অনুপ্রেরণা

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

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

বাস্তব জীবনের দৃশ্য: খালি হুমকি

একটি ইউনিয়ন ধর্মঘটে আছে। ম্যানেজমেন্ট প্রকাশ্যে বলে: "যদি শুক্রবারের মধ্যে আমাদের অফার না মানো, আমরা কারখানা স্থায়ীভাবে বন্ধ করব।" এই হুমকি কি বিশ্বাসযোগ্য?

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

গাণিতিক দিক: সাবগেম পারফেক্ট ইকুইলিব্রিয়াম

একটি কৌশল প্রোফাইল $\sigma^* = (\sigma_1^*, \dots, \sigma_n^*)$ একটি এক্সটেনসিভ-ফর্ম গেমে সাবগেম পারফেক্ট ইকুইলিব্রিয়াম যদি এটি পুরো গেমের এবং প্রতিটি যথাযথ সাবগেমের একটি ন্যাশ ইকুইলিব্রিয়াম।

সমতুল্যভাবে: প্রতিটি সাবগেম $G'$ এর জন্য, $(\sigma_1^*|_{G'}, \dots, \sigma_n^*|_{G'})$ কৌশলগুলো $G'$ এ সীমাবদ্ধ $G'$ এর একটি ন্যাশ ইকুইলিব্রিয়াম গঠন করে।

সহজাত: SPE অবিশ্বাস্য হুমকি বাদ দেয় খেলোয়াড়দের প্রতিটি সিদ্ধান্ত পয়েন্টে যেটিতে তারা বাস্তবে পৌঁছাতে পারে সেখানে সর্বোত্তম খেলা দাবি করে।

দুটি সমতুল্য সংজ্ঞা

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

SPE — ধাপে ধাপে অ্যালগরিদম

সসীম এক্সটেনসিভ-ফর্ম গেমের জন্য নিখুঁত তথ্য সহ, ব্যাকওয়ার্ড-ইন্ডাকশন অ্যালগরিদম SPE তৈরি করে:

বীজগাণিতিকভাবে SPE ডেরাইভ করা

নিখুঁত তথ্য সহ একটি সসীম গেমের জন্য, SPE তিনটি সুনির্দিষ্ট ধাপে ডেরাইভ করা যায়:

1. প্রতিটি টার্মিনাল নোড $z \in Z$-কে পেওয়াফ ভেক্টর $(u_1(z), \dots, u_n(z))$ দিয়ে লেবেল করো।
2. খেলোয়াড় $i = P(h)$ যেখানে সরানো হয় এমন প্রতিটি অ-টার্মিনাল নোড $h$-তে, $h$-এর তাৎক্ষণিক উত্তরসূরিদের মধ্যে $i$-এর পেওয়াফ সর্বোচ্চ করে এমন পদক্ষেপ $a^*$ বেছে নাও:

$$a^*(h) \;=\; \arg\max_{a \in A(h)} u_i(h \cdot a).$$

3. প্রতিটি এমন নোডকে নির্বাচিত পদক্ষেপের পেওয়াফ দিয়ে প্রতিস্থাপন করো এবং রুট পৌঁছানো পর্যন্ত উপরে পুনরাবৃত্তি করো।

প্রতিটি সিদ্ধান্ত নোডে নির্বাচিত পদক্ষেপ রেকর্ড করা কৌশল প্রোফাইল $\sigma^*$ হলো অনন্য SPE। (যখন টাই থাকে — নোডে সমান পেওয়াফ — একাধিক SPE বিদ্যমান; টাই হওয়া সেরা পদক্ষেপগুলোর মধ্যে যেকোনো পছন্দ কিছু SPE-এর অংশ।)

ব্যবহারিক রেসিপি

1. সমস্ত সিদ্ধান্ত নোড এবং প্রতিটিতে পদক্ষেপ চিহ্নিত করো।
2. সমস্ত টার্মিনাল নোড পেওয়াফ দিয়ে চিহ্নিত করো।
3. গভীরতম সিদ্ধান্ত নোডগুলোতে শুরু করো (যাদের উত্তরসূরি সব টার্মিনাল)।
4. প্রতিটি এমন নোডে, এই নোড থেকে শাখা দেওয়া টার্মিনাল পেওয়াফগুলোর মধ্যে সংশ্লিষ্ট খেলোয়াড়ের পেওয়াফ সর্বোচ্চ করে এমন পদক্ষেপ বেছে নাও।
5. সাবগেমটিকে নির্বাচিত পদক্ষেপ এবং এর ফলে পেওয়াফ দিয়ে প্রতিস্থাপন করো।
6. এক স্তর উপরে যাও, প্রতিস্থাপিত সাবগেমকে একটি একক টার্মিনাল ফলাফল হিসেবে বিবেচনা করে।
7. রুট পৌঁছানো পর্যন্ত পুনরাবৃত্তি করো।
8. তুমি যে কৌশল প্রোফাইল পাও — প্রতিটি সিদ্ধান্ত নোডে পদক্ষেপ — সেটাই SPE।

অসম্পূর্ণ তথ্যের গেমের জন্য, এই অ্যালগরিদম ব্যর্থ হয় কারণ সংশ্লিষ্ট খেলোয়াড় জানেন না তারা কোন নোডে। SPE তখন প্রতিটি সাবগেমকে পৃথক গেম হিসেবে সমাধান করতে হয়, প্রায়ই মিশ্র কৌশলে।

নরমাল ফর্ম বনাম এক্সটেনসিভ ফর্ম

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

প্রতিটি এক্সটেনসিভ-ফর্ম গেমের একটি সংশ্লিষ্ট নরমাল ফর্ম আছে, এবং প্রতিটি সসীম গেমের অন্তত একটি নরমাল ফর্ম আছে। SPE যেকোনো ফর্মে সংজ্ঞায়িত করা যায়।

সাধারণ ভুল

• প্রতিটি ন্যাশ ইকুইলিব্রিয়ামকে "সাবগেম পারফেক্ট" বলা। SPE একটি পরিমার্জন। বেশিরভাগ গেমে ন্যাশ ইকুইলিব্রিয়ামের চেয়ে বেশি SPE আছে।
• বিশ্বাস করা যে SPE একটি অনন্য ইকুইলিব্রিয়াম দাবি করে। অনেক গেমে একাধিক SPE আছে।
• অ-একক তথ্য সেটের গেমে ব্যাকওয়ার্ড ইন্ডাকশন প্রয়োগ করা। অ্যালগরিদম ব্যর্থ হয় যখন একজন খেলোয়াড় জানেন না তারা কোন নোডে।
• ভাবা যে SPE কোনো পরম অর্থে "যুক্তিসঙ্গত"। SPE যুক্তিসঙ্গত খেলার একটি মডেল।

সারসংক্ষেপ

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

পরবর্তী কী?

পরবর্তী অধ্যায় গেম-থিওরি টুলকিট তথ্য কাঠামো দিয়ে শেষ করে। আমরা দেখব কী ঘটে যখন খেলোয়াড়রা একে অন্যকে পর্যবেক্ষণ করে না — যখন গেমের অসম্পূর্ণ তথ্য থাকে।