183:. Each participant orders the other members by preference, resulting in a preference list—an ordered set of the other participants. Participants then propose to each person on their list, in order, continuing to the next person if and when their current proposal is rejected. A participant will reject a proposal if they already hold a proposal from someone they prefer. A participant will also reject a previously-accepted proposal if they later receive a proposal that they prefer. In this case, the rejected participant will then propose to the next person on their list, continuing until a proposal is again accepted. If any participant is eventually rejected by all other participants, this indicates that no stable matching is possible. Otherwise, Phase 1 will end with each person holding a proposal from one of the others.
916:. After the elimination of a rotation, we continue to store only its tail, if any, in the list and as visited in the array, and start the search for the next rotation at the last individual on the tail, and otherwise at the next unmatched individual if there is no tail. This reduces repeated traversal of the tail, since it is largely unaffected by the elimination of the rotation.
898:) time. With the ranking matrix, checking whether an individual prefers one to another can be done in constant time by comparing their ranks in the matrix. Furthermore, instead of explicitly removing elements from the preference lists, the indices of the first, second and last on each individual's reduced list are maintained. The first individual that is
608:
is removed from their lists. If a reduced list becomes empty during these removals, then there is no stable matching. Otherwise, the new table is again a stable table, and either already specifies a matching since each list contains exactly one individual or there remains another rotation to find and
147:
be paired with D and the other two with each other (for example AD and BC), yet for anyone who is partnered with D, another member will have rated them highest, and D's partner will in turn prefer this other member over D. In this example, AC is a more favorable pairing than AD, but the necessary
267:. A stable table, by definition, is the set of preference lists from the original table after members have been removed from one or more of the lists, and the following three conditions are satisfied (where reduced list means a list in the stable table):
262:
cannot be partners in any stable matching. The resulting reduced set of preference lists together is called the Phase 1 table. In this table, if any reduced list is empty, then there is no stable matching. Otherwise, the Phase 1 table is a
467:'s reduced list, for i = 0, ..., k-1 where the indices are taken modulo k. It follows that in any stable table with a reduced list containing at least two individuals, such a rotation always exists. To find it, start at such a
340:
Any stable table must be a subtable of the Phase 1 table, where subtable is a table where the preference lists of the subtable are those of the supertable with some individuals removed from each other's
160:) is the following. The algorithm will determine, for any instance of the problem, whether a stable matching exists, and if so, will find such a matching. Irving's algorithm has
1995:
119:, a stable matching may fail to exist for certain sets of participants and their preferences. For a minimal example of a stable pairing not existing, consider 4 people
354:
Any stable subtable of a stable table, and in particular any stable subtable that specifies a stable matching as in 2, can be obtained by a sequence of
63:
if there are no two elements which are not roommates and which both prefer each other to their roommate under the matching. This is distinct from the
1976:: The "Dyad Finder" website provides a free, web-based implementation of the algorithm, including source code for the website and solver written in
1954:: A constraint programming model to find all stable matchings in the roommates problem with incomplete lists is available under the CRAPL licence.
148:
remaining pairing of BD then raises the same issue, illustrating the absence of a stable matching for these participants and their preferences.
168:, provided suitable data structures are used to implement the necessary manipulation of the preference lists and identification of rotations.
351:
If the stable roommates problem instance has a stable matching, then there is a stable matching contained in any one of the stable tables.
909:"traversed" to find a rotation is stored in a list, and an array is used to mark individuals as having been visited, as in a standard
1991:
2338:
2081:
1271:= (1,4), (3,2) is first identified. This is because 2 is 1's second favorite, and 4 is the second favorite of 3. Eliminating
67:
in that the stable-roommates problem allows matches between any two elements, not just between classes of "men" and "women".
1096:
So Phase 1 ends with the following reduced preference lists: (for example we cross out 5 for 1: because 1: gets at least 6)
3242:
2249:
Fleiner, Tamás; Irving, Robert W.; Manlove, David F. (2007), "An efficient algorithm for the "stable roommates" problem",
3059:
2589:
2387:
2878:
2697:
1967:
1060:
A possible execution of Phase 1 consists of the following sequence of proposals and rejections, where → represents
2494:
2116:
924:
The following are the preference lists for a Stable
Roommates instance involving 6 participants: 1, 2, 3, 4, 5, 6.
143:
In this ranking, each of A, B, and C is the most preferable person for someone. In any solution, one of A, B, or C
2968:
3425:
2838:
2504:
2677:
3019:
2432:
2407:
2058:
1983:
1941:
365:
By 2, if each reduced list of the Phase 1 table contains exactly one individual, then this gives a matching.
3369:
2795:
2544:
2534:
2469:
336:
Stable tables have several important properties, which are used to justify the remainder of the procedure:
348:
one individual, then pairing each individual with the single person on their list gives a stable matching.
2584:
2564:
1951:
3415:
3303:
3054:
3024:
2682:
2519:
2514:
2193:
2137:
509:, at which point a rotation is found: it is the sequence of pairs starting at the first occurrence of (
902:, i.e. has at least two in their reduced lists, is also maintained. Then, in Phase 2, the sequence of
3339:
3262:
2998:
2549:
2474:
2331:
2301:
541:
of the rotation. The fact that it's a stable table in which this search occurs guarantees that each
3420:
3354:
3087:
2973:
2770:
2559:
2377:
1957:
3157:
3359:
2958:
2928:
2579:
2367:
180:
116:
64:
56:
3405:
3384:
3364:
3344:
3293:
2963:
2868:
2727:
2672:
2599:
2569:
2489:
2417:
2296:
176:
2843:
2828:
2397:
1970:: The MatchingTools API provides a free application programming interface for the algorithm.
3410:
3177:
3162:
3049:
3044:
2948:
2933:
2898:
2863:
2457:
2402:
2324:
2029:
8:
3334:
2953:
2903:
2740:
2667:
2642:
2499:
2382:
2993:
2097:
2033:
3313:
3172:
3003:
2983:
2833:
2712:
2612:
2539:
2484:
2222:
Irving, Robert W. (1985), "An efficient algorithm for the "stable roommates" problem",
910:
3298:
3267:
3222:
3117:
2988:
2943:
2918:
2848:
2722:
2647:
2637:
2529:
2479:
2427:
2235:
2077:
78:
participants ranks the others in strict order of preference. A matching is a set of
3379:
3374:
3308:
3272:
3252:
3212:
3182:
3137:
3092:
3077:
3034:
2888:
2662:
2524:
2461:
2447:
2412:
2306:
2258:
2231:
2069:
2037:
28:
474:
containing at least two individuals in their reduced list, and define recursively
3277:
3237:
3192:
3107:
3102:
2823:
2775:
2657:
2422:
2392:
2362:
1973:
913:
3142:
2073:
3217:
3207:
3197:
3132:
3122:
3112:
3097:
2893:
2873:
2858:
2853:
2813:
2780:
2765:
2760:
2750:
2554:
161:
2263:
59:
is a separation of the set into disjoint pairs ("roommates"). The matching is
3399:
3257:
3247:
3202:
3187:
3167:
2938:
2913:
2785:
2755:
2745:
2732:
2632:
2574:
2509:
2442:
32:
3232:
3227:
3082:
2652:
2310:
1960:: The same constraint programming model is also available as part of the R
3349:
3152:
3147:
3127:
2923:
2908:
2717:
2687:
2617:
2607:
2437:
2372:
2348:
2281:
36:
20:
2316:
2042:
2017:
2978:
2627:
1977:
40:
1944:: An implementation of Irving's algorithm is available as part of the
2883:
2803:
2622:
2068:. Lecture Notes in Computer Science. Vol. 8451. pp. 15–28.
523:) and ending at the pair before the last occurrence. The sequence of
24:
362:
These rotation eliminations comprise Phase 2 of Irving's algorithm.
3318:
2818:
74:
In a given instance of the stable-roommates problem (SRP), each of
3039:
3029:
2707:
1477:= (1,2), (2,6), (4,5) is identified, and its elimination yields:
86:
in an instance of SRP is stable if there are no two participants
583:. To restore the stable table properties (i) and (ii), for each
2169:
171:
The algorithm consists of two phases. In Phase 1, participants
2808:
2066:
Integration of AI and OR Techniques in
Constraint Programming
2155:
2117:"Analysis of Stable Matchings in R: Package matchingMarkets"
612:
Phase 2 of the algorithm can now be summarized as follows:
1700:= (2,5), (3,4) is identified, and its elimination gives:
2018:"Matching: A Python library for solving matching games"
1935:
2273:
The Stable
Marriage Problem: Structure and Algorithms
94:, each of whom prefers the other to their partner in
2248:
1932:
Hence the matching {1, 6}, {2,4}, {3, 5} is stable.
878:) running time, a ranking matrix whose entry at row
344:
In any stable table, if every reduced list contains
2098:"Constraint encoding for stable roommates problem"
2015:
217:, and symmetrically, for each removed participant
175:to each other, in a manner similar to that of the
1693:Hence 1 and 6 are matched. Finally, the rotation
3397:
2271:Gusfield, Daniel M.; Irving, Robert W. (1989),
2138:"matchingMarkets: Analysis of Stable Matchings"
2270:
2332:
2280:Irving, Robert W.; Manlove, David F. (2002),
2279:
2059:"Stable Roommates and Constraint Programming"
548:has at least two individuals on their list.
2016:Wilde, H.; Knight, V.; Gillard, J. (2020).
368:Otherwise, the algorithm enters Phase 2. A
102:, or to be a blocking pair with respect to
82:disjoint pairs of participants. A matching
2339:
2325:
502:'s list, until this sequence repeats some
139:A:(B,C,D), B:(C,A,D), C:(A,B,D), D:(A,B,C)
2346:
2300:
2262:
2041:
1992:United States Naval Research Laboratory's
320:prefers the last person on their list to
2282:"The Stable Roommates Problem with Ties"
2056:
1986:: The algorithm is implemented in the
3398:
2221:
157:
2320:
2124:Vignette to R Package MatchingMarkets
2114:
609:eliminate, so the step is repeated.
1936:Implementation in software packages
328:, the last person on their list to
13:
2388:First-player and second-player win
2242:
14:
3437:
2495:Coalition-proof Nash equilibrium
31:, particularly in the fields of
2022:Journal of Open Source Software
333:(iii) no reduced list is empty
98:. Such a pair is said to block
51:) is the problem of finding a
16:Type of stable matching problem
2505:Evolutionarily stable strategy
2186:
2162:
2148:
2130:
2108:
2090:
2050:
2009:
305:s reduced list if and only if
281:s reduced list if and only if
1:
2433:Simultaneous action selection
2002:
1990:function that is part of the
3370:List of games in game theory
2545:Quantal response equilibrium
2535:Perfect Bayesian equilibrium
2470:Bayes correlated equilibrium
2251:Theoretical Computer Science
2236:10.1016/0196-6774(85)90033-1
151:
7:
2839:Optional prisoner's dilemma
2565:Self-confirming equilibrium
2194:"Tracker Component Library"
2074:10.1007/978-3-319-07046-9_2
551:To eliminate the rotation,
186:Consider two participants,
110:
10:
3442:
3304:Principal variation search
3020:Aumann's agreement theorem
2683:Strategy-stealing argument
2590:Trembling hand equilibrium
2520:Markov perfect equilibrium
2515:Mertens-stable equilibrium
2215:
919:
376:is defined as a sequence (
70:It is commonly stated as:
3340:Combinatorial game theory
3327:
3286:
3068:
3012:
2999:Princess and monster game
2794:
2696:
2598:
2550:Quasi-perfect equilibrium
2475:Bayesian Nash equilibrium
2456:
2355:
2264:10.1016/j.tcs.2007.04.029
1996:Tracker Component Library
1264:In Phase 2, the rotation
55:for an even-sized set. A
3355:Evolutionary game theory
3088:Antoine Augustin Cournot
2974:Guess 2/3 of the average
2771:Strictly determined game
2560:Satisfaction equilibrium
2378:Escalation of commitment
894:th's list; this takes O(
614:
209:s list all participants
156:An efficient algorithm (
3360:Glossary of game theory
2959:Stackelberg competition
2580:Strong Nash equilibrium
886:is the position of the
181:stable marriage problem
117:stable marriage problem
65:stable-marriage problem
45:stable-roommate problem
3385:Tragedy of the commons
3365:List of game theorists
3345:Confrontation analysis
3055:Sprague–Grundy theorem
2570:Sequential equilibrium
2490:Correlated equilibrium
2311:10.1006/jagm.2002.1219
202:, then we remove from
198:holds a proposal from
177:Gale-Shapley algorithm
135:, whose rankings are:
3426:Mathematical problems
3158:Jean-François Mertens
2289:Journal of Algorithms
2224:Journal of Algorithms
1988:assignStableRoommates
890:th individual in the
453:'s reduced list) and
356:rotation eliminations
3287:Search optimizations
3163:Jennifer Tour Chayes
3050:Revelation principle
3045:Purification theorem
2984:Nash bargaining game
2949:Bertrand competition
2934:El Farol Bar problem
2899:Electronic mail game
2864:Lewis signaling game
2403:Hierarchy of beliefs
2057:Prosser, P. (2014).
587:, all successors of
481:to be the second on
439:'s reduced list (or
358:on the stable table.
3335:Bounded rationality
2954:Cournot competition
2904:Rock paper scissors
2879:Battle of the sexes
2869:Volunteer's dilemma
2741:Perfect information
2668:Dominant strategies
2500:Epsilon-equilibrium
2383:Extensive-form game
2174:dyad-finder.web.app
2156:"MatchingTools API"
2043:10.21105/joss.02169
2034:2020JOSS....5.2169W
1470:Next, the rotation
3314:Paranoid algorithm
3294:Alpha–beta pruning
3173:John Maynard Smith
3004:Rendezvous problem
2844:Traveler's dilemma
2834:Gift-exchange game
2829:Prisoner's dilemma
2746:Large Poisson game
2713:Bargaining problem
2613:Backward induction
2585:Subgame perfection
2540:Proper equilibrium
2115:Klein, T. (2015).
911:depth-first search
495:to be the last on
372:in a stable table
3416:Cooperative games
3393:
3392:
3299:Aspiration window
3268:Suzanne Scotchmer
3223:Oskar Morgenstern
3118:Donald B. Gillies
3060:Zermelo's theorem
2989:Induction puzzles
2944:Fair cake-cutting
2919:Public goods game
2849:Coordination game
2723:Intransitive game
2648:Forward induction
2530:Pareto efficiency
2510:Gibbs equilibrium
2480:Berge equilibrium
2428:Simultaneous game
2198:Matlab Repository
2083:978-3-319-07045-2
1064:and Ă— represents
594:are removed from
316:s if and only if
3433:
3380:Topological game
3375:No-win situation
3273:Thomas Schelling
3253:Robert B. Wilson
3213:Merrill M. Flood
3183:John von Neumann
3093:Ariel Rubinstein
3078:Albert W. Tucker
2929:War of attrition
2889:Matching pennies
2663:Pairing strategy
2525:Nash equilibrium
2448:Mechanism design
2413:Normal-form game
2368:Cooperative game
2341:
2334:
2327:
2318:
2317:
2313:
2304:
2286:
2276:
2267:
2266:
2257:(1–3): 162–176,
2238:
2209:
2208:
2206:
2204:
2190:
2184:
2183:
2181:
2180:
2166:
2160:
2159:
2152:
2146:
2145:
2134:
2128:
2127:
2121:
2112:
2106:
2105:
2094:
2088:
2087:
2063:
2054:
2048:
2047:
2045:
2013:
1989:
1963:
1947:
1928:
1924:
1920:
1916:
1912:
1908:
1904:
1900:
1896:
1890:
1886:
1882:
1878:
1874:
1870:
1866:
1862:
1858:
1852:
1848:
1844:
1840:
1836:
1832:
1828:
1824:
1820:
1814:
1810:
1806:
1802:
1798:
1794:
1790:
1786:
1782:
1776:
1772:
1768:
1764:
1760:
1756:
1752:
1748:
1744:
1738:
1734:
1730:
1726:
1722:
1718:
1714:
1710:
1706:
1689:
1685:
1681:
1677:
1673:
1669:
1665:
1661:
1657:
1651:
1647:
1643:
1639:
1635:
1631:
1627:
1623:
1617:
1613:
1609:
1605:
1601:
1597:
1593:
1589:
1583:
1579:
1575:
1571:
1567:
1563:
1559:
1555:
1549:
1545:
1541:
1537:
1533:
1529:
1525:
1521:
1515:
1511:
1507:
1503:
1499:
1495:
1491:
1487:
1483:
1466:
1462:
1458:
1454:
1450:
1446:
1442:
1438:
1432:
1428:
1424:
1420:
1416:
1412:
1408:
1402:
1398:
1394:
1390:
1386:
1382:
1378:
1372:
1368:
1364:
1360:
1356:
1352:
1348:
1344:
1338:
1334:
1330:
1326:
1322:
1318:
1312:
1308:
1304:
1300:
1296:
1292:
1288:
1284:
1260:
1256:
1252:
1248:
1244:
1240:
1236:
1230:
1226:
1222:
1218:
1214:
1210:
1206:
1200:
1196:
1192:
1188:
1184:
1178:
1174:
1170:
1166:
1162:
1158:
1154:
1148:
1144:
1140:
1136:
1132:
1126:
1122:
1118:
1114:
1110:
1106:
1102:
1090:
1082:
1056:
1052:
1048:
1044:
1040:
1034:
1030:
1026:
1022:
1018:
1012:
1008:
1004:
1000:
996:
990:
986:
982:
978:
974:
968:
964:
960:
956:
952:
946:
942:
938:
934:
930:
874:To achieve an O(
870:
867:
864:
861:
858:
855:
852:
849:
846:
843:
840:
837:
834:
831:
828:
825:
822:
819:
816:
813:
810:
807:
804:
801:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
768:
765:
762:
759:
756:
753:
750:
747:
744:
741:
738:
735:
732:
729:
726:
723:
720:
717:
714:
711:
708:
705:
702:
699:
696:
693:
690:
687:
684:
681:
678:
675:
672:
669:
666:
663:
660:
657:
654:
651:
648:
645:
642:
639:
636:
633:
630:
627:
624:
621:
618:
418:) such that the
315:
304:
291:
280:
253:
242:
232:s list, so that
231:
208:
29:computer science
3441:
3440:
3436:
3435:
3434:
3432:
3431:
3430:
3421:Stable matching
3396:
3395:
3394:
3389:
3323:
3309:max^n algorithm
3282:
3278:William Vickrey
3238:Reinhard Selten
3193:Kenneth Binmore
3108:David K. Levine
3103:Daniel Kahneman
3070:
3064:
3040:Negamax theorem
3030:Minimax theorem
3008:
2969:Diner's dilemma
2824:All-pay auction
2790:
2776:Stochastic game
2728:Mean-field game
2699:
2692:
2658:Markov strategy
2594:
2460:
2452:
2423:Sequential game
2408:Information set
2393:Game complexity
2363:Congestion game
2351:
2345:
2302:10.1.1.108.7366
2284:
2245:
2243:Further reading
2218:
2213:
2212:
2202:
2200:
2192:
2191:
2187:
2178:
2176:
2168:
2167:
2163:
2154:
2153:
2149:
2136:
2135:
2131:
2119:
2113:
2109:
2096:
2095:
2091:
2084:
2061:
2055:
2051:
2014:
2010:
2005:
1987:
1974:Web Application
1962:matchingMarkets
1961:
1945:
1938:
1929:
1926:
1922:
1921:
1918:
1914:
1913:
1910:
1906:
1902:
1901:
1898:
1894:
1892:
1891:
1888:
1884:
1883:
1880:
1876:
1875:
1872:
1868:
1867:
1864:
1860:
1856:
1854:
1853:
1850:
1846:
1845:
1842:
1838:
1837:
1834:
1830:
1826:
1825:
1822:
1818:
1816:
1815:
1812:
1808:
1807:
1804:
1800:
1796:
1795:
1792:
1788:
1787:
1784:
1780:
1778:
1777:
1774:
1770:
1769:
1766:
1762:
1758:
1757:
1754:
1750:
1749:
1746:
1742:
1740:
1739:
1736:
1732:
1728:
1727:
1724:
1720:
1719:
1716:
1712:
1711:
1708:
1704:
1699:
1690:
1687:
1683:
1682:
1679:
1675:
1674:
1671:
1667:
1663:
1662:
1659:
1655:
1653:
1652:
1649:
1645:
1644:
1641:
1637:
1633:
1632:
1629:
1625:
1621:
1619:
1618:
1615:
1611:
1610:
1607:
1603:
1599:
1595:
1594:
1591:
1587:
1585:
1584:
1581:
1577:
1576:
1573:
1569:
1565:
1561:
1560:
1557:
1553:
1551:
1550:
1547:
1543:
1542:
1539:
1535:
1531:
1527:
1526:
1523:
1519:
1517:
1516:
1513:
1509:
1505:
1504:
1501:
1497:
1496:
1493:
1489:
1488:
1485:
1481:
1476:
1464:
1463:
1460:
1456:
1455:
1452:
1448:
1444:
1443:
1440:
1436:
1434:
1433:
1430:
1426:
1422:
1418:
1417:
1414:
1410:
1406:
1404:
1403:
1400:
1396:
1395:
1392:
1388:
1384:
1380:
1376:
1374:
1373:
1370:
1366:
1365:
1362:
1358:
1354:
1350:
1349:
1346:
1342:
1340:
1339:
1336:
1332:
1328:
1324:
1320:
1316:
1314:
1313:
1310:
1306:
1302:
1298:
1297:
1294:
1290:
1289:
1286:
1282:
1277:
1270:
1258:
1254:
1253:
1250:
1246:
1242:
1241:
1238:
1234:
1232:
1231:
1228:
1224:
1220:
1216:
1215:
1212:
1208:
1204:
1202:
1198:
1194:
1190:
1186:
1182:
1180:
1179:
1176:
1172:
1171:
1168:
1164:
1160:
1156:
1152:
1150:
1146:
1142:
1138:
1134:
1130:
1128:
1127:
1124:
1120:
1116:
1112:
1108:
1107:
1104:
1100:
1092:
1088:
1086:
1084:
1080:
1078:
1076:
1074:
1072:
1054:
1050:
1046:
1042:
1038:
1036:
1032:
1028:
1024:
1020:
1016:
1014:
1010:
1006:
1002:
998:
994:
992:
988:
984:
980:
976:
972:
970:
966:
962:
958:
954:
950:
948:
944:
940:
936:
932:
928:
922:
914:graph traversal
908:
872:
871:
868:
865:
862:
859:
856:
853:
850:
847:
844:
841:
838:
835:
832:
829:
826:
823:
820:
817:
814:
811:
808:
805:
802:
799:
796:
793:
790:
787:
784:
781:
778:
775:
772:
769:
766:
763:
760:
757:
754:
751:
748:
745:
742:
739:
736:
733:
730:
727:
724:
721:
718:
715:
712:
709:
706:
703:
700:
697:
694:
691:
688:
685:
682:
679:
676:
673:
670:
667:
664:
661:
658:
655:
652:
649:
646:
643:
640:
637:
634:
631:
628:
625:
622:
619:
616:
607:
600:
593:
578:
571:
564:
557:
547:
536:
529:
522:
515:
508:
501:
494:
487:
480:
473:
466:
459:
452:
445:
438:
431:
424:
417:
410:
403:
396:
389:
382:
332:
313:
302:
293:
289:
278:
251:
240:
229:
206:
154:
134:
130:
126:
122:
113:
53:stable matching
17:
12:
11:
5:
3439:
3429:
3428:
3423:
3418:
3413:
3408:
3391:
3390:
3388:
3387:
3382:
3377:
3372:
3367:
3362:
3357:
3352:
3347:
3342:
3337:
3331:
3329:
3325:
3324:
3322:
3321:
3316:
3311:
3306:
3301:
3296:
3290:
3288:
3284:
3283:
3281:
3280:
3275:
3270:
3265:
3260:
3255:
3250:
3245:
3243:Robert Axelrod
3240:
3235:
3230:
3225:
3220:
3218:Olga Bondareva
3215:
3210:
3208:Melvin Dresher
3205:
3200:
3198:Leonid Hurwicz
3195:
3190:
3185:
3180:
3175:
3170:
3165:
3160:
3155:
3150:
3145:
3140:
3135:
3133:Harold W. Kuhn
3130:
3125:
3123:Drew Fudenberg
3120:
3115:
3113:David M. Kreps
3110:
3105:
3100:
3098:Claude Shannon
3095:
3090:
3085:
3080:
3074:
3072:
3066:
3065:
3063:
3062:
3057:
3052:
3047:
3042:
3037:
3035:Nash's theorem
3032:
3027:
3022:
3016:
3014:
3010:
3009:
3007:
3006:
3001:
2996:
2991:
2986:
2981:
2976:
2971:
2966:
2961:
2956:
2951:
2946:
2941:
2936:
2931:
2926:
2921:
2916:
2911:
2906:
2901:
2896:
2894:Ultimatum game
2891:
2886:
2881:
2876:
2874:Dollar auction
2871:
2866:
2861:
2859:Centipede game
2856:
2851:
2846:
2841:
2836:
2831:
2826:
2821:
2816:
2814:Infinite chess
2811:
2806:
2800:
2798:
2792:
2791:
2789:
2788:
2783:
2781:Symmetric game
2778:
2773:
2768:
2766:Signaling game
2763:
2761:Screening game
2758:
2753:
2751:Potential game
2748:
2743:
2738:
2730:
2725:
2720:
2715:
2710:
2704:
2702:
2694:
2693:
2691:
2690:
2685:
2680:
2678:Mixed strategy
2675:
2670:
2665:
2660:
2655:
2650:
2645:
2640:
2635:
2630:
2625:
2620:
2615:
2610:
2604:
2602:
2596:
2595:
2593:
2592:
2587:
2582:
2577:
2572:
2567:
2562:
2557:
2555:Risk dominance
2552:
2547:
2542:
2537:
2532:
2527:
2522:
2517:
2512:
2507:
2502:
2497:
2492:
2487:
2482:
2477:
2472:
2466:
2464:
2454:
2453:
2451:
2450:
2445:
2440:
2435:
2430:
2425:
2420:
2415:
2410:
2405:
2400:
2398:Graphical game
2395:
2390:
2385:
2380:
2375:
2370:
2365:
2359:
2357:
2353:
2352:
2344:
2343:
2336:
2329:
2321:
2315:
2314:
2277:
2268:
2244:
2241:
2240:
2239:
2230:(4): 577–595,
2217:
2214:
2211:
2210:
2185:
2161:
2147:
2129:
2107:
2089:
2082:
2049:
2007:
2006:
2004:
2001:
2000:
1999:
1981:
1971:
1965:
1955:
1949:
1937:
1934:
1925:
1917:
1909:
1897:
1887:
1879:
1871:
1863:
1849:
1841:
1833:
1821:
1811:
1803:
1791:
1783:
1773:
1765:
1753:
1745:
1735:
1723:
1715:
1707:
1697:
1686:
1678:
1670:
1658:
1648:
1640:
1628:
1614:
1606:
1590:
1580:
1572:
1556:
1546:
1538:
1522:
1512:
1500:
1492:
1484:
1474:
1459:
1451:
1439:
1429:
1413:
1399:
1391:
1369:
1361:
1345:
1335:
1309:
1293:
1285:
1275:
1268:
1249:
1237:
1227:
1211:
1175:
1167:
1123:
1103:
921:
918:
906:
615:
605:
598:
591:
576:
569:
562:
555:
545:
537:is called the
534:
527:
520:
513:
506:
499:
492:
485:
478:
471:
464:
457:
450:
443:
436:
429:
425:are distinct,
422:
415:
408:
401:
394:
387:
380:
360:
359:
352:
349:
342:
153:
150:
141:
140:
132:
128:
124:
120:
112:
109:
108:
107:
15:
9:
6:
4:
3:
2:
3438:
3427:
3424:
3422:
3419:
3417:
3414:
3412:
3409:
3407:
3406:Combinatorics
3404:
3403:
3401:
3386:
3383:
3381:
3378:
3376:
3373:
3371:
3368:
3366:
3363:
3361:
3358:
3356:
3353:
3351:
3348:
3346:
3343:
3341:
3338:
3336:
3333:
3332:
3330:
3328:Miscellaneous
3326:
3320:
3317:
3315:
3312:
3310:
3307:
3305:
3302:
3300:
3297:
3295:
3292:
3291:
3289:
3285:
3279:
3276:
3274:
3271:
3269:
3266:
3264:
3263:Samuel Bowles
3261:
3259:
3258:Roger Myerson
3256:
3254:
3251:
3249:
3248:Robert Aumann
3246:
3244:
3241:
3239:
3236:
3234:
3231:
3229:
3226:
3224:
3221:
3219:
3216:
3214:
3211:
3209:
3206:
3204:
3203:Lloyd Shapley
3201:
3199:
3196:
3194:
3191:
3189:
3188:Kenneth Arrow
3186:
3184:
3181:
3179:
3176:
3174:
3171:
3169:
3168:John Harsanyi
3166:
3164:
3161:
3159:
3156:
3154:
3151:
3149:
3146:
3144:
3141:
3139:
3138:Herbert Simon
3136:
3134:
3131:
3129:
3126:
3124:
3121:
3119:
3116:
3114:
3111:
3109:
3106:
3104:
3101:
3099:
3096:
3094:
3091:
3089:
3086:
3084:
3081:
3079:
3076:
3075:
3073:
3067:
3061:
3058:
3056:
3053:
3051:
3048:
3046:
3043:
3041:
3038:
3036:
3033:
3031:
3028:
3026:
3023:
3021:
3018:
3017:
3015:
3011:
3005:
3002:
3000:
2997:
2995:
2992:
2990:
2987:
2985:
2982:
2980:
2977:
2975:
2972:
2970:
2967:
2965:
2962:
2960:
2957:
2955:
2952:
2950:
2947:
2945:
2942:
2940:
2939:Fair division
2937:
2935:
2932:
2930:
2927:
2925:
2922:
2920:
2917:
2915:
2914:Dictator game
2912:
2910:
2907:
2905:
2902:
2900:
2897:
2895:
2892:
2890:
2887:
2885:
2882:
2880:
2877:
2875:
2872:
2870:
2867:
2865:
2862:
2860:
2857:
2855:
2852:
2850:
2847:
2845:
2842:
2840:
2837:
2835:
2832:
2830:
2827:
2825:
2822:
2820:
2817:
2815:
2812:
2810:
2807:
2805:
2802:
2801:
2799:
2797:
2793:
2787:
2786:Zero-sum game
2784:
2782:
2779:
2777:
2774:
2772:
2769:
2767:
2764:
2762:
2759:
2757:
2756:Repeated game
2754:
2752:
2749:
2747:
2744:
2742:
2739:
2737:
2735:
2731:
2729:
2726:
2724:
2721:
2719:
2716:
2714:
2711:
2709:
2706:
2705:
2703:
2701:
2695:
2689:
2686:
2684:
2681:
2679:
2676:
2674:
2673:Pure strategy
2671:
2669:
2666:
2664:
2661:
2659:
2656:
2654:
2651:
2649:
2646:
2644:
2641:
2639:
2636:
2634:
2633:De-escalation
2631:
2629:
2626:
2624:
2621:
2619:
2616:
2614:
2611:
2609:
2606:
2605:
2603:
2601:
2597:
2591:
2588:
2586:
2583:
2581:
2578:
2576:
2575:Shapley value
2573:
2571:
2568:
2566:
2563:
2561:
2558:
2556:
2553:
2551:
2548:
2546:
2543:
2541:
2538:
2536:
2533:
2531:
2528:
2526:
2523:
2521:
2518:
2516:
2513:
2511:
2508:
2506:
2503:
2501:
2498:
2496:
2493:
2491:
2488:
2486:
2483:
2481:
2478:
2476:
2473:
2471:
2468:
2467:
2465:
2463:
2459:
2455:
2449:
2446:
2444:
2443:Succinct game
2441:
2439:
2436:
2434:
2431:
2429:
2426:
2424:
2421:
2419:
2416:
2414:
2411:
2409:
2406:
2404:
2401:
2399:
2396:
2394:
2391:
2389:
2386:
2384:
2381:
2379:
2376:
2374:
2371:
2369:
2366:
2364:
2361:
2360:
2358:
2354:
2350:
2342:
2337:
2335:
2330:
2328:
2323:
2322:
2319:
2312:
2308:
2303:
2298:
2295:(1): 85–105,
2294:
2290:
2283:
2278:
2274:
2269:
2265:
2260:
2256:
2252:
2247:
2246:
2237:
2233:
2229:
2225:
2220:
2219:
2199:
2195:
2189:
2175:
2171:
2170:"Dyad Finder"
2165:
2157:
2151:
2144:. 2019-02-04.
2143:
2139:
2133:
2125:
2118:
2111:
2103:
2099:
2093:
2085:
2079:
2075:
2071:
2067:
2060:
2053:
2044:
2039:
2035:
2031:
2027:
2023:
2019:
2012:
2008:
1997:
1993:
1985:
1982:
1979:
1975:
1972:
1969:
1966:
1959:
1956:
1953:
1950:
1943:
1940:
1939:
1933:
1930:
1701:
1696:
1691:
1478:
1473:
1468:
1279:
1274:
1267:
1262:
1097:
1094:
1069:
1067:
1063:
1058:
925:
917:
915:
912:
905:
901:
897:
893:
889:
885:
881:
877:
613:
610:
604:
601:'s list, and
597:
590:
586:
582:
575:
568:
561:
554:
549:
544:
540:
533:
530:up until the
526:
519:
512:
505:
498:
491:
484:
477:
470:
463:
460:is second on
456:
449:
442:
435:
428:
421:
414:
407:
400:
393:
386:
379:
375:
371:
366:
363:
357:
353:
350:
347:
343:
339:
338:
337:
334:
331:
327:
323:
319:
312:
308:
301:
297:
288:
284:
277:
273:
268:
266:
261:
257:
250:
246:
239:
235:
228:
224:
220:
216:
212:
205:
201:
197:
193:
189:
184:
182:
178:
174:
169:
167:
165:
159:
149:
146:
138:
137:
136:
118:
105:
101:
97:
93:
89:
85:
81:
77:
73:
72:
71:
68:
66:
62:
58:
54:
50:
46:
42:
38:
34:
33:combinatorics
30:
26:
22:
3233:Peyton Young
3228:Paul Milgrom
3143:Hervé Moulin
3083:Amos Tversky
3025:Folk theorem
2736:-player game
2733:
2653:Grim trigger
2292:
2288:
2272:
2254:
2250:
2227:
2223:
2201:. Retrieved
2197:
2188:
2177:. Retrieved
2173:
2164:
2150:
2141:
2132:
2123:
2110:
2102:Java release
2101:
2092:
2065:
2052:
2028:(48): 2169.
2025:
2021:
2011:
1931:
1702:
1694:
1692:
1479:
1471:
1469:
1280:
1272:
1265:
1263:
1098:
1095:
1070:
1065:
1061:
1059:
926:
923:
903:
899:
895:
891:
887:
883:
879:
875:
873:
611:
602:
595:
588:
584:
580:
573:
572:proposes to
566:
559:
552:
550:
542:
538:
531:
524:
517:
510:
503:
496:
489:
488:'s list and
482:
475:
468:
461:
454:
447:
440:
433:
432:is first on
426:
419:
412:
405:
398:
391:
384:
377:
373:
369:
367:
364:
361:
355:
345:
335:
329:
325:
321:
317:
310:
306:
299:
295:
286:
282:
275:
274:is first on
271:
269:
265:stable table
264:
259:
255:
248:
244:
243:s list; and
237:
236:is first in
233:
226:
222:
221:, we remove
218:
214:
210:
203:
199:
195:
191:
187:
185:
172:
170:
166:) complexity
163:
155:
144:
142:
114:
103:
99:
95:
91:
87:
83:
79:
75:
69:
60:
52:
48:
44:
18:
3411:Game theory
3350:Coopetition
3153:Jean Tirole
3148:John Conway
3128:Eric Maskin
2924:Blotto game
2909:Pirate game
2718:Global game
2688:Tit for tat
2618:Bid shading
2608:Appeasement
2458:Equilibrium
2438:Solved game
2373:Determinacy
2356:Definitions
2349:game theory
2275:, MIT Press
1062:proposes to
882:and column
579:, for each
446:is last on
285:is last on
158:Irving 1985
115:Unlike the
37:game theory
21:mathematics
3400:Categories
2994:Trust game
2979:Kuhn poker
2643:Escalation
2638:Deterrence
2628:Cheap talk
2600:Strategies
2418:Preference
2347:Topics of
2203:January 5,
2179:2020-05-06
2003:References
1978:JavaScript
309:is not on
298:is not on
247:, last in
41:algorithms
3178:John Nash
2884:Stag hunt
2623:Collusion
2297:CiteSeerX
2142:R Project
1893:6 :
1855:5 :
1817:4 :
1779:3 :
1741:2 :
1703:1 :
1654:6 :
1620:5 :
1586:4 :
1552:3 :
1518:2 :
1480:1 :
1435:6 :
1405:5 :
1375:4 :
1341:3 :
1315:2 :
1281:1 :
1233:6 :
1203:5 :
1181:4 :
1151:3 :
1129:2 :
1099:1 :
1037:6 :
1015:5 :
993:4 :
971:3 :
949:2 :
927:1 :
900:unmatched
671:eliminate
404:), ..., (
254:s, since
152:Algorithm
25:economics
3319:Lazy SMP
3013:Theorems
2964:Deadlock
2819:Checkers
2700:of games
2462:concepts
1964:package.
1948:library.
1946:matching
863:matching
782:matching
728:matching
656:rotation
650:identify
565:so that
558:rejects
370:rotation
258:and any
179:for the
111:Solution
57:matching
3071:figures
2854:Chicken
2708:Auction
2698:Classes
2216:Sources
2030:Bibcode
1278:gives:
1087:6 → 5;
1079:5 → 3;
1066:rejects
920:Example
752:reduced
701:becomes
346:exactly
173:propose
2299:
2080:
1984:Matlab
1942:Python
1923:
1915:
1907:
1903:
1895:
1885:
1877:
1869:
1861:
1857:
1847:
1839:
1831:
1827:
1819:
1809:
1801:
1797:
1789:
1781:
1771:
1763:
1759:
1751:
1743:
1733:
1729:
1721:
1713:
1705:
1684:
1676:
1668:
1664:
1656:
1646:
1638:
1634:
1626:
1622:
1612:
1604:
1600:
1596:
1588:
1578:
1570:
1566:
1562:
1554:
1544:
1536:
1532:
1528:
1520:
1510:
1506:
1498:
1490:
1482:
1465:
1457:
1449:
1445:
1437:
1427:
1423:
1419:
1411:
1407:
1397:
1389:
1385:
1381:
1377:
1367:
1359:
1355:
1351:
1343:
1333:
1329:
1325:
1321:
1317:
1307:
1303:
1299:
1291:
1283:
1259:
1255:
1247:
1243:
1235:
1225:
1221:
1217:
1209:
1205:
1199:
1195:
1191:
1187:
1183:
1173:
1165:
1161:
1157:
1153:
1147:
1143:
1139:
1135:
1131:
1121:
1117:
1113:
1109:
1101:
1093:6 → 1
1091:5 Ă— 6
1089:
1085:1 → 4
1083:3 Ă— 1
1081:
1077:4 → 5
1075:3 → 2
1073:2 → 6
1071:1 → 3
1055:
1051:
1047:
1043:
1039:
1033:
1029:
1025:
1021:
1017:
1011:
1007:
1003:
999:
995:
989:
985:
981:
977:
973:
967:
963:
959:
955:
951:
945:
941:
937:
933:
929:
860:stable
776:return
725:stable
710:return
341:lists.
213:after
194:. If
131:, and
61:stable
43:, the
2809:Chess
2796:Games
2285:(PDF)
2120:(PDF)
2062:(PDF)
1994:free
836:lists
830:'
827:other
734:exist
704:empty
635:while
629:table
623:Phase
324:; or
314:'
303:'
294:(ii)
290:'
279:'
252:'
241:'
230:'
225:from
207:'
2485:Core
2205:2019
2078:ISBN
1952:Java
851:this
824:each
767:size
755:list
749:each
740:else
713:null
692:list
689:some
677:from
641:true
539:tail
390:), (
270:(i)
190:and
145:must
90:and
39:and
27:and
3069:Key
2307:doi
2259:doi
2255:381
2232:doi
2070:doi
2038:doi
1968:API
1731:6
1508:6
1425:4
1331:1
1305:6
1257:4
1223:4
1197:6
1145:1
1119:6
1053:4
1031:4
1009:6
987:1
965:1
943:6
818:are
812:and
779:the
764:has
731:can
592:i-1
577:i+1
500:i+1
493:i+1
479:i+1
458:i+1
416:k-1
409:k-1
49:SRP
19:In
3402::
2804:Go
2305:,
2293:43
2291:,
2287:,
2253:,
2226:,
2196:.
2172:.
2140:.
2122:.
2100:.
2076:.
2064:.
2036:.
2024:.
2020:.
1905:1
1859:3
1829:2
1799:5
1761:4
1666:1
1636:2
1624:3
1602:3
1598:2
1568:5
1564:4
1534:4
1530:5
1467:2
1447:1
1421:2
1409:3
1387:3
1383:2
1379:5
1357:5
1353:4
1327:4
1323:5
1319:6
1301:2
1261:2
1245:1
1219:2
1207:3
1201:1
1193:3
1189:2
1185:5
1163:5
1159:4
1155:2
1149:3
1141:4
1137:5
1133:6
1115:2
1111:4
1068:.
1057:2
1049:3
1045:1
1041:5
1035:6
1027:2
1023:1
1019:3
1013:1
1005:3
1001:2
997:5
991:6
983:5
979:4
975:2
969:3
961:4
957:5
953:6
947:5
939:2
935:4
931:3
854:is
845:};
839:in
821:on
791:{{
758:in
743:if
722:no
695:in
686:if
662:in
516:,
411:,
397:,
383:,
292:s
162:O(
127:,
123:,
76:2n
35:,
23:,
2734:n
2340:e
2333:t
2326:v
2309::
2261::
2234::
2228:6
2207:.
2182:.
2158:.
2126:.
2104:.
2086:.
2072::
2046:.
2040::
2032::
2026:5
1998:.
1980:.
1958:R
1927:2
1919:4
1911:3
1899:5
1889:6
1881:4
1873:2
1865:1
1851:1
1843:6
1835:3
1823:5
1813:6
1805:1
1793:4
1785:2
1775:3
1767:1
1755:5
1747:6
1737:5
1725:2
1717:4
1709:3
1698:3
1695:r
1688:2
1680:4
1672:3
1660:5
1650:6
1642:4
1630:1
1616:1
1608:6
1592:5
1582:6
1574:1
1558:2
1548:3
1540:1
1524:6
1514:5
1502:2
1494:4
1486:3
1475:2
1472:r
1461:4
1453:3
1441:5
1431:6
1415:1
1401:1
1393:6
1371:6
1363:1
1347:2
1337:3
1311:5
1295:4
1287:3
1276:1
1273:r
1269:1
1266:r
1251:3
1239:5
1229:6
1213:1
1177:6
1169:1
1125:5
1105:3
907:i
904:p
896:n
892:i
888:j
884:j
880:i
876:n
869:}
866:)
857:a
848:(
842:T
833:s
815:y
809:x
806:|
803:}
800:y
797:,
794:x
788:=
785:M
773:)
770:1
761:T
746:(
737:)
719:(
716:;
707:,
698:T
683:;
680:T
674:r
668:;
665:T
659:r
653:a
647:{
644:)
638:(
632:;
626:1
620:=
617:T
606:i
603:y
599:i
596:y
589:x
585:i
581:i
574:y
570:i
567:x
563:i
560:x
556:i
553:y
546:i
543:p
535:j
532:p
528:i
525:p
521:j
518:q
514:j
511:p
507:j
504:p
497:q
490:p
486:i
483:p
476:q
472:0
469:p
465:i
462:x
455:y
451:i
448:y
444:i
441:x
437:i
434:x
430:i
427:y
423:i
420:x
413:y
406:x
402:1
399:y
395:1
392:x
388:0
385:y
381:0
378:x
374:T
330:q
326:p
322:p
318:q
311:p
307:q
300:q
296:p
287:p
283:q
276:q
272:p
260:x
256:q
249:q
245:p
238:p
234:q
227:x
223:q
219:x
215:p
211:x
204:q
200:p
196:q
192:p
188:q
164:n
133:D
129:C
125:B
121:A
106:.
104:M
100:M
96:M
92:y
88:x
84:M
80:n
47:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.