চিরায়ত অর্থনীতিতে বাজারগুলো ভারসাম্যে পৌঁছায় মূল্যের মাধ্যমে: চাহিদা বেশি হলে দাম বাড়ে; সরবরাহ বেশি হলে দাম কমে। কিন্তু মানব সভ্যতার সবচেয়ে সংবেদনশীল ও মহৎ ক্ষেত্রগুলোতে অর্থের লেনদেন আইনত, নৈতিকভাবে ও সামাজিকভাবে সম্পূর্ণ নিষিদ্ধ। আপনি হার্ভার্ড বা ঢাকা মেডিকেলে রেসিডেন্সির সিট নিলামে তুলে সর্বোচ্চ ধনী শিক্ষার্থীর কাছে বিক্রি করতে পারেন না; বাবা-মায়েরা সরকারি স্কুলে ভর্তির সিট টাকা দিয়ে কিনতে পারেন না; ডায়ালাইসিসের ধনাঢ্য রোগীর কাছে মানুষের কিডনি বিক্রি করা আন্তর্জাতিক আইনে অপরাধ। যেখানে টাকার ব্যবহার নিষিদ্ধ, সেখানে কীভাবে একটি ন্যায্য, দক্ষ ও নিখুঁত বাজার তৈরি করা সম্ভব? ১৯৬২ সালে দুই গণিতবিদ ডেভিড গেল এবং লয়েড শ্যাপলে এক অমর গবেষণাপত্র প্রকাশ করেন: “College Admissions and the Stability of Marriage”। তাদের ডেফার্ড অ্যাকসেপ্টেন্স অ্যালগরিদম বাজার নকশায় বিপ্লব ঘটায়, যার জন্য ২০১২ সালে অ্যালভিন রথ এবং লয়েড শ্যাপলে নোবেল পুরস্কার লাভ করেন।
দ্বিমুখী ম্যাচিং ও ব্লকিং পেয়ার (Blocking Pairs)
ধরা যাক দুটি দল রয়েছে: $n$ জন ডাক্তার (বা বর) এবং $n$ টি হাসপাতাল (বা কনে)। প্রতিটি ডাক্তারের কাছে হাসপাতালগুলোর একটি নিজস্ব পছন্দের তালিকা রয়েছে, এবং প্রতিটি হাসপাতালের কাছে ডাক্তারদের পছন্দের তালিকা রয়েছে।
একটি বণ্টনকে অস্থিতিশীল বলা হবে যদি সেখানে একটি ব্লকিং পেয়ার $(m, w)$ তৈরি হয়: ডাক্তার $m$ তার বর্তমান হাসপাতালের চেয়ে হাসপাতাল $w$-কে বেশি পছন্দ করে, এবং একই সাথে হাসপাতাল $w$-ও তার বর্তমান ডাক্তারের চেয়ে ডাক্তার $m$-কে বেশি পছন্দ করে! এমন জুটি তৈরি হলে তারা প্রাতিষ্ঠানিক বরাদ্দ ছুড়ে ফেলে নিজেরাই গোপনে চুক্তি করবে, ফলে পুরো ব্যবস্থা ধসে পড়বে। একটি ম্যাচিংকে স্থিতিশীল (Stable) হতে হলে এমন কোনো ব্লকিং পেয়ার থাকা চলবে না।
গেল-শ্যাপলে ডেফার্ড অ্যাকসেপ্টেন্স অ্যালগরিদম
গেল এবং শ্যাপলে এমন একটি অ্যালগরিদম তৈরি করলেন যা সসীম ধাপে নিখুঁত স্থিতিশীল ম্যাচিং এনে দেয়:
ধাপ ১: প্রতিটি অবিবাহিত পুরুষ তার পছন্দের তালিকার ১ নম্বর নারীকে বিয়ের প্রস্তাব দেয়। প্রতিটি নারী তার কাছে আসা সমস্ত প্রস্তাব বিবেচনা করে সবচেয়ে পছন্দের পুরুষটিকে সাময়িক বিবেচনায় (Tentative Hold) রাখে এবং বাকিদের সরাসরি ফিরিয়ে দেয়।
ধাপ ২: যারা প্রত্যাখ্যাত হলো, তারা তাদের তালিকার পরবর্তী পছন্দের নারীকে প্রস্তাব দেয়। নারীরা নতুন প্রস্তাব এবং আগের রাখা প্রস্তাব তুলনা করে সেরা একজনকে রেখে বাকিদের বাতিল করে।
সমাপ্তি: যখন আর কোনো পুরুষ প্রত্যাখ্যাত হবে না, তখন সাময়িক রাখা জুটিগুলোই চূড়ান্ত বিবাহ হিসেবে কার্যকর হয়।
স্থিতিশীলতা ও প্রস্তাবকের শ্রেষ্ঠত্ব
গেল ও শ্যাপলে প্রমাণ করলেন:
- অ্যালগরিদমটি নিশ্চিতভাবে শেষ হবে এবং ফলাফলটি শতভাগ ব্লকিং পেয়ারমুক্ত স্থিতিশীল হবে।
- যারা প্রস্তাব দেয়, তারা সম্ভাব্য সকল স্থিতিশীল ম্যাচিংয়ের মধ্যে তাদের সর্বোত্তম পছন্দ লাভ করে!
- ১৯৮২ সালে অ্যালভিন রথ প্রমাণ করেন যে প্রস্তাবকদের জন্য সত্য পছন্দের তালিকা দেওয়াই একমাত্র প্রভাবশালী কৌশল (Dominant Strategy)।
বিয়ে থেকে হাজার হাজার মানুষের জীবন রক্ষা
১৯৯০-এর দশকে অর্থনীতিবিদ অ্যালভিন রথ আমেরিকার ন্যাশনাল রেসিডেন্ট ম্যাচিং প্রোগ্রামকে গেল-শ্যাপলে অ্যালগরিদম দিয়ে নতুন রূপ দেন, যা আজও প্রতি বছর ৪০,০০০ নবীন চিকিৎসকের ক্যারিয়ার নির্ধারণ করে।
২০০৪ সালে অ্যালভিন রথ এই ম্যাচিং অ্যালগরিদম প্রয়োগ করেন মানুষের কিডনি প্রতিস্থাপন বিনিময় (Kidney Exchange)-এ। প্রায়শই রোগীর আত্মীয় কিডনি দিতে চাইলেও রক্তের গ্রুপ বা অ্যান্টিবডির কারণে তা ম্যাচ করে না। রথের ম্যাচিং নেটওয়ার্ক এমন শত শত অসম জুটির মধ্যে চক্রাকার বিনিময় (Donor Swap Chains) তৈরি করে, যা কোনো অর্থের লেনদেন ছাড়াই হাজার হাজার মুমূর্ষু রোগীর প্রাণ বাঁচিয়ে চলেছে।
