ランデブージレンマ は論理的なジレンマであり、典型的には次のように定式化される。
二人は初めて訪れる公園でデートをすることになった。別々に公園に到着した二人は、その広さに驚き、お互いを見つけられなくなってしまう。このような状況で、それぞれが決められた場所で相手が見つけてくれるのを待つか、相手 が どこかで待っていることを期待して探し始めるか、どちらかを選ばなければならない。 両者が待つことを選択した場合、二人は決して出会うことはない。両者が歩くことを選択した場合、出会う可能性もあれば、出会わない可能性もある。一方が待つことを選択し、もう一方が歩くことを選択した場合、理論的には最終的に出会うことは確実である。しかし実際には、それが保証されるには時間がかかりすぎるかもしれない。そこで問題となるのは、出会う確率を最大化するために、二人はどのような戦略を選択すべきかということである。
この種の問題の例としては、ランデブー問題 が挙げられます。これらの問題は、1976 年にSteve Alpernによって非公式に初めて紹介され [ 1 ] [ 2 ]。 [ 3 ]。n 個の 離散的な場所で行われる対称ランデブー問題(モーツァルトカフェランデブー問題 と呼ばれることもあります) [ 4 ] Richard Weber と Eddie Anderson が最適な戦略を予想しました[ 5 ] 。2012 年に、 n = 3 の場合について Richard Weber によって予想が証明されました[ 6 ]
ランデブー問題は、理論的に興味深い問題であるだけでなく、同期 、オペレーティングシステム 設計、オペレーションズリサーチ 、さらには捜索救助 活動の計画といった分野に応用される現実世界の問題も含まれる。
決定論的ランデブー問題 決定論的ランデブー問題 は、プレイヤーまたはロボットが 決定論的な 一連の指示に従って互いを見つけなければならないランデブー問題の変種です。各ロボットは同じ指示シーケンスに従いますが、対称性を破る ために各ロボットに割り当てられた固有のラベルが使用されます。[ 7 ]
参考文献 ↑ アルパーン、スティーブ (1976)、かくれんぼゲーム 、セミナー、Institut fur Hohere Studien、ウィーン、7 月 26 日↑ Alpern, Steve (1995), "ランデブー探索問題", SIAM Journal on Control and Optimization , 33 (3): 673–683 , doi : 10.1137/S0363012993249195 , MR 1327232 ↑ Alpern, Steve ; Gal, Shmuel (2003), 『探索ゲームとランデブーの理論』 、International Series in Operations Research & Management Science、第 55巻、ボストン、マサチューセッツ州：Kluwer Academic Publishers、 ISBN 0-7923-7468-1 MR 2005053 ↑ Alpern, Steve (2011), "ランデブー探索ゲーム", Cochran, James J. (編), Wiley Encyclopedia of Operations Research and Management Science , Wiley, doi : 10.1002/9780470400531.eorms0720 ↑ Anderson, EJ; Weber, RR (1990)、 「離散的な場所におけるランデブー問題」 、 Journal of Applied Probability 、 27 (4): 839–851 、 doi : 10.2307/3214827 、 JSTOR 3214827 、 MR 1077533 、 S2CID 122587972 ↑ Weber, Richard (2012), "3 つの場所における最適な対称ランデブー探索" (PDF) , Mathematics of Operations Research , 37 (1): 111– 122, doi : 10.1287/moor.1110.0528 , MR 2891149 ↑ Ta-Shma, Amnon; Zwick, Uri (2014年4月)「決定論的ランデブー、宝探し、および強力な普遍的探索シーケンス」 ACM Transactions on Algorithms . 10 (3). 12. doi : 10.1145/2601068 . S2CID 10718957 .
