使用消息配對人的算法

Question

想象一下，你有一羣人都想從這羣人中找到合作伙伴。每個人都可以向整個團體或任何特定人員發佈公告。目標是在可能的情況下它們都會成對出現。

新人可以進入組而配對過程正在進行。一旦兩個人儘可能優化配對，他們就會退出組隊。

每個人對每個其他人都有一個「分數」。人們應儘可能與更高分的合作伙伴配對。然而，更重要的是人們找到配對，而不是那些配對是嚴格最優的。因此，例如，讓兩個人「臨時配對」，然後等一會兒，看看是否有更好的伴侶出現，這是合理的。如果沒有，那麼將這兩者妥善配對，然後退出組。

沒有中央控制實體：所有的工作必須通過在人們之間傳遞消息（或廣播給整個組）來完成。

這樣做的最佳算法是什麼？

很顯然，我試圖避免的問題是，A隨機選擇B，並說「嘿，做我的搭檔」，同時B對C說「嘿，做我的搭檔」。此外，A不能只是宣佈「有人成爲我的伴侶！」因爲A會收到每個人的回覆，如果B還宣佈「有人成爲我的合作伙伴」，B是否應答A的聲明？ （a）這是關於找到一個「穩定」（嚴格最優）解決方案，這對我的問題是有用的，但不是必需的;（b）它假設組是固定的規模並沒有改變，而我的問題允許在「配對選舉」正在進行的同時加入新的參與者。

Answer 1

好像你只是需要一個「棒或扭曲」的權重爲每對允許'足夠好'出口，認爲「關閉時間在迪斯科舞廳」。

每個人有一些粘性係數= 0 開始啓動通過選擇一個臨時的合作伙伴（通過一些合理的啓發式/隨機哈希/其他）

過這樣的事情然後遍歷：

1. 如果你的臨時夥伴也選擇了你，你是一對
2. 如果你的臨時性伴侶還沒有選擇你，並且你「足夠粘」，他們仍然是你的臨時伴侶
3. if你的臨時搭檔還沒有選擇你呢，你是「不粘性不夠」：選擇其他合作伙伴
4. 如果求婚者有大約卡住了，認爲他們在下一輪
5. 更有吸引力，如果你還處於磨合，增加你的「粘性」

Answer 2

取決於涉及的人數，你可能能夠將所有傳入數據存儲在一個客戶端中，並在客戶端廣播時將其與消息一起發送。 例子：

，現在只有3人ABC

一個廣播

B存儲，{A，味精：XXX}

乙廣泛蒙上{A，味精：XXX} {我（ B），MSG：YYY}

A存儲，{B，MSG：YYY}

C存儲，{A，MSG：XXX}，{B，MSG：YYY}

d加入，以讓所有的人要求

A發送回撒施{B，味精：YYY} {我的（A），味精：XXX}

B回送{A，味精：XXX } {我的（B），味精：YYY}

C不是廣泛鑄造因此沒有發送任何

d處理所有傳入的請求，並做了一些分析，以確定該地區

一個可能的人和B匹配

A，B廣播去除A，B

C存儲，{}

d店，{}

Answer 3

您似乎沒有得到的方法用於說明的 「良好性」配對，或需要什麼信息來確定。例如，我可以知道我的「善良」與某人沒有發送信息嗎？我有完美的信息嗎？在這種情況下，有一些衆所周知的和快速的網絡流量類型配方，將找到最好的整體解決方案。只要每個人「獨立」地得出這個結論，就沒有問題了。

它也非常重要的知道這種善良措施是否是對稱的。分數（A，B）=分數（B，A）？如果可以建立，傳遞性也是有用的。但這似乎不太可能。

如果另一方面，我需要向某人發送消息以確定我們的身材，然後我們會遇到菜單類型問題。例如，查看Feynmann's Restaurant problem，如果您想從某些選項中獲得最大效用，它會告訴您應該在固定大小菜單中嘗試多少菜。

它也不清楚，如果你打算這是一個代表性的代理類型問題（每個人都必須使用最好的解決方案）或遊戲理論類型的解決方案（用戶應該最大限度地提高他們的個人得分）。例如，最好的解決方案可能是某種混合均衡，在這種混合均衡中，一些人播放他們的屬性，其他人制作他們的分數並且看起來最好。

這是一個引人入勝的問題，但我不確定它是否已經很好地定義了。