بخشی از پاورپوینت
اسلاید 1 :
هزینه ی بی نظمی
اسلاید 2 :
مثال پیگو
مثال: یک واحد ترافیک می خواهد از s به t برود.
سوال: کاربران (خودخواه) شبکه چگونه عمل خواهند کرد؟
فرض کنید همه به دنبال کمترین هزینه ی ممکن هستند.
c(x)=x
c(x)=1
هزینه وابسته به ازدحام است.
ازدحام تاثیری روی هزینه ندارد.
اسلاید 3 :
ادامه ی مثال
ادعا: تمام ترافیک از لینک بالایی استفاده خواهد کرد.
دلیل:
Є > 0 ترافیک قسمت پایین به قسمت بالا حسادت خواهد کرد.
اما اگر e=0 باشد در حالت تعادل هستیم.
لذا تمام ترافیک با یک واحد هزینه ی مواجه خواهد شد.
c(x)=x
c(x)=1
Flow = 1-Є
Flow = Є
این ترافیک حسود است!
اسلاید 4 :
آیا می توانیم بهتر عمل کنیم؟
فرض کنید که ترافیک را به طور مساوی بین دو بخش تقسیم کنیم.
بهبود:
نصف ترافیک با هزینه ی یک مواجه می شوند. (مثل قبل)
نصف ترافیک با هزینه ½ مواجه می شوند. (بهبود)
c(x)=x
c(x)=1
Flow = ½
Flow = ½
اسلاید 5 :
پارادوکس برائس
شبکه ی اصلی شبکه ی تغییر یافته
Cost = 1.5
Now what?
اسلاید 6 :
پارادوکس برائس
شبکه ی تغییر یافته شبکه ی اصلی
Cost = 1.5
Cost = 2
اسلاید 7 :
پارادوکس برائس
شبکه ی تغییر یافته شبکه ی اصلی
تمام ترافیک با هزینه بزرگتری روبرو می شوند.
Cost = 1.5
Cost = 2
اسلاید 8 :
High-Level Overview
انگیزه: حالت تعادل در یک شبکه ی غیر تعاملی معمولا کارآمد نیست.
مثالها: شبکه پیگو و برائس
بهینه کردن توابع هدف (مینیمم کردن هزینه یا کوتاهترین مسیر) کارآمد نیست.
هزینه ی بی نظمی: میزان ناکارآمدی نسبت به یک تابع هدف را به صورت عددی بیان می کند.
هدف ما: چه موقع هزینه ی بی نظمی کم خواهد بود؟
یعنی رقبا با هم تعامل خوبی دارند.
یا سود حاصل از کنترل مرکزی کم است.
اسلاید 9 :
بازیهای خودخواهانه ی شبکه
گراف جهتدار G = (V,E)
زوجهای مبدا و مقصد (s1,t1), …, (sk,tk)
Ri میزان ترافیکی که از si به ti می رود.
هر یال مثل e یک تابع هزینه ce(•) دارد.
فرض می کنیم که هزینه پیوسته و غیرنزولی است.
مثال: (r,k=1)
c(x)=x
c(x)=1
c(x)=x
c(x)=1
c(x)=x
c(x)=1
c(x)=0
اسلاید 10 :
خروجیها= جریانهای شبکه
خروجیهای محتمل بازی خودخواهانه ی شبکه
fP میزان ترافیکی است که مسیر p بین si-ti را انتخاب می کند.
outcomes of game flow vectors f
بردار جریان: غیر منفی است و fP (یعنی تاثیر جریان f روی تمام مسیرهایی که انتخاب کرده است) با نرخ ri برابر است.
حالت تعادل این بازی چیست؟
اسلاید 11 :
جریانهای نش
تعریف: یک جریان در تعادل نش به سر می برد اگر هیچ جریانی نتواند به مسیری با هزینه ی کمتر سوییچ کند. یعنی تمام جریانها از مسیرهای با کمترین هزینه عبور کنند.
مثالها:
اسلاید 12 :
تابع هدف مورد نظر ما
تعریف هزینه ی اجتماعی: مجموع هزینه ای که از ترافیک جریان f ناشی می شود. با C(f) نشان داده می شود.
تعریف رسمی: اگر cP(f) با مجموع هزینه ی یالهای مسیر p ناشی از جریان f برابر باشد، داریم:
C(f) = P fP • cP(f)
مثال:
Cost = ½•½ +½•1 = ¾
اسلاید 13 :
هزینه ی بی نظمی
تعریف:
هزینه ی بی نظمی یک بازی
خروجی بازی در حالت خودخواهانه
خروجی بهینه ی بازی
مثال: در شبکه ی پیگو POA = 4/3
Cost = 1
Cost = 3/4
اسلاید 14 :
هزینه ی بی نظمی
تعریف کلی: در اینجا S مجموعه ی راهبردهای بازی و E مجموعه ی تعادلهای نش بازی است. W نیز تابع بهره ی اجتماعی است.
اگر به جای بهره ی اجتماعی از هزینه ی اجتماعی استفاده کنیم:
اسلاید 15 :
مثال
بازی دو زندانی را در نظر بگیرید:
بهره ی بهترین حالت برابر 10 و بهره ی بدترین تعادل نش 2 است. البته این بازی فقط یک تعادل نش دارد. لذا:
POA=5
اسلاید 16 :
یک شبکه ی پیگوی غیر خطی
یک مثال بد: فرض کنید d خیلی بزرگ است.
هزینه تعادل برابر 1 است و حداقل هزینه تقریباً برابر 0 است.
اگر d به سمت بی نهایت برود هزینه ی بی نظمی نامحدود خواهد بود.
هدف: ضعیف ترین شرایط ممکن که تحت آن POA کوچک باشد.
اسلاید 17 :
توابع هزینه چندجمله ای
تعریف: تابع هزینه ی خطی به فرم ce(x)=aex+be است.
نظریه: برای هر شبکه با تابع هزینه ی خطی داریم:
≤ 4/3 ×
چندجمله ای محدود: (با ضرایب غیر منفی) می توانید 4/3 را با
Θ(d/log d) عوض کنید.
هزینه ی جریان نش
هزینه ی جریان بهینه
tight
example
اسلاید 18 :
طراحی شبکه ی خودخواهانه
برای: G = (V,E) که هزینه ی تمام e є E برابر ce است، k زوج (si,ti) داریم.
هر بازیگر می خواهد یک شبکه بسازد که در آن نودهایش به هم وصل باشند.
راهبرد بازیگر: انتخاب یک مسیر برای وصل کردن si به ti.
اسلاید 19 :
Shapley Cost Sharing
چگونه هزینه ی یک یال بین چند بازیگر تقسیم می شود؟
اشتراک عادلانه یک راه حل طبیعی است.
بازیگرهایی که از e استفاده می کنند هزینه ی آن را به طور مساوی پرداخت می کنند:
ci(P) = Σ ce/ke
هر بازیگر سعی می کند هزینه ی خود را حداقل کند.
e є P
اسلاید 20 :
هزینه ی پایداری
تعریف کلی: در اینجا S مجموعه ی راهبردهای بازی و E مجموعه ی تعادلهای نش بازی است. W نیز تابع بهره ی اجتماعی است.
اگر به جای بهره ی اجتماعی از هزینه ی اجتماعی استفاده کنیم:
