論文の概要: On the Structure of Game Provenance and its Applications
- arxiv url: http://arxiv.org/abs/2410.05094v1
- Date: Mon, 7 Oct 2024 14:48:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-02 00:28:18.646656
- Title: On the Structure of Game Provenance and its Applications
- Title（参考訳）: ゲームプロヴァンスの構造とその応用について
- Authors: Shawn Bowers, Yilin Xia, Bertram Ludäscher,
- Abstract要約: ゲーム前駆体の微細粒構造について検討する。
我々は、新しい種類の証明をもたらす7つのエッジタイプ、すなわちポテンシャル、現実、プライマリを識別する。
- 参考スコア（独自算出の注目度）: 1.4064491732635236
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Provenance in databases has been thoroughly studied for positive and for recursive queries, then for first-order (FO) queries, i.e., having negation but no recursion. Query evaluation can be understood as a two-player game where the opponents argue whether or not a tuple is in the query answer. This game-theoretic approach yields a natural provenance model for FO queries, unifying how and why-not provenance. Here, we study the fine-grain structure of game provenance. A game $G=(V,E)$ consists of positions $V$ and moves $E$ and can be solved by computing the well-founded model of a single, unstratifiable rule: \[ \text{win}(X) \leftarrow \text{move}(X, Y), \neg \, \text{win}(Y). \] In the solved game $G^{\lambda}$, the value of a position $x\,{\in}\,V$ is either won, lost, or drawn. This value is explained by the provenance $\mathscr{P}$(x), i.e., certain (annotated) edges reachable from $x$. We identify seven edge types that give rise to new kinds of provenance, i.e., potential, actual, and primary, and demonstrate that "not all moves are created equal". We describe the new provenance types, show how they can be computed while solving games, and discuss applications, e.g., for abstract argumentation frameworks.
- Abstract（参考訳）: データベースの出現は、肯定的および再帰的なクエリのために徹底的に研究され、その後、一階述語(FO)クエリ、すなわち、否定するが再帰しないクエリに対して研究されている。
クエリ評価は、タプルがクエリ応答に含まれるかどうかを議論する2人プレイヤゲームとして理解することができる。
このゲーム理論のアプローチは、FOクエリの自然なプロファイランスモデルをもたらし、どのようにして、なぜプロファイランスではないのかを統一する。
本稿では,ゲーム前駆体の微細粒構造について検討する。
ゲーム $G=(V, E)$ は、位置 $V$ と移動 $E$ で構成され、単一で不安定な規則の確立したモデルを計算することで解決できる: \[ \text{win}(X) \leftarrow \text{move}(X, Y) \neg \, \text{win}(Y) 。
解決されたゲーム $G^{\lambda}$ では、位置 $x\,{\in}\,V$ の値は、勝ち、負け、引き分けのいずれかである。
この値は前置詞 $\mathscr{P}$(x) で説明され、すなわち、ある(注釈付き)エッジが$x$から到達可能である。
我々は、新しい種類の証明をもたらす7つのエッジタイプ、すなわちポテンシャル、現実、プライマリを識別し、「すべての動きが等しくなるわけではない」ことを示す。
本稿では,新しい証明型について述べるとともに,ゲーム解決時にどのように計算可能かを示し,抽象的な議論フレームワークのためのアプリケーション,例えばアプリケーションについて議論する。
関連論文リスト
- Distribution-Independent Regression for Generalized Linear Models with
Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。
本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。
これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文 参考訳（メタデータ） (2023-09-20T21:41:59Z) - Higher rank antipodality [0.0]
一般確率論に動機づけられて、集合 $X$ in $mathbbRd$ はランク $k$ のエンファンティポッドであると言う。
k=1$ の場合、Klee が導入した(ペアワイズで)反ポッド性の概念と一致する。
論文 参考訳（メタデータ） (2023-07-31T17:15:46Z) - Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳（メタデータ） (2023-05-15T05:37:32Z) - On Computing Probabilistic Explanations for Decision Trees [4.406418914680962]
十分な理由は、決定木を$T$とインスタンスを$x$とすると、決定を$T(x)$とします。
本稿では,決定木に対する$delta$sufficient-reasonsの計算複雑性について検討する。
決定木の構造的制約を識別し,SATソルバがこれらの問題に実際にどのように対処できるかを示す。
論文 参考訳（メタデータ） (2022-06-30T21:58:31Z) - Repeated Averages on Graphs [2.363388546004777]
我々は$frac(1-epsilon)2log2nlog n-O(n)$が$n$ノード上のすべての連結グラフに対する一般的な下界であることを証明する。
また、星、膨張星、ダンベル、サイクルなど、いくつかの重要なグラフの族に対して、$t_epsilon,1$の急激な等級も得られる。
論文 参考訳（メタデータ） (2022-05-09T20:18:31Z) - 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) - Nonlocal games with noisy maximally entangled states are decidable [5.076419064097734]
本稿では,非ローカルゲームの特別なクラスである$(G,psi)$について考察する。
ゲーム $(G,psi)$ では、プレイヤーは任意の数の $psi$ のコピーを共有することができる。
任意の精度で$omega*(G,psi)$を計算できる。
論文 参考訳（メタデータ） (2021-08-20T12:25:55Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z) - Completing the quantum formalism in a contextually objective framework [0.0]
標準的な量子力学では、状態ベクトル $| psi ラングル$ は無限に多くの異なる直交基底に属する。
理想化された場合、$A$を何度も測定すると、同じ固有値で同じ結果が繰り返される。
なぜなら、$| psi rangle$は、$mu$を取得できる完全なオブザーバブルな$A$を指定していないからである。
論文 参考訳（メタデータ） (2020-03-06T10:27:10Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。