Content deleted Content added
IznoRepeat (talk | contribs) m replace soft-deprecated authors parameter, rm ref=harv as applic., gen fixes, misc cite cleaning |
Citation bot (talk | contribs) Add: s2cid, author pars. 1-1. Removed parameters. Some additions/deletions were actually parameter name changes. | You can use this bot yourself. Report bugs here. | Suggested by AManWithNoPlan | All pages linked from cached copy of User:AManWithNoPlan/sandbox4 | via #UCB_webform_linked |
||
Line 19:
| pages = 129–140
| title = Proceedings of the 31st ACM Symposium on Theory of Computing (STOC '99)
| year = 1999| isbn = 978-1581130676 | s2cid = 8316937 }}</ref> drew the attention of the Theoretical Computer Science community to designing algorithms for selfish (strategic) users. As they claim in the abstract:
{{Quote|We consider algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. As such participants, termed agents, are capable of manipulating the algorithm, the algorithm designer should ensure in advance that the agents’ interests are best served by behaving correctly.
Line 39:
{{main|Price of Anarchy}}
The other two papers cited in the 2012 Gödel Prize for fundamental contributions to Algorithmic Game Theory introduced and developed the concept of "Price of Anarchy".
In their 1999 paper "Worst-case Equilibria",<ref name = "kp">{{Cite journal|title=Worst-case Equilibria|
(The term "Price of Anarchy" only appeared a couple of years later.<ref>{{citation
| last = Papadimitriou | first = Christos | author-link = Christos Papadimitriou
Line 46:
| pages = 749–753
| title = Proceedings of the 33rd ACM Symposium on Theory of Computing (STOC '01)
| year = 2001| isbn = 978-1581133493 | citeseerx = 10.1.1.70.8836 | s2cid = 207594967 }}</ref>)
===The Internet as a catalyst===
Line 62:
===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 relative to the optimal performance possible.<ref>{{cite book |author1=[[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|s2cid=2839399}}</ref> These concepts are counterparts to the notion of [[approximation ratio]] in algorithm design.
===Complexity of finding equilibria===
The existence of an equilibrium in a game is typically established using non-constructive [[fixed point theorem]]s. There are no efficient algorithms known for computing [[Nash equilibrium|Nash equilibria]]. The problem is complete for the [[complexity class]] [[PPAD]] even in 2-player games.<ref name="chen2005">*{{Cite conference|first1=Xi|last1=Chen|first2=Xiaotie|last2=Deng|title=Settling the complexity of two-player Nash equilibrium|conference=Proc. 47th Symp. Foundations of Computer Science|year=2006|pages=261–271|doi=10.1109/FOCS.2006.69|id={{ECCC|2005|05|140}}}}.</ref> In contrast, [[correlated equilibrium|correlated equilibria]] can be computed efficiently using linear programming,<ref>{{cite journal |
=== [[Computational social choice]]===
| |||