نظریه گراف و نظریه بازی ها

Graph theory and game theory

راستش من نمی دونستم در چه مورد و موضوعی حرف بزنم بهتره به همین خاطر این موضوع انتخاب کردم.امیدوارم که خوشتون بیاد.در مورد موضوعات بعدی می تونید شما نظر بدین.برای بحث بیشتر در مورد موضوعات می تونید در گروه اینترنتی زیر عضو بشید:

Mathematics-kanoon-sampad.groups.yahoo

اینم ID منه که می تونید با من تماس بگیرید،من تا جایی که بتونم راهنمایی می کنم:

Abolfazl.taheri@yahoo.com

Taheri.abolfaz@gmail.com

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

Game Theory یا نظریه ی بازی شاخه ای به نسبت نوین در ریاضیات کاربری (با کاربرد ویژه در اقتصاد) است که در آن به مطالعه ی شرایطی می پردازیم که بازیکنان قصد دارند با انجام حرکات مختلف سودشان را بیشینه کنند.در کل Game Theory قصد در مدلیزه کردن کمیت وار شرایط اجتماعی دارد تا به نوعی به معرفی تصمیم گیری اصلح در شرایط مسأله بپردازد. این نظریه از توپولوژی برای اثبات اصول خود استفاده کرده و بر اساس قوانین احتمالات نقطه تعادل نش را دنبال می‌کند.

نظریه بازی ها در سال 1928 توسط فون نیومن مطرح شد و در سال 1944 با انتشار کتابی(Theory of Games and Economic Behavior) توسط او و مورگنشترن جایگاه وسیعی در علوم اقتصادی پیدا کرد. کتابی حجیم و پر از فرمول های ریاضی که حالت های بسیار خاصی از بازی ها را بررسی می کرد.در مورد نویسندگان کتاب نیز باید این نکته را یاد آور شد که جان فون نیومن از بزرگترین ریاضیدانان جهان و سلطان بلا منازع ریاضی در دههی 40 و 50 بود.مورگن اشترن نیز اقتصاد دانی آلمانی بود که در کار نوشتن کتاب به فون نیومن کمک می کرد (اکثر قریب به اتفاق کتاب توسط خود جان فون نیومن نوشته شده بود) در 1950 تلاشهای ریاضیدان جوان جان فوربز نش در پرینستون (مکان تولد نظریه ی بازی) برای به دست آوردن یک تعادل کارآمد نتیجه داد و تعادل نش مطرح شد.این تعادل به نحوی پلی میان بازی های تعاونی و غیر تعاونی به وجود آورد.

بازی چیست؟

یک بازی می تواند هر موقعیتی که بازیکنان (شرکت کنندگان) در آن تصمیمات راهبردی اتخاذ می کنند باشد. یعنی تصمیماتی که واکنش های یکدیگر را در آن در نظر بگیرند.

تصمیمات راهبردی به بازیکنان پاداش می دهد: نتایجی که با پاداش یا منافع توأم است. مثلا در مورد بنگاههای اقتصادی پاداش به صورت سود ظاهر می گردد یا در یک حراج به صورت رفاه مصرف کننده (ارزشی که وی برای این کار هنری قایل است منهای مقداری که باید پرداخت می کرد) نمایان می شود.

بدیهی است که همواره بازیکنان به دنبال راهبرد هایی هستند که پاداش آنها را بهینه سازد.

در بررسی بازیهای مختلف تمرکز بر روی بازی هایی است که در آن بازیکنان منطقی اند. یعنی ما باید فرض کنیم که رقبایمان نیز مثل ما به دنبال بهینه کردن منافعشان هستند. در عموم مسایل بهتر این است که فرض کنیم رقبایمان نیز به اندازه ی ما منطقی و باهوشند( هر چند که عموما این طور نیست). نوع دیگری از بازیها نیز وجود دارد که در آن بازیکنان دارای اطلاعات متقارن نمی باشند که در نهایت به بررسی موضوعاتی چون بازارهایی فاقد اطلاعات متقارن می شود.

بازیهای تعاونی و غیر تعاونی

در بازیهای تعاونی(Cooperative) بازیکنان می توانند بر سر قراردادها و راهبردهای لازم الاجرا با یکدیگر ذاکره کنند در حالیکه در بازیهای غیر تعاونی ( Non-Cooperative)این امکان وجود ندارد.

بازی های منصفانه (impartial games)

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

در یک بازی منصفانه،مستقل از اینکه نوبت کدام بازیکن است،امکانات یکسانی وجود دارد.

در اینجا بیشتر در مورد بازیهای منصفانه حرف می زنیم.حال چند نمونه بازی را معرفی می کنیم.

نیمبل(Nimbel):

بازی ساده ای را در اینجا معرفی می کنیم که در آن می توانید دست کم تا وقتی که دوستانتان هم راز و رمز بازی را یاد بگیرند،آنها را شکست بدهید.

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

شرط پایان پذیری یک بازی:دنباله ای نامتناهی از حرکتها وجود ندارد.

یک نمونه از بازی:

1

2

3

7

6

5

4

9

8

 

این یه حالت ساده از بازی نیمبل است و به راحتی نفر اول می تواند برنده شود کافیه که سکه خانه ی شماره 6 را بردارید و آن را روی سکه خانه ی 1 بگذارید.در این صورت دو جفت سکه دارید،و می توانید هر حرکتی را که رقیبتان انجام داد تقلید کنید و مطمئن باشید که بازیکن آخر خواهید بود.این را اصل مشابه سازی می نامیم.

نیم(Nim):

بازی اول را به این دلیل نیمبل نامیدیم،که یکی از شکلهای متنوع بازی نیم است.

بازی نیم مثالی از بازی های منصفانه است ودر واقع نماد بازی های منصفانه محسوب می شود در این بازی n کپه لوبیا داریم وهر بازیکن در هر مرحله می تواند یک دسته را انتخاب کند واز آن تعدادی لوبیا بردارد.(هر تعداد که بخواهد بردارد،حتی کل یک کپه را می تواند بردارد).

بازی های N و P :

بازی N به بازی می گویند که درآن کسی که نوبت اوست استراتژی برد دارد. بازی P به بازی می گویند که نفردوم در آن استراتژی برد دارد.

چگونه می توانیم pوضعیتها را در بازی نیم پیدا کنیم؟و بهترین حرکتها زمانی که در Nوضعیتها هستید،چیست؟

سعی می کنم این موضوع رو ادامه بدم و مطالب بیشتری در این مورد بگم.