তদস্তু হৃদয়ং তব

অর্থনীতির প্রায়-নোবেল পুরস্কার এবার জিতেছেন আলভিন রথ ও লয়েড শেপলি। রথ ও শেপলি গেইম থিয়োরি নামে অর্থনীতির গাণিতিক তত্ব ও তার প্রায়োগিক ব্যবহারে অবদানের জন্য পুরস্কারটি পেলেন।

এই সংবাদে আমার অনুভূতি হয়েছে তিক্ত-মধুর। গেইম থিয়োরির গণিত নান্দনিক ও প্রায়োগিক, ফলিত গণিত ও প্রযুক্তির বহু শাখায় গেইম থিয়োরির চমৎকার ব্যবহার রয়েছে। মধুরতার উৎস সেইটি। তিক্ততার কারণটি ব্যক্তিগত। ধারণা ছিল, সৃজনশীল কাজ কেউ পুরস্কার লাভের আশায় করে না। কিন্তু রাত্রির গভীরতা ও রেড ওয়াইনের আতিশয্যে একাধিক মেধাবী কিন্তু তরলজিহ্ব গণিতবিদ ও কম্পিউটার বিজ্ঞানীকে বলতে শুনেছি, তারা যে গেইম থিয়োরিতে কাজ করেন, সেটার কারণ নাকি আর কিছুই না, কোনদিন যদি অর্থনীতির নোবেল প্রাইজটা লাইগা যায়! হা হতোস্মি! এর মধ্যে আবার একটা একাডেমিক গুজবের মত উঠেছিল যে টমাস শেলিং এবং (অতুলনীয়) রবার্ট আউম্যানের ২০০৫ নোবেল পুরস্কারই গেইম থিয়োরীর শেষ পুরস্কার, ও বিষয়টা অন্তত অর্থনীতির নোবেলের ক্ষেত্রে আর “hot” নয়। কিন্তু এবারের পুরস্কার আলভিন রথ ও লয়েড শেপলিকে দেয়ায় এই বিশ্রী ডায়নামিকের আগুনে আবার ডালডা পড়ল, সেটাকে পুরোপুরি হজম করতে পারছি না।

যাহোক। এবারের নোবেল জয়ীদের কাজের একটি সহজ ধারণা পাঠককে দেয়ার চেষ্টা করা যাক। শেপলির প্রথম দিককার একটা মজার কাজের বর্ণনা নিচে দেয়া গেল।

যে সমস্যাটির সমাধান তিনি করেছিলেন (ডেভিড গেইলের সাথে) তার নাম The Stable Marriage Problem। সমস্যাটি এরকম। ধরা যাক সমান সংখ্যক বিয়ে-পাগলা নারী ও পুরুষ আছে, এবং প্রত্যেকের রয়েছে একটি পছন্দের তালিকা। যেমন, ক্লিওপাট্রার হয়ত প্রথম পছন্দ রৌরব, দ্বিতীয় মার্ক এন্টনী, তারপর রূপম এবং সর্বশেষ পছন্দ বঙ্গ সামুরাই ফরিদ আহমেদ। ইত্যাদি। প্রশ্নটি হল, কার সাথে কার বিয়ে দিলে সবগুলি বিয়ে টিকবে। বিয়ে টেকা-না-টেকার নিয়মটি এরকমঃ যদি এমন একজন নারী ও একজন পুরুষ থাকে, পরস্পরকে যারা তাদের বর্তমান সংগীদের চেয়ে বেশি পছন্দ করে, তাহলে দুজন নিজেদের বর্তমান সঙ্গীদের ছেড়ে পরস্পরকে বেছে নেবে। উদাহরণস্বরূপ, ক্লিওপাট্রার সাথে ফরিদ আহমেদ ও ঘসেটি বেগমের সাথে রৌরবের বিয়ে দিলে ক্লিওপাট্রা ও রৌরব বরং পরস্পরকেই বেছে নেবে। এরকম পছন্দের তালিকা দেয়ার পরে আমাদের লক্ষ্য হল এমন একটি সঙ্গী-সঙ্গীনীর তালিকা তৈরি করা, যাতে এধরণের কোন অস্থিতিশীল জুটি না থাকে।

সমস্যাটি গেইম থিয়োরির সমস্যা কেন, বা অর্থনীতির সাথে এর সম্পর্ক কি? আসলে অর্থনীতিবিদ্যাটাকে একটু বিমূর্ত ভাবে দেখলে আমরা দেখব, এটি হচ্ছে সামাজিক প্রেক্ষিতে মানুষ তার নিজের স্বার্থ হাসিলের জন্য কি ধরণের আচরণ করে তার বিদ্যা। গেইম থিয়োরি একেই একটি গাণিতিক রূপ দান করে। Stable Marriage Problem টি এ ধরণের সরল একটি সমস্যা — এখানে প্রত্যেকের লক্ষ্য হচ্ছে যতটা সম্ভব ভাল সঙ্গী জোগাড় করা। সমস্যার সমাধানকারী হিসেবে আমাদের লক্ষ্য হচ্ছে এমন একটি সমাধান বের করা যাতে এই “সমাজ”-টি সুস্থিত থাকে, অনবরত বিয়ে ভাঙাভাঙি না হতে থাকে। এই সমস্যাটি অর্থনৈতিক পরিকল্পকদের সামনে যেধরণের সমস্যা এসে উপস্থিত হয় তারই একটি সরল রূপ। এর একটি বাস্তব উদাহরণ হতে পারে ভর্তিচ্ছু ছাত্র-ছাত্রীকে এমন ভাবে বিভিন্ন বিশ্ববিদ্যালয়ে ভর্তির সুযোগ দেয়া, যাতে ভাল ছাত্র-ছাত্রী বা ভাল বিশ্ববিদ্যালয়ের জন্য প্রতিযোগিতা অসুস্থ কামড়কামড়ির পর্যায়ে না যায়। বস্তুত, এরকম একটি বাস্তব সমস্যায় অবদানের জন্য আলভিন রথ খ্যাতিমান।

The Stable Marriage Problem সমাধানের জন্য Gale-Shapley-র চমৎকার ও পুরুষতান্ত্রিক অ্যালগরিদমটি এরকম। ছেলেরা সবাই নিজের সবচেয়ে পছন্দের মেয়েটিকে প্রস্তাব দেবে। প্রতিটি মেয়ে তাদের পাওয়া প্রস্তাবগুলির মধ্যে সবচেয়ে ভাল জনকে (আপাতত) বেছে নেবে। এই হল প্রথম রাউন্ড। দ্বিতীয় রাউন্ডে যেসব ছেলের এই মুহূর্তে বাগদ্ত্তা নেই তারা তাদের পরের পছন্দের মেয়েটিকে প্রস্তাব করবে (সেই মেয়ের এই মুহূর্তে সঙ্গী থাকুক বা না থাকুক)। মেয়েরা আবারও তাদের পাওয়া প্রস্তাব ও এই মুহূর্তের সঙ্গী (যদি থেকে থাকে) তাদের সবার মধ্যে সবচেয়ে পছন্দের জনকে বেছে নেবে। তৃতীয় রাউন্ডে যেসব ছেলে বাগদত্তাহীন, তারা তাদের পরের পছন্দের মেয়েটিকে প্রস্তাব করবে। এভাবে রাউন্ডকে রাউন্ড চলতে থাকবে যতক্ষণ না ছেলেদের আর প্রস্তাব দেয়ার কিছু না থাকে।

দেখা যাক একটি উদাহরণ।

পুরুষ: রৌরব, রূপম, মার্ক এন্টনী, ব-সা ফরিদ আহমেদ
নারী: ক্লিওপাট্রা, ঘসেটি বেগম, অলিভিয়া, সিমন দ্য বুভোয়া

পছন্দের তালিকা (বেশি পছন্দ থেকে কম পছন্দ)
ক্লিওপাট্রা: রৌরব, মার্ক এন্ট্নী, রূপম, ফরিদ আহমেদ
ঘসেটি বেগম:, রৌরব, ফরিদ আহমেদ, মার্ক এন্টনী , রূপম
সিমন দ্য বুভোয়া: রৌরব, রূপম, মার্ক এন্টনী, ফরিদ আহমেদ
অলিভিয়া: ফরিদ আহমেদ, রৌরব, মার্ক এন্টনী, রূপম

রৌরব: অলিভিয়া, ক্লিওপাট্রা, ঘসেটি বেগম, সিমন দ্য বুভোয়া
রূপম: অলিভিয়া, ঘসেটি বেগম, সিমন দ্য বুভোয়া, ক্লিওপাট্রা
মার্ক এন্টনী: ক্লিওপাট্রা, ঘসেটি বেগম, অলিভিয়া, সিমন দ্য বুভোয়া
ফরিদ আহমেদ: ক্লিওপাট্রা, অলিভিয়া, সিমন দ্য বুভোয়া, ঘসেটি বেগম

উপরের উদাহরণের ক্ষেত্রে অ্যালগরিদমটি কাজ করবে এভাবে..

প্রথম রাউন্ড
রৌরব ও রূপম প্রস্তাব করবে অলিভিয়াকে
মার্ক এন্টনী ও ফরিদ আহমেদ প্রস্তাব করবে ক্লিওপাট্রাকে

মেয়েরা সবচেয়ে ভাল প্রস্তাব বাছাইয়ের পর জুটি হবে

রৌরব-অলিভিয়া
মার্ক-ক্লিওপাট্রা

বাকিরা সঙ্গীহীন।

দ্বিতীয় রাউন্ড
সঙ্গীহীন পুরুষ দুজন তাদের দ্বিতীয় পছন্দের মেয়েকে প্রস্তাব দেবে।

অর্থাৎ রূপম ঘসেটিকে ও ফরিদ আহমেদ অলিভিয়াকে। অলিভিয়া রৌরবকে ত্যাগ করবে, কাজেই এই রাউন্ডের শেষে তিনটি জুটি

ফরিদ-অলিভিয়া
রূপম-ঘসেটি
মার্ক -ক্লিওপাট্রা

তৃতীয় রাউন্ড
একমাত্র সঙ্গীহীন পুরুষ রৌরব তার পরের পছন্দ ক্লিওপাট্রাকে প্রস্তাব করবে। ক্লিওপাট্রা মার্ক এন্টনীকে ছেড়ে রৌরবের সাথে জুটে যাওয়ায় এ রাউন্ডের শেষে জুটি গুলি হল

ফরিদ-অলিভিয়া
রূপম-ঘসেটি
রৌরব-ক্লিওপাট্রা

চতুর্থ রাউন্ড
দারাহীন মার্ক এন্টনী তার দ্বিতীয় পছন্দ ঘসেটিকে প্রস্তাব দেবে, যে তার রূপমকে ছেড়ে মার্কের সাথেই লটকে পড়বে, কাজেই এই রাউন্ডের শেষে…

ফরিদ-অলিভিয়া
মার্ক-ঘসেটি
রৌরব-ক্লিওপাট্রা

পঞ্চম রাউন্ড
রূপম এবার তার পরের পছন্দ সিমন দ্য বুভোয়াকে প্রস্তাব দেবে। নিজের পাওয়া প্রথম প্রস্তাবটি সিমন দ্য বুভুক্ষু মহাসমাদরে গ্রহণ করায়…

ফরিদ-অলিভিয়া
মার্ক-ঘসেটি
রৌরব-ক্লিওপাট্রা
রূপম-সিমন

এই চার জুটিতে গিয়ে আমাদের সমাধান ঠেকবে। সমাধানটি যে স্তিতিশীল, অর্থাৎ কোন বিয়ে ভাঙবে না, সেটি পাঠক যাচাই করে দেখতে পারেন।

এখন প্রশ্ন হল, এই বিশেষ উদাহরণের বাইরে যেকোন উদাহরণের জন্যই অ্যালগরিদমটি একটি স্থিতিশীল সমাধান দেবে কিনা। এমনটি দাবি করার জন্য আমাদের দেখাতে হবে:

১. অ্যালগিরদমটি আদৌ শেষ হয়, অসীম সময় ধরে চলতে থাকে না
২. অ্যালগরিদমটি যখন শেষ হয়, তখন সকলেরই সঙ্গী জোটে
৩. অ্যালগরিদমটির শেষে পাওয়া সঙ্গী-সঙ্গীনী তালিকাটি স্থিতিশীল।

এই তিনটি দাবি নিচে প্রমাণ করা হল:
দাবি: অ্যালগরিদমটি এক সময় শেষ হয়।
প্রমাণ: প্রতিটি ছেলে একটি মেয়েকে একবারের বেশি প্রস্তাব দেয় না। এই প্রক্রিয়া অবশেষে শেষ হতে বাধ্য।

দাবি: শেষ পর্যন্ত সবারই বিয়ে হয়।
প্রমাণ: ধরা যাক দাবিটি সত্য নয়। তাহলে একটা ছেলে ক ও একটা মেয়ে খ পাওয়া যাবে যাদের বিয়ে হয়নি। কিন্তু অ্যালগরিদমটি এমন যে ক অবশ্যই একসময় খ কে প্রস্তাব দেবে। লক্ষ্য করুন যে প্রস্তাব পাওয়া কোন মেয়ে সঙ্গীহীন থাকতে পারে না, কারণ মেয়েরা অন্য প্রস্তাব না পেয়ে কখনও বর্তমান সঙ্গীকে পরিত্যাগ করে না। কাজেই এরকম খ আসলে থাকতে পারেনা।

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

এই তিনটি দাবি মিলিয়ে Stable Marriage Problem এর সমাধানের সঠিকতা নির্ধারণ করা গেল।