Hyper Strategy Logic

• URL: http://arxiv.org/abs/2403.13741v1
• Date: Wed, 20 Mar 2024 16:47:53 GMT
• Title: Hyper Strategy Logic
• Authors: Raven Beutner, Bernd Finkbeiner,
• Abstract summary: Strategy logic (SL) is a powerful temporal logic that enables strategic reasoning in multi-agent systems. We present Hyper Strategy Logic (HyperSL), a strategy logic where the outcome of multiple strategy profiles can be compared w.r.t. a hyperproperty. We show that HyperSL can capture important properties that cannot be expressed in SL, including non-interference, quantitative Nash equilibria, optimal adversarial planning, and reasoning under imperfect information.
• Score: 4.726777092009553
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Strategy logic (SL) is a powerful temporal logic that enables strategic reasoning in multi-agent systems. SL supports explicit (first-order) quantification over strategies and provides a logical framework to express many important properties such as Nash equilibria, dominant strategies, etc. While in SL the same strategy can be used in multiple strategy profiles, each such profile is evaluated w.r.t. a path-property, i.e., a property that considers the single path resulting from a particular strategic interaction. In this paper, we present Hyper Strategy Logic (HyperSL), a strategy logic where the outcome of multiple strategy profiles can be compared w.r.t. a hyperproperty, i.e., a property that relates multiple paths. We show that HyperSL can capture important properties that cannot be expressed in SL, including non-interference, quantitative Nash equilibria, optimal adversarial planning, and reasoning under imperfect information. On the algorithmic side, we identify an expressive fragment of HyperSL with decidable model checking and present a model-checking algorithm. We contribute a prototype implementation of our algorithm and report on encouraging experimental results.

Related papers

• Paths to Equilibrium in Games [6.812247730094933]
  We study sequences of strategies satisfying a pairwise constraint inspired by policy updating in reinforcement learning. Our analysis reveals a counterintuitive insight that reward deteriorating strategic updates are key to driving play to equilibrium along a satisficing path.
  arXiv  Detail & Related papers  (2024-03-26T19:58:39Z)
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach [57.788675205519986]
  We learn high-quality traces from POMDP executions generated by any solver. We exploit data- and time-efficient Indu Logic Programming (ILP) to generate interpretable belief-based policy specifications. We show that learneds expressed in Answer Set Programming (ASP) yield performance superior to neural networks and similar to optimal handcrafted task-specifics within lower computational time.
  arXiv  Detail & Related papers  (2024-02-29T15:36:01Z)
• On Alternating-Time Temporal Logic, Hyperproperties, and Strategy Sharing [5.584060970507506]
  We show that HyperATL$*_S$ is a rich specification language that captures important AI-related properties. We implement our model-checking algorithm in a tool we call HyMASMC and evaluate it on a range of benchmarks.
  arXiv  Detail & Related papers  (2023-12-19T18:37:39Z)
• StrategyLLM: Large Language Models as Strategy Generators, Executors, Optimizers, and Evaluators for Problem Solving [76.5322280307861]
  StrategyLLM allows LLMs to perform inductive reasoning, deriving general strategies from specific task instances, and deductive reasoning, applying these general strategies to particular task examples, for constructing generalizable and consistent few-shot prompts. Experimental results demonstrate that StrategyLLM outperforms the competitive baseline CoT-SC that requires human-annotated solutions on 13 datasets across 4 challenging tasks without human involvement, including math reasoning (34.2% $rightarrow$ 38.8%), commonsense reasoning (70.3% $rightarrow$ 72.5%), algorithmic reasoning (73.7% $rightarrow$ 85.0
  arXiv  Detail & Related papers  (2023-11-15T09:18:09Z)
• The Alternating-Time \mu-Calculus With Disjunctive Explicit Strategies [1.7725414095035827]
  We study the strategic abilities of coalitions of agents in concurrent game structures. Key ingredient of the logic are path quantifiers specifying that some coalition of agents has a joint strategy to enforce a given goal. We extend ATLES with fixpoint operators and strategy disjunction, arriving at the alternating-time $mu$-calculus with explicit strategies.
  arXiv  Detail & Related papers  (2023-05-30T07:16:59Z)
• ImitAL: Learned Active Learning Strategy on Synthetic Data [30.595138995552748]
  We propose ImitAL, a domain-independent novel query strategy, which encodes AL as a learning-to-rank problem. We train ImitAL on large-scale simulated AL runs on purely synthetic datasets. To show that ImitAL was successfully trained, we perform an extensive evaluation comparing our strategy on 13 different datasets.
  arXiv  Detail & Related papers  (2022-08-24T16:17:53Z)
• Active Pointly-Supervised Instance Segmentation [106.38955769817747]
  We present an economic active learning setting, named active pointly-supervised instance segmentation (APIS) APIS starts with box-level annotations and iteratively samples a point within the box and asks if it falls on the object. The model developed with these strategies yields consistent performance gain on the challenging MS-COCO dataset.
  arXiv  Detail & Related papers  (2022-07-23T11:25:24Z)
• CSS-LM: A Contrastive Framework for Semi-supervised Fine-tuning of Pre-trained Language Models [59.49705076369856]
  We introduce a novel framework to improve the fine-tuning phase of pre-trained language models (PLMs) We retrieve positive and negative instances from large-scale unlabeled corpora according to their domain-level and class-level semantic relatedness to a task. We then perform contrastive semi-supervised learning on both the retrieved unlabeled and original labeled instances to help PLMs capture crucial task-related semantic features.
  arXiv  Detail & Related papers  (2021-02-07T09:27:26Z)
• SemiNLL: A Framework of Noisy-Label Learning by Semi-Supervised Learning [58.26384597768118]
  SemiNLL is a versatile framework that combines SS strategies and SSL models in an end-to-end manner. Our framework can absorb various SS strategies and SSL backbones, utilizing their power to achieve promising performance.
  arXiv  Detail & Related papers  (2020-12-02T01:49:47Z)
• Prototypical Contrastive Learning of Unsupervised Representations [171.3046900127166]
  Prototypical Contrastive Learning (PCL) is an unsupervised representation learning method. PCL implicitly encodes semantic structures of the data into the learned embedding space. PCL outperforms state-of-the-art instance-wise contrastive learning methods on multiple benchmarks.
  arXiv  Detail & Related papers  (2020-05-11T09:53:36Z)

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.