177:
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.
225:). An equilibrium is generally defined as a state in which no player has an incentive to change their strategy. Equilibria are found in several fields related to the Internet, for instance financial interactions and communication load-balancing. Game theory provides tools to analyze equilibria, and a common approach is then to ‘find the game’—that is, to formalize specific Internet interactions as a game, and to derive the associated equilibria.
36:
217:
The
Internet created a new economy—both as a foundation for exchange and commerce, and in its own right. The computational nature of the Internet allowed for the use of computational tools in this new emerging economy. On the other hand, the Internet itself is the outcome of actions of many. This was
228:
Rephrasing problems in terms of games allows the analysis of
Internet-based interactions and the construction of mechanisms to meet specified demands. If equilibria can be shown to exist, a further question must be answered: can an equilibrium be found, and in reasonable time? This leads to the
176:
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
208:
proposed a new measure of the degradation of system efficiency due to the selfish behavior of its agents: the ratio of between system efficiency at an optimal configuration, and its efficiency at the worst Nash equilibrium. (The term "Price of
Anarchy" only appeared a couple of years later.)
203:
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", Koutsoupias and
218:
new to the classic, ‘top-down’ approach to computation that held till then. Thus, game theory is a natural way to view the
Internet and interactions within it, both human and mechanical.
110:
Typically, in
Algorithmic Game Theory problems, the input to a given algorithm is distributed among many players who have a personal interest in the output. In those situations, the
263:
considers the optimization of economic systems under computational efficiency requirements. Typical objectives studied include revenue maximization and social welfare maximization.
708:
Anshelevich, Elliot; Dasgupta, Anirban; Kleinberg, Jon; Tardos, Éva; Wexler, Tom; Roughgarden, Tim (2008). "The Price of
Stability for Network Design with Fair Cost Allocation".
757:
336:, the aggregation of individual agents' preferences. Examples include algorithms and computational complexity of voting rules and coalition formation.
172:
drew the attention of the
Theoretical Computer Science community to designing algorithms for selfish (strategic) users. As they claim in the abstract:
555:
287:, on the other hand, captures the relative performance of the best equilibrium of the system. These concepts are counterparts to the notion of
1024:
989:
980:
46:
57:
114:
might not report the input truthfully because of their own personal interests. We can see
Algorithmic Game Theory from two perspectives:
425:
652:
532:
961:
875:
691:
75:
121:: given the currently implemented algorithms, analyze them using Game Theory tools (e.g., calculate and prove properties on their
822:
1067:
581:
1043:- a library of game theory software and tools for the construction and analysis of finite extensive and strategic games.
260:
251:
182:
136:
936:
461:
436:
327:
279:
were introduced to capture the loss in performance of a system due to the selfish behavior of its participants. The
867:
471:
283:
captures the worst-case performance of the system at equilibrium relative to the optimal performance possible. The
444:
364:
776:
Papadimitriou, Christos H.; Roughgarden, Tim (2008). "Computing correlated equilibria in multi-player games".
1011:
413:
785:
630:
622:
315:
230:
205:
104:
50:
that states a
Knowledge (XXG) editor's personal feelings or presents an original argument about a topic.
394:
1062:
559:
790:
135:: design games that have both good game-theoretical and algorithmic properties. This area is called
1072:
635:
354:
318:
can be computed efficiently using linear programming, as well as learned via no-regret strategies.
300:
288:
803:
725:
658:
538:
481:
384:
379:
344:
284:
276:
556:"ACM SIGACT Presents Gödel Prize for Research that Illuminated Effects of Selfish Internet Use"
1020:
985:
975:
871:
687:
648:
528:
234:
111:
934:(2015), "Introduction to the Special Issue – Algorithmic Game Theory – STOC/FOCS/SODA 2011",
971:
945:
840:
Felix Brandt; Vincent Conitzer; Ulle Endriss; Jérôme Lang; Ariel D. Procaccia, eds. (2016),
795:
749:
717:
640:
593:
518:
476:
369:
308:
304:
280:
272:
256:
222:
198:
126:
100:
189:
committee as one of "three papers laying foundation of growth in Algorithmic Game Theory".
1003:
931:
859:
675:
558:(Press release). New York. Association for Computing Machinery. 2012-05-16. Archived from
398:
389:
299:
The existence of an equilibrium in a game is typically established using non-constructive
122:
435:
Algorithmic Game Theory papers are often also published in Game Theory journals such as
995:
456:
374:
186:
17:
259:
is the subarea of economics that deals with optimization under incentive constraints.
1056:
1007:
927:
662:
486:
407:
402:
349:
807:
729:
542:
466:
440:
891:
597:
96:
761:
601:
1049:- a suite of game generators designated for testing game-theoretic algorithms.
999:
949:
510:
506:
169:
165:
799:
683:
841:
644:
523:
753:
627:
Proceedings of the 33rd ACM Symposium on Theory of Computing (STOC '01)
515:
Proceedings of the 31st ACM Symposium on Theory of Computing (STOC '99)
748:. Proc. 47th Symp. Foundations of Computer Science. pp. 261–271.
721:
233:
for finding equilibria. Of special importance is the complexity class
143:
On top of the usual requirements in classical algorithm design (e.g.,
892:"EC'19 || 20th ACM Conference on Economics and Computation"
915:
103:, with the objective of understanding and design of algorithms in
1040:
311:
29:
1046:
332:
Computational social choice studies computational aspects of
237:, which includes many problems in algorithmic game theory.
47:
personal reflection, personal essay, or argumentative essay
360:
And the area counts with diverse practical applications:
151:
the designer must also care about incentive constraints.
904:
580:
Koutsoupias, Elias; Papadimitriou, Christos (May 2009).
303:. There are no efficient algorithms known for computing
53:
746:
Settling the complexity of two-player Nash equilibrium
160:
Nisan-Ronen: a new framework for studying algorithms
428:Transactions on Economics and Computation (TEAC)
823:"Calibrated Learning and Correlated Equilibrium"
625:(2001), "Algorithms, games, and the Internet",
174:
1019:, Cambridge, UK: Cambridge University Press,
27:Study of algorithms in strategic environments
8:
221:Game theory studies equilibria (such as the
864:Twenty lectures on algorithmic game theory
821:Foster, Dean P.; Vohra, Rakesh V. (1996).
789:
634:
522:
76:Learn how and when to remove this message
680:Selfish routing and the price of anarchy
513:(1999), "Algorithmic mechanism design",
443:, and Computer Science journals such as
984:. Princeton Univ. Press. 2007 edition:
843:Handbook of Computational Social Choice
498:
981:Theory of Games and Economic Behavior
314:even in 2-player games. In contrast,
7:
930:; Fleischer, Lisa; Hartline, Jason;
95:) is an area in the intersection of
307:. The problem is complete for the
25:
744:Chen, Xi; Deng, Xiaotie (2006).
295:Complexity of finding equilibria
34:
185:and was recognized by the 2012
164:In 1999, the seminal paper of
129:, and best-response dynamics).
1:
439:, Economics journals such as
598:10.1016/j.cosrev.2009.04.003
261:Algorithmic mechanism design
252:Algorithmic mechanism design
246:Algorithmic mechanism design
183:algorithmic mechanism design
145:polynomial-time running time
137:algorithmic mechanism design
937:Games and Economic Behavior
827:Games and Economic Behavior
462:Computational social choice
328:Computational social choice
322:Computational social choice
181:This paper coined the term
1089:
868:Cambridge University Press
472:Load balancing (computing)
325:
267:Inefficiency of equilibria
249:
213:The Internet as a catalyst
196:
149:good approximation ratio),
950:10.1016/j.geb.2015.02.011
365:Sponsored search auctions
343:Algorithms for computing
420:Journals and newsletters
1013:Algorithmic Game Theory
800:10.1145/1379759.1379762
623:Papadimitriou, Christos
586:Computer Science Review
582:"Worst-case Equilibria"
89:Algorithmic game theory
18:Algorithmic Game Theory
1041:gambit.sourceforge.net
414:Economics of the cloud
339:Other topics include:
231:analysis of algorithms
179:
56:by rewriting it in an
1068:Theory of computation
645:10.1145/380752.380883
524:10.1145/301250.301287
487:Voting in game theory
316:correlated equilibria
291:in algorithm design.
754:10.1109/FOCS.2006.69
629:, pp. 749–753,
517:, pp. 129–140,
301:fixed point theorems
355:Multi-agent systems
289:approximation ratio
1047:gamut.stanford.edu
996:Vazirani, Vijay V.
482:Multi-agent system
431:SIGEcom Exchanges
385:Reputation systems
380:Prediction markets
285:price of stability
277:price of stability
58:encyclopedic style
45:is written like a
1026:978-0-521-87282-9
990:978-0-691-13061-3
976:Oskar Morgenstern
916:SIGEcom Exchanges
784:(3): 14:1–14:29.
722:10.1137/070680096
370:Spectrum auctions
345:Market equilibria
241:Areas of research
86:
85:
78:
16:(Redirected from
1080:
1029:
1018:
1004:Roughgarden, Tim
972:John von Neumann
964:
959:
953:
952:
924:
918:
913:
907:
902:
896:
895:
888:
882:
881:
856:
850:
849:
848:
837:
831:
830:
818:
812:
811:
793:
773:
767:
765:
740:
734:
733:
716:(4): 1602–1623.
704:
698:
697:
672:
666:
665:
638:
619:
613:
612:
610:
609:
600:. Archived from
577:
571:
570:
568:
567:
552:
546:
545:
526:
503:
477:Mechanism design
410:and peer grading
395:Matching markets
375:Cryptocurrencies
309:complexity class
281:price of anarchy
273:price of anarchy
271:The concepts of
257:Mechanism design
223:Nash equilibrium
199:Price of Anarchy
193:Price of Anarchy
127:price of anarchy
101:computer science
81:
74:
70:
67:
61:
38:
37:
30:
21:
1088:
1087:
1083:
1082:
1081:
1079:
1078:
1077:
1053:
1052:
1037:
1027:
1016:
994:
968:
967:
960:
956:
932:Tim Roughgarden
926:
925:
921:
914:
910:
903:
899:
890:
889:
885:
878:
860:Tim Roughgarden
858:
857:
853:
846:
839:
838:
834:
820:
819:
815:
791:10.1.1.335.2634
775:
774:
770:
743:
741:
737:
707:
705:
701:
694:
676:Tim Roughgarden
674:
673:
669:
655:
621:
620:
616:
607:
605:
579:
578:
574:
565:
563:
554:
553:
549:
535:
505:
504:
500:
495:
453:
422:
399:kidney exchange
390:Sharing economy
330:
324:
305:Nash equilibria
297:
269:
254:
248:
243:
215:
201:
195:
162:
157:
123:Nash equilibria
82:
71:
65:
62:
54:help improve it
51:
39:
35:
28:
23:
22:
15:
12:
11:
5:
1086:
1084:
1076:
1075:
1070:
1065:
1055:
1054:
1051:
1050:
1044:
1036:
1035:External links
1033:
1032:
1031:
1025:
992:
966:
965:
954:
928:Chawla, Shuchi
919:
908:
897:
883:
876:
851:
832:
813:
768:
735:
710:SIAM J. Comput
699:
692:
667:
654:978-1581133493
653:
636:10.1.1.70.8836
614:
572:
547:
534:978-1581130676
533:
497:
496:
494:
491:
490:
489:
484:
479:
474:
469:
464:
459:
457:Auction Theory
452:
449:
433:
432:
429:
421:
418:
417:
416:
411:
405:
392:
387:
382:
377:
372:
367:
358:
357:
352:
347:
326:Main article:
323:
320:
296:
293:
268:
265:
250:Main article:
247:
244:
242:
239:
214:
211:
197:Main article:
194:
191:
161:
158:
156:
153:
141:
140:
130:
107:environments.
84:
83:
42:
40:
33:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1085:
1074:
1071:
1069:
1066:
1064:
1061:
1060:
1058:
1048:
1045:
1042:
1039:
1038:
1034:
1028:
1022:
1015:
1014:
1009:
1005:
1001:
997:
993:
991:
987:
983:
982:
977:
973:
970:
969:
963:
958:
955:
951:
947:
943:
939:
938:
933:
929:
923:
920:
917:
912:
909:
906:
901:
898:
893:
887:
884:
879:
877:9781316624791
873:
869:
865:
861:
855:
852:
845:
844:
836:
833:
828:
824:
817:
814:
809:
805:
801:
797:
792:
787:
783:
779:
772:
769:
763:
759:
755:
751:
747:
739:
736:
731:
727:
723:
719:
715:
711:
703:
700:
695:
693:0-262-18243-2
689:
685:
681:
677:
671:
668:
664:
660:
656:
650:
646:
642:
637:
632:
628:
624:
618:
615:
604:on 2016-03-13
603:
599:
595:
591:
587:
583:
576:
573:
562:on 2013-07-18
561:
557:
551:
548:
544:
540:
536:
530:
525:
520:
516:
512:
508:
502:
499:
492:
488:
485:
483:
480:
478:
475:
473:
470:
468:
465:
463:
460:
458:
455:
454:
450:
448:
446:
442:
438:
430:
427:
424:
423:
419:
415:
412:
409:
408:Crowdsourcing
406:
404:
403:school choice
400:
396:
393:
391:
388:
386:
383:
381:
378:
376:
373:
371:
368:
366:
363:
362:
361:
356:
353:
351:
350:Fair division
348:
346:
342:
341:
340:
337:
335:
334:social choice
329:
321:
319:
317:
313:
310:
306:
302:
294:
292:
290:
286:
282:
278:
274:
266:
264:
262:
258:
253:
245:
240:
238:
236:
232:
226:
224:
219:
212:
210:
207:
206:Papadimitriou
200:
192:
190:
188:
184:
178:
173:
171:
167:
159:
154:
152:
150:
146:
138:
134:
131:
128:
124:
120:
117:
116:
115:
113:
108:
106:
102:
98:
94:
90:
80:
77:
69:
59:
55:
49:
48:
43:This article
41:
32:
31:
19:
1012:
979:
957:
941:
935:
922:
911:
900:
886:
863:
854:
842:
835:
826:
816:
781:
777:
771:
745:
738:
713:
709:
702:
679:
670:
626:
617:
606:. Retrieved
602:the original
592:(2): 65–69.
589:
585:
575:
564:. Retrieved
560:the original
550:
514:
501:
467:Gamification
441:Econometrica
434:
359:
338:
333:
331:
298:
270:
255:
227:
220:
216:
202:
180:
175:
163:
148:
144:
142:
132:
118:
109:
92:
88:
87:
72:
63:
44:
1063:Game theory
1008:Tardos, Éva
1000:Nisan, Noam
944:: 228–231,
511:Ronen, Amir
507:Nisan, Noam
187:Gödel Prize
97:game theory
66:August 2013
1073:Algorithms
1057:Categories
608:2018-01-08
566:2018-01-08
493:References
170:Amir Ronen
166:Noam Nisan
786:CiteSeerX
684:MIT Press
663:207594967
631:CiteSeerX
105:strategic
1010:(2007),
862:(2016).
808:53224027
762:TR05-140
678:(2005).
451:See also
397:such as
119:Analysis
978:(1944)
730:2839399
543:8316937
155:History
52:Please
1023:
988:
962:SICOMP
874:
806:
788:
778:J. ACM
760:
728:
690:
661:
651:
633:
541:
531:
445:SICOMP
133:Design
112:agents
1017:(PDF)
847:(PDF)
804:S2CID
726:S2CID
659:S2CID
539:S2CID
1021:ISBN
986:ISBN
905:TEAC
872:ISBN
758:ECCC
688:ISBN
649:ISBN
529:ISBN
401:and
312:PPAD
275:and
235:PPAD
168:and
99:and
946:doi
796:doi
750:doi
718:doi
641:doi
594:doi
519:doi
437:GEB
426:ACM
93:AGT
1059::
1006:;
1002:;
998:;
974:,
942:92
940:,
870:.
866:.
825:.
802:.
794:.
782:55
780:.
756:.
724:.
714:38
712:.
686:.
682:.
657:,
647:,
639:,
588:.
584:.
537:,
527:,
509:;
447:.
147:,
125:,
1030:.
948::
894:.
880:.
829:.
810:.
798::
766:.
764:.
752::
742:*
732:.
720::
706:*
696:.
643::
611:.
596::
590:3
569:.
521::
139:.
91:(
79:)
73:(
68:)
64:(
60:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.