The price of anarchy for polynomial social cost

Martin Gairing, Thomas Luecking, Marios Mavronicolas and Burkhard Monien
Theoretical Computer Science
Volume 369, Issues 1-3 , 15 December 2006, Pages 116-135
http://dx.doi.org/10.1016/j.tcs.2006.07.055

MFCS2004の論文．ゲーム理論関係．

Koutsoupias & Papadimitriou (STACS1999) 以来，いわゆる「price of anarchy」の研究は盛んで，これもその1つ．
論文中の表が先行研究とのモデルの違いを表わしていて，大きな違いはlatency functionが(任意次元の)多項式になっていることである．
その場合のprice of anarchyを調べている．