bluuebunny/crossref_metadata_2025 huggingface dataset:
Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting
Authors: Bednarczyk Bartosz , Rudolph Sebastian
Published: July 2019

Among the most expressive knowledge representation formalisms are the description logics of the Z family. For well-behaved fragments of ZOIQ, entailment of positive two-way regular path queries is well known to be 2EXPTIME-complete under the proviso of unary encoding of numbers in cardinality constraints. We show that this assumption can be dropped without an increase in complexity and EXPTIME-completeness can be achieved when bounding the number of query atoms, using a novel reduction from query entailment to knowledge base satisfiability. These findings allow to strengthen other results regarding query entailment and query containment problems in very expressive description logics. Our results also carry over to GC2, the two-variable guarded fragment of first-order logic with counting quantifiers, for which hitherto only conjunctive query entailment has been investigated.
Comparing Options with Argument Schemes Powered by Cancellation
Authors: Belahcene Khaled , Labreuche Christophe , Maudet Nicolas , Mousseau Vincent , Ouerdane Wassila
Published: July 2019

We introduce a way of reasoning about preferences represented as pairwise comparative statements, based on a very simple yet appealing principle: cancelling out common values across statements. We formalize and streamline this procedure with argument schemes. As a result, any conclusion drawn by means of this approach comes along with a justification. It turns out that the statements which can be inferred through this process form a proper preference relation. More precisely, it corresponds to a necessary preference relation under the assumption of additive utilities. We show the inference task can be performed in polynomial time in this setting, but that finding a minimal length explanation is NP-complete.
Possibilistic Games with Incomplete Information
Authors: Ben Amor Nahla , Fargier Helene , Sabbadin Régis , Trabelsi Meriem
Published: July 2019

Bayesian games offer a suitable framework for
games where the utility degrees are additive in
essence. This approach does nevertheless not apply to ordinal games, where the utility degrees do
not capture more than a ranking, nor to situations
of decision under qualitative uncertainty. This paper proposes a representation framework for ordinal games under possibilistic incomplete information (π-games) and extends the fundamental notion
of Nash equilibrium (NE) to this framework. We
show that deciding whether a NE exists is a difficult
problem (NP-hard) and propose a  Mixed Integer Linear Programming  (MILP) encoding.
Experiments on variants of the GAMUT problems
confirm the feasibility of this approach.
Reasoning about Disclosure in Data Integration in the Presence of Source Constraints
Authors: Benedikt Michael , Bourhis Pierre , Jachiet Louis , Thomazo Michaël
Published: July 2019

Data integration systems allow users to access data sitting in multiple sources by means of queries over a global schema, related to the sources via mappings. Datasources often contain sensitive information, and thus an analysis is needed to verify that a schema satisfies a privacy policy, given as a set of queries whose answers should not be accessible to users. Such an analysis should take into account not only knowledge that an attacker may have about the mappings, but also what they may know about the semantics of the sources.In this paper, we show that source constraints can have a dramatic impact on disclosure analysis. We study the problem of determining whether a given data integration system discloses a source query to an attacker in the presence of constraints, providing both lower and upper bounds on source-aware disclosure analysis.
Mixed-World Reasoning with Existential Rules under Active-Domain Semantics
Authors: Bienvenu Meghyn , Bourhis Pierre
Published: July 2019

In this paper, we study reasoning with existential rules in a setting where some of the predicates may be closed (i.e., their content is fully specified by the data instance) and the remaining open predicates are interpreted under active-domain semantics. We show, unsurprisingly, that the main reasoning tasks (satisfiability and certainty / possibility of Boolean queries) are all intractable in data complexity in the general case. However, several positive (PTIME data) results are obtained for the linear fragment, and interestingly, these tractability results hold also for various extensions, e.g., with negated closed atoms and disjunctive rule heads. This motivates us to take a closer look at the linear fragment, exploring its expressivity and defining a fixpoint extension to approximate non-linear rules.
Guarantees for Sound Abstractions for Generalized Planning
Authors: Bonet Blai , Fuentetaja Raquel , E-Martín Yolanda , Borrajo Daniel
Published: July 2019

Generalized planning is about finding plans that solve collections of planning instances, often infinite collections, rather than single instances. Recently it has been shown how to reduce the planning problem for generalized planning to the planning problem for a qualitative numerical problem; the latter being a reformulation that simultaneously captures all the instances in the collection. An important thread of research thus consists in finding such reformulations, or abstractions, automatically. A recent proposal learns the abstractions inductively from a finite and small sample of transitions from instances in the collection. However, as in all inductive processes, the learned abstraction is not guaranteed to be correct for the whole collection. In this work we address this limitation by performing an analysis of the abstraction with respect to the collection, and show how to obtain formal guarantees for generalization. These guarantees, in the form of first-order formulas, may be used to 1) define subcollections of instances on which the abstraction is guaranteed to be sound, 2) obtain necessary conditions for generalization under certain assumptions, and 3) do automated synthesis of complex invariants for planning problems. Our framework is general, it can be extended or combined with other approaches, and it has applications that go beyond generalized planning.
Ontology Approximation in Horn Description Logics
Authors: Bötcher Anneke , Lutz Carsten , Wolter Frank
Published: July 2019

We study the approximation of a description logic (DL) ontology in a
less expressive DL, focusing on the case of Horn DLs. It is common
to construct such approximations in an ad hoc way in practice and
the resulting incompleteness is typically neither analyzed nor
understood. In this paper, we show how to construct complete
approximations. These are typically infinite or of excessive size
and thus cannot be used directly in applications, but our results
provide an important theoretical foundation that enables informed
decisions when constructing incomplete approximations in practice.
Oblivious and Semi-Oblivious Boundedness for Existential Rules
Authors: Bourhis Pierre , Leclère Michel , Mugnier Marie-Laure , Tison Sophie , Ulliana Federico , Gallois Lily
Published: July 2019

We study the notion of boundedness in the context positive existential rules, that is, wether there exists an upper bound to the depth of the chase procedure, that is independent from the initial instance. By focussing our attention on the oblivious and the semi-oblivious chase variants, we give a characterization of boundedness in terms of FO-rewritability and chase termination. We show that it is decidable to recognize if a set of rules is bounded for several classes of rules and outline the complexity of the problem.
Approximately Maximizing the Broker's Profit in a Two-sided Market
Authors: Chen Jing , Li Bo , Li Yingkai
Published: July 2019

We study how to maximize the broker's (expected) profit in a two-sided market, where she buys items from a set of sellers and resells them to a set of buyers. Each seller has a single item to sell and holds a private value on her item, and each buyer has a valuation function over the bundles of the sellers' items. We consider the Bayesian setting where the agents' values/valuations are independently drawn from prior distributions, and aim at designing dominant-strategy incentive-compatible (DSIC) mechanisms that are approximately optimal.

Production-cost markets, where each item has a publicly-known cost to be produced, provide a platform for us to study two-sided markets. Briefly, we show how to covert a mechanism for production-cost markets into a mechanism for the broker, whenever the former satisfies cost-monotonicity. This reduction holds even when buyers have general combinatorial valuation functions. When the buyers' valuations are additive, we generalize an existing mechanism to production-cost markets in an approximation-preserving way. We then show that the resulting mechanism is cost-monotone and thus can be converted into an 8-approximation mechanism for two-sided markets.
Reasoning about Quality and Fuzziness of Strategic Behaviours
Authors: Bouyer Patricia , Kupferman Orna , Markey Nicolas , Maubert Bastien , Murano Aniello , Perelli Giuseppe
Published: July 2019

We introduce and study SL[F], a quantitative extension of SL (Strategy Logic), one of the most natural and expressive logics describing strategic behaviours. The satisfaction value of an SL[F] formula is a real value in [0,1], reflecting ``how much'' or ``how well'' the strategic on-going objectives of the underlying agents are satisfied. We demonstrate the applications of SL[F] in quantitative reasoning about multi-agent systems, by showing how it can express concepts of stability in multi-agent systems, and how it generalises some fuzzy temporal logics. We also provide a model-checking algorithm for ourlogic, based on a quantitative extension of Quantified CTL*.
The Complexity of Model Checking Knowledge and Time
Authors: Bozzelli Laura , Maubert Bastien , Murano Aniello
Published: July 2019

We establish the precise complexity of the model checking problem for the main logics of knowledge and time. While this problem was known to be non-elementary for agents with perfect recall, with a number of exponentials that increases with the alternation of knowledge operators, the precise complexity of the problem when the maximum alternation is fixed has been an open problem for twenty years. We close it by establishing improved upper bounds for CTL* with knowledge, and providing matching lower bounds that also apply for epistemic extensions of LTL and CTL.
Planning for LTLf /LDLf Goals in Non-Markovian Fully Observable Nondeterministic Domains
Authors: Brafman Ronen I. , De Giacomo Giuseppe
Published: July 2019

In this paper, we investigate non-Markovian Nondeterministic Fully Observable Planning Domains (NMFONDs), variants of Nondeterministic Fully Observable Planning Domains (FONDs) where the next state is determined by the full history leading to the current state. In particular, we introduce TFONDs which are NMFONDs where conditions on the history are succinctly and declaratively specified using the linear-time temporal logic on finite traces LTLf and its extension LDLf. We provide algorithms for planning in TFONDs for general LTLf/LDLf goals, and establish tight complexity bounds w.r.t. the domain representation and the goal, separately. We also show that TFONDs are able to capture all NMFONDs in which the dependency on the history is "finite state". Finally, we show that TFONDs also capture Partially Observable Nondeterministic Planning Domains (PONDs), but without referring to unobservable variables.
Causal Discovery with Cascade Nonlinear Additive Noise Model
Authors: Cai Ruichu , Qiao Jie , Zhang Kun , Zhang Zhenjie , Hao Zhifeng
Published: July 2019

Identification of causal direction between a causal-effect pair from observed data has recently attracted much attention. Various methods based on functional causal models have been proposed to solve this problem, by assuming the causal process satisfies some (structural) constraints and showing that the reverse direction violates such constraints. The nonlinear additive noise model has been demonstrated to be effective for this purpose, but the model class is not transitive--even if each direct causal relation follows this model, indirect causal influences, which result from omitted intermediate causal variables and are frequently encountered in practice, do not necessarily follow the model constraints; as a consequence, the nonlinear additive noise model may fail to correctly discover causal direction. In this work, we propose a cascade nonlinear additive noise model to represent such causal influences--each direct causal relation follows the nonlinear additive noise model but we observe only the initial cause and final effect. We further propose a method to estimate the model, including the unmeasured intermediate variables, from data, under the variational auto-encoder framework. Our theoretical results show that with our model, causal direction is identifiable under suitable technical conditions on the data generation process. Simulation results illustrate the power of the proposed method in identifying indirect causal relations across various settings, and experimental results on real data suggest that the proposed model and method greatly extend the applicability of causal discovery based on functional causal models in nonlinear cases.
Enriching Ontology-based Data Access with Provenance
Authors: Calvanese Diego , Lanti Davide , Ozaki Ana , Penaloza Rafael , Xiao Guohui
Published: July 2019

Ontology-based data access (OBDA) is a popular paradigm for querying heterogeneous data sources by connecting them through mappings to an ontology. In OBDA, it is often difficult to reconstruct why a tuple occurs in the answer of a query. We address this challenge by enriching OBDA with provenance semirings, taking inspiration from database theory. In particular, we investigate the problems of (i) deciding whether a provenance annotated OBDA instance entails a provenance annotated conjunctive query, and (ii) computing a polynomial representing the provenance of a query entailed by a provenance annotated OBDA instance. Differently from pure databases, in our case, these polynomials may be infinite. To regain finiteness, we consider idempotent semirings, and study the complexity in the case of DL-LiteR ontologies. We implement Task (ii) in a state-of-the-art OBDA system and show the practical feasibility of the approach through an extensive evaluation against two popular benchmarks.
Chasing Sets: How to Use Existential Rules for Expressive Reasoning
Authors: Carral David , Dragoste Irina , Krötzsch Markus , Lewe Christian
Published: July 2019

We propose that modern existential rule reasoners can enable fully declarative implementations of rule-based inference methods in knowledge representation, in the sense that a particular calculus is captured by a fixed set of rules that can be evaluated on varying inputs (encoded as facts). We introduce Datalog(S) -- Datalog with support for sets -- as a surface language for such translations, and show that it can be captured in a decidable fragment of existential rules. We then implement several known inference methods in Datalog(S), and empirically show that an existing existential rule reasoner can thus be used to solve practical reasoning problems.
Simple Conditionals with Constrained Right Weakening
Authors: Casini Giovanni , Meyer Thomas , Varzinczak Ivan
Published: July 2019

In this paper we introduce and investigate a very basic semantics for conditionals that can be used to define a broad class of conditional reasoning. We show that it encompasses the most popular kinds of conditional reasoning developed in logic-based KR. It turns out that the semantics we propose is appropriate for a structural analysis of those conditionals that do not satisfy the property of Right Weakening. We show that it can be used for the further development of an analysis of the notion of relevance in conditional reasoning.
Explanations for Query Answers under Existential Rules
Authors: Ceylan İsmail İlkan , Lukasiewicz Thomas , Malizia Enrico , Vaicenavičius Andrius
Published: July 2019

Ontology-mediated query answering is an extensively studied paradigm, which aims at improving query answers with the use of a logical theory. As a form of logical entailment, ontology-mediated query answering is fully interpretable, which makes it possible to derive explanations for query answers. Surprisingly, however, explaining answers for ontology-mediated queries has received little attention for ontology languages based on existential rules. In this paper, we close this gap, and study the problem of explaining query answers in terms of minimal subsets of database facts. We provide a thorough complexity analysis for several decision problems associated with minimal explanations under existential rules.
Semantic Characterization of Data Services through Ontologies
Authors: Cima Gianluca , Lenzerini Maurizio , Poggi Antonella
Published: July 2019

We study the problem of associating formal semantic descriptions to data services. We base our proposal on the Ontology-based Data Access paradigm, where a domain ontology is used to provide a semantic layer mapped to the data sources of an organization. The basic idea is to explain the semantics of a data service in terms of a query over the ontology. We illustrate a formal framework for this problem, based on the notion of source-to-ontology (s-to-o) rewriting, which comes in three variants, called sound, complete and perfect, respectively. We present a thorough complexity analysis of two computational problems, namely verification (checking whether a query is an s-to-o rewriting of a given data service), and computation (computing an s-to-o rewriting of a data service).
Measuring the Likelihood of Numerical Constraints
Authors: Console Marco , Hofer Matthias , Libkin Leonid
Published: July 2019

Our goal is to measure the likelihood of the satisfaction of numerical
constraints in the absence of prior information. We study expressive
constraints, involving arithmetic and complex numerical functions, and
even quantification over numbers. Such problems arise in processing
incomplete data, or analyzing conditions in programs without a priori
bounds on variables. We show that for constraints on n variables,
the proper way to define such a measure is as the limit of the part of
the n-dimensional ball that consists of points satisfying the
constraints, when the radius increases. We prove that the existence of
such a limit is closely related to the notion of o-minimality from
model theory. Thus, for constraints definable with the usual
arithmetic and exponentiation, the likelihood is well defined, but
adding trigonometric functions is problematic. We look at computing
and approximating such likelihoods for order and linear
constraints, and prove an impossibility result for approximating with
multiplicative error. However, as the
likelihood is a number between 0 and 1, an approximation scheme with
additive error is acceptable, and we give it for arbitrary
linear constraints.
Election with Bribe-Effect Uncertainty: A Dichotomy Result
Authors: Chen Lin , Xu Lei , Xu Shouhuai , Gao Zhimin , Shi Weidong
Published: July 2019

We consider the electoral bribery problem in computational social choice. In this context, extensive studies have been carried out to analyze the computational vulnerability of various voting (or election) rules. However, essentially all prior studies assume a deterministic model where each voter has an associated threshold value, which is used as follows. A voter will take a bribe and vote according to the attacker's (i.e., briber's) preference when the amount of the bribe is above the threshold, and a voter will not take a bribe when the amount of the bribe is not above the threshold (in this case, the voter will vote according to its own preference, rather than the attacker's). In this paper, we initiate the study of a more realistic model where each voter is associated with a  willingness function, rather than a fixed threshold value. The willingness function characterizes the  likelihood a bribed voter would vote according to the attacker's preference; we call this bribe-effect uncertainty. We characterize the computational complexity of the electoral bribery problem in this new model. In particular, we discover a dichotomy result: a certain mathematical property of the willingness function dictates whether or not the computational hardness can serve as a deterrence to bribery attackers.
From Statistical Transportability to Estimating the Effect of Stochastic Interventions
Authors: Correa Juan D. , Bareinboim Elias
Published: July 2019

Learning systems often face a critical challenge when applied to settings that differ from those under which they were initially trained. In particular, the assumption that both the source/training and the target/deployment domains follow the same causal mechanisms and observed distributions is commonly violated. This implies that the robustness and convergence guarantees usually expected from these methods are no longer attainable. In this paper, we study these violations through causal lens using the formalism of statistical transportability [Pearl and Bareinboim, 2011] (PB, for short). We start by proving sufficient and necessary graphical conditions under which a probability distribution observed in the source domain can be extrapolated to the target one, where strictly less data is available. We develop the first sound and complete procedure for statistical transportability, which formally closes the problem introduced by PB. Further, we tackle the general challenge of identification of stochastic interventions from observational data [Sec.~4.4, Pearl, 2000]. This problem has been solved in the context of atomic interventions using Pearl's do-calculus, which lacks complete treatment in the stochastic case. We prove completeness of stochastic identification by constructing a reduction of any instance of this problem to an instance of statistical transportability, closing the problem.
Answer Set Programming for Judgment Aggregation
Authors: de Haan Ronald , Slavkovik Marija
Published: July 2019

Judgment aggregation (JA) studies how to aggregate truth valuations on logically related issues. Computing the outcome of aggregation procedures is notoriously computationally hard, which is the likely reason that no implementation of them exists as of yet. However, even hard problems sometimes need to be solved. The worst-case computational complexity of answer set programming (ASP) matches that of most problems in judgment aggregation. We take advantage of this and propose a natural and modular encoding of various judgment aggregation procedures and related problems in JA into ASP. With these encodings, we achieve two results: (1) paving the way towards constructing a wide range of new benchmark instances (from JA) for answer set solving algorithms; and (2) providing an automated tool for researchers in the area of judgment aggregation.
An ASP Approach to Generate Minimal Countermodels in Intuitionistic Propositional Logic
Authors: Fiorentini Camillo
Published: July 2019

Intuitionistic Propositional Logic is complete w.r.t. Kripke semantics: if a formula is not intuitionistically valid, then there exists a finite Kripke model falsifying it. The problem of obtaining concise models has been scarcely investigated in the literature. We present a procedure to generate minimal models in the number of worlds relying on Answer Set Programming (ASP).
Learning Description Logic Concepts: When can Positive and Negative Examples be Separated?
Authors: Funk Maurice , Jung Jean Christoph , Lutz Carsten , Pulcini Hadrien , Wolter Frank
Published: July 2019

Learning description logic (DL) concepts from positive and negative examples given in the form of labeled data items in a KB has received significant attention in the literature. We study the fundamental question of when a separating DL concept exists and provide useful model-theoretic characterizations as well as complexity results for the associated decision problem. For expressive DLs such as ALC and ALCQI, our characterizations show a surprising link to the evaluation of ontology-mediated conjunctive queries. We exploit this to determine the combined complexity (between ExpTime and NExpTime) and data complexity (second level of the polynomial hierarchy) of separability. For the Horn DL EL, separability is ExpTime-complete both in combined and in data complexity while for its modest extension ELI it is even undecidable. Separability is also undecidable when the KB is formulated in ALC and the separating concept is required to be in EL or ELI.
Aggressive Driving Saves More Time? Multi-task Learning for Customized Travel Time Estimation
Authors: Gao Ruipeng , Guo Xiaoyu , Sun Fuyong , Dai Lin , Zhu Jiayan , Hu Chenxi , Li Haibo
Published: July 2019

Estimating the origin-destination travel time is a fundamental problem in many location-based services for vehicles, e.g., ride-hailing, vehicle dispatching, and route planning. Recent work has made significant progress to accuracy but they largely rely on GPS traces which are too coarse to model many personalized driving events. In this paper, we propose Customized Travel Time Estimation (CTTE) that fuses GPS traces, smartphone inertial data, and road network within a deep recurrent neural network. It constructs a link traffic database with topology representation, speed statistics, and query distribution. It also uses inertial data to estimate the arbitrary phone's pose in car, and detects fine-grained driving events. The multi-task learning structure predicts both traffic speed at public level and customized travel time at personal level. Extensive experiments on two real-world traffic datasets from Didi Chuxing have demonstrated our effectiveness.
Approximating Integer Solution Counting via Space Quantification for Linear Constraints
Authors: Ge Cunjing , Ma Feifei , Ma Xutong , Zhang Fan , Huang Pei , Zhang Jian
Published: July 2019

Solution counting or solution space quantification (means volume computation and volume estimation) for linear constraints (LCs) has found interesting applications in various fields. Experimental data shows that integer solution counting is usually more expensive than quantifying volume of solution space while their output values are close. So it is helpful to approximate the number of integer solutions by the volume if the error is acceptable. In this paper, we present and prove a bound of such error for LCs. It is the first bound that can be used to approximate the integer solution counts. Based on this result, an approximate integer solution counting method for LCs is proposed. Experiments show that our approach is over 20x faster than the state-of-the-art integer solution counters. Moreover, such advantage increases with the problem scale.
Best Answers over Incomplete Data : Complexity and First-Order Rewritings
Authors: Gheerbrant Amélie , Sirangelo Cristina
Published: July 2019

Answering queries over incomplete data is ubiquitous in data management and in many AI applications that use query rewriting to take advantage of relational database technology. In these scenarios one lacks full information on the data but queries still need to be answered with certainty. The certainty aspect often makes query answering unfeasible except for restricted classes, such as unions of conjunctive queries. In addition often there are no, or very few certain answers, thus expensive computation is in vain. Therefore we study a relaxation of certain answers called best answers. They are defined as those answers for which there is no better one (that is, no answer true in more possible worlds). When certain answers exist the two notions coincide. We compare different ways of casting query answering as a decision problem and characterise its complexity for first-order queries, showing significant differences in the behavior of best and certain answers.We then restrict attention to best answers for unions of conjunctive queries and produce a practical algorithm for finding them based on query rewriting techniques.
On Division Versus Saturation in Pseudo-Boolean Solving
Authors: Gocht Stephan , Nordström Jakob , Yehudayoff Amir
Published: July 2019

The conflict-driven clause learning (CDCL) paradigm has revolutionized
SAT solving over the last two decades. Extending this approach to
pseudo-Boolean (PB) solvers doing 0-1 linear programming holds the
promise of further exponential improvements in theory, but
intriguingly such gains have not materialized in practice. Also
intriguingly, most PB extensions of CDCL use not the division rule in
cutting planes as defined in [Cook et al., '87] but instead the
so-called saturation rule. To the best of our knowledge, there has
been no study comparing the strengths of division and saturation in
the context of conflict-driven PB learning, when all linear
combinations of inequalities are required to cancel variables.
We show that PB solvers with division instead of saturation can be
exponentially stronger. In the other direction, we prove that
simulating a single saturation step can require an exponential number
of divisions. We also perform some experiments to see whether these
phenomena can be observed in actual solvers. Our conclusion is that a
careful combination of division and saturation seems to be crucial to
harness more of the power of cutting planes.
On Finite and Unrestricted Query Entailment beyond SQ with Number Restrictions on Transitive Roles
Authors: Gogacz Tomasz , Gutiérrez-Basulto Víctor , Ibáñez-García Yazmín , Jung Jean Christoph , Murlak Filip
Published: July 2019

We study the description logic SQ with number restrictions applicable to transitive roles, extended with either nominals or inverse roles. We show tight 2EXPTIME upper bounds for unrestricted entailment of regular path queries for both extensions and finite entailment of positive existential queries for nominals. For inverses, we establish 2EXPTIME-completeness for unrestricted and finite entailment of instance queries (the latter under restriction to a single, transitive role).
Belief Revision Operators with Varying Attitudes Towards Initial Beliefs
Authors: Haret Adrian , Woltran Stefan
Published: July 2019

Classical axiomatizations of belief revision include a postulate stating that if new information is consistent with initial beliefs, then revision amounts to simply adding the new information to the original knowledge base. This postulate assumes a conservative attitude towards initial beliefs, in the sense that an agent faced with the need to revise them will seek to preserve initial beliefs as much as possible. In this work we look at operators that can assume different attitudes towards original beliefs. We provide axiomatizations of these operators by varying the aforementioned postulate and obtain representation results that characterize the new types of operators using preorders on possible worlds. We also present concrete examples for each new type of operator, adapting notions from decision theory.
Dispatching Through Pricing: Modeling Ride-Sharing and Designing Dynamic Prices
Authors: Chen Mengjing , Shen Weiran , Tang Pingzhong , Zuo Song
Published: July 2019

Over the past few years, ride-sharing has emerged as an effective way to relieve traffic congestion. A key problem for the ride-sharing platforms is to come up with a revenue-optimal (or GMV-optimal) pricing scheme and a vehicle dispatching policy that incorporate geographic and temporal information. In this paper, we aim to tackle this problem via an economic approach. Modeled naively, the underlying optimization problem may be non-convex and thus hard to solve. To this end, we use a so-called ``ironing'' technique to convert the problem into an equivalent convex optimization one via a clean Markov decision process (MDP) formulation, where the states are the driver distributions and the decision variables are the prices for each pair of locations. Our main finding is an efficient algorithm that computes the exact revenue-optimal (or GMV-optimal) randomized pricing scheme, which naturally induces the accompany vehicle dispatching policy. We also conduct empirical evaluations of our solution through real data of a major ride-sharing platform and show its advantages over fixed pricing schemes as well as several prevalent surge-based pricing schemes.
Some Things are Easier for the Dumb and the Bright Ones (Beware the Average!)
Authors: Jamroga Wojciech , Knapik Michał
Published: July 2019

Model checking strategic abilities in multi-agent systems is hard, especially for agents with partial observability of the state of the system. In that case, it ranges from NP-complete to undecidable, depending on the precise syntax and the semantic variant. That, however, is the worst case complexity, and the problem might as well be easier when restricted to particular subclasses of inputs. In this paper, we look at the verification of models with "extreme" epistemic structure, and identify several special cases for which model checking is easier than in general. We also prove that, in the other cases, no gain is possible even if the agents have almost full (or almost nil) observability. To prove the latter kind of results, we develop generic techniques that may be useful also outside of this study.
Converging on Common Knowledge
Authors: Klein Dominik , Rendsvig Rasmus Kræmmer
Published: July 2019

Common knowledge, as is well known, is not attainable in finite time by unreliable communication, thus hindering perfect coordination. Focusing on the coordinated attack problem modeled using dynamic epistemic logic, this paper discusses unreliable communication protocols from a topological perspective and asks "If the generals may communicate indefinitely, will they then *converge* to a state of common knowledge?" We answer by making precise and showing the following: *common knowledge is attainable if, and only if, we do not care about common knowledge*.
Rational Inference Relations from Maximal Consistent Subsets Selection
Authors: Konieczny Sébastien , Marquis Pierre , Vesic Srdjan
Published: July 2019

When one wants to draw non-trivial inferences from an inconsistent belief base, a very  natural approach is to take advantage of the maximal consistent subsets of the base. But few inference relations from maximal consistent subsets exist. In this paper we point out new such relations based on selection of some of the maximal consistent subsets, leading thus to inference relations with a stronger inferential power. The selection process must obey some principles to ensure that it leads to an inference relation which is rational. We define a general class of monotonic selection relations for comparing maximal consistent sets. And we show that it corresponds to the class of rational inference relations.
How to Handle Missing Values in Multi-Criteria Decision Aiding?
Authors: Labreuche Christophe , Destercke Sébastien
Published: July 2019

It is often the case in the applications of Multi-Criteria Decision Making that the values of alternatives are unknown on some attributes. An interesting situation arises when the attributes having missing values are actually not relevant and shall thus be removed from the model. Given a model that has been elicited on the complete set of attributes, we are looking thus for a way -- called restriction operator -- to automatically remove the missing attributes from this model. Axiomatic characterizations are proposed for three classes of models. For general quantitative models, the restriction operator is characterized by linearity, recursivity and decomposition on variables. The second class is the set of monotone quantitative models satisfying normalization conditions. The linearity axiom is changed to fit with these conditions. Adding recursivity and symmetry, the restriction operator takes the form of a normalized average. For the last class of models -- namely the Choquet integral, we obtain a simpler expression. Finally, a very intuitive interpretation is provided.
A Tractable, Expressive, and Eventually Complete First-Order Logic of Limited Belief
Authors: Lakemeyer Gerhard , Levesque Hector J.
Published: July 2019

In knowledge representation, obtaining a notion of belief which is tractable, expressive, and eventually complete has been a somewhat elusive goal. Expressivity here means that an agent should be able to hold arbitrary beliefs in a very expressive language like that of first-order logic, but without being required to perform full logical reasoning on those beliefs. Eventual completeness means that any logical consequence of what is believed will eventually come to be believed, given enough reasoning effort. Tractability in a first-order setting has been a research topic for many years, but in most cases limitations were needed on the form of what was believed, and eventual completeness was so far restricted to the propositional case. In this paper, we propose a novel logic of limited belief, which has all three desired properties.
Travel Time Estimation without Road Networks: An Urban Morphological Layout Representation Approach
Authors: Lan Wuwei , Xu Yanyan , Zhao Bin
Published: July 2019

Travel time estimation is a crucial task for not only personal travel scheduling but also city planning. Previous methods focus on modeling toward road segments or sub-paths, then summing up for a final prediction, which have been recently replaced by deep neural models with end-to-end training. Usually, these methods are based on explicit feature representations, including spatio-temporal features, traffic states, etc. Here, we argue that the local traffic condition is closely tied up with the land-use and built environment, i.e., metro stations, arterial roads, intersections, commercial area, residential area, and etc, yet the relation is time-varying and too complicated to model explicitly and efficiently. Thus, this paper proposes an end-to-end multi-task deep neural model, named Deep Image to Time (DeepI2T), to learn the travel time mainly from the built environment images, a.k.a. the morphological layout images, and showoff the new state-of-the-art performance on real-world datasets in two cities. Moreover, our model is designed to tackle both path-aware and path-blind scenarios in the testing phase. This work opens up new opportunities of using the publicly available morphological layout images as considerable information in multiple geography-related smart city applications.
Augmenting Transfer Learning with Semantic Reasoning
Authors: Lécué Freddy , Chen Jiaoyan , Pan Jeff Z. , Chen Huajun
Published: July 2019

Transfer learning aims at building robust prediction models by transferring knowledge gained from one problem to another. In the semantic Web, learning tasks are enhanced with semantic representations. We exploit their semantics to augment transfer learning by dealing with when to transfer with semantic measurements and what to transfer with semantic embeddings. We further present a general framework that integrates the above measurements and embeddings with existing transfer learning algorithms for higher performance. It has demonstrated to be robust in two real-world applications: bus delay forecasting and air quality forecasting.
Revisiting Controlled Query Evaluation in Description Logics
Authors: Lembo Domenico , Rosati Riccardo , Savo Domenico Fabio
Published: July 2019

Controlled Query Evaluation (CQE) is a confidentiality-preserving framework in which private information is protected through a policy, and a (optimal) censor guarantees that answers to queries are maximized without violating the policy. CQE has been recently studied in the context of ontologies, where the focus has been mainly on the problem of the existence of an optimal censor. In this paper we instead consider query answering over all possible optimal censors. We study data complexity of this problem for ontologies specified in the Description Logics DL-LiteR and EL_bottom and for variants of the censor language, which is the language used by the censor to enforce the policy. In our investigation we also analyze the relationship between CQE and the problem of Consistent Query Answering (CQA). Some of the complexity results we provide are indeed obtained through mutual reduction between CQE and CQA.
Unit Selection Based on Counterfactual Logic
Authors: Li Ang , Pearl Judea
Published: July 2019

The unit selection problem aims to identify a set of individuals who are most likely to exhibit a desired mode of behavior, which is defined in counterfactual terms. A typical example is that of selecting individuals who would respond one way if encouraged and a different way if not encouraged. Unlike previous works on this problem, which rely on ad-hoc heuristics, we approach this problem formally, using counterfactual logic, to properly capture the nature of the desired behavior. This formalism enables us to derive an informative selection criterion which integrates experimental and observational data. We demonstrate the superiority of this criterion over A/B-test-based approaches.
Story Ending Prediction by Transferable BERT
Authors: Li Zhongyang , Ding Xiao , Liu Ting
Published: July 2019

Recent advances, such as GPT and BERT, have shown success in incorporating a pre-trained transformer language model and fine-tuning operation to improve downstream NLP systems. However, this framework still has some fundamental problems in effectively incorporating supervised knowledge from other related tasks. In this study, we investigate a transferable BERT (TransBERT) training framework, which can transfer not only general language knowledge from large-scale unlabeled data but also specific kinds of knowledge from various semantically related supervised tasks, for a target task. Particularly, we propose utilizing three kinds of transfer tasks, including natural language inference, sentiment classification, and next action prediction, to further train BERT based on a pre-trained model. This enables the model to get a better initialization for the target task. We take story ending prediction as the target task to conduct experiments. The final result, an accuracy of 91.8%, dramatically outperforms previous state-of-the-art baseline methods. Several comparative experiments give some helpful suggestions on how to select transfer tasks to improve BERT.
ATSIS: Achieving the Ad hoc Teamwork by Sub-task Inference and Selection
Authors: Chen Shuo , Andrejczuk Ewa , A. Irissappane Athirai , Zhang Jie
Published: July 2019

In an ad hoc teamwork setting, the team needs to coordinate their activities to perform a task without prior agreement on how to achieve it. The ad hoc agent cannot communicate with its teammates but it can observe their behaviour and plan accordingly. To do so, the existing approaches rely on the teammates' behaviour models. However, the models may not be accurate, which can compromise teamwork. For this reason, we present Ad Hoc Teamwork by Sub-task Inference and Selection (ATSIS) algorithm that uses a sub-task inference without relying on teammates' models. First, the ad hoc agent observes its teammates to infer which sub-tasks they are handling. Based on that, it selects its own sub-task using a partially observable Markov decision process that handles the uncertainty of the sub-task inference. Last, the ad hoc agent uses the Monte Carlo tree search to find the set of actions to perform the sub-task. Our experiments show the benefits of ATSIS for robust teamwork.
Geo-ALM: POI Recommendation by Fusing Geographical Information and Adversarial Learning Mechanism
Authors: Liu Wei , Wang Zhi-Jie , Yao Bin , Yin Jian
Published: July 2019

Learning user’s preference from check-in data is
important for POI recommendation. Yet, a user
usually has visited some POIs while most of POIs
are unvisited (i.e., negative samples). To leverage
these “no-behavior” POIs, a typical approach
is pairwise ranking, which constructs ranking pairs
for the user and POIs. Although this approach is
generally effective, the negative samples in ranking
pairs are obtained randomly, which may fail to
leverage “critical” negative samples in the model
training. On the other hand, previous studies also
utilized geographical feature to improve the recommendation
quality. Nevertheless, most of previous
works did not exploit geographical information
comprehensively, which may also affect the performance.
To alleviate these issues, we propose a geographical
information based adversarial learning
model (Geo-ALM), which can be viewed as a fusion
of geographic features and generative adversarial
networks. Its core idea is to learn the discriminator
and generator interactively, by exploiting two
granularity of geographic features (i.e., region and
POI features). Experimental results show that Geo-
ALM can achieve competitive performance, compared
to several state-of-the-arts.
Automatic Verification of FSA Strategies via Counterexample-Guided Local Search for Invariants
Authors: Luo Kailun , Liu Yongmei
Published: July 2019

Strategy representation and reasoning has received much attention over the past years. In this paper, we consider the representation of general strategies that solve a class of (possibly infinitely many) games with similar structures, and their automatic verification, which is an undecidable problem. We propose to represent a general strategy by an FSA (Finite State Automaton) with edges labelled by restricted Golog programs. We formalize the semantics of FSA strategies in the situation calculus. Then we propose an incomplete method for verifying whether an FSA strategy is a winning strategy by counterexample-guided local search for appropriate invariants. We implemented our method and did experiments on combinatorial game and also single-agent domains. Experimental results showed that our system can successfully verify most of them within a reasonable amount of time.
BiOWA for Preference Aggregation with Bipolar Scales: Application to Fair Optimization in Combinatorial Domains
Authors: Martin Hugo , Perny Patrice
Published: July 2019

We study the biOWA model for preference aggregation and multicriteria decision making from bipolar rating scales. A biOWA is an ordered doubly weighted averaging extending standard ordered weighted averaging (OWA) and allowing a finer control of the importance attached to positive and negative evaluations in the aggregation. After establishing some useful properties of biOWA to generate balanced Pareto-optimal solutions, we address fair biOWA-optimization problems in combinatorial domains. We first consider the use of biOWA in multi-winner elections for aggregating graded approval and disapproval judgements. Then we consider the use of biOWA for solving robust path problems with costs expressing gains and losses. A linearization of biOWA is proposed, allowing both problems to be solved by MIP. A path-ranking algorithm for biOWA optimization is also proposed. Numerical tests are provided to show the practical efficiency of our models.
Satisfaction and Implication of Integrity Constraints in Ontology-based Data Access
Authors: Nikolaou Charalampos , Cuenca Grau Bernardo , Kostylev Egor V. , Kaminski Mark , Horrocks Ian
Published: July 2019

We extend ontology-based data access with integrity constraints over both the source and target schemas. The relevant reasoning problems in this setting are constraint satisfaction—to check whether a database satisfies the target constraints given the mappings and the ontology—and source-to-target (resp., target-to-source) constraint implication, which is to check whether a target constraint (resp., a source constraint) is satisfied by each database satisfying the source constraints (resp., the target constraints). We establish decidability and complexity bounds for all these problems in the case where ontologies are expressed in DL-LiteR and constraints range from functional dependencies to disjunctive tuple-generating dependencies.