280:
140:
servers around the world that offer that service. A user prefers servers that are proximal enough to provide a faster response time for the requested service, resulting in a (partial) preferential ordering of the servers for each user. Each server prefers to serve users that it can with a lower cost, resulting in a (partial) preferential ordering of users for each server.
333:) each woman replies "maybe" if she is currently not engaged or if she prefers this man over her current provisional partner (in this case, she rejects her current provisional partner who becomes unengaged). The provisional nature of engagements preserves the right of an already-engaged woman to "trade up" (and, in the process, to "jilt" her until-then partner).
144:
that distribute much of the world's content and services solve this large and complex stable marriage problem between users and servers every tens of seconds to enable billions of users to be matched up with their respective servers that can provide the requested web pages, videos, or other services.
527:
allows the set of residents to include couples who must be assigned together, either to the same hospital or to a specific pair of hospitals chosen by the couple (e.g., a married couple want to ensure that they will stay together and not be stuck in programs that are far away from each other). The
195:
All three are stable, because instability requires both of the participants to be happier with an alternative match. Giving one group their first choices ensures that the matches are stable because they would be unhappy with any other proposed match. Giving everyone their second choice ensures that
139:
An important and large-scale application of stable marriage is in assigning users to servers in a large distributed
Internet service. Billions of users access web pages, videos, and other services on the Internet, requiring each user to be matched to one of (potentially) hundreds of thousands of
413:
for men, i.e., no coalition of men can coordinate a misrepresentation of their preferences such that all men in the coalition are strictly better-off. However, it is possible for some coalition to misrepresent their preferences such that some men are better-off and the other men retain the same
454:
In this case, the condition of stability is that no unmatched pair prefer each other to their situation in the matching (whether that situation is another partner or being unmatched). With this condition, a stable matching will still exist, and can still be found by the Gale–Shapley algorithm.
106:
women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of
123:
Algorithms for finding solutions to the stable marriage problem have applications in a variety of real-world situations, perhaps the best known of these being in the assignment of graduating medical students to their first hospital appointments. In 2012, the
322:) each woman replies "maybe" to her suitor she most prefers and "no" to all other suitors. She is then provisionally "engaged" to the suitor she most prefers so far, and that suitor is likewise provisionally engaged to her.
428:
The rural hospitals theorem concerns a more general variant of the stable matching problem, like that applying in the problem of matching doctors to positions at hospitals, differing in the following ways from the basic
506:– differs from the stable marriage problem in that a hospital can take multiple residents, or a college can take an incoming class of more than one student. Algorithms to solve the hospitals/residents problem can be
552:
problem is a generalization of matching problem, in which participants can be matched with different terms of contracts. An important special case of contracts is matching with flexible wages.
196:
any other match would be disliked by one of the parties. In general, the family of solutions to any instance of the stable marriage problem can be given the structure of a finite
409:
from the point of view of men (the proposing side), i.e., no man can get a better matching for himself by misrepresenting his preferences. Moreover, the GS algorithm is even
493:
is similar to the stable marriage problem, but differs in that all participants belong to a single pool (instead of being divided into equal numbers of "men" and "women").
251:
377:
797:; Gharan, Shayan Oveis; Weber, Robbie (2018). "A simply exponential upper bound on the maximum number of stable matchings". In Diakonikolas, Ilias; Kempe, David;
153:
545:
that has maximum weight. Maximum weighted matchings do not have to be stable, but in some applications a maximum weighted matching is better than a stable one.
397:
295:
proved that, for any equal number of men and women, it is always possible to solve the stable marriage problem and make all marriages stable. They presented an
170:
In general, there may be many different stable matchings. For example, suppose there are three men (A,B,C) and three women (X,Y,Z) which have preferences of:
414:
partner. The GS algorithm is non-truthful for the women (the reviewing side): each woman may be able to misrepresent her preferences and get a better match.
39:) is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a
329:) each unengaged man proposes to the most-preferred woman to whom he has not yet proposed (regardless of whether the woman is already engaged), and then
444:
The participants on one side of the matching (the hospitals) may have a numerical capacity, specifying the number of doctors they are willing to hire.
402:
Among all possible different stable matchings, it always yields the one that is best for all men among all stable matchings, and worst for all women.
111:
The existence of two classes that need to be paired with each other (heterosexual men and women in this example) distinguishes this problem from the
518:. This problem was solved, with an algorithm, in the same original paper by Gale and Shapley, in which the stable marriage problem was solved.
1074:
Huang, Chien-Chung (2006). "Cheating by men in the Gale-Shapley stable matching algorithm". In Azar, Yossi; Erlebach, Thomas (eds.).
125:
1448:
447:
The total number of participants on one side might not equal the total capacity to which they are to be matched on the other side.
1485:
1371:
977:
883:
680:"High Tech for a Higher Authority: The Placement of Graduating Rabbis from Hebrew Union College—Jewish Institute of Religion"
1259:
Stable
Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms
2389:
759:
2206:
1736:
1534:
1402:
511:
462:
The set of assigned doctors, and the number of filled positions in each hospital, are the same in all stable matchings.
653:
2557:
2025:
1844:
1427:
1272:
1144:
480:
441:
Each participant may only be willing to be matched to a subset of the participants on the other side of the matching.
1641:
947:
1243:
2115:
465:
Any hospital that has some empty positions in some stable matching, receives exactly the same set of doctors in
2567:
1985:
1651:
253:. In a stable marriage instance chosen to maximize the number of different stable matchings, this number is an
1824:
1076:
Algorithms - ESA 2006, 14th Annual
European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings
2166:
1579:
1554:
1031:
888:
1458:
1387:
952:
International
Conference on Informatics Education and Research for Knowledge-Circulating Society (ICKS 2008)
2516:
1942:
1691:
1681:
1616:
1312:
1731:
1711:
1453:
584:
165:
2562:
2450:
2201:
2171:
1829:
1666:
1661:
1363:
1348:
994:
303:
274:
2486:
2409:
2145:
1696:
1621:
1478:
844:
722:
624:
2572:
2501:
2234:
2120:
1917:
1706:
1524:
1197:
Crawford, Vincent; Knoer, Elsie Marie (1981). "Job
Matching with Heterogeneous Firms and Workers".
1162:
579:
489:
141:
112:
2304:
1305:"The evolution of the labor market for medical interns and residents: A case study in game theory"
214:
2506:
2105:
2075:
1726:
1514:
1449:
https://web.archive.org/web/20080512150525/http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP
1304:
561:
423:
1413:
2577:
2552:
2531:
2511:
2491:
2440:
2110:
2015:
1874:
1819:
1746:
1716:
1636:
1564:
679:
149:
346:
1990:
1975:
1544:
934:
564:– matching between different vertices of the graph; usually unrelated to preference-ordering.
200:, and this structure leads to efficient algorithms for several problems on stable marriages.
2324:
2309:
2196:
2191:
2095:
2080:
2045:
2010:
1604:
1549:
1471:
1091:
1060:
865:
828:
780:
743:
254:
197:
8:
2481:
2100:
2050:
1887:
1814:
1789:
1646:
1529:
2140:
1261:. CRM Proceedings and Lecture Notes. English translation. American Mathematical Society.
950:; Miyazaki, Shuichi (2008). "A Survey of the Stable Marriage Problem and Its Variants".
842:
Irving, Robert W.; Leather, Paul (1986). "The complexity of counting stable marriages".
2460:
2319:
2150:
2130:
1980:
1859:
1759:
1686:
1631:
1342:
1329:
1291:
1216:
1179:
1048:
905:
806:
612:
567:
537:
406:
382:
2445:
2414:
2369:
2264:
2135:
2090:
2065:
1995:
1869:
1794:
1784:
1676:
1626:
1574:
1423:
1398:
1367:
1140:
1026:
973:
699:
589:
523:
498:
306:(also known as the deferred acceptance algorithm) involves a number of "rounds" (or "
2526:
2521:
2455:
2419:
2399:
2359:
2329:
2284:
2239:
2224:
2181:
2035:
1809:
1671:
1608:
1594:
1559:
1333:
1321:
1281:
1208:
1171:
1079:
1040:
963:
955:
897:
853:
816:
798:
768:
731:
691:
649:
573:
458:
For this kind of stable matching problem, the rural hospitals theorem states that:
129:
28:
913:
340:
This algorithm is guaranteed to produce a stable marriage for all participants in
2424:
2384:
2339:
2254:
2249:
1970:
1922:
1804:
1569:
1539:
1509:
1443:
1247:
1087:
1078:. Lecture Notes in Computer Science. Vol. 4168. Springer. pp. 418–431.
1056:
861:
824:
776:
739:
542:
262:
2289:
2364:
2354:
2344:
2279:
2269:
2259:
2244:
2040:
2020:
2005:
2000:
1960:
1927:
1912:
1907:
1897:
1701:
341:
1379:
1286:
1267:
695:
43:
from the elements of one set to the elements of the other set. A matching is
2546:
2404:
2394:
2349:
2334:
2314:
2085:
2060:
1932:
1902:
1892:
1879:
1779:
1721:
1656:
1589:
1175:
1022:
926:
703:
292:
133:
820:
596:) – deciding when to stop to obtain the best reward in a sequence of options
91:) which both prefer each other to their current partner under the matching.
2379:
2374:
2229:
1799:
1254:
1199:
717:
528:
addition of couples to the hospitals/residents problem renders the problem
484:, some men might be indifferent between two or more women and vice versa.
136:"for the theory of stable allocations and the practice of market design."
2496:
2299:
2294:
2274:
2070:
2055:
1864:
1834:
1764:
1754:
1584:
1519:
1495:
1393:. In Nisan, Noam; Roughgarden, Tim; Tardos, Eva; Vazirani, Vijay (eds.).
1160:
Hatfield, John
William; Milgrom, Paul (2005). "Matching with Contracts".
794:
529:
83:
In other words, a matching is stable when there does not exist any pair (
20:
1463:
1359:
Multiagent
Systems: Algorithmic, Game-Theoretic, and Logical Foundations
1083:
959:
2125:
1774:
1295:
1241:
1220:
1183:
1106:
1052:
968:
909:
288:
1454:
http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html
720:(1987). "Three fast algorithms for four problems in stable marriage".
2030:
1950:
1769:
1419:
318:) each unengaged man proposes to the woman he prefers most, and then
307:
296:
40:
24:
1212:
1044:
901:
857:
803:
Proceedings of the 50th
Symposium on Theory of Computing (STOC 2018)
772:
735:
2465:
1965:
1344:
Two-sided matching: A study in game-theoretic modeling and analysis
1325:
811:
570:– a relaxation of stable matching for many-to-one matching problems
203:
In a uniformly-random instance of the stable marriage problem with
16:
Pairing where no unchosen pair prefers each other over their choice
2186:
2176:
1854:
261:. Counting the number of stable matchings in a given instance is
185:
men get their first choice and women their third - (AY, BZ, CX);
1357:
757:
Pittel, Boris (1989). "The average number of stable matchings".
647:
211:
women, the average number of stable matchings is asymptotically
191:
women get their first choice and men their third - (AZ, BX, CY).
450:
The resulting matching might not match all of the participants.
279:
181:
There are three stable solutions to this matching arrangement:
152:
for stable matching is used to assign rabbis who graduate from
1444:
Interactive flash demonstration of the stable marriage problem
1955:
1107:"Are Medical Students Meeting Their (Best Possible) Match?"
283:
Animation showing an example of the Gale–Shapley algorithm
56:
of the first matched set which prefers some given element
1240:, Chapter 1, pp 1–12. See companion website for the Text
805:. Association for Computing Machinery. pp. 920–925.
1385:
188:
all participants get their second choice - (AX, BY, CZ);
94:
The stable marriage problem has been stated as follows:
1029:(1981). "Machiavelli and the Gale–Shapley algorithm".
1415:
The Stable
Marriage Problem: Structure and Algorithms
1137:
The Stable
Marriage Problem: Structure and Algorithms
385:
349:
217:
60:
of the second matched set over the element to which
336:
This process is repeated until everyone is engaged.
1355:
1268:"On likely solutions of a stable marriage problem"
884:"College Admissions and the Stability of Marriage"
391:
371:
245:
940:
793:
2544:
1159:
1411:
1134:
1021:
1479:
1340:
1196:
946:
841:
159:
678:Bodin, Lawrence; Panken, Aaron (June 2003).
881:
677:
1486:
1472:
1356:Shoham, Yoav; Leyton-Brown, Kevin (2009).
1004:. University of Illinois. pp. 170–176
417:
1493:
1341:Roth, A. E.; Sotomayor, M. A. O. (1990).
1285:
967:
810:
661:ACM SIGCOMM Computer Communication Review
654:"Algorithmic nuggets in content delivery"
643:
641:
174:A: YXZ B: ZYX C: XZY
126:Nobel Memorial Prize in Economic Sciences
1104:
1098:
992:
716:
524:hospitals/residents problem with couples
278:
541:seeks to find a matching in a weighted
268:
2545:
1265:
877:
875:
756:
638:
1467:
1459:Stable marriage problem lecture notes
1253:
1236:Kleinberg, J., and Tardos, E. (2005)
1073:
625:"The Prize in Economic Sciences 2012"
437:form of the stable marriage problem:
1302:
1135:Gusfield, D.; Irving, R. W. (1989).
760:SIAM Journal on Discrete Mathematics
1412:Gusfield, D.; Irving, R.W. (1989).
1386:Schummer, J.; Vohra, R. V. (2007).
872:
473:
13:
1535:First-player and second-player win
1230:
177:X: BAC Y: CBA Z: ACB
14:
2589:
1437:
1273:The Annals of Applied Probability
929:: "The Stable Marriage Problem",
882:Gale, D.; Shapley, L. S. (1962).
481:stable matching with indifference
1642:Coalition-proof Nash equilibrium
1388:"Mechanism design without money"
325:In each subsequent round, first
1190:
1153:
1128:
1067:
1015:
986:
920:
399:is the number of men or women.
118:
1652:Evolutionarily stable strategy
835:
787:
750:
710:
671:
617:
606:
366:
353:
1:
1580:Simultaneous action selection
1105:Robinson, Sara (April 2003).
1032:American Mathematical Monthly
889:American Mathematical Monthly
600:
2517:List of games in game theory
1692:Quantal response equilibrium
1682:Perfect Bayesian equilibrium
1617:Bayes correlated equilibrium
1313:Journal of Political Economy
993:Erickson, Jeff (June 2019).
246:{\displaystyle e^{-1}n\ln n}
7:
1986:Optional prisoner's dilemma
1712:Self-confirming equilibrium
585:Lattice of stable matchings
555:
499:hospitals/residents problem
166:Lattice of stable matchings
107:marriages is deemed stable.
10:
2594:
2451:Principal variation search
2167:Aumann's agreement theorem
1830:Strategy-stealing argument
1737:Trembling hand equilibrium
1667:Markov perfect equilibrium
1662:Mertens-stable equilibrium
1364:Cambridge University Press
1349:Cambridge University Press
954:. IEEE. pp. 131–136.
613:Stable Matching Algorithms
504:college admissions problem
421:
314:In the first round, first
272:
163:
160:Different stable matchings
74:over the element to which
2487:Combinatorial game theory
2474:
2433:
2215:
2159:
2146:Princess and monster game
1941:
1843:
1745:
1697:Quasi-perfect equilibrium
1622:Bayesian Nash equilibrium
1603:
1502:
1139:. MIT Press. p. 54.
845:SIAM Journal on Computing
723:SIAM Journal on Computing
696:10.1287/inte.33.3.1.16013
156:to Jewish congregations.
142:Content delivery networks
2558:Game theory game classes
2502:Evolutionary game theory
2235:Antoine Augustin Cournot
2121:Guess 2/3 of the average
1918:Strictly determined game
1707:Satisfaction equilibrium
1525:Escalation of commitment
1380:downloadable free online
1176:10.1257/0002828054825466
1163:American Economic Review
580:Stable matching polytope
490:stable roommates problem
372:{\displaystyle O(n^{2})}
113:stable roommates problem
2507:Glossary of game theory
2106:Stackelberg competition
1727:Strong Nash equilibrium
1395:Algorithmic Game Theory
1287:10.1214/aoap/1177005708
821:10.1145/3188745.3188848
576:for edge colored graphs
562:Matching (graph theory)
550:matching with contracts
424:Rural hospitals theorem
418:Rural hospitals theorem
64:is already matched, and
37:stable matching problem
33:stable marriage problem
2532:Tragedy of the commons
2512:List of game theorists
2492:Confrontation analysis
2202:Sprague–Grundy theorem
1717:Sequential equilibrium
1637:Correlated equilibrium
916:on September 25, 2017.
393:
373:
304:Gale–Shapley algorithm
284:
275:Gale–Shapley algorithm
247:
150:Gale-Shapley algorithm
109:
2568:Mathematical problems
2305:Jean-François Mertens
995:"4.5 Stable matching"
394:
374:
282:
248:
96:
2434:Search optimizations
2310:Jennifer Tour Chayes
2197:Revelation principle
2192:Purification theorem
2131:Nash bargaining game
2096:Bertrand competition
2081:El Farol Bar problem
2046:Electronic mail game
2011:Lewis signaling game
1550:Hierarchy of beliefs
1397:. pp. 255–262.
1378:See Section 10.6.4;
1303:Roth, A. E. (1984).
514:was before 1995) or
502:– also known as the
411:group-strategy proof
383:
347:
269:Algorithmic solution
255:exponential function
215:
198:distributive lattice
154:Hebrew Union College
52:There is an element
2482:Bounded rationality
2101:Cournot competition
2051:Rock paper scissors
2026:Battle of the sexes
2016:Volunteer's dilemma
1888:Perfect information
1815:Dominant strategies
1647:Epsilon-equilibrium
1530:Extensive-form game
1266:Pittel, B. (1992).
1084:10.1007/11841036_39
960:10.1109/ICKS.2008.7
931:The Brandeis Review
78:is already matched.
2461:Paranoid algorithm
2441:Alpha–beta pruning
2320:John Maynard Smith
2151:Rendezvous problem
1991:Traveler's dilemma
1981:Gift-exchange game
1976:Prisoner's dilemma
1893:Large Poisson game
1860:Bargaining problem
1760:Backward induction
1732:Subgame perfection
1687:Proper equilibrium
1246:2011-05-14 at the
568:Envy-free matching
538:assignment problem
407:truthful mechanism
389:
369:
285:
243:
2563:Cooperative games
2540:
2539:
2446:Aspiration window
2415:Suzanne Scotchmer
2370:Oskar Morgenstern
2265:Donald B. Gillies
2207:Zermelo's theorem
2136:Induction puzzles
2091:Fair cake-cutting
2066:Public goods game
1996:Coordination game
1870:Intransitive game
1795:Forward induction
1677:Pareto efficiency
1657:Gibbs equilibrium
1627:Berge equilibrium
1575:Simultaneous game
1373:978-0-521-89943-7
979:978-0-7695-3128-1
799:Henzinger, Monika
590:Secretary problem
516:resident-oriented
508:hospital-oriented
469:stable matchings.
392:{\displaystyle n}
2585:
2527:Topological game
2522:No-win situation
2420:Thomas Schelling
2400:Robert B. Wilson
2360:Merrill M. Flood
2330:John von Neumann
2240:Ariel Rubinstein
2225:Albert W. Tucker
2076:War of attrition
2036:Matching pennies
1810:Pairing strategy
1672:Nash equilibrium
1595:Mechanism design
1560:Normal-form game
1515:Cooperative game
1488:
1481:
1474:
1465:
1464:
1433:
1408:
1392:
1377:
1352:
1337:
1309:
1299:
1289:
1262:
1238:Algorithm Design
1225:
1224:
1194:
1188:
1187:
1157:
1151:
1150:
1132:
1126:
1125:
1123:
1121:
1111:
1102:
1096:
1095:
1071:
1065:
1064:
1019:
1013:
1012:
1010:
1009:
999:
990:
984:
983:
971:
944:
938:
924:
918:
917:
912:. Archived from
879:
870:
869:
839:
833:
832:
814:
791:
785:
784:
754:
748:
747:
714:
708:
707:
675:
669:
668:
658:
650:Ramesh Sitaraman
648:Bruce Maggs and
645:
636:
635:
633:
632:
627:. Nobelprize.org
621:
615:
610:
594:marriage problem
574:Rainbow matching
474:Related problems
436:
432:
398:
396:
395:
390:
378:
376:
375:
370:
365:
364:
260:
252:
250:
249:
244:
230:
229:
210:
206:
130:Lloyd S. Shapley
29:computer science
2593:
2592:
2588:
2587:
2586:
2584:
2583:
2582:
2573:Stable matching
2543:
2542:
2541:
2536:
2470:
2456:max^n algorithm
2429:
2425:William Vickrey
2385:Reinhard Selten
2340:Kenneth Binmore
2255:David K. Levine
2250:Daniel Kahneman
2217:
2211:
2187:Negamax theorem
2177:Minimax theorem
2155:
2116:Diner's dilemma
1971:All-pay auction
1937:
1923:Stochastic game
1875:Mean-field game
1846:
1839:
1805:Markov strategy
1741:
1607:
1599:
1570:Sequential game
1555:Information set
1540:Game complexity
1510:Congestion game
1498:
1492:
1440:
1430:
1405:
1390:
1374:
1320:(6): 991–1016.
1307:
1248:Wayback Machine
1233:
1231:Further reading
1228:
1213:10.2307/1913320
1195:
1191:
1158:
1154:
1147:
1133:
1129:
1119:
1117:
1109:
1103:
1099:
1072:
1068:
1045:10.2307/2321753
1027:Freedman, D. A.
1020:
1016:
1007:
1005:
997:
991:
987:
980:
945:
941:
925:
921:
902:10.2307/2312726
880:
873:
858:10.1137/0215048
840:
836:
795:Karlin, Anna R.
792:
788:
773:10.1137/0402048
755:
751:
736:10.1137/0216010
715:
711:
676:
672:
656:
646:
639:
630:
628:
623:
622:
618:
611:
607:
603:
558:
543:bipartite graph
476:
434:
430:
426:
420:
384:
381:
380:
360:
356:
348:
345:
344:
277:
271:
258:
222:
218:
216:
213:
212:
208:
204:
168:
162:
128:was awarded to
121:
81:
17:
12:
11:
5:
2591:
2581:
2580:
2575:
2570:
2565:
2560:
2555:
2538:
2537:
2535:
2534:
2529:
2524:
2519:
2514:
2509:
2504:
2499:
2494:
2489:
2484:
2478:
2476:
2472:
2471:
2469:
2468:
2463:
2458:
2453:
2448:
2443:
2437:
2435:
2431:
2430:
2428:
2427:
2422:
2417:
2412:
2407:
2402:
2397:
2392:
2390:Robert Axelrod
2387:
2382:
2377:
2372:
2367:
2365:Olga Bondareva
2362:
2357:
2355:Melvin Dresher
2352:
2347:
2345:Leonid Hurwicz
2342:
2337:
2332:
2327:
2322:
2317:
2312:
2307:
2302:
2297:
2292:
2287:
2282:
2280:Harold W. Kuhn
2277:
2272:
2270:Drew Fudenberg
2267:
2262:
2260:David M. Kreps
2257:
2252:
2247:
2245:Claude Shannon
2242:
2237:
2232:
2227:
2221:
2219:
2213:
2212:
2210:
2209:
2204:
2199:
2194:
2189:
2184:
2182:Nash's theorem
2179:
2174:
2169:
2163:
2161:
2157:
2156:
2154:
2153:
2148:
2143:
2138:
2133:
2128:
2123:
2118:
2113:
2108:
2103:
2098:
2093:
2088:
2083:
2078:
2073:
2068:
2063:
2058:
2053:
2048:
2043:
2041:Ultimatum game
2038:
2033:
2028:
2023:
2021:Dollar auction
2018:
2013:
2008:
2006:Centipede game
2003:
1998:
1993:
1988:
1983:
1978:
1973:
1968:
1963:
1961:Infinite chess
1958:
1953:
1947:
1945:
1939:
1938:
1936:
1935:
1930:
1928:Symmetric game
1925:
1920:
1915:
1913:Signaling game
1910:
1908:Screening game
1905:
1900:
1898:Potential game
1895:
1890:
1885:
1877:
1872:
1867:
1862:
1857:
1851:
1849:
1841:
1840:
1838:
1837:
1832:
1827:
1825:Mixed strategy
1822:
1817:
1812:
1807:
1802:
1797:
1792:
1787:
1782:
1777:
1772:
1767:
1762:
1757:
1751:
1749:
1743:
1742:
1740:
1739:
1734:
1729:
1724:
1719:
1714:
1709:
1704:
1702:Risk dominance
1699:
1694:
1689:
1684:
1679:
1674:
1669:
1664:
1659:
1654:
1649:
1644:
1639:
1634:
1629:
1624:
1619:
1613:
1611:
1601:
1600:
1598:
1597:
1592:
1587:
1582:
1577:
1572:
1567:
1562:
1557:
1552:
1547:
1545:Graphical game
1542:
1537:
1532:
1527:
1522:
1517:
1512:
1506:
1504:
1500:
1499:
1491:
1490:
1483:
1476:
1468:
1462:
1461:
1456:
1451:
1446:
1439:
1438:External links
1436:
1435:
1434:
1428:
1409:
1404:978-0521872829
1403:
1383:
1372:
1353:
1338:
1326:10.1086/261272
1300:
1280:(2): 358–401.
1263:
1251:
1232:
1229:
1227:
1226:
1207:(2): 437–450.
1189:
1170:(4): 913–935.
1152:
1145:
1127:
1097:
1066:
1039:(7): 485–494.
1014:
985:
978:
939:
919:
871:
852:(3): 655–667.
834:
786:
767:(4): 530–549.
749:
730:(1): 111–128.
709:
670:
637:
616:
604:
602:
599:
598:
597:
587:
582:
577:
571:
565:
557:
554:
475:
472:
471:
470:
463:
452:
451:
448:
445:
442:
422:Main article:
419:
416:
388:
368:
363:
359:
355:
352:
338:
337:
334:
323:
273:Main article:
270:
267:
242:
239:
236:
233:
228:
225:
221:
193:
192:
189:
186:
179:
178:
175:
164:Main article:
161:
158:
120:
117:
80:
79:
65:
49:
15:
9:
6:
4:
3:
2:
2590:
2579:
2578:Lloyd Shapley
2576:
2574:
2571:
2569:
2566:
2564:
2561:
2559:
2556:
2554:
2553:Combinatorics
2551:
2550:
2548:
2533:
2530:
2528:
2525:
2523:
2520:
2518:
2515:
2513:
2510:
2508:
2505:
2503:
2500:
2498:
2495:
2493:
2490:
2488:
2485:
2483:
2480:
2479:
2477:
2475:Miscellaneous
2473:
2467:
2464:
2462:
2459:
2457:
2454:
2452:
2449:
2447:
2444:
2442:
2439:
2438:
2436:
2432:
2426:
2423:
2421:
2418:
2416:
2413:
2411:
2410:Samuel Bowles
2408:
2406:
2405:Roger Myerson
2403:
2401:
2398:
2396:
2395:Robert Aumann
2393:
2391:
2388:
2386:
2383:
2381:
2378:
2376:
2373:
2371:
2368:
2366:
2363:
2361:
2358:
2356:
2353:
2351:
2350:Lloyd Shapley
2348:
2346:
2343:
2341:
2338:
2336:
2335:Kenneth Arrow
2333:
2331:
2328:
2326:
2323:
2321:
2318:
2316:
2315:John Harsanyi
2313:
2311:
2308:
2306:
2303:
2301:
2298:
2296:
2293:
2291:
2288:
2286:
2285:Herbert Simon
2283:
2281:
2278:
2276:
2273:
2271:
2268:
2266:
2263:
2261:
2258:
2256:
2253:
2251:
2248:
2246:
2243:
2241:
2238:
2236:
2233:
2231:
2228:
2226:
2223:
2222:
2220:
2214:
2208:
2205:
2203:
2200:
2198:
2195:
2193:
2190:
2188:
2185:
2183:
2180:
2178:
2175:
2173:
2170:
2168:
2165:
2164:
2162:
2158:
2152:
2149:
2147:
2144:
2142:
2139:
2137:
2134:
2132:
2129:
2127:
2124:
2122:
2119:
2117:
2114:
2112:
2109:
2107:
2104:
2102:
2099:
2097:
2094:
2092:
2089:
2087:
2086:Fair division
2084:
2082:
2079:
2077:
2074:
2072:
2069:
2067:
2064:
2062:
2061:Dictator game
2059:
2057:
2054:
2052:
2049:
2047:
2044:
2042:
2039:
2037:
2034:
2032:
2029:
2027:
2024:
2022:
2019:
2017:
2014:
2012:
2009:
2007:
2004:
2002:
1999:
1997:
1994:
1992:
1989:
1987:
1984:
1982:
1979:
1977:
1974:
1972:
1969:
1967:
1964:
1962:
1959:
1957:
1954:
1952:
1949:
1948:
1946:
1944:
1940:
1934:
1933:Zero-sum game
1931:
1929:
1926:
1924:
1921:
1919:
1916:
1914:
1911:
1909:
1906:
1904:
1903:Repeated game
1901:
1899:
1896:
1894:
1891:
1889:
1886:
1884:
1882:
1878:
1876:
1873:
1871:
1868:
1866:
1863:
1861:
1858:
1856:
1853:
1852:
1850:
1848:
1842:
1836:
1833:
1831:
1828:
1826:
1823:
1821:
1820:Pure strategy
1818:
1816:
1813:
1811:
1808:
1806:
1803:
1801:
1798:
1796:
1793:
1791:
1788:
1786:
1783:
1781:
1780:De-escalation
1778:
1776:
1773:
1771:
1768:
1766:
1763:
1761:
1758:
1756:
1753:
1752:
1750:
1748:
1744:
1738:
1735:
1733:
1730:
1728:
1725:
1723:
1722:Shapley value
1720:
1718:
1715:
1713:
1710:
1708:
1705:
1703:
1700:
1698:
1695:
1693:
1690:
1688:
1685:
1683:
1680:
1678:
1675:
1673:
1670:
1668:
1665:
1663:
1660:
1658:
1655:
1653:
1650:
1648:
1645:
1643:
1640:
1638:
1635:
1633:
1630:
1628:
1625:
1623:
1620:
1618:
1615:
1614:
1612:
1610:
1606:
1602:
1596:
1593:
1591:
1590:Succinct game
1588:
1586:
1583:
1581:
1578:
1576:
1573:
1571:
1568:
1566:
1563:
1561:
1558:
1556:
1553:
1551:
1548:
1546:
1543:
1541:
1538:
1536:
1533:
1531:
1528:
1526:
1523:
1521:
1518:
1516:
1513:
1511:
1508:
1507:
1505:
1501:
1497:
1489:
1484:
1482:
1477:
1475:
1470:
1469:
1466:
1460:
1457:
1455:
1452:
1450:
1447:
1445:
1442:
1441:
1431:
1429:0-262-07118-5
1425:
1421:
1417:
1416:
1410:
1406:
1400:
1396:
1389:
1384:
1381:
1375:
1369:
1365:
1361:
1360:
1354:
1350:
1346:
1345:
1339:
1335:
1331:
1327:
1323:
1319:
1315:
1314:
1306:
1301:
1297:
1293:
1288:
1283:
1279:
1275:
1274:
1269:
1264:
1260:
1256:
1252:
1249:
1245:
1242:
1239:
1235:
1234:
1222:
1218:
1214:
1210:
1206:
1202:
1201:
1193:
1185:
1181:
1177:
1173:
1169:
1165:
1164:
1156:
1148:
1146:0-262-07118-5
1142:
1138:
1131:
1115:
1108:
1101:
1093:
1089:
1085:
1081:
1077:
1070:
1062:
1058:
1054:
1050:
1046:
1042:
1038:
1034:
1033:
1028:
1024:
1023:Dubins, L. E.
1018:
1003:
996:
989:
981:
975:
970:
965:
961:
957:
953:
949:
943:
936:
932:
928:
927:Harry Mairson
923:
915:
911:
907:
903:
899:
895:
891:
890:
885:
878:
876:
867:
863:
859:
855:
851:
847:
846:
838:
830:
826:
822:
818:
813:
808:
804:
800:
796:
790:
782:
778:
774:
770:
766:
762:
761:
753:
745:
741:
737:
733:
729:
725:
724:
719:
718:Gusfield, Dan
713:
705:
701:
697:
693:
689:
685:
681:
674:
666:
662:
655:
651:
644:
642:
626:
620:
614:
609:
605:
595:
592:(also called
591:
588:
586:
583:
581:
578:
575:
572:
569:
566:
563:
560:
559:
553:
551:
546:
544:
540:
539:
533:
531:
526:
525:
519:
517:
513:
509:
505:
501:
500:
494:
492:
491:
485:
483:
482:
468:
464:
461:
460:
459:
456:
449:
446:
443:
440:
439:
438:
425:
415:
412:
408:
403:
400:
386:
361:
357:
350:
343:
335:
332:
328:
324:
321:
317:
313:
312:
311:
309:
305:
300:
298:
294:
293:Lloyd Shapley
290:
281:
276:
266:
264:
256:
240:
237:
234:
231:
226:
223:
219:
201:
199:
190:
187:
184:
183:
182:
176:
173:
172:
171:
167:
157:
155:
151:
146:
143:
137:
135:
134:Alvin E. Roth
131:
127:
116:
114:
108:
105:
101:
95:
92:
90:
86:
77:
73:
70:also prefers
69:
66:
63:
59:
55:
51:
50:
48:
46:
42:
38:
34:
30:
26:
22:
2380:Peyton Young
2375:Paul Milgrom
2290:Hervé Moulin
2230:Amos Tversky
2172:Folk theorem
1883:-player game
1880:
1800:Grim trigger
1414:
1394:
1362:. New York:
1358:
1343:
1317:
1311:
1277:
1271:
1258:
1255:Knuth, D. E.
1237:
1204:
1200:Econometrica
1198:
1192:
1167:
1161:
1155:
1136:
1130:
1118:. Retrieved
1113:
1100:
1075:
1069:
1036:
1030:
1017:
1006:. Retrieved
1001:
988:
951:
948:Iwama, Kazuo
942:
930:
922:
914:the original
893:
887:
849:
843:
837:
802:
789:
764:
758:
752:
727:
721:
712:
687:
683:
673:
664:
660:
629:. Retrieved
619:
608:
593:
549:
547:
536:
534:
522:
520:
515:
507:
503:
497:
495:
488:
486:
479:
477:
466:
457:
453:
427:
410:
404:
401:
339:
330:
326:
319:
315:
301:
286:
202:
194:
180:
169:
147:
138:
122:
119:Applications
110:
103:
99:
97:
93:
88:
84:
82:
75:
71:
67:
61:
57:
53:
44:
36:
32:
18:
2497:Coopetition
2300:Jean Tirole
2295:John Conway
2275:Eric Maskin
2071:Blotto game
2056:Pirate game
1865:Global game
1835:Tit for tat
1765:Bid shading
1755:Appeasement
1605:Equilibrium
1585:Solved game
1520:Determinacy
1503:Definitions
1496:game theory
969:2433/226940
896:(1): 9–14.
690:(3): 1–11.
530:NP-complete
263:#P-complete
47:stable if:
21:mathematics
2547:Categories
2141:Trust game
2126:Kuhn poker
1790:Escalation
1785:Deterrence
1775:Cheap talk
1747:Strategies
1565:Preference
1494:Topics of
1008:2023-12-19
1002:Algorithms
933:12, 1992 (
812:1711.01032
684:Interfaces
631:2013-09-09
601:References
308:iterations
299:to do so.
289:David Gale
2325:John Nash
2031:Stag hunt
1770:Collusion
1420:MIT Press
1120:2 January
1114:SIAM News
704:0092-2102
297:algorithm
287:In 1962,
238:
224:−
41:bijection
25:economics
2466:Lazy SMP
2160:Theorems
2111:Deadlock
1966:Checkers
1847:of games
1609:concepts
1257:(1996).
1244:Archived
801:(eds.).
652:(2015).
556:See also
510:(as the
405:It is a
207:men and
102:men and
2218:figures
2001:Chicken
1855:Auction
1845:Classes
1334:1360205
1296:2959755
1221:1913320
1184:4132699
1116:(3): 36
1092:2347162
1061:0628016
1053:2321753
910:2312726
866:0850415
829:3826305
781:1018538
744:0873255
1426:
1401:
1370:
1332:
1294:
1219:
1182:
1143:
1090:
1059:
1051:
976:
935:online
908:
864:
827:
779:
742:
702:
379:where
98:Given
35:(also
31:, the
27:, and
1956:Chess
1943:Games
1391:(PDF)
1330:S2CID
1308:(PDF)
1292:JSTOR
1217:JSTOR
1180:JSTOR
1110:(PDF)
1049:JSTOR
998:(PDF)
906:JSTOR
807:arXiv
657:(PDF)
1632:Core
1424:ISBN
1399:ISBN
1368:ISBN
1141:ISBN
1122:2018
974:ISBN
700:ISSN
667:(3).
548:The
535:The
521:The
512:NRMP
496:The
487:The
433:-to-
342:time
310:"):
302:The
291:and
148:The
132:and
2216:Key
1322:doi
1282:doi
1209:doi
1172:doi
1080:doi
1041:doi
964:hdl
956:doi
898:doi
854:doi
817:doi
769:doi
732:doi
692:doi
478:In
467:all
257:of
45:not
19:In
2549::
1951:Go
1422:.
1418:.
1366:.
1347:.
1328:.
1318:92
1316:.
1310:.
1290:.
1276:.
1270:.
1215:.
1205:49
1203:.
1178:.
1168:95
1166:.
1112:.
1088:MR
1086:.
1057:MR
1055:.
1047:.
1037:88
1035:.
1025:;
1000:.
972:.
962:.
937:).
904:.
894:69
892:.
886:.
874:^
862:MR
860:.
850:15
848:.
825:MR
823:.
815:.
777:MR
775:.
763:.
740:MR
738:.
728:16
726:.
698:.
688:33
686:.
682:.
665:45
663:.
659:.
640:^
532:.
265:.
235:ln
115:.
87:,
23:,
1881:n
1487:e
1480:t
1473:v
1432:.
1407:.
1382:.
1376:.
1351:.
1336:.
1324::
1298:.
1284::
1278:2
1250:.
1223:.
1211::
1186:.
1174::
1149:.
1124:.
1094:.
1082::
1063:.
1043::
1011:.
982:.
966::
958::
900::
868:.
856::
831:.
819::
809::
783:.
771::
765:2
746:.
734::
706:.
694::
634:.
435:n
431:n
387:n
367:)
362:2
358:n
354:(
351:O
331:b
327:a
320:b
316:a
259:n
241:n
232:n
227:1
220:e
209:n
205:n
104:n
100:n
89:B
85:A
76:B
72:A
68:B
62:A
58:B
54:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
