We introduce a novel approach (COpt) to Fixed-Budget Best-Arm Identification (FBBAI) specifically designed for contexts where both the expected rewards and their variances are unknown a priori. Our methodology starts with the derivation of a general upper bound on the misidentification probability applicable to sub-Gaussian distributions. Based on this theoretical foundation, we develop an algorithm that iteratively solves a non-linear optimization problem over empirical estimators to determine the optimal allocation of the residual sampling budget among the arms. We conducted empirical validation across a range of synthetic distribution classes and a real-world scenario based on the MovieLens dataset. Experimental results demonstrate that COpt consistently achieves superior accuracy compared to established algorithms, including Sequential Halving, VBR, and Gap-EV. Execution time remains within the range of tens of milliseconds, making it suitable for a wide range of applications.

Controlled Query Evaluation (CQE) is a methodology designed to maintain confidentiality by either rejecting specific queries or adjusting responses to safeguard sensitive information. In this investigation, our focus centers on CQE within Description Logic ontologies, aiming to ensure that queries are answered truthfully as long as possible before resorting to deceptive responses, a cooperativity property which is called the “longest honeymoon”. Our work introduces new semantics for CQE, denoted as MC-CQE, which enjoys the longest honeymoon property and outperforms previous methodologies in terms of cooperativity. We study the complexity of query answering in this new framework for ontologies expressed in the Description Logic DL-Lite_R. Specifically, we establish data complexity results under different maximally cooperative semantics and for different classes of queries. Our results identify both tractable and intractable cases. In particular, we show that the evaluation of Boolean unions of conjunctive queries is the same under all the above semantics and its data complexity is in AC^0. This result makes query answering amenable to SQL query rewriting. However, this favorable property does not extend to open queries, even with a restricted query language limited to conjunctions of atoms. While, in general, answering open queries in the MC-CQE framework is intractable, we identify a sub-family of semantics under which answering full conjunctive queries is tractable.

A deductive module of a knowledge base KB is a subset of KB that preserves a specified class of consequences. Module extraction is applied in ontology design, debugging, and reasoning. The locality-based module extractors of the OWL API are less effective when the knowledge base contains facts such as ABox assertions. The competing module extractor PrisM computes smaller modules at the cost of higher computation time. In this paper, we introduce and study a novel module extraction technique, called conditional module extraction , that can be applied to satisfiable SRIQ ( D ) knowledge bases. Experimental analysis shows that conditional module extraction constitutes an appealing alternative to PrisM and to the locality-based extractors of the OWL API, when the ABox is nonempty.

This paper introduces and investigates k-unmatchability, a counterpart of k-anonymity for knowledge graphs. Like k-anonimity, k-unmatchability enhances privacy by ensuring that any individual in any external source can always be matched to either none or at least k different anonymized individuals. The tradeoff between privacy protection and information loss can be controlled with parameter k. We analyze the data complexity of k-unmatchability under different notions of anonymization.

Abstract We study the rational preferences of agents participating in a mechanism whose outcome is a ranking (i.e., a weak order) among participants. We propose a set of self-interest axioms corresponding to different ways for participants to compare rankings. These axioms vary from minimal conditions that most participants can be expected to agree on, to more demanding requirements that apply to specific scenarios. Then, we analyze the theories that can be obtained by combining the previous axioms and characterize their mutual relationships, revealing a rich hierarchical structure. After this broad investigation on preferences over rankings, we consider the case where the mechanism can distribute a fixed monetary reward to the participants in a fair way (that is, depending only on the anonymized output ranking). We show that such mechanisms can induce specific classes of preferences by suitably choosing the assigned rewards, even in the absence of tie breaking.

One of the factors that hinder the adoption of nonmonotonic description logics in applications is performance. Even when monotonic and nonmonotonic inferences have the same asymptotic complexity, the implementation of nonmonotonic reasoning may be significantly slower. The family of nonmonotonic logics DLN is no exception to this behavior. We address this issue by introducing two provably correct and complete optimizations for reasoning in DLN. The first optimization is a module extractor that has the purpose of focusing reasoning on a relevant subset of the knowledge base. The second, called optimistic evaluation, aims at exploiting incremental reasoning in a better way. Extensive experimental evaluation shows that the optimized DLN reasoning is often compatible with interactive query answering, thus bringing nonmonotonic description logics closer to practical applications.

We introduce a non-Bayesian variant of Thompson sampling whose belief is based on the Central Limit Theorem. As such, it is a parameter-less and prior-free algorithm for the stochastic multi-armed bandit problem. We analyze its asymptotical behavior by proving that it is greedy in the limit of infinite exploration. Further, we empirically evaluate its performance in the fixed-budget best-arm identification problem. In a suite of empirical tests, including both bounded and unbounded reward distributions, our approach exhibits in many cases the lowest misidentification rate among the state-of-the-art algorithms.

Bayesian Preference Elicitation (PE) is an active learning technique aimed at discovering users’ preferences through a suitable sequence of queries. One of its prominent applications consists in providing personalized product recommendations in e-Commerce scenarios. In these settings, where catalogs may contain hundreds or thousands of different products, it becomes crucial to find a good trade-off between recommendation quality and computational cost.In this paper we introduce QUEST, a highly configurable PE framework supporting arbitrary value functions on multi-attribute product domains. We use QUEST to compare established and novel query selection methodologies to achieve real-time user interaction, while preserving recommendation quality. In particular, the experimental assessment shows that a novel uncertainty-based query selection strategy outperforms the largely used value-of-information (VOI) both in accuracy and execution time.

Abstract We consider tournaments played by a set of players in order to establish a ranking among them. We introduce the notion of irrelevant match, as a match that does not influence the ultimate ranking of the involved parties. After discussing the basic properties of this notion, we seek out tournaments that have no irrelevant matches, focusing on the class of tournaments where each player challenges each other exactly once. We prove that tournaments with a static schedule and at least five players always include irrelevant matches. Conversely, dynamic schedules for an arbitrary number of players can be devised that avoid irrelevant matches, at least for one of the players involved in each match. Finally, we prove by computational means that there exist tournaments where all matches are relevant to both players, at least up to eight players.

We study the rational preferences of agents participating in a mechanism whose outcome is a weak order among participants. We propose a set of self-interest axioms and characterize the mutual relationships between all subsets thereof. We then assume that the mechanism can assign monetary rewards to the agents, in a way that is consistent with the weak order. We show that the mechanism can induce specific classes of preferences by suitably choosing the assigned rewards, even in the absence of tie breaking.

This paper shows how knowledge representation and reasoning techniques can be used to support organizations in complying with the GDPR, that is, the new European data protection regulation. This work is carried out in a European H2020 project called SPECIAL. Data usage policies, the consent of data subjects, and selected fragments of the GDPR are encoded in a fragment of OWL2 called PL (policy language); compliance checking and policy validation are reduced to subsumption checking and concept consistency checking. This work proposes a satisfactory tradeoff between the expressiveness requirements on PL posed by the modeling of the GDPR, and the scalability requirements that arise from the use cases provided by SPECIAL's industrial partners. Real-time compliance checking is achieved by means of a specialized reasoner, called PLR, that leverages knowledge compilation and structural subsumption techniques. The performance of a prototype implementation of PLR is analyzed through systematic experiments, and compared with the performance of other important reasoners. Moreover, we show how PL and PLR can be extended to support richer ontologies, by means of import-by-query techniques. We prove novel tractability and intractability results related to PL, and some negative results about the restrictions posed on ontology import.

DL^N is a recent nonmonotonic description logic, designed for satisfying independently proposed knowledge engineering requirements, and for removing some recurrent drawbacks of traditional nonmonotonic semantics. In this paper we study the logical properties of DL^N and their relationships with the KLM postulates. We use various versions of the KLM postulates to deepen the comparison with related work, and illustrate the different tradeoffs between opposite expressivity requirements adopted by each approach.

Nonmonotonic inferences are not yet supported by Description Logic technology, although their potential usefulness is widely recognized. Lack of support to nonmonotonic reasoning is due to a number of issues related to expressiveness, computational complexity, and optimizations. This work contributes to the practical support of nonmonotonic reasoning in description logics by introducing a new semantics designed to address knowledge engineering needs. The formalism is validated through extensive comparison with the other nonmonotonic DLs, and systematic scalability tests.

In the setting of multi-agent games, considerable effort has been devoted to the definition of modal logics for strategic reasoning. In this area, a recent contribution is given by the introduction of Strategy Logic (SL, for short) by Mogavero, Murano, and Vardi. This logic allows to reason explicitly about strategies as first order objects and express in a very natural and elegant way several solution concepts like Nash, resilient, and secure equilibria, dominant strategies, etc. The price that one has to pay for the high expressiveness of SL semantics is that agents strategies it admits may be not behavioral, i.e., a choice of an agent, at a given moment of a play, may depend on the choices another agent can make in another counterfactual play. As the latter moves are unpredictable, this kind of strategies cannot be synthesized in practice. In this paper, we investigate two syntactical fragments of SL, namely the conjunctive-goal and disjunctive-goal, called SL[CG] and SL[DG] for short, and prove that their semantics admit behavioral strategies only. These logics are obtained by forcing SL formulas to be only of the form of conjunctions or disjunctions of goals, which are temporal assertions associated with a binding of agents with strategies. As SL formulas with any Boolean combination of goals turn out to be non behavioral, we have that SL[CG] and SL[DG] represent the maximal fragments of SL describing agent behaviors that are synthesizable. As a consequence of the above results, the model-checking problem for both SL[CG] and SL[DG] is shown to be solvable in 2EXPTIME, as it is for the subsumed logic ATL*.

Cooperative boolean games (CBG) are a family of coalitional games where agents may depend on each other for the satisfaction of their personal goals. In Dunne et al. (2008, Cooperative Boolean games. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008), 1015–1022), the authors define as solution concept the notion of core showing that several decision problems, such as core-emptiness, are Π2p-complete. In this work, we investigate how to improve the computation of the core. In particular, we introduce two different types of dependence networks, abstract dependence networks and refined dependence networks, that are used to define the notion of stable coalitions and Δ-reduction, respectively. Stable coalitions enable to focus on a subset of the agents and use results to determinate the core of the whole game. Δ-reduction prunes the search space by returning a set of actions that are not admissible to be executed. We present an algorithm based on stable coalitions and a Δ-reduction implemented in Prolog and experimental results that show how they effectively improve the computation of the core.

The research on low-complexity nonmonotonic description logics recently identified a fragment of EL with bottom, supporting defeasible inheritance with overriding, where reasoning can be carried out in polynomial time. We contribute to that framework by supporting more axiom schemata and all the concept constructors of EL++ without increasing asymptotic complexity. Moreover, we show that all the syntactic restrictions we adopt are necessary by proving several coNP-hardness results.

We analyze the complexity of reasoning in EL with defeasible inclusions and extensions thereof. The results by Bonatti et al., 2009a are extended by proving tight lower complexity bounds and by relaxing the syntactic restrictions adopted there. We further extend the old framework by supporting arbitrary priority relations.

Open distributed environments, such as the World Wide Web, facilitate information sharing but provide limited support to the protection of sensitive information and resources. Trust negotiation (TN) frameworks have been proposed as a better solution for open environments, in which parties may get in touch and interact without being previously known to each other. In this paper, we illustrate Protune, a rule-based TN system. By describing Protune, we will illustrate the advantages that arise from an advanced rule-based approach in terms of deployment efforts, user friendliness, communication efficiency, and interoperability. The generality and technological feasibility of Protune's approach are assessed through an extensive analysis and experimental evaluations.