title:
Homogenization of Parabolic Equations with Large Time-dependent Random
  Potential

abstract:
  This paper concerns the homogenization problem of a parabolic equation with
large, time-dependent, random potentials in high dimensions $d\geq 3$.
Depending on the competition between temporal and spatial mixing of the
randomness, the homogenization procedure turns to be different. We characterize
the difference by proving the corresponding weak convergence of Brownian motion
in random scenery. When the potential depends on the spatial variable
macroscopically, we prove a convergence to SPDE.


title:
On the Existence of MDS Codes Over Small Fields With Constrained
  Generator Matrices

abstract:
  We study the existence over small fields of Maximum Distance Separable (MDS)
codes with generator matrices having specified supports (i.e. having specified
locations of zero entries). This problem unifies and simplifies the problems
posed in recent works of Yan and Sprintson (NetCod'13) on weakly secure
cooperative data exchange, of Halbawi et al. (arxiv'13) on distributed
Reed-Solomon codes for simple multiple access networks, and of Dau et al.
(ISIT'13) on MDS codes with balanced and sparse generator matrices. We
conjecture that there exist such $[n,k]_q$ MDS codes as long as $q \geq n + k -
1$, if the specified supports of the generator matrices satisfy the so-called
MDS condition, which can be verified in polynomial time. We propose a
combinatorial approach to tackle the conjecture, and prove that the conjecture
holds for a special case when the sets of zero coordinates of rows of the
generator matrix share with each other (pairwise) at most one common element.
Based on our numerical result, the conjecture is also verified for all $k \leq
7$. Our approach is based on a novel generalization of the well-known Hall's
marriage theorem, which allows (overlapping) multiple representatives instead
of a single representative for each subset.


title: Phase transitions in the complex plane of physical parameters

abstract:
  At low temperature a thermodynamic system undergoes a phase transition when a
physical parameter passes through a singularity point of the free energy,
corresponding to formation of a new order. At high temperature the thermal
fluctuations destroy the orders; correspondingly the free energy is a smooth
function of the physical parameter and the singularity would occur only at
complex values of the parameter. Since a complex parameter is unphysical, at
high temperature no phase transition is expected with varying the physical
parameter. Here we show that the quantum evolution, driven by a designed
interaction, of a system initialized in thermal equilibrium is equivalent to
the partition function of a complex parameter. Therefore we can access the
complex singularity points of thermodynamic functions and observe phase
transitions even at high temperatures. This discovery makes it possible to
study thermodynamics in the complex plane of physical parameters.


title:
An Information-Spectrum Approach to Weak Variable-Length Source Coding
  with Side-Information

abstract:
  This paper studies variable-length (VL) source coding of general sources with
side-information. Novel one-shot coding theorems for coding with common
side-information available at the encoder and the decoder and Slepian- Wolf
(SW) coding (i.e., with side-information only at the decoder) are given, and
then, are applied to asymptotic analyses of these coding problems. Especially,
a general formula for the infimum of the coding rate asymptotically achievable
by weak VL-SW coding (i.e., VL-SW coding with vanishing error probability) is
derived. Further, the general formula is applied to investigating weak VL-SW
coding of mixed sources. Our results derive and extend several known results on
SW coding and weak VL coding, e.g., the optimal achievable rate of VL-SW coding
for mixture of i.i.d. sources is given for countably infinite alphabet case
with mild condition. In addition, the usefulness of the encoder
side-information is investigated. Our result shows that if the encoder
side-information is useless in weak VL coding then it is also useless even in
the case where the error probability may be positive asymptotically.


title:
Subwavelength imaging of sparse broadband sources surrounded by an open
  disordered medium from a single antenna

abstract:
  In this letter we study the subwavelength imaging of sparse broadband sources
inside a disordered medium by processing the data acquired by a single antenna.
A mathematical model has been developed for solving such problem based on the
idea of sparse reconstruction. We show that the strongly disordered medium can
serves as an efficient apparatus for compressive measurement, which shifts the
complexity of devising compressive sensing (CS) hardware from the design,
fabrication and electronic control. The proposed method and associated results
can find applications in several imaging disciplines, such as optics, THz, RF
or ultrasound imaging.


title: The reductivity of spherical curves

abstract:
  We show that we can obtain a reducible spherical curve from any non-trivial
spherical curve by four or less inverse-half-twisted splices, i.e., the
reductivity, which represents how reduced a spherical curve is, is four or
less. We also discuss unavoidable sets of tangles for spherical curves.


title:
Estimating Box-Cox power transformation parameter via goodness of fit
  tests

abstract:
  Box-Cox power transformation is a commonly used methodology to transform the
distribution of a non-normal data into a normal one. Estimation of the
transformation parameter is crucial in this methodology. In this study, the
estimation process is hold via a searching algorithm and is integrated into
well-known seven goodness of fit tests for normal distribution. An artificial
covariate method is also included for comparative purposes. Simulation studies
are implemented to compare the effectiveness of the proposed methods. The
methods are also illustrated on two different real life data applications.
Moreover, an R package AID is proposed for implementation.


title:
Seeded Graph Matching Via Joint Optimization of Fidelity and
  Commensurability

abstract:
  We present a novel approximate graph matching algorithm that incorporates
seeded data into the graph matching paradigm. Our Joint Optimization of
Fidelity and Commensurability (JOFC) algorithm embeds two graphs into a common
Euclidean space where the matching inference task can be performed. Through
real and simulated data examples, we demonstrate the versatility of our
algorithm in matching graphs with various characteristics--weightedness,
directedness, loopiness, many-to-one and many-to-many matchings, and soft
seedings.


title: Information Geometry Approach to Parameter Estimation in Markov Chains

abstract:
  We consider the parameter estimation of Markov chain when the unknown
transition matrix belongs to an exponential family of transition matrices.
Then, we show that the sample mean of the generator of the exponential family
is an asymptotically efficient estimator. Further, we also define a curved
exponential family of transition matrices. Using a transition matrix version of
the Pythagorean theorem, we give an asymptotically efficient estimator for a
curved exponential family.


title:
On Swarm Stability of Linear Time-Invariant Descriptor Compartmental
  Networks

abstract:
  Swarm stability is concerned for descriptor compartmental networks with
linear time-invariant protocol. Compartmental network is a specific type of
dynamical multi-agent system. Necessary and sufficient conditions for both
consensus and critical swarm stability are presented, which require a joint
matching between the interactive dynamics of nearest neighboring vertices and
the Laplacian spectrum of the overall network topology. Three numerical
instances are illustrated to verify the theoretical results.


title: Physics-Based Learning Models for Ship Hydrodynamics

abstract:
  We present the concepts of physics-based learning models (PBLM) and their
relevance and application to the field of ship hydrodynamics. The utility of
physics-based learning is motivated by contrasting generic learning models for
regression predictions, which do not presume any knowledge of the system other
than the training data provided with methods such as semi-empirical models,
which incorporate physical insights along with data-fitting. PBLM provides a
framework wherein intermediate models, which capture (some) physical aspects of
the problem, are incorporated into modern generic learning tools to
substantially improve the predictions of the latter, minimizing the reliance on
costly experimental measurements or high-resolution high-fidelity numerical
solutions. To illustrate the versatility and efficacy of PBLM, we present three
wave-ship interaction problems: 1) at speed waterline profiles; 2) ship motions
in head seas; and 3) three-dimensional breaking bow waves. PBLM is shown to be
robust and produce error rates at or below the uncertainty in the generated
data at a small fraction of the expense of high-resolution numerical
predictions.


title: Heavy Flavor at the Large Hadron Collider in a Strong Coupling Approach

abstract:
  Employing nonperturbative transport coefficients for heavy-flavor (HF)
diffusion through quark-gluon plasma (QGP), hadronization and hadronic matter,
we compute $D$- and $B$-meson observables in Pb+Pb ($\sqrt{s}$=2.76\,TeV)
collisions at the LHC. Elastic heavy-quark scattering in the QGP is evaluated
within a thermodynamic $T$-matrix approach, generating resonances close to the
critical temperature which are utilized for recombination into $D$ and $B$
mesons, followed by hadronic diffusion using effective hadronic scattering
amplitudes. The transport coefficients are implemented via Fokker-Planck
Langevin dynamics within hydrodynamic simulations of the bulk medium in nuclear
collisions. The hydro expansion is quantitatively constrained by
transverse-momentum spectra and elliptic flow of light hadrons. Our approach
thus incorporates the paradigm of a strongly coupled medium in both bulk and HF
dynamics throughout the thermal evolution of the system.


title:
Structured Priors for Sparse-Representation-Based Hyperspectral Image
  Classification

abstract:
  Pixel-wise classification, where each pixel is assigned to a predefined
class, is one of the most important procedures in hyperspectral image (HSI)
analysis. By representing a test pixel as a linear combination of a small
subset of labeled pixels, a sparse representation classifier (SRC) gives rather
plausible results compared with that of traditional classifiers such as the
support vector machine (SVM). Recently, by incorporating additional structured
sparsity priors, the second generation SRCs have appeared in the literature and
are reported to further improve the performance of HSI. These priors are based
on exploiting the spatial dependencies between the neighboring pixels, the
inherent structure of the dictionary, or both. In this paper, we review and
compare several structured priors for sparse-representation-based HSI
classification. We also propose a new structured prior called the low rank
group prior, which can be considered as a modification of the low rank prior.
Furthermore, we will investigate how different structured priors improve the
result for the HSI classification.


title: Thermal quantum discord in the Heisenberg chain with impurity

abstract:
  We study thermal quantum discord (TQD) in the Heisenberg chain with spin site
or magnetic impurity. The former one of which may induce inhomogeneous exchange
interactions between the neighboring spins, while the latter one modelling a
spin chain with nonuniform magnetic field. In contrast with one's traditional
understanding, we found that the spin impurity can be used to enhance the TQD
greatly for all the bipartition schemes of the chain, while the magnetic
impurity located on one spin can make the TQD between the other two spins
approaching its maximum 1 for the antiferromagnetic chain.


title: Quantum circuit complexity of one-dimensional topological phases

abstract:
  Topological quantum states cannot be created from product states with local
quantum circuits of constant depth and are in this sense more entangled than
topologically trivial states, but how entangled are they? Here we quantify the
entanglement in one-dimensional topological states by showing that local
quantum circuits of linear depth are necessary to generate them from product
states. We establish this linear lower bound for both bosonic and fermionic
one-dimensional topological phases and use symmetric circuits for phases with
symmetry. We also show that the linear lower bound can be saturated by
explicitly constructing circuits generating these topological states. The same
results hold for local quantum circuits connecting topological states in
different phases.


title: Generating geometry axioms from poset axioms

abstract:
  Two axioms of order geoemtry are the poset axioms of transitivity and
antisymmetry of the relation "is in front of" when looking from a point. From
these axioms, by looking from an interval instead of a point, further
well-known axioms of order geometry are generated in the following sense:
Transitivity when looking from an interval is equivalent to Assioma XIII of
paragraph 10 in G. Peano, I principii di geometria logacimente exposti.
Assuming this axiom, antisymmetry when looking from an interval is equivalent
VIII. Grundsatz in paragraph 1 in M. Pasch, Vorlesungen ueber neuere Geometrie.
Further equivalences, with some of the implications well-known, are proved
along the way.


title:
Global solutions for semilinear Klein-Gordon equations in FLRW
  spacetimes

abstract:
  We consider waves, which obey the semilinear Klein-Gordon equation,
propagating in the Friedmann-Lemaitre-Robertson-Walker spacetimes. The
equations in the de Sitter and Einstein-de Sitter spacetimes are the important
particular cases.
  We show the global in time existence in the energy class of solutions of the
Cauchy problem.


title:
Comparing the strength of diagonally non-recursive functions in the
  absence of $\Sigma^0_2$ induction

abstract:
  We prove that the statement "there is a $k$ such that for every $f$ there is
a $k$-bounded diagonally non-recursive function relative to $f$" does not imply
weak K\"onig's lemma over $\mathrm{RCA}_0 + \mathrm{B}\Sigma^0_2$. This answers
a question posed by Simpson. A recursion-theoretic consequence is that the
classic fact that every $k$-bounded diagonally non-recursive function computes
a $2$-bounded diagonally non-recursive function may fail in the absence of
$\mathrm{I}\Sigma^0_2$.


title:
Power Aware Wireless File Downloading: A Constrained Restless Bandit
  Approach

abstract:
  This paper treats power-aware throughput maximization in a multi-user file
downloading system. Each user can receive a new file only after its previous
file is finished. The file state processes for each user act as coupled Markov
chains that form a generalized restless bandit system. First, an optimal
algorithm is derived for the case of one user. The algorithm maximizes
throughput subject to an average power constraint. Next, the one-user algorithm
is extended to a low complexity heuristic for the multi-user problem. The
heuristic uses a simple online index policy and its effectiveness is shown via
simulation. For simple 3-user cases where the optimal solution can be computed
offline, the heuristic is shown to be near-optimal for a wide range of
parameters.


title: Reasoning About the Transfer of Control

abstract:
  We present DCL-PC: a logic for reasoning about how the abilities of agents
and coalitions of agents are altered by transferring control from one agent to
another. The logical foundation of DCL-PC is CL-PC, a logic for reasoning about
cooperation in which the abilities of agents and coalitions of agents stem from
a distribution of atomic Boolean variables to individual agents -- the choices
available to a coalition correspond to assignments to the variables the
coalition controls. The basic modal constructs of DCL-PC are of the form
coalition C can cooperate to bring about phi. DCL-PC extends CL-PC with dynamic
logic modalities in which atomic programs are of the form agent i gives control
of variable p to agent j; as usual in dynamic logic, these atomic programs may
be combined using sequence, iteration, choice, and test operators to form
complex programs. By combining such dynamic transfer programs with cooperation
modalities, it becomes possible to reason about how the power of agents and
coalitions is affected by the transfer of control. We give two alternative
semantics for the logic: a direct semantics, in which we capture the
distributions of Boolean variables to agents; and a more conventional Kripke
semantics. We prove that these semantics are equivalent, and then present an
axiomatization for the logic. We investigate the computational complexity of
model checking and satisfiability for DCL-PC, and show that both problems are
PSPACE-complete (and hence no worse than the underlying logic CL-PC). Finally,
we investigate the characterisation of control in DCL-PC. We distinguish
between first-order control -- the ability of an agent or coalition to control
some state of affairs through the assignment of values to the variables under
the control of the agent or coalition -- and second-order control -- the
ability of an agent to exert control over the control that other agents have by
transferring variables to other agents. We give a logical characterisation of
second-order control.


title: Adversary Lower Bound for Element Distinctness with Small Range

abstract:
  The Element Distinctness problem is to decide whether each character of an
input string is unique. The quantum query complexity of Element Distinctness is
known to be $\Theta(N^{2/3})$; the polynomial method gives a tight lower bound
for any input alphabet, while a tight adversary construction was only known for
alphabets of size $\Omega(N^2)$.
  We construct a tight $\Omega(N^{2/3})$ adversary lower bound for Element
Distinctness with minimal non-trivial alphabet size, which equals the length of
the input. This result may help to improve lower bounds for other related query
problems.


title: Efficient Planning under Uncertainty with Macro-actions

abstract:
  Deciding how to act in partially observable environments remains an active
area of research. Identifying good sequences of decisions is particularly
challenging when good control performance requires planning multiple steps into
the future in domains with many states. Towards addressing this challenge, we
present an online, forward-search algorithm called the Posterior Belief
Distribution (PBD). PBD leverages a novel method for calculating the posterior
distribution over beliefs that result after a sequence of actions is taken,
given the set of observation sequences that could be received during this
process. This method allows us to efficiently evaluate the expected reward of a
sequence of primitive actions, which we refer to as macro-actions. We present a
formal analysis of our approach, and examine its performance on two very large
simulation experiments: scientific exploration and a target monitoring domain.
We also demonstrate our algorithm being used to control a real robotic
helicopter in a target monitoring experiment, which suggests that our approach
has practical potential for planning in real-world, large partially observable
domains where a multi-step lookahead is required to achieve good performance.


title: On periodic solutions and their modulations for the Manakov system

abstract:
  Periodic solutions of the Manakov system are studied with the aim to
establish links between recent results of Wright (Physica D 2013 {\bf 264} 1)
and Kamchatnov (EPL 2013 \textbf{103} 60003), where the one-phase solutions
have been obtained by different methods and with different parameterizations.
Two types of waves, which in the context of dynamics of two-component
Bose-Einstein condensates can be called {\it density} and {\it polarization}
waves, are determined as particular solutions of the Manakov system. Whitham
equations describing modulations of these two types of waves are obtained.


title: RoxyBot-06: Stochastic Prediction and Optimization in TAC Travel

abstract:
  In this paper, we describe our autonomous bidding agent, RoxyBot, who emerged
victorious in the travel division of the 2006 Trading Agent Competition in a
photo finish. At a high level, the design of many successful trading agents can
be summarized as follows: (i) price prediction: build a model of market prices;
and (ii) optimization: solve for an approximately optimal set of bids, given
this model. To predict, RoxyBot builds a stochastic model of market prices by
simulating simultaneous ascending auctions. To optimize, RoxyBot relies on the
sample average approximation method, a stochastic optimization technique.


title: Interactive Cost Configuration Over Decision Diagrams

abstract:
  In many AI domains such as product configuration, a user should interactively
specify a solution that must satisfy a set of constraints. In such scenarios,
offline compilation of feasible solutions into a tractable representation is an
important approach to delivering efficient backtrack-free user interaction
online. In particular,binary decision diagrams (BDDs) have been successfully
used as a compilation target for product and service configuration. In this
paper we discuss how to extend BDD-based configuration to scenarios involving
cost functions which express user preferences.
  We first show that an efficient, robust and easy to implement extension is
possible if the cost function is additive, and feasible solutions are
represented using multi-valued decision diagrams (MDDs). We also discuss the
effect on MDD size if the cost function is non-additive or if it is encoded
explicitly into MDD. We then discuss interactive configuration in the presence
of multiple cost functions. We prove that even in its simplest form,
multiple-cost configuration is NP-hard in the input MDD. However, for solving
two-cost configuration we develop a pseudo-polynomial scheme and a fully
polynomial approximation scheme. The applicability of our approach is
demonstrated through experiments over real-world configuration models and
product-catalogue datasets. Response times are generally within a fraction of a
second even for very large instances.


title:
An Investigation into Mathematical Programming for Finite Horizon
  Decentralized POMDPs

abstract:
  Decentralized planning in uncertain environments is a complex task generally
dealt with by using a decision-theoretic approach, mainly through the framework
of Decentralized Partially Observable Markov Decision Processes (DEC-POMDPs).
Although DEC-POMDPS are a general and powerful modeling tool, solving them is a
task with an overwhelming complexity that can be doubly exponential. In this
paper, we study an alternate formulation of DEC-POMDPs relying on a
sequence-form representation of policies. From this formulation, we show how to
derive Mixed Integer Linear Programming (MILP) problems that, once solved, give
exact optimal solutions to the DEC-POMDPs. We show that these MILPs can be
derived either by using some combinatorial characteristics of the optimal
solutions of the DEC-POMDPs or by using concepts borrowed from game theory.
Through an experimental validation on classical test problems from the
DEC-POMDP literature, we compare our approach to existing algorithms. Results
show that mathematical programming outperforms dynamic programming but is less
efficient than forward search, except for some particular problems. The main
contributions of this work are the use of mathematical programming for
DEC-POMDPs and a better understanding of DEC-POMDPs and of their solutions.
Besides, we argue that our alternate representation of DEC-POMDPs could be
helpful for designing novel algorithms looking for approximate solutions to
DEC-POMDPs.


title: Constructing Reference Sets from Unstructured, Ungrammatical Text

abstract:
  Vast amounts of text on the Web are unstructured and ungrammatical, such as
classified ads, auction listings, forum postings, etc. We call such text
"posts." Despite their inconsistent structure and lack of grammar, posts are
full of useful information. This paper presents work on semi-automatically
building tables of relational information, called "reference sets," by
analyzing such posts directly. Reference sets can be applied to a number of
tasks such as ontology maintenance and information extraction. Our
reference-set construction method starts with just a small amount of background
knowledge, and constructs tuples representing the entities in the posts to form
a reference set. We also describe an extension to this approach for the special
case where even this small amount of background knowledge is impossible to
discover and use. To evaluate the utility of the machine-constructed reference
sets, we compare them to manually constructed reference sets in the context of
reference-set-based information extraction. Our results show the reference sets
constructed by our method outperform manually constructed reference sets. We
also compare the reference-set-based extraction approach using the
machine-constructed reference set to supervised extraction approaches using
generic features. These results demonstrate that using machine-constructed
reference sets outperforms the supervised methods, even though the supervised
methods require training data.


title: Active Tuples-based Scheme for Bounding Posterior Beliefs

abstract:
  The paper presents a scheme for computing lower and upper bounds on the
posterior marginals in Bayesian networks with discrete variables. Its power
lies in its ability to use any available scheme that bounds the probability of
evidence or posterior marginals and enhance its performance in an anytime
manner. The scheme uses the cutset conditioning principle to tighten existing
bounding schemes and to facilitate anytime behavior, utilizing a fixed number
of cutset tuples. The accuracy of the bounds improves as the number of used
cutset tuples increases and so does the computation time. We demonstrate
empirically the value of our scheme for bounding posterior marginals and
probability of evidence using a variant of the bound propagation algorithm as a
plug-in scheme.


title: Mechanisms for Multi-Unit Auctions

abstract:
  We present an incentive-compatible polynomial-time approximation scheme for
multi-unit auctions with general k-minded player valuations. The mechanism
fully optimizes over an appropriately chosen sub-range of possible allocations
and then uses VCG payments over this sub-range. We show that obtaining a fully
polynomial-time incentive-compatible approximation scheme, at least using VCG
payments, is NP-hard. For the case of valuations given by black boxes, we give
a polynomial-time incentive-compatible 2-approximation mechanism and show that
no better is possible, at least using VCG payments.


title: On Action Theory Change

abstract:
  As historically acknowledged in the Reasoning about Actions and Change
community, intuitiveness of a logical domain description cannot be fully
automated. Moreover, like any other logical theory, action theories may also
evolve, and thus knowledge engineers need revision methods to help in
accommodating new incoming information about the behavior of actions in an
adequate manner. The present work is about changing action domain descriptions
in multimodal logic. Its contribution is threefold: first we revisit the
semantics of action theory contraction proposed in previous work, giving more
robust operators that express minimal change based on a notion of distance
between Kripke-models. Second we give algorithms for syntactical action theory
contraction and establish their correctness with respect to our semantics for
those action theories that satisfy a principle of modularity investigated in
previous work. Since modularity can be ensured for every action theory and, as
we show here, needs to be computed at most once during the evolution of a
domain description, it does not represent a limitation at all to the method
here studied. Finally we state AGM-like postulates for action theory
contraction and assess the behavior of our operators with respect to them.
Moreover, we also address the revision counterpart of action theory change,
showing that it benefits from our semantics for contraction.


title:
An Active Learning Approach for Jointly Estimating Worker Performance
  and Annotation Reliability with Crowdsourced Data

abstract:
  Crowdsourcing platforms offer a practical solution to the problem of
affordably annotating large datasets for training supervised classifiers.
Unfortunately, poor worker performance frequently threatens to compromise
annotation reliability, and requesting multiple labels for every instance can
lead to large cost increases without guaranteeing good results. Minimizing the
required training samples using an active learning selection procedure reduces
the labeling requirement but can jeopardize classifier training by focusing on
erroneous annotations. This paper presents an active learning approach in which
worker performance, task difficulty, and annotation reliability are jointly
estimated and used to compute the risk function guiding the sample selection
procedure. We demonstrate that the proposed approach, which employs active
learning with Bayesian networks, significantly improves training accuracy and
correctly ranks the expertise of unknown labelers in the presence of annotation
noise.


title: Mixed Strategies in Combinatorial Agency

abstract:
  In many multiagent domains a set of agents exert effort towards a joint
outcome, yet the individual effort levels cannot be easily observed. A typical
example for such a scenario is routing in communication networks, where the
sender can only observe whether the packet reached its destination, but often
has no information about the actions of the intermediate routers, which
influences the final outcome. We study a setting where a principal needs to
motivate a team of agents whose combination of hidden efforts stochastically
determines an outcome. In a companion paper we devise and study a basic
combinatorial agency model for this setting, where the principal is restricted
to inducing a pure Nash equilibrium. Here we study various implications of this
restriction. First, we show that, in contrast to the case of observable
efforts, inducing a mixed-strategies equilibrium may be beneficial for the
principal. Second, we present a sufficient condition for technologies for which
no gain can be generated. Third, we bound the principals gain for various
families of technologies. Finally, we study the robustness of mixed equilibria
to coalitional deviations and the computational hardness of the optimal mixed
equilibria.


title: Change in Abstract Argumentation Frameworks: Adding an Argument

abstract:
  In this paper, we address the problem of change in an abstract argumentation
system. We focus on a particular change: the addition of a new argument which
interacts with previous arguments. We study the impact of such an addition on
the outcome of the argumentation system, more particularly on the set of its
extensions. Several properties for this change operation are defined by
comparing the new set of extensions to the initial one, these properties are
called structural when the comparisons are based on set-cardinality or
set-inclusion relations. Several other properties are proposed where
comparisons are based on the status of some particular arguments: the accepted
arguments; these properties refer to the evolution of this status during the
change, e.g., Monotony and Priority to Recency. All these properties may be
more or less desirable according to specific applications. They are studied
under two particular semantics: the grounded and preferred semantics.


title: The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks

abstract:
  LAMA is a classical planning system based on heuristic forward search. Its
core feature is the use of a pseudo-heuristic derived from landmarks,
propositional formulas that must be true in every solution of a planning task.
LAMA builds on the Fast Downward planning system, using finite-domain rather
than binary state variables and multi-heuristic search. The latter is employed
to combine the landmark heuristic with a variant of the well-known FF
heuristic. Both heuristics are cost-sensitive, focusing on high-quality
solutions in the case where actions have non-uniform cost. A weighted A* search
is used with iteratively decreasing weights, so that the planner continues to
search for plans of better quality until the search is terminated. LAMA showed
best performance among all planners in the sequential satisficing track of the
International Planning Competition 2008. In this paper we present the system in
detail and investigate which features of LAMA are crucial for its performance.
We present individual results for some of the domains used at the competition,
demonstrating good and bad cases for the techniques implemented in LAMA.
Overall, we find that using landmarks improves performance, whereas the
incorporation of action costs into the heuristic estimators proves not to be
beneficial. We show that in some domains a search that ignores cost solves far
more problems, raising the question of how to deal with action costs more
effectively in the future. The iterated weighted A* search greatly improves
results, and shows synergy effects with the use of landmarks.


title: Grounding FO and FO(ID) with Bounds

abstract:
  Grounding is the task of reducing a first-order theory and finite domain to
an equivalent propositional theory. It is used as preprocessing phase in many
logic-based reasoning systems. Such systems provide a rich first-order input
language to a user and can rely on efficient propositional solvers to perform
the actual reasoning. Besides a first-order theory and finite domain, the input
for grounders contains in many applications also additional data. By exploiting
this data, the size of the grounders output can often be reduced significantly.
A common practice to improve the efficiency of a grounder in this context is by
manually adding semantically redundant information to the input theory,
indicating where and when the grounder should exploit the data. In this paper
we present a method to compute and add such redundant information
automatically. Our method therefore simplifies the task of writing input
theories that can be grounded efficiently by current systems. We first present
our method for classical first-order logic (FO) theories. Then we extend it to
FO(ID), the extension of FO with inductive definitions, which allows for more
concise and comprehensive input theories. We discuss implementation issues and
experimentally validate the practical applicability of our method.


title: Narrative Planning: Balancing Plot and Character

abstract:
  Narrative, and in particular storytelling, is an important part of the human
experience. Consequently, computational systems that can reason about narrative
can be more effective communicators, entertainers, educators, and trainers. One
of the central challenges in computational narrative reasoning is narrative
generation, the automated creation of meaningful event sequences. There are
many factors -- logical and aesthetic -- that contribute to the success of a
narrative artifact. Central to this success is its understandability. We argue
that the following two attributes of narratives are universal: (a) the logical
causal progression of plot, and (b) character believability. Character
believability is the perception by the audience that the actions performed by
characters do not negatively impact the audiences suspension of disbelief.
Specifically, characters must be perceived by the audience to be intentional
agents. In this article, we explore the use of refinement search as a technique
for solving the narrative generation problem -- to find a sound and believable
sequence of character actions that transforms an initial world state into a
world state in which goal propositions hold. We describe a novel refinement
search planning algorithm -- the Intent-based Partial Order Causal Link (IPOCL)
planner -- that, in addition to creating causally sound plot progression,
reasons about character intentionality by identifying possible character goals
that explain their actions and creating plan structures that explain why those
characters commit to their goals. We present the results of an empirical
evaluation that demonstrates that narrative plans generated by the IPOCL
algorithm support audience comprehension of character intentions better than
plans generated by conventional partial-order planners.


title:
Developing Approaches for Solving a Telecommunications Feature
  Subscription Problem

abstract:
  Call control features (e.g., call-divert, voice-mail) are primitive options
to which users can subscribe off-line to personalise their service. The
configuration of a feature subscription involves choosing and sequencing
features from a catalogue and is subject to constraints that prevent
undesirable feature interactions at run-time. When the subscription requested
by a user is inconsistent, one problem is to find an optimal relaxation, which
is a generalisation of the feedback vertex set problem on directed graphs, and
thus it is an NP-hard task. We present several constraint programming
formulations of the problem. We also present formulations using partial
weighted maximum Boolean satisfiability and mixed integer linear programming.
We study all these formulations by experimentally comparing them on a variety
of randomly generated instances of the feature subscription problem.


title: Theta*: Any-Angle Path Planning on Grids

abstract:
  Grids with blocked and unblocked cells are often used to represent terrain in
robotics and video games. However, paths formed by grid edges can be longer
than true shortest paths in the terrain since their headings are artificially
constrained. We present two new correct and complete any-angle path-planning
algorithms that avoid this shortcoming. Basic Theta* and Angle-Propagation
Theta* are both variants of A* that propagate information along grid edges
without constraining paths to grid edges. Basic Theta* is simple to understand
and implement, fast and finds short paths. However, it is not guaranteed to
find true shortest paths. Angle-Propagation Theta* achieves a better worst-case
complexity per vertex expansion than Basic Theta* by propagating angle ranges
when it expands vertices, but is more complex, not as fast and finds slightly
longer paths. We refer to Basic Theta* and Angle-Propagation Theta*
collectively as Theta*. Theta* has unique properties, which we analyze in
detail. We show experimentally that it finds shorter paths than both A* with
post-smoothed paths and Field D* (the only other version of A* we know of that
propagates information along grid edges without constraining paths to grid
edges) with a runtime comparable to that of A* on grids. Finally, we extend
Theta* to grids that contain unblocked cells with non-uniform traversal costs
and introduce variants of Theta* which provide different tradeoffs between path
length and runtime.


title: Multiattribute Auctions Based on Generalized Additive Independence

abstract:
  We develop multiattribute auctions that accommodate generalized additive
independent (GAI) preferences. We propose an iterative auction mechanism that
maintains prices on potentially overlapping GAI clusters of attributes, thus
decreases elicitation and computational burden, and creates an open competition
among suppliers over a multidimensional domain. Most significantly, the auction
is guaranteed to achieve surplus which approximates optimal welfare up to a
small additive factor, under reasonable equilibrium strategies of traders. The
main departure of GAI auctions from previous literature is to accommodate
non-additive trader preferences, hence allowing traders to condition their
evaluation of specific attributes on the value of other attributes. At the same
time, the GAI structure supports a compact representation of prices, enabling a
tractable auction process. We perform a simulation study, demonstrating and
quantifying the significant efficiency advantage of more expressive preference
modeling. We draw random GAI-structured utility functions with various internal
structures, generate additive functions that approximate the GAI utility, and
compare the performance of the auctions using the two representations. We find
that allowing traders to express existing dependencies among attributes
improves the economic efficiency of multiattribute auctions.


title:
Resource-Driven Mission-Phasing Techniques for Constrained Agents in
  Stochastic Environments

abstract:
  Because an agents resources dictate what actions it can possibly take, it
should plan which resources it holds over time carefully, considering its
inherent limitations (such as power or payload restrictions), the competing
needs of other agents for the same resources, and the stochastic nature of the
environment. Such agents can, in general, achieve more of their objectives if
they can use --- and even create --- opportunities to change which resources
they hold at various times. Driven by resource constraints, the agents could
break their overall missions into an optimal series of phases, optimally
reconfiguring their resources at each phase, and optimally using their assigned
resources in each phase, given their knowledge of the stochastic environment.
In this paper, we formally define and analyze this constrained, sequential
optimization problem in both the single-agent and multi-agent contexts. We
present a family of mixed integer linear programming (MILP) formulations of
this problem that can optimally create phases (when phases are not predefined)
accounting for costs and limitations in phase creation. Because our
formulations multaneously also find the optimal allocations of resources at
each phase and the optimal policies for using the allocated resources at each
phase, they exploit structure across these coupled problems. This allows them
to find solutions significantly faster(orders of magnitude faster in larger
problems) than alternative solution techniques, as we demonstrate empirically.


title: Fast Set Bounds Propagation Using a BDD-SAT Hybrid

abstract:
  Binary Decision Diagram (BDD) based set bounds propagation is a powerful
approach to solving set-constraint satisfaction problems. However, prior BDD
based techniques in- cur the significant overhead of constructing and
manipulating graphs during search. We present a set-constraint solver which
combines BDD-based set-bounds propagators with the learning abilities of a
modern SAT solver. Together with a number of improvements beyond the basic
algorithm, this solver is highly competitive with existing propagation based
set constraint solvers.


title: Automatic Induction of Bellman-Error Features for Probabilistic Planning

abstract:
  Domain-specific features are important in representing problem structure
throughout machine learning and decision-theoretic planning. In planning, once
state features are provided, domain-independent algorithms such as approximate
value iteration can learn weighted combinations of those features that often
perform well as heuristic estimates of state value (e.g., distance to the
goal). Successful applications in real-world domains often require features
crafted by human experts. Here, we propose automatic processes for learning
useful domain-specific feature sets with little or no human intervention. Our
methods select and add features that describe state-space regions of high
inconsistency in the Bellman equation (statewise Bellman error) during
approximate value iteration. Our method can be applied using any
real-valued-feature hypothesis space and corresponding learning method for
selecting features from training sets of state-value pairs. We evaluate the
method with hypothesis spaces defined by both relational and propositional
feature languages, using nine probabilistic planning domains. We show that
approximate value iteration using a relational feature space performs at the
state-of-the-art in domain-independent stochastic relational planning. Our
method provides the first domain-independent approach that plays Tetris
successfully (without human-engineered features).


title: Approximate Model-Based Diagnosis Using Greedy Stochastic Search

abstract:
  We propose a StochAstic Fault diagnosis AlgoRIthm, called SAFARI, which
trades off guarantees of computing minimal diagnoses for computational
efficiency. We empirically demonstrate, using the 74XXX and ISCAS-85 suites of
benchmark combinatorial circuits, that SAFARI achieves several
orders-of-magnitude speedup over two well-known deterministic algorithms, CDA*
and HA*, for multiple-fault diagnoses; further, SAFARI can compute a range of
multiple-fault diagnoses that CDA* and HA* cannot. We also prove that SAFARI is
optimal for a range of propositional fault models, such as the widely-used
weak-fault models (models with ignorance of abnormal behavior). We discuss the
optimality of SAFARI in a class of strong-fault circuit models with stuck-at
failure modes. By modeling the algorithm itself as a Markov chain, we provide
exact bounds on the minimality of the diagnosis computed. SAFARI also displays
strong anytime behavior, and will return a diagnosis after any non-trivial
inference time.


title:
Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity
  is your Friend!

abstract:
  Description Logics are knowledge representation formalisms that provide, for
example, the logical underpinning of the W3C OWL standards. Conjunctive
queries, the standard query language in databases, have recently gained
significant attention as an expressive formalism for querying Description Logic
knowledge bases. Several different techniques for deciding conjunctive query
entailment are available for a wide range of DLs. Nevertheless, the combination
of nominals, inverse roles, and number restrictions in OWL 1 and OWL 2 DL
causes unsolvable problems for the techniques hitherto available. We tackle
this problem and present a decidability result for entailment of unions of
conjunctive queries in the DL ALCHOIQb that contains all three problematic
constructors simultaneously. Provided that queries contain only simple roles,
our result also shows decidability of entailment of (unions of) conjunctive
queries in the logic that underpins OWL 1 DL and we believe that the presented
results will pave the way for further progress towards conjunctive query
entailment decision procedures for the Description Logics underlying the OWL
standards.


title: A Model-Based Active Testing Approach to Sequential Diagnosis

abstract:
  Model-based diagnostic reasoning often leads to a large number of diagnostic
hypotheses. The set of diagnoses can be reduced by taking into account extra
observations (passive monitoring), measuring additional variables (probing) or
executing additional tests (sequential diagnosis/test sequencing). In this
paper we combine the above approaches with techniques from Automated Test
Pattern Generation (ATPG) and Model-Based Diagnosis (MBD) into a framework
called FRACTAL (FRamework for ACtive Testing ALgorithms). Apart from the inputs
and outputs that connect a system to its environment, in active testing we
consider additional input variables to which a sequence of test vectors can be
supplied. We address the computationally hard problem of computing optimal
control assignments (as defined in FRACTAL) in terms of a greedy approximation
algorithm called FRACTAL-G. We compare the decrease in the number of remaining
minimal cardinality diagnoses of FRACTAL-G to that of two more FRACTAL
algorithms: FRACTAL-ATPG and FRACTAL-P. FRACTAL-ATPG is based on ATPG and
sequential diagnosis while FRACTAL-P is based on probing and, although not an
active testing algorithm, provides a baseline for comparing the lower bound on
the number of reachable diagnoses for the FRACTAL algorithms. We empirically
evaluate the trade-offs of the three FRACTAL algorithms by performing extensive
experimentation on the ISCAS85/74XXX benchmark of combinational circuits.


title: Intrusion Detection using Continuous Time Bayesian Networks

abstract:
  Intrusion detection systems (IDSs) fall into two high-level categories:
network-based systems (NIDS) that monitor network behaviors, and host-based
systems (HIDS) that monitor system calls. In this work, we present a general
technique for both systems. We use anomaly detection, which identifies patterns
not conforming to a historic norm. In both types of systems, the rates of
change vary dramatically over time (due to burstiness) and over components (due
to service difference). To efficiently model such systems, we use continuous
time Bayesian networks (CTBNs) and avoid specifying a fixed update interval
common to discrete-time models. We build generative models from the normal
training data, and abnormal behaviors are flagged based on their likelihood
under this norm. For NIDS, we construct a hierarchical CTBN model for the
network packet traces and use Rao-Blackwellized particle filtering to learn the
parameters. We illustrate the power of our method through experiments on
detecting real worms and identifying hosts on two publicly available network
traces, the MAWI dataset and the LBNL dataset. For HIDS, we develop a novel
learning method to deal with the finite resolution of system log file time
stamps, without losing the benefits of our continuous time model. We
demonstrate the method by detecting intrusions in the DARPA 1998 BSM dataset.


title:
Non-Transferable Utility Coalitional Games via Mixed-Integer Linear
  Constraints

abstract:
  Coalitional games serve the purpose of modeling payoff distribution problems
in scenarios where agents can collaborate by forming coalitions in order to
obtain higher worths than by acting in isolation. In the classical Transferable
Utility (TU) setting, coalition worths can be freely distributed amongst
agents. However, in several application scenarios, this is not the case and the
Non-Transferable Utility setting (NTU) must be considered, where additional
application-oriented constraints are imposed on the possible worth
distributions. In this paper, an approach to define NTU games is proposed which
is based on describing allowed distributions via a set of mixed-integer linear
constraints applied to an underlying TU game. It is shown that such games allow
non-transferable conditions on worth distributions to be specified in a natural
and succinct way. The properties and the relationships among the most prominent
solution concepts for NTU games that hold when they are applied on
(mixed-integer) constrained games are investigated. Finally, a thorough
analysis is carried out to assess the impact of issuing constraints on the
computational complexity of some of these solution concepts.


title: Implicit Abstraction Heuristics

abstract:
  State-space search with explicit abstraction heuristics is at the state of
the art of cost-optimal planning. These heuristics are inherently limited,
nonetheless, because the size of the abstract space must be bounded by some,
even if a very large, constant. Targeting this shortcoming, we introduce the
notion of (additive) implicit abstractions, in which the planning task is
abstracted by instances of tractable fragments of optimal planning. We then
introduce a concrete setting of this framework, called fork-decomposition, that
is based on two novel fragments of tractable cost-optimal planning. The induced
admissible heuristics are then studied formally and empirically. This study
testifies for the accuracy of the fork decomposition heuristics, yet our
empirical evaluation also stresses the tradeoff between their accuracy and the
runtime complexity of computing them. Indeed, some of the power of the explicit
abstraction heuristics comes from precomputing the heuristic function offline
and then determining h(s) for each evaluated state s by a very fast lookup in a
database. By contrast, while fork-decomposition heuristics can be calculated in
polynomial time, computing them is far from being fast. To address this
problem, we show that the time-per-node complexity bottleneck of the
fork-decomposition heuristics can be successfully overcome. We demonstrate that
an equivalent of the explicit abstraction notion of a database exists for the
fork-decomposition abstractions as well, despite their exponential-size
abstract spaces. We then verify empirically that heuristic search with the
databased" fork-decomposition heuristics favorably competes with the state of
the art of cost-optimal planning.


title:
A Constraint Satisfaction Framework for Executing Perceptions and
  Actions in Diagrammatic Reasoning

abstract:
  Diagrammatic reasoning (DR) is pervasive in human problem solving as a
powerful adjunct to symbolic reasoning based on language-like representations.
The research reported in this paper is a contribution to building a general
purpose DR system as an extension to a SOAR-like problem solving architecture.
The work is in a framework in which DR is modeled as a process where subtasks
are solved, as appropriate, either by inference from symbolic representations
or by interaction with a diagram, i.e., perceiving specified information from a
diagram or modifying/creating objects in a diagram in specified ways according
to problem solving needs. The perceptions and actions in most DR systems built
so far are hand-coded for the specific application, even when the rest of the
system is built using the general architecture. The absence of a general
framework for executing perceptions/actions poses as a major hindrance to using
them opportunistically -- the essence of open-ended search in problem solving.
Our goal is to develop a framework for executing a wide variety of specified
perceptions and actions across tasks/domains without human intervention. We
observe that the domain/task-specific visual perceptions/actions can be
transformed into domain/task-independent spatial problems. We specify a spatial
problem as a quantified constraint satisfaction problem in the real domain
using an open-ended vocabulary of properties, relations and actions involving
three kinds of diagrammatic objects -- points, curves, regions. Solving a
spatial problem from this specification requires computing the equivalent
simplified quantifier-free expression, the complexity of which is inherently
doubly exponential. We represent objects as configuration of simple elements to
facilitate decomposition of complex problems into simpler and similar
subproblems. We show that, if the symbolic solution to a subproblem can be
expressed concisely, quantifiers can be eliminated from spatial problems in
low-order polynomial time using similar previously solved subproblems. This
requires determining the similarity of two problems, the existence of a mapping
between them computable in polynomial time, and designing a memory for storing
previously solved problems so as to facilitate search. The efficacy of the idea
is shown by time complexity analysis. We demonstrate the proposed approach by
executing perceptions and actions involved in DR tasks in two army
applications.


title: Algorithms for Closed Under Rational Behavior (CURB) Sets

abstract:
  We provide a series of algorithms demonstrating that solutions according to
the fundamental game-theoretic solution concept of closed under rational
behavior (CURB) sets in two-player, normal-form games can be computed in
polynomial time (we also discuss extensions to n-player games). First, we
describe an algorithm that identifies all of a player's best responses
conditioned on the belief that the other player will play from within a given
subset of its strategy space. This algorithm serves as a subroutine in a series
of polynomial-time algorithms for finding all minimal CURB sets, one minimal
CURB set, and the smallest minimal CURB set in a game. We then show that the
complexity of finding a Nash equilibrium can be exponential only in the size of
a game's smallest CURB set. Related to this, we show that the smallest CURB set
can be an arbitrarily small portion of the game, but it can also be arbitrarily
larger than the supports of its only enclosed Nash equilibrium. We test our
algorithms empirically and find that most commonly studied academic games tend
to have either very large or very small minimal CURB sets.


title: Cooperative Games with Overlapping Coalitions

abstract:
  In the usual models of cooperative game theory, the outcome of a coalition
formation process is either the grand coalition or a coalition structure that
consists of disjoint coalitions. However, in many domains where coalitions are
associated with tasks, an agent may be involved in executing more than one
task, and thus may distribute his resources among several coalitions. To tackle
such scenarios, we introduce a model for cooperative games with overlapping
coalitions--or overlapping coalition formation (OCF) games. We then explore the
issue of stability in this setting. In particular, we introduce a notion of the
core, which generalizes the corresponding notion in the traditional
(non-overlapping) scenario. Then, under some quite general conditions, we
characterize the elements of the core, and show that any element of the core
maximizes the social welfare. We also introduce a concept of balancedness for
overlapping coalitional games, and use it to characterize coalition structures
that can be extended to elements of the core. Finally, we generalize the notion
of convexity to our setting, and show that under some natural assumptions
convex games have a non-empty core. Moreover, we introduce two alternative
notions of stability in OCF that allow a wider range of deviations, and explore
the relationships among the corresponding definitions of the core, as well as
the classic (non-overlapping) core and the Aubin core. We illustrate the
general properties of the three cores, and also study them from a computational
perspective, thus obtaining additional insights into their fundamental
structure.


title:
Case-Based Subgoaling in Real-Time Heuristic Search for Video Game
  Pathfinding

abstract:
  Real-time heuristic search algorithms satisfy a constant bound on the amount
of planning per action, independent of problem size. As a result, they scale up
well as problems become larger. This property would make them well suited for
video games where Artificial Intelligence controlled agents must react quickly
to user commands and to other agents actions. On the downside, real-time search
algorithms employ learning methods that frequently lead to poor solution
quality and cause the agent to appear irrational by re-visiting the same
problem states repeatedly. The situation changed recently with a new algorithm,
D LRTA*, which attempted to eliminate learning by automatically selecting
subgoals. D LRTA* is well poised for video games, except it has a complex and
memory-demanding pre-computation phase during which it builds a database of
subgoals. In this paper, we propose a simpler and more memory-efficient way of
pre-computing subgoals thereby eliminating the main obstacle to applying
state-of-the-art real-time search methods in video games. The new algorithm
solves a number of randomly chosen problems off-line, compresses the solutions
into a series of subgoals and stores them in a database. When presented with a
novel problem on-line, it queries the database for the most similar previously
solved case and uses its subgoals to solve the problem. In the domain of
pathfinding on four large video game maps, the new algorithm delivers solutions
eight times better while using 57 times less memory and requiring 14% less
pre-computation time.


title: Logical Foundations of RDF(S) with Datatypes

abstract:
  The Resource Description Framework (RDF) is a Semantic Web standard that
provides a data language, simply called RDF, as well as a lightweight ontology
language, called RDF Schema. We investigate embeddings of RDF in logic and show
how standard logic programming and description logic technology can be used for
reasoning with RDF. We subsequently consider extensions of RDF with datatype
support, considering D entailment, defined in the RDF semantics specification,
and D* entailment, a semantic weakening of D entailment, introduced by ter
Horst. We use the embeddings and properties of the logics to establish novel
upper bounds for the complexity of deciding entailment. We subsequently
establish two novel lower bounds, establishing that RDFS entailment is
PTime-complete and that simple-D entailment is coNP-hard, when considering
arbitrary datatypes, both in the size of the entailing graph. The results
indicate that RDFS may not be as lightweight as one may expect.


title: A Utility-Theoretic Approach to Privacy in Online Services

abstract:
  Online offerings such as web search, news portals, and e-commerce
applications face the challenge of providing high-quality service to a large,
heterogeneous user base. Recent efforts have highlighted the potential to
improve performance by introducing methods to personalize services based on
special knowledge about users and their context. For example, a users
demographics, location, and past search and browsing may be useful in enhancing
the results offered in response to web search queries. However, reasonable
concerns about privacy by both users, providers, and government agencies acting
on behalf of citizens, may limit access by services to such information. We
introduce and explore an economics of privacy in personalization, where people
can opt to share personal information, in a standing or on-demand manner, in
return for expected enhancements in the quality of an online service. We focus
on the example of web search and formulate realistic objective functions for
search efficacy and privacy. We demonstrate how we can find a provably
near-optimal optimization of the utility-privacy tradeoff in an efficient
manner. We evaluate our methodology on data drawn from a log of the search
activity of volunteer participants. We separately assess users' preferences
about privacy and utility via a large-scale survey, aimed at eliciting
preferences about peoples' willingness to trade the sharing of personal data in
returns for gains in search efficiency. We show that a significant level of
personalization can be achieved using a relatively small amount of information
about users.


title: Planning with Noisy Probabilistic Relational Rules

abstract:
  Noisy probabilistic relational rules are a promising world model
representation for several reasons. They are compact and generalize over world
instantiations. They are usually interpretable and they can be learned
effectively from the action experiences in complex worlds. We investigate
reasoning with such rules in grounded relational domains. Our algorithms
exploit the compactness of rules for efficient and flexible decision-theoretic
planning. As a first approach, we combine these rules with the Upper Confidence
Bounds applied to Trees (UCT) algorithm based on look-ahead trees. Our second
approach converts these rules into a structured dynamic Bayesian network
representation and predicts the effects of action sequences using approximate
inference and beliefs over world states. We evaluate the effectiveness of our
approaches for planning in a simulated complex 3D robot manipulation scenario
with an articulated manipulator and realistic physics and in domains of the
probabilistic planning competition. Empirical results show that our methods can
solve problems where existing methods fail.


title: Best-First Heuristic Search for Multicore Machines

abstract:
  To harness modern multicore processors, it is imperative to develop parallel
versions of fundamental algorithms. In this paper, we compare different
approaches to parallel best-first search in a shared-memory setting. We present
a new method, PBNF, that uses abstraction to partition the state space and to
detect duplicate states without requiring frequent locking. PBNF allows
speculative expansions when necessary to keep threads busy. We identify and fix
potential livelock conditions in our approach, proving its correctness using
temporal logic. Our approach is general, allowing it to extend easily to
suboptimal and anytime heuristic search. In an empirical comparison on STRIPS
planning, grid pathfinding, and sliding tile puzzle problems using 8-core
machines, we show that A*, weighted A* and Anytime weighted A* implemented
using PBNF yield faster search than improved versions of previous parallel
search proposals.


title: A Probabilistic Approach for Maintaining Trust Based on Evidence

abstract:
  Leading agent-based trust models address two important needs. First, they
show how an agent may estimate the trustworthiness of another agent based on
prior interactions. Second, they show how agents may share their knowledge in
order to cooperatively assess the trustworthiness of others. However, in
real-life settings, information relevant to trust is usually obtained
piecemeal, not all at once. Unfortunately, the problem of maintaining trust has
drawn little attention. Existing approaches handle trust updates in a
heuristic, not a principled, manner. This paper builds on a formal model that
considers probability and certainty as two dimensions of trust. It proposes a
mechanism using which an agent can update the amount of trust it places in
other agents on an ongoing basis. This paper shows via simulation that the
proposed approach (a) provides accurate estimates of the trustworthiness of
agents that change behavior frequently; and (b) captures the dynamic behavior
of the agents. This paper includes an evaluation based on a real dataset drawn
from Amazon Marketplace, a leading e-commerce site.


title:
An Effective Algorithm for and Phase Transitions of the Directed
  Hamiltonian Cycle Problem

abstract:
  The Hamiltonian cycle problem (HCP) is an important combinatorial problem
with applications in many areas. It is among the first problems used for
studying intrinsic properties, including phase transitions, of combinatorial
problems. While thorough theoretical and experimental analyses have been made
on the HCP in undirected graphs, a limited amount of work has been done for the
HCP in directed graphs (DHCP). The main contribution of this work is an
effective algorithm for the DHCP. Our algorithm explores and exploits the close
relationship between the DHCP and the Assignment Problem (AP) and utilizes a
technique based on Boolean satisfiability (SAT). By combining effective
algorithms for the AP and SAT, our algorithm significantly outperforms previous
exact DHCP algorithms, including an algorithm based on the award-winning
Concorde TSP algorithm. The second result of the current study is an
experimental analysis of phase transitions of the DHCP, verifying and refining
a known phase transition of the DHCP.


title: A Logical Study of Partial Entailment

abstract:
  We introduce a novel logical notion--partial entailment--to propositional
logic. In contrast with classical entailment, that a formula P partially
entails another formula Q with respect to a background formula set \Gamma
intuitively means that under the circumstance of \Gamma, if P is true then some
"part" of Q will also be true. We distinguish three different kinds of partial
entailments and formalize them by using an extended notion of prime implicant.
We study their semantic properties, which show that, surprisingly, partial
entailments fail for many simple inference rules. Then, we study the related
computational properties, which indicate that partial entailments are
relatively difficult to be computed. Finally, we consider a potential
application of partial entailments in reasoning about rational agents.


title: Evaluating Temporal Graphs Built from Texts via Transitive Reduction

abstract:
  Temporal information has been the focus of recent attention in information
extraction, leading to some standardization effort, in particular for the task
of relating events in a text. This task raises the problem of comparing two
annotations of a given text, because relations between events in a story are
intrinsically interdependent and cannot be evaluated separately. A proper
evaluation measure is also crucial in the context of a machine learning
approach to the problem. Finding a common comparison referent at the text level
is not obvious, and we argue here in favor of a shift from event-based measures
to measures on a unique textual object, a minimal underlying temporal graph, or
more formally the transitive reduction of the graph of relations between event
boundaries. We support it by an investigation of its properties on synthetic
data and on a well-know temporal corpus.


title:
Automated Search for Impossibility Theorems in Social Choice Theory:
  Ranking Sets of Objects

abstract:
  We present a method for using standard techniques from satisfiability
checking to automatically verify and discover theorems in an area of economic
theory known as ranking sets of objects. The key question in this area, which
has important applications in social choice theory and decision making under
uncertainty, is how to extend an agents preferences over a number of objects to
a preference relation over nonempty sets of such objects. Certain combinations
of seemingly natural principles for this kind of preference extension can
result in logical inconsistencies, which has led to a number of important
impossibility theorems. We first prove a general result that shows that for a
wide range of such principles, characterised by their syntactic form when
expressed in a many-sorted first-order logic, any impossibility exhibited at a
fixed (small) domain size will necessarily extend to the general case. We then
show how to formulate candidates for impossibility theorems at a fixed domain
size in propositional logic, which in turn enables us to automatically search
for (general) impossibility theorems using a SAT solver. When applied to a
space of 20 principles for preference extension familiar from the literature,
this method yields a total of 84 impossibility theorems, including both known
and nontrivial new results.


title: Iterated Belief Change Due to Actions and Observations

abstract:
  In action domains where agents may have erroneous beliefs, reasoning about
the effects of actions involves reasoning about belief change. In this paper,
we use a transition system approach to reason about the evolution of an agents
beliefs as actions are executed. Some actions cause an agent to perform belief
revision while others cause an agent to perform belief update, but the
interaction between revision and update can be non-elementary. We present a set
of rationality properties describing the interaction between revision and
update, and we introduce a new class of belief change operators for reasoning
about alternating sequences of revisions and updates. Our belief change
operators can be characterized in terms of a natural shifting operation on
total pre-orderings over interpretations. We compare our approach with related
work on iterated belief change due to action, and we conclude with some
directions for future research.


title:
Clause-Learning Algorithms with Many Restarts and Bounded-Width
  Resolution

abstract:
  We offer a new understanding of some aspects of practical SAT-solvers that
are based on DPLL with unit-clause propagation, clause-learning, and restarts.
We do so by analyzing a concrete algorithm which we claim is faithful to what
practical solvers do. In particular, before making any new decision or restart,
the solver repeatedly applies the unit-resolution rule until saturation, and
leaves no component to the mercy of non-determinism except for some internal
randomness. We prove the perhaps surprising fact that, although the solver is
not explicitly designed for it, with high probability it ends up behaving as
width-k resolution after no more than O(n^2k+2) conflicts and restarts, where n
is the number of variables. In other words, width-k resolution can be thought
of as O(n^2k+2) restarts of the unit-resolution rule with learning.


title: False-Name Manipulations in Weighted Voting Games

abstract:
  Weighted voting is a classic model of cooperation among agents in
decision-making domains. In such games, each player has a weight, and a
coalition of players wins the game if its total weight meets or exceeds a given
quota. A players power in such games is usually not directly proportional to
his weight, and is measured by a power index, the most prominent among which
are the Shapley-Shubik index and the Banzhaf index.In this paper, we
investigate by how much a player can change his power, as measured by the
Shapley-Shubik index or the Banzhaf index, by means of a false-name
manipulation, i.e., splitting his weight among two or more identities. For both
indices, we provide upper and lower bounds on the effect of weight-splitting.
We then show that checking whether a beneficial split exists is NP-hard, and
discuss efficient algorithms for restricted cases of this problem, as well as
randomized algorithms for the general case. We also provide an experimental
evaluation of these algorithms. Finally, we examine related forms of
manipulative behavior, such as annexation, where a player subsumes other
players, or merging, where several players unite into one. We characterize the
computational complexity of such manipulations and provide limits on their
effects. For the Banzhaf index, we describe a new paradox, which we term the
Annexation Non-monotonicity Paradox.


title:
Learning to Make Predictions In Partially Observable Environments
  Without a Generative Model

abstract:
  When faced with the problem of learning a model of a high-dimensional
environment, a common approach is to limit the model to make only a restricted
set of predictions, thereby simplifying the learning problem. These partial
models may be directly useful for making decisions or may be combined together
to form a more complete, structured model. However, in partially observable
(non-Markov) environments, standard model-learning methods learn generative
models, i.e. models that provide a probability distribution over all possible
futures (such as POMDPs). It is not straightforward to restrict such models to
make only certain predictions, and doing so does not always simplify the
learning problem. In this paper we present prediction profile models:
non-generative partial models for partially observable systems that make only a
given set of predictions, and are therefore far simpler than generative models
in some cases. We formalize the problem of learning a prediction profile model
as a transformation of the original model-learning problem, and show
empirically that one can learn prediction profile models that make a small set
of important predictions even in systems that are too complex for standard
generative models.


title: Non-Deterministic Policies in Markovian Decision Processes

abstract:
  Markovian processes have long been used to model stochastic environments.
Reinforcement learning has emerged as a framework to solve sequential planning
and decision-making problems in such environments. In recent years, attempts
were made to apply methods from reinforcement learning to construct decision
support systems for action selection in Markovian environments. Although
conventional methods in reinforcement learning have proved to be useful in
problems concerning sequential decision-making, they cannot be applied in their
current form to decision support systems, such as those in medical domains, as
they suggest policies that are often highly prescriptive and leave little room
for the users input. Without the ability to provide flexible guidelines, it is
unlikely that these methods can gain ground with users of such systems. This
paper introduces the new concept of non-deterministic policies to allow more
flexibility in the users decision-making process, while constraining decisions
to remain near optimal solutions. We provide two algorithms to compute
non-deterministic policies in discrete domains. We study the output and running
time of these method on a set of synthetic and real-world problems. In an
experiment with human subjects, we show that humans assisted by hints based on
non-deterministic policies outperform both human-only and computer-only agents
in a web navigation task.


title: Second-Order Consistencies

abstract:
  In this paper, we propose a comprehensive study of second-order consistencies
(i.e., consistencies identifying inconsistent pairs of values) for constraint
satisfaction. We build a full picture of the relationships existing between
four basic second-order consistencies, namely path consistency (PC),
3-consistency (3C), dual consistency (DC) and 2-singleton arc consistency
(2SAC), as well as their conservative and strong variants. Interestingly, dual
consistency is an original property that can be established by using the
outcome of the enforcement of generalized arc consistency (GAC), which makes it
rather easy to obtain since constraint solvers typically maintain GAC during
search. On binary constraint networks, DC is equivalent to PC, but its
restriction to existing constraints, called conservative dual consistency
(CDC), is strictly stronger than traditional conservative consistencies derived
from path consistency, namely partial path consistency (PPC) and conservative
path consistency (CPC). After introducing a general algorithm to enforce strong
(C)DC, we present the results of an experimentation over a wide range of
benchmarks that demonstrate the interest of (conservative) dual consistency. In
particular, we show that enforcing (C)DC before search clearly improves the
performance of MAC (the algorithm that maintains GAC during search) on several
binary and non-binary structured problems.


title: Covariant Approach to the No-ghost Theorem in Massive Gravity

abstract:
  We discuss the no-ghost theorem in the massive gravity in a covariant manner.
Using the BRST formalism and St\"{u}ckelberg fields, we first clarify how the
Boulware-Deser ghost decouples in the massive gravity theory with Fierz-Pauli
mass term. Here we find that the crucial point in the proof is that there is no
higher (time) derivative for the St\"{u}ckelberg `scalar' field. We then
analyze the nonlinear massive gravity proposed by de Rham, Gabadadze and
Tolley, and show that there is no ghost for general admissible backgrounds. In
this process, we find a very nontrivial decoupling limit for general
backgrounds. We end the paper by demonstrating the general results explicitly
in a nontrivial example where there apparently appear higher time derivatives
for St\"{u}ckelberg scalar field, but show that this does not introduce the
ghost into the theory.


title: Identifying Aspects for Web-Search Queries

abstract:
  Many web-search queries serve as the beginning of an exploration of an
unknown space of information, rather than looking for a specific web page. To
answer such queries effec- tively, the search engine should attempt to organize
the space of relevant information in a way that facilitates exploration. We
describe the Aspector system that computes aspects for a given query. Each
aspect is a set of search queries that together represent a distinct
information need relevant to the original search query. To serve as an
effective means to explore the space, Aspector computes aspects that are
orthogonal to each other and to have high combined coverage. Aspector combines
two sources of information to compute aspects. We discover candidate aspects by
analyzing query logs, and cluster them to eliminate redundancies. We then use a
mass-collaboration knowledge base (e.g., Wikipedia) to compute candidate
aspects for queries that occur less frequently and to group together aspects
that are likely to be "semantically" related. We present a user study that
indicates that the aspects we compute are rated favorably against three
competing alternatives -related searches proposed by Google, cluster labels
assigned by the Clusty search engine, and navigational searches proposed by
Bing.


title:
On-line Planning and Scheduling: An Application to Controlling Modular
  Printers

abstract:
  We present a case study of artificial intelligence techniques applied to the
control of production printing equipment. Like many other real-world
applications, this complex domain requires high-speed autonomous
decision-making and robust continual operation. To our knowledge, this work
represents the first successful industrial application of embedded
domain-independent temporal planning. Our system handles execution failures and
multi-objective preferences. At its heart is an on-line algorithm that combines
techniques from state-space planning and partial-order scheduling. We suggest
that this general architecture may prove useful in other applications as more
intelligent systems operate in continual, on-line settings. Our system has been
used to drive several commercial prototypes and has enabled a new product
architecture for our industrial partner. When compared with state-of-the-art
off-line planners, our system is hundreds of times faster and often finds
better plans. Our experience demonstrates that domain-independent AI planning
based on heuristic search can flexibly handle time, resources, replanning, and
multiple objectives in a high-speed practical application without requiring
hand-coded control knowledge.


title: Determining Possible and Necessary Winners Given Partial Orders

abstract:
  Usually a voting rule requires agents to give their preferences as linear
orders. However, in some cases it is impractical for an agent to give a linear
order over all the alternatives. It has been suggested to let agents submit
partial orders instead. Then, given a voting rule, a profile of partial orders,
and an alternative (candidate) c, two important questions arise: first, is it
still possible for c to win, and second, is c guaranteed to win? These are the
possible winner and necessary winner problems, respectively. Each of these two
problems is further divided into two sub-problems: determining whether c is a
unique winner (that is, c is the only winner), or determining whether c is a
co-winner (that is, c is in the set of winners). We consider the setting where
the number of alternatives is unbounded and the votes are unweighted. We
completely characterize the complexity of possible/necessary winner problems
for the following common voting rules: a class of positional scoring rules
(including Borda), Copeland, maximin, Bucklin, ranked pairs, voting trees, and
plurality with runoff.


title: Properties of Bethe Free Energies and Message Passing in Gaussian Models

abstract:
  We address the problem of computing approximate marginals in Gaussian
probabilistic models by using mean field and fractional Bethe approximations.
We define the Gaussian fractional Bethe free energy in terms of the moment
parameters of the approximate marginals, derive a lower and an upper bound on
the fractional Bethe free energy and establish a necessary condition for the
lower bound to be bounded from below. It turns out that the condition is
identical to the pairwise normalizability condition, which is known to be a
sufficient condition for the convergence of the message passing algorithm. We
show that stable fixed points of the Gaussian message passing algorithm are
local minima of the Gaussian Bethe free energy. By a counterexample, we
disprove the conjecture stating that the unboundedness of the free energy
implies the divergence of the message passing algorithm.


title: Computing Small Unsatisfiable Cores in Satisfiability Modulo Theories

abstract:
  The problem of finding small unsatisfiable cores for SAT formulas has
recently received a lot of interest, mostly for its applications in formal
verification. However, propositional logic is often not expressive enough for
representing many interesting verification problems, which can be more
naturally addressed in the framework of Satisfiability Modulo Theories, SMT.
Surprisingly, the problem of finding unsatisfiable cores in SMT has received
very little attention in the literature. In this paper we present a novel
approach to this problem, called the Lemma-Lifting approach. The main idea is
to combine an SMT solver with an external propositional core extractor. The SMT
solver produces the theory lemmas found during the search, dynamically lifting
the suitable amount of theory information to the Boolean level. The core
extractor is then called on the Boolean abstraction of the original SMT problem
and of the theory lemmas. This results in an unsatisfiable core for the
original SMT problem, once the remaining theory lemmas are removed. The
approach is conceptually interesting, and has several advantages in practice.
In fact, it is extremely simple to implement and to update, and it can be
interfaced with every propositional core extractor in a plug-and-play manner,
so as to benefit for free of all unsat-core reduction techniques which have
been or will be made available.
  We have evaluated our algorithm with a very extensive empirical test on
SMT-LIB benchmarks, which confirms the validity and potential of this approach.


title: Soft Constraints of Difference and Equality

abstract:
  In many combinatorial problems one may need to model the diversity or
similarity of assignments in a solution. For example, one may wish to maximise
or minimise the number of distinct values in a solution. To formulate problems
of this type, we can use soft variants of the well known AllDifferent and
AllEqual constraints. We present a taxonomy of six soft global constraints,
generated by combining the two latter ones and the two standard cost functions,
which are either maximised or minimised. We characterise the complexity of
achieving arc and bounds consistency on these constraints, resolving those
cases for which NP-hardness was neither proven nor disproven. In particular, we
explore in depth the constraint ensuring that at least k pairs of variables
have a common value. We show that achieving arc consistency is NP-hard, however
achieving bounds consistency can be done in polynomial time through dynamic
programming. Moreover, we show that the maximum number of pairs of equal
variables can be approximated by a factor 1/2 with a linear time greedy
algorithm. Finally, we provide a fixed parameter tractable algorithm with
respect to the number of values appearing in more than two distinct domains.
Interestingly, this taxonomy shows that enforcing equality is harder than
enforcing difference.


title: Regression Conformal Prediction with Nearest Neighbours

abstract:
  In this paper we apply Conformal Prediction (CP) to the k-Nearest Neighbours
Regression (k-NNR) algorithm and propose ways of extending the typical
nonconformity measure used for regression so far. Unlike traditional regression
methods which produce point predictions, Conformal Predictors output predictive
regions that satisfy a given confidence level. The regions produced by any
Conformal Predictor are automatically valid, however their tightness and
therefore usefulness depends on the nonconformity measure used by each CP. In
effect a nonconformity measure evaluates how strange a given example is
compared to a set of other examples based on some traditional machine learning
algorithm. We define six novel nonconformity measures based on the k-Nearest
Neighbours Regression algorithm and develop the corresponding CPs following
both the original (transductive) and the inductive CP approaches. A comparison
of the predictive regions produced by our measures with those of the typical
regression measure suggests that a major improvement in terms of predictive
region tightness is achieved by the new measures.


title:
Value of Information Lattice: Exploiting Probabilistic Independence for
  Effective Feature Subset Acquisition

abstract:
  We address the cost-sensitive feature acquisition problem, where
misclassifying an instance is costly but the expected misclassification cost
can be reduced by acquiring the values of the missing features. Because
acquiring the features is costly as well, the objective is to acquire the right
set of features so that the sum of the feature acquisition cost and
misclassification cost is minimized. We describe the Value of Information
Lattice (VOILA), an optimal and efficient feature subset acquisition framework.
Unlike the common practice, which is to acquire features greedily, VOILA can
reason with subsets of features. VOILA efficiently searches the space of
possible feature subsets by discovering and exploiting conditional independence
properties between the features and it reuses probabilistic inference
computations to further speed up the process. Through empirical evaluation on
five medical datasets, we show that the greedy strategy is often reluctant to
acquire features, as it cannot forecast the benefit of acquiring multiple
features in combination.


title: Probabilistic Relational Planning with First Order Decision Diagrams

abstract:
  Dynamic programming algorithms have been successfully applied to
propositional stochastic planning problems by using compact representations, in
particular algebraic decision diagrams, to capture domain dynamics and value
functions. Work on symbolic dynamic programming lifted these ideas to first
order logic using several representation schemes. Recent work introduced a
first order variant of decision diagrams (FODD) and developed a value iteration
algorithm for this representation. This paper develops several improvements to
the FODD algorithm that make the approach practical. These include, new
reduction operators that decrease the size of the representation, several
speedup techniques, and techniques for value approximation. Incorporating
these, the paper presents a planning system, FODD-Planner, for solving
relational stochastic planning problems. The system is evaluated on several
domains, including problems from the recent international planning competition,
and shows competitive performance with top ranking systems. This is the first
demonstration of feasibility of this approach and it shows that abstraction
through compact representation is a promising approach to stochastic planning.


title:
From "Identical" to "Similar": Fusing Retrieved Lists Based on
  Inter-Document Similarities

abstract:
  Methods for fusing document lists that were retrieved in response to a query
often utilize the retrieval scores and/or ranks of documents in the lists. We
present a novel fusion approach that is based on using, in addition,
information induced from inter-document similarities. Specifically, our methods
let similar documents from different lists provide relevance-status support to
each other. We use a graph-based method to model relevance-status propagation
between documents. The propagation is governed by inter-document-similarities
and by retrieval scores of documents in the lists. Empirical evaluation
demonstrates the effectiveness of our methods in fusing TREC runs. The
performance of our most effective methods transcends that of effective fusion
methods that utilize only retrieval scores or ranks.


title: Redistribution Mechanisms for Assignment of Heterogeneous Objects

abstract:
  There are p heterogeneous objects to be assigned to n competing agents (n >
p) each with unit demand. It is required to design a Groves mechanism for this
assignment problem satisfying weak budget balance, individual rationality, and
minimizing the budget imbalance. This calls for designing an appropriate rebate
function. When the objects are identical, this problem has been solved which we
refer as WCO mechanism. We measure the performance of such mechanisms by the
redistribution index. We first prove an impossibility theorem which rules out
linear rebate functions with non-zero redistribution index in heterogeneous
object assignment. Motivated by this theorem, we explore two approaches to get
around this impossibility. In the first approach, we show that linear rebate
functions with non-zero redistribution index are possible when the valuations
for the objects have a certain type of relationship and we design a mechanism
with linear rebate function that is worst case optimal. In the second approach,
we show that rebate functions with non-zero efficiency are possible if
linearity is relaxed. We extend the rebate functions of the WCO mechanism to
heterogeneous objects assignment and conjecture them to be worst case optimal.


title: Scaling up Heuristic Planning with Relational Decision Trees

abstract:
  Current evaluation functions for heuristic planning are expensive to compute.
In numerous planning problems these functions provide good guidance to the
solution, so they are worth the expense. However, when evaluation functions are
misguiding or when planning problems are large enough, lots of node evaluations
must be computed, which severely limits the scalability of heuristic planners.
In this paper, we present a novel solution for reducing node evaluations in
heuristic planning based on machine learning. Particularly, we define the task
of learning search control for heuristic planning as a relational
classification task, and we use an off-the-shelf relational classification tool
to address this learning task. Our relational classification task captures the
preferred action to select in the different planning contexts of a specific
planning domain. These planning contexts are defined by the set of helpful
actions of the current state, the goals remaining to be achieved, and the
static predicates of the planning task. This paper shows two methods for
guiding the search of a heuristic planner with the learned classifiers. The
first one consists of using the resulting classifier as an action policy. The
second one consists of applying the classifier to generate lookahead states
within a Best First Search algorithm. Experiments over a variety of domains
reveal that our heuristic planner using the learned classifiers solves larger
problems than state-of-the-art planners.


title:
Exploiting Structure in Weighted Model Counting Approaches to
  Probabilistic Inference

abstract:
  Previous studies have demonstrated that encoding a Bayesian network into a
SAT formula and then performing weighted model counting using a backtracking
search algorithm can be an effective method for exact inference. In this paper,
we present techniques for improving this approach for Bayesian networks with
noisy-OR and noisy-MAX relations---two relations that are widely used in
practice as they can dramatically reduce the number of probabilities one needs
to specify. In particular, we present two SAT encodings for noisy-OR and two
encodings for noisy-MAX that exploit the structure or semantics of the
relations to improve both time and space efficiency, and we prove the
correctness of the encodings. We experimentally evaluated our techniques on
large-scale real and randomly generated Bayesian networks. On these benchmarks,
our techniques gave speedups of up to two orders of magnitude over the best
previous approaches for networks with noisy-OR/MAX relations and scaled up to
larger networks. As well, our techniques extend the weighted model counting
approach for exact inference to networks that were previously intractable for
the approach.


title: The Complexity of Integer Bound Propagation

abstract:
  Bound propagation is an important Artificial Intelligence technique used in
Constraint Programming tools to deal with numerical constraints. It is
typically embedded within a search procedure ("branch and prune") and used at
every node of the search tree to narrow down the search space, so it is
critical that it be fast. The procedure invokes constraint propagators until a
common fixpoint is reached, but the known algorithms for this have a
pseudo-polynomial worst-case time complexity: they are fast indeed when the
variables have a small numerical range, but they have the well-known problem of
being prohibitively slow when these ranges are large. An important question is
therefore whether strongly-polynomial algorithms exist that compute the common
bound consistent fixpoint of a set of constraints. This paper answers this
question. In particular we show that this fixpoint computation is in fact
NP-complete, even when restricted to binary linear constraints.


title:
Stackelberg vs. Nash in Security Games: An Extended Investigation of
  Interchangeability, Equivalence, and Uniqueness

abstract:
  There has been significant recent interest in game-theoretic approaches to
security, with much of the recent research focused on utilizing the
leader-follower Stackelberg game model. Among the major applications are the
ARMOR program deployed at LAX Airport and the IRIS program in use by the US
Federal Air Marshals (FAMS). The foundational assumption for using Stackelberg
games is that security forces (leaders), acting first, commit to a randomized
strategy; while their adversaries (followers) choose their best response after
surveillance of this randomized strategy. Yet, in many situations, a leader may
face uncertainty about the follower's surveillance capability. Previous work
fails to address how a leader should compute her strategy given such
uncertainty. We provide five contributions in the context of a general class of
security games. First, we show that the Nash equilibria in security games are
interchangeable, thus alleviating the equilibrium selection problem. Second,
under a natural restriction on security games, any Stackelberg strategy is also
a Nash equilibrium strategy; and furthermore, the solution is unique in a class
of security games of which ARMOR is a key exemplar. Third, when faced with a
follower that can attack multiple targets, many of these properties no longer
hold. Fourth, we show experimentally that in most (but not all) games where the
restriction does not hold, the Stackelberg strategy is still a Nash equilibrium
strategy, but this is no longer true when the attacker can attack multiple
targets. Finally, as a possible direction for future research, we propose an
extensive-form game model that makes the defender's uncertainty about the
attacker's ability to observe explicit.