Daily Arxiv

世界中で発行される人工知能関連の論文をまとめるページです。
このページはGoogle Geminiを活用して要約し、非営利で運営しています。
論文の著作権は著者および関連機関にあり、共有する際は出典を明記してください。

Recognizing and Eliciting Weakly Single Crossing Profiles on Trees

Created by
  • Haebom

作者

Palash Dey

概要

本論文は、社会選択理論でよく研究された単一のクロスドメインの一般化であるツリー上の弱い単一クロスドメインを提示し研究する。このドメインに属する嗜好プロファイルを認識する多項時間アルゴリズムを設計し、嗜好に逐次アクセスすることができ、基底単一クロスツリー構造が事前にわからない場合でも機能する効率的な情報収集アルゴリズムを開発する。さらに、投票者の数が候補者の数よりもはるかに多い場合、情報収集アルゴリズムの照会の複雑さに対する一致する下限を証明する。ランダムなクエリが許可されているときに単一のクロスプロファイルを収集するために、どのアルゴリズムがクエリする必要があるクエリの数について、$ \ Omega(m ^ 2 \ log n)$の下限を証明します。これは、以前の論文の未解決の問題を解決し、ランダムなクエリが許可されたときの好み情報収集アルゴリズムの最適性を証明します。

Takeaways、Limitations

Takeaways:ツリー上の弱い単一クロスドメインの効率的な認識と情報収集アルゴリズムを提示し、社会選択の問題解決に貢献します。ランダムなクエリが許可されている場合は、既存のアルゴリズムの最適性を証明し、以前の研究の未解決の問題を解決します。
Limitations:アルゴリズムのパフォーマンスは、投票者数と候補者数の比率によって異なります。特定の条件(投票者数が候補者よりもはるかに多い場合)の下限証明に限定され、他の条件ではアルゴリズムの効率が異なる可能性があります。
👍