Multiplicative Bidding in Online Advertising

http://arxiv.org/pdf/1404.6727.pdf

موضوعات کلی کارگاه نظریه الگوریتمی بازیها

http://en.wikipedia.org/wiki/Incentive_compatibility

http://en.wikipedia.org/wiki/Mechanism_design

http://en.wikipedia.org/wiki/Revelation_principle

http://en.wikipedia.org/wiki/Combinatorial_auction

http://en.wikipedia.org/wiki/Job_scheduling_game

http://en.wikipedia.org/wiki/Coordination_game

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

من این درس را نداشتم پس ممکن است جوابها درست نباشند!

۱- الف) تعادل نش وقتی است که هیچ کس نخواهد انتخاب خودش را عوض کند.

همه عدد ۱ را انتخاب کنند. در این صورت همه به ۲/۳*۱ نزدیک‌تر هستند. چون تقارن داریم همه باید مثل هم انتخاب کنند و تنها عددی که اگر همه انتخاب کنند کسی با انجام ندادن آن برنده نمی‌شود همین ۱ است پس همین تنها تعادل نش است.

ب) با استدلال مشابه قسمت الف، همه باید عدد ۱۰۰ را انتخاب کنند.

۲- برای همه‌ی حالت‌های جدول چک می‌کنیم! (۱۲ حالت ناقابل!)

ACF: نفر اول و دوم خوشحالند ولی نفر سوم ناراضی است. (تعادل نیست)

ACG: اول ناراضی پس تعادل نیست

ADF: اول ناراضی پس تعادل نیست

ADG: سوم ناراضی پس تعادل نیست

AEF: تعادل است!

AEG: اول ناراضی است.

BCF: اول ناراضی است.

BCG: تعادل است!

BDF: دوم ناراضی است.

BDG: دوم ناراضی است.

BEF: دوم ناراضی است.

BEG: اول ناراضی است.

پس دو تا حالت تعادل داریم: AEF و BCG.

۳- تعادل‌های نش یکی دقیقاً k نفر پول بدهند و یکی دیگر اینکه هیچ کس پول ندهد. C(n,k)+1 تا در کل.

۴- چون گفته سود هر کس به تعداد رأی‌هایی است که می‌آورد، پس در تعادل باید هر کس کل بازه‌اش را انتخاب کرده باشد. همه‌ی این حالت‌ها هم تعادل هستند چون کار بیشتری نمی‌توان کرد. هزینه هم ندارد. پس برای سمت چپ y=x و برای سمت راست هم y=x است.

۵- 

max_{p\in [0,1]} p^2+100p-2np^2

p = -50 +sqrt( 2500+2n-1)

0<= p <=1

1/2 <= n <= 51

ب) خیر. چون تعادلی که پیدا کردیم بهترین حالت است.

۶- الف) در حالتی که vi=bi باشد، در حالتی که سود برنده vi-bi باشد، چون vi-bi=0 پس با سود بقیه که ۰ است برابر است و تعادل نش است. در حالتی که سود برنده vi-max bj باشد، سود برنده vi-max vj است و بقیه ۰، پس چون برنده کسی است که بیشترین قیمت را داده است و سود آن مثبت است قیمت کمتر دادن سود برنده را بیشتر می‌کند و قیمت بیشتر دادن ضرر خود فرد را. پس این هم تعادل است.

ب) چون حالت تعادل حالت بهینه هم هست، چون از قیمت بقیه خبر نداریم، ممکن است برنده نشود. پس همه بیشترین قیمت یعنی vi را می‌دهند و ماکسیمم می‌برد.

ج) اگر هر فردی با این فکر که همه قیمت را کم داده‌اند قیمت کمتری بدهد اما کسی باشد که این کار را نکرده باشد و ببرد. چون حالت دیگر این است که چنین فردی نباشد و با سود زیادی ببرد.

مؤلفه‌های همبندی در گراف‌های بزرگ

http://www.mmds-data.org/presentations/vassilvitskii_mmds14.pdf

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

کاهش با حفظ ضریب تقریب

http://www.cs.umd.edu/~hajiagha/ALB14/scribe-10-07-2014.pdf

جلسه چهارم نظریه بازی‌ها

http://www.cs.umd.edu/~hajiagha/AGT10/scribe-15-09-2010.pdf

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

http://www.cs.umd.edu/~hajiagha/AGT10/scribe-08-09-2010.pdf

ایده‌ی حل سوالهای میان ترم ۹۱ الگوریتم

۱- تکراری با سوال ۱ ما. (رجوع به پست قبلی)
۲-....
۳- به نظرم رسید با min cut حل کنیم که رأسهای یک طرف جزو مسیر هستند و یالهای طرف دیگر جزو مسیر نیستند. می‌دانیم که رأسها به ترتیب توپولوژیکی هستند (طبق شرط جهت که گذاشته)
برای اینکه رأس تکراری نباشد هم یک کپی از رأسها می‌گذاریم با یال بینهایت وصل می‌کنیم.
۴- به نظرم باید دایجسترا اجرا کنیم (کوتاهترین مسیر چون شار در طول مسیر ثابت است همینکه کوتاهترین مسیر باشد کافی است.)
۵- ب) مشابه مسأله‌ی پروژه‌ها: پروژه ها همان سرمایه گذارها هستند و پیشنیازها بازیگرهای مربوط به آن هستند.

میان ترم الگوریتم پیشرفته

۱- n عنصر و m مجموعه داریم که هر مجموعه k عضو دارد می‌خواهیم عناصر را با k رنگ، رنگ آمیزی کنیم که از هر رنگ یکی در هر مجموعه باشد.
الف) ثابت کنید که این مسأله NP است.
ب) ثابت کنید که برای k=3 ان پی کامل است. (با استفاده از ۳-رنگ پذیری گراف)
ج) ثابت کنید برای k=2 پی است.
جواب:
الف) یک مصداقش در زمان چندجمله‌ای قابل جواب دادن است.
ب) هر رأس و رأسهای مجاور را یک مجموعه بگیرید.
ج) رنگ آمیزی گراف با دو رنگ فقط برای گراف دوبخشی ممکن است (دور فرد نداشته باشد).
۲- مسأله‌ی هش کردن پویا را با فرض اینکه به جای دو برابر رادیکال n برابر کنیم که n تعداد عناصر موجود است حل کنید.
الف) زمان درج هش پویای معمولی چقدر است.
ب) حداکثر جای خالی جدول در این تعریف جدید چقدر است؟ (ثابت کنید از مرتبه رادیکال n است)
ج) زمان درج برای این حالت جدید چقدر است؟ (سرشکنی)
جواب: تابع پتانسیل را تعداد اعداد موجود منهای توان ۲ تعداد جاهای خالی +۱ گرفتم. (اون +۱ برای حالت پایه اش بود که منفی نشه)

۳- یک گراف نامشخص داریم فقط درجه ورودی و خروجی هر رأس را می‌دانیم. گراف را پیدا کنید.

جواب: شار بیشینه. n رأس سمت راست و n رأس سمت چپ می‌گذاریم و از s با درجه خروجی هر رأس و به t با درجه ورودی هر رأس وصل می‌کنیم. بین رأسهای سمت راست و چپ هم یالهای با ظرفیت ۱ می‌گذاریم. این گراف جهت دار بدون یال چندگانه و با طوقه می‌دهد. اگر بخواهیم طوقه نداشته باشد باید رأسها را به خودشان وصل نکنیم. برای یال چندگانه هم ظرفیت بینهایت بگذاریم به جای ۱.

۴- در مورد push relabel به سوالهای زیر جواب بدهید:

الف) ثابت کنید اگر رأس u پیش شار داشته باشد در Gf مسیر از u به s هست.

ب) تعداد عملیات مختلف را به دست بیاورید. non saturating push, saturating push, relabel

*اگر سوالی هست که یادم رفته بنویسم کامنت بگذارید.

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

http://www.cs.umd.edu/~hajiagha/AGT10/scribe-01-09-2010.pdf