network flow: pre-flow push algorithm

مرجع: http://cseweb.ucsd.edu/classes/sp11/cse202-a/lecture8-final.pdf

http://cseweb.ucsd.edu/classes/sp11/cse202-a/lecture9-final.pdf

اسلایدهای نظریه الگوریتمی بازی‌ها

http://www.cs.umd.edu/~hajiagha/AGT10/AGT14.html

با توجه به اینکه اسلایدهای اینجا از بقیه بهتر بود از این به بعد را از روی این جلو می‌رویم.

MIT algorithmic game theory

http://people.csail.mit.edu/costis/6896sp10/

Bayesian Mechanism Design

http://www.sigecom.org/ec12/slides/Tutorial-bamd.pdf

جلسه اول

مرجع: http://theory.stanford.edu/~tim/f13/l/l1.pdf

اهداف کلی نظریه الگوریتمی بازی‌ها:

۱- چطور سیستمی طراحی کنیم که با وجود شرکت کنندگان هوشمند، تضمین کارایی داشته باشد. (طراحی مکانیزم‌ها: علم قانون گذاری)

مثال: در مسابقه‌ی المپیک تنیس بانوان در سال ۲۰۱۲، ۴ تیم در ۴ گروه با هم مسابقه می‌دادند. مسابقه دو مرحله بود: مرحله‌ی اول هر تیم با هر تیم دیگر مسابقه می‌داد و مرحله‌ی بعدی حذفی بود. می‌خواهیم نشان دهیم مغایرت قانون و هدف شرکت کنندگان باعث شکست این سیستم می‌شود.

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

در مرحله‌ی نیمه نهایی مسابقات ۴ تیم از هر گروه باقی می‌مانند و در نتیجه ۲ مسابقه برگزار می‌شود که نفرات اول-دوم و نفرات سوم-چهارم را مشخص می‌کند. سپس در مرحله‌ی نهایی دو مسابقه‌ی دیگر انجام می‌شود و برندگان نهایی مشخص می‌شوند.

اشکال: قوی‌ترین تیم در گروه اول است. تیم‌های گروه دوم هر کدام سعی می‌کنند ببازند تا با تیم ضعیف‌تر در مرحله نهایی مواجه شوند و مدال نقره را به دست بیاورند، چون مدال طلا که حتما به قوی‌ترین تیم می‌رسد.

۲- چه زمانی رفتار خودخواهانه نزدیک به بهینه است؟ (هزینه‌ی بی‌نظمی)

وقتی که ما قانون‌گذار نیستیم.

مثال: فرض کنید در s هستیم و می‌خواهیم به t برویم. دو مسیر وجود دارد: اولی ابتدا یک مسیر تنگ دارد که زمان طی کردن آن با ترافیک آن متناسب است و بعد یک مسیر بزرگتر دارد که زمان ثابت ۱ می‌برد. مسیر دومی برعکس آن است. پس زمان طی کردن هر مسیر 1+x است. پس مسیرها یکسان هستند و باید ترافیک بین آنها نصف شود. (فرض کنید x<=1 باشد). در نتیجه زمان هر مسیر ۱.۵ می‌شود.

اگر یک مسیر با زمان صفر در جهت نشان داده شده در شکل اضافه کنیم، مسافران چطور رفتار می‌کنند؟

طول مسیر گذرنده از یال جدید 2x است که همیشه کمتر از طول مسیرهای دیگر خواهد بود. به همین دلیل هر فردی این مسیر را انتخاب می‌کند چون در صورتی که ترافیک نباشد از همه سریعتر است، اما وقتی همه از این مسیر عبور کنند، زمان هر کدام از یالهای x برابر ۱ می‌شود و در نتیجه همه ۲ ساعت طول می‌کشد تا به مقصدشان برسند.

اگر مدیری باشد که افراد را ملزم به طی کردن مسیری خاص کند، می‌توان از این امر جلوگیری کرد. نسبت بهترین سیستم با افراد هوشمند و بهترین سیستم ممکن را هزینه‌ی بی‌نظمی price of anarchy می‌گویند. در این مثال خاص جواب بهینه مثل حالت قبل ۱.۵ است و جواب سیستم هوشمند ۲ است پس:

POA = 2/1.5 = 4/3

همه می‌دانند تعادل در سیستم بهینه نیست. ما سعی می‌کنیم روشی پیدا کنیم که POA تا حد امکان به ۱ نزدیک باشد.

مثال ۲: نخ و فنر

در شکل زیر یک سر نخ به میخ و سر دیگر آن به فنر وصل است. به سر دیگر فنر یک فنر دیگر وصل است که به آن یک وزنه‌ی سنگین وصل است. همچنین فنر اول به طور مستقیم به وزنه و فنر دوم به طور مستقیم به میخ با هر کدام با یک نخ شل وصل شده‌اند.

با فرض ایده‌آل بودن فنرها تغییر طول آنها با وزنه‌ای که به آنها آویزان است متناسب است. در این صورت این مسأله مشابه مثال قبل می‌شود که نیروی وارد شده به فنر معادل ترافیک و طول معادل زمان است. می‌توانیم طول فنرها را طوری انتخاب کنیم که وضعیت b حالت تعادل سیستم باشد.

در حالت اول فنرها سری هستند در نتیجه طول هر کدام زیاد است و متناسب با وزنه است. در حالت دوم که نخ محکم (که دو فنر را وصل می‌کرد) بریده شده است، فنرها موازی می‌شوند و نصف وزن روی هر کدام می‌افتد، در نتیجه طولشان نصف می‌شود.

این مثالی از کاربرد پارادوکس Braess است.

۳- پیچیدگی حالت تعادل: آیا بازیکنان یاد می‌گیرند؟

چطور بازیکنان به یک تعادل می‌رسند؟ (اصلاً می‌رسند؟)

حالت تعادل، حالتی در سیستم است که هر کس می‌خواهد همان طور که هست بماند. (وضعیت پایدار)

مثال: بازی سنگ-کاغذ-قیچی را در نظر بگیرید. در این بازی هیچ راه حل قطعی برای بردن وجود ندارد و هر حرکت می‌تواند به نفع هر کدام از بازیکن‌ها باشد. در زیر ماتریس دوتایی آن را می‌بینید: (یک بازیکن عمل روی سطرها و دیگری عمل روی ستونها را انجام می‌دهد و در هر خانه سود بازیکنها نوشته شده است.)

ایده‌ی von Neumann: اگر هر دو بازیکن به صورت تصادفی یکنواخت بازی کنند، دیگری نمی‌تواند ببرد. متوسط سود در این حالت صفر خواهد شد. به توابع تصادفی با این ویژگی تعادل نش می‌گویند.

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

قضیه نش: هر بازی با ماتریس دوتایی حتماً یک تعادل نش دارد.

هر بازی با تعداد بازیکن‌های متناهی یک تعادل نش دارد.

برای بازی‌ها با تعادل صفر می‌توان در زمان چندجمله‌ای تابع تعادل نش را به دست آورد. این کار را می‌توان با linear programming یا در صورت مجاز دانستن مقداری خطا، با الگوریتم‌های یادگیری ساده بازگشتی انجام داد.

هیچ راهی برای محاسبه‌ی تابع نش در بازی‌های غیر جمع-صفر (حالت کلی) وجود ندارد. (PPAD-hard)

اکثر بازی‌ها نیاز دارند که یک نفر (بازیکن یا طراح) تابع تعادل نش را بداند. 

نظریه الگوریتمی بازی‌ها

سایت درس در استنفورد: http://theory.stanford.edu/~tim/f13/f13.html

سایت درس در شریف (قدیمی): http://www.ce.sharif.ir/courses/90-91/2/ce835-1

(کاربرد سایت شریف در تمرین‌ها است)

مراجع درس:

1. Algorithmic Game Theory, by Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani, 

2. A Course in Game Theory, by Martin J. Osborne

3. Networks, Crowds, and Markets, by David Easley and Jon Kleinberg

که مرجع اصلی که همان مرجع اول است را می‌توانید دانلود کنید:

http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf