2869:
2275:. This would mean simply an action profile whose makespan is minimum. However, this will not be enough. There may be several such action profiles leading to a variety of different loads distributions (all having the same maximum load). Among these, we further restrict ourselves to one that has a minimum second-largest load. Again, this results in a set of possible load distributions, and we repeat until the
5160:
41:
to reach the destination. In the 'centralized' solution, a central authority can tell each agent which path to take in order to minimize the average travel time. In the 'decentralized' version, each agent chooses its own path. The Price of
Anarchy measures the ratio between average travel time in the two cases.
40:
behavior of its agents. It is a general notion that can be extended to diverse systems and notions of efficiency. For example, consider the system of transportation of a city and many agents trying to go from some initial location to a destination. Here, efficiency means the average time for an agent
2875:
Consider a road network as shown in the adjacent diagram on which 4000 drivers wish to travel from point Start to End. The travel time in minutes on the Start–A road is the number of travelers (T) divided by 100, and on Start–B is a constant 45 minutes (likewise with the roads across from them). If
3287:
minutes. Nobody has any incentive to travel A-End or Start-B because any driver trying them will take 85 minutes. Thus, the opening of the cross route triggers an irreversible change to it by everyone, costing everyone 80 minutes instead of the original 65. If every driver were to agree not to use
6748:
48:
and the efficiency is some function of the outcomes (e.g. maximum delay in a network, congestion in a transportation system, social welfare in an auction, etc.). Different concepts of equilibrium can be used to model the selfish behavior of the agents, among which the most common is the
7696:
8105:
Moreover, for these (finite) games it was proven that every equilibrium which achieves the PoA bound is fragile, in the sense that the agents demonstrate a state of indifference between their equilibrium action and the action they would pursue in a system-optimal outcome.
3145:
minutes, a saving of almost 25 minutes. Soon, more of the 4000 drivers are trying this new route. The time taken rises from 40.01 and keeps climbing. When the number of drivers trying the new route reaches 2500, with 1500 still in the Start–B–End route, their time will be
2781:
7812:
4916:
5381:
7298:
6923:
1015:
900:
775:
626:
8066:
4382:
3907:
3621:
7135:
1526:
machines to run the job. The Price of
Anarchy compares the situation where the selection of machines is guided/directed centrally to the situation where each player chooses the machine that will make its job run fastest.
6538:
6417:
2607:
6549:
5710:
3094:
Now suppose the dashed line A–B is a road with an extremely short travel time of approximately 0 minutes. Suppose that the road is opened and one driver tries Start–A–B–End. To his surprise he finds that his time is
4704:
1277:
7882:
7573:
1816:
468:
395:
3143:
662:
322:
3475:
6268:
3285:
3194:
4013:
2638:
7704:
5155:{\displaystyle \sum _{i=1}^{k}\sum _{p:s_{i}\rightarrow t_{i}}f_{p}^{*}\cdot \sum _{e\in p}l_{e}(f_{e})<\sum _{i=1}^{k}\sum _{p:s_{i}\rightarrow t_{i}}f_{p}\cdot \sum _{e\in p}l_{e}(f_{e})}
2203:
7389:
6992:
4167:
1972:
230:
4837:
288:
6015:
5245:
3235:
3089:
7143:
1632:
1580:
4908:
1692:
1469:
6756:
909:
794:
669:
520:
1907:
2984:
2929:
7565:
5600:
5555:
7937:
6074:
4462:
1061:
1338:
509:
7517:. Consider the example shown in the following figure, where we assume unit flow: the Nash-equilibrium flows have social welfare 1; however, the best welfare is achieved when
5430:
4424:
4108:
3683:
3657:
2129:
2057:
1389:
4257:
4196:
3790:
3782:
2813:
5237:
4069:
142:
7492:
6148:
3480:
3048:
3016:
2234:
4502:
3338:
2517:
80:, but the idea of measuring inefficiency of equilibrium is older. The concept in its current form was designed to be the analogue of the 'approximation ratio' in an
6295:
6117:
5841:
5814:
5787:
5740:
5510:
5483:
5211:
4757:
4573:
4250:
4223:
4043:
3760:
3733:
2273:
189:
2842:
5456:
2083:
2011:
7905:
7515:
7463:
7443:
7417:
6174:
5955:
5935:
5909:
5881:
5861:
5760:
5184:
4730:
4593:
4542:
4522:
4482:
3930:
3706:
3378:
3358:
2949:
2894:
2630:
2491:
2460:
2440:
2420:
2400:
2380:
2360:
2340:
2320:
2293:
1839:
1716:
1524:
1504:
162:
8098:, is precisely the Shapley value cost-sharing rule. (A symmetrical statement is similarly valid for utility-sharing games with convex utility functions.) In
1987:. It should be clear that mixed PoA ≥ pure PoA, because any pure Nash equilibrium is also a mixed Nash equilibrium (this inequality can be strict: e.g. when
3091:
minutes. If either route took less time, it would not be a Nash equilibrium: a rational driver would switch from the longer route to the shorter route.
7003:
6743:{\displaystyle w^{f}(f^{*})\leq \sum _{e\in E}\left(a_{e}\cdot \left((f_{e}^{*})^{2}+(f_{e})^{2}/4\right)\right)+\sum _{e\in E}f_{e}^{*}\cdot b_{e}}
6425:
6303:
2525:
2422:
must decrease as a result of the move and no other machine is affected, this means that the new configuration is guaranteed to have reduced the
5608:
2295:
th-largest (i.e., smallest) load, where there can only be one distribution of loads (unique up to permutation). This would also be called the
4601:
3296:
The routing problem introduced in the Braess's paradox can be generalized to many different flows traversing the same graph at the same time.
8488:
8237:
9550:
9387:
8120:
1146:
7691:{\displaystyle w=\left(1-{\frac {1}{\sqrt {d+1}}}\right)^{d}\cdot \left(1-{\frac {1}{\sqrt {d+1}}}\right)+1\cdot {\frac {1}{\sqrt {d+1}}}}
8461:
1063:
by the definition. It is expected that the loss in efficiency due to game-theoretical constraints is somewhere between 'PoS' and 'PoA'.
7820:
1724:
9204:
8739:
8537:
8135:
400:
327:
3098:
633:
293:
9023:
8842:
8444:
8417:
3383:
6179:
3240:
3149:
8644:
3938:
9113:
2876:
the dashed road does not exist (so the traffic network has 4 roads in total), the time needed to drive Start–A–End route with
2776:{\displaystyle w(a)\geq {\frac {\sum _{i}{w_{i}}}{\sum _{j}{s_{j}}}}\geq {\frac {\sum _{i}{w_{i}}}{M\cdot \max _{j}{s_{j}}}}.}
8654:
4387:
This definition is closely related to what we said about the support of mixed-strategy Nash equilibria in normal-form games.
8983:
9164:
8582:
8557:
8160:
7807:{\displaystyle =\left(\left(1-{\frac {1}{\sqrt {d+1}}}\right)^{\sqrt {d+1}}\right)^{\sqrt {d+1}}+{\frac {1}{\sqrt {d+1}}}}
515:). The Price of Anarchy is then defined as the ratio between the optimal 'centralized' solution and 'worst equilibrium':
9514:
8940:
8694:
8684:
8619:
8115:
2442:
th-largest (or higher ranked) load in the distribution. This, however, violates the assumed lexicographic minimality of
2134:
8734:
8714:
7306:
6931:
4117:
1912:
65:(for games with incomplete information). Solution concepts other than Nash equilibrium lead to variations such as the
9199:
664:
which we want to 'minimize' (e.g. delay in a network) we use (following the convention in approximation algorithms):
194:
4762:
9448:
9169:
8827:
8669:
8664:
8216:
Chung, Christine; Ligett, Katrina; Pruhs, Kirk; Roth, Aaron (2008), Monien, Burkhard; Schroeder, Ulf-Peter (eds.),
5376:{\displaystyle \sum _{p:s_{i}\rightarrow t_{i}}f_{p}=\sum _{p:s_{i}\rightarrow t_{i}}f_{p}^{*}=r_{i}\;\;\forall i.}
4524:. In what follows, we will drop the subscript to make the notation clearer. Assume to fix the latencies induced by
290:
also called set of outcomes). We can define a measure of efficiency of each outcome which we call welfare function
235:
7293:{\displaystyle =(1/4)\cdot \sum _{e\in E}(f_{e})^{2}+\underbrace {(1/4)\cdot \sum _{e\in E}f_{e}b_{e}} _{\geq 0}.}
5863:
from the higher-cost path to the lower-cost path. This situation is clearly incompatible with the assumption that
9484:
9407:
9143:
8699:
8624:
8481:
470:..., or any function that is meaningful for the particular game being analyzed and is desirable to be maximized.
6918:{\displaystyle =\left(\sum _{e\in E}a_{e}(f_{e}^{*})^{2}+f_{e}^{*}b_{e}\right)+\sum _{e\in E}a_{e}(f_{e})^{2}/4}
5960:
3288:
the A–B path, or if that route were closed, every driver would benefit by a 15-minute reduction in travel time.
3199:
3053:
1010:{\displaystyle PoS={\frac {\min _{s\in Equil}\operatorname {Cost} (s)}{\min _{s\in S}\operatorname {Cost} (s)}}}
895:{\displaystyle PoS={\frac {\max _{s\in S}\operatorname {Welf} (s)}{\max _{s\in Equil}\operatorname {Welf} (s)}}}
770:{\displaystyle PoA={\frac {\max _{s\in Equil}\operatorname {Cost} (s)}{\min _{s\in S}\operatorname {Cost} (s)}}}
621:{\displaystyle PoA={\frac {\max _{s\in S}\operatorname {Welf} (s)}{\min _{s\in Equil}\operatorname {Welf} (s)}}}
9499:
9232:
9118:
8915:
8709:
8527:
1585:
1533:
9302:
4848:
2302:
We claim that this is a pure-strategy Nash equilibrium. Reasoning by contradiction, suppose that some player
1637:
1394:
630:
If, instead of a 'welfare' which we want to 'maximize', the function measure efficiency is a 'cost function'
9504:
9103:
9073:
8729:
8517:
3196:
minutes, which is no improvement over the original route. Meanwhile, those 1500 drivers have been slowed to
1844:
89:
81:
9438:
9529:
9509:
9489:
9108:
9013:
8872:
8822:
8817:
8749:
8719:
8639:
8567:
8404:
8130:
8061:{\displaystyle \sum _{i=1}^{n}C_{i}\left(a_{i}^{*},a_{-i}\right)\leq \lambda C\left(a^{*}\right)+\mu C(a)}
2954:
2899:
77:
7520:
8547:
5560:
5515:
8988:
8973:
6026:
4429:
1077:
1022:
3237:
minutes, a 20-minute increase. They are obliged to switch to the new route via A too, so it now takes
1286:
476:
9322:
9307:
9194:
9189:
9093:
9078:
9043:
9008:
8607:
8552:
8474:
8090:
For cost-sharing games with concave cost functions, the optimal cost-sharing rule that optimizes the
4377:{\displaystyle f_{p}>0\Rightarrow \sum _{e\in p}{l_{e}(f_{e})}\leq \sum _{e\in q}{l_{e}(f_{e})}.}
3902:{\displaystyle \sum _{p:\,s_{i}\rightarrow t_{i}}{f_{p}}=r_{i}\;\;\forall (s_{i},t_{i})\in \Gamma .}
9479:
9098:
9048:
8885:
8812:
8792:
8649:
8532:
8306:
Phillips, Matthew; Marden, Jason R. (July 2018). "Design
Tradeoffs in Concave Cost-Sharing Games".
5389:
4396:
4080:
3662:
3629:
2863:
2088:
2016:
1343:
33:
789:) which measures the ratio between the optimal 'centralized' solution and the 'best equilibrium':
9458:
9317:
9148:
9128:
8978:
8857:
8762:
8689:
8634:
8331:
8125:
8095:
4172:
3764:
3616:{\displaystyle \Gamma =\{(s_{1},t_{1}),(s_{2},t_{2}),\dots ,(s_{k},t_{k})\}\subseteq (V\times V)}
781:
8386:
Tim
Roughgarden and Eva Tardos, "Introduction to the Inefficiency of Equilibria". Chapter 17 in
2789:
53:. Different flavors of Nash equilibrium lead to variations of the notion of Price of Anarchy as
5216:
4048:
103:
9443:
9412:
9367:
9262:
9133:
9088:
9063:
8993:
8867:
8797:
8787:
8679:
8629:
8577:
8440:
8413:
8370:
8323:
8288:
8233:
7468:
6122:
3021:
2989:
2868:
2208:
73:
4487:
3305:
2502:
9524:
9519:
9453:
9417:
9397:
9357:
9327:
9282:
9237:
9222:
9179:
9033:
8674:
8611:
8597:
8562:
8362:
8315:
8280:
8225:
8172:
8099:
1340:. However, the highest social welfare occurs when both cooperate, in which case the cost is
1280:
85:
50:
6273:
6090:
5819:
5792:
5765:
5718:
5488:
5461:
5189:
4735:
4551:
4228:
4201:
4021:
3738:
3711:
2251:
1474:
Since the game has a unique Nash equilibrium, the PoS is equal to the PoA and it is 5 too.
167:
88:. This is in the context of the current trend of analyzing games using algorithmic lenses (
9422:
9382:
9337:
9252:
9247:
8968:
8920:
8807:
8572:
8542:
8512:
8428:
8396:
7399:
Note that in the proof we have made extensive use of the assumption that the functions in
2818:
2242:. For each job scheduling game, there exists at least one pure-strategy Nash equilibrium.
1634:
A player picks a machine to run his or her job on. So, the strategies of each player are
512:
9287:
8217:
8102:, this means that the Shapley value solution concept is optimal for these sets of games.
5435:
2062:
1990:
2499:. It is easy to upper-bound the welfare obtained at any mixed-strategy Nash equilibrium
9362:
9352:
9342:
9277:
9267:
9257:
9242:
9038:
9018:
9003:
8998:
8958:
8925:
8910:
8905:
8895:
8704:
8388:
7890:
7500:
7448:
7428:
7402:
6159:
5940:
5920:
5894:
5866:
5846:
5745:
5169:
4715:
4578:
4527:
4507:
4467:
3915:
3691:
3363:
3343:
2934:
2879:
2615:
2476:
2445:
2425:
2405:
2385:
2365:
2345:
2325:
2305:
2278:
1984:
1824:
1701:
1509:
1489:
147:
6156:. Note that this theorem is equivalent to saying that for each Nash-equilibrium flow
9544:
9402:
9392:
9347:
9332:
9312:
9138:
9083:
9058:
8930:
8900:
8890:
8877:
8782:
8724:
8659:
8592:
8400:
8335:
8224:, vol. 4997, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 303–314,
1909:
i.e., the load of the machine they chose. We consider the egalitarian cost function
9377:
9372:
9227:
8802:
2205:
achieve an average makespan of 1.5, while any pure-strategy PoA in this setting is
324:. Natural candidates include the sum of players utilities (utilitarian objective)
8350:
8229:
8176:
9494:
9297:
9292:
9272:
9068:
9053:
8862:
8832:
8767:
8757:
8587:
8522:
8498:
7130:{\displaystyle (1/4)\cdot w(f)=(1/4)\cdot \sum _{e\in E}f_{e}(a_{e}f_{e}+b_{e})}
45:
37:
29:
8366:
8202:
8180:
9123:
8777:
8392:
8257:
P. Dubey. Inefficiency of Nash equilibria. Math. Operat. Res., 11(1):1–8, 1986
8374:
8327:
8319:
8292:
7915:
PoA upper bounds can be obtained if the game is shown to satisfy a so-called
6533:{\displaystyle =\sum _{e}(a_{e}f_{e}f_{e}^{*})+\sum _{e\in E}f_{e}^{*}b_{e}.}
9028:
8948:
8772:
8436:
6412:{\displaystyle w^{f}(f^{*})=\sum _{e\in E}f_{e}^{*}(a_{e}\cdot f_{e}+b_{e})}
2602:{\displaystyle w(\sigma )\leq {\frac {\sum _{i}{w_{i}}}{\max _{j}{s_{j}}}}.}
25:
2786:
Since the above holds for the social optimum as well, comparing the ratios
9463:
8963:
8268:
5705:{\displaystyle \sum _{e\in p}l_{e}(f_{e})<\sum _{e\in q}l_{e}(f_{e}).}
1976:
8466:
4699:{\displaystyle w^{f}(f^{*})=\sum _{e\in E}{f_{e}^{*}\cdot l_{e}(f_{e})}}
9184:
9174:
8852:
3380:
be as defined above, and suppose that we want to route the quantities
2612:
Consider, for clarity of exposition, any pure-strategy action profile
5891:
Note that Fact 1 does not assume any particular structure on the set
1272:{\displaystyle C(s_{1},s_{2})=u_{1}(s_{1},s_{2})+u_{2}(s_{1},s_{2}).}
8284:
511:
to be the set of strategies in equilibrium (for example, the set of
8953:
1506:
players and each of them has a job to run. They can choose one of
7877:{\displaystyle \leq e^{-{\sqrt {d+1}}}+{\frac {1}{\sqrt {d+1}}}.}
2236:). First we need to argue that there exist pure Nash equilibria.
1811:{\displaystyle L_{j}(a)={\frac {\sum _{i:a_{i}=j}w_{i}}{s_{j}}}.}
463:{\displaystyle \operatorname {Welf} (s)=\min _{i\in N}u_{i}(s),}
390:{\displaystyle \operatorname {Welf} (s)=\sum _{i\in N}u_{i}(s),}
8470:
3138:{\displaystyle {\tfrac {2000}{100}}+{\tfrac {2001}{100}}=40.01}
3050:
when the system is at equilibrium. Therefore, each route takes
657:{\displaystyle \operatorname {Cost} :S\rightarrow \mathbb {R} }
317:{\displaystyle \operatorname {Welf} :S\rightarrow \mathbb {R} }
3470:{\displaystyle R=\{r_{1},r_{2},\dots ,r_{k},\;|\;r_{i}>0\}}
6263:{\displaystyle w(f)\leq (4/3)\cdot \min _{f^{*}}\{w(f^{*})\}}
3280:{\displaystyle {\tfrac {4000}{100}}+{\tfrac {4000}{100}}=80}
3189:{\displaystyle {\tfrac {2500}{100}}+{\tfrac {4000}{100}}=65}
2867:
1283:
would be when both players defect and the resulting cost is
7919:
inequality. More precisely, a cost-minimimization game is
4008:{\displaystyle f_{e,\Gamma ,R}=\sum _{p:\,e\in p}{f_{p}}.}
2248:. We would like to take a socially optimal action profile
2473:. For each job scheduling game, the pure PoA is at most
2382:
after the move is still smaller than the load of machine
8159:
Koutsoupias, Elias; Papadimitriou, Christos (May 2009).
1983:
We consider two concepts of equilibrium: pure Nash and
6023:. This is another way to express the true inequality
3260:
3245:
3210:
3169:
3154:
3118:
3103:
3058:
2959:
2931:. The time needed to drive the Start–B–End route with
2904:
1917:
7940:
7893:
7823:
7707:
7576:
7523:
7503:
7471:
7451:
7431:
7405:
7309:
7146:
7006:
6934:
6759:
6552:
6428:
6306:
6276:
6182:
6162:
6125:
6093:
6029:
5963:
5943:
5923:
5897:
5869:
5849:
5822:
5795:
5768:
5748:
5721:
5611:
5563:
5518:
5491:
5464:
5438:
5392:
5248:
5219:
5192:
5172:
4919:
4851:
4765:
4738:
4718:
4604:
4581:
4554:
4530:
4510:
4490:
4470:
4432:
4399:
4260:
4231:
4204:
4175:
4120:
4083:
4051:
4024:
3941:
3918:
3793:
3767:
3741:
3714:
3694:
3665:
3632:
3483:
3386:
3366:
3346:
3308:
3243:
3202:
3152:
3101:
3056:
3024:
2992:
2957:
2937:
2902:
2882:
2821:
2792:
2641:
2618:
2528:
2505:
2479:
2448:
2428:
2408:
2388:
2368:
2348:
2328:
2308:
2281:
2254:
2211:
2137:
2091:
2065:
2019:
1993:
1915:
1847:
1827:
1727:
1704:
1640:
1588:
1536:
1512:
1492:
1397:
1346:
1289:
1149:
1025:
912:
797:
672:
636:
523:
479:
403:
330:
296:
238:
197:
170:
150:
106:
8351:"On the Intrinsic Fragility of the Price of Anarchy"
397:
minimum utility (fairness or egalitarian objective)
9472:
9431:
9213:
9157:
8939:
8841:
8748:
8606:
8505:
6087:. The pure PoA of any generalized routing problem
8060:
7899:
7876:
7806:
7690:
7559:
7509:
7486:
7457:
7437:
7425:. Given a generalized routing problem with graph
7411:
7383:
7292:
7129:
6986:
6917:
6742:
6532:
6411:
6289:
6262:
6168:
6142:
6111:
6068:
6009:
5949:
5929:
5903:
5875:
5855:
5835:
5808:
5781:
5754:
5734:
5704:
5594:
5549:
5504:
5477:
5450:
5424:
5375:
5231:
5205:
5178:
5154:
4902:
4831:
4751:
4724:
4698:
4587:
4567:
4536:
4516:
4496:
4476:
4456:
4418:
4376:
4244:
4217:
4190:
4161:
4102:
4063:
4037:
4007:
3924:
3901:
3776:
3754:
3727:
3700:
3677:
3651:
3615:
3469:
3372:
3352:
3332:
3279:
3229:
3188:
3137:
3083:
3042:
3010:
2978:
2943:
2923:
2888:
2836:
2807:
2775:
2624:
2601:
2511:
2485:
2454:
2434:
2414:
2394:
2374:
2354:
2334:
2314:
2287:
2267:
2228:
2197:
2123:
2077:
2051:
2005:
1966:
1901:
1833:
1810:
1710:
1686:
1626:
1574:
1518:
1498:
1463:
1383:
1332:
1271:
1055:
1009:
894:
769:
656:
620:
503:
462:
389:
316:
282:
224:
183:
156:
136:
7419:are linear. Actually, a more general fact holds.
2362:. This means that the increased load of machine
2198:{\displaystyle \sigma _{1}=\sigma _{2}=(1/2,1/2)}
7384:{\displaystyle w^{f}(f^{*})\leq w(f^{*})+w(f)/4}
6987:{\displaystyle \leq w(f^{*})+{\frac {w(f)}{4}},}
6219:
4162:{\displaystyle \forall (s_{i},t_{i})\in \Gamma }
2746:
2572:
1967:{\displaystyle {\mbox{MS}}(a)=\max _{j}L_{j}(a)}
1936:
974:
929:
847:
814:
734:
689:
573:
540:
423:
8154:
8152:
7465:with nonnegative coefficients, the pure PoA is
225:{\displaystyle u_{i}:S\rightarrow \mathbb {R} }
8269:"Intrinsic Robustness of the Price of Anarchy"
4832:{\displaystyle w(f)=w^{f}(f)\leq w^{f}(f^{*})}
2322:could strictly improve by moving from machine
8482:
8412:. Cambridge, UK: Cambridge University Press.
8079:*. In this case, the PoA is upper bounded by
283:{\displaystyle S=S_{1}\times ...\times S_{n}}
8:
8349:Seaton, Joshua H.; Brown, Philip N. (2023).
7931:(with λ ≥ 0 and μ < 1) if the inequality
6257:
6235:
3592:
3490:
3464:
3393:
1678:
1654:
72:The term Price of Anarchy was first used by
7445:and polynomial latency functions of degree
2986:. As there are 4000 drivers, the fact that
8489:
8475:
8467:
6010:{\displaystyle x\cdot y\leq x^{2}+y^{2}/4}
5363:
5362:
4391:Definition (Conditional welfare of a flow)
3857:
3856:
3447:
3441:
3230:{\displaystyle 45+{\tfrac {4000}{100}}=85}
3084:{\displaystyle {\tfrac {2000}{100}}+45=65}
8030:
7999:
7986:
7981:
7966:
7956:
7945:
7939:
7892:
7853:
7835:
7831:
7822:
7786:
7769:
7751:
7728:
7706:
7670:
7638:
7618:
7595:
7575:
7544:
7539:
7522:
7502:
7470:
7450:
7430:
7404:
7373:
7349:
7327:
7314:
7308:
7278:
7266:
7256:
7240:
7222:
7213:
7203:
7193:
7174:
7156:
7145:
7118:
7105:
7095:
7082:
7066:
7048:
7013:
7005:
6960:
6948:
6933:
6907:
6901:
6891:
6878:
6862:
6844:
6834:
6829:
6816:
6806:
6801:
6788:
6772:
6758:
6734:
6721:
6716:
6700:
6675:
6669:
6659:
6643:
6633:
6628:
6607:
6586:
6570:
6557:
6551:
6521:
6511:
6506:
6490:
6474:
6469:
6459:
6449:
6436:
6427:
6400:
6387:
6374:
6361:
6356:
6340:
6324:
6311:
6305:
6281:
6275:
6248:
6227:
6222:
6204:
6181:
6161:
6132:
6124:
6092:
6054:
6042:
6028:
5999:
5993:
5980:
5962:
5942:
5922:
5896:
5868:
5848:
5827:
5821:
5800:
5794:
5773:
5767:
5747:
5726:
5720:
5690:
5677:
5661:
5645:
5632:
5616:
5610:
5586:
5573:
5568:
5562:
5541:
5528:
5523:
5517:
5496:
5490:
5469:
5463:
5437:
5413:
5400:
5391:
5356:
5343:
5338:
5326:
5313:
5302:
5289:
5277:
5264:
5253:
5247:
5218:
5197:
5191:
5171:
5143:
5130:
5114:
5101:
5089:
5076:
5065:
5055:
5044:
5028:
5015:
4999:
4986:
4981:
4969:
4956:
4945:
4935:
4924:
4918:
4885:
4869:
4856:
4850:
4820:
4807:
4785:
4764:
4743:
4737:
4717:
4686:
4673:
4660:
4655:
4650:
4638:
4622:
4609:
4603:
4580:
4559:
4553:
4529:
4509:
4489:
4469:
4448:
4437:
4431:
4404:
4398:
4361:
4348:
4343:
4331:
4314:
4301:
4296:
4284:
4265:
4259:
4236:
4230:
4209:
4203:
4174:
4144:
4131:
4119:
4088:
4082:
4050:
4029:
4023:
3995:
3990:
3978:
3971:
3946:
3940:
3917:
3881:
3868:
3850:
3836:
3831:
3823:
3810:
3805:
3798:
3792:
3766:
3746:
3740:
3719:
3713:
3693:
3664:
3637:
3631:
3583:
3570:
3545:
3532:
3513:
3500:
3482:
3452:
3442:
3432:
3413:
3400:
3385:
3365:
3345:
3307:
3259:
3244:
3242:
3209:
3201:
3168:
3153:
3151:
3117:
3102:
3100:
3057:
3055:
3023:
2991:
2958:
2956:
2936:
2903:
2901:
2881:
2820:
2791:
2760:
2755:
2749:
2730:
2725:
2719:
2712:
2699:
2694:
2688:
2675:
2670:
2664:
2657:
2640:
2617:
2586:
2581:
2575:
2562:
2557:
2551:
2544:
2527:
2504:
2478:
2447:
2427:
2407:
2402:before the move. As the load of machine
2387:
2367:
2347:
2327:
2307:
2280:
2259:
2253:
2218:
2210:
2184:
2170:
2155:
2142:
2136:
2109:
2096:
2090:
2064:
2037:
2024:
2018:
1992:
1949:
1939:
1916:
1914:
1879:
1874:
1852:
1846:
1826:
1797:
1786:
1768:
1757:
1750:
1732:
1726:
1703:
1645:
1639:
1627:{\displaystyle w_{1},\ldots ,w_{N}>0.}
1612:
1593:
1587:
1575:{\displaystyle s_{1},\ldots ,s_{M}>0.}
1560:
1541:
1535:
1511:
1491:
1447:
1429:
1420:
1402:
1396:
1351:
1345:
1294:
1288:
1257:
1244:
1231:
1215:
1202:
1189:
1173:
1160:
1148:
1024:
977:
932:
925:
911:
850:
817:
810:
796:
737:
692:
685:
671:
650:
649:
635:
576:
543:
536:
522:
478:
442:
426:
402:
369:
353:
329:
310:
309:
295:
274:
249:
237:
218:
217:
202:
196:
175:
169:
149:
105:
8433:Selfish routing and the price of anarchy
4903:{\displaystyle w^{f}(f^{*})<w^{f}(f)}
1687:{\displaystyle A_{i}=\{1,2,\ldots ,M\}.}
1464:{\displaystyle C_{equil}/C_{min}=10/2=5}
1082:
8148:
8138:- a game with a small price-of-anarchy.
3912:The flow traversing a specific edge of
3477:through each distinct pair of nodes in
8308:IEEE Transactions on Automatic Control
3685:of a real, nonnegative number to each
1902:{\displaystyle c_{i}(a)=L_{a_{i}}(a),}
1080:, given by the following cost matrix:
7391:, and prove the thesis using Fact 1.
1482:A more natural example is the one of
7:
8121:Price of anarchy in congestion games
3018:can be used to derive the fact that
2979:{\displaystyle {\tfrac {b}{100}}+45}
2924:{\displaystyle {\tfrac {a}{100}}+45}
1391:. Thus the PoA of this game will be
8200:M. Goemans, V. Mirrokni, A. Vetta,
7560:{\displaystyle x=1-1/{\sqrt {d+1}}}
44:Usually the system is modeled as a
8538:First-player and second-player win
8136:Competitive facility location game
6297:is any other flow. By definition,
5595:{\displaystyle f_{q}^{*}<f_{q}}
5550:{\displaystyle f_{p}^{*}>f_{p}}
5364:
5220:
5213:are associated with the same sets
4491:
4438:
4405:
4176:
4156:
4121:
4089:
4075:Definition (Nash-equilibrium flow)
4052:
3953:
3893:
3858:
3771:
3672:
3638:
3484:
904:or in the case of cost functions:
14:
8218:"The Price of Stochastic Anarchy"
7887:This quantity tends to zero when
6069:{\displaystyle (x-y/2)^{2}\geq 0}
5762:only if there are two paths from
5742:can achieve a lower welfare than
4457:{\displaystyle f_{\Gamma ,R}^{*}}
1056:{\displaystyle 1\leq PoS\leq PoA}
84:or the 'competitive ratio' in an
61:(for randomized equilibria), and
8645:Coalition-proof Nash equilibrium
7497:Note that the PoA can grow with
5386:Therefore, there must be a pair
4712:. Given a Nash-equilibrium flow
1333:{\displaystyle C_{equil}=5+5=10}
779:A related notion is that of the
504:{\displaystyle Equil\subseteq S}
57:(for deterministic equilibria),
8267:Roughgarden, Tim (2015-11-02).
8203:Sink equilibria and convergence
5816:having different costs, and if
8655:Evolutionarily stable strategy
8055:
8049:
7370:
7364:
7355:
7342:
7333:
7320:
7230:
7216:
7200:
7186:
7164:
7150:
7124:
7088:
7056:
7042:
7036:
7030:
7021:
7007:
6972:
6966:
6954:
6941:
6898:
6884:
6813:
6794:
6666:
6652:
6640:
6621:
6576:
6563:
6543:By using Fact 2, we have that
6480:
6442:
6406:
6367:
6330:
6317:
6254:
6241:
6212:
6198:
6192:
6186:
6106:
6094:
6051:
6030:
5917:. Given any two real numbers
5696:
5683:
5651:
5638:
5419:
5393:
5319:
5270:
5149:
5136:
5082:
5034:
5021:
4962:
4897:
4891:
4875:
4862:
4826:
4813:
4797:
4791:
4775:
4769:
4692:
4679:
4628:
4615:
4484:associated with the same sets
4367:
4354:
4320:
4307:
4277:
4150:
4124:
3887:
3861:
3816:
3669:
3610:
3598:
3589:
3563:
3551:
3525:
3519:
3493:
3443:
3327:
3315:
2831:
2825:
2802:
2796:
2651:
2645:
2538:
2532:
2192:
2164:
1961:
1955:
1929:
1923:
1893:
1887:
1864:
1858:
1744:
1738:
1263:
1237:
1221:
1195:
1179:
1153:
1001:
995:
968:
962:
886:
880:
841:
835:
761:
755:
728:
722:
646:
612:
606:
567:
561:
454:
448:
416:
410:
381:
375:
343:
337:
306:
214:
191:for each player and utilities
144:, defined by a set of players
131:
113:
1:
8583:Simultaneous action selection
5425:{\displaystyle (s_{i},t_{i})}
4419:{\displaystyle f_{\Gamma ,R}}
4103:{\displaystyle f_{\Gamma ,R}}
3678:{\displaystyle p\mapsto \Re }
3652:{\displaystyle f_{\Gamma ,R}}
3300:Definition (Generalized flow)
2299:smallest sorted load vector.
2124:{\displaystyle s_{1}=s_{2}=1}
2052:{\displaystyle w_{1}=w_{2}=1}
1384:{\displaystyle C_{min}=1+1=2}
1143:and let the cost function be
1076:Consider the 2x2 game called
9515:List of games in game theory
8695:Quantal response equilibrium
8685:Perfect Bayesian equilibrium
8620:Bayes correlated equilibrium
8355:IEEE Control Systems Letters
8230:10.1007/978-3-540-79309-0_27
8177:10.1016/j.cosrev.2009.04.003
8116:Price of anarchy in auctions
3659:is defined as an assignment
36:of a system degrades due to
9551:Inefficiency in game theory
8984:Optional prisoner's dilemma
8715:Self-confirming equilibrium
5883:is a Nash-equilibrium flow.
4191:{\displaystyle \forall p,q}
4018:For succinctness, we write
3784:, with the constraint that
3777:{\displaystyle \in \Gamma }
3292:Generalized routing problem
63:Bayes–Nash Price of Anarchy
9567:
9449:Principal variation search
9165:Aumann's agreement theorem
8828:Strategy-stealing argument
8740:Trembling hand equilibrium
8670:Markov perfect equilibrium
8665:Mertens-stable equilibrium
8367:10.1109/LCSYS.2023.3335315
2861:
2808:{\displaystyle w(\sigma )}
1279:Now, the worst (and only)
9485:Combinatorial game theory
9144:Princess and monster game
8700:Quasi-perfect equilibrium
8625:Bayesian Nash equilibrium
6119:with linear latencies is
5715:In other words, the flow
5232:{\displaystyle \Gamma ,R}
4064:{\displaystyle \Gamma ,R}
1530:Each machine has a speed
1118:
1095:
1090:
1087:
137:{\displaystyle G=(N,S,u)}
9500:Evolutionary game theory
9233:Antoine Augustin Cournot
9119:Guess 2/3 of the average
8916:Strictly determined game
8710:Satisfaction equilibrium
8528:Escalation of commitment
8320:10.1109/tac.2017.2765299
7487:{\displaystyle \leq d+1}
6143:{\displaystyle \leq 4/3}
4843:Proof (By contradiction)
4071:are clear from context.
3043:{\displaystyle a=b=2000}
3011:{\displaystyle a+b=4000}
2229:{\displaystyle \leq 4/3}
9505:Glossary of game theory
9104:Stackelberg competition
8730:Strong Nash equilibrium
8406:Algorithmic Game Theory
8222:Algorithmic Game Theory
8165:Computer Science Review
8161:"Worst-case Equilibria"
4497:{\displaystyle \Gamma }
3333:{\displaystyle G=(V,E)}
2857:
2512:{\displaystyle \sigma }
2131:, the mixed strategies
1071:
473:We can define a subset
96:Mathematical definition
90:algorithmic game theory
82:approximation algorithm
9530:Tragedy of the commons
9510:List of game theorists
9490:Confrontation analysis
9200:Sprague–Grundy theorem
8720:Sequential equilibrium
8640:Correlated equilibrium
8131:Tragedy of the commons
8071:holds for any outcome
8062:
7961:
7901:
7878:
7808:
7692:
7561:
7511:
7488:
7459:
7439:
7413:
7385:
7294:
7131:
6988:
6919:
6744:
6534:
6413:
6291:
6264:
6170:
6144:
6113:
6070:
6011:
5951:
5931:
5905:
5877:
5857:
5843:reroutes some flow of
5837:
5810:
5783:
5756:
5736:
5706:
5596:
5551:
5506:
5479:
5452:
5426:
5377:
5233:
5207:
5180:
5156:
5060:
4940:
4904:
4833:
4753:
4726:
4700:
4589:
4569:
4538:
4518:
4498:
4478:
4458:
4420:
4378:
4246:
4219:
4192:
4163:
4104:
4065:
4039:
4009:
3926:
3903:
3778:
3756:
3729:
3702:
3679:
3653:
3617:
3471:
3374:
3354:
3334:
3281:
3231:
3190:
3139:
3085:
3044:
3012:
2980:
2945:
2925:
2890:
2872:
2838:
2809:
2777:
2626:
2603:
2513:
2487:
2456:
2436:
2416:
2396:
2376:
2356:
2336:
2316:
2289:
2269:
2230:
2199:
2125:
2079:
2053:
2007:
1968:
1903:
1835:
1812:
1712:
1688:
1628:
1582:Each job has a weight
1576:
1520:
1500:
1465:
1385:
1334:
1273:
1057:
1011:
896:
771:
658:
622:
505:
464:
391:
318:
284:
226:
185:
158:
138:
78:Christos Papadimitriou
59:Mixed Price of Anarchy
32:that measures how the
9303:Jean-François Mertens
8063:
7941:
7902:
7879:
7809:
7693:
7562:
7512:
7489:
7460:
7440:
7414:
7386:
7303:We can conclude that
7295:
7132:
6989:
6920:
6745:
6535:
6414:
6292:
6290:{\displaystyle f^{*}}
6265:
6171:
6145:
6114:
6112:{\displaystyle (G,L)}
6071:
6012:
5952:
5932:
5906:
5878:
5858:
5838:
5836:{\displaystyle f^{*}}
5811:
5809:{\displaystyle t_{i}}
5784:
5782:{\displaystyle s_{i}}
5757:
5737:
5735:{\displaystyle f^{*}}
5707:
5597:
5552:
5507:
5505:{\displaystyle t_{i}}
5480:
5478:{\displaystyle s_{i}}
5453:
5427:
5378:
5234:
5208:
5206:{\displaystyle f^{*}}
5181:
5157:
5040:
4920:
4905:
4834:
4754:
4752:{\displaystyle f^{*}}
4727:
4701:
4590:
4570:
4568:{\displaystyle f^{*}}
4539:
4519:
4499:
4479:
4459:
4421:
4379:
4247:
4245:{\displaystyle t_{i}}
4220:
4218:{\displaystyle s_{i}}
4193:
4164:
4112:Nash-equilibrium flow
4105:
4066:
4040:
4038:{\displaystyle f_{e}}
4010:
3927:
3904:
3779:
3757:
3755:{\displaystyle t_{i}}
3730:
3728:{\displaystyle s_{i}}
3703:
3680:
3654:
3618:
3472:
3375:
3355:
3335:
3282:
3232:
3191:
3140:
3086:
3045:
3013:
2981:
2946:
2926:
2891:
2871:
2839:
2810:
2778:
2627:
2604:
2514:
2488:
2457:
2437:
2417:
2397:
2377:
2357:
2337:
2317:
2290:
2270:
2268:{\displaystyle a^{*}}
2231:
2200:
2126:
2080:
2054:
2008:
1969:
1904:
1836:
1813:
1713:
1689:
1629:
1577:
1521:
1501:
1466:
1386:
1335:
1274:
1058:
1012:
897:
772:
659:
623:
506:
465:
392:
319:
285:
227:
186:
184:{\displaystyle S_{i}}
159:
139:
55:Pure Price of Anarchy
9432:Search optimizations
9308:Jennifer Tour Chayes
9195:Revelation principle
9190:Purification theorem
9129:Nash bargaining game
9094:Bertrand competition
9079:El Farol Bar problem
9044:Electronic mail game
9009:Lewis signaling game
8553:Hierarchy of beliefs
7938:
7891:
7821:
7705:
7574:
7521:
7501:
7469:
7449:
7429:
7403:
7307:
7144:
7004:
6932:
6757:
6550:
6426:
6304:
6274:
6180:
6160:
6123:
6091:
6027:
5961:
5941:
5921:
5895:
5867:
5847:
5820:
5793:
5766:
5746:
5719:
5609:
5561:
5516:
5489:
5462:
5436:
5390:
5246:
5217:
5190:
5170:
4917:
4849:
4763:
4736:
4716:
4602:
4579:
4552:
4528:
4508:
4488:
4468:
4430:
4397:
4258:
4229:
4202:
4173:
4118:
4081:
4049:
4022:
3939:
3916:
3791:
3765:
3739:
3712:
3692:
3663:
3630:
3481:
3384:
3364:
3344:
3306:
3241:
3200:
3150:
3099:
3054:
3022:
2990:
2955:
2935:
2900:
2880:
2837:{\displaystyle w(a)}
2819:
2790:
2639:
2616:
2526:
2503:
2477:
2446:
2426:
2406:
2386:
2366:
2346:
2326:
2306:
2279:
2252:
2209:
2135:
2089:
2063:
2017:
1991:
1913:
1845:
1825:
1821:The cost for player
1725:
1702:
1638:
1586:
1534:
1510:
1490:
1395:
1344:
1287:
1147:
1023:
910:
795:
670:
634:
521:
477:
401:
328:
294:
236:
195:
168:
148:
104:
9480:Bounded rationality
9099:Cournot competition
9049:Rock paper scissors
9024:Battle of the sexes
9014:Volunteer's dilemma
8886:Perfect information
8813:Dominant strategies
8650:Epsilon-equilibrium
8533:Extensive-form game
7991:
7907:tends to infinity.
6839:
6811:
6726:
6638:
6516:
6479:
6366:
5578:
5533:
5451:{\displaystyle p,q}
5348:
4991:
4732:and any other flow
4665:
4546:conditional welfare
4453:
2078:{\displaystyle M=2}
2006:{\displaystyle N=2}
9459:Paranoid algorithm
9439:Alpha–beta pruning
9318:John Maynard Smith
9149:Rendezvous problem
8989:Traveler's dilemma
8979:Gift-exchange game
8974:Prisoner's dilemma
8891:Large Poisson game
8858:Bargaining problem
8763:Backward induction
8735:Subgame perfection
8690:Proper equilibrium
8389:Vazirani, Vijay V.
8273:Journal of the ACM
8126:Price of stability
8096:price of stability
8094:, followed by the
8058:
7977:
7897:
7874:
7804:
7688:
7557:
7507:
7484:
7455:
7435:
7409:
7381:
7290:
7286:
7276:
7251:
7185:
7127:
7077:
6984:
6915:
6873:
6825:
6797:
6783:
6740:
6712:
6711:
6624:
6597:
6530:
6502:
6501:
6465:
6441:
6409:
6352:
6351:
6287:
6260:
6234:
6166:
6140:
6109:
6066:
6007:
5947:
5927:
5901:
5873:
5853:
5833:
5806:
5779:
5752:
5732:
5702:
5672:
5627:
5592:
5564:
5547:
5519:
5502:
5475:
5448:
5422:
5373:
5334:
5333:
5284:
5229:
5203:
5176:
5152:
5125:
5096:
5010:
4977:
4976:
4900:
4829:
4749:
4722:
4696:
4651:
4649:
4585:
4565:
4544:on the graph: the
4534:
4514:
4494:
4474:
4454:
4433:
4416:
4374:
4342:
4295:
4242:
4215:
4188:
4159:
4100:
4061:
4035:
4005:
3989:
3922:
3899:
3830:
3774:
3752:
3725:
3698:
3675:
3649:
3613:
3467:
3370:
3350:
3330:
3277:
3269:
3254:
3227:
3219:
3186:
3178:
3163:
3135:
3127:
3112:
3081:
3067:
3040:
3008:
2976:
2968:
2941:
2921:
2913:
2886:
2873:
2844:proves the claim.
2834:
2805:
2773:
2754:
2724:
2693:
2669:
2622:
2599:
2580:
2556:
2509:
2483:
2452:
2432:
2412:
2392:
2372:
2352:
2332:
2312:
2285:
2265:
2226:
2195:
2121:
2075:
2049:
2003:
1974:, here called the
1964:
1944:
1921:
1899:
1831:
1808:
1781:
1708:
1684:
1624:
1572:
1516:
1496:
1461:
1381:
1330:
1269:
1078:prisoner's dilemma
1072:Prisoner's dilemma
1053:
1007:
988:
955:
892:
873:
828:
782:Price of Stability
767:
748:
715:
654:
618:
599:
554:
501:
460:
437:
387:
364:
314:
280:
222:
181:
154:
134:
24:) is a concept in
9538:
9537:
9444:Aspiration window
9413:Suzanne Scotchmer
9368:Oskar Morgenstern
9263:Donald B. Gillies
9205:Zermelo's theorem
9134:Induction puzzles
9089:Fair cake-cutting
9064:Public goods game
8994:Coordination game
8868:Intransitive game
8798:Forward induction
8680:Pareto efficiency
8660:Gibbs equilibrium
8630:Berge equilibrium
8578:Simultaneous game
8239:978-3-540-79308-3
7900:{\displaystyle d}
7869:
7868:
7846:
7802:
7801:
7780:
7762:
7744:
7743:
7686:
7685:
7654:
7653:
7611:
7610:
7555:
7510:{\displaystyle d}
7458:{\displaystyle d}
7438:{\displaystyle G}
7412:{\displaystyle L}
7236:
7214:
7212:
7170:
7062:
6979:
6858:
6768:
6696:
6582:
6486:
6432:
6336:
6218:
6169:{\displaystyle f}
5950:{\displaystyle y}
5930:{\displaystyle x}
5904:{\displaystyle L}
5876:{\displaystyle f}
5856:{\displaystyle f}
5755:{\displaystyle f}
5657:
5612:
5298:
5249:
5179:{\displaystyle f}
5110:
5061:
4995:
4941:
4910:. By definition,
4725:{\displaystyle f}
4634:
4588:{\displaystyle f}
4537:{\displaystyle f}
4517:{\displaystyle R}
4477:{\displaystyle G}
4327:
4280:
3967:
3925:{\displaystyle G}
3794:
3701:{\displaystyle p}
3373:{\displaystyle w}
3353:{\displaystyle L}
3268:
3253:
3218:
3177:
3162:
3126:
3111:
3066:
2967:
2951:drivers would be
2944:{\displaystyle b}
2912:
2896:drivers would be
2889:{\displaystyle a}
2768:
2745:
2715:
2707:
2684:
2660:
2625:{\displaystyle a}
2594:
2571:
2547:
2486:{\displaystyle M}
2455:{\displaystyle a}
2435:{\displaystyle j}
2415:{\displaystyle j}
2395:{\displaystyle j}
2375:{\displaystyle k}
2355:{\displaystyle k}
2335:{\displaystyle j}
2315:{\displaystyle i}
2288:{\displaystyle M}
1935:
1920:
1834:{\displaystyle i}
1803:
1753:
1711:{\displaystyle j}
1519:{\displaystyle M}
1499:{\displaystyle N}
1141:
1140:
1005:
973:
928:
890:
846:
813:
765:
733:
688:
616:
572:
539:
422:
349:
157:{\displaystyle N}
100:Consider a game
74:Elias Koutsoupias
9558:
9525:Topological game
9520:No-win situation
9418:Thomas Schelling
9398:Robert B. Wilson
9358:Merrill M. Flood
9328:John von Neumann
9238:Ariel Rubinstein
9223:Albert W. Tucker
9074:War of attrition
9034:Matching pennies
8675:Nash equilibrium
8598:Mechanism design
8563:Normal-form game
8518:Cooperative game
8491:
8484:
8477:
8468:
8462:Price of anarchy
8450:
8423:
8411:
8397:Roughgarden, Tim
8379:
8378:
8346:
8340:
8339:
8314:(7): 2242–2247.
8303:
8297:
8296:
8264:
8258:
8255:
8249:
8248:
8247:
8246:
8213:
8207:
8198:
8192:
8191:
8189:
8188:
8179:. Archived from
8156:
8100:mechanism design
8092:price of anarchy
8067:
8065:
8064:
8059:
8039:
8035:
8034:
8012:
8008:
8007:
8006:
7990:
7985:
7971:
7970:
7960:
7955:
7906:
7904:
7903:
7898:
7883:
7881:
7880:
7875:
7870:
7858:
7854:
7849:
7848:
7847:
7836:
7813:
7811:
7810:
7805:
7803:
7791:
7787:
7782:
7781:
7770:
7768:
7764:
7763:
7752:
7750:
7746:
7745:
7733:
7729:
7697:
7695:
7694:
7689:
7687:
7675:
7671:
7660:
7656:
7655:
7643:
7639:
7623:
7622:
7617:
7613:
7612:
7600:
7596:
7567:, in which case
7566:
7564:
7563:
7558:
7556:
7545:
7543:
7516:
7514:
7513:
7508:
7493:
7491:
7490:
7485:
7464:
7462:
7461:
7456:
7444:
7442:
7441:
7436:
7418:
7416:
7415:
7410:
7390:
7388:
7387:
7382:
7377:
7354:
7353:
7332:
7331:
7319:
7318:
7299:
7297:
7296:
7291:
7285:
7277:
7272:
7271:
7270:
7261:
7260:
7250:
7226:
7208:
7207:
7198:
7197:
7184:
7160:
7136:
7134:
7133:
7128:
7123:
7122:
7110:
7109:
7100:
7099:
7087:
7086:
7076:
7052:
7017:
6993:
6991:
6990:
6985:
6980:
6975:
6961:
6953:
6952:
6924:
6922:
6921:
6916:
6911:
6906:
6905:
6896:
6895:
6883:
6882:
6872:
6854:
6850:
6849:
6848:
6838:
6833:
6821:
6820:
6810:
6805:
6793:
6792:
6782:
6749:
6747:
6746:
6741:
6739:
6738:
6725:
6720:
6710:
6692:
6688:
6687:
6683:
6679:
6674:
6673:
6664:
6663:
6648:
6647:
6637:
6632:
6612:
6611:
6596:
6575:
6574:
6562:
6561:
6539:
6537:
6536:
6531:
6526:
6525:
6515:
6510:
6500:
6478:
6473:
6464:
6463:
6454:
6453:
6440:
6418:
6416:
6415:
6410:
6405:
6404:
6392:
6391:
6379:
6378:
6365:
6360:
6350:
6329:
6328:
6316:
6315:
6296:
6294:
6293:
6288:
6286:
6285:
6269:
6267:
6266:
6261:
6253:
6252:
6233:
6232:
6231:
6208:
6175:
6173:
6172:
6167:
6149:
6147:
6146:
6141:
6136:
6118:
6116:
6115:
6110:
6075:
6073:
6072:
6067:
6059:
6058:
6046:
6016:
6014:
6013:
6008:
6003:
5998:
5997:
5985:
5984:
5956:
5954:
5953:
5948:
5936:
5934:
5933:
5928:
5910:
5908:
5907:
5902:
5882:
5880:
5879:
5874:
5862:
5860:
5859:
5854:
5842:
5840:
5839:
5834:
5832:
5831:
5815:
5813:
5812:
5807:
5805:
5804:
5788:
5786:
5785:
5780:
5778:
5777:
5761:
5759:
5758:
5753:
5741:
5739:
5738:
5733:
5731:
5730:
5711:
5709:
5708:
5703:
5695:
5694:
5682:
5681:
5671:
5650:
5649:
5637:
5636:
5626:
5601:
5599:
5598:
5593:
5591:
5590:
5577:
5572:
5556:
5554:
5553:
5548:
5546:
5545:
5532:
5527:
5511:
5509:
5508:
5503:
5501:
5500:
5484:
5482:
5481:
5476:
5474:
5473:
5457:
5455:
5454:
5449:
5431:
5429:
5428:
5423:
5418:
5417:
5405:
5404:
5382:
5380:
5379:
5374:
5361:
5360:
5347:
5342:
5332:
5331:
5330:
5318:
5317:
5294:
5293:
5283:
5282:
5281:
5269:
5268:
5238:
5236:
5235:
5230:
5212:
5210:
5209:
5204:
5202:
5201:
5185:
5183:
5182:
5177:
5161:
5159:
5158:
5153:
5148:
5147:
5135:
5134:
5124:
5106:
5105:
5095:
5094:
5093:
5081:
5080:
5059:
5054:
5033:
5032:
5020:
5019:
5009:
4990:
4985:
4975:
4974:
4973:
4961:
4960:
4939:
4934:
4909:
4907:
4906:
4901:
4890:
4889:
4874:
4873:
4861:
4860:
4838:
4836:
4835:
4830:
4825:
4824:
4812:
4811:
4790:
4789:
4758:
4756:
4755:
4750:
4748:
4747:
4731:
4729:
4728:
4723:
4705:
4703:
4702:
4697:
4695:
4691:
4690:
4678:
4677:
4664:
4659:
4648:
4627:
4626:
4614:
4613:
4594:
4592:
4591:
4586:
4575:with respect to
4574:
4572:
4571:
4566:
4564:
4563:
4543:
4541:
4540:
4535:
4523:
4521:
4520:
4515:
4503:
4501:
4500:
4495:
4483:
4481:
4480:
4475:
4464:be two flows in
4463:
4461:
4460:
4455:
4452:
4447:
4425:
4423:
4422:
4417:
4415:
4414:
4383:
4381:
4380:
4375:
4370:
4366:
4365:
4353:
4352:
4341:
4323:
4319:
4318:
4306:
4305:
4294:
4270:
4269:
4251:
4249:
4248:
4243:
4241:
4240:
4224:
4222:
4221:
4216:
4214:
4213:
4197:
4195:
4194:
4189:
4168:
4166:
4165:
4160:
4149:
4148:
4136:
4135:
4109:
4107:
4106:
4101:
4099:
4098:
4070:
4068:
4067:
4062:
4044:
4042:
4041:
4036:
4034:
4033:
4014:
4012:
4011:
4006:
4001:
4000:
3999:
3988:
3963:
3962:
3931:
3929:
3928:
3923:
3908:
3906:
3905:
3900:
3886:
3885:
3873:
3872:
3855:
3854:
3842:
3841:
3840:
3829:
3828:
3827:
3815:
3814:
3783:
3781:
3780:
3775:
3761:
3759:
3758:
3753:
3751:
3750:
3734:
3732:
3731:
3726:
3724:
3723:
3707:
3705:
3704:
3699:
3684:
3682:
3681:
3676:
3658:
3656:
3655:
3650:
3648:
3647:
3622:
3620:
3619:
3614:
3588:
3587:
3575:
3574:
3550:
3549:
3537:
3536:
3518:
3517:
3505:
3504:
3476:
3474:
3473:
3468:
3457:
3456:
3446:
3437:
3436:
3418:
3417:
3405:
3404:
3379:
3377:
3376:
3371:
3359:
3357:
3356:
3351:
3339:
3337:
3336:
3331:
3286:
3284:
3283:
3278:
3270:
3261:
3255:
3246:
3236:
3234:
3233:
3228:
3220:
3211:
3195:
3193:
3192:
3187:
3179:
3170:
3164:
3155:
3144:
3142:
3141:
3136:
3128:
3119:
3113:
3104:
3090:
3088:
3087:
3082:
3068:
3059:
3049:
3047:
3046:
3041:
3017:
3015:
3014:
3009:
2985:
2983:
2982:
2977:
2969:
2960:
2950:
2948:
2947:
2942:
2930:
2928:
2927:
2922:
2914:
2905:
2895:
2893:
2892:
2887:
2864:Braess's paradox
2858:Braess's paradox
2843:
2841:
2840:
2835:
2814:
2812:
2811:
2806:
2782:
2780:
2779:
2774:
2769:
2767:
2766:
2765:
2764:
2753:
2737:
2736:
2735:
2734:
2723:
2713:
2708:
2706:
2705:
2704:
2703:
2692:
2682:
2681:
2680:
2679:
2668:
2658:
2631:
2629:
2628:
2623:
2608:
2606:
2605:
2600:
2595:
2593:
2592:
2591:
2590:
2579:
2569:
2568:
2567:
2566:
2555:
2545:
2518:
2516:
2515:
2510:
2492:
2490:
2489:
2484:
2461:
2459:
2458:
2453:
2441:
2439:
2438:
2433:
2421:
2419:
2418:
2413:
2401:
2399:
2398:
2393:
2381:
2379:
2378:
2373:
2361:
2359:
2358:
2353:
2341:
2339:
2338:
2333:
2321:
2319:
2318:
2313:
2294:
2292:
2291:
2286:
2274:
2272:
2271:
2266:
2264:
2263:
2235:
2233:
2232:
2227:
2222:
2204:
2202:
2201:
2196:
2188:
2174:
2160:
2159:
2147:
2146:
2130:
2128:
2127:
2122:
2114:
2113:
2101:
2100:
2084:
2082:
2081:
2076:
2058:
2056:
2055:
2050:
2042:
2041:
2029:
2028:
2012:
2010:
2009:
2004:
1973:
1971:
1970:
1965:
1954:
1953:
1943:
1922:
1918:
1908:
1906:
1905:
1900:
1886:
1885:
1884:
1883:
1857:
1856:
1840:
1838:
1837:
1832:
1817:
1815:
1814:
1809:
1804:
1802:
1801:
1792:
1791:
1790:
1780:
1773:
1772:
1751:
1737:
1736:
1717:
1715:
1714:
1709:
1693:
1691:
1690:
1685:
1650:
1649:
1633:
1631:
1630:
1625:
1617:
1616:
1598:
1597:
1581:
1579:
1578:
1573:
1565:
1564:
1546:
1545:
1525:
1523:
1522:
1517:
1505:
1503:
1502:
1497:
1470:
1468:
1467:
1462:
1451:
1440:
1439:
1424:
1419:
1418:
1390:
1388:
1387:
1382:
1362:
1361:
1339:
1337:
1336:
1331:
1311:
1310:
1281:Nash Equilibrium
1278:
1276:
1275:
1270:
1262:
1261:
1249:
1248:
1236:
1235:
1220:
1219:
1207:
1206:
1194:
1193:
1178:
1177:
1165:
1164:
1137:
1133:
1128:
1124:
1114:
1110:
1105:
1101:
1083:
1062:
1060:
1059:
1054:
1016:
1014:
1013:
1008:
1006:
1004:
987:
971:
954:
926:
901:
899:
898:
893:
891:
889:
872:
844:
827:
811:
776:
774:
773:
768:
766:
764:
747:
731:
714:
686:
663:
661:
660:
655:
653:
627:
625:
624:
619:
617:
615:
598:
570:
553:
537:
510:
508:
507:
502:
469:
467:
466:
461:
447:
446:
436:
396:
394:
393:
388:
374:
373:
363:
323:
321:
320:
315:
313:
289:
287:
286:
281:
279:
278:
254:
253:
231:
229:
228:
223:
221:
207:
206:
190:
188:
187:
182:
180:
179:
164:, strategy sets
163:
161:
160:
155:
143:
141:
140:
135:
86:online algorithm
67:Price of Sinking
51:Nash equilibrium
18:Price of Anarchy
9566:
9565:
9561:
9560:
9559:
9557:
9556:
9555:
9541:
9540:
9539:
9534:
9468:
9454:max^n algorithm
9427:
9423:William Vickrey
9383:Reinhard Selten
9338:Kenneth Binmore
9253:David K. Levine
9248:Daniel Kahneman
9215:
9209:
9185:Negamax theorem
9175:Minimax theorem
9153:
9114:Diner's dilemma
8969:All-pay auction
8935:
8921:Stochastic game
8873:Mean-field game
8844:
8837:
8808:Markov strategy
8744:
8610:
8602:
8573:Sequential game
8558:Information set
8543:Game complexity
8513:Congestion game
8501:
8495:
8457:
8455:Further reading
8447:
8429:Tim Roughgarden
8427:
8420:
8409:
8387:
8383:
8382:
8348:
8347:
8343:
8305:
8304:
8300:
8285:10.1145/2806883
8266:
8265:
8261:
8256:
8252:
8244:
8242:
8240:
8215:
8214:
8210:
8199:
8195:
8186:
8184:
8158:
8157:
8150:
8145:
8112:
8026:
8022:
7995:
7976:
7972:
7962:
7936:
7935:
7913:
7911:Further results
7889:
7888:
7827:
7819:
7818:
7721:
7717:
7716:
7712:
7711:
7703:
7702:
7631:
7627:
7588:
7584:
7583:
7572:
7571:
7519:
7518:
7499:
7498:
7467:
7466:
7447:
7446:
7427:
7426:
7401:
7400:
7345:
7323:
7310:
7305:
7304:
7262:
7252:
7215:
7199:
7189:
7142:
7141:
7114:
7101:
7091:
7078:
7002:
7001:
6962:
6944:
6930:
6929:
6897:
6887:
6874:
6840:
6812:
6784:
6767:
6763:
6755:
6754:
6730:
6665:
6655:
6639:
6620:
6616:
6603:
6602:
6598:
6566:
6553:
6548:
6547:
6517:
6455:
6445:
6424:
6423:
6396:
6383:
6370:
6320:
6307:
6302:
6301:
6277:
6272:
6271:
6244:
6223:
6178:
6177:
6158:
6157:
6121:
6120:
6089:
6088:
6050:
6025:
6024:
5989:
5976:
5959:
5958:
5939:
5938:
5919:
5918:
5893:
5892:
5865:
5864:
5845:
5844:
5823:
5818:
5817:
5796:
5791:
5790:
5769:
5764:
5763:
5744:
5743:
5722:
5717:
5716:
5686:
5673:
5641:
5628:
5607:
5606:
5582:
5559:
5558:
5537:
5514:
5513:
5492:
5487:
5486:
5465:
5460:
5459:
5434:
5433:
5409:
5396:
5388:
5387:
5352:
5322:
5309:
5285:
5273:
5260:
5244:
5243:
5239:, we know that
5215:
5214:
5193:
5188:
5187:
5168:
5167:
5139:
5126:
5097:
5085:
5072:
5024:
5011:
4965:
4952:
4915:
4914:
4881:
4865:
4852:
4847:
4846:
4845:. Assume that
4816:
4803:
4781:
4761:
4760:
4739:
4734:
4733:
4714:
4713:
4682:
4669:
4618:
4605:
4600:
4599:
4577:
4576:
4555:
4550:
4549:
4526:
4525:
4506:
4505:
4486:
4485:
4466:
4465:
4428:
4427:
4400:
4395:
4394:
4357:
4344:
4310:
4297:
4261:
4256:
4255:
4232:
4227:
4226:
4205:
4200:
4199:
4171:
4170:
4140:
4127:
4116:
4115:
4084:
4079:
4078:
4047:
4046:
4025:
4020:
4019:
3991:
3942:
3937:
3936:
3914:
3913:
3877:
3864:
3846:
3832:
3819:
3806:
3789:
3788:
3763:
3762:
3742:
3737:
3736:
3715:
3710:
3709:
3690:
3689:
3661:
3660:
3633:
3628:
3627:
3579:
3566:
3541:
3528:
3509:
3496:
3479:
3478:
3448:
3428:
3409:
3396:
3382:
3381:
3362:
3361:
3342:
3341:
3304:
3303:
3294:
3239:
3238:
3198:
3197:
3148:
3147:
3097:
3096:
3052:
3051:
3020:
3019:
2988:
2987:
2953:
2952:
2933:
2932:
2898:
2897:
2878:
2877:
2866:
2860:
2855:
2853:Selfish Routing
2817:
2816:
2788:
2787:
2756:
2738:
2726:
2714:
2695:
2683:
2671:
2659:
2637:
2636:
2614:
2613:
2582:
2570:
2558:
2546:
2524:
2523:
2501:
2500:
2475:
2474:
2444:
2443:
2424:
2423:
2404:
2403:
2384:
2383:
2364:
2363:
2344:
2343:
2324:
2323:
2304:
2303:
2277:
2276:
2255:
2250:
2249:
2207:
2206:
2151:
2138:
2133:
2132:
2105:
2092:
2087:
2086:
2061:
2060:
2033:
2020:
2015:
2014:
1989:
1988:
1945:
1911:
1910:
1875:
1870:
1848:
1843:
1842:
1823:
1822:
1793:
1782:
1764:
1752:
1728:
1723:
1722:
1700:
1699:
1641:
1636:
1635:
1608:
1589:
1584:
1583:
1556:
1537:
1532:
1531:
1508:
1507:
1488:
1487:
1480:
1425:
1398:
1393:
1392:
1347:
1342:
1341:
1290:
1285:
1284:
1253:
1240:
1227:
1211:
1198:
1185:
1169:
1156:
1145:
1144:
1135:
1131:
1126:
1122:
1112:
1108:
1103:
1099:
1074:
1069:
1021:
1020:
972:
927:
908:
907:
845:
812:
793:
792:
732:
687:
668:
667:
632:
631:
571:
538:
519:
518:
513:Nash equilibria
475:
474:
438:
399:
398:
365:
326:
325:
292:
291:
270:
245:
234:
233:
198:
193:
192:
171:
166:
165:
146:
145:
102:
101:
98:
12:
11:
5:
9564:
9562:
9554:
9553:
9543:
9542:
9536:
9535:
9533:
9532:
9527:
9522:
9517:
9512:
9507:
9502:
9497:
9492:
9487:
9482:
9476:
9474:
9470:
9469:
9467:
9466:
9461:
9456:
9451:
9446:
9441:
9435:
9433:
9429:
9428:
9426:
9425:
9420:
9415:
9410:
9405:
9400:
9395:
9390:
9388:Robert Axelrod
9385:
9380:
9375:
9370:
9365:
9363:Olga Bondareva
9360:
9355:
9353:Melvin Dresher
9350:
9345:
9343:Leonid Hurwicz
9340:
9335:
9330:
9325:
9320:
9315:
9310:
9305:
9300:
9295:
9290:
9285:
9280:
9278:Harold W. Kuhn
9275:
9270:
9268:Drew Fudenberg
9265:
9260:
9258:David M. Kreps
9255:
9250:
9245:
9243:Claude Shannon
9240:
9235:
9230:
9225:
9219:
9217:
9211:
9210:
9208:
9207:
9202:
9197:
9192:
9187:
9182:
9180:Nash's theorem
9177:
9172:
9167:
9161:
9159:
9155:
9154:
9152:
9151:
9146:
9141:
9136:
9131:
9126:
9121:
9116:
9111:
9106:
9101:
9096:
9091:
9086:
9081:
9076:
9071:
9066:
9061:
9056:
9051:
9046:
9041:
9039:Ultimatum game
9036:
9031:
9026:
9021:
9019:Dollar auction
9016:
9011:
9006:
9004:Centipede game
9001:
8996:
8991:
8986:
8981:
8976:
8971:
8966:
8961:
8959:Infinite chess
8956:
8951:
8945:
8943:
8937:
8936:
8934:
8933:
8928:
8926:Symmetric game
8923:
8918:
8913:
8911:Signaling game
8908:
8906:Screening game
8903:
8898:
8896:Potential game
8893:
8888:
8883:
8875:
8870:
8865:
8860:
8855:
8849:
8847:
8839:
8838:
8836:
8835:
8830:
8825:
8823:Mixed strategy
8820:
8815:
8810:
8805:
8800:
8795:
8790:
8785:
8780:
8775:
8770:
8765:
8760:
8754:
8752:
8746:
8745:
8743:
8742:
8737:
8732:
8727:
8722:
8717:
8712:
8707:
8705:Risk dominance
8702:
8697:
8692:
8687:
8682:
8677:
8672:
8667:
8662:
8657:
8652:
8647:
8642:
8637:
8632:
8627:
8622:
8616:
8614:
8604:
8603:
8601:
8600:
8595:
8590:
8585:
8580:
8575:
8570:
8565:
8560:
8555:
8550:
8548:Graphical game
8545:
8540:
8535:
8530:
8525:
8520:
8515:
8509:
8507:
8503:
8502:
8496:
8494:
8493:
8486:
8479:
8471:
8465:
8464:
8460:Fabio Cunial,
8456:
8453:
8452:
8451:
8445:
8425:
8418:
8381:
8380:
8341:
8298:
8259:
8250:
8238:
8208:
8193:
8147:
8146:
8144:
8141:
8140:
8139:
8133:
8128:
8123:
8118:
8111:
8108:
8069:
8068:
8057:
8054:
8051:
8048:
8045:
8042:
8038:
8033:
8029:
8025:
8021:
8018:
8015:
8011:
8005:
8002:
7998:
7994:
7989:
7984:
7980:
7975:
7969:
7965:
7959:
7954:
7951:
7948:
7944:
7912:
7909:
7896:
7885:
7884:
7873:
7867:
7864:
7861:
7857:
7852:
7845:
7842:
7839:
7834:
7830:
7826:
7815:
7814:
7800:
7797:
7794:
7790:
7785:
7779:
7776:
7773:
7767:
7761:
7758:
7755:
7749:
7742:
7739:
7736:
7732:
7727:
7724:
7720:
7715:
7710:
7699:
7698:
7684:
7681:
7678:
7674:
7669:
7666:
7663:
7659:
7652:
7649:
7646:
7642:
7637:
7634:
7630:
7626:
7621:
7616:
7609:
7606:
7603:
7599:
7594:
7591:
7587:
7582:
7579:
7554:
7551:
7548:
7542:
7538:
7535:
7532:
7529:
7526:
7506:
7483:
7480:
7477:
7474:
7454:
7434:
7408:
7380:
7376:
7372:
7369:
7366:
7363:
7360:
7357:
7352:
7348:
7344:
7341:
7338:
7335:
7330:
7326:
7322:
7317:
7313:
7301:
7300:
7289:
7284:
7281:
7275:
7269:
7265:
7259:
7255:
7249:
7246:
7243:
7239:
7235:
7232:
7229:
7225:
7221:
7218:
7211:
7206:
7202:
7196:
7192:
7188:
7183:
7180:
7177:
7173:
7169:
7166:
7163:
7159:
7155:
7152:
7149:
7138:
7137:
7126:
7121:
7117:
7113:
7108:
7104:
7098:
7094:
7090:
7085:
7081:
7075:
7072:
7069:
7065:
7061:
7058:
7055:
7051:
7047:
7044:
7041:
7038:
7035:
7032:
7029:
7026:
7023:
7020:
7016:
7012:
7009:
6995:
6994:
6983:
6978:
6974:
6971:
6968:
6965:
6959:
6956:
6951:
6947:
6943:
6940:
6937:
6926:
6925:
6914:
6910:
6904:
6900:
6894:
6890:
6886:
6881:
6877:
6871:
6868:
6865:
6861:
6857:
6853:
6847:
6843:
6837:
6832:
6828:
6824:
6819:
6815:
6809:
6804:
6800:
6796:
6791:
6787:
6781:
6778:
6775:
6771:
6766:
6762:
6751:
6750:
6737:
6733:
6729:
6724:
6719:
6715:
6709:
6706:
6703:
6699:
6695:
6691:
6686:
6682:
6678:
6672:
6668:
6662:
6658:
6654:
6651:
6646:
6642:
6636:
6631:
6627:
6623:
6619:
6615:
6610:
6606:
6601:
6595:
6592:
6589:
6585:
6581:
6578:
6573:
6569:
6565:
6560:
6556:
6541:
6540:
6529:
6524:
6520:
6514:
6509:
6505:
6499:
6496:
6493:
6489:
6485:
6482:
6477:
6472:
6468:
6462:
6458:
6452:
6448:
6444:
6439:
6435:
6431:
6420:
6419:
6408:
6403:
6399:
6395:
6390:
6386:
6382:
6377:
6373:
6369:
6364:
6359:
6355:
6349:
6346:
6343:
6339:
6335:
6332:
6327:
6323:
6319:
6314:
6310:
6284:
6280:
6259:
6256:
6251:
6247:
6243:
6240:
6237:
6230:
6226:
6221:
6217:
6214:
6211:
6207:
6203:
6200:
6197:
6194:
6191:
6188:
6185:
6165:
6139:
6135:
6131:
6128:
6108:
6105:
6102:
6099:
6096:
6065:
6062:
6057:
6053:
6049:
6045:
6041:
6038:
6035:
6032:
6006:
6002:
5996:
5992:
5988:
5983:
5979:
5975:
5972:
5969:
5966:
5946:
5926:
5900:
5872:
5852:
5830:
5826:
5803:
5799:
5776:
5772:
5751:
5729:
5725:
5713:
5712:
5701:
5698:
5693:
5689:
5685:
5680:
5676:
5670:
5667:
5664:
5660:
5656:
5653:
5648:
5644:
5640:
5635:
5631:
5625:
5622:
5619:
5615:
5589:
5585:
5581:
5576:
5571:
5567:
5544:
5540:
5536:
5531:
5526:
5522:
5499:
5495:
5472:
5468:
5447:
5444:
5441:
5432:and two paths
5421:
5416:
5412:
5408:
5403:
5399:
5395:
5384:
5383:
5372:
5369:
5366:
5359:
5355:
5351:
5346:
5341:
5337:
5329:
5325:
5321:
5316:
5312:
5308:
5305:
5301:
5297:
5292:
5288:
5280:
5276:
5272:
5267:
5263:
5259:
5256:
5252:
5228:
5225:
5222:
5200:
5196:
5175:
5164:
5163:
5151:
5146:
5142:
5138:
5133:
5129:
5123:
5120:
5117:
5113:
5109:
5104:
5100:
5092:
5088:
5084:
5079:
5075:
5071:
5068:
5064:
5058:
5053:
5050:
5047:
5043:
5039:
5036:
5031:
5027:
5023:
5018:
5014:
5008:
5005:
5002:
4998:
4994:
4989:
4984:
4980:
4972:
4968:
4964:
4959:
4955:
4951:
4948:
4944:
4938:
4933:
4930:
4927:
4923:
4899:
4896:
4893:
4888:
4884:
4880:
4877:
4872:
4868:
4864:
4859:
4855:
4828:
4823:
4819:
4815:
4810:
4806:
4802:
4799:
4796:
4793:
4788:
4784:
4780:
4777:
4774:
4771:
4768:
4746:
4742:
4721:
4707:
4706:
4694:
4689:
4685:
4681:
4676:
4672:
4668:
4663:
4658:
4654:
4647:
4644:
4641:
4637:
4633:
4630:
4625:
4621:
4617:
4612:
4608:
4595:is defined as
4584:
4562:
4558:
4533:
4513:
4493:
4473:
4451:
4446:
4443:
4440:
4436:
4413:
4410:
4407:
4403:
4385:
4384:
4373:
4369:
4364:
4360:
4356:
4351:
4347:
4340:
4337:
4334:
4330:
4326:
4322:
4317:
4313:
4309:
4304:
4300:
4293:
4290:
4287:
4283:
4279:
4276:
4273:
4268:
4264:
4239:
4235:
4212:
4208:
4187:
4184:
4181:
4178:
4158:
4155:
4152:
4147:
4143:
4139:
4134:
4130:
4126:
4123:
4097:
4094:
4091:
4087:
4060:
4057:
4054:
4032:
4028:
4016:
4015:
4004:
3998:
3994:
3987:
3984:
3981:
3977:
3974:
3970:
3966:
3961:
3958:
3955:
3952:
3949:
3945:
3932:is defined as
3921:
3910:
3909:
3898:
3895:
3892:
3889:
3884:
3880:
3876:
3871:
3867:
3863:
3860:
3853:
3849:
3845:
3839:
3835:
3826:
3822:
3818:
3813:
3809:
3804:
3801:
3797:
3773:
3770:
3749:
3745:
3722:
3718:
3697:
3674:
3671:
3668:
3646:
3643:
3640:
3636:
3612:
3609:
3606:
3603:
3600:
3597:
3594:
3591:
3586:
3582:
3578:
3573:
3569:
3565:
3562:
3559:
3556:
3553:
3548:
3544:
3540:
3535:
3531:
3527:
3524:
3521:
3516:
3512:
3508:
3503:
3499:
3495:
3492:
3489:
3486:
3466:
3463:
3460:
3455:
3451:
3445:
3440:
3435:
3431:
3427:
3424:
3421:
3416:
3412:
3408:
3403:
3399:
3395:
3392:
3389:
3369:
3349:
3329:
3326:
3323:
3320:
3317:
3314:
3311:
3293:
3290:
3276:
3273:
3267:
3264:
3258:
3252:
3249:
3226:
3223:
3217:
3214:
3208:
3205:
3185:
3182:
3176:
3173:
3167:
3161:
3158:
3134:
3131:
3125:
3122:
3116:
3110:
3107:
3080:
3077:
3074:
3071:
3065:
3062:
3039:
3036:
3033:
3030:
3027:
3007:
3004:
3001:
2998:
2995:
2975:
2972:
2966:
2963:
2940:
2920:
2917:
2911:
2908:
2885:
2862:Main article:
2859:
2856:
2854:
2851:
2833:
2830:
2827:
2824:
2804:
2801:
2798:
2795:
2784:
2783:
2772:
2763:
2759:
2752:
2748:
2744:
2741:
2733:
2729:
2722:
2718:
2711:
2702:
2698:
2691:
2687:
2678:
2674:
2667:
2663:
2656:
2653:
2650:
2647:
2644:
2621:
2610:
2609:
2598:
2589:
2585:
2578:
2574:
2565:
2561:
2554:
2550:
2543:
2540:
2537:
2534:
2531:
2508:
2482:
2451:
2431:
2411:
2391:
2371:
2351:
2331:
2311:
2284:
2262:
2258:
2225:
2221:
2217:
2214:
2194:
2191:
2187:
2183:
2180:
2177:
2173:
2169:
2166:
2163:
2158:
2154:
2150:
2145:
2141:
2120:
2117:
2112:
2108:
2104:
2099:
2095:
2074:
2071:
2068:
2048:
2045:
2040:
2036:
2032:
2027:
2023:
2002:
1999:
1996:
1963:
1960:
1957:
1952:
1948:
1942:
1938:
1934:
1931:
1928:
1925:
1898:
1895:
1892:
1889:
1882:
1878:
1873:
1869:
1866:
1863:
1860:
1855:
1851:
1830:
1819:
1818:
1807:
1800:
1796:
1789:
1785:
1779:
1776:
1771:
1767:
1763:
1760:
1756:
1749:
1746:
1743:
1740:
1735:
1731:
1707:
1683:
1680:
1677:
1674:
1671:
1668:
1665:
1662:
1659:
1656:
1653:
1648:
1644:
1623:
1620:
1615:
1611:
1607:
1604:
1601:
1596:
1592:
1571:
1568:
1563:
1559:
1555:
1552:
1549:
1544:
1540:
1515:
1495:
1484:job scheduling
1479:
1478:Job scheduling
1476:
1460:
1457:
1454:
1450:
1446:
1443:
1438:
1435:
1432:
1428:
1423:
1417:
1414:
1411:
1408:
1405:
1401:
1380:
1377:
1374:
1371:
1368:
1365:
1360:
1357:
1354:
1350:
1329:
1326:
1323:
1320:
1317:
1314:
1309:
1306:
1303:
1300:
1297:
1293:
1268:
1265:
1260:
1256:
1252:
1247:
1243:
1239:
1234:
1230:
1226:
1223:
1218:
1214:
1210:
1205:
1201:
1197:
1192:
1188:
1184:
1181:
1176:
1172:
1168:
1163:
1159:
1155:
1152:
1139:
1138:
1129:
1120:
1116:
1115:
1106:
1097:
1093:
1092:
1089:
1086:
1073:
1070:
1068:
1065:
1052:
1049:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1003:
1000:
997:
994:
991:
986:
983:
980:
976:
970:
967:
964:
961:
958:
953:
950:
947:
944:
941:
938:
935:
931:
924:
921:
918:
915:
888:
885:
882:
879:
876:
871:
868:
865:
862:
859:
856:
853:
849:
843:
840:
837:
834:
831:
826:
823:
820:
816:
809:
806:
803:
800:
763:
760:
757:
754:
751:
746:
743:
740:
736:
730:
727:
724:
721:
718:
713:
710:
707:
704:
701:
698:
695:
691:
684:
681:
678:
675:
652:
648:
645:
642:
639:
614:
611:
608:
605:
602:
597:
594:
591:
588:
585:
582:
579:
575:
569:
566:
563:
560:
557:
552:
549:
546:
542:
535:
532:
529:
526:
500:
497:
494:
491:
488:
485:
482:
459:
456:
453:
450:
445:
441:
435:
432:
429:
425:
421:
418:
415:
412:
409:
406:
386:
383:
380:
377:
372:
368:
362:
359:
356:
352:
348:
345:
342:
339:
336:
333:
312:
308:
305:
302:
299:
277:
273:
269:
266:
263:
260:
257:
252:
248:
244:
241:
220:
216:
213:
210:
205:
201:
178:
174:
153:
133:
130:
127:
124:
121:
118:
115:
112:
109:
97:
94:
13:
10:
9:
6:
4:
3:
2:
9563:
9552:
9549:
9548:
9546:
9531:
9528:
9526:
9523:
9521:
9518:
9516:
9513:
9511:
9508:
9506:
9503:
9501:
9498:
9496:
9493:
9491:
9488:
9486:
9483:
9481:
9478:
9477:
9475:
9473:Miscellaneous
9471:
9465:
9462:
9460:
9457:
9455:
9452:
9450:
9447:
9445:
9442:
9440:
9437:
9436:
9434:
9430:
9424:
9421:
9419:
9416:
9414:
9411:
9409:
9408:Samuel Bowles
9406:
9404:
9403:Roger Myerson
9401:
9399:
9396:
9394:
9393:Robert Aumann
9391:
9389:
9386:
9384:
9381:
9379:
9376:
9374:
9371:
9369:
9366:
9364:
9361:
9359:
9356:
9354:
9351:
9349:
9348:Lloyd Shapley
9346:
9344:
9341:
9339:
9336:
9334:
9333:Kenneth Arrow
9331:
9329:
9326:
9324:
9321:
9319:
9316:
9314:
9313:John Harsanyi
9311:
9309:
9306:
9304:
9301:
9299:
9296:
9294:
9291:
9289:
9286:
9284:
9283:Herbert Simon
9281:
9279:
9276:
9274:
9271:
9269:
9266:
9264:
9261:
9259:
9256:
9254:
9251:
9249:
9246:
9244:
9241:
9239:
9236:
9234:
9231:
9229:
9226:
9224:
9221:
9220:
9218:
9212:
9206:
9203:
9201:
9198:
9196:
9193:
9191:
9188:
9186:
9183:
9181:
9178:
9176:
9173:
9171:
9168:
9166:
9163:
9162:
9160:
9156:
9150:
9147:
9145:
9142:
9140:
9137:
9135:
9132:
9130:
9127:
9125:
9122:
9120:
9117:
9115:
9112:
9110:
9107:
9105:
9102:
9100:
9097:
9095:
9092:
9090:
9087:
9085:
9084:Fair division
9082:
9080:
9077:
9075:
9072:
9070:
9067:
9065:
9062:
9060:
9059:Dictator game
9057:
9055:
9052:
9050:
9047:
9045:
9042:
9040:
9037:
9035:
9032:
9030:
9027:
9025:
9022:
9020:
9017:
9015:
9012:
9010:
9007:
9005:
9002:
9000:
8997:
8995:
8992:
8990:
8987:
8985:
8982:
8980:
8977:
8975:
8972:
8970:
8967:
8965:
8962:
8960:
8957:
8955:
8952:
8950:
8947:
8946:
8944:
8942:
8938:
8932:
8931:Zero-sum game
8929:
8927:
8924:
8922:
8919:
8917:
8914:
8912:
8909:
8907:
8904:
8902:
8901:Repeated game
8899:
8897:
8894:
8892:
8889:
8887:
8884:
8882:
8880:
8876:
8874:
8871:
8869:
8866:
8864:
8861:
8859:
8856:
8854:
8851:
8850:
8848:
8846:
8840:
8834:
8831:
8829:
8826:
8824:
8821:
8819:
8818:Pure strategy
8816:
8814:
8811:
8809:
8806:
8804:
8801:
8799:
8796:
8794:
8791:
8789:
8786:
8784:
8783:De-escalation
8781:
8779:
8776:
8774:
8771:
8769:
8766:
8764:
8761:
8759:
8756:
8755:
8753:
8751:
8747:
8741:
8738:
8736:
8733:
8731:
8728:
8726:
8725:Shapley value
8723:
8721:
8718:
8716:
8713:
8711:
8708:
8706:
8703:
8701:
8698:
8696:
8693:
8691:
8688:
8686:
8683:
8681:
8678:
8676:
8673:
8671:
8668:
8666:
8663:
8661:
8658:
8656:
8653:
8651:
8648:
8646:
8643:
8641:
8638:
8636:
8633:
8631:
8628:
8626:
8623:
8621:
8618:
8617:
8615:
8613:
8609:
8605:
8599:
8596:
8594:
8593:Succinct game
8591:
8589:
8586:
8584:
8581:
8579:
8576:
8574:
8571:
8569:
8566:
8564:
8561:
8559:
8556:
8554:
8551:
8549:
8546:
8544:
8541:
8539:
8536:
8534:
8531:
8529:
8526:
8524:
8521:
8519:
8516:
8514:
8511:
8510:
8508:
8504:
8500:
8492:
8487:
8485:
8480:
8478:
8473:
8472:
8469:
8463:
8459:
8458:
8454:
8448:
8446:0-262-18243-2
8442:
8438:
8434:
8430:
8426:
8421:
8419:0-521-87282-0
8415:
8408:
8407:
8402:
8398:
8394:
8390:
8385:
8384:
8376:
8372:
8368:
8364:
8361:: 3573–3578.
8360:
8356:
8352:
8345:
8342:
8337:
8333:
8329:
8325:
8321:
8317:
8313:
8309:
8302:
8299:
8294:
8290:
8286:
8282:
8278:
8274:
8270:
8263:
8260:
8254:
8251:
8241:
8235:
8231:
8227:
8223:
8219:
8212:
8209:
8205:
8204:
8197:
8194:
8183:on 2016-03-13
8182:
8178:
8174:
8170:
8166:
8162:
8155:
8153:
8149:
8142:
8137:
8134:
8132:
8129:
8127:
8124:
8122:
8119:
8117:
8114:
8113:
8109:
8107:
8103:
8101:
8097:
8093:
8088:
8086:
8082:
8078:
8074:
8052:
8046:
8043:
8040:
8036:
8031:
8027:
8023:
8019:
8016:
8013:
8009:
8003:
8000:
7996:
7992:
7987:
7982:
7978:
7973:
7967:
7963:
7957:
7952:
7949:
7946:
7942:
7934:
7933:
7932:
7930:
7928:
7924:
7918:
7910:
7908:
7894:
7871:
7865:
7862:
7859:
7855:
7850:
7843:
7840:
7837:
7832:
7828:
7824:
7817:
7816:
7798:
7795:
7792:
7788:
7783:
7777:
7774:
7771:
7765:
7759:
7756:
7753:
7747:
7740:
7737:
7734:
7730:
7725:
7722:
7718:
7713:
7708:
7701:
7700:
7682:
7679:
7676:
7672:
7667:
7664:
7661:
7657:
7650:
7647:
7644:
7640:
7635:
7632:
7628:
7624:
7619:
7614:
7607:
7604:
7601:
7597:
7592:
7589:
7585:
7580:
7577:
7570:
7569:
7568:
7552:
7549:
7546:
7540:
7536:
7533:
7530:
7527:
7524:
7504:
7495:
7481:
7478:
7475:
7472:
7452:
7432:
7424:
7420:
7406:
7397:
7396:
7395:
7378:
7374:
7367:
7361:
7358:
7350:
7346:
7339:
7336:
7328:
7324:
7315:
7311:
7287:
7282:
7279:
7273:
7267:
7263:
7257:
7253:
7247:
7244:
7241:
7237:
7233:
7227:
7223:
7219:
7209:
7204:
7194:
7190:
7181:
7178:
7175:
7171:
7167:
7161:
7157:
7153:
7147:
7140:
7139:
7119:
7115:
7111:
7106:
7102:
7096:
7092:
7083:
7079:
7073:
7070:
7067:
7063:
7059:
7053:
7049:
7045:
7039:
7033:
7027:
7024:
7018:
7014:
7010:
7000:
6999:
6998:
6981:
6976:
6969:
6963:
6957:
6949:
6945:
6938:
6935:
6928:
6927:
6912:
6908:
6902:
6892:
6888:
6879:
6875:
6869:
6866:
6863:
6859:
6855:
6851:
6845:
6841:
6835:
6830:
6826:
6822:
6817:
6807:
6802:
6798:
6789:
6785:
6779:
6776:
6773:
6769:
6764:
6760:
6753:
6752:
6735:
6731:
6727:
6722:
6717:
6713:
6707:
6704:
6701:
6697:
6693:
6689:
6684:
6680:
6676:
6670:
6660:
6656:
6649:
6644:
6634:
6629:
6625:
6617:
6613:
6608:
6604:
6599:
6593:
6590:
6587:
6583:
6579:
6571:
6567:
6558:
6554:
6546:
6545:
6544:
6527:
6522:
6518:
6512:
6507:
6503:
6497:
6494:
6491:
6487:
6483:
6475:
6470:
6466:
6460:
6456:
6450:
6446:
6437:
6433:
6429:
6422:
6421:
6401:
6397:
6393:
6388:
6384:
6380:
6375:
6371:
6362:
6357:
6353:
6347:
6344:
6341:
6337:
6333:
6325:
6321:
6312:
6308:
6300:
6299:
6298:
6282:
6278:
6249:
6245:
6238:
6228:
6224:
6215:
6209:
6205:
6201:
6195:
6189:
6183:
6163:
6155:
6151:
6137:
6133:
6129:
6126:
6103:
6100:
6097:
6086:
6082:
6081:
6080:
6063:
6060:
6055:
6047:
6043:
6039:
6036:
6033:
6022:
6018:
6004:
6000:
5994:
5990:
5986:
5981:
5977:
5973:
5970:
5967:
5964:
5944:
5924:
5916:
5912:
5898:
5889:
5888:
5887:
5870:
5850:
5828:
5824:
5801:
5797:
5774:
5770:
5749:
5727:
5723:
5699:
5691:
5687:
5678:
5674:
5668:
5665:
5662:
5658:
5654:
5646:
5642:
5633:
5629:
5623:
5620:
5617:
5613:
5605:
5604:
5603:
5587:
5583:
5579:
5574:
5569:
5565:
5542:
5538:
5534:
5529:
5524:
5520:
5497:
5493:
5470:
5466:
5445:
5442:
5439:
5414:
5410:
5406:
5401:
5397:
5370:
5367:
5357:
5353:
5349:
5344:
5339:
5335:
5327:
5323:
5314:
5310:
5306:
5303:
5299:
5295:
5290:
5286:
5278:
5274:
5265:
5261:
5257:
5254:
5250:
5242:
5241:
5240:
5226:
5223:
5198:
5194:
5173:
5144:
5140:
5131:
5127:
5121:
5118:
5115:
5111:
5107:
5102:
5098:
5090:
5086:
5077:
5073:
5069:
5066:
5062:
5056:
5051:
5048:
5045:
5041:
5037:
5029:
5025:
5016:
5012:
5006:
5003:
5000:
4996:
4992:
4987:
4982:
4978:
4970:
4966:
4957:
4953:
4949:
4946:
4942:
4936:
4931:
4928:
4925:
4921:
4913:
4912:
4911:
4894:
4886:
4882:
4878:
4870:
4866:
4857:
4853:
4844:
4840:
4821:
4817:
4808:
4804:
4800:
4794:
4786:
4782:
4778:
4772:
4766:
4744:
4740:
4719:
4711:
4687:
4683:
4674:
4670:
4666:
4661:
4656:
4652:
4645:
4642:
4639:
4635:
4631:
4623:
4619:
4610:
4606:
4598:
4597:
4596:
4582:
4560:
4556:
4547:
4531:
4511:
4471:
4449:
4444:
4441:
4434:
4411:
4408:
4401:
4392:
4388:
4371:
4362:
4358:
4349:
4345:
4338:
4335:
4332:
4328:
4324:
4315:
4311:
4302:
4298:
4291:
4288:
4285:
4281:
4274:
4271:
4266:
4262:
4254:
4253:
4252:
4237:
4233:
4210:
4206:
4185:
4182:
4179:
4153:
4145:
4141:
4137:
4132:
4128:
4113:
4095:
4092:
4085:
4076:
4072:
4058:
4055:
4030:
4026:
4002:
3996:
3992:
3985:
3982:
3979:
3975:
3972:
3968:
3964:
3959:
3956:
3950:
3947:
3943:
3935:
3934:
3933:
3919:
3896:
3890:
3882:
3878:
3874:
3869:
3865:
3851:
3847:
3843:
3837:
3833:
3824:
3820:
3811:
3807:
3802:
3799:
3795:
3787:
3786:
3785:
3768:
3747:
3743:
3720:
3716:
3695:
3688:
3666:
3644:
3641:
3634:
3626:
3607:
3604:
3601:
3595:
3584:
3580:
3576:
3571:
3567:
3560:
3557:
3554:
3546:
3542:
3538:
3533:
3529:
3522:
3514:
3510:
3506:
3501:
3497:
3487:
3461:
3458:
3453:
3449:
3438:
3433:
3429:
3425:
3422:
3419:
3414:
3410:
3406:
3401:
3397:
3390:
3387:
3367:
3347:
3324:
3321:
3318:
3312:
3309:
3301:
3297:
3291:
3289:
3274:
3271:
3265:
3262:
3256:
3250:
3247:
3224:
3221:
3215:
3212:
3206:
3203:
3183:
3180:
3174:
3171:
3165:
3159:
3156:
3132:
3129:
3123:
3120:
3114:
3108:
3105:
3092:
3078:
3075:
3072:
3069:
3063:
3060:
3037:
3034:
3031:
3028:
3025:
3005:
3002:
2999:
2996:
2993:
2973:
2970:
2964:
2961:
2938:
2918:
2915:
2909:
2906:
2883:
2870:
2865:
2852:
2850:
2849:
2848:
2828:
2822:
2799:
2793:
2770:
2761:
2757:
2750:
2742:
2739:
2731:
2727:
2720:
2716:
2709:
2700:
2696:
2689:
2685:
2676:
2672:
2665:
2661:
2654:
2648:
2642:
2635:
2634:
2633:
2619:
2596:
2587:
2583:
2576:
2563:
2559:
2552:
2548:
2541:
2535:
2529:
2522:
2521:
2520:
2506:
2498:
2494:
2480:
2472:
2468:
2467:
2466:
2449:
2429:
2409:
2389:
2369:
2349:
2329:
2309:
2300:
2298:
2297:lexicographic
2282:
2260:
2256:
2247:
2243:
2241:
2237:
2223:
2219:
2215:
2212:
2189:
2185:
2181:
2178:
2175:
2171:
2167:
2161:
2156:
2152:
2148:
2143:
2139:
2118:
2115:
2110:
2106:
2102:
2097:
2093:
2072:
2069:
2066:
2046:
2043:
2038:
2034:
2030:
2025:
2021:
2000:
1997:
1994:
1986:
1981:
1980:
1978:
1958:
1950:
1946:
1940:
1932:
1926:
1896:
1890:
1880:
1876:
1871:
1867:
1861:
1853:
1849:
1828:
1805:
1798:
1794:
1787:
1783:
1777:
1774:
1769:
1765:
1761:
1758:
1754:
1747:
1741:
1733:
1729:
1721:
1720:
1719:
1705:
1697:
1681:
1675:
1672:
1669:
1666:
1663:
1660:
1657:
1651:
1646:
1642:
1621:
1618:
1613:
1609:
1605:
1602:
1599:
1594:
1590:
1569:
1566:
1561:
1557:
1553:
1550:
1547:
1542:
1538:
1528:
1513:
1493:
1485:
1477:
1475:
1472:
1458:
1455:
1452:
1448:
1444:
1441:
1436:
1433:
1430:
1426:
1421:
1415:
1412:
1409:
1406:
1403:
1399:
1378:
1375:
1372:
1369:
1366:
1363:
1358:
1355:
1352:
1348:
1327:
1324:
1321:
1318:
1315:
1312:
1307:
1304:
1301:
1298:
1295:
1291:
1282:
1266:
1258:
1254:
1250:
1245:
1241:
1232:
1228:
1224:
1216:
1212:
1208:
1203:
1199:
1190:
1186:
1182:
1174:
1170:
1166:
1161:
1157:
1150:
1130:
1121:
1117:
1107:
1098:
1094:
1085:
1084:
1081:
1079:
1066:
1064:
1050:
1047:
1044:
1041:
1038:
1035:
1032:
1029:
1026:
1019:We know that
1017:
998:
992:
989:
984:
981:
978:
965:
959:
956:
951:
948:
945:
942:
939:
936:
933:
922:
919:
916:
913:
905:
902:
883:
877:
874:
869:
866:
863:
860:
857:
854:
851:
838:
832:
829:
824:
821:
818:
807:
804:
801:
798:
790:
788:
784:
783:
777:
758:
752:
749:
744:
741:
738:
725:
719:
716:
711:
708:
705:
702:
699:
696:
693:
682:
679:
676:
673:
665:
643:
640:
637:
628:
609:
603:
600:
595:
592:
589:
586:
583:
580:
577:
564:
558:
555:
550:
547:
544:
533:
530:
527:
524:
516:
514:
498:
495:
492:
489:
486:
483:
480:
471:
457:
451:
443:
439:
433:
430:
427:
419:
413:
407:
404:
384:
378:
370:
366:
360:
357:
354:
350:
346:
340:
334:
331:
303:
300:
297:
275:
271:
267:
264:
261:
258:
255:
250:
246:
242:
239:
211:
208:
203:
199:
176:
172:
151:
128:
125:
122:
119:
116:
110:
107:
95:
93:
91:
87:
83:
79:
75:
70:
68:
64:
60:
56:
52:
47:
42:
39:
35:
31:
27:
23:
19:
9378:Peyton Young
9373:Paul Milgrom
9288:Hervé Moulin
9228:Amos Tversky
9170:Folk theorem
8881:-player game
8878:
8803:Grim trigger
8432:
8405:
8358:
8354:
8344:
8311:
8307:
8301:
8276:
8272:
8262:
8253:
8243:, retrieved
8221:
8211:
8201:
8196:
8185:. Retrieved
8181:the original
8171:(2): 65–69.
8168:
8164:
8104:
8091:
8089:
8084:
8080:
8076:
8072:
8070:
7926:
7922:
7920:
7916:
7914:
7886:
7496:
7422:
7421:
7398:
7393:
7392:
7302:
6996:
6542:
6153:
6152:
6084:
6083:
6078:
6077:
6020:
6019:
5914:
5913:
5890:
5885:
5884:
5714:
5385:
5165:
4842:
4841:
4709:
4708:
4545:
4390:
4389:
4386:
4111:
4074:
4073:
4017:
3911:
3686:
3624:
3299:
3298:
3295:
3093:
2874:
2846:
2845:
2785:
2611:
2496:
2495:
2470:
2469:
2464:
2463:
2301:
2296:
2245:
2244:
2239:
2238:
1982:
1975:
1820:
1695:
1529:
1486:. There are
1483:
1481:
1473:
1142:
1075:
1018:
906:
903:
791:
786:
780:
778:
666:
629:
517:
472:
99:
71:
66:
62:
58:
54:
43:
21:
17:
15:
9495:Coopetition
9298:Jean Tirole
9293:John Conway
9273:Eric Maskin
9069:Blotto game
9054:Pirate game
8863:Global game
8833:Tit for tat
8768:Bid shading
8758:Appeasement
8608:Equilibrium
8588:Solved game
8523:Determinacy
8506:Definitions
8499:game theory
8401:Tardos, Éva
8393:Nisan, Noam
8279:(5): 1–42.
3708:going from
2342:to machine
1698:on machine
1694:Define the
30:game theory
9139:Trust game
9124:Kuhn poker
8793:Escalation
8788:Deterrence
8778:Cheap talk
8750:Strategies
8568:Preference
8497:Topics of
8245:2023-12-29
8187:2010-09-12
8143:References
7917:smoothness
5512:such that
2632:: clearly
1985:mixed Nash
1096:Cooperate
1088:Cooperate
34:efficiency
9323:John Nash
9029:Stag hunt
8773:Collusion
8437:MIT Press
8375:2475-1456
8328:0018-9286
8293:0004-5411
8206:, FOCS 05
8044:μ
8032:∗
8017:λ
8014:≤
8001:−
7988:∗
7943:∑
7833:−
7825:≤
7726:−
7668:⋅
7636:−
7625:⋅
7593:−
7534:−
7473:≤
7351:∗
7337:≤
7329:∗
7280:≥
7274:⏟
7245:∈
7238:∑
7234:⋅
7179:∈
7172:∑
7168:⋅
7071:∈
7064:∑
7060:⋅
7025:⋅
6950:∗
6936:≤
6867:∈
6860:∑
6836:∗
6808:∗
6777:∈
6770:∑
6728:⋅
6723:∗
6705:∈
6698:∑
6635:∗
6614:⋅
6591:∈
6584:∑
6580:≤
6572:∗
6513:∗
6495:∈
6488:∑
6476:∗
6434:∑
6381:⋅
6363:∗
6345:∈
6338:∑
6326:∗
6283:∗
6250:∗
6229:∗
6216:⋅
6196:≤
6127:≤
6061:≥
6037:−
5974:≤
5968:⋅
5829:∗
5728:∗
5666:∈
5659:∑
5621:∈
5614:∑
5575:∗
5530:∗
5365:∀
5345:∗
5320:→
5300:∑
5271:→
5251:∑
5221:Γ
5199:∗
5119:∈
5112:∑
5108:⋅
5083:→
5063:∑
5042:∑
5004:∈
4997:∑
4993:⋅
4988:∗
4963:→
4943:∑
4922:∑
4871:∗
4822:∗
4801:≤
4745:∗
4667:⋅
4662:∗
4643:∈
4636:∑
4624:∗
4561:∗
4492:Γ
4450:∗
4439:Γ
4406:Γ
4336:∈
4329:∑
4325:≤
4289:∈
4282:∑
4278:⇒
4177:∀
4157:Γ
4154:∈
4122:∀
4090:Γ
4077:. A flow
4053:Γ
3983:∈
3969:∑
3954:Γ
3894:Γ
3891:∈
3859:∀
3817:→
3796:∑
3772:Γ
3769:∈
3673:ℜ
3670:↦
3639:Γ
3605:×
3596:⊆
3558:…
3485:Γ
3423:…
2800:σ
2743:⋅
2717:∑
2710:≥
2686:∑
2662:∑
2655:≥
2549:∑
2542:≤
2536:σ
2507:σ
2261:∗
2213:≤
2153:σ
2140:σ
1755:∑
1670:…
1603:…
1551:…
1042:≤
1030:≤
993:
982:∈
960:
937:∈
878:
855:∈
833:
822:∈
753:
742:∈
720:
697:∈
647:→
604:
581:∈
559:
548:∈
496:⊆
431:∈
408:
358:∈
351:∑
335:
307:→
268:×
256:×
215:→
26:economics
9545:Category
9464:Lazy SMP
9158:Theorems
9109:Deadlock
8964:Checkers
8845:of games
8612:concepts
8431:(2005).
8403:(2007).
8336:45923961
8110:See also
7929:)-smooth
6270:, where
1977:makespan
1067:Examples
9216:figures
8999:Chicken
8853:Auction
8843:Classes
7423:Theorem
6085:Theorem
1718:to be:
1119:Defect
1091:Defect
232:(where
38:selfish
8443:
8416:
8373:
8334:
8326:
8291:
8236:
8083:/(1 −
7394:Q.E.D.
6997:since
6079:Q.E.D.
5915:Fact 2
5886:Q.E.D.
5602:, and
5166:Since
4710:Fact 1
4393:. Let
3302:. Let
2465:Q.E.D.
2085:, and
8954:Chess
8941:Games
8410:(PDF)
8332:S2CID
6154:Proof
6021:Proof
5458:from
4198:from
4110:is a
4045:when
3133:40.01
2847:Q.E.D
2497:Proof
2471:Claim
2246:Proof
2240:Claim
8635:Core
8441:ISBN
8414:ISBN
8371:ISSN
8324:ISSN
8289:ISSN
8234:ISBN
8075:and
5937:and
5655:<
5580:<
5535:>
5186:and
5038:<
4879:<
4504:and
4426:and
4272:>
4169:and
4114:iff
3687:path
3625:flow
3623:. A
3459:>
3360:and
3263:4000
3248:4000
3213:4000
3172:4000
3157:2500
3121:2001
3106:2000
3061:2000
3038:2000
3006:4000
2815:and
1696:load
1619:>
1567:>
990:Cost
957:Cost
875:Welf
830:Welf
750:Cost
717:Cost
638:Cost
601:Welf
556:Welf
405:Welf
332:Welf
298:Welf
76:and
46:game
28:and
16:The
9214:Key
8363:doi
8316:doi
8281:doi
8226:doi
8173:doi
8087:).
6220:min
5789:to
5485:to
4548:of
4225:to
3735:to
3266:100
3251:100
3216:100
3175:100
3160:100
3124:100
3109:100
3064:100
2965:100
2910:100
2747:max
2573:max
2519:by
1937:max
1841:is
975:min
930:min
848:max
815:max
787:PoS
735:min
690:max
574:min
541:max
424:min
92:).
22:PoA
9547::
8949:Go
8439:.
8435:.
8399:;
8395:;
8391:;
8369:.
8357:.
8353:.
8330:.
8322:.
8312:63
8310:.
8287:.
8277:62
8275:.
8271:.
8232:,
8220:,
8167:.
8163:.
8151:^
7494:.
6176:,
6150:.
6076:.
6017:.
5957:,
5911:.
5557:,
4839:.
4759:,
3340:,
3275:80
3225:85
3204:45
3184:65
3079:65
3073:45
2974:45
2919:45
2493:.
2059:,
2013:,
1919:MS
1622:0.
1570:0.
1471:.
1445:10
1328:10
1134:,
1125:,
1111:,
1102:,
69:.
8879:n
8490:e
8483:t
8476:v
8449:.
8424:.
8422:.
8377:.
8365::
8359:7
8338:.
8318::
8295:.
8283::
8228::
8190:.
8175::
8169:3
8085:μ
8081:λ
8077:a
8073:a
8056:)
8053:a
8050:(
8047:C
8041:+
8037:)
8028:a
8024:(
8020:C
8010:)
8004:i
7997:a
7993:,
7983:i
7979:a
7974:(
7968:i
7964:C
7958:n
7953:1
7950:=
7947:i
7927:μ
7925:,
7923:λ
7921:(
7895:d
7872:.
7866:1
7863:+
7860:d
7856:1
7851:+
7844:1
7841:+
7838:d
7829:e
7799:1
7796:+
7793:d
7789:1
7784:+
7778:1
7775:+
7772:d
7766:)
7760:1
7757:+
7754:d
7748:)
7741:1
7738:+
7735:d
7731:1
7723:1
7719:(
7714:(
7709:=
7683:1
7680:+
7677:d
7673:1
7665:1
7662:+
7658:)
7651:1
7648:+
7645:d
7641:1
7633:1
7629:(
7620:d
7615:)
7608:1
7605:+
7602:d
7598:1
7590:1
7586:(
7581:=
7578:w
7553:1
7550:+
7547:d
7541:/
7537:1
7531:1
7528:=
7525:x
7505:d
7482:1
7479:+
7476:d
7453:d
7433:G
7407:L
7379:4
7375:/
7371:)
7368:f
7365:(
7362:w
7359:+
7356:)
7347:f
7343:(
7340:w
7334:)
7325:f
7321:(
7316:f
7312:w
7288:.
7283:0
7268:e
7264:b
7258:e
7254:f
7248:E
7242:e
7231:)
7228:4
7224:/
7220:1
7217:(
7210:+
7205:2
7201:)
7195:e
7191:f
7187:(
7182:E
7176:e
7165:)
7162:4
7158:/
7154:1
7151:(
7148:=
7125:)
7120:e
7116:b
7112:+
7107:e
7103:f
7097:e
7093:a
7089:(
7084:e
7080:f
7074:E
7068:e
7057:)
7054:4
7050:/
7046:1
7043:(
7040:=
7037:)
7034:f
7031:(
7028:w
7022:)
7019:4
7015:/
7011:1
7008:(
6982:,
6977:4
6973:)
6970:f
6967:(
6964:w
6958:+
6955:)
6946:f
6942:(
6939:w
6913:4
6909:/
6903:2
6899:)
6893:e
6889:f
6885:(
6880:e
6876:a
6870:E
6864:e
6856:+
6852:)
6846:e
6842:b
6831:e
6827:f
6823:+
6818:2
6814:)
6803:e
6799:f
6795:(
6790:e
6786:a
6780:E
6774:e
6765:(
6761:=
6736:e
6732:b
6718:e
6714:f
6708:E
6702:e
6694:+
6690:)
6685:)
6681:4
6677:/
6671:2
6667:)
6661:e
6657:f
6653:(
6650:+
6645:2
6641:)
6630:e
6626:f
6622:(
6618:(
6609:e
6605:a
6600:(
6594:E
6588:e
6577:)
6568:f
6564:(
6559:f
6555:w
6528:.
6523:e
6519:b
6508:e
6504:f
6498:E
6492:e
6484:+
6481:)
6471:e
6467:f
6461:e
6457:f
6451:e
6447:a
6443:(
6438:e
6430:=
6407:)
6402:e
6398:b
6394:+
6389:e
6385:f
6376:e
6372:a
6368:(
6358:e
6354:f
6348:E
6342:e
6334:=
6331:)
6322:f
6318:(
6313:f
6309:w
6279:f
6258:}
6255:)
6246:f
6242:(
6239:w
6236:{
6225:f
6213:)
6210:3
6206:/
6202:4
6199:(
6193:)
6190:f
6187:(
6184:w
6164:f
6138:3
6134:/
6130:4
6107:)
6104:L
6101:,
6098:G
6095:(
6064:0
6056:2
6052:)
6048:2
6044:/
6040:y
6034:x
6031:(
6005:4
6001:/
5995:2
5991:y
5987:+
5982:2
5978:x
5971:y
5965:x
5945:y
5925:x
5899:L
5871:f
5851:f
5825:f
5802:i
5798:t
5775:i
5771:s
5750:f
5724:f
5700:.
5697:)
5692:e
5688:f
5684:(
5679:e
5675:l
5669:q
5663:e
5652:)
5647:e
5643:f
5639:(
5634:e
5630:l
5624:p
5618:e
5588:q
5584:f
5570:q
5566:f
5543:p
5539:f
5525:p
5521:f
5498:i
5494:t
5471:i
5467:s
5446:q
5443:,
5440:p
5420:)
5415:i
5411:t
5407:,
5402:i
5398:s
5394:(
5371:.
5368:i
5358:i
5354:r
5350:=
5340:p
5336:f
5328:i
5324:t
5315:i
5311:s
5307::
5304:p
5296:=
5291:p
5287:f
5279:i
5275:t
5266:i
5262:s
5258::
5255:p
5227:R
5224:,
5195:f
5174:f
5162:.
5150:)
5145:e
5141:f
5137:(
5132:e
5128:l
5122:p
5116:e
5103:p
5099:f
5091:i
5087:t
5078:i
5074:s
5070::
5067:p
5057:k
5052:1
5049:=
5046:i
5035:)
5030:e
5026:f
5022:(
5017:e
5013:l
5007:p
5001:e
4983:p
4979:f
4971:i
4967:t
4958:i
4954:s
4950::
4947:p
4937:k
4932:1
4929:=
4926:i
4898:)
4895:f
4892:(
4887:f
4883:w
4876:)
4867:f
4863:(
4858:f
4854:w
4827:)
4818:f
4814:(
4809:f
4805:w
4798:)
4795:f
4792:(
4787:f
4783:w
4779:=
4776:)
4773:f
4770:(
4767:w
4741:f
4720:f
4693:)
4688:e
4684:f
4680:(
4675:e
4671:l
4657:e
4653:f
4646:E
4640:e
4632:=
4629:)
4620:f
4616:(
4611:f
4607:w
4583:f
4557:f
4532:f
4512:R
4472:G
4445:R
4442:,
4435:f
4412:R
4409:,
4402:f
4372:.
4368:)
4363:e
4359:f
4355:(
4350:e
4346:l
4339:q
4333:e
4321:)
4316:e
4312:f
4308:(
4303:e
4299:l
4292:p
4286:e
4275:0
4267:p
4263:f
4238:i
4234:t
4211:i
4207:s
4186:q
4183:,
4180:p
4151:)
4146:i
4142:t
4138:,
4133:i
4129:s
4125:(
4096:R
4093:,
4086:f
4059:R
4056:,
4031:e
4027:f
4003:.
3997:p
3993:f
3986:p
3980:e
3976::
3973:p
3965:=
3960:R
3957:,
3951:,
3948:e
3944:f
3920:G
3897:.
3888:)
3883:i
3879:t
3875:,
3870:i
3866:s
3862:(
3852:i
3848:r
3844:=
3838:p
3834:f
3825:i
3821:t
3812:i
3808:s
3803::
3800:p
3748:i
3744:t
3721:i
3717:s
3696:p
3667:p
3645:R
3642:,
3635:f
3611:)
3608:V
3602:V
3599:(
3593:}
3590:)
3585:k
3581:t
3577:,
3572:k
3568:s
3564:(
3561:,
3555:,
3552:)
3547:2
3543:t
3539:,
3534:2
3530:s
3526:(
3523:,
3520:)
3515:1
3511:t
3507:,
3502:1
3498:s
3494:(
3491:{
3488:=
3465:}
3462:0
3454:i
3450:r
3444:|
3439:,
3434:k
3430:r
3426:,
3420:,
3415:2
3411:r
3407:,
3402:1
3398:r
3394:{
3391:=
3388:R
3368:w
3348:L
3328:)
3325:E
3322:,
3319:V
3316:(
3313:=
3310:G
3272:=
3257:+
3222:=
3207:+
3181:=
3166:+
3130:=
3115:+
3076:=
3070:+
3035:=
3032:b
3029:=
3026:a
3003:=
3000:b
2997:+
2994:a
2971:+
2962:b
2939:b
2916:+
2907:a
2884:a
2832:)
2829:a
2826:(
2823:w
2803:)
2797:(
2794:w
2771:.
2762:j
2758:s
2751:j
2740:M
2732:i
2728:w
2721:i
2701:j
2697:s
2690:j
2677:i
2673:w
2666:i
2652:)
2649:a
2646:(
2643:w
2620:a
2597:.
2588:j
2584:s
2577:j
2564:i
2560:w
2553:i
2539:)
2533:(
2530:w
2481:M
2462:.
2450:a
2430:j
2410:j
2390:j
2370:k
2350:k
2330:j
2310:i
2283:M
2257:a
2224:3
2220:/
2216:4
2193:)
2190:2
2186:/
2182:1
2179:,
2176:2
2172:/
2168:1
2165:(
2162:=
2157:2
2149:=
2144:1
2119:1
2116:=
2111:2
2107:s
2103:=
2098:1
2094:s
2073:2
2070:=
2067:M
2047:1
2044:=
2039:2
2035:w
2031:=
2026:1
2022:w
2001:2
1998:=
1995:N
1979:.
1962:)
1959:a
1956:(
1951:j
1947:L
1941:j
1933:=
1930:)
1927:a
1924:(
1897:,
1894:)
1891:a
1888:(
1881:i
1877:a
1872:L
1868:=
1865:)
1862:a
1859:(
1854:i
1850:c
1829:i
1806:.
1799:j
1795:s
1788:i
1784:w
1778:j
1775:=
1770:i
1766:a
1762::
1759:i
1748:=
1745:)
1742:a
1739:(
1734:j
1730:L
1706:j
1682:.
1679:}
1676:M
1673:,
1667:,
1664:2
1661:,
1658:1
1655:{
1652:=
1647:i
1643:A
1614:N
1610:w
1606:,
1600:,
1595:1
1591:w
1562:M
1558:s
1554:,
1548:,
1543:1
1539:s
1514:M
1494:N
1459:5
1456:=
1453:2
1449:/
1442:=
1437:n
1434:i
1431:m
1427:C
1422:/
1416:l
1413:i
1410:u
1407:q
1404:e
1400:C
1379:2
1376:=
1373:1
1370:+
1367:1
1364:=
1359:n
1356:i
1353:m
1349:C
1325:=
1322:5
1319:+
1316:5
1313:=
1308:l
1305:i
1302:u
1299:q
1296:e
1292:C
1267:.
1264:)
1259:2
1255:s
1251:,
1246:1
1242:s
1238:(
1233:2
1229:u
1225:+
1222:)
1217:2
1213:s
1209:,
1204:1
1200:s
1196:(
1191:1
1187:u
1183:=
1180:)
1175:2
1171:s
1167:,
1162:1
1158:s
1154:(
1151:C
1136:5
1132:5
1127:7
1123:0
1113:0
1109:7
1104:1
1100:1
1051:A
1048:o
1045:P
1039:S
1036:o
1033:P
1027:1
1002:)
999:s
996:(
985:S
979:s
969:)
966:s
963:(
952:l
949:i
946:u
943:q
940:E
934:s
923:=
920:S
917:o
914:P
887:)
884:s
881:(
870:l
867:i
864:u
861:q
858:E
852:s
842:)
839:s
836:(
825:S
819:s
808:=
805:S
802:o
799:P
785:(
762:)
759:s
756:(
745:S
739:s
729:)
726:s
723:(
712:l
709:i
706:u
703:q
700:E
694:s
683:=
680:A
677:o
674:P
651:R
644:S
641::
613:)
610:s
607:(
596:l
593:i
590:u
587:q
584:E
578:s
568:)
565:s
562:(
551:S
545:s
534:=
531:A
528:o
525:P
499:S
493:l
490:i
487:u
484:q
481:E
458:,
455:)
452:s
449:(
444:i
440:u
434:N
428:i
420:=
417:)
414:s
411:(
385:,
382:)
379:s
376:(
371:i
367:u
361:N
355:i
347:=
344:)
341:s
338:(
311:R
304:S
301::
276:n
272:S
265:.
262:.
259:.
251:1
247:S
243:=
240:S
219:R
212:S
209::
204:i
200:u
177:i
173:S
152:N
132:)
129:u
126:,
123:S
120:,
117:N
114:(
111:=
108:G
20:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
