1,720,996 research outputs found
Enforcing equilibria in multi-agent systems
Full text linkWe introduce and investigate Normative Synthesis: a new class of problems for the equilibrium verification that counters the absence of equilibria by purposely constraining multi-agent systems. We show that norms are powerful enough to ensure a positive answer to every instance of the equilibrium verification problem. Subsequently, we focus on two optimization versions, that aim at providing a solution in compliance with implementation costs. We show that the complexities of our procedures range between 2exptime and 3exptime, thus that the problems are no harder than the corresponding equilibrium verification ones
Multi-player games with LDL goals over finite traces
Full text linkLinear Dynamic Logic on finite traces (LDLF) is a powerful logic for reasoning about the behaviour of concurrent and multi-agent systems. In this paper, we investigate techniques for both the characterisation and verification of equilibria in multi-player games with goals/objectives expressed using logics based on LDLF. This study builds upon a generalisation of Boolean games, a logic-based game model of multi-agent systems where players have goals succinctly represented in a logical way. Because LDLF goals are considered, in the settings we study—Reactive Modules games and iterated Boolean games with goals over finite traces—players' goals can be defined to be regular properties while achieved in a finite, but arbitrarily large, trace. In particular, using alternating automata, the paper investigates automata-theoretic approaches to the characterisation and verification of (pure strategy Nash) equilibria, shows that the set of Nash equilibria in multi-player games with LDLF objectives is regular, and provides complexity results for the associated automata constructions
Abitare il tempo...libero. Il sogno probabile del turismo minerario in Sardegna
No full textIl senso del rapporto fra spazio e tempo assume uno specifico significato nelle regioni in riconversione economica, dove il tema del heritage tourism si vuole portatore di nuove relazioni fra patrimonio e dinamica dei luoghi.
Specialmente laddove l’offerta turistica cerca di staccarsi dal modello classico della fruizione balneare, immaginare, progettare e realizzare turismo deve fare i conti con una domanda di turismo che oggi è un ibrido di domanda di tempo libero, viaggi a scopo educativo o di lavoro e forme di mobilità più o meno innovative. Ad alcuni anni da un a precedente indagine (Boggio et al., 2003), ed alla luce del lavoro di campo finalizzato alla redazione del Piano Socio economico del nuovo Parco Geominerario Storico ed Ambientale della Sardegna, pare interessante analizzare le ragioni per le quali, secondo gli attori del territorio, l’atteso emergere del nuovo eden turistico si sia finora modestamente realizzato. Non meno interessante è l’analisi di come il venir meno della territorialità industriale storica abbia condizionato la percezione identitaria delle comunità coinvolte e di quale reale relazione possa esistere fra progettazione istituzionale e partecipazione collettiva alla costruzione della nuova immagine territoriale. In particolare ci si sofferma sub-regione del Sulcis-Iglesiente,in ragione dell’importanza che l’attività estrattiva vi ha avuto nel XIX e nel XX secolo, dell’effetto visibile dell’abbandono che caratterizza la fine dell’ultimo secolo, della rilevanza degli investimenti in aree industriali contermini alle aree minerarie , della specificità del tentativo di far decollare prima un’industria turistica costiera e poi una nuova forma di heritage tourism e della presenza di elementi intangibili specifici (metodologie di lavoro, rituali, espressioni di socialità, memoria, etc.)
Binding Forms in First-Order Logic
Full text linkAiming to pinpoint the reasons behind the decidability of some complex extensions of modal logic, we propose a new classification criterion for sentences of first-order logic, which is based on the kind of binding forms admitted in their expressions, i.e., on the way the arguments of a relation can be bound to a variable. In particular, we describe a hierarchy of four fragments focused on the Boolean combinations of these forms, showing that the less expressive one is already incomparable with several first-order limitations proposed in the literature, as the guarded and unary negation fragments. We also prove, via a novel model-theoretic technique, that our logic enjoys the finite-model property, Craig's interpolation, and Beth's definability. Furthermore, the associated model-checking and satisfiability problems are solvable in PTime and Sigma_3^P, respectively
Cycle detection in computation tree logic
No full textWe introduce Cycle-CTL⋆, an extension of CTL⋆ with cycle quantifications that are able to predicate over cycles. The introduced logic turns out to be very expressive. Indeed, we prove that it strictly extends CTL⋆ and is orthogonal to μCALCULUS. We also give an evidence of its usefulness by providing few examples involving non-regular properties. We extensively investigate both the model-checking and satisfiability problems for Cycle-CTL⋆ and some of its variants/fragments
Synthesis of controllable nash equilibria in games with quantitative objectives
Full text linkIn Rational Synthesis, we consider a multi-agent system
in which some of the agents are controllable and
some are not. All agents have objectives, and the goal
is to synthesize strategies for the controllable agents so
that their objectives are satisfied, assuming rationality
of the uncontrollable agents. Previous work on rational
synthesis considers objectives in LTL, namely ones
that describe on-going behaviors, and in Objective-LTL,
which allows ranking of LTL formulas. In this paper,
we extend rational synthesis to LTL[F]– an extension
of LTL by quality operators. The satisfaction value of
an LTL[F] formula is a real value in [0; 1], where the
higher the value is, the higher is the quality in which
the computation satisfies the specification. The extension
significantly strengthens the framework of rational
synthesis and enables a study its game- and socialchoice
theoretic aspects. In particular, we study the
price of stability and price of anarchy of the rationalsynthesis
game and use them to explain the cooperative
and non-cooperative settings of rational synthesis. Our
algorithms make use of strategy logic and decision procedures
for it. Thus, we are able to handle the richer
quantitative setting using existing tools. In particular,
we show that the cooperative and non-cooperative versions
of quantitative rational synthesis are 2EXPTIMEcomplete
and in 3EXPTIME, respectively – not harder
than the complexity known for their Boolean analogues
Pushdown multi-agent system verification
No full textIn this paper we investigate the model-checking problem of pushdown multi-agent systems for ATL* specifications. To this aim, we introduce pushdown game structures over which ATL∗ formulas are interpreted. We show an algorithm that solves the addressed model-checking problem in 3EXPTIME. We also provide a 2EXPSPACE lower bound by showing a reduction from the word acceptance problem for deterministic Turing machines with doubly exponential space
Indagine sieroepidemiologica sulla diffusione della Chlamydiosi in piccioni di città della Toscana
No full text
- …
