J

IJCAI Conference 2016 Conference Paper

Achieving Proportional Representation in Conference Programs

• Ioannis Caragiannis
• Laurent Gourv
• egrave; s
• J
• eacute; r
• ocirc; me Monnot

We study the optimization problem of designing the program of a conference with parallel sessions, so that the intended participants are as happy as possible from the talks they can attend. Interestingly, this can be thought of as a two-dimensional extension of a scheme proposed by Chamberlin and Courant [1983] for achieving proportional representation in multi-winner elections. We show that different variations of the problem are computationally hard by exploiting relations of the problem with well-known hard graph problems. On the positive side, we present polynomial-time algorithms that compute conference programs that have a social utility that is provably close to the optimal one (within constant factors). Our algorithms are either combinatorial or based on linear programming and randomized rounding.

IJCAI Conference 2016 Conference Paper

Computing Pareto Optimal Committees

• Haris Aziz
• ocirc; me Lang
• J
• eacute; r
• ocirc; me Monnot

Selecting a set of alternatives based on the preferences of agents is an important problem in committee selection and beyond. Among the various criteria put forth for desirability of a committee, Pareto optimality is a minimal and important requirement. As asking agents to specify their preferences over exponentially many subsets of alternatives is practically infeasible, we assume that each agent specifies a weak order on single alternatives, from which a preference relation over subsets is derived using some preference extension. We consider four prominent extensions (responsive, leximax, best, and worst). For each of them, we consider the corresponding Pareto optimality notion, and we study the complexity of computing and verifying Pareto optimal outcomes. We also consider strategic issues: for three of the set extensions, we present linear-time, Pareto optimal and strategyproof algorithms that work even for weak preferences.

IJCAI Conference 2016 Conference Paper

Conditional and Sequential Approval Voting on Combinatorial Domains

• Nathana
• euml; l Barrot
• J
• eacute; r
• ocirc; me Lang

Several methods exist for making collective decisions on a set of variables when voters possibly have preferential dependencies. None is based on approval voting. We define a family of rules for approval-based voting on combinatorial domains, where voters cast conditional approval ballots, allowing them to approve values of a variable conditionally on the values of other variables. We study three such rules. The first two generalize simple multiwinner approval voting and minimax approval voting. The third one is an approval-based version of sequential voting on combinatorial domains. We study some properties of these rules, and compare their outcomes.

IJCAI Conference 2016 Conference Paper

Decoupled Strong Stubborn Sets

• Daniel Gnad
• Martin Wehrle
• J
• ouml; rg Hoffmann

Recent work has introduced fork-decoupled search, addressing classical planning problems where a single center component provides preconditions for several leaf components. Given a fixed center path π C, the leaf moves compliant with π C can then be scheduled independently for each leaf. Fork-decoupled search thus searches over center paths only, maintaining the compliant paths for each leaf separately. This can yield dramatic benefits. It is empirically complementary to partial order reduction via strong stubborn sets, in that each method yields its strongest reductions in different benchmarks. Here we show that the two methods can be combined, in the form of strong stubborn sets for fork-decoupled search. This can yield exponential advantages relative to both methods. Empirically, the combination reliably inherits the best of its components, and often outperforms both.

IJCAI Conference 2016 Conference Paper

How Hard Is It for a Party to Nominate an Election Winner?

• Piotr Faliszewski
• Laurent Gourv
• egrave; s
• ocirc; me Lang
• Julien Lesca
• J
• eacute; r
• ocirc; me Monnot

We consider a Plurality-voting scenario, where the candidates are split between parties, and each party nominates exactly one candidate for the final election. We study the computational complexity of deciding if there is a set of nominees such that a candidate from a given party wins in the final election. In our second problem, the goal is to decide if a candidate from a given party always wins, irrespective who is nominated. We show that these problems are computationally hard, but are polynomial-time solvable for restricted settings.

IJCAI Conference 2016 Conference Paper

On State-Dominance Criteria in Fork-Decoupled Search

• aacute; lvaro Torralba
• Daniel Gnad
• Patrick Dubbert
• J
• ouml; rg Hoffmann

Fork-decoupled search is a recent approach to classical planning that exploits fork structures, where a single center component provides preconditions for several leaf components. The decoupled states in this search consist of a center state, along with a price for every leaf state. Given this, when does one decoupled state dominate another? Such state-dominance criteria can be used to prune dominated search states. Prior work has devised only a trivial criterion. We devise several more powerful criteria, show that they preserve optimality, and establish their interrelations. We show that they can yield exponential reductions. Experiments on IPC benchmarks attest to the possible practical benefits.

IJCAI Conference 2015 Conference Paper

On the Aggregation of Argumentation Frameworks

• J
• eacute; r
• ocirc; me Delobelle
• S
• eacute; bastien Konieczny
• Srdjan Vesic

We study the problem of aggregation of Dung’s abstract argumentation frameworks. Some operators for this aggregation have been proposed, as well as some rationality properties for this process. In this work we study the existing operators and new ones that we propose in light of the proposed properties, highlighting the fact that existing operators do not satisfy a lot of these properties. The conclusions are that on one hand none of the existing operators seem fully satisfactory, but on the other hand some of the properties proposed so far seem also too demanding.

IJCAI Conference 2015 Conference Paper

Probabilistic Knowledge-Based Programs

• J
• eacute; r
• ocirc; me Lang
• Bruno Zanuttini

We introduce Probabilistic Knowledge-Based Programs (PKBPs), a new, compact representation of policies for factored partially observable Markov decision processes. PKBPs use branching conditions such as if the probability of ϕ is larger than p, and many more. While similar in spirit to valuebased policies, PKBPs leverage the factored representation for more compactness. They also cope with more general goals than standard state-based rewards, such as pure information-gathering goals. Compactness comes at the price of reactivity, since evaluating branching conditions on-line is not polynomial in general. In this sense, PKBPs are complementary to other representations. Our intended application is as a tool for experts to specify policies in a natural, compact language, then have them verified automatically. We study succinctness and the complexity of verification for PKBPs.

IJCAI Conference 2015 Conference Paper

Realizability of Three-Valued Semantics for Abstract Dialectical Frameworks

• J
• ouml; rg P
• uuml; hrer

We investigate fundamental properties of threevalued semantics for abstract dialectical frameworks (ADFs). In particular, we deal with realizability, i. e. , the question whether there exists an ADF that has a given set of interpretations as its semantics. We provide necessary and sufficient conditions that hold for a set of three-valued interpretations whenever there is an ADF realizing it under admissible, complete, grounded, or preferred semantics. Moreover, we discuss how to construct such an ADF in case of realizability. Our results lay the ground for studying the expressiveness of ADFs under three-valued semantics. As a first application we study implications of our results on the existence of certain join operators on ADFs.

IJCAI Conference 2015 Conference Paper

Simulation-Based Admissible Dominance Pruning

• aacute; lvaro Torralba
• J
• ouml; rg Hoffmann

In optimal planning as heuristic search, admissible pruning techniques are paramount. One idea is dominance pruning, identifying states “better than” other states. Prior approaches are limited to simple dominance notions, like “more STRIPS facts true” or “higher resource supply”. We apply simulation, well-known in model checking, to compute much more general dominance relations based on comparing transition behavior across states. We do so effectively by expressing state-space simulations through the composition of simulations on orthogonal projections. We show how simulation can be made more powerful by intertwining it with a notion of label dominance. Our experiments show substantial improvements across several IPC benchmark domains.

IJCAI Conference 2015 Conference Paper

Strategy-Proofness of Scoring Allocation Correspondences for Indivisible Goods

• Nhan-Tam Nguyen
• Dorothea Baumeister
• J
• ouml; rg Rothe

We study resource allocation in a model due to Brams and King [2005] and further developed by Baumeister et al. [2014]. Resource allocation deals with the distribution of resources to agents. We assume resources to be indivisible, nonshareable, and of single-unit type. Agents have ordinal preferences over single resources. Using scoring vectors, every ordinal preference induces a utility function. These utility functions are used in conjunction with utilitarian social welfare to assess the quality of allocations of resources to agents. Then allocation correspondences determine the optimal allocations that maximize utilitarian social welfare. Since agents may have an incentive to misreport their true preferences, the question of strategyproofness is important to resource allocation. We assume that a manipulator has a strictly monotonic and strictly separable linear order on the power set of the resources. We use extension principles (from social choice theory, such as the Kelly and the Gärdenfors extension) for preferences to study manipulation of allocation correspondences. We characterize strategy-proofness of the utilitarian allocation correspondence: It is Gärdenfors/Kellystrategy-proof if and only if the number of different values in the scoring vector is at most two or the number of occurrences of the greatest value in the scoring vector is larger than half the number of goods.

AAMAS Conference 2012 Conference Paper

Campaigns for Lazy Voters: Truncated Ballots

• Dorothea Baumeister
• Piotr Faliszewski
• eacute; r
• ocirc; me Lang
• J
• ouml; rg Rothe

We study elections in which voters may submit partial ballots consisting of truncated lists: each voter ranks some of her top candidates (and possibly some of her bottom candidates) and is indifferent among the remaining ones. Holding elections with such votes requires adapting classical voting rules (which expect complete rankings as input) and these adaptations create various opportunities for candidates who want to increase their chances of winning. We provide complexity results regarding planning various kinds of campaign in such settings, and we study the complexity of the possible winner problem for the case of truncated votes.

AAMAS Conference 2012 Conference Paper

Complexity and Approximability of Social Welfare Optimization in Multiagent Resource Allocation

• Nhan-Tam Nguyen
• Trung Thanh Nguyen
• Magnus Roos
• J
• ouml; rg Rothe

An important task in multiagent resource allocation, which provides mechanisms to allocate bundles of (indivisible and nonshareable) resources to agents, is to maximize social welfare. We study the computational complexity of exact social welfare optimization by the Nash product, which can be seen as a sensible compromise between the well-known notions of utilitarian and egalitarian social welfare. When utilitiy functions are represented in the bundle or the k-additive form, for k ≥ 3, we prove that the corresponding computational problems are DP-complete (where DP denotes the second level of the boolean hierarchy over NP), thus confirming two conjectures raised by Roos and Rothe [10]. We also study the approximability of social welfare optimization problems.

AAMAS Conference 2012 Conference Paper

Possible and Necessary Winners of Partial Tournaments

• Haris Aziz
• Markus Brill
• Felix Fischer
• Paul Harrenstein
• J
• eacute; r
• ocirc; me Lang
• Hans Georg Seedig

We study the problem of computing possible and necessary winners for partially specified weighted and unweighted tournaments. This problem arises naturally in elections with incompletely specified votes, partially completed sports competitions, and more generally in any scenario where the outcome of some pairwise comparisons is not yet fully known. We specifically consider a number of well-known solution concepts---including the uncovered set, Borda, ranked pairs, and maximin---and show that for most of them possible and necessary winners can be identified in polynomial time. These positive algorithmic results stand in sharp contrast to earlier results concerning possible and necessary winners given partially specified preference profiles.

AAMAS Conference 2012 Conference Paper

Strategic voting and the logic of knowledge

• Hans van Ditmarsch
• J
• eacute; r
• ocirc; me Lang
• Abdallah Saffidine

AAMAS Conference 2011 Conference Paper

( PcWNA ) problem, which asks, given an election with strict preferences over the candidates, is it possible to make a designated candidate win the election by adding a limited number of new candidates to the election? In the case of unweighted voters we show NP-completeness of PcWNA for a broad class of pure scoring rules. We will also briefly study the case of weighted voters. The second type of possible winner problem we study is Possible Winner/co-Winner under Uncertain Voting System ( PWUVS and PcWUVS ). Here, uncertainty is present not in the votes but in the election rule itself. For example, PcWUVS is the problem of whether, given a set C of candidates, a list of votes over C, a distinguished candidate c ı n C, and a class of election rules, there is at least one election rule from this class under which c wins the election. We study these two problems for a class of systems based on approval voting, the family of Copeland ^α elections, and a certain class of scoring rules. Our main result is that it is NP-complete to determine whether there is a scoring vector that makes c win the election, if we restrict the set of possible scoring vectors for an m-candidate election to those of the form (α _1, .. ., α _{m-4}, x_1, x_2, x_3, 0), with x_i = 1 for at least one i ı n {1, 2, 3}. Computational Complexity of Two Variants of the Possible Winner Problem

• Dorothea Baumeister
• Magnus Roos
• J
• ouml; rg Rothe

A possible winner of an election is a candidate that has, in some kind of incomplete-information election, the possibility to win in a complete extension of the election. The first type of problem we study is the Possible co-Winner with respect to the Addition of New Candidates

IJCAI Conference 2011 Conference Paper

A General Elicitation-Free Protocol for Allocating Indivisible Goods

• Sylvain Bouveret
• J
• eacute; r
• ocirc; me Lang

We consider the following sequential allocation process. A benevolent central authority has to allocate a set of indivisible goods to a set of agents whose preferences it is totally ignorant of. We consider the process of allocating objects one after the other by designating an agent and asking her to pick one of the objects among those that remain. The problem consists in choosing the "best" sequence of agents, according to some optimality criterion. We assume that agents have additive preferences over objects. The choice of an optimality criterion depends on three parameters: how utilities of objects are related to their ranking in an agent's preference relation; how the preferences of different agents are correlated; and how social welfare is defined from the agents' utilities. We address the computation of a sequence maximizing expected social welfare under several assumptions. We also address strategical issues.

IJCAI Conference 2011 Conference Paper

Choosing Collectively Optimal Sets of Alternatives Based on the Condorcet Criterion

• Edith Elkind
• J
• eacute; r
• ocirc; me Lang
• Abdallah Saffidine

In elections, an alternative is said to be a Condorcet winner if it is preferred to any other alternative by a majority of voters. While this is a very attractive solution concept, many elections do not have a Condorcet winner. In this paper, we propose a setvalued relaxation of this concept, which we call a Condorcet winning set: such sets consist of alternatives that collectively dominate any other alternative. We also consider a more general version of this concept, where instead of domination by a majority of voters we require domination by a given fraction theta of voters; we refer to this concept as theta-winning set. We explore social choice-theoretic and algorithmic aspects of these solution concepts, both theoretically and empirically.

IJCAI Conference 2011 Conference Paper

Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstraction in Optimal Planning

• Raz Nissim
• J
• ouml; rg Hoffmann
• Malte Helmert

A* with admissible heuristics is a very successful approach to optimal planning. But how to derive such heuristics automatically? Merge-and-shrink abstraction (M&S) is a general approach to heuristic design whose key advantage is its capability to make very fine-grained choices in defining abstractions. However, little is known about how to actually make these choices. We address this via the well-known notion of bisimulation. When aggregating only bisimilar states, M&S yields a perfect heuristic. Alas, bisimulations are exponentially large even in trivial domains. We show how to apply label reduction - not distinguishing between certain groups of operators - without incurring any information loss, while potentially reducing bisimulation size exponentially. In several benchmark domains, the resulting algorithm computes perfect heuristics in polynomial time. Empirically, we show that approximating variants of this algorithm improve the state of the art in M&S heuristics. In particular, a simple hybrid of two such variants is competitive with the leading heuristic LM-cut.

AAMAS Conference 2011 Conference Paper

Designing Incentives for Boolean Games

• Ulle Endriss
• Sarit Kraus
• J
• eacute; r
• ocirc; me Lang
• Michael Wooldridge

Boolean games are a natural, compact, and expressive class of logic-based games, in which each player exercises unique control over some set of Boolean variables, and has some logical goal formula that it desires to be achieved. A player's strategy set is the set of all possible valuations that may be made to its variables. A player's goal formula may contain variables controlled by other agents, and in this case, it must reason strategically about how best to assign values to its variables. In the present paper, we consider the possibility of overlaying Boolean games with taxation schemes. A taxation scheme imposes a cost on every possible assignment an agent can make. By designing a taxation scheme appropriately, it is possible to perturb the preferences of the agents within a society, so that agents are rationally incentivised to choose some socially desirable equilibrium that would not otherwise be chosen, or incentivised to rule out some socially undesirable equilibria. After formally presenting the model, we explore some issues surrounding it (e. g. , the complexity of finding a taxation scheme that implements some socially desirable outcome), and then discuss possible desirable properties of taxation schemes.

IJCAI Conference 2011 Conference Paper

Evaluation of Group Profiling Strategies

• Christophe Senot
• Dimitre Kostadinov
• Makram Bouzid
• J
• eacute; r
• ocirc; me Picault
• Armen Aghasaryan

Most of the existing personalization systems such as content recommenders or targeted ads focus on individual users and ignore the social situation in which the services are consumed. However, many human activities are social and involve several in-dividuals whose tastes and expectations must be taken into account by the system. When a group profile is not available, different profile aggrega-tion strategies can be applied to recommend ade-quate items to a group of users based on their indi-vidual profiles. We consider an approach intended to determine the factors that influence the choice of an aggregation strategy. We present evaluations made on a large-scale dataset of TV viewings, where real group interests are compared to the pre-dictions obtained by combining individual user profiles according to different strategies.

IJCAI Conference 2011 Conference Paper

Flexible, High Performance Convolutional Neural Networks for Image Classification

• Dan C. Ciresan
• Ueli Meier
• Jonathan Masci
• Luca Maria Gambardella
• J
• uuml; rgen Schmidhuber

We present a fast, fully parameterizable GPU implementation of Convolutional Neural Network variants. Our feature extractors are neither carefully designed nor pre-wired, but rather learned in a supervised way. Our deep hierarchical architectures achieve the best published results on benchmarks for object classification (NORB, CIFAR10) and handwritten digit recognition (MNIST), with error rates of 2. 53%, 19. 51%, 0. 35%, respectively. Deep nets trained by simple back-propagation perform better than more shallow ones. Learning is surprisingly rapid. NORB is completely trained within five epochs. Test error rates on MNIST drop to 2. 42%, 0. 97% and 0. 48% after 1, 3 and 17 epochs, respectively.

IJCAI Conference 2011 Conference Paper

Hypercubewise Preference Aggregation in Multi-Issue Domains

• Vincent Conitzer
• J
• eacute; r
• ocirc; me Lang
• Lirong Xia

We consider a framework for preference aggregation on multiple binary issues, where agents' preferences are represented by (possibly cyclic) CP-nets. We focus on the majority aggregation of the individual CP-nets, which is the CP-net where the direction of each edge of the hypercube is decided according to the majority rule. First we focus on hypercube Condorcet winners (HCWs); in particular, we show that, assuming a uniform distribution for the CP-nets, the probability that there exists at least one HCW is at least 1-1/e, and the expected number of HCWs is 1. Our experimental results confirm these results. We also show experimental results under the Impartial Culture assumption. We then generalize a few tournament solutions to select winners from (weighted) majoritarian CP-nets, namely Copeland, maximin, and Kemeny. For each of these, we address some social choice theoretic and computational issues.

IJCAI Conference 2011 Conference Paper

Incentive Engineering for Boolean Games

• Ulle Endriss
• Sarit Kraus
• J
• eacute; r
• ocirc; me Lang
• Michael Wooldridge

We investigate the problem of influencing the preferences of players within a Boolean game so that, if all players act rationally, certain desirable outcomes will result. The way in which we influence preferences is by overlaying games with taxation schemes. In a Boolean game, each player has unique control of a set of Boolean variables, and the choices available to the player correspond to the possible assignments that may be made to these variables. Each player also has a goal, represented by a Boolean formula, that they desire to see satisfied. Whether or not a player's goal is satisfied will depend both on their own choices and on the choices of others, which gives Boolean games their strategic charac- ter. We extend this basic framework by introducing an external principal who is able to levy a taxation scheme on the game, which imposes a cost on every possible action that a player can choose. By designing a taxation scheme appropriately, it is possible to perturb the preferences of the players, so that they are incentivised to choose some equilibrium that would not otherwise be chosen. After motivating and formally presenting our model, we explore some issues surrounding it, including the complexity of finding a taxation scheme that implements some socially desirable outcome, and then discuss desirable properties of taxation schemes.

IJCAI Conference 2011 Conference Paper

Incremental Slow Feature Analysis

• Varun Raj Kompella
• Matthew Luciw
• J
• uuml; rgen Schmidhuber

The Slow Feature Analysis (SFA) unsupervised learning framework extracts features representing the underlying causes of the changes within a temporally coherent high-dimensional raw sensory input signal. We develop the first online version of SFA, via a combination of incremental Principal Components Analysis and Minor Components Analysis. Unlike standard batch-based SFA, online SFA adapts along with non-stationary environments, which makes it a generally useful unsupervised preprocessor for autonomous learning agents. We compare online SFA to batch SFA in several experiments and show that it indeed learns without a teacher to encode the input stream by informative slow features representing meaningful abstract environmental properties. We extend online SFA to deep networks in hierarchical fashion, and use them to successfully extract abstract object position information from high-dimensional video.

AAMAS Conference 2011 Conference Paper

Possible Winners When New Alternatives Join: New Results Coming Up!

• Lirong Xia
• ocirc; me Lang
• J
• eacute; r
• ocirc; me Monnot

In a voting system, sometimes multiple new alternatives will join the election after the voters' preferences over the initial alternatives have been revealed. Computing whether a given alternative can be a co-winner when multiple new alternatives join the election is called the possible co-winner with new alternatives (PcWNA) problem and was introduced by (Chevaleyre et al. , 2010). In this paper, we show that the PcWNA problems are NP-complete for the Bucklin, Copeland _0, and maximin (a. k. a. Simpson) rule, even when the number of new alternatives is no more than a constant. We also show that the PcWNA problem can be solved in polynomial time for plurality with runoff. For the approval rule, we examine three different ways to extend a linear order with new alternatives, and characterize the computational complexity of the PcWNA problem for each of them.

AAMAS Conference 2011 Conference Paper

The Complexity of Voter Partition in Bucklin and Fallback Voting: Solving Three Open Problems

• G
• aacute; bor Erd
• eacute; lyi
• Lena Piras
• J
• ouml; rg Rothe

Electoral control models ways of changing the outcome of an election via such actions as adding/deleting/partitioning either candidates or voters. These actions modify an election's participation structure and aim at either making a favorite candidate win ("constructive control") or prevent a despised candidate from winning ("destructive control"). To protect elections from such control attempts, computational complexity has been used to show that electoral control, though not impossible, is computationally prohibitive. Recently, Erdé lyi and Rothe proved that Brams and Sanver's fallback voting, a hybrid voting system that combines Bucklin with approval voting, is resistant to each of the standard types of control except five types of voter control. They proved that fallback voting is vulnerable to two of those control types, leaving the other three cases open. We solve these three open problems, thus showing that fallback voting is resistant to all standard types of control by partition of voters-which is a particularly important and well-motivated control type, as it models "two-district gerrymandering. " Hence, fallback voting is not only fully resistant to candidate control but also fully resistant to constructive control, and it displays the broadest resistance to control currently known to hold among natural voting systems with a polynomial-time winner problem. We also show that Bucklin voting behaves almost as good in terms of control resistance. Each resistance for Bucklin voting strengthens the corresponding control resistance for fallback voting.

AAMAS Conference 2011 Conference Paper

The Face of Emotions: A Logical Formalization of Expressive Speech Acts

• Nadine Guiraud
• Dominique Longin
• Emiliano Lorini
• Sylvie Pesty
• J
• eacute; r
• eacute; my Rivi
• egrave; re

In this paper, we merge speech act theory, emotion theory, and logic. We propose a modal logic that integrates the concepts of belief, goal, ideal and responsibility and that allows to describe what a given agent expresses in the context of a conversation with another agent. We use the logic in order to provide a systematic analysis of expressive speech acts, that is, speech acts that are aimed at expressing a given emotion (e. g. to apologize, to thank, to reproach, etc. ).

AAMAS Conference 2008 Conference Paper

Modelling Coalitions: ATL + Argumentation

• Nils Bulling
• Carlos I. Chesnevar
• J
• uuml; rgen Dix

In the last few years, argumentation frameworks have been successfully applied to multi agent systems. Recently, argumentation has been used to provide a framework for reasoning about coalition formation. At the same time alternatingtime temporal logic has been used to reason about the behavior and abilities of coalitions of agents. However, ATL operators account only for the existence of successful strategies of coalitions. They do not consider whether coalitions can be actually formed. This paper is an attempt to combine both frameworks and to develop a logic through which we can reason at the same time (1) about abilities of coalitions of agents and (2) about the formation of coalitions. We provide a formal extension of ATL, ATLc, in which the actual computation of the coalition is modelled in terms of argumentation semantics. We show that ATLc ’s proof theory can be understood as a natural extension of the model checking procedure used in ATL.

IJCAI Conference 2007 Conference Paper

• J
• eacute; r
• ocirc; me Lang

Although many papers about belief update have been written, its precise scope still remains unclear. In this paper we aim at identifying this scope, and we show that belief update is a specific case of feedback-free action progression. This strong connection with the field of reasoning about action leads us to reconsider belief update and investigate new issues, especially reverse update, which is to regression what update is to progression.

IJCAI Conference 2007 Conference Paper

• Marco Benedetti
• Arnaud Lallouet
• J
• eacute; r
• eacute; mie Vautard

The QCSP+ language we introduce extends the framework of Quantified Constraint Satisfaction Problems (QCSPs) by enabling us to neatly express restricted quantifications via a chain of nested CSPs to be interpreted as alternately conjuncted and disjuncted. Restricted quantifiers turn out to be a convenient solution to the crippling modeling issues we encounter in QCSP and - surprisingly - they help to reuse propagation technology and to prune the search space. Our QCSP+ solver - which also handles arithmetic and global constraints - exhibits state-of-the-art performances.

IJCAI Conference 2007 Conference Paper

• J
• eacute; r
• ocirc; me Euzenat

In order to evaluate ontology matching algorithms it is necessary to confront them with test ontologies and to compare the results with some reference. The most prominent comparison criteria are precision and recall originating from information retrieval. Precision and recall are thought of as some degree of correction and completeness of results. However, when the objects to compare are semantically defined, like ontologies and alignments, it can happen that a fully correct alignment has low precision. This is due to the restricted set-theoretic foundation of these measures. Drawing on previous syntactic generalizations of precision and recall, semantically justified measures that satisfy maximal precision and maximal recall for correct and complete alignments is proposed. These new measures are compatible with classical precision and recall and can be computed.

IJCAI Conference 2007 Conference Paper

• J
• uuml; rgen Kuster
• Jannach Dietmar
• Gerhard Friedrich

In the context of operative disruption management, decision support systems have to evaluate the typically manifold options of responding to disturbances: The temporal shift of activities and the allocation of alternative resources can be assessed by the application of generic scheduling frameworks such as the Resource-Constrained Project Scheduling Problem (RCPSP). However, switches from one process variant to another one are usually not supported by the corresponding models, even though they represent a common way of repairing broken schedules in many practical domains. In this paper, we thus show how the RCPSP can be extended by the concept of alternative activities, making it possible to model and search within alternative process execution paths. Beside a formal description of the conceptual extension, we show how such generalized rescheduling problems can be solved by a novel genetic algorithm and summarize the promising results of a detailed evaluation.

IJCAI Conference 2007 Conference Paper

• J
• ouml; rg Hoffmann
• Carla Gomes
• Bart Selman
• Henry Kautz

Translation to Boolean satisfiability is an important approach for solving state-space reachability problems that arise in planning and verification. Many important problems, however, involve numeric variables; for example, C programs or planning with resources. Focussing on planning, we propose a method for translating such problems into propositional SAT, based on an approximation of reachable variable domains. We compare to a more direct translation into "SAT modulo theory" (SMT), that is, SAT extended with numeric variables and arithmetic constraints. Though translation to SAT generates much larger formulas, we show that it typically outperforms translation to SMT almost up to the point where the formulas don't fit into memory any longer. We also show that, even though our planner is optimal, it tends to outperform state-of-the-art sub-optimal heuristic planners in domains with tightly constrained resources. Finally we present encouraging initial results on applying the approach to model checking.

IJCAI Conference 2007 Conference Paper

• Matteo Gagliolo
• J
• uuml; rgen Schmidhuber

Restart strategies are commonly used for minimizing the computational cost of randomized algorithms, but require prior knowledge of the run-time distribution in order to be effective. We propose a portfolio of two strategies, one fixed, with a provable bound on performance, the other based on a model of run-time distribution, updated as the two strategies are run on a sequence of problems. Computational resources are allocated probabilistically to the two strategies, based on their performances, using a well-known K-armed bandit problem solver. We present bounds on the performance of the resulting technique, and experiments with a satisfiability problem solver, showing rapid convergence to a near-optimal execution time.

IJCAI Conference 2007 Conference Paper

• Santiago Fern
• aacute; ndez
• Alex Graves
• J
• uuml; rgen Schmidhuber

Modelling data in structured domains requires establishing the relations among patterns at multiple scales. When these patterns arise from sequential data, the multiscale structure also contains a dynamic component that must be modelled, particularly, as is often the case, if the data is unsegmented. Probabilistic graphical models are the predominant framework for labelling unsegmented sequential data in structured domains. Their use requires a certain degree of a priori knowledge about the relations among patterns and about the patterns themselves. This paper presents a hierarchical system, based on the connectionist temporal classification algorithm, for labelling unsegmented sequential data at multiple scales with recurrent neural networks only. Experiments on the recognition of sequences of spoken digits show that the system outperforms hidden Markov models, while making fewer assumptions about the domain.

IJCAI Conference 2007 Conference Paper

• James P. Delgrande
• J
• eacute; r
• ocirc; me Lang
• Torsten Schaub

A general framework for minimisation-based belief change is presented. A problem instance is made up of an undirected graph, where a formula is associated with each vertex. For example, vertices may represent spatial locations, points in time, or some other notion of locality. Information is shared between vertices via a process of minimisation over the graph. We give equivalent semantic and syntactic characterisations of this minimisation. We also show that this approach is general enough to capture existing minimisation-based approaches to belief merging, belief revision, and (temporal) extrapolation operators. While we focus on a set-theoretic notion of minimisation, we also consider other approaches, such as cardinality-based and priority-based minimisation.

IJCAI Conference 2007 Conference Paper

• J
• eacute; r
• ocirc; me Lang
• Maria Silvia Pini
• Francesca Rossi
• K. Brent Venable
• Toby Walsh

Preferences can be aggregated using voting rules. We consider here the family of rules which perform a sequence of pairwise majority comparisons between two candidates. The winner thus depends on the chosen sequence of comparisons, which can be represented by a binary tree. We address the difficulty of computing candidates that win for some trees, and then introduce and study the notion of fair winner, i. e. candidates who win in a balanced tree. We then consider the situation where we lack complete informations about preferences, and determine the computational complexity of computing winners in this case.

IJCAI Conference 2007 Conference Paper

• Edith Hemaspaandra
• Lane A. Hemaspaandra
• J
• ouml; rg Rothe

Electoral control refers to attempts by an election's organizer ("the chair") to influence the outcome by adding/deleting/partitioning voters or candidates. The groundbreaking work of Bartholdi, Tovey, and Trick on (constructive) control proposes computational complexity as a means of resisting control attempts: Look for election systems where the chair's task in seeking control is itself computationally infeasible. We introduce and study a method of combining two or more candidate-anonymous election schemes in such a way that the combined scheme possesses all the resistances to control (i. e. , all the NP-hardnesses of control) possessed by any of its constituents: It combines their strengths. From this and new resistance constructions, we prove for the first time that there exists an election scheme that is resistant to all twenty standard types of electoral control.

IJCAI Conference 2007 Conference Paper

• J
• eacute; r
• ocirc; me Lang

In many real-world collective decision problems, the set of alternatives is a Cartesian product of finite value domains for each of a given set of variables. The prohibitive size of such domains makes it practically impossible to represent preference relations explicitly. Now, AI has been developing languages for representing preferences on such domains in a succinct way, exploiting structural properties such as conditional preferential independence. Here we reconsider voting and aggregation rules in the case where voters' preferences have a common preferential independence structure, and address the decompossition a voting rule or an aggregation function following a linear order over variables.

AAMAS Conference 2005 Conference Paper

A Simulator for Multi-Agent Partnership Formation Based on Dependence Graphs

• J
• uacute; lio Monteiro
• Jaime Sichman

AAMAS Conference 2005 Conference Paper

Allocation Of Indivisible Goods: A General Model And Some Complexity Results

• Sylvain Bouveret
• H
• eacute; l
• egrave; ne Fargier
• J
• eacute; r
• ocirc; me Lang
• Michel Lema

IJCAI Conference 2005 Conference Paper

Approximating Pseudo-Boolean Functions on Non-Uniform Domains

• R. F. Lax
• Guoli Ding
• Peter P. Chen
• J

In Machine Learning (ML) and Evolutionary Computation (EC), it is often beneficial to approximate a complicated function by a simpler one, such as a linear or quadratic function, for computational efficiency or feasibility reasons (cf. [Jin, 2005]). A complicated function (the target function in ML or the fitness function in EC) may require an exponential amount of computation to learn/evaluate, and thus approximations by simpler functions are needed. We consider the problem of approximating pseudo-Boolean functions by simpler (e. g. , linear) functions when the instance space is associated with a probability distribution. We consider {0, 1}n as a sample space with a (possibly nonuniform) probability measure on it, thus making pseudo-Boolean functions into random variables. This is also in the spirit of the PAC learning framework of Valiant [Valiant, 1984] where the instance space has a probability distribution on it. The best approximation to a target function f is then defined as the function g (from all possible approximating functions of the simpler form) that minimizes the expected distance to f. In an example, we use methods from linear algebra to find, in this more general setting, the best approximation to a given pseudo-Boolean function by a linear function.

AAMAS Conference 2005 Conference Paper

Negotiating over Small Bundles of Resources

• Yann Chevaleyre
• Ulle Endriss
• J
• eacute; r
• ocirc; me Lang
• Nicolas Maudet

AAMAS Conference 2003 Conference Paper

Elicitation of User Preferences for Multi-attribute Negotiation

• Yutao Guo
• J
• ouml; rg P. M
• uuml; ller

AAMAS Conference 2003 Conference Paper

Securing FIPA Agent Conversations

• Nicolas Lhuillier
• J
• eacute; r
• ocirc; me Picault

IJCAI Conference 1969 Conference Paper

The Stanford Hand-Eye Project.

• J. A. Feldman
• G. M. Feldman
• G. Falk
• G. Grape
• J. PearlmanI. Sobel
• J
• M. Tenenbaum