پاورپوینت بازیهای تکراری

بخشی از پاورپوینت

اسلاید 1 :

بازیهای تکراری

اسلاید 2 :

بازیهای تکراری محدود
در بازی تکراری، یک بازی مثل G چندین بار بازی می شود.
به هر دور از بازی یک تکرار یا راند گفته می شود.
به G بازی طبقه ای نیز گفته می شود.
Agent 1: C
D
Agent 2: C
C
دور اول:
دو دوم:
معضل زندانی
3+0 = 3
3+5 = 8
Total payoff:
Nau: Game Theory 2
معضل زندانی تکراری با دو تکرار

اسلاید 3 :

6, 6
3, 8
8, 3
4, 4
3, 8
0, 10
5, 5
1, 6
8, 3
5, 5
10, 0
6, 1
4, 4
1, 6
6, 1
2, 2
Stage 1
Stage 2

اسلاید 4 :

استنتاج معکوس

اگر تعداد تکرارها محدود و معلوم باشد می توان با استنتاج معکوس یک SPE را به درست آورد.
مثال: معضل زندانی با تعداد تکرار معلوم
در دور آخر، راهبرد غالب D است.
چون بازی تمام می شود بهتر است هر کس راهبرد غالب خود را بازی کند.
در دور ماقبل آخر نیز راهبرد غالب D است.
..
لذا در تمام دورها راهبرد غالب (D,D) است.
این استدلال ضعیف است و از لحاظ تجربی نقض شده است.
از لحاظ تئوری زیر سوال است.
Nau: Game Theory 4

اسلاید 5 :

Nau: Game Theory 5
سود بازیگر i ام در آینده برابر است با جمع تخفیف یافته ی تمام سودها:
که p (with 0 ≤ p≤ 1) یک ثابت است به اسم عامل تخفیف
دو راه هم ارز برای تفسیر عبارت فوق وجود دارد:
بازیگر حال را به آینده ترجیح می دهد.
بازیگر به آینده توجه می کند، اما احتمال دارد که بازی در پایان هر دور با احتمال 1 − p تمام شود.

بازیهای تکراری محدود

اسلاید 6 :

مثال
Nau: Game Theory 6
بعضی از راهبردهای معروف بازی معضل زندانی:
»AllC: همواره همکاری کنید.
»AllD : همواره خیانت کنید.
»Grim: تا وقتی که دیگری خیانت نکرده همکاری کنید. بعد از آن همواره خیانت کنید.
»Tit-for-Tat (TFT): در گام اول همکاری کنید. در گامهای بعدی بازی بازیگر را دگام قبلی تکرار کنید.
Tester: دور اول خیانت کنید. اگر بازیگر دوم تلافی کرد، TFT بازی کنید. در غیر این صورت یک در میان C و D بازی کنید.
اگر عامل تخفیف بزرگ باشد هر کدام از راهبردهای زیر تعادل نش هستند:
(TFT, TFT), (TFT,GRIM), and (GRIM,GRIM)
TFT Tester
CD
DC
CC
CC
CC
CC
CC
TFT
or
GrimAllD
CD
DD
DD
DD
DD
DD
DD
.
.
AllC,AllC,
Grim,Grim, or TFTor TFT
CC
CC
CC
CC
CC
CC
CC

اسلاید 7 :

Nau: Game Theory 7
تعادل در بازیهای تکراری: نظریه ی folk
نظریه folk می گوید که در بازیهای تکراری امکان وقوع تعادل وجود دارد:

در یک بازی تکراری نامحدود G، یک تعادل نش با مقدار سود (p1, p2, …, pn) وجود دارد اگر و فقط اگر:
G دارای یک راهبرد ترکیبی (s1, s2, …, sn) با خاصیت زیر باشد:
برای بازیگر i ام، اگر بازیگران دیگر از راهبرد minimax در مقابل i استفاده کنند، سود si از pi بیشتر یا مساوی باشد.

اسلاید 8 :

اثبات و مثال
اثبات شامل دو قسمت است:
از تعریف بهترین پاسخ و minimax استفاده کنید و نشان دهید که سود بازیگر در هر تعادل، از مقدار minimax بیشتر است.
نشان دهید که چگونه می توان یک تعادل ساخت که به هر بازیگر مثل i سود متوسط pi می دهد و:
در این تعادل، هر بازیگر تعدادی از خروجیهای بازی را در یک سیکل بسته انتخاب می کند تا همه به سود (p1, p2, …, pn) برسند.
اگر بازیگر i سیکل مربوط به خود را انجام ندهد، بقیه می توانند با اتخاذ راهبرد minimax آنرا جریمه کنند.
Example 2:
IPD with
(p1, p2) = (2.5,2.5)

Agent 1 Agent 2 DC
CD
DC
CD
DD
DD
DC
DD
Example 1:
IPD with (p1, p2) = (3,3)
Other
Grimagent
CC
CC
CC
CC
CD
DC
DC
DC
Nau: Game Theory 8

اسلاید 9 :

Nau: Game Theory 9
در صورتی اتخاذ راهبرد تعادل نش برای شما مناسب است که بقیه نیز راهبردهای تعادل نش خود را انتخاب کنند.

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

دلیل این که بقیه راهبرد تعادل نش خود را بازی نمی کنند چیست؟
آنها نیز ممکن است سعی کنند رفتار شما را پیش بینی کنند.

اسلاید 10 :

Nau: Game Theory 10
TFTTFT
TFT Grim
TFT Tester
TFTAllD
استفاده از راهبرد TFT در مقابل بقیه ی راهبردها
در تورنمنت Axelrod’s ، معمولا TFT بهترین جواب را می دهد.
می تواند با انواع متعددی از بازیگران به تعادل برسد.
می تواند جلوی سوء استفاده بازیگران بدخواه را بگیرد.
TFTAllC

اسلاید 11 :

دو بازیگر TFT را در نظر بگیرید.

یک حرکت تصادفی یا سوءبرداشت می تواند منجر به زنجیره ای از تلافیها شود.
. . .
. . .
Noise
Retaliation
Retaliation
وجود نویز در سیستم می تواند مانع رسیدن به تعادل شود.
Nau: Game Theory 11

اسلاید 12 :

Nau: Game Theory 12
بعضی راهبردهای مناسب برای محیطهای نویزی
قانون: در مواقع بروز مشکلات بیشتر گذشت کنید.

Tit-For-Two-Tats (TFTT)
»اگر بازیگر دیگر دوبار خیانت کرد، شما تلافی کنید.
این راهبرد مشکل خیانتهای تکی را حل می کند، اما امکان سوء استفاده ی طرف مقابل وجود دارد.
Generous Tit-For-Tat (GTFT)
» به صورت تصادفی گذشت کنید.
»از لحاظ امکان سوء استفاده از TFTT بهتر است و از لحاظ حفظ همکاری بدتر است.
Pavlov (پاولوف)
»اگر بردید ادامه دهید، اگر باختید روش را عوض کنید.
اگر دفعه ی قبل 3 یا 5 امتیاز به دست اوردید، حرکت دفعه ی قبل را تکرار کنید.
اگر دفعه ی قبل 0 یا 1 امتیاز به دست آوردید، حرکت قبلی را معکوس کنید.
» لذا اگر بازیگر دیگر به صورت دایم خیانت کند، پاولوف به صورت متناوب D و C را انتخاب می کند.

اسلاید 13 :

Nau: Game Theory 27
تغییر رفتار
تغییر رفتار طرف مقابل دو دلیل دارد. یا دلیل آن نویز است یا این که طرف مقابل تغییر راهبرد داده است.
در مثال روبرو، وقوع نویز باعث می شود بازیگر دوم به طور دایم تغییر رفتار دهد.
چگونه بین نویز و تغییر دایمی رفتار تفاوت قایل شویم؟
These moves are not noise
CC
CC
C DC
CD
CD
CD
:D
:D
::
من از Grim استفاده می کنم. اگر حتی یکبار خیانت کنی، هیچوقت تو را نمی بخشم.

اسلاید 14 :

تشخیص تغییر رفتار
ممکن است عدم همکاری طرف مقابل ناشی از نویز باشد، بهتر است صبر کنم.
C C C D D D D D
:
C C C C C C D D
:
طرف مقابل واقعا تغییر کرده است. بهتر است من هم تغییر کنم.
تحمل موقتی:
وقتی رفتار طرف مقابل مورد انتظار شما نیست
سریع قضاوت نکنید.
چند تکرار صبر کنید و بعد قضاوت کنید.
اگر موضوع ادامه پیدا کرد، بهره ی خود را بر اساس رفتار کنونی طرف مقابل بهینه کنید.
طرف مقابل قصد همکاری دارد
Nau: Game Theory 14

اسلاید 15 :

سریهای ریاضی

اسلاید 16 :

تکرار نامحدود بازی زندانی
محاسبه ی سود: فرض کنید بازیگر دوم از Grimm Trigger استفاده کند. سود مورد انتظار بازیگر دوم چقدر است؟
اگر بازی با احتمال p تکرار شود و با احتمال 1-p خاتمه یابد.

اگر بازیگر اول همیشه همکاری کند:
Stage 1Stage 2Stage 3 Stage 4 · · ·
33·p + 0·(1-p)3·p2 + 0·(1-p2) · · · ·= 3 +3p + 3p2 + 3p3 + · · ·

اگر بازیگر اول همیشه خیانت کند:
Stage 1Stage 2Stage 3 Stage 4 · · ·
51·p + 0·(1-p)1·p2 + 0·(1-p2) · · · ·= 5 + 1p + 1p2 + 1p3 + · · ·

اسلاید 17 :

تکرار نامحدود بازی زندانی
محاسبه ی سود: فرض کنید بازیگر دوم از Grimm Trigger استفاده کند. سود مورد انتظار بازیگر دوم چقدر است؟
اگر بازی با احتمال 0.9تکرار شود و با احتمال 0.1خاتمه یابد.


اگر بازیگر اول همیشه همکاری کند:
Stage 1Stage 2Stage 3 Stage 4 · · ·
33·p + 0·(1-p)3·p2 + 0·(1-p2) · · · ·= 3 +3p + 3p2 + 3p3 + · · ·
3 3·(0.9)3·(0.9)·(0.9)= 3 + 3·(0.9) + 3·(0.9)2 + · · .

اگر بازیگر اول همیشه خیانت کند:
Stage 1Stage 2Stage 3 Stage 4 · · ·
51·p + 0·(1-p)1·p2 + 0·(1-p2) · · · ·= 5 + 1p + 1p2 + 1p3 + · · ·
5 1·(0.9)1·(0.9)·(0.9)= 5 + 1·(0.9) + 1·(0.9)2 + · ·
= 5 + 0.9 + 0.81 + · · ··

اسلاید 18 :

تکرار نامحدود بازی زندانی
فرض کنید بازیگر دوم از Grimm Trigger استفاده کند. بهترین کار برای بازیگر اول چیست؟

اگر بازیگر اول همیشه همکاری کند:
Stage 1Stage 2Stage 3 Stage 4 · · ·
33·p + 0·(1-p)3·p2 + 0·(1-p2) · · · ·= 3 +3p + 3p2 + 3p3 + · · ·

اگر بازیگر اول همیشه خیانت کند:
Stage 1Stage 2Stage 3 Stage 4 · · ·
51·p + 0·(1-p)1·p2 + 0·(1-p2) · · · ·= 5 + 1p + 1p2 + 1p3 + · · ·

اسلاید 19 :

تکرار نامحدود بازی زندانی