一貫性のない関係から全体または半順序を生成する
要素のセットから全順序を構築したいとします。 $E$、ただし、比較関数は非決定論的な結果を生成します。セット内の各要素が少なくとも1回表されるように、比較関数を繰り返し適用して、要素のペア（e、e）のリストを作成します。
この入力を使用して全順序を作成するにはどうすればよいですか？ここで適用できるアルゴリズムのクラスは何ですか？
より明確にするために、具体的な例を示します。
最高のピザのトッピングは何ですか？
私の要素のセット $E$ ペパロニ、チーズ、マッシュルーム、パイナップル、ピーマン、オリーブなど、人気のピザのトッピングが含まれています。
次に、友達ごとに、ランダムなサイズのトッピングのサブセットを選び、友達に最高から最低の順に並べるように依頼します。私の友人は忠実に返信し、私のアルゴリズムの入力を作成します。
- チーズ、ペパロニ、オリーブ
- チーズ、パイナップル、きのこ、オリーブ
- ピーマン、きのこ、オリーブ
- ペパロニ、チーズ、オリーブ
- チーズ、ピーマン
ここにはあいまいな注文があるようですが（オリーブが最悪であることに誰もが同意しています）、私の友人は、チーズとペパロニのどちらがピザのトッピングに適しているかについて合意に達していません。入力のどこでアイテムが発生するか、およびそれらがどのくらいの頻度で発生するかを考えると、おそらくこのような注文を作成します。
- チーズ>ペパロニ>ピーマン>パイナップル>きのこ>オリーブ
これを形式化して、はるかに大きな入力で機能させる方法がわかりません。
解決策にはおそらくグラフと重み付きエッジが含まれると思いますが、これが名前付きの研究領域であるかどうかを認識するためのグラフアルゴリズムについての十分な知識が不足しています。私はすでに「トポロジカルソート」に出くわしましたが、それは有向非巡回グラフでのみ機能し、DAGを生成できない入力に特に興味があります。
また、この問題は、選出された代表者への投票に似ているように思われることにも気づきました。実際、それは同じクラスの問題ですか？
回答
より多くのコンテキストとより多くのモデリングなしで言うのは難しいです。比較関数の結果が（隠された）望ましい全順序にどのように関連するかについて、いくつかの仮定が必要になります。
Bradley-Terry-Luceモデルが必要になる可能性があります。もしそうなら、多くの標準的なアルゴリズムがあります。も参照してくださいhttps://cs.stackexchange.com/a/85204/755。
Eloなどのランキングシステムが必要になる可能性があります。
IRV、コンドルセ方式、ボルダカウント、またはその他の多くのランク付けされた投票システムが必要になる可能性があります。それらにはすべて、さまざまな欠陥とトレードオフがあります。アローの定理や非推移性の問題（たとえば、友達の個々の好みのそれぞれが推移的である場合でも、全順序である場合など）を参照してください。それらすべてと一致するグローバルな全順序が存在するという保証はありません）。