Algorithmic game theory: Difference between revisions

Revision as of 09:18, 14 May 2024

Revision as of 01:09, 15 May 2024

Line 12:

===Nisan-Ronen: a new framework for studying algorithms===

In 1999, the seminal paper of [[Noam Nisan]] and [[Amir Ronen]] <ref name="nr">{{citation

| last1 = Nisan | first1 = Noam | author1-link = Noam Nisan

| last2 = Ronen | first2 = Amir | author2-link = Amir Ronen

Line 21:

| year = 1999| isbn = 978-1581130676 | s2cid = 8316937 | doi-access = free}}</ref> drew the attention of the Theoretical Computer Science community to designing algorithms for selfish (strategic) users. As they claim in the abstract:

{{QuoteBlockquote|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.

Following notions from the field of mechanism design, we suggest a framework for studying such algorithms. In this model the algorithmic solution is adorned with payments to the participants and is termed a mechanism. The payments should be carefully chosen as to motivate all participants to act as the algorithm designer wishes. We apply the standard tools of mechanism design to algorithmic problems and in particular to the shortest path problem.}}