Minimum cost connection networks: Truth-telling and implementation

در مقاله حاضر در نظر داریم تخصیص هزینه ها در شبکه های ارتباطی. نمایندگان خواستار اتصال به شکل جفت مکان هایی هستند که می خواهند ارتباط برقرار کنند. ارتباطات بین مکان ها برای ساختن بسیار هزینه است. مشکل این است که تخصیص هزینه های شبکه های رضایت تمام درخواست های اتصال. ما از چند اصل برای مشخص کردن قوانین تخصیص استفاده می کنیم که به درستی هزینه های به حداقل رساندن شبکه ها را برآورده می کند که رضایت همه خواسته های اتصال در یک بازی را نشان می دهد: (1) یک برنامه ریز مرکزی، یک قانون تخصیص و یک قانون تخمین هزینه را اعلام می کند؛ (2) هر نماینده تقاضای اتصال خود و نیز هزینه های اتصال را گزارش می دهد؛ (3) برنامه ریزنده مرکزی هزینه های به حداقل رساندن شبکه را برآورده می کند که رضایت خواسته های اتصال گزارش شده را براساس هزینه های برآورد شده انتخاب می کند؛ و (4) برنامه ریز هزینه های واقعی شبکه انتخاب شده را اختصاص می دهد. معلوم می شود که یک قانون تخصیص به معیارهای حقیقی برسد اگر و فقط اگر هزینه نسبی هزینه ثابت باشد.