Search

We propose a notion of alternating bisimulation for strategic abilities under imperfect information. The bisimulation preserves formulas of ATL$^*$ for both the {\em objective} and {\em subjective} variants of the state-based semantics with imperfect information, which are commonly used in the modeling and verification of multi-agent systems. Furthermore, we apply the theoretical result to the verification of coercion-resistance in the ThreeBallot voting system, a voting protocol that does not use cryptography. In particular, we show that natural simplifications of an initial model of the protocol are in fact bisimulations of the original model, and therefore satisfy the same ATL$^*$ properties, including coercion-resistance. These simplifications allow the model-checking tool MCMAS to terminate on models with a larger number of voters and candidates, compared with the initial model.

In online advertising, search engines sell ad placements for keywords continuously through auctions. This problem can be seen as an infinitely repeated game since the auction is executed whenever a user performs a query with the keyword. As advertisers may frequently change their bids, the game will have a large set of equilibria with potentially complex strategies. In this paper, we propose the use of natural strategies for reasoning in such setting as they are processable by artificial agents with limited memory and/or computational power as well as understandable by human users. To reach this goal, we introduce a quantitative version of Strategy Logic with natural strategies in the setting of imperfect information. In a first step, we show how to model strategies for repeated keyword auctions and take advantage of the model for proving properties evaluating this game. In a second step, we study the logic in relation to the distinguishing power, expressivity, and model-checking complexity for strategies with and without recall., Comment: Extended version of paper accepted at AAMAS 2022

The growing trend of fledgling reinforcement learning systems making their way into real-world applications has been accompanied by growing concerns for their safety and robustness. In recent years, a variety of approaches have been put forward to address the challenges of safety-aware reinforcement learning; however, these methods often either require a handcrafted model of the environment to be provided beforehand, or that the environment is relatively simple and low-dimensional. We present a novel approach to safety-aware deep reinforcement learning in high-dimensional environments called latent shielding. Latent shielding leverages internal representations of the environment learnt by model-based agents to "imagine" future trajectories and avoid those deemed unsafe. We experimentally demonstrate that this approach leads to improved adherence to formally-defined safety specifications., Comment: Accepted at SafeAI 2022

We address the problem of building agents whose goal is to learn to execute out-of distribution (OOD) multi-task instructions expressed in temporal logic (TL) by using deep reinforcement learning (DRL). Recent works provided evidence that the agent's neural architecture is a key feature when DRL agents are learning to solve OOD tasks in TL. Yet, the studies on this topic are still in their infancy. In this work, we propose a new deep learning configuration with inductive biases that lead agents to generate latent representations of their current goal, yielding a stronger generalization performance. We use these latent-goal networks within a neuro-symbolic framework that executes multi-task formally-defined instructions and contrast the performance of the proposed neural networks against employing different state-of-the-art (SOTA) architectures when generalizing to unseen instructions in OOD environments.

In the present article, the author uses Fourier theory of tempered distributions (generalized functions) in deriving a formula for Dirichlet-like integrals. The applied method is remarkably efficient and allows a solution in a few calculational steps. The interest of the present article lies not only in the derivation of an appearently unknown formula but also in the original methodology of its derivation., Comment: 7 pages

In the present article, the volume of the hypersphere in n-dimensional euclidean space is recalculated in a rather original way by using the theory of generalized functions (tempered distributions). The calculation is performed by applying the integral representation of the Heaviside unit step function and furthermore by using the distributional Fourier transform of general power-law functions. The same method (added by a regularization procedure of the occurring infinite-dimensional integral via the Riemann-zeta function) is applied in the case of infinite dimensions giving rise to some sort of anti-measure of spheres in the Hilbert space of square-summable complex sequences., Comment: 8 pages

The literature on awareness modeling includes both syntax-free and syntax-based frameworks. Heifetz, Meier \& Schipper (HMS) propose a lattice model of awareness that is syntax-free. While their lattice approach is elegant and intuitive, it precludes the simple option of relying on formal language to induce lattices, and does not explicitly distinguish uncertainty from unawareness. Contra this, the most prominent syntax-based solution, the Fagin-Halpern (FH) model, accounts for this distinction and offers a simple representation of awareness, but lacks the intuitiveness of the lattice structure. Here, we combine these two approaches by providing a lattice of Kripke models, induced by atom subset inclusion, in which uncertainty and unawareness are separate. We show our model equivalent to both HMS and FH models by defining transformations between them which preserve satisfaction of formulas of a language for explicit knowledge, and obtain completeness through our and HMS' results. Lastly, we prove that the Kripke lattice model can be shown equivalent to the FH model (when awareness is propositionally determined) also with respect to the language of the Logic of General Awareness, for which the FH model where originally proposed., Comment: arXiv admin note: substantial text overlap with arXiv:2012.12982

This paper discusses the role of 2-D/3-D cochlear fluid hydrodynamics in the generation of the large nonlinear dynamical range of the basilar membrane (BM) and pressure response, in the decoupling between cochlear gain and tuning, and in the dynamic stabilization of the high-gain BM response in the peak region. The large and closely correlated dependence on stimulus level of the BM velocity and fluid pressure gain (Dong and Olson, 2013), is consistent with a physiologically-oriented schematization of the outer hair cell (OHC) mechanism if two hydrodynamic effects are accounted for: amplification of the differential pressure associated with a focusing phenomenon, and viscous damping at the BM-fluid interface. The predictions of the analytical 2-D WKB approach are compared to solutions of a 3-D finite element model, showing that these hydrodynamic phenomena yield stable high-gain response in the peak region and a smooth transition among models with different effectiveness of the active mechanism, mimicking the cochlear nonlinear response over a wide stimulus level range. This study explains how an effectively anti-damping nonlinear OHC force may yield large BM and pressure dynamical ranges along with an almost level-independent admittance., Comment: The following article has been submitted to the Journal of the Acoustical Society of America (JASA). After it is published, it will be found at https://publishing.aip.org/resources/librarians/products/journals/

Where information grows abundant, attention becomes a scarce resource. As a result, agents must plan wisely how to allocate their attention in order to achieve epistemic efficiency. Here, we present a framework for multi-agent epistemic planning with attention, based on Dynamic Epistemic Logic (DEL, a powerful formalism for epistemic planning). We identify the framework as a fragment of standard DEL, and consider its plan existence problem. While in the general case undecidable, we show that when attention is required for learning, all instances of the problem are decidable.

In the present article, a new method for the evaluation of fractional derivatives of arbitrary real order is proposed. Numerous but inequivalent formulations have been given in the past. Some of them exhibit unsatisfactory properties such as e.g. the absence of a semigroup property. It is shown that the proposed definition is free from such drawbacks. In order to achieve such a generalization one has to work in the context of tempered distributions (generalized functions) where the concept works nicely. The last part of the article shows the possibility of defining fractional derivatives of periodic functions (Fourier series)., Comment: 28 pages, 1 figure

We introduce a novel method to aggregate Bipolar Argumentation (BA) Frameworks expressing opinions by different parties in debates. We use Bipolar Assumption-based Argumentation (ABA) as an all-encompassing formalism for BA under different semantics. By leveraging on recent results on judgement aggregation in Social Choice Theory, we prove several preservation results, both positive and negative, for relevant properties of Bipolar ABA.

Multi-agent reinforcement learning (RL) often struggles to ensure the safe behaviours of the learning agents, and therefore it is generally not adapted to safety-critical applications. To address this issue, we present a methodology that combines formal verification with (deep) RL algorithms to guarantee the satisfaction of formally-specified safety constraints both in training and testing. The approach we propose expresses the constraints to verify in Probabilistic Computation Tree Logic (PCTL) and builds an abstract representation of the system to reduce the complexity of the verification step. This abstract model allows for model checking techniques to identify a set of abstract policies that meet the safety constraints expressed in PCTL. Then, the agents' behaviours are restricted according to these safe abstract policies. We provide formal guarantees that by using this method, the actions of the agents always meet the safety constraints, and provide a procedure to generate an abstract model automatically. We empirically evaluate and show the effectiveness of our method in a multi-agent environment., Comment: Extended version of AAMAS publication under the same name

We report the first study on the thermal behaviour of the stiffness of individual carbon nanotubes, which is achieved by measuring the resonance frequency of their fundamental mechanical bending modes. We observe a reduction of the Young's modulus over a large temperature range with a slope $-(173\pm 65)$ ppm/K in its relative shift. These findings are reproduced by two different theoretical models based on the thermal dynamics of the lattice. These results reveal how the measured fundamental bending modes depend on the phonons in the nanotube via the Young's modulus. An alternative description based on the coupling between the measured mechanical modes and the phonon thermal bath in the Akhiezer limit is discussed.

Heifetz, Meier and Schipper (HMS) present a lattice model of awareness. The HMS model is syntax-free, which precludes the simple option to rely on formal language to induce lattices, and represents uncertainty and unawareness with one entangled construct, making it difficult to assess the properties of either. Here, we present a model based on a lattice of Kripke models, induced by atom subset inclusion, in which uncertainty and unawareness are separate. We show the models to be equivalent by defining transformations between them which preserve formula satisfaction, and obtain completeness through our and HMS' results., Comment: 18 pages, 2 figures, proceedings of DaLi conference 2020

We show that a history-based variant of alternating bisimulation with imperfect information allows it to be related to a variant of Alternating-time Temporal Logic (ATL) with imperfect information by a full Hennessy-Milner theorem. The variant of ATL we consider has a common knowledge semantics, which requires that the uniform strategy available for a coalition to accomplish some goal must be common knowledge inside the coalition, while other semantic variants of ATL with imperfect information do not accommodate a Hennessy-Milner theorem. We also show that the existence of a history-based alternating bisimulation between two finite Concurrent Game Structures with imperfect information (iCGS) is undecidable.

This work introduces a neuro-symbolic agent that combines deep reinforcement learning (DRL) with temporal logic (TL) to achieve systematic zero-shot, i.e., never-seen-before, generalisation of formally specified instructions. In particular, we present a neuro-symbolic framework where a symbolic module transforms TL specifications into a form that helps the training of a DRL agent targeting generalisation, while a neural module learns systematically to solve the given tasks. We study the emergence of systematic learning in different settings and find that the architecture of the convolutional layers is key when generalising to new instructions. We also provide evidence that systematic learning can emerge with abstract operators such as negation when learning from a few training examples, which previous research have struggled with.

The combination of Formal Methods with Reinforcement Learning (RL) has recently attracted interest as a way for single-agent RL to learn multiple-task specifications. In this paper we extend this convergence to multi-agent settings and formally define Extended Markov Games as a general mathematical model that allows multiple RL agents to concurrently learn various non-Markovian specifications. To introduce this new model we provide formal definitions and proofs as well as empirical tests of RL algorithms running on this framework. Specifically, we use our model to train two different logic-based multi-agent RL algorithms to solve diverse settings of non-Markovian co-safe LTL specifications., Comment: Long version of the correspondent ECAI 2020 paper

In the present article the author extends the Fourier transform to a more general class of functions; First to power-law functions with integer and half-integer exponents then to the widely used quantum statistics function (Fermi-Dirac and Bose-Einstein-distributions). The results are used to derive rather straightforwardly an integral formula. Moreover, generalized Fourier transforms are used to define fractional derivatives of distributions (generalized functions) and Fourier series (periodic functions) as well., Comment: 14 pages, 5 figures

Humans engage in informal debates on a daily basis. By expressing their opinions and ideas in an argumentative fashion, they are able to gain a deeper understanding of a given problem and in some cases, find the best possible course of actions towards resolving it. In this paper, we develop a methodology to verify debates formalised as abstract argumentation frameworks. We first present a translation from debates to transition systems. Such transition systems can model debates and represent their evolution over time using a finite set of states. We then formalise relevant debate properties using temporal and strategy logics. These formalisations, along with a debate transition system, allow us to verify whether a given debate satisfies certain properties. The verification process can be automated using model checkers. Therefore, we also measure their performance when verifying debates, and use the results to discuss the feasibility of model checking debates., Comment: Accepted for publication as full paper at the 35th ACM/SIGAPP Symposium On Applied Computing (SAC2020), KRR track

In the present article the linear mass Density for vertically suspended heavy springs is calculated for two different cases. First for a spring of invariable length suspended at the top and fixed at the bottom of the spring, then for a hanging heavy spring with an additional load. Both cases are solved by minimizing the total energy which is a sum of potential energy and energy due to the deformation., Comment: 9 pages, 4 figures

In the present paper the author evaluates the path integral of a charged anisotropic Harmonic Oscillator (HO) in crossed electric and magnetic fields by two alternative methods. Both methods enable a rather formal calculation and circumvent some mathematical delicate issues such as the occurrence of an infinite Normalization constant and ambiguities with path integral calculations when magnetic fields are present. The \emph{$1^{\text{st}}$} method uses complex Fourier series and a regularization scheme via the Riemann-$\zeta$-function. The \emph{$2^{\text{nd}}$} method evaluates the path integral by transforming the Lagrangian to a uniformly rotating system. The latter method uses the fact that the Lorentz- and Coriolis force have the same functional form. Both forces cancel each other within the rotating system given that it rotates with Larmor frequency $\omega_{L}$. This fact simplifies considerably the calculation of the path integral., Comment: 22 pages

Knowledge can be represented compactly in multiple ways, from a set of propositional formulas, to a Kripke model, to a database. In this paper we study the aggregation of information coming from multiple sources, each source submitting a database modelled as a first-order relational structure. In the presence of integrity constraints, we identify classes of aggregators that respect them in the aggregated database, provided these are satisfied in all individual databases. We also characterise languages for first-order queries on which the answer to a query on the aggregated database coincides with the aggregation of the answers to the query obtained on each individual database. This contribution is meant to be a first step on the application of techniques from social choice theory to knowledge representation in databases., Comment: In Proceedings TARK 2019, arXiv:1907.08335. arXiv admin note: substantial text overlap with arXiv:1802.08586

We prove that the model checking ATL* on concurrent game structures with propositional control for atom-visibility (vCGS) is undecidable. To do so, we reduce this problem to model checking ATL* on iCGS.

Stochastic switching between the two bistable states of a strongly driven mechanical resonator enables detection of weak signals based on probability distributions, in a manner that mimics biological systems. However, conventional silicon resonators at the microscale require a large amount of fluctuation power to achieve a switching rate in the order of a few Hertz. Here, we employ graphene membrane resonators of atomic thickness to achieve a stochastic switching rate of 7.8 kHz, which is 200 times faster than current state-of-the-art. The (effective) temperature of the fluctuations is approximately 400 K, which is 3000 times lower than the state-of-the-art. This shows that these membranes are potentially useful to transduce weak signals in the audible frequency domain. Furthermore, we perform numerical simulations to understand the transition dynamics of the resonator and derive simple analytical expressions to investigate the relevant scaling parameters that allow high-frequency, low-temperature stochastic switching to be achieved in mechanical resonators.

In the recent years the lattice Boltzmann (LB) methodology has been fruitfully extended to include the effects of thermal fluctuations. So far, all studied cases pertain equilibrium fluctuations, i.e. fluctuations with respect to an equilibrium background state. In this paper we take a step further and present results of fluctuating LB simulations of a binary mixture confined between two parallel walls in presence of a constant concentration gradient in the wall-to-wall direction. This is a paradigmatic set-up for the study of non-equilibrium (NE) fluctuations, i.e. fluctuations with respect to a non- equilibrium state. We analyze the dependence of the structure factors for the hydrodynamical fields on the wave vector $\boldsymbol{q}$ in both the directions parallel and perpendicular to the walls, as well as the finite-size effects induced by confinement, highlighting the long-range ($\sim |\boldsymbol{q}|^{-4}$) nature of correlations in the NE framework. Results quantitatively agree with the predictions of fluctuating hydrodynamics. Moreover, in presence of a non-ideal (NI) equation of state of the mixture, we also observe that the (spatially homogeneous) average pressure changes, due to a genuinely new contribution triggered by the long-range nature of NE fluctuations. These NE pressure effects are studied at changing the system size and the concentration gradient. Taken all together, we argue that these findings are instrumental to boost the applicability of the fluctuating LB methodology in the framework of NE fluctuations, possibly in conjunction with experiments., Comment: 19 pages, 16 figures (10 captions)

The bending rigidity of two-dimensional (2D) materials is a key parameter for understanding the mechanics of 2D NEMS devices. The apparent bending rigidity of graphene membranes at macroscopic scale differs from theoretical predictions at micro-scale. This difference is believed to originate from thermally induced dynamic ripples in the atomically thin membrane. In this paper, we perform modal analysis to estimate the effective macroscopic bending rigidity of graphene membranes from the frequency spectrum of their Brownian motion. Our method is based on fitting the resonance frequencies obtained from the Brownian motion in molecular dynamics simulations, to those obtained from a continuum mechanics model, with bending rigidity and pretension as the fit parameters. In this way, the effective bending rigidity of the membrane and its temperature and size dependence, are extracted, while including the effects of dynamic ripples and thermal fluctuations. The proposed method provides a framework for estimating the macroscopic mechanical properties at high frequencies in other two-dimensional nano-structures at finite temperatures.

Knowledge can be represented compactly in a multitude ways, from a set of propositional formulas, to a Kripke model, to a database. In this paper we study the aggregation of information coming from multiple sources, each source submitting a database modelled as a first-order relational structure. In the presence of an integrity constraint, we identify classes of aggregators that respect it in the aggregated database, provided all individual databases satisfy it. We also characterise languages for first-order queries on which the answer to queries on the aggregated database coincides with the aggregation of the answers to the query obtained on each individual database. This contribution is meant to be a first step on the application of techniques from rational choice theory to knowledge representation in databases., Comment: 20 pages

Tactile speech aids, though extensively studied in the 1980s and 90s, never became a commercial success. A hypothesis to explain this failure might be that it is difficult to obtain true perceptual integration of a tactile signal with information from auditory speech: exploitation of tactile cues from a tactile aid might require cognitive effort and so prevent speech understanding at the high rates typical of everyday speech. To test this hypothesis, we attempted to create true perceptual integration of tactile with auditory information in what might be considered the simplest situation encountered by a hearing-impaired listener. We created an auditory continuum between the syllables BA and VA, and trained participants to associate BA to one tactile stimulus VA to another tactile stimulus. After training, we tested if auditory discrimination along the continuum between the two syllables could be biased by incongruent tactile stimulation. We found that such a bias occurred only when the tactile stimulus was above its previously measured tactile discrimination threshold. Such a pattern is compatible with the idea that the effect is due to a cognitive or decisional strategy, rather than to truly perceptual integration. We therefore ran a further study, where we created a tactile version of the McGurk effect. We extensively trained two Subjects over six days to associate four recorded auditory syllables with four corresponding apparent motion tactile patterns. In a subsequent test, we presented stimulation that was either congruent or incongruent with the learnt association, and asked Subjects to report the syllable they perceived. We found no analog to the McGurk effect. These findings strengthen our hypothesis according to which tactile aids failed because integration of tactile cues with auditory speech occurred at a cognitive or decisional level, rather than truly at a perceptual level

The hydrodynamics of a liquid-vapour interface in contact with an heterogeneous surface is largely impacted by the presence of defects at the smaller scales. Such defects introduce morphological disturbances on the contact line and ultimately determine the force exerted on the wedge of liquid in contact with the surface. From the mathematical point of view, defects introduce perturbation modes, whose space-time evolution is governed by the interfacial hydrodynamic equations of the contact line. In this paper we derive the response function of the contact line to such generic perturbations. The contact line response may be used to design simplified 1+1 dimensional models accounting for the complexity of interfacial flows coupled to nanoscale defects, yet offering a more tractable mathematical framework to include thermal fluctuations and explore thermally activated contact line motion through a disordered energy landscape., Comment: 17 Pages, 6 Figures

In the typical framework for boolean games (BG) each player can change the truth value of some propositional atoms, while attempting to make her goal true. In standard BG goals are propositional formulas, whereas in iterated BG goals are formulas of Linear Temporal Logic. Both notions of BG are characterised by the fact that agents have exclusive control over their set of atoms, meaning that no two agents can control the same atom. In the present contribution we drop the exclusivity assumption and explore structures where an atom can be controlled by multiple agents. We introduce Concurrent Game Structures with Shared Propositional Control (CGS-SPC) and show that they ac- count for several classes of repeated games, including iterated boolean games, influence games, and aggregation games. Our main result shows that, as far as verification is concerned, CGS-SPC can be reduced to concurrent game structures with exclusive control. This result provides a polynomial reduction for the model checking problem of specifications in Alternating-time Temporal Logic on CGS-SPC., Comment: In Proceedings TARK 2017, arXiv:1707.08250

In this paper we introduce {\em global and local announcement logic} (GLAL), a dynamic epistemic logic with two distinct announcement operators -- $[\phi]^+_A$ and $[\phi]^-_A$ indexed to a subset $A$ of the set $Ag$ of all agents -- for global and local announcements respectively. The boundary case $[\phi]^+_{Ag}$ corresponds to the public announcement of $\phi$, as known from the literature. Unlike standard public announcements, which are {\em model transformers}, the global and local announcements are {\em pointed model transformers}. In particular, the update induced by the announcement may be different in different states of the model. Therefore, the resulting computations are trees of models, rather than the typical sequences. A consequence of our semantics is that modally bisimilar states may be distinguished in our logic. Then, we provide a stronger notion of bisimilarity and we show that it preserves modal equivalence in GLAL. Additionally, we show that GLAL is strictly more expressive than public announcement logic with common knowledge. We prove a wide range of validities for GLAL involving the interaction between dynamics and knowledge, and show that the satisfiability problem for GLAL is decidable. We illustrate the formal machinery by means of detailed epistemic scenarios., Comment: In Proceedings TARK 2017, arXiv:1707.08250

The effect of thermal fluctuations near a contact line of a liquid interface partially wetting an impenetrable substrate is studied analytically and numerically. Promoting both the interface profile and the contact line position to random variables, we explore the equilibrium properties of the corresponding fluctuating contact line problem based on an interfacial Hamiltonian involving a "contact" binding potential. To facilitate an analytical treatment we consider the case of a one-dimensional interface. The effective boundary condition at the contact line is determined by a dimensionless parameter that encodes the relative importance of thermal energy and substrate energy at the microscopic scale. We find that this parameter controls the transition from a partially wetting to a pseudo-partial wetting state, the latter being characterized by a thin prewetting film of fixed thickness. In the partial wetting regime, instead, the profile typically approaches the substrate via an exponentially thinning prewetting film. We show that, independently of the physics at the microscopic scale, Young's angle is recovered sufficiently far from the substrate. The fluctuations of the interface and of the contact line give rise to an effective disjoining pressure, exponentially decreasing with height. Fluctuations therefore provide a regularization of the singular contact forces occurring in the corresponding deterministic problem., Comment: 40 Pages, 12 Figures