Stochastic game
গেম থিওরিতে, 1950-এর দশকের গোড়ার দিকে লয়েড শ্যাপলি দ্বারা প্রবর্তিত একটি স্টোকাস্টিক গেম (বা মার্কভ গেম) হল এক বা একাধিক খেলোয়াড়ের দ্বারা খেলা সম্ভাব্য রূপান্তর সহ একটি পুনরাবৃত্ত খেলা। খেলাটি পর্যায়ক্রমে খেলা হয়। প্রতিটি পর্যায়ের শুরুতে খেলাটি কোনও না কোনও অবস্থায় থাকে। খেলোয়াড়রা অ্যাকশন নির্বাচন করে এবং প্রতিটি খেলোয়াড় একটি বেতন পায় যা বর্তমান অবস্থা এবং নির্বাচিত অ্যাকশনের উপর নির্ভর করে। এরপরে খেলাটি একটি নতুন এলোমেলো অবস্থায় চলে যায় যার বিতরণ পূর্ববর্তী অবস্থা এবং খেলোয়াড়দের দ্বারা নির্বাচিত ক্রিয়াগুলির উপর নির্ভর করে। পদ্ধতিটি নতুন রাজ্যে পুনরাবৃত্তি করা হয় এবং খেলাটি একটি সীমাবদ্ধ বা অসীম সংখ্যক পর্যায়ের জন্য চলতে থাকে। একজন খেলোয়াড়ের মোট বেতনকে প্রায়শই স্টেজ পে-অফের ছাড়ের পরিমাণ বা স্টেজ পে-অফের গড়ের চেয়ে নিকৃষ্ট সীমা হিসাবে নেওয়া হয়। স্টোকাস্টিক গেমগুলি একাধিক মিথস্ক্রিয়াশীল সিদ্ধান্ত গ্রহণকারীদের কাছে মার্কভ সিদ্ধান্ত প্রক্রিয়াগুলিকে সাধারণীকরণ করে, পাশাপাশি কৌশলগত-ফর্ম গেমগুলিকে গতিশীল পরিস্থিতিতে পরিণত করে যেখানে খেলোয়াড়দের পছন্দের প্রতিক্রিয়ায় পরিবেশ পরিবর্তিত হয়। একটি অজানা (প্রতিকূল) পরিবেশে পরিচালিত বিচ্ছিন্ন ব্যবস্থাগুলির মডেলিং এবং বিশ্লেষণের জন্য নির্দেশিত গ্রাফগুলিতে দুই খেলোয়াড়ের খেলা ব্যাপকভাবে ব্যবহৃত হয়। একটি সিস্টেম এবং তার পরিবেশের সম্ভাব্য বিন্যাসগুলি শীর্ষ হিসাবে উপস্থাপিত হয় এবং রূপান্তরগুলি সিস্টেমের ক্রিয়া, তার পরিবেশ বা "প্রকৃতি"-র সাথে সামঞ্জস্যপূর্ণ। সিস্টেমের একটি রান তারপর গ্রাফের একটি অসীম পথের সাথে মিলে যায়। সুতরাং, একটি সিস্টেম এবং তার পরিবেশকে বিরোধী উদ্দেশ্য সহ দুই খেলোয়াড় হিসাবে দেখা যেতে পারে, যেখানে একজন খেলোয়াড় (সিস্টেম) "ভাল" রানের সম্ভাবনা সর্বাধিক করার লক্ষ্য রাখে, অন্য খেলোয়াড় (পরিবেশ) বিপরীত দিকে লক্ষ্য রাখে। অনেক ক্ষেত্রে, এই সম্ভাবনার একটি ভারসাম্য মূল্য বিদ্যমান, তবে উভয় খেলোয়াড়ের জন্য সর্বোত্তম কৌশল বিদ্যমান নাও থাকতে পারে। আমরা এই ক্ষেত্রে অধ্যয়নরত মৌলিক ধারণা এবং অ্যালগরিদমিক প্রশ্নগুলি উপস্থাপন করি এবং কিছু দীর্ঘস্থায়ী উন্মুক্ত সমস্যার কথা উল্লেখ করি। তারপর, আমরা সাম্প্রতিক নির্বাচিত ফলাফলগুলি উল্লেখ করি। একটি স্টোকাস্টিক গেমের উপাদানগুলি হলঃ খেলোয়াড়দের একটি সীমাবদ্ধ সেট; একটি স্টেট স্পেস (একটি সীমাবদ্ধ সেট বা একটি পরিমাপযোগ্য স্থান); প্রতিটি খেলোয়াড়ের জন্য, একটি অ্যাকশন সেট (একটি সীমাবদ্ধ সেট বা একটি পরিমাপযোগ্য স্থান); একটি ট্রানজিশন সম্ভাব্যতা, যেখানে অ্যাকশন প্রোফাইল রয়েছে, যেখানে বর্তমান অবস্থা এবং বর্তমান অ্যাকশন প্রোফাইলের পরিপ্রেক্ষিতে পরবর্তী অবস্থা হওয়ার সম্ভাবনা রয়েছে; এবং একটি পেঅফ ফাংশন থেকে, যেখানে-তম স্থানাঙ্ক, অবস্থা এবং অ্যাকশন প্রোফাইলের একটি ফাংশন হিসাবে খেলোয়াড়কে প্রদান করা হয়। খেলাটি কিছু প্রাথমিক অবস্থায় শুরু হয়। পর্যায়ে, খেলোয়াড়রা প্রথমে পর্যবেক্ষণ করে, তারপর একই সাথে ক্রিয়া নির্বাচন করে, তারপর ক্রিয়া প্রোফাইল পর্যবেক্ষণ করে এবং তারপর প্রকৃতি সম্ভাবনা অনুযায়ী নির্বাচন করে। স্টোকাস্টিক গেমের একটি খেলা, অর্থপ্রদানের একটি প্রবাহকে সংজ্ঞায়িত করে, যেখানে। ডিসকাউন্ট ফ্যাক্টর () সহ ডিসকাউন্টেড গেমটি হল সেই গেম যেখানে খেলোয়াড়কে অর্থ প্রদান করা হয়। স্টেজের খেলা হল সেই খেলা যেখানে খেলোয়াড়কে অর্থ প্রদান করা হয়। একটি দুই-ব্যক্তি শূন্য-সমষ্টি যাদৃচ্ছিক খেলার মান, যথাক্রমে, সীমাবদ্ধভাবে অনেকগুলি অবস্থা এবং ক্রিয়া সহ বিদ্যমান, এবং ট্রুম্যান বিউলি এবং ইলন কোলবার্গ (1976) প্রমাণ করেছেন যে একটি সীমাতে একত্রিত হয় যা অনন্তের দিকে যায় এবং যা একই সীমাতে একত্রিত হয় যা যায়। "অনির্দিষ্ট" খেলাটি হল সেই খেলা যেখানে খেলোয়াড়কে প্রদত্ত অর্থপ্রদান হল পর্যায়গত অর্থপ্রদানের গড়ের "সীমা"। দুই ব্যক্তির শূন্য-যোগফলের মান সংজ্ঞায়িত করতে এবং অ-শূন্য-যোগফলের ভারসাম্য পরিশোধ সংজ্ঞায়িত করতে কিছু সতর্কতা প্রয়োজন। দুই ব্যক্তির শূন্য-সমষ্টি যাদৃচ্ছিক খেলার অভিন্ন মান বিদ্যমান থাকে যদি প্রত্যেকের জন্য একটি ধনাত্মক পূর্ণসংখ্যা এবং খেলোয়াড় 1 এবং খেলোয়াড় 2-এর একটি কৌশল জোড়া থাকে যাতে প্রতিটি এবং প্রত্যেকের জন্য খেলার সম্ভাব্যতা সম্পর্কিত প্রত্যাশা দ্বারা সংজ্ঞায়িত করা হয় এবং কমপক্ষে হয়, এবং খেলার সম্ভাব্যতা সম্পর্কিত প্রত্যাশা দ্বারা সংজ্ঞায়িত এবং সর্বাধিক হয়। জিন-ফ্রাঙ্কোইস মার্টেন্স এবং আব্রাহাম নেইম্যান (1981) প্রমাণ করেছেন যে প্রতিটি দুই-ব্যক্তি শূন্য-সমষ্টি স্টোকাস্টিক খেলার একটি অভিন্ন মূল্য রয়েছে যার মধ্যে সীমাবদ্ধভাবে অনেকগুলি অবস্থা এবং ক্রিয়া রয়েছে। যদি সীমিত সংখ্যক খেলোয়াড় থাকে এবং অ্যাকশন সেট এবং অবস্থার সেট সীমাবদ্ধ হয়, তবে সীমিত সংখ্যক পর্যায় সহ একটি স্টোকাস্টিক গেমের সর্বদা একটি ন্যাশ ভারসাম্য থাকে। অসীম সংখ্যক পর্যায় সহ একটি খেলার ক্ষেত্রেও একই কথা প্রযোজ্য, যদি মোট লভ্যাংশটি ছাড়ের পরিমাণ হয়। অ-শূন্য-সমষ্টিগত খেলার একটি অভিন্ন ভারসাম্য রয়েছে যদি প্রত্যেকের জন্য একটি ধনাত্মক পূর্ণসংখ্যা এবং একটি কৌশলগত রূপরেখা থাকে যাতে একজন খেলোয়াড়ের দ্বারা প্রতিটি একতরফা বিচ্যুতির জন্য, অর্থাৎ, সকলের জন্য একটি কৌশলগত রূপরেখা, এবং দ্বারা সংজ্ঞায়িত খেলার সম্ভাব্যতা সম্পর্কিত প্রতিটি প্রত্যাশা অন্তত হয়, এবং দ্বারা সংজ্ঞায়িত খেলার সম্ভাব্যতা সম্পর্কিত প্রত্যাশা সর্বাধিক হয়। নিকোলাস ভিয়েল দেখিয়েছেন যে সীমাবদ্ধ অবস্থা এবং অ্যাকশন স্পেস সহ সমস্ত দুই ব্যক্তির স্টোকাস্টিক গেমের একটি অভিন্ন ভারসাম্য রয়েছে। নন-জিরো-সাম স্টোকাস্টিক গেমের একটি সীমিত-গড় ভারসাম্য রয়েছে যদি প্রত্যেকের জন্য একটি কৌশলগত প্রোফাইল থাকে যাতে কোনও খেলোয়াড়ের প্রতিটি একতরফা বিচ্যুতির জন্য, দ্বারা সংজ্ঞায়িত খেলার সম্ভাবনার ক্ষেত্রে স্টেজ পে-অফের গড়ের চেয়ে নিকৃষ্ট সীমার প্রত্যাশা কমপক্ষে হয় এবং দ্বারা সংজ্ঞায়িত খেলার সম্ভাবনার ক্ষেত্রে স্টেজ পে-অফের গড়ের চেয়ে উচ্চতর সীমার প্রত্যাশা সর্বাধিক হয়। জিন-ফ্রাঙ্কোইস মার্টেন্স এবং আব্রাহাম নেইম্যান (1981) প্রমাণ করেছেন যে প্রতিটি দুই-ব্যক্তি শূন্য-সমষ্টি স্টোকাস্টিক গেমের সীমিত-গড় মান রয়েছে এবং নিকোলাস ভিয়েল দেখিয়েছেন যে সীমাবদ্ধ অবস্থা এবং অ্যাকশন স্পেস সহ সমস্ত দুই-ব্যক্তি স্টোকাস্টিক গেমের একটি সীমিত-গড় ভারসাম্য রয়েছে। বিশেষত, এই ফলাফলগুলি বোঝায় যে এই খেলাগুলির একটি মূল্য এবং আনুমানিক ভারসাম্য পরিশোধ রয়েছে, যাকে বলা হয় লিমিনফ-গড় (যথাক্রমে, লিমসআপ-গড়) ভারসাম্য পরিশোধ, যখন মোট পরিশোধ পর্যায় পরিশোধের গড়ের নিকৃষ্ট (বা উচ্চতর সীমা) হয়। সীমিত সংখ্যক খেলোয়াড়, অবস্থা এবং ক্রিয়া সহ প্রতিটি অপ্রচলিত খেলার একটি অভিন্ন ভারসাম্য প্রদান, বা একটি সীমিত-গড় ভারসাম্য প্রদান, বা এমনকি একটি সীমিত-গড় ভারসাম্য প্রদান, একটি চ্যালেঞ্জিং উন্মুক্ত প্রশ্ন। একটি মার্কভ নিখুঁত ভারসাম্য হল সাব-গেম নিখুঁত ন্যাশ ভারসাম্য ধারণার একটি পরিমার্জন। খেলোয়াড়দের কৌশল নিয়ে অনিশ্চয়তার মডেল তৈরি করতে স্টোকাস্টিক গেমগুলিকে বায়েসিয়ান গেমের সাথে একত্রিত করা হয়েছে। ফলস্বরূপ স্টোকাস্টিক বায়েসিয়ান গেম মডেলটি বায়েসিয়ান ন্যাশ ভারসাম্য সমীকরণ এবং বেলম্যান অপ্টিমালিটি সমীকরণের একটি পুনরাবৃত্তিমূলক সংমিশ্রণের মাধ্যমে সমাধান করা হয়। অ্যাপ্লিকেশন স্টোকাস্টিক গেমসের অর্থনীতি, বিবর্তনীয় জীববিজ্ঞান এবং কম্পিউটার নেটওয়ার্কে অ্যাপ্লিকেশন রয়েছে। এগুলি পুনরাবৃত্ত গেমগুলির সাধারণীকরণ যা বিশেষ ক্ষেত্রে যেখানে শুধুমাত্র একটি রাজ্য রয়েছে তার সাথে সামঞ্জস্যপূর্ণ। আরও দেখুন স্টোকাস্টিক প্রসেস নোটস আরও পড়া (আন্ডারগ্রাজুয়েটদের জন্য উপযুক্ত; প্রধান ফলাফল, কোনও প্রমাণ নেই) বহিরাগত লিঙ্ক অ্যান্টোনিন কুসেরা দ্বারা স্টোকাস্টিক টু-প্লেয়ার গেমসের উপর বক্তৃতা গেম তত্ত্ব গেম ক্লাস গাণিতিক এবং পরিমাণগত পদ্ধতি (অর্থনীতি)