Algorithmic game theory: Difference between revisions

Revision as of 07:27, 18 July 2019

Revision as of 12:28, 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===

Line 87:

* [[Multi-agent systems]]

And the area counts with diverse practical applications:<ref>{{cite book | authors=[[Tim Roughgarden]] |title=Twenty lectures on algorithmic game theory |publisher=[[Cambridge University Press]] |year=2016 |isbn=9781316624791}}</ref><ref>{{Citecite web | url=http://www.sigecom.org/ec19/callforpapers.html |title = EC'19 &#124;&#124; 20th ACM Conference on Economics and Computation}}</ref>

* [[Sponsored search auction]]s

Line 104:

* International Symposium on Algorithmic Game Theory (SAGT) <ref name="SAGT"> [http://corelab.ntua.gr/sagt2019/ SAGT 2019]</ref>

Algorithmic Game Theory papers also often appear in general [[Theoretical Computer Science]] conferences such as [[Symposium on Theory of Computing|STOC]]<ref>[http://acm-stoc.org/stoc2019/call-for-papers.html STOC 2019 call for papers]</ref> and [[Symposium on Foundations of Computer Science|FOCS]],<ref>[http://focs2019.cs.jhu.edu/cfp/ FOCS 2019 call for papers]</ref>, or [[Artificial Intelligence]] conferences such as [[Association for the Advancement of Artificial Intelligence # Conferences and publications|AAAI]]<ref> [https://aaai.org/Conferences/AAAI-19/wp-content/uploads/2018/11/AAAI-19_Accepted_Papers.pdf AAAI 2019 accepted papers]</ref> and [[International Joint Conference on Artificial Intelligence|IJCAI]].<ref> [https://www.ijcai19.org/accepted-papers.html IJCAI 2019 accepted papers]</ref>.

== Journals and newsletters ==

* [[Association for Computing Machinery|ACM]] Transactions on Economics and Computation (TEAC) <ref name="TEAC"> [https://teac.acm.org/ TEAC]</ref>

* SIGEcom Exchanges <ref> [http://www.sigecom.org/exchanges/ SIGEcom Exchanges]</ref>

Algorithmic Game Theory papers are often also published in Game Theory journals such as [[Games and Economic Behavior| GEB]],<ref>

{{citation

| last1 = Chawla | first1 = Shuchi

Line 123:

| author4-link = Tim Roughgarden

| doi = 10.1016/j.geb.2015.02.011

}}</ref>, Economics journals such as [[Econometrica]], and Computer Science journals such as [[SIAM Journal on Computing|SICOMP]].<ref> [https://www-siam-org.stanford.idm.oclc.org/Publications/Journals/SIAM-Journal-on-Computing-SICOMP SICOMP]</ref>.

==See also==