Author name cluster

Alessandro Facchini

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

2 author rows

ISIPTA Conference 2025 Conference Paper

The AI off-switch problem as a signalling game: bounded rationality and incomparability

Alessio Benavoli
Alessandro Facchini
Marco Zaffalon

The off-switch problem is a critical challenge in AI control: if an AI system resists being switched off, it poses a significant risk. In this paper, we model the off-switch problem as a signalling game, where a human decision-maker communicates its preferences about some underlying decision problem to an AI agent, which then selects actions to maximise the human’s utility. We assume that the human is a bounded rational agent and explore various bounded rationality mechanisms. Using real machine learning models, we reprove prior results and demonstrate that a necessary condition for an AI system to refrain from disabling its off-switch is its uncertainty about the human’s utility. We also analyse how message costs influence optimal strategies and extend the analysis to scenarios involving incomparability.

PDF Details

EUMAS Conference 2021 Conference Paper

Logic and Model Checking by Imprecise Probabilistic Interpreted Systems

Alberto Termine
Alessandro Antonucci 0001
Giuseppe Primiero
Alessandro Facchini

Abstract Stochastic multi-agent systems raise the necessity to extend probabilistic model checking to the epistemic domain. Results in this direction have been achieved by epistemic extensions of Probabilistic Computation Tree Logic and related Probabilistic Interpreted Systems. The latter, however, suffer of an important limitation: they require the probabilities governing the system’s behaviour to be fully specified. A promising way to overcome this limitation is represented by imprecise probabilities. In this paper we introduce imprecise probabilistic interpreted systems and present a related logical language and model-checking procedures based on recent advances in the study of imprecise Markov processes.

Details

ISIPTA Conference 2017 Conference Paper

A Polarity Theory for Sets of Desirable Gambles

Alessio Benavoli
Alessandro Facchini
Marco Zaffalon
José Vicente-Pérez

Coherent sets of almost desirable gambles and credal sets are known to be equivalent models. That is, there exists a bijection between the two collections of sets preserving the usual operations, e. g. conditioning. Such a correspondence is based on the polarity theory for closed convex cones. Learning from this simple observation, in this paper we introduce a new (lexicographic) polarity theory for general convex cones and then we apply it in order to establish an analogous correspondence between coherent sets of desirable gambles and convex sets of lexicographic probabilities.

PDF Details

ISIPTA Conference 2017 Conference Paper

SOS for Bounded Rationality

Alessio Benavoli
Alessandro Facchini
Dario Piga
Marco Zaffalon

In the gambling foundation of probability theory, rationality requires that a subject should always (never) find desirable all nonnegative (negative) gambles, because no matter the result of the experiment the subject never (always) decreases her money. Evaluating the nonnegativity of a gamble in infinite spaces is a difficult task. In fact, even if we restrict the gambles to be polynomials in $R^n$, the problem of determining nonnegativity is NP-hard. The aim of this paper is to develop a computable theory of desirable gambles. Instead of requiring the subject to accept all nonnegative gambles, we only require her to accept gambles for which she can efficiently determine the nonnegativity (in particular SOS polynomials). We call this new criterion bounded rationality.

PDF Details

Highlights Conference 2013 Conference Abstract

Game or not Game?

Alessandro Facchini
Michał Skrzypczak
Filip Murlak

Recently the present authors have shown that both the non-deterministic and the alternating Rabin-Mostowski index problems are decidable for languages recognisable by so-called game automata, which can be seen as the closure of deterministic ones under complementation and composition. In order to be able to claim decidability of the index problem for a given subclass of regular languages, one should however prove that membership in is decidable too. In this talk we show that membership in the class of languages recognizable by game automata is decidable.

PDF Details

MFCS Conference 2011 Conference Paper

Characterizing EF over Infinite Trees and Modal Logic on Transitive Graphs

Balder ten Cate
Alessandro Facchini

Abstract We provide several effective equivalent characterizations of EF (the modal logic of the descendant relation) on arbitrary trees. More specifically, we prove that, for EF -bisimulation invariant properties of trees, being definable by an EF formula, being a Borel set, and being definable in weak monadic second order logic, all coincide. The proof builds upon a known algebraic characterization of EF for the case of finitely branching trees due to Bojańczyk and Idziaszek. We furthermore obtain characterizations of modal logic on transitive Kripke structures as a fragment of weak monadic second order logic and of the μ -calculus.

Details

CSL Conference 2009 Conference Paper

Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata

Jacques Duparc
Alessandro Facchini
Filip Murlak

Abstract For deterministic tree automata, classical hierarchies, like Mostowski-Rabin (or index) hierarchy, Borel hierarchy, or Wadge hierarchy, are known to be decidable. However, when it comes to non-deterministic tree automata, none of these hierarchies is even close to be understood. Here we make an attempt in paving the way towards a clear understanding of tree automata. We concentrate on the class of linear game automata (LGA), and prove within this new context, that all corresponding hierarchies mentioned above—Mostowski-Rabin, Borel, and Wadge—are decidable. The class LGA is obtained by taking linear tree automata with alternation restricted to the choice of path in the input tree. Despite their simplicity, LGA recognize sets of arbitrary high Borel rank. The actual richness of LGA is revealed by the height of their Wadge hierarchy: ( ω ω ) ω.

Details