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

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

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

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

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

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

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 را می‌دهند و ماکسیمم می‌برد.

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