Payamvdn/NorthPersian_fa_wiki huggingface dataset:
برای بیان بهینگی پارتو به روشی دیگر می توان به بازی شکار گوزن اشاره کرد. فرض کنید دو بازیکن داریم که هرکدام از عمل دیگری بی خبر هستند. هرکدام می توانند یا به شکار گوزن بروند یا به شکار خرگوش و اگر به شکار گوزن بروند در صورتی سود می کنند که هردو با هم به شکار بروند و اگر به شکار خرگوش بروند کمتر سود می کنند چون ارزش یک خرگوش کمتر از ارزش یک گوزن است. فرم استراتژیک بازی در زیر نشان داده شده. همان طور که در جدول مشخص شده، این بازی تنها یک تعادل بهینهٔ پارتو دارد و آن هم وقتی است که هردو بازیکن به شکار گوزن بروند. یک تعادل بهینهٔ پارتو، یک بهینهٔ اجتماعی را توصیف می کند که در آن هیچ بازیکنی نمی تواند سود خود را بدون کمتر کردن سود حداقل یک بازیکن دیگر، بیشتر کند. بهینهٔ پارتو مستقیماً یک مفهوم راه حل نیست اما یک صفت بسیار مهم برای تشخیص راه حل هایی که بازیکنان باید بازی کنند یا در طول زمان یاد بگیرند است. استنتاج معکوس. در برخی بازی ها چندین تعادل نش داریم که برخی از آن ها اصلاً واقع گرایانه نیستند. در بازی های پویا تعادل های نش غیر واقع گرایانه را با روش استنتاج معکوس می توان حذف کرد. استنتاج معکوس بر اساس این تف
کر است که تمام اعمال آیندهٔ بازیکنان عاقلانه خواهد بود. در نتیجه این روش استنتاج تهدیدهای غیر واقع گرایانه را از بازی می کند چرا که این نوع تهدیدها از دید یک بازیکن عاقل اعمال نمی شوند. استنتاج معکوس یکی از روش های محاسبهٔ تعادل نش زیربازی کامل در بازی های ترتیبی است. برای مثال یک بازی پویا فرض کنید که در آن، یک تازه وارد به صنعت فیلم می خواهد از طریق فیلم سازی کسب درآمد کند. یک شرکت دیگر هم وجود دارد که روی صنعت فیلم سازی به صورت انحصاری تسلط داشته و در صورتی که به شرکت تازه وارد اجازهٔ عرضه بدهد از سودش کم می شود. اول از همه شرکت تازه وارد می تواند تصمیم بگیرد که به صنعت وارد شود یا نشود. اگر وارد نشود سود اش صفر و سود شرکت دیگر همانی خواهد بود که از اول بود و صنعت در انحصار او باقی می ماند. اگر شرکت تازه وارد به صنعت وارد شود شرکت دوم دو کار می تواند بکند: یا با پایین آوردن قیمت های خود به مقابله پرداخته، سود خود را کم کرده و در عوض شرکت تازه وارد را از دور خارج کند؛ یا این که با شرکت تازه وارد مقابله نکند، کمی سود خود را کم کند، و هردو به کسب درآمد بپردازند (باز هم از سود انحصار کمتر است). در صورتی که شرک
ت تازه وارد به صنعت وارد شود، بهترین پاسخ شرکت دیگر این است که مقابله نکند. اگر شرکت تازه وارد بداند شرکت دیگر مقابله نمی کند هم بهترین پاسخش این است که به صنعت وارد شود؛ لذا حالتی که شرکت تازه وارد به صنعت وارد شده و شرکت دیگر مقابله نکند یک تعادل نش است. در مقابل اگر شرکت تازه وارد بداند که شرکت دیگر قرار است مقابله کند، بهترین پاسخ آن ها این است که به صنعت وارد نشوند و ضرر نکنند. اما اگر شرکت تازه وارد به صنعت وارد نشود، مهم نیست شرکت دیگر مقابله کند یا نکند و اگر وارد نشود اصلاً هیچوقت قیمت های خود را پایین نمی آورد و از طرفی برایش بهترین پاسخ هم هست. پس استراتژی پروفایلی که شرکت تازه وارد وارد صنعت نشود و شرکت دیگر مقابله کند هم یک تعادل نش است. زمانی که به گرهٔ انتخاب مقابله کردن یا نکردن می رسیم، غیر عقلانی است که مقابله کنیم و در نتیجه حالتی که شرکت دوم مقابله کند غیر عقلانی بوده و از تعادل ها می تواند حذف شود.
نظریهٔ مزایده یک شاخه از اقتصاد کاربردی است که به نحوه عملکرد افراد در بازار مزایده و بررسی ویژگی های بازار مزایده می پردازد. تا کنون طرح ها و مجموعه قوانین بسیاری مانند بهره وری از یک طرح مزایده داده شده، استراتژی های قیمت گذاری مطلوب، بهینه و تعادل استراتژی های (راهبردهای) مناقصه و مقایسه درآمد، توسط نظریه پردازان برای مزایده و موضوعات متداول این موضوع مورد بررسی قرار گرفته اند. سالیان سال تصویری که از مزایده در ذهن مردم وجود داشت، همان تصویری بود که در تلویزیون و سینما وجود داشت. از نظر آن ها مزایده ها چیزی شبیه حراجی هایی برای فروش تابلوهای پیکاسو و ون گوگ بود که در آن یک نفر در یک سالن شلوغ مزایده را مدیریت می کند و مردم قیمت ها را فریاد می زنند. در سال های اخیر این رویه تغییر کرده است. هم اکنون بسیاری از مردم در مزایده های اینترنتی برای خرید یا فروش محصولات شرکت می کنند. حتی آن هایی که از امکانات مزایده اینترنتی که شرکت هایی مانند eBay ارائه می دهند استفاده نمی کنند احتمالاً در جریان مزایده هایی که دولت ها برای واگذاری برخی از امتیازها برگزار می کنند، هستند. نظریه مزایده به عنوان یک ابزار برای اطلاع رسا
نی و طراحی مزایده های واقعی در جهان نیز استفاده می شود که مهم ترین آن ها خصوصی سازی شرکت های بخش دولتی یا فروش مجوز برای استفاده از طیف الکترومغناطیسی است. ایده کلی. مزایده ها معاملاتی هستند که با توجه به پیشنهادهای شرکت کنندگان، با یک مجموعه خاص از قوانین و جزئیات تخصیص منابع مشخص می شوند. مزایده ها به عنوان یک بازی با اطلاعات ناقص طبقه بندی می شوند، زیرا در اکثر اوقات یک فرد اطلاعات مربوط به معاملهٔ فرد دیگر را ندارد. (به عنوان مثال شرکت کنندگان معمولاً از ارزش گذاری خود از محصول را می دانند و این برای باقی شرکت کنندگان و فروشنده ها مجهول است) مزایده ها انواع مختلفی دارند، ولی ویژگی خاص همه آن ها این است که همگانی هستند و می توانند برای خرید یا فروش هر موردی استفاده شوند. در بسیاری از انواع آن نتیجهٔ مزایده به هویت شرکت کنندگان بستگی ندارد. (شرکت کنندگان می توانند مجهول باشند) در بیشتر مزایده ها شرکت کنندگان میزان پولی را که مایلند پرداخت کنند را پیشنهاد می دهند. در مزایده های استاندارد، برندهٔ مزایده فردی است که بیشترین پیشنهاد را داده است ولی در مزایده های غیر استاندارد این اتفاق نمی افتد. (مثال: قرعه کشی
ها) انواع مزایده. دسته بندی های بسیار زیادی برای مزایده ها وجود دارد. به عنوان مثال مزایده می تواند یک بعدی یا چندبعدی باشد، می تواند یک طرفه یا دو طرفه باشد، پیشنهادها می توانند open-cry یا مهر و موم شده باشند، می تواند یک واحد یا چند واحد باشد و…. به طور کلی چهار نوع مزایده وجود دارد که برای تخصیص یک محصول واحد، مورد استفاده قرار می گیرد: مزایده اولین قیمت با پیشنهاد مهر و موم شده. در این نوع مزایده شرکت کنندگان پیشنهاد خود را در یک بسته مهر و موم شده قرار داده و به طور همزمان پیشنهاد همه به مزایده گذاشته می شود. پاکت ها باز می شوند و فرد با بالاترین پیشنهاد، برنده می شود و باید مبلغ پیشنهادی اش را پرداخت کند. در این نوع مزایده هیچ کس قادر به دیدن پیشنهاد رقیبش قبل از اعلام پیشنهاد خودش نیست. به عنوان مثال این نوع مزایده برای فروش حق استفاده از معادن موجود در زمین های متعلق به دولت آمریکا استفاده می شود. همچنین گاهی برای فروش محصولات هنری یا خانه ها استفاده می شود. مزایده دومین قیمت با پیشنهاد مهروموم شده (مزایده ویکری Vickrey). در این نوع مزایده شرکت کنندگان پیشنهاد خود را در یک بسته مهر و موم شده قرار دا
ده و به طور همزمان پیشنهاد همه به مزایده گذاشته می شود. پاکت ها باز می شوند و فردی با بالاترین پیشنهاد، برنده می شود و باید مبلغ دومین پیشنهاد بالاتر را پرداخت کند. هرچند که این نوع مزایده از لحاظ نظری ویژگی های مفیدی دارد، در عمل به ندرت از آن استفاده می شود. مزایده های پیشنهاد صعودی (مزایده های انگلیسی). در این نوع مزایده شرکت کنندگان پیشنهاد خود را بالاتر از پیشنهاد نفر قبلی اعلام می کنند. در صورتی که حاضر به پرداخت نرخی بالاتر از نرخ فعلی نباشند دیگر قیمتی را پیشنهاد نمی دهند. این روند ادامه پیدا می کند تا هیچ مشارکت کننده ای آماده پذیرش نرخ بالاتری نسبت به قیمت فعلی نباشد. فردی که این بیشترین قیمت را پیشنهاد داده است مزایده را در همین قیمت نهایی به نفع خود می برد. گاهی اوقات این مقدار تنها در صورتی فروخته می شود که نرخ پیشنهادی بیشتر از قیمت های تعیین شده توسط فروشنده باشد. مزایده ممکن است یک متصدی داشته باشد که قیمت ها را اعلام کند یا شرکت کننده ها خود فریاد بزنند. همچنین ممکن است مزایده به صورت الکترونیکی برگزار شود و محصول به کسی برسد که بیشترین پیشنهاد را پست کند. محصولات هنری و عتیقه ها اغلب از این
طریق به فروش می رسند. مزایده های پیشنهاد نزولی (مزایده های هلندی). در این نوع مزایده قیمتی در سطح به اندازه کافی بالا (برای جلوگیری از پیشنهاد چند شرکت کننده) توسط حراج کننده تعیین می شود. سپس به طور تدریجی قیمت را کاهش می دهند تا زمانی که یک خریدار آماده خرید در قیمت فعلی باشد، در این صورت این خریدار با پرداخت قیمت فعلی، برنده این حراج می شود. به طور مثال برای فروش گل در هلند یا فروش ماهی در اسرائیل یا تنباکو در کانادا از این نوع مزایده استفاده می کنند. اکثر نظریه حراج پیرامون این چهار نوع «اساسی» انواع حراج است ولی گاهی این چهار نوع در ترکیب با یکدیگر استفاده می شوند؛ مثلاً زمانی که قیمت های پیشنهادی بسیار پایین باشد، فروشنده خود قیمت بالاتری را پیشنهاد می کند که یا سطح قیمت ها را بالا ببرد یا مزایده را لغو کند. گاهی هم در مزایده ها فروشنده از شرکت کننده ها مبلغی را برای ورود به مزایده دریافت می کند. مدل معیار. مدل معیار برای مزایده ها توسط McAfee و McMillan در سال ۱۹۸۷ مطرح شده اند. بر اساس چهار فرضیه زیر تعمیمی از انواع مزایده را ارائه می دهند: مدل معیار اکثر اوقات همراه با «اصل آشکارسازی» استفاده می شوند
؛ که بیانگر این است که هر مزایده دارای ساختاری است که در آن هر یک از شرکت کنندگان انگیزه دارد که ارزیابی خود را صادقانه بیان کند. این دو اصل توسط فروشندگان استفاده می شود که حداکثر قیمت مورد انتظار را تعیین می کند. این ساختار مزایده به این صورت تعریف شده است که شرکت کنندگان بالاترین پیشنهاد بنا بر ارزش گذاری خود ارائه دهند ولی فروشنده در صورتی که تمام پیشنهادات از قیمت مورد نظرش کمتر باشند از فروش خودداری می کند. کاستن هر یک از ۴ فرضیه اصلی مدل معیار ویژگی های مشخصی به مزایده می دهد: خطر پذیری شرکت کنندگان که برای خطر کردن نوعی هزینه ای پرداخت می کنند، که بر ارزش گذاری آن ها بر محصول تأثیر می گذارد. در مزایده های مهر و موم شده با قیمت اولیه داوطلبان برای بیشتر کردن احتمال برنده شدن خود تمایل دارند پیشنهاد بالاتری بدهند، بنابراین در این نوع مزایده ها قیمت نهایی از مزایده های مهر و موم شده با قیمت ثانویه و مزایده های پیشنهاد صعودی (مزایده های انگلیسی)، قیمت نهایی بالاتری دارند. در نوع هایی که ارزش گذاری ها مرتبطند و ارزش گذاری شرکت کنندگان مستقل از هم نیست اگر یکی از شرکت کنندگان ارزش بالایی به محصول بدهد باعث
می شود باقی شرکت کنندگان نیز مقدار بالاتری نسبت به ارزش گذاری خود پیشنهاد دهند. مثال قابل توجه این قضیه نفرین برنده است. هنگامی که برنده مشخص می شود و همهٔ شرکت کنندگان مقداری که پیشنهاد داده اند بیشتر از ارزش کالا برای آن ها باشد. در مدل نا متقارن شرکت کنندگان به دو گروه با توزیع های مختلف ارزش گذاری افراز می شوند. (به طور مثال دلالان و خریداران) مدل های نظریه بازی ها. در مدل نظریه بازی ها برای مزایده یک بازی ریاضی داریم که با تعدادی شرکت کننده، مجموعه استراتژی ها برای هر شرکت کننده و بردار سود به ازای هر ترکیبی از استراتژی نشان داده می شود. به طور کلی شرکت کنندگان به دو دستهٔ خریداران و فروشندگان تقسیم می شوند. مجموعه حرکات هر شرکت کننده یک تابع پیشنهاد یا رزرو قیمت است. هر تابع پیشنهاد تابعی از ارزش یا هزینه هر بازیکن را به یک قیمت پیشنهادی است. مدل های نظریه بازی برای مزایده ها معمولاً به دو دسته تقسیم می شوند. مدل ارزش خصوصی. در این مدل، هر شرکت کننده (پیشنهاد دهنده) فرض می کند که هر یک از رقیب های شرکت کننده یک مقدار خصوصی تصادفی از توزیع احتمالی به دست می آورد. هر کسی که در این مزایده شرکت می کند از ار
زش واقعی آن محصول برای خود آگاه است؛ بنابراین قیمت پیشنهادی او هرگز از ارزش واقعی آن بیشتر نخواهد بود و برخلاف مزایده های عمومی قیمت پیشنهادی او تحت تأثیر دیگر پیشنهادها قرار نمی گیرد بنابراین شرکت کننده ها کمتر ضرر می کنند. یکی دیگر از مزایای این نوع مزایده این است که از آن جا که هر کس با توجه به ارزش آن محصول برای خود پیشنهادش را ارائه می دهد، در نهایت محصول به کسی می رسد که برایش بیشترین ارزش را دارد. البته از آن جا که شرکت کننده ها اغلب قیمتی کمتر از ارزش واقعی محصول برای خود را پیشنهاد می کنند، این مزایده ها کمتر از مزایده پیشنهاد نزولی و مزایده های قیمت گذاری شده با قیمت اول برای فروشنده درآمد دارد. مدل مقدار متداول. در این مدل، محصول ارزش یکسانی برای شرکت کنندگان دارد اما شرکت کنندگان ارزیابی یکسانی از ارزش محصول ندارند. به جای دانستن ارزیابی دقیق، هر شرکت کننده می تواند فرض کند که هر شرکت کننده دیگری یک سیگنال تصادفی به دست می دهد که می تواند برای ارزیابی واقعی از توزیع احتمالی مشترک برای همه داوطلبان استفاده شود. در مدل مقدار متداول فرض می شود ارزش گذاری ها توزیع احتمال مشترک دارند. هنگامی که لازم اس
ت فرض دقیقی از توزیع ارزش گذاری افراد داشته باشیم، در اکثر تحقیقات شرکت کنندگان متقارن را در نظر می گیرند، بدین معنا که توزیع احتمال ارزش گذاری ها برای همهٔ شرکت کنندگان به طور مستقل و یکسان توزیع شده باشد. مثلاً در مورد فروش یک زمین نفت خیز، ارزش واقعی زمین برای همهٔ شرکت کننده ها یکسان است اما اطلاعات شرکت کننده ها از ارزش واقعی زمین متفاوت است؛ بنابراین یک شرکت کننده ممکن است در صورت آگاهی از اطلاعات یا قیمت پیشنهادی رقیب، قیمت پیشنهادی خود را تغییر دهد. معمولاً، اما نه همیشه، یک مدل ارزش خصوصی فرض می کند که ارزش ها در میان شرکت کننده ها مستقل هستند، در حالی که یک مدل ارزش مشترک معمولاً فرض می کند که مقادیر مستقل از پارامترهای مشترک توزیع احتمالی هستند. affiliated values model. یک رده کلی تر برای پیشنهاد استراتژیک، مدل ارزش وابسته است که در آن کل سودمندی شرکت کننده بستگی به هر دو سیگنال شخصی فرد و مقداری از ارزش ناشناخته مشترک دارد. هر دو مدل ارزش شخصی و ارزش مشترک می توانند به عنوان پسوند مدل های وابسته به ارزش کلی دیده شوند. مثلاً در مورد فروش یک اثر هنری، قیمت پیشنهادی یک شرکت کننده هم از ارزش محصول برا
ی او (میزان علاقهٔ شخصی او به محصول) و هم از ارزش محصول برای دیگران تأثیر می پذیرد؛ زیرا هر چقدر این محصول برای دیگران ارزش بیشتری داشته باشد، در درآمد ناشی از فروش یا به نمایش گذاشتن اثر هنری تأثیر خواهد گذاشت. هنگامی که لازم است پیش فرض های صریح دربارهٔ توزیع ارزش های شرکت کنندگان بپردازیم، اکثر تحقیقات منتشر شده، پیشنهاد دهندگان متقارن را می پذیرند. این بدان معنی است که توزیع احتمالی که هر شرکت کنندگان ارزش های (یا سیگنال های) خود را به دست می آورد، در میان شرکت کنندگان یکسان است. در یک مدل ارزش های خصوصی که استقلال را فرض می کند، تقارن نشان می دهد که ارزش های شرکت کنندگان به طور مستقل است و یکسان توزیع شده است. آنالیز رسمی مزایده. اولین آنالیز رسمی مزایده توسط ویلیام ویکری(۱۹۶۱) صورت گرفته است. ویکری دو شرکت کننده را برای یک جنس در نظر می گیرد. ارزش هر شرکت کننده(v) از توزیع یکنواخت به دست می آید. ویکری نشان داده است که در مزایده های مهر و موم شده با قیمت اولیه استراتژی تعادل برای هر دو نفر این است که نصف ارزش خود را پیشنهاد دهند. همچنین برای n شرکت کننده با ارزش های مشابه ثابت می شود استراتژی تعادل برای
هر نفر پیشنهاد formula_1 است. برای اینکه ثابت کنیم این استراتژی تعادل است نشان می دهیم اگر برای formula_2 نفر استراتژی درست باشد برای نفر اول نیز استراتژی درست است. می دانیم نفر اول با پیشنهاد formula_3 به احتمال ۱ حتماً مزایده را برنده می شود. پس تنها بازهٔ formula_4 بررسی می کنیم. فرض کنید نفر اول ارزش formula_5 و پیشنهاد formula_6 را دارد و نفر دوم ارزش formula_7 و پیشنهاد formula_8 را دارد. در این صورت نفر اول نفر دوم را می برد اگر formula_9 برقرار بوده است. از آنجایی که formula_7 توزیع یکنواخت دارد پیشنهاد نفر اول با احتمال formula_11 از پیشنهاد نفر دوم بیشتر است. برای اینکه نفر اول برندهٔ مزایده شود باید پیشنهادش از بقیهٔ شرکت کنندگان بیشتر باشد که این به احتمال زیر رخ می دهد: &lt;math&gt; w(b)=Pr
اشتباه تایپی، خطای تایپی یا تایپو ، به اشتباهی گفته می شود که در تایپ صورت صحیح نوشتار چاپی یا آنلاین رخ می دهد. در گذشته، این عبارت به اشتباهات رخ داده در هنگام حروف چینی (تایپوگرافی) گفته می شد. این اصطلاح شامل خطاهای ناشی از نقص سخت افزاری یا لغزش و خطای دست یا انگشت می شود اما غلط هایی مانند غلط های املایی یا به کارگیری اشتباه کلماتی مانند «فراق» و «فراغ» که به دلیل بی اطلاعی رخ می دهند را شامل نمی شود. اکثر اشتباهات تایپی ساده بوده و به صورت تکرار، جا انداختن، جابجایی یا جایگزینی تعداد کمی کاراکتر اتفاق می افتند. انگشت چاق یا "سندرم انگشت چاق" اصطلاحی عامیانه است که اشاره به عمل ثانویهٔ ناخواسته ای دارد که در هنگام تایپ رخ می دهد. هنگامی که انگشت فردی بزرگ تر از محدودهٔ لمس باشد، ممکن است اعمال حرکتی با بدون دقت انجام شده و اشتباهاتی رخ دهد. این اتفاق در صفحات لمسی شایع است. ممکن است افراد با گذاشتن انگشت بر روی یک از کلیدهای صفحه کلید، دو کلید مجاور را فشار دهند. به عنوان مثال تایپ کلمهٔ "سمند" به جای "سند" که به دلیل کنار هم بودن دو کلید"م" و "ن" است. اشتباهی تایپی ریز. گونهٔ دیگری از اشتباه تایپی به ا
شتباه تایپی ریز معروف است و بر حسب اتفاق منجر به تایپ کلمه ای می شود که صورت املایی صحیحی دارد اما کلمهٔ مورد نظر تایپیست نیست و به دلیل این که املا صحیحی دارد، غلط یاب قادر به تشخیص این اشتباه نیست. از نمونه های آن می توان به تایپ «برگ» به جای «بزرگ» و «فریب» به جای «قریب» اشاره کرد.
مفهوم هزینهٔ هرج ومرج (Price of Anarchy یا PoA)، از مباحث اقتصاد و نظریهٔ بازی است که در آن، میزان کاهش بازدهی سیستم به دلیل خودخواهی بازیکنان بررسی می شود. این مفهوم در سیستم های گوناگون با تعریف های متفاوتی از بازدهی کاربرد دارد. به عنوان مثال سیستم حمل ونقل شهری را، که بازدهی می تواند رسیدن در زمان کمتر تعریف شود، بررسی کنیم. در این سیستم، یک سری بازیکن می خواهند از یک مبدأ به یک مقصد بروند. دو حالت وجود دارد؛ حالت اول اینکه مدیریت مرکزی وجود داشته باشد و بازیکنان با توجه به فرمان مدیریت مرکزی جهت های حرکت خود را انتخاب کنند (فرض می شود بازیکن ها کاملاً به فرمان ها گوش می دهند) و حالت دوم اینکه مدیریت مرکزی وجود نداشته باشد و بازیکنان به صورت خودخواهانه تصمیم های خود را بگیرند، یعنی هر بازیکن تنها بازدهی خود را در نظر بگیرد. هزینهٔ هرج ومرج نمایشی برای اندازه گیری کاهش بازدهی سیستم در حالت دوم نسبت به حالت اول است. سیستم هایی که در آن ها به بررسی هزینهٔ هرج ومرج پرداخته می شود معمولاً به صورت یک بازی مدل می شوند. در یک بازی، با توجه به اینکه هر بازیکن چه استراتژی ای را انتخاب می کند، هر بازیکن میزانی سود (
یا ضرر) می کند. بازدهی در این مدل، تابعی از سود (یا ضرر) بازیکنان با توجه به استراتژی های انتخاب شده است. یعنی کارایی آن به صورت تابعی از نتیجهٔ برهم کنش رفتار عامل های مختلف آن مدل می شود. مثلاً تعریف کارایی در سیستم حمل ونقل برابر معکوس ازدحام، در شبکه برابر بیشترین تأخیر (Maximum Delay) و در بازارهای حراجی (Auction) برابر سود اجتماعی تعریف می شود. برای مدل کردن رفتار خودخواهانهٔ بازیکنان، می توان از مفاهیم تعادل در بازی ها استفاده کرد که یکی از پرکاربردترین تعادل ها، تعادل نش است. حال با توجه به اینکه از کدام نوع تعادل نش استفاده شود، نوع های مختلف هزینهٔ هرج ومرج بدست می آید؛ مثلاً اگر از تعادل نش خالص استفاده شود، هزینهٔ هرج ومرج خالص بدست می آید یا اگر از تعادل نش ترکیبی استفاده شود، هزینهٔ هرج ومرج ترکیبی بدست می آید و یا برای بازی های با اطلاعات ناقص، هزینهٔ هرج ومرج بیز-نش بدست می آید. تعریف قیمت هرج ومرج ابتدا توسط کوتسوپیاس (Koutsoupias) و پاپادیمیتریو (Papadimitriou) بیان شد، در حالی که اندازه گیری ناکارامدی تعادل نش از دیدگاه سود اجتماعی، ایده ای قدیمی تر است. مفهوم قیمت هرج ومرج به شکل امروزی خو
د، به گونهٔ معادل با ضریب تقریب (Approx-ratio) در بحث الگوریتم های تقریبی، یا به تعبیر دیگر به صورت معادل با نسبت رقابت (Competitive-ratio) در الگوریتم های آنلاین تعریف شده است. تعریف ریاضی. هزینهٔ هرج ومرج را می خواهیم در بازی formula_1 بررسی کنیم که formula_2 مجموعهٔ بازیکنان است، formula_3، در واقع formula_4 مجموعهٔ استراتژی پروفایل ها است (formula_5، مجموعهٔ استراتژی های بازیکن formula_6ام است) و formula_7 مجموعهٔ formula_8ها است که هر formula_8 یک تابع است که formula_10 . در واقع formula_8 تابعی است که سود نفر formula_6ام را در هر استراتژی پروفایل بدست می آورد. تابع بازدهی را نیز، به صورت formula_13 تعریف می کنیم، که برای هر استراتژی پروفایل، یک عدد به نشان میزان بازدهی ارائه می دهد. حال برای formula_14، می توان تابع های بهینهٔ اجتماعی در بازی ها را در نظر گرفت، به عنوان مثال می توان formula_15 (مجموع سود تمام بازیکنان در یک استراتژی پروفایل)، یا تابع formula_16 (کمترین مقدار سود بازیکنان در یک استراتژی پروفایل) و یا هر تابعی که مقدار مطلوبی را حداکثر می کند را در نظر گرفت. اگر در این مدل بازی، عددها به
جای سود بازیکنان، هزینهٔ بازیکنان تعریف شده باشند، در این صورت به جای تابع formula_14، تابع formula_18 را تعریف می کنیم که هرچه مقدار کمتری داشته باشد، نشاندهندهٔ بازده بیشتری است. اگر مجموعهٔ formula_19 را مجموعه ای از استراتژی پروفایل هایی بگیریم که در آن ها تعادل داریم (در واقع formula_20)، در این صورت هزینهٔ هرج ومرج (formula_21) نسبت بازده در بهترین حالت از میان استراتژی پروفایل ها، به بدترین بازده در میان استراتژی های تعادل (یا همان بازده بدترین تعادل) است: formula_22 در صورتی که به جای تابع formula_14، تابع formula_24 داشته باشیم، در این صورت formula_21 به صورت زیر تعریف می شود: formula_26 یکی دیگر از مفاهیم مرتبط با هزینهٔ هرج ومرج، هزینهٔ پایداری (Price of Stability یا formula_27) است که تعریف آن نسبت بازده در بهترین حالت از میان استراتژی پروفایل ها، به بهترین بازده در میان استراتژی های تعادل (یا همان بازده بهترین تعادل) است: formula_28 مفهوم formula_27 به این دلیل مهم است که بهترین تعادل نش به طور طبیعی مفهوم پایداری را در خود دارد و زمانی که بازی در بهترین تعادل نش از لحاظ بازده باشد، احتمال اینکه
بازیکنی استراتژی خود را تغییر دهد کم است. اگر به جای formula_14، تابع formula_24 تعریف شده باشد، formula_27 به شکل زیر تعریف می شود: formula_33 با توجه به این تعریف ها، بدیهی است که formula_34 و تخمین زده می شود که از دست دادن بازده به دلیل محدودیت های نظریهٔ بازی، مقداری میان formula_27 و formula_21 است. در زیر به بررسی formula_21 و formula_27 دریک مثال می پردازیم. معمای زندانی. مثلاً بازی ای را در نظر بگیرید که جدول هزینه های آن به شکل زیر باشد: در این بازی، دو متهم همکار در یک جرم، زندانی شده اند و آن ها را به طور هم زمان و جدا از هم بازجویی می کنند. اگر هردو سکوت کنند و اعتراف نکنند، هر یک ۱ سال حبس می گیرند. اگر هر دو اعتراف کنند، هر یک ۵ سال حبس می گیرند و اگر یکی اعتراف کند و دیگری سکوت کند، متهمی که سکوت کرده ۱۰ سال حبس می گیرد و متهم دیگر آزاد می شود. این بازی به معمای زندانی معروف است. در این مثال تابع Cost را به شکل formula_39 تعریف می کنیم. حال تنها تعادل نش در این بازی، زمانی است که هر دو بازیکن، اعتراف کنند (زیرا اگر هر بازیکن استراتژی خود را عوض کند، سودی کمتر از حالت کنونی اش می گیرد). این درح
الی است که formula_24 زمانی که هر دو بازیکن همکاری کنند کمترین حالت است. پس: اگر هردو بازیکن سکوت کنند: formula_41 اگر هردو بازیکن اعتراف کنند: formula_42 پس با توجه به این مقادیر، formula_43 است و چون این بازی تنها یک تعادل نش دارد، پس formula_27 نیز مقدارش برابر formula_21 می شود. شبکه های ترافیک خودخواهانه. شکلی از مفهوم هزینهٔ هرج ومرج در شبکه های ترافیک تعریف می شود که در تحلیل های شبکه ها از جمله شبکهٔ ترافیک حمل ونقل کاربرد زیادی دارد. مدل کردن این شبکه ها عموماً به شکل شبکه های چند جریانه (Multicommodity network) صورت می گیرد. یک شبکهٔ چند جریانه با یک ۳ تای formula_46معرفی می شود. formula_47 از گردایه ای از سفرها (Commodity) تشکیل شده است. هر سفر یک دوتایی formula_48از رأس های گراف است، که formula_49مبدا و formula_50مقصد آن است. به ازای سفر formula_6ام، formula_52مجموعهٔ تمامی مسیرها در formula_47است که با formula_49شروع و با formula_50بایان می یابند، و formula_56. یک جریان (Flow) در شبکه، تشکیل شده از یک بردار formula_57 با بعد formula_58، به گونه ای که برای هر سفر مانند formula_48و به ازای هر مسیر
متناظر با این سفر مانند formula_60, formula_61درایه ای از formula_57را که متناظر با میزان جریان در مسیر formula_63است نشان می دهد. از طرفی هر جریان formula_57، میزانی از جریان را روی یال دلخواه formula_65از formula_47القا می کند که آن را با formula_67نشان می دهیم. در این چارچوب، خواهیم داشت: formula_68. شبکه خودخواهانه. یک شبکهٔ خودخواهانه، یک ۳تایی formula_69تلقی می شود که formula_47، گراف در تناظر با شبکهٔ چند جریانهٔ formula_2 است. اگر تعداد سفرهای متناظر با formula_2 را formula_73 بگیریم، آنگاه formula_74 یک بردار با بعد formula_73 است که درایهٔ formula_76ام آن میزان ترافیک مورد نیاز برای سفر از راس formula_49 به راس formula_50 در شبکه است. بنابراین جریان formula_57 را برای این شبکه مجاز گوییم، اگر به ازای تمام مسیرهای بین formula_49 تا formula_50، جمع جریانشان برابر با میزان مورد نیاز formula_82 شود، یعنی: formula_83 . از طرفی، هر یال از formula_47 دارای میزانی سربار است. مثلاً سربار می تواند میزان تأخیر عبور یک بستهٔ ترافیکی یا یک وسیلهٔ نقلیه از یال مورد نظر باشد. سربار یال formula_65 را با formula_86
نشان می دهیم که در تناظر با بردار formula_87 است. برای این که قدرت مدل کردن ازدحام در شبکه را داشته باشیم، formula_86 عموماً به صورت تابعی غیرنزولی از میزان جریان عبوری از یال مورد نظر تعریف می شود. برای مسیری از گراف که متناظر با یکی از سفرها باشد، یعنی برای formula_89، و نیز برای جریان formula_57،formula_91 برابر میزان سربار در طول این مسیر، یعنی برابر formula_92 تعریف می شود. تعادل واردراپ. شکل معادلی از تعادل نش در مدل کردن شبکه های ترافیکی به صورت بازی، توسط "جان گلن واردراپ (John Glen Wardrop)" تعریف شده است، که به تعادل واردراپ (به انگلیسی: Wardrop Equilibrium) شهرت یافته است. مشابه با مفهوم کلیدی در تعریف تعادل نش، موسوم به اینکه بازیکنی انگیزه تخطی نداشته باشد، جریانی در شبکهٔ خودخواهانهٔ formula_69 تعادل واردراپ است، اگر به ازای هر formula_94، و به ازای هر دو مسیر formula_95، به گونه ای که formula_96، داشته باشیم formula_97. بنابراین، تمامی مسیرهایی از formula_49 به formula_50 که جریان مثبت دارند، همگی الزاماً هزینه (سربار) یکسان دارند. همان گونه که بیان شد، تعادل واردراپ، صورت بندی دیگری از مفهوم ت
عادل نش است، به همین دلیل به آن اصطلاح جریان نش (Nash flows) نیز اختصاص داده شده است. "هری (Haurie)" "و مارکوت (Marcotte)" صورت بندی دقیقی از تناظر دو مفهوم تعادل واردراپ و تعادل نش برای بازی های متناهی و فرم نرمال ارائه کردند. شاید بتوان گفت پایه ای ترین قضیه در این باب، قضیه وجود تعادل واردراپ در شبکهٔ خودخواهانه دلخواه است. بکمن، مک گور و وینستن صورت بندی مناسبی از این قضیه ارائه کردند، به این صورت که اولاً به ازای هر شبکه خودخواهانهٔ دلخواه formula_100، حداقل یک تعادل واردراپ داریم، ثانیاً اگر formula_101 دو تعادل واردراپ باشند، آنگاه به ازای هر یال دلخواه formula_65خواهیم داشت: .formula_103 بازی های پتانسیلی. راه حل اثبات این حقیقت از ایده ای بسیار کلیدی در حل مسایل جستجو در ریاضیات استفاده می کند، که به ایدهٔ وریشنال (Variational) معروف است، به این صورت عمل می کند که برای بررسی وجود و یافتن جواب ایده آل یک مساله در فضای جستجو، تابعی به اعضای آن فضا نسبت می دهد، به گونه ای که جواب ایده آل میزان تابع را کمینه (یا بیشنیه) کند. به این ترتیب، تحلیل جواب ایده آل به یک مسالهٔ بهینه سازی تقلیل پیدا می کند. استف