مقاله رویکردی نوین در حل مسائل نظریه بازیها به کمک چارچوب MapReduce

بخشی از مقاله

چکیده

در دنیای امروز، هر روز بیش از روز قبل داده تولید میشود و یکی از چالشهای پیش رو، مدیریت و پردازش این حجم عظیم اطلاعات می باشد، از طرف دیگر یکی از روشهایی که قابلیت خود را در حل مسئلههای پیچیده زیادی نشان داده است، نظریه الگوریتمی بازیها می باشد. برای پردازش داده های حجیم روش ها و چارچوبهای مختلفی تا کنون ارائه شده است، همچنین روشهای متعددی برای استفاده از روشهای نظریه الگوریتمی بازیها وجود دارد، ولی تا کنون روشی که هر دوی این قابلیتها را در کنار هم قرار دهد ارائه نشده است. در این مقاله روشی جدید برای حل مسائل مرتبط با نظریه الگوریتمی بازیها به کمک چارچوب MapReduce ارائه شده است، به کمک این روش می توان طیف وسیعی ازمسائل مرتبط با نظریه الگوریتمی بازیها را که حجم داده های آنها زیاد است حل نمود و تعادل نش آنها را بدست آورد.

کلید واژه-نظریه الگوریتمی بازیها، کلان داده، پردازش توزیع شده، چارچوب .MapReduce

-1 مقدمه

نظریه بازی یک روش برای حل مسئله در علوم مختلف نظیر اقتصاد، سیاست، کامپیوتر و ریاضی می باشد. در جوامعی می توان از نظریه بازی برای حل مسئله استفاده نمود که همه عامل ها منطقی باشند. مفهوم منطقی بودن در نظریه بازی به این معنا است که هر عامل سعی در بیشینه نمودن بهرهوری خود در بازی را داشته باشد.یکی از روشهای پیشنهادی در نظریه بازی، مفهومی به نام تعادل نش است. در استراتژی تعادل نش هر بازیکن بدون توجه به بازیکنان دیگر و بدون توجه به رفاه جامعه، بهترین عمل ممکن را بر اساس اهداف خود در بازی انتخاب میکند. اگر تمامی بازیکنان عملی انجام دهند که در تعادل نش باشد، هیچ کدام انگیزه تخطی ندارند؛ زیرا هر عاملی که عملش را عوض کند، بهرهوری او در بازی کم میشود.

جان نش ثابت کرد که همهی بازیها دارای حداقل یک تعادل نش هستند. این تعادل میتواند محض یا ترکیبی باشد. تعادل نش محض زمانی اتفاق میافتد که هر کدام از عامل ها عملش را به طور قطعی انتخاب کند، ولی در تعادل نش ترکیبی هر کدام از عامل ها عملش را به طور احتمالی انتخاب میکند.مفهوم دیگری که در نظریه بازی ها استفاده می شود، مفهوم پرتو غالب است. یک استراتژی در صورتی پرتو غالب است که سود همه عامل ها در آن بزرگتر یا مساوی سود همان عامل ها در یک استراتژی دیگر باشد. در استراتژی غالب برای تمامی حالتها، بهترین عمل یک عامل بدون توجه به عمل بقیه عامل ها انتخاب میشود.بیشینه سود جامعه یکی دیگر از مفاهیم نظریه بازی است. یک استراتژی در صورتی نشانگر بیشینه سود جامعه است، که مجموع سود همهی عاملها در آن بیشینه باشد.

روش های سنتی نظریه بازی ها مسئله ها را با داده های کم حل می نمودند. امروزه حجم دادهها به سرعت در حال افزایش است و لازم است که دادههای حجیم را پردازش کنیم.[2] حجم داده های مسائلی که برای حل آن ها از نظریه بازی استفاده می شد، نیز روز به روز رو به افزایش است. در این مقاله روشی پیشنهاد می گردد که بر اساس آن می توان از نطریه بازی برای حل مسائل در حضور داده های زیاد استفاده نمود. استفاده از داده های بسیار بیشتر موجب دستیابی به نتایج بهتر نسبت به سایر روشها میشود.در مواردی که حجم داده ها زیاد میشود، با چالش مقیاس پذیری راه حل روبرو هستیم. به طور مثال اگر داده ها دو برابر شود، ممکن است سیستم سخت افزاری مورد استفاده قادر به انجام محاسبات نباشد.

برای مواجهه با این چالش، باید مسئله را به صورت توزیع شده حل نمود. با توجه به این که روش ها و ابزار کلان داده مقیاس پذیر بوده و مسئله را به صورت توزیع شده حل میکنند، ما از این ابزار برای بدست آوردن تعادل نش استفاده می نماییم. ابزاری که برای این کار استفاده شده است، Apache Hadoop است. Hadoop یک نرم افزار متن باز است کهدارای  HDFS - Hadoop   DistrubiutedFile   system -   وMapReduce است. این ابزار بخاطر سادگی، مقیاسپذیری و تحمل خطا یکی از رایج ترین ابزارهای بررسی کلان داده است. MapReduce یک ابزار برنامه نویسی است که توسط Google برای پردازش داده های حجیم به صورت توزیع شده و موازی طراحی شده است. این ابزار یک روش ساده ولی قدرتمند، برای اجرای برنامهها به صورت توزیع شده دارد. MapReduce محیطی است که چندین کاربر، چندین کار و چندین وظیفه، منابع فیزیکی مشترکی را به اشتراک میگذارند.

MapReduce شامل دو تابع اصلی Map و Reduce است. تابع Map روی رکورد های زیادی تکرار میشود و نتایج میانی که مورد توجه ما است را به صورت کلید و مقدارش استخراج میکند. چارچوب MapReduce این نتایج میانی را بهم میآمیزد و آنها را مرتب میکند، به این معنا که نتایج با کلید یکسان را به Reducer یکسان و به صورت مرتب میفرستد. Reducer نتایج میانی با کلید یکسان را با هم تجمیع میکند و به خروجی میفرستد. MapReduce تمام این کارها را به صورت کارا انجام می دهد.در ادامه این مقاله ابتدا کارهای مشابه در فصل 2 مورد بررسی قرار میگیرند. سپس در فصل 3 روش پیشنهادی ما ارائه میشود. در بخش 4 نتایج کار مود بررسی قرار میگیرد. در بخش 5 نتیجه گیری و راهکارهای آتی بررسی میشوند. در انتها نیز مراجع و منابع استفاده شده آورده میشوند.

-2 کارهای مشابه

در زمینهی نظریه بازیها در سال های اخیر کار های خوبی انجام شده است. ولی در هیچ کدام از این کارها به این توجه نشده است که داده ها روز به روز زیاد میشود. این روشها برای حل از داده های محدودی استفاده میکنند، در حالی که ممکن است داده های انتخاب شده توسط آن ها معیار خوبی از کل داده ها نباشد.Greenwood and Tymerski - 2008 - [3] روشی را برای پیداکردن بهترین استراتژی در بازار بورس پیشنهاد داده اند. این روش به این صورت است که ویژگیهایی مثل narrow range، DOJI و hook day را برای داده ها حساب میکند. این اعداد را به سیستم فازی تبدیل میشوند. سپس با استفاده از اطلاعات به دست آمده و الگوریتم تکاملی روش هایی پیشنهاد میدهد. درنهایت با استفاده از نظریه بازی بهترین راه حل را پیدا میکند. داده های که در بازار بورس هستند بسیار زیاد هستند.

تصمیم گیری در بازار بورس باید در لحظه باشد. اگر تصمیم گیری ما تاخیر داشته باشد، فرصت از بین میرود. یکی از خصوصیات کلانداده پردازش در لحظه است. در این شرایط که هم داده ها خیلی زیاد است، هم زمان خیلی اهمیت دارد، تکنیک های کلانداده کمک زیادی میکنند.1417 Palacios-Huerta - 2003 - [4] دادهی پنالتی را از لیگ های اسپانیا، ایتالیا و انگلیس، که اکثر داده ها مربوط به لیگ ایتالیا بود را بررسی کردهاند. با استفاده از این داده ها روشی پیشنهاد داده اند. این روش بررسی میکند که احتمال موفقیت بازیکنها و دروازه بانها در اعمال مختلف ثابت باشند. این روش بررسی دیگری انجام میدهد، که انتخاب عمل دروازهبان و بازیکن ضربهزننده از اعمال قبل مستقل باشند. روش کار آن ها دقیق بوده، ولی مشکلی که دارند تعداد پنالتی های مورد بررسی بسیار کم است نمیتوانیم مطمئن باشیم که همهی پنالتیها مانند این 1417 پنالتی باشند.

Walker  and  Wooders - 2001 - [5]  سرویس های بازی تنیس را مورد بررسی قرار دادهاند . با استفاده از این داده ها روشی پیشنهاد داده اند که بررسی میکنند بازیکنها احتمال موفقیتشان در اعمال مختلف ثابت باشند و انتخاب عمل آنها از اعمال قبل مستقل باشند. در هر بازی تنیس تعداد زیادی سرویس وجود دارد. آنها با روش سنتی فقط توانسته اند مقداری از آنها را بررسی کنند. حجم دادهی زیادی در دسترس داریم، اگر از روش پیشنهادی ما استفاده می شد جامعیت خیلی بالایی داشت.Song and others - 2013 - [6] روشی را با استفاده نظریه بازی برای بهینه کردن زمانبندی در mapreduce پیشنهاد دادهاند. روش آنها به این صورت است که یک زمانبندی دو سطحی بر اساس مدل هزینه ایجاد میکنند بعد این زمانبندی را به دو بازی تقسیم میکنند سپس این بازی ها را با نظریه بازی حل میکنند.

Hungarian - 2005 - [7] مدل های مختلف اختصاص کار ها را به کارگرها را مورد بررسی قرار داده است. از این روش ها در بازی های همکارانه نظریه بازی استفاده خوبی میشود.Xin and yu - 2014 - [8] روشی را با استفاده از نظریه بازی برای تخصیص منابع در رایانش ابری پیشنهاد داده اند که شبیهروش song[6] است.Chiappori  and  others - 2002 - [9]  تعادل نش ترکیبی راوقتی بازیکن ها ناهمگون هستند بررسی کردهاند. مورد مطالعه آنها پنالتی های فوتبال است. آنها بررسی کردهاند که چگونه تعادل نش ترکیبی در پنالتی های فوتبال برقرار است. 
Bar-Eli and Azar - 2009 - [10] با استفاده از نظریه بازی وبر اساس 311 داده پنالتی روشی پیشنهاد کرده است که ادعا کردهاند بهترین استراتژی برای ضربه زننده و دروازهبان پیدا کردهاند.Goeree and others - 2003 - [11] بازی های 2*2 را بررسی کرده اند، که درصد اتفاق افتادن اعمال در داده های مشاهده شده، با درصدی که از تعادل نش ترکیبی بدست میآید، تطابق ندارد.

-3 روش پیشنهادی

روش های سنتی نظریه بازی ها مسئله ها را با داده های کم حل مینمودند. حجم داده های مسائلی که برای حل آن ها از نظریه بازی استفاده می شد، روز به روز رو به افزایش است. با توجه به این که روش ها و ابزار کلان داده مقیاس پذیر بوده، مسئله را به صورت توزیع شده حل میکنند، ما از این ابزار برای بدست آوردن تعادل نش استفاده می نماییم . ابزاری که برای این کار استفاده شده است، Apache Hadoop است. همچنین این ابزار به منظور کم شدن احتمال خطا چند کپی از هر فایل را در سرور های جداگانه قرار میدهد. داده ها را به وسیلهی Mapreduce تحلیل می کنیم.در تابع Map اول کلید های میانی تمام اعمال ممکن است. این کلید ها در Reducer با یکدیگر تجمیع میشوند. سپس نسبت هر عمل به کل اعمال عامل محاسبه میشود . به این ترتیب درصد اتفاق افتادن هر عمل اندازه گیری میشود.

در تابع Map دوم کلیدهای میانی تمام استراتژی ها است. این کلید ها در Reducer با همدیگر تجمیع میشوند. این تجمیع سود هر عامل در هر استراتژی به دست میآورد. با استفاده از سود هر استراتژی جدول بازی رسم میشود. تعادل نش به کمک جدول بازی محاسبه میشود. نتایج پیش بینی شده به وسیله تعادل نش را با نتایج اتفاق افتاده مقایسه میشوند. این مقایسه نشان میدهد که در دنیای واقعی عامل ها چه مقدار نزدیک به تعادل نش بازی میکنند. برای مثال این روش را روی پنالتی های فوتبال آزمایش کردهایم.پنالتی موقعی به یک تیم تعلق میگیرد که تیم حریف خطایی را در محوطه جریمه انجام داده باشد. فدراسیون بینالمللی فوتبال، فیفا - Fédération Internationale de Football - Association قوانینی را در مورد ضربات پنالتی نوشته است. - FIFA,2000 - [12] قوانین موقعیت بازیکن و توپ به شکل زیر مشخص شده است:

·توپ باید روی نقطه پنالتی باشد.

·بازیکنی که میخواهد ضربه بزند باید مشخص باشد.

·دروازبان باید تا زمانی که زننده پنالتی ضربه را نزده است، روی خط دروازه، روبروی او و بین دو خط دروازه باقی بماند.

·باقی بازیکن ها به غیر از ضربه زننده، باید داخل زمین، خارج محوطه جریمه، پشت نقطه پنالتی و

حداقل به فاصله 10 یارد 9.15 - متر - از نقطه پنالتی فاصله داشته باشند.

مراحل زدن پنالتی به شکل زیر مشخص شده است:
·ضربه زننده توپ را به سمت جلو میزند.

·او تا زمانی که بازیکن دیگری توپ را لمس نکرده باشد، حق ندارد توپ را برای بار دوم بزند.

·گل ممکن است به صورت مستقیم از ضربه پنالتی به ثمر برسد.

در بررسی ما فقط گل مستقیم اهمیت دارد. در این روش اگر گلی مستقیم زده نشود، آن، گل نشدن در نظر گرفته میشود. توپ حدود 0.3 ثانیه از نقطه پنالتی تا خط دروازه میرسد. از این رو دروازه بان فرصت دیدن توپ، سپس جهش را ندارد، در نتیجه این بازی یک بازی دو نفره، مجموع صفر و همزمان در نظر گرفته می شود.سود بازیکن ضربهزننده احتمال گل شدن توپ و سود دروازبان احتمال گل نشدن توپ است. هدف ضربهزننده بیشینه کردن احتمال گل شدن توپ است. هدف دروازه بان کمینه کردن این احتمال است. تعادل این بازی زمانی اتفاق می افتد که هر بازیکن از استراتژی میکس اتفاده کند.

طبق قوائد نظریه بازی تعادل میکس زمانی اتفاق می افتد که احتمال گل شدن توپ برای ضربه زننده بین تمام استراتژی هایش یکسان باشد، همچنین احتمال گل نشدن توپ برای دروازه بان بین تمام استراتژی هایش یکسان باشد. اکثر پنالتی ها به راست یا چپ زده میشوند و تعداد کمی وسط زده می شوند، درنتیجه این تعداد کم در نظر گرفته نمیشوند. فرض میشود همه پنالتیها به سمت چپ و راست زده میشوند و دروازه بانها هم فقط به چپ و راست جهش می کنند. بازیکن چپپا سمت قوی متفاوتی با بازیکن راستپا دارد، درنتیجه برای بازیکن چپپا جهت برعکس در نظر گرفته میشود. برای ضربه قویترین جهت مهم است. دروازه بان ها هم به سمت قوی ضربه زننده توجه دارند،