論文の概要: A Theory of Tournament Representations

• arxiv url: http://arxiv.org/abs/2110.05188v2
• Date: Tue, 12 Oct 2021 07:34:00 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-17 13:16:39.623629
• Title: A Theory of Tournament Representations
• Title（参考訳）: トーナメント表現の理論
• Authors: Arun Rajkumar, Vishnu Veerathu and Abdul Bakey Mir
• Abstract要約: 我々はパラメトリックトーナメント表現を理解するための新しい理論を開発した。 私たちの最初の貢献は、$d$次元表現から生じるトーナメントのクラスを構造的に特徴づけることです。 さらに2ドルのトーナメントは、関連する禁止されたフリップクラスがわずか2ドルのトーナメントを含むことを示すことで、完全にランク付けします。
• 参考スコア（独自算出の注目度）: 4.969254618158096
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Real world tournaments are almost always intransitive. Recent works have noted that parametric models which assume $d$ dimensional node representations can effectively model intransitive tournaments. However, nothing is known about the structure of the class of tournaments that arise out of any fixed $d$ dimensional representations. In this work, we develop a novel theory for understanding parametric tournament representations. Our first contribution is to structurally characterize the class of tournaments that arise out of $d$ dimensional representations. We do this by showing that these tournament classes have forbidden configurations which must necessarily be union of flip classes, a novel way to partition the set of all tournaments. We further characterise rank $2$ tournaments completely by showing that the associated forbidden flip class contains just $2$ tournaments. Specifically, we show that the rank $2$ tournaments are equivalent to locally-transitive tournaments. This insight allows us to show that the minimum feedback arc set problem on this tournament class can be solved using the standard Quicksort procedure. For a general rank $d$ tournament class, we show that the flip class associated with a coned-doubly regular tournament of size $\mathcal{O}(\sqrt{d})$ must be a forbidden configuration. To answer a dual question, using a celebrated result of \cite{forster}, we show a lower bound of $\mathcal{O}(\sqrt{n})$ on the minimum dimension needed to represent all tournaments on $n$ nodes. For any given tournament, we show a novel upper bound on the smallest representation dimension that depends on the least size of the number of unique nodes in any feedback arc set of the flip class associated with a tournament. We show how our results also shed light on upper bound of sign-rank of matrices.
• Abstract（参考訳）: 現実世界のトーナメントはほとんど常に非定型である。 最近の研究によると、d$ 次元のノード表現を仮定したパラメトリックモデルは、非推移的なトーナメントを効果的にモデル化できる。 しかし、固定された$d$次元表現から生じるトーナメントのクラスの構造については何も分かっていない。 本研究では,パラメトリックトーナメント表現を理解するための新しい理論を開発する。 私たちの最初の貢献は、$d$次元表現から生じるトーナメントのクラスを構造的に特徴づけることです。 これらのトーナメントクラスは、必ずしもフリップクラスの統一でなければならない構成を禁止しており、これはすべてのトーナメントのセットを分割する新しい方法である。 さらに、関連する禁制のフリップクラスがわずか2ドルのトーナメントを含んでいることを示すことで、2ドルのトーナメントを完全に特徴づける。 具体的には、ランキング2ドルのトーナメントは、地域横断トーナメントと同等であることを示す。 この知見は,このトーナメントクラスにおける最小フィードバック節集合問題を,標準Quicksortプロシージャを用いて解くことができることを示す。 一般的な階数$d$トーナメントクラスの場合、サイズ$\mathcal{O}(\sqrt{d})$の2倍正規トーナメントに関連するフリップクラスは禁制の構成でなければならないことを示す。 二重質問に答えるためには、 \cite{forster} の有名な結果を用いて、$n$ ノード上のすべてのトーナメントを表すのに必要な最小次元に対して、$\mathcal{o}(\sqrt{n})$ の下限を示す。 任意のトーナメントにおいて、トーナメントに関連するフリップクラスのフィードバックアーク集合における一意ノードの数の最小サイズに依存する最小の表現次元上の新しい上限を示す。 我々の結果は、行列の符号ランクの上限にも光を当てている。

関連論文リスト

• How Does Variance Shape the Regret in Contextual Bandits? [59.8472760881411]
  一般関数近似を用いた文脈的包帯について考察する。 共振器次元 $d_textelu$-$play が分散依存境界において重要な役割を果たすことを示す。
  論文  参考訳（メタデータ） (2024-10-16T16:20:07Z)
• The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
  バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。 我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-16T12:11:09Z)
• On the communication complexity of finding a king in a tournament [0.5999777817331317]
  エッジが2つのプレイヤー間で分割されるタスクの通信複雑性について検討する。 トーナメントのソースを見つけることは、無向グラフ上のよく研究されているClique vs. Independent Set(CIS)問題と同等であることを示す。
  論文  参考訳（メタデータ） (2024-02-22T18:11:19Z)
• 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)
• Adapting to game trees in zero-sum imperfect information games [41.4836057085788]
  不完全な情報ゲーム(IIG)は、各プレイヤーが現在の遊技状態を部分的に観察するゲームである。 我々は,ゼロサムIIGにおいて,軌道フィードバックによる自己プレイを通じて,$epsilon$-optimal Strategyを学習する方法を研究する。
  論文  参考訳（メタデータ） (2022-12-23T19:45:25Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。 我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。 先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
  論文  参考訳（メタデータ） (2022-06-17T12:58:58Z)
• Efficient $\Phi$-Regret Minimization in Extensive-Form Games via Online Mirror Descent [49.93548413166884]
  $Phi$-Hedgeは、正規形式ゲーム(NFG)のための大規模な平衡を学習できる汎用アルゴリズムである。 EFGにおけるNash Equilibria(ゼロサム設定)、Normal-Form Coarse Correlated Equilibria(NFCCE)、Extensive-Form Correlated Equilibria(EFCE)の学習に$Phi$-Hedgeが直接利用できることを示す。 それらの設定において、emph$Phi$-Hedgeアルゴリズムは標準ミラーDescent(OMD)アルゴリズムと等価であることを示す。
  論文  参考訳（メタデータ） (2022-05-30T17:58:06Z)
• Merging Knockout and Round-Robin Tournaments: A Flexible Linear Elimination Tournament Design [0.0]
  本稿では,人気のあるノックアウトトーナメントとラウンドロビントーナメントを組み合わせた新しいトーナメント構造を提案する。 分断的排除と排除の極端さとは対照的に,我々のトーナメントは,参加者をできるだけ直線的に排除することを目的としている。
  論文  参考訳（メタデータ） (2022-03-22T19:36:40Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• Adversarial Dueling Bandits [85.14061196945599]
  本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2020-10-27T19:09:08Z)
• Query Complexity of Tournament Solutions [12.192470787877594]
  我々は、コペランド集合、スレーター集合、マルコフ集合、バイパルチザン集合、未発見集合、バンクス集合、および最上位サイクルを見つけるアルゴリズムが、最悪の場合、$Omega(n2)$ edgesを問う必要があることを示す。 肯定的な面では、入力トーナメントの上位サイクルのサイズが最大で1kドルであれば、上記のすべてのトーナメントソリューションが見つかることを証明して、クエリの複雑さを低く抑えることができる。
  論文  参考訳（メタデータ） (2016-11-18T18:19:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。