نشریه دانشکده کامپیوتر دانشگاه صنعتی اصفهان
چگونه برنده شویم؟(نگاهی بر نظریه بازی‌ها و طراحی مکانیزم)
به قلم محمدجلالی ورودی ۹۷ کارشناسی صنعتی اصفهان دانشجوی مهندسی کامپیوتر و ریاضی
بازنگری شده توسط سنا محراب بیگی و رسول بوسعیدی
زندگی سراسر بازیست. خواه به عنوان بازیکن، یا بازیچه یا مخلوطی از هر دو؛ می‌آییم و می‌رویم. صحنه‌ی بازی هم پیوسته برجا، اما در حال تغییرست. شاید بشه این رباعی خیام را تفسیری شاعرانه از نظریه بازی‌ها دونست:
ما لُعْبَتِکانیم(عروسک) و فلک لُعبَت‌باز
از روی حقیقتی نه از روی مَجاز
یک‌چند درین بساط بازی کردیم
رفتیم به صندوقِ عدم یک‌یک باز
نظریه بازی‌ها چیست؟
احتمالا فیلم ذهن زیبا رو دیدین. این فیلم زندگی جان نَش[1]، ریاضیدان و برنده‌ی نوبل اقتصاد سال ۱۹۹۴ رو نشون میده که تقریبا محال هستش اسم نظریه بازی‌ها به گوشتون خورده باشه و اسم این فرد نه!
به طور کلی میشه بازی رو در این نظریه اینطوری تعریف کرد که افراد و یا چیزهای هوشمند که خودخواه[2] و منطقی[3] هستند و با یکدیگر تعامل دارن، تلاش می‌کنن بر مبنای قوانین موجود، بهترین تصمیم رو بگیرن به طوری که سود و منفعت شخصیشون رو بیشتر کنن.
بیاین با یک مثال این مدل سازی و کاربردش رو بیشتر درک کنیم:
فرض کنین آمریکا قصد داره یک مقام بلندپایه ایرانی رو ترور کنه و در صورت ترور، ایران باید تصمیم بگیره که به مقر نظامی آمریکا حمله کنه یا نه. در این سناریوی به نسبت ساده، عوامل زیادی وجود داره، به طور مثال ممکنه این حرکت ایران باعث جنگ بین دو کشور بشه که برای هر دو کشور ضرر بسیاری داره؛ از طرفی عکس العمل نشون ندادن ایران می‌تونه وجهه بدی داشته باشه.
این که ایران و آمریکا چه استراتژی‌ای رو انتخاب کنن که به بیشترین سود برسن به کمک این نظریه قابل مدل سازی ست.
همچنین این مدل سازی در زمینه‌هایی مثل اقتصاد، سیاست، نظریه بازی تکاملی [4]، امنیت و بلاکچین[5]، هوش مصنوعی[6] و [7]GANs و به طور کلی هر مسئله‌ای که در قالب تعریف شده‌ی بالا بگنجه، کاربردهای زیادی داره.
خب حالا در ادامه مفاهیم اولیه‌ای از این نظریه رو بررسی می‌کنیم:
چه کسی منطقیه؟ (تعادل نَش[8])
فرض کنید قُلی و گُلی هنگام یه دزدی بزرگ دستشون پیش پلیس رو شده! اما پلیس فکر می‌کنه این تنها جرم اون‌ها نیست و اختلاسی که در گذشته اتفاق افتاده هم زیر سر اون‌هاست اما مدرکی علیه‌شون نیست و اعتراف خودشون تنها راه اثبات می‌تونه باشه!
پلیس‌ها تصمیم می گیرن از قُلی و گُلی جداگانه بازجویی کنن و ازشون بپرسن: "آیا دوستت مرتکب جرم قبلی هم شده؟"
این بازی سه قانون داره:
- در صورتی که جرم قبلی ثابت نشه هر دو مجرم ۲ سال حبس میرن.
- اگر جفتشون بگن دوستمون مرتکب اون جرم شده هر کدوم ۳ سال حبس میرن.
- در صورتی که یکیشون بگه دوستم مرتکب شده ولی دوست وفادارش سکوت کنه فرد اول ۱ و دوستش که لو نداده ۵ سال باید آب خنک بخوره!
بنظرتون کار منطقی چیه؟
این جاست که نَش آقا میاد وسط :)
از دید ما هر دو این افراد باید سکوت کنن تا به نفع جفتشون بشه، اما بیاین قضیه رو از دید قُلی توی اون اتاق تاریک ترسناک ببینیم. :)) از اون جایی که افراد منطقی و خودخواه دنبال بیشینه کردن سود خودشونن، قُلی پیش خودش میگه اگر گُلی تصمیم گرفته باشه سکوت کنه، من اگر به جای سکوت اون رو لو بدم به جای دو سال، یه سال حبس می‌کشم؛ از طرفی اگر گُلی من رو لو داده باشه، پس منم باید اون رو لو بدم وگرنه همه کاسه کوزه‌ها سر من خراب میشه و پنج سال باید زندان برم!
در نتیجه قُلی تصمیم می‌گیره زیر آب دوستش رو بزنه؛ با همین استدلال گُلی هم همینطور!
به این نقطه از بازی که این دو بازیکن انتخاب کردن، تعادل نَش می‌گیم که در اینجا بازی پایدار میشه و هیچ بازیکنی نمی‌تونه با عوض کردن استراتژی خودش و با فرض ثابت بودن استراتژِی فرد مقابل، سودش رو بیشتر کنه.
شاید فکر کنین شرایط این بازی یک حالت خاص است و کاربرد زیادی نداره؛ ولی برای مثال سناریو زیر رو در نظر بگیرین:
شرکت کوکاکولا و پپسی قصد دارن در مورد فروش و تبلیغاتشون تصمیم بگیرن.
فرض کنین این دو شرکت محصولی با کیفیت یکسان تولید می‌کنن (هر چند همه می‌دونیم پپسی بهتره :دی). اگر هر دو شرکت تبلیغ نکنن براشون بهتره چون پولی خرج نمی‌کنن و بازار هم بینشون تقسیم میشه؛ اما اگر یه شرکت تبلیغ کنه و اون یکی نکنه، همه سهم بازار مال اون میشه و شرکت دوم فروشش صفر میشه و ضرر می‌کنه! پس جدول بازی‌ای که استراتژی‌های بازیکنان و سود حاصل از هر استراتژی رو نشون میده به شکل زیر میشه: (سطر‌ها استراتژی‌های شرکت پپسی هستن و ستون‌ها استراتژی‌های شرکت کوکاکولا، همچنین زوج مرتب‌ها سود هر بازیکن رو نشون میدن که عضو اول سود پپسی و عضو دوم سود کوکاکولاست.)
باز هم اینجا استدلال مسئله قبلی تکرار میشه! هر دو شرکت دست به تبلیغات می‌زنن چون اگر طرف مقابلشون تبلیغ کنه و اون‌ها نکنن سودشون کمینه میشه؛ همچنین اگر طرف مقابلشون تبلیغ نکنه، پس اونا باز باید تبلیغ کنن چون سودشون بیشتر میشه پس سود ۲ بهشون می‌رسه، پس این جا هم تعادل نَش بازی نقطه (۲ و ۲) میشه.
خب این دو مسئله‌ای که با هم دیدیم رو تحت عنوان مسئله دوراهی زندانی[9] می‌شناسیم که یکی از مسائل معروف در نظریه بازی‌هاست.
جالبه بدونین یکی از قضیه‌هایی که نَش اون رو اثبات کرد این بود که همه‌ی بازی‌ها تعادل نَش دارن و همیشه استراتژی‌ای وجود داره که به تعادل نَش منتهی میشه. همین نکته باعث شده که نظریه بازی‌ها قدرت زیادی داشته باشه.
راه حلی برای راه حل‌ها!
همون طور که در دو مثال قبل دیدیم، همیشه منطقی عمل کردن رسیدن به بیشترین سود نیست! ولی ما می‌خوایم تلاش کنیم که افراد به سود بیشتری برسن و سوالی که پیش میاد اینه که آیا نظریه بازی راه حلی برای رسیدن به راه حل‌های خوب داره؟
اینجاست که سروکله طراحی مکانیزم پیدا میشه، طراحی مکانیزم[10] که اون رو به reverse game theory هم می‌شناسن، تلاش می‌کنه که قوانین بازی رو جوری تغییر بده و بازی جدیدی طراحی کنه که سود این افراد منطقی و خودخواه در راستای سود اجتماعی قرار بگیره و فاصله نقطه‌های خوب بازی رو به تعادل نَش که حاصل بازی خودخواهانه‌ست نزدیک کنه.
برای مثال، دوراهی زندانی رو در نظر بگیرین که افراد لو می‌دادن؛ یه راهکاری که مافیاها برای حل این مسئله انجام میدن این هست که با تهدید به کشتن خانواده بهت پیشنهادی میدن که نتونی رد کنی! در حقیقت کاری می‌کنن که سود حاصل از لو دادن رفیقش اصلا به چشم نیاد و هر دو ساکت بمونن.
تقسیم کیک! یک مثال ملموس‌تری که میشه زد:
قُلی و گُلی که همو لو ندادن و زود از زندان آزاد شدن جشن دونفره می‌گیرن و یک کیک می‌خوان با هم بخورن! اما باز دعواشون میشه چون هر کس می‌خواد قسمت بیشتری از کیک رو بخوره :)
یک راهکار ساده این است که نفر اول تقسیم و نفر دیگر انتخاب کنه. همین ایده، نمونه مکانیزم تقسیم عادلانه‌ست.
اما اگر دوستشون نٌقلی هم به جمع اون‌ها اضافه بشه چی؟ چطوری این کیک رو بین سه نفر تقسیم کنیم که عادلانه باشه و بهم حسودی[11] نکنن و شرایط یکسان باشه؟
یکی از راه حل‌های این مسئله که می‌تونه به n نفر هم تعمیم پیدا کنه این هست که یک فرد از ابتدای کیک چاقو رو روی کیک حرکت بده و هر کس زودتر ادعای مالکیت کرد از ابتدا تا آن قسمت رو بهش بدیم. به همین ترتیب برای قسمت باقی مانده کیک هم این کار رومی‌کنیم.
در این حالت به هر کس حداقل یک سوم می‌رسه چون اگر کسی وجود داشته باشه که یک سوم بهش نرسیده باشه، در مقابلش فرد دیگه‌ای وجود داره که بهش بیشتر رسیده که در این صورت، فرد مدعی می‌تونست اون رو انتخاب کنه! (این راه حل با کمی تغییر برای کیک‌هایی با طعم‌های مختلف و زمانی که علایق افراد متفاوت‌ست هم می‌تونه تعمیم پیدا کنه!)
مسئله تقسیم کیک می‌تونه به تقسیم ارث، اجاره بها، مالیات و … بین چندین نفر که هر کسی علایق خاص خودش رو داره تعمیم پیدا کنه. به طور کلی به این دسته از مسائل "تقسیم منصفانه"[11] میگن.
ولی طراحی مکانیزم به همین جا خلاصه نمیشه!
از الگوریتم‌های قیمت گذاری کالا که گوگل و شرکت‌های بزرگ استفاده می‌کنن، برگزاری مزایده‌هایی که هم برگزارکننده مزایده بیشترین سود رو ببره و هم افراد شرکت‌کننده تجربه خوبی از این مزایده داشته باشن تا بیان الگوریتم‌های رای گیری‌ای که عادلانه باشه و حتی کنترل ترافیک خیابان‌ها کاربردهای این نظریه‌ست که هر کدام دنیایی هستن و تا به امروز موفق به کسب نوبل‌های زیادی شدن!
همه ما مدام در تعامل با دیگرانیم و بازیکن بازی‌هایی هستیم که میشه اسمشون رو زندگی گذاشت. از بچگی تفاوت‌های زیادی داشتیم، بعضی خوب و خوشحال‌کننده، بعضی شاید به ظاهر ناعادلانه؛ همین تفاوت‌ها باعث شده هر کدام از ما استراتژی‌های متفاوتی در این بازی داشته باشیم؛ علم نظریه بازی‌ها شاید بتونه در این راستا کمکمون کنه. :)
مراجع:
- Essentials of Game Theory Book
- Algorithmic game theory Course
پانویس‌ها:
[1] John Forbes Nash Jr.
[2] Selfish
[3] Rational
[4] Evolutionary Game Theory
[4] BlockChain
[5] Artificial Intelligence
[6] Generative adversarial network
[7] Nash Equilibria
[8] Prisoner’s Dilemma
[9] Mechanism Design
[10] Envy Free
[11] Fair Division
مطلبی دیگر از این انتشارات
روش های توسعه اپ موبایل
مطلبی دیگر از این انتشارات
جنگ برنچ‌ها؛ نبردی برای کنترل کد;
مطلبی دیگر از این انتشارات
مفهوم قرارداد هوشمند و کاربرد آن در بیمه اتومبیل