ランダムな両側マッチング

ランダムツーサイド マッチングは、2 つのグループのメンバーをランダムに組み合わせるプロセスです。スポーツでは、ノックアウト トーナメントでチームをマッチングするためによく使用されます。このコンテキストでは、ボウルからボールを​​ランダムに引き、各ボールがチーム名を表すため、 抽選と呼ばれることがよくあります。

UEFAチャンピオンズリーグのベスト16では、ランダムな2面マッチングが行われます。 ^{[1] [2]} 8つのグループ内でいくつかの試合が行われた後、グループ優勝チームとグループ準優勝チームがチャンピオンズリーグに進みます。UEFAのルールでは、各優勝チームは準優勝チームとペアになる必要があります。さらなる制約がなければ、この問題は優勝チームのランダムな順列を見つけることで簡単に解決できます。しかし、UEFAのルールでは、同じグループの2チームをペアにすることはできない、同じ協会の2チームをペアにすることはできないという、さらに2つの制約が課せられます。したがって、目標は不完全二部グラフでランダムなマッチングを選択することです。

UEFA の仕組みでは、異なるボウルから複数の抽選が行われます。最初は次のようになります。

• ボウル 1。各ボールはグループ準優勝者 1 名を表す同一のボールが入っています。
• ボウル 2 は最初は空ですが、後で満たして再度満たします。
• ボウル A から H まで、それぞれがグループの優勝者を表し、優勝者の名前が書かれた 7 個のボールが入っています。

抽選は次のように進行します。

• ボウル 1 からボールが抽選され、次点者の名前が表示されます。
• コンピューター プログラムは、UEFA の規則に従って、抽選された次点チームと組み合わせることができるすべての優勝チームを表示します。このとき、現在の制約だけでなく、将来の次点チームに対する制約も考慮されます。
• 勝者候補を表すボウル A から H までのいくつかから、ボールが 1 つ取り出され、ボウル 2 に入れられます。
• ボウル 2 のボールはシャッフルされます。1 つのボールが抽選され、それが前回抽選された次点者と一致する勝者を表します。
• ボウル 2 が空になり、このプロセスが 8 ラウンド繰り返されます。

この手順では、単にランダムにマッチングを選択する場合とは異なる確率が得られます。これにより、異なるグループのマッチング確率に歪みが生じ、疑惑や陰謀説が生じます。^{[1] [2]}

FIFAワールドカップでも、もう一つの2面マッチングが行われます。^{[3] [4]}まず、準優勝者がランダムな順番で抽選されます。次に、各優勝者が順番に抽選され、制約に従ってマッチングできる順番の最初の準優勝者とマッチングされます。

この抽選も、均一ランダムマッチングに比べて歪んだ確率を生み出します。^{[3] [4]}

• 公平なランダム割り当て- 一方的なマッチング - 異なる好みを持つエージェントにアイテムを割り当てます。