On the Structure of Game Provenance and its Applications

• URL: http://arxiv.org/abs/2410.05094v1
• Date: Mon, 7 Oct 2024 14:48:56 GMT
• Title: On the Structure of Game Provenance and its Applications
• Authors: Shawn Bowers, Yilin Xia, Bertram Ludäscher,
• Abstract summary: We study the fine-grain structure of game provenance. We identify seven edge types that give rise to new kinds of provenance, i.e. potential, actual, and primary.
• Score: 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.

Related papers

• Choices and their Provenance: Explaining Stable Solutions of Abstract Argumentation Frameworks [1.4064491732635236]
  We present a novel approach for extending this provenance to stable AF solutions.<n>Our approach identifies minimal sets of critical attacks, pinpointing choices and assumptions made by a stable model.
  arXiv  Detail & Related papers  (2025-06-01T17:09:55Z)
• The Aldous--Lyons Conjecture II: Undecidability [3.8370118222043694]
  We show that given a tailored non-local game $G$, it is undecidable to distinguish between the case where $G$ has a special kind of perfect strategy, and the case where every strategy for $G$ is far from being perfect. Using a reduction introduced in the companion paper [BCLV24], this undecidability result implies a negative answer to the Aldous--Lyons conjecture.
  arXiv  Detail & Related papers  (2024-12-30T22:59:56Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ with a complexity that is not governed by information exponents.
  arXiv  Detail & Related papers  (2024-06-03T17:56:58Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  We show the first algorithms for the problem of regression for generalized linear models (GLMs) in the presence of additive oblivious noise. We present an algorithm that tackles newthis problem in its most general distribution-independent setting. This is the first newalgorithmic result for GLM regression newwith oblivious noise which can handle more than half the samples being arbitrarily corrupted.
  arXiv  Detail & Related papers  (2023-09-20T21:41:59Z)
• Higher rank antipodality [0.0]
  Motivated by general probability theory, we say that the set $X$ in $mathbbRd$ is emphantipodal of rank $k$. For $k=1$, it coincides with the well-studied notion of (pairwise) antipodality introduced by Klee.
  arXiv  Detail & Related papers  (2023-07-31T17:15:46Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  We show that our algorithm achieves an $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ are the cardinalities of the state and action spaces
  arXiv  Detail & Related papers  (2023-05-15T05:37:32Z)
• On Computing Probabilistic Explanations for Decision Trees [4.406418914680962]
  "sufficient reasons" are a kind of explanation in which given a decision tree $T$ and an instance $x$, one explains the decision $T(x)$. Our paper settles the computational complexity of $delta$-sufficient-reasons over decision trees. We identify structural restrictions of decision trees that make the problem tractable, and show how SAT solvers might be able to tackle these problems in practical settings.
  arXiv  Detail & Related papers  (2022-06-30T21:58:31Z)
• Repeated Averages on Graphs [2.363388546004777]
  We prove that $frac(1-epsilon)2log2nlog n-O(n)$ is a general lower bound for all connected graphs on $n$ nodes. We also get sharp magnitude of $t_epsilon,1$ for several important families of graphs, including star, expander, dumbbell, and cycle.
  arXiv  Detail & Related papers  (2022-05-09T20:18:31Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  We present the first line of algorithms that require only $widetildemathcalO((XA+YB)/varepsilon2)$ episodes of play to find an $varepsilon$-approximate Nash equilibrium in two-player zero-sum games. This improves upon the best known sample complexity of $widetildemathcalO((X2A+Y2B)/varepsilon2)$ by a factor of $widetildemathcalO(maxX,
  arXiv  Detail & Related papers  (2022-02-03T18:18:28Z)
• Nonlocal games with noisy maximally entangled states are decidable [5.076419064097734]
  This paper considers a special class of nonlocal games $(G,psi)$, where $G$ is a two-player one-round game. In the game $(G,psi)$, the players are allowed to share arbitrarily many copies of $psi$. It is feasible to approximately compute $omega*(G,psi)$ to an arbitrarily precision.
  arXiv  Detail & Related papers  (2021-08-20T12:25:55Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We design novel cutting-plane algorithms with low "regret" -- the total distance between the true point $w*$ and the hyperplanes the separation oracle returns.
  arXiv  Detail & Related papers  (2021-06-09T05:39:05Z)
• Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
  We study efficient estimation and detection of a planted vector $v$ whose $ell_4$ norm differs from that of a Gaussian vector with the same $ell$ norm. We show that in the regime $n rho gg sqrtN$, any spectral method from a large class (and more generally, any low-degree of the input) fails to detect the planted vector.
  arXiv  Detail & Related papers  (2021-05-31T16:10:49Z)
• A General Derivative Identity for the Conditional Mean Estimator in Gaussian Noise and Some Applications [128.4391178665731]
  Several identities in the literature connect $E[bf X|bf Y=bf y]$ to other quantities such as the conditional variance, score functions, and higher-order conditional moments. The objective of this paper is to provide a unifying view of these identities.
  arXiv  Detail & Related papers  (2021-04-05T12:48:28Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  We focus on self-play algorithms which learn the optimal policy by playing against itself without any direct supervision. We propose an optimistic variant of the emphNash Q-learning algorithm with sample complexity $tildemathcalO(SAB)$, and a new emphNash V-learning algorithm with sample complexity $tildemathcalO(S(A+B))$.
  arXiv  Detail & Related papers  (2020-06-22T05:00:13Z)
• Completing the quantum formalism in a contextually objective framework [0.0]
  In standard quantum mechanics, a state vector $| psi rangle$ may belong to infinitely many different orthogonal bases. In an idealized case, measuring $A$ again and again will give repeatedly the same result, with the same eigenvalue. The answer is obviously no, since $| psi rangle$ does not specify the full observable $A$ that allowed us to obtain $mu$.
  arXiv  Detail & Related papers  (2020-03-06T10:27:10Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.