40:
If they both choose to wait, they will never meet. If they both choose to walk there are chances that they meet and chances that they do not. If one chooses to wait and the other chooses to walk, then there is a theoretical certainty that they will meet eventually; in practice, though, it may take
27:
Two people have a date in a park they have never been to before. Arriving separately in the park, they are both surprised to discover that it is a huge area and consequently they cannot find one another. In this situation each person has to choose between waiting in a
72:. This was the first non-trivial symmetric rendezvous search problem to be fully solved. The corresponding asymmetric rendezvous problem has a simple optimal solution: one player stays put and the other player visits a random permutation of the locations.
52:
in 1976, and he formalised the continuous version of the problem in 1995. This has led to much recent research in rendezvous search. Even the symmetric rendezvous problem played in
41:
too long for it to be guaranteed. The question posed, then, is: what strategies should they choose to maximize their probability of meeting?
117:
sequence of instructions. Although each robot follows the same instruction sequence, a unique label assigned to each robot is used for
75:
As well as being problems of theoretical interest, rendezvous problems include real-world problems with applications in the fields of
252:, International Series in Operations Research & Management Science, vol. 55, Boston, MA: Kluwer Academic Publishers,
469:
1368:
1185:
720:
518:
378:
1004:
823:
257:
625:
100:
1094:
964:
635:
803:
1145:
563:
538:
366:
308:
69:
61:
1495:
921:
675:
665:
600:
715:
695:
135:
417:(April 2014). "Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences".
1531:
1429:
1180:
1150:
808:
650:
645:
1465:
1388:
1124:
680:
605:
462:
165:
29:
1480:
1213:
1099:
896:
690:
508:
32:
in the hope that the other will find them, or else starting to look for the other in the hope that
1283:
1485:
1084:
1054:
710:
498:
150:
140:
370:
1510:
1490:
1470:
1419:
1089:
994:
853:
798:
730:
700:
620:
548:
969:
954:
528:
114:
1303:
1288:
1175:
1170:
1074:
1059:
1024:
989:
588:
533:
455:
399:
344:
267:
228:
64:
and Eddie
Anderson conjectured the optimal strategy. In 2012 the conjecture was proved for
312:
8:
1460:
1079:
1029:
866:
793:
773:
630:
513:
84:
1119:
1439:
1298:
1109:
959:
838:
743:
670:
615:
434:
348:
332:
1424:
1393:
1348:
1243:
1114:
1069:
1044:
974:
848:
778:
768:
660:
610:
558:
352:
253:
160:
130:
118:
88:
438:
293:
1505:
1500:
1434:
1398:
1378:
1338:
1308:
1263:
1218:
1203:
1160:
1014:
655:
592:
578:
543:
426:
387:
324:
289:
216:
155:
80:
1403:
1363:
1318:
1233:
1228:
949:
901:
788:
553:
523:
493:
395:
340:
263:
224:
76:
1268:
1343:
1333:
1323:
1258:
1248:
1238:
1223:
1019:
999:
984:
979:
939:
906:
891:
886:
876:
685:
220:
1525:
1383:
1373:
1328:
1313:
1293:
1064:
1039:
911:
881:
871:
858:
763:
705:
640:
573:
1358:
1353:
1208:
783:
391:
281:
241:
204:
185:
145:
49:
1475:
1278:
1273:
1253:
1049:
1034:
843:
813:
748:
738:
568:
503:
479:
447:
1104:
758:
336:
245:
1009:
929:
753:
414:
430:
328:
1444:
944:
1165:
1155:
833:
286:
Wiley
Encyclopedia of Operations Research and Management Science
284:(2011), "Rendezvous search games", in Cochran, James J. (ed.),
934:
109:
is a variant of the rendezvous problem where the players, or
60:) has turned out to be very difficult to solve, and in 1990
371:"Optimal symmetric Rendezvous search on three locations"
23:
is a logical dilemma, typically formulated in this way:
48:. These problems were first introduced informally by
192:, Seminar, Institut fur Hohere Studien, Wien, 26 July
94:
1523:
44:Examples of this class of problems are known as
313:"The rendezvous problem on discrete locations"
463:
306:
412:
470:
456:
477:
250:The Theory of Search Games and Rendezvous
240:
207:(1995), "The rendezvous search problem",
56:discrete locations (sometimes called the
209:SIAM Journal on Control and Optimization
1524:
280:
203:
184:
113:, must find each other by following a
451:
365:
13:
519:First-player and second-player win
379:Mathematics of Operations Research
14:
1543:
626:Coalition-proof Nash equilibrium
107:deterministic rendezvous problem
101:Deterministic rendezvous problem
95:Deterministic rendezvous problem
294:10.1002/9780470400531.eorms0720
636:Evolutionarily stable strategy
419:ACM Transactions on Algorithms
406:
359:
317:Journal of Applied Probability
300:
274:
234:
197:
178:
58:Mozart Cafe Rendezvous Problem
36:have chosen to wait somewhere.
1:
564:Simultaneous action selection
172:
1496:List of games in game theory
676:Quantal response equilibrium
666:Perfect Bayesian equilibrium
601:Bayes correlated equilibrium
7:
965:Optional prisoner's dilemma
696:Self-confirming equilibrium
136:Dining philosophers problem
124:
10:
1548:
1430:Principal variation search
1146:Aumann's agreement theorem
809:Strategy-stealing argument
721:Trembling hand equilibrium
651:Markov perfect equilibrium
646:Mertens-stable equilibrium
98:
1466:Combinatorial game theory
1453:
1412:
1194:
1138:
1125:Princess and monster game
920:
822:
729:
681:Quasi-perfect equilibrium
606:Bayesian Nash equilibrium
587:
486:
221:10.1137/S0363012993249195
168:, a default meeting place
1481:Evolutionary game theory
1214:Antoine Augustin Cournot
1100:Guess 2/3 of the average
897:Strictly determined game
691:Satisfaction equilibrium
509:Escalation of commitment
1486:Glossary of game theory
1085:Stackelberg competition
711:Strong Nash equilibrium
151:Sleeping barber problem
141:Probabilistic algorithm
1511:Tragedy of the commons
1491:List of game theorists
1471:Confrontation analysis
1181:Sprague–Grundy theorem
701:Sequential equilibrium
621:Correlated equilibrium
392:10.1287/moor.1110.0528
1284:Jean-François Mertens
91:operations planning.
1413:Search optimizations
1289:Jennifer Tour Chayes
1176:Revelation principle
1171:Purification theorem
1110:Nash bargaining game
1075:Bertrand competition
1060:El Farol Bar problem
1025:Electronic mail game
990:Lewis signaling game
534:Hierarchy of beliefs
1461:Bounded rationality
1080:Cournot competition
1030:Rock paper scissors
1005:Battle of the sexes
995:Volunteer's dilemma
867:Perfect information
794:Dominant strategies
631:Epsilon-equilibrium
514:Extensive-form game
190:Hide and Seek Games
85:operations research
46:rendezvous problems
1440:Paranoid algorithm
1420:Alpha–beta pruning
1299:John Maynard Smith
1130:Rendezvous problem
970:Traveler's dilemma
960:Gift-exchange game
955:Prisoner's dilemma
872:Large Poisson game
839:Bargaining problem
744:Backward induction
716:Subgame perfection
671:Proper equilibrium
21:rendezvous dilemma
1532:Cooperative games
1519:
1518:
1425:Aspiration window
1394:Suzanne Scotchmer
1349:Oskar Morgenstern
1244:Donald B. Gillies
1186:Zermelo's theorem
1115:Induction puzzles
1070:Fair cake-cutting
1045:Public goods game
975:Coordination game
849:Intransitive game
779:Forward induction
661:Pareto efficiency
641:Gibbs equilibrium
611:Berge equilibrium
559:Simultaneous game
307:Anderson, E. J.;
161:Symmetry breaking
131:Coordination game
119:symmetry breaking
89:search and rescue
1539:
1506:Topological game
1501:No-win situation
1399:Thomas Schelling
1379:Robert B. Wilson
1339:Merrill M. Flood
1309:John von Neumann
1219:Ariel Rubinstein
1204:Albert W. Tucker
1055:War of attrition
1015:Matching pennies
656:Nash equilibrium
579:Mechanism design
544:Normal-form game
499:Cooperative game
472:
465:
458:
449:
448:
443:
442:
413:Ta-Shma, Amnon;
410:
404:
402:
375:
363:
357:
355:
304:
298:
296:
278:
272:
270:
238:
232:
231:
201:
195:
193:
182:
156:Superrationality
81:operating system
1547:
1546:
1542:
1541:
1540:
1538:
1537:
1536:
1522:
1521:
1520:
1515:
1449:
1435:max^n algorithm
1408:
1404:William Vickrey
1364:Reinhard Selten
1319:Kenneth Binmore
1234:David K. Levine
1229:Daniel Kahneman
1196:
1190:
1166:Negamax theorem
1156:Minimax theorem
1134:
1095:Diner's dilemma
950:All-pay auction
916:
902:Stochastic game
854:Mean-field game
825:
818:
789:Markov strategy
725:
591:
583:
554:Sequential game
539:Information set
524:Game complexity
494:Congestion game
482:
476:
446:
431:10.1145/2601068
411:
407:
373:
364:
360:
329:10.2307/3214827
305:
301:
279:
275:
260:
239:
235:
202:
198:
183:
179:
175:
127:
103:
97:
77:synchronization
17:
16:Logical dilemma
12:
11:
5:
1545:
1535:
1534:
1517:
1516:
1514:
1513:
1508:
1503:
1498:
1493:
1488:
1483:
1478:
1473:
1468:
1463:
1457:
1455:
1451:
1450:
1448:
1447:
1442:
1437:
1432:
1427:
1422:
1416:
1414:
1410:
1409:
1407:
1406:
1401:
1396:
1391:
1386:
1381:
1376:
1371:
1369:Robert Axelrod
1366:
1361:
1356:
1351:
1346:
1344:Olga Bondareva
1341:
1336:
1334:Melvin Dresher
1331:
1326:
1324:Leonid Hurwicz
1321:
1316:
1311:
1306:
1301:
1296:
1291:
1286:
1281:
1276:
1271:
1266:
1261:
1259:Harold W. Kuhn
1256:
1251:
1249:Drew Fudenberg
1246:
1241:
1239:David M. Kreps
1236:
1231:
1226:
1224:Claude Shannon
1221:
1216:
1211:
1206:
1200:
1198:
1192:
1191:
1189:
1188:
1183:
1178:
1173:
1168:
1163:
1161:Nash's theorem
1158:
1153:
1148:
1142:
1140:
1136:
1135:
1133:
1132:
1127:
1122:
1117:
1112:
1107:
1102:
1097:
1092:
1087:
1082:
1077:
1072:
1067:
1062:
1057:
1052:
1047:
1042:
1037:
1032:
1027:
1022:
1020:Ultimatum game
1017:
1012:
1007:
1002:
1000:Dollar auction
997:
992:
987:
985:Centipede game
982:
977:
972:
967:
962:
957:
952:
947:
942:
940:Infinite chess
937:
932:
926:
924:
918:
917:
915:
914:
909:
907:Symmetric game
904:
899:
894:
892:Signaling game
889:
887:Screening game
884:
879:
877:Potential game
874:
869:
864:
856:
851:
846:
841:
836:
830:
828:
820:
819:
817:
816:
811:
806:
804:Mixed strategy
801:
796:
791:
786:
781:
776:
771:
766:
761:
756:
751:
746:
741:
735:
733:
727:
726:
724:
723:
718:
713:
708:
703:
698:
693:
688:
686:Risk dominance
683:
678:
673:
668:
663:
658:
653:
648:
643:
638:
633:
628:
623:
618:
613:
608:
603:
597:
595:
585:
584:
582:
581:
576:
571:
566:
561:
556:
551:
546:
541:
536:
531:
529:Graphical game
526:
521:
516:
511:
506:
501:
496:
490:
488:
484:
483:
475:
474:
467:
460:
452:
445:
444:
405:
386:(1): 111–122,
367:Weber, Richard
358:
323:(4): 839–851,
299:
273:
258:
233:
215:(3): 673–683,
196:
176:
174:
171:
170:
169:
163:
158:
153:
148:
143:
138:
133:
126:
123:
99:Main article:
96:
93:
38:
37:
15:
9:
6:
4:
3:
2:
1544:
1533:
1530:
1529:
1527:
1512:
1509:
1507:
1504:
1502:
1499:
1497:
1494:
1492:
1489:
1487:
1484:
1482:
1479:
1477:
1474:
1472:
1469:
1467:
1464:
1462:
1459:
1458:
1456:
1454:Miscellaneous
1452:
1446:
1443:
1441:
1438:
1436:
1433:
1431:
1428:
1426:
1423:
1421:
1418:
1417:
1415:
1411:
1405:
1402:
1400:
1397:
1395:
1392:
1390:
1389:Samuel Bowles
1387:
1385:
1384:Roger Myerson
1382:
1380:
1377:
1375:
1374:Robert Aumann
1372:
1370:
1367:
1365:
1362:
1360:
1357:
1355:
1352:
1350:
1347:
1345:
1342:
1340:
1337:
1335:
1332:
1330:
1329:Lloyd Shapley
1327:
1325:
1322:
1320:
1317:
1315:
1314:Kenneth Arrow
1312:
1310:
1307:
1305:
1302:
1300:
1297:
1295:
1294:John Harsanyi
1292:
1290:
1287:
1285:
1282:
1280:
1277:
1275:
1272:
1270:
1267:
1265:
1264:Herbert Simon
1262:
1260:
1257:
1255:
1252:
1250:
1247:
1245:
1242:
1240:
1237:
1235:
1232:
1230:
1227:
1225:
1222:
1220:
1217:
1215:
1212:
1210:
1207:
1205:
1202:
1201:
1199:
1193:
1187:
1184:
1182:
1179:
1177:
1174:
1172:
1169:
1167:
1164:
1162:
1159:
1157:
1154:
1152:
1149:
1147:
1144:
1143:
1141:
1137:
1131:
1128:
1126:
1123:
1121:
1118:
1116:
1113:
1111:
1108:
1106:
1103:
1101:
1098:
1096:
1093:
1091:
1088:
1086:
1083:
1081:
1078:
1076:
1073:
1071:
1068:
1066:
1065:Fair division
1063:
1061:
1058:
1056:
1053:
1051:
1048:
1046:
1043:
1041:
1040:Dictator game
1038:
1036:
1033:
1031:
1028:
1026:
1023:
1021:
1018:
1016:
1013:
1011:
1008:
1006:
1003:
1001:
998:
996:
993:
991:
988:
986:
983:
981:
978:
976:
973:
971:
968:
966:
963:
961:
958:
956:
953:
951:
948:
946:
943:
941:
938:
936:
933:
931:
928:
927:
925:
923:
919:
913:
912:Zero-sum game
910:
908:
905:
903:
900:
898:
895:
893:
890:
888:
885:
883:
882:Repeated game
880:
878:
875:
873:
870:
868:
865:
863:
861:
857:
855:
852:
850:
847:
845:
842:
840:
837:
835:
832:
831:
829:
827:
821:
815:
812:
810:
807:
805:
802:
800:
799:Pure strategy
797:
795:
792:
790:
787:
785:
782:
780:
777:
775:
772:
770:
767:
765:
764:De-escalation
762:
760:
757:
755:
752:
750:
747:
745:
742:
740:
737:
736:
734:
732:
728:
722:
719:
717:
714:
712:
709:
707:
706:Shapley value
704:
702:
699:
697:
694:
692:
689:
687:
684:
682:
679:
677:
674:
672:
669:
667:
664:
662:
659:
657:
654:
652:
649:
647:
644:
642:
639:
637:
634:
632:
629:
627:
624:
622:
619:
617:
614:
612:
609:
607:
604:
602:
599:
598:
596:
594:
590:
586:
580:
577:
575:
574:Succinct game
572:
570:
567:
565:
562:
560:
557:
555:
552:
550:
547:
545:
542:
540:
537:
535:
532:
530:
527:
525:
522:
520:
517:
515:
512:
510:
507:
505:
502:
500:
497:
495:
492:
491:
489:
485:
481:
473:
468:
466:
461:
459:
454:
453:
450:
440:
436:
432:
428:
424:
420:
416:
409:
401:
397:
393:
389:
385:
381:
380:
372:
368:
362:
354:
350:
346:
342:
338:
334:
330:
326:
322:
318:
314:
310:
303:
295:
291:
287:
283:
282:Alpern, Steve
277:
269:
265:
261:
259:0-7923-7468-1
255:
251:
247:
243:
242:Alpern, Steve
237:
230:
226:
222:
218:
214:
210:
206:
205:Alpern, Steve
200:
191:
187:
186:Alpern, Steve
181:
177:
167:
164:
162:
159:
157:
154:
152:
149:
147:
144:
142:
139:
137:
134:
132:
129:
128:
122:
120:
116:
115:deterministic
112:
108:
102:
92:
90:
86:
82:
78:
73:
71:
70:Richard Weber
67:
63:
62:Richard Weber
59:
55:
51:
47:
42:
35:
31:
26:
25:
24:
22:
1359:Peyton Young
1354:Paul Milgrom
1269:Hervé Moulin
1209:Amos Tversky
1151:Folk theorem
1129:
862:-player game
859:
784:Grim trigger
422:
418:
408:
383:
377:
361:
320:
316:
309:Weber, R. R.
302:
285:
276:
249:
236:
212:
208:
199:
189:
180:
146:Search games
110:
106:
104:
74:
65:
57:
53:
50:Steve Alpern
45:
43:
39:
33:
20:
18:
1476:Coopetition
1279:Jean Tirole
1274:John Conway
1254:Eric Maskin
1050:Blotto game
1035:Pirate game
844:Global game
814:Tit for tat
749:Bid shading
739:Appeasement
589:Equilibrium
569:Solved game
504:Determinacy
487:Definitions
480:game theory
246:Gal, Shmuel
166:Focal point
87:, and even
30:fixed place
1120:Trust game
1105:Kuhn poker
774:Escalation
769:Deterrence
759:Cheap talk
731:Strategies
549:Preference
478:Topics of
415:Zwick, Uri
173:References
1304:John Nash
1010:Stag hunt
754:Collusion
425:(3). 12.
353:122587972
288:, Wiley,
1526:Category
1445:Lazy SMP
1139:Theorems
1090:Deadlock
945:Checkers
826:of games
593:concepts
439:10718957
369:(2012),
311:(1990),
248:(2003),
188:(1976),
125:See also
83:design,
1197:figures
980:Chicken
834:Auction
824:Classes
400:2891149
345:1077533
337:3214827
268:2005053
229:1327232
68:= 3 by
437:
398:
351:
343:
335:
266:
256:
227:
111:robots
935:Chess
922:Games
435:S2CID
374:(PDF)
349:S2CID
333:JSTOR
616:Core
254:ISBN
105:The
34:they
19:The
1195:Key
427:doi
388:doi
325:doi
290:doi
217:doi
1528::
930:Go
433:.
423:10
421:.
396:MR
394:,
384:37
382:,
376:,
347:,
341:MR
339:,
331:,
321:27
319:,
315:,
264:MR
262:,
244:;
225:MR
223:,
213:33
211:,
121:.
79:,
860:n
471:e
464:t
457:v
441:.
429::
403:.
390::
356:.
327::
297:.
292::
271:.
219::
194:.
66:n
54:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.