論文の概要: Query Complexity of Tournament Solutions
- arxiv url: http://arxiv.org/abs/1611.06189v4
- Date: Sat, 27 Jan 2024 15:16:16 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-31 01:26:00.899239
- Title: Query Complexity of Tournament Solutions
- Title（参考訳）: トーナメントソリューションのクエリー複雑性
- Authors: Arnab Maiti and Palash Dey
- Abstract要約: 我々は、コペランド集合、スレーター集合、マルコフ集合、バイパルチザン集合、未発見集合、バンクス集合、および最上位サイクルを見つけるアルゴリズムが、最悪の場合、$Omega(n2)$ edgesを問う必要があることを示す。
肯定的な面では、入力トーナメントの上位サイクルのサイズが最大で1kドルであれば、上記のすべてのトーナメントソリューションが見つかることを証明して、クエリの複雑さを低く抑えることができる。
- 参考スコア（独自算出の注目度）: 12.192470787877594
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A directed graph where there is exactly one edge between every pair of
vertices is called a {\em tournament}. Finding the "best" set of vertices of a
tournament is a well studied problem in social choice theory. A {\em tournament
solution} takes a tournament as input and outputs a subset of vertices of the
input tournament. However, in many applications, for example, choosing the best
set of drugs from a given set of drugs, the edges of the tournament are given
only implicitly and knowing the orientation of an edge is costly. In such
scenarios, we would like to know the best set of vertices (according to some
tournament solution) by "querying" as few edges as possible. We, in this paper,
precisely study this problem for commonly used tournament solutions: given an
oracle access to the edges of a tournament T, find $f(T)$ by querying as few
edges as possible, for a tournament solution f. We first show that the set of
Condorcet non-losers in a tournament can be found by querying $2n-\lfloor \log
n \rfloor -2$ edges only and this is tight in the sense that every algorithm
for finding the set of Condorcet non-losers needs to query at least $2n-\lfloor
\log n \rfloor -2$ edges in the worst case, where $n$ is the number of vertices
in the input tournament. We then move on to study other popular tournament
solutions and show that any algorithm for finding the Copeland set, the Slater
set, the Markov set, the bipartisan set, the uncovered set, the Banks set, and
the top cycle must query $\Omega(n^2)$ edges in the worst case. On the positive
side, we are able to circumvent our strong query complexity lower bound results
by proving that, if the size of the top cycle of the input tournament is at
most $k$, then we can find all the tournament solutions mentioned above by
querying $O(nk + \frac{n\log n}{\log(1-\frac{1}{k})})$ edges only.
- Abstract（参考訳）: すべての頂点の対の間にちょうど1つの辺が存在する有向グラフは、 {\em tournament} と呼ばれる。
トーナメントの「最高の」頂点集合を見つけることは、社会的選択理論においてよく研究されている問題である。
トーナメントソリューションは、入力としてトーナメントを受け取り、入力トーナメントの頂点のサブセットを出力する。
しかし、例えば、与えられた薬物群から最高の薬物群を選択するなど、多くの応用において、トーナメントのエッジは暗黙的にのみ与えられ、エッジの向きを知ることはコストがかかる。
このようなシナリオでは、最小限のエッジを"クエリ"することで、最高の頂点セット(トーナメントソリューションによっては)を知りたいと思っています。
本稿では,トーナメントTのエッジへのオラクルアクセスが与えられた場合,トーナメントソリューションfに対して,できるだけ少数のエッジを問合せして$f(T)$を求める。
最初に、トーナメントにおけるコンドルセットの非ロッサー集合は、2n-\lfloor \log n \rfloor -2$ edgeのみを問うことで見つけることができ、これは、コンドルセットの非ロッサー集合を見つけるアルゴリズムが少なくとも2n-\lfloor \log n \rfloor -2$ edgesを問う必要があるという意味において厳密である。
その後、他の人気のあるトーナメントソリューションを研究し、コープランドセット、スレーターセット、マルコフセット、二パルチザンセット、暴露セット、バンクセット、トップサイクルを見つけるアルゴリズムが最悪の場合には$\omega(n^2)$ edgesをクエリする必要があることを示した。
正の面では、入力トーナメントの最上位サイクルのサイズが最大$k$であるなら、$o(nk + \frac{n\log n}{\log(1-\frac{1}{k})})$エッジのみをクエリすることで、上記のすべてのトーナメントソリューションを見つけることができる、という証明によって、クエリの複雑さの低さを回避できる。
関連論文リスト
- On the communication complexity of finding a king in a tournament [0.5999777817331317]
エッジが2つのプレイヤー間で分割されるタスクの通信複雑性について検討する。
トーナメントのソースを見つけることは、無向グラフ上のよく研究されているClique vs. Independent Set(CIS)問題と同等であることを示す。
論文 参考訳（メタデータ） (2024-02-22T18:11:19Z) - On the Complexity of First-Order Methods in Stochastic Bilevel
Optimization [9.649991673557167]
両レベル最適化における定常点を求める問題は、下層問題に制約がなく、強い凸がある場合に考慮する。
既存のアプローチは、それらの分析を低レベルの解を知っているジェニーアルゴリズムに結びつける。
我々は、$O(epsilon-6), O(epsilon-4)$ 1次$y*$-aware oraclesを使って、$epsilon$固定点に収束する単純な一階法を提案する。
論文 参考訳（メタデータ） (2024-02-11T04:26:35Z) - Randomized and quantum query complexities of finding a king in a
tournament [0.0]
決定論的クエリの複雑さについて、最もよく知られた上限と下限を示す。
我々の貢献は、*randomized* および *quantum* クエリモデルにおける Theta(n) および Theta(sqrtn) の*tight* 境界(対数要素まで)を示すことである。
論文 参考訳（メタデータ） (2023-08-04T17:21:11Z) - A Theory of Tournament Representations [4.969254618158096]
我々はパラメトリックトーナメント表現を理解するための新しい理論を開発した。
私たちの最初の貢献は、$d$次元表現から生じるトーナメントのクラスを構造的に特徴づけることです。
さらに2ドルのトーナメントは、関連する禁止されたフリップクラスがわずか2ドルのトーナメントを含むことを示すことで、完全にランク付けします。
論文 参考訳（メタデータ） (2021-10-06T09:08:00Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Adversarial Dueling Bandits [85.14061196945599]
本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。
学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。
我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
論文 参考訳（メタデータ） (2020-10-27T19:09:08Z) - Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。
低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
論文 参考訳（メタデータ） (2020-10-13T17:26:09Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z) - Explicit Best Arm Identification in Linear Bandits Using No-Regret
Learners [17.224805430291177]
線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。
そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-13T05:00:01Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。