Algorithmic game theory: Difference between revisions

Revision as of 22:29, 30 June 2019

Revision as of 07:27, 18 July 2019

Line 63:

===Inefficiency of equilibria===

The concepts of [[price of anarchy]] and [[price of stability]] were introduced to capture the loss in performance of a system due to the selfish behavior of its participants. The [[price of anarchy]] captures the worst case performance of the system at [[equilibrium]]{{dn|date=July 2019}} relative to the optimal performance possible.<ref>{{cite book | authors=[[Tim Roughgarden]] |title=Selfish routing and the price of anarchy |publisher=[[MIT Press]] |year=2005 |isbn=0-262-18243-2 }}</ref> The [[price of stability]], on the other hand, captures the relative performance of the best equilibrium of the system.<ref>*{{Cite journal|first1=Elliot|last1=Anshelevich|first2=Anirban|last2=Dasgupta|first3=Jon|last3=Kleinberg|first4=Éva|last4=Tardos|first5=Tom|last5=Wexler|first6=Tim|last6=Roughgarden|title=The Price of Stability for Network Design with Fair Cost Allocation|journal=SIAM J. Comput.|volume=38|issue=4|year=2008|pages=1602–1623|doi=10.1137/070680096}}.</ref> These concepts are counterparts to the notion of [[approximation ratio]] in algorithm design.

===Complexity of finding equilibria===