Answer set programming (ASP) is a declarative programming paradigm based on logic programs under stable model semantics, respectively its generalization to answer set semantics. Besides the availability of rather efficient answer set solvers, one of the major reasons for the success of ASP in recent years was the shift from a theorem proving to a constraint programming view: problems are represented such that stable models, respectively answer sets, rather than theorems correspond to solutions.
The representation of both contexts and preferences has received considerable attention in Artificial Intelligence over the last years. In the talk I will present some of the existing preference handling methods for ASP and also a more recent attempt to integrate context based reasoning into ASP. I will show that by adding adequate optimization and context constructs to logic programming one obtains interesting solutions to problems in belief merging, consistency handling, game theory and social choice.

Belief merging is the process of defining a belief base representing the beliefs of a group of agents from the bases encoding the beliefs of each agent.

We focus on the propositional case, i.e. when all the available information are the bases, that are sets of propositional formulae. This means, among other things, that all the beliefs of an agent have the same importance, and that all the agents have the same importance/reliability.
We first consider the logical properties that one can expect from such processes. Then we explore the two main ways that have been proposed to address this problem: model-based operators that compute the most credible worlds, given the set of bases; and formula-based operators that select some formulae in the union of all the bases.

We investigate the connections with related areas such as belief revision, social choice theory and judgment aggregation. Finally we mention some new developments on propositional base merging.

Jérôme Lang (IRIT, France)

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. Examples of such problems are multi-issue referenda, fair allocation of indivisible goods etc. 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 I reconsider voting and aggregation rules in the case where voters' preferences have a common preferential independence structure, and I address the decompossition a voting rule or an aggregation function following a linear order over variables. The talk will be half way between a survey (on compact preference representation for combinatorial domains) and an exposition of some recent work.

Much recent research has addressed the problem of judgment aggregation: What are the possible aggregation rules for mapping a profile of individual sets of judgments on some propositions to a single collectiv set of judgments on these propositions?

Drawing on insights gained from the study of judgment aggregation, I here introduce the related problem of judgment transformation: What are the possible transformation rules for mapping a profile of individual sets of judgments on some propositions to another, possibly revised such profile? The judgment transformation problem arises, in particular, in group deliberation, where several individuals communicate about their judgments and possibly revise them in this process, which may or may not lead to consensus.

To sketch an axiomatic approach to the problem, I state a baseline impossibility result, showing that, when the propositions under consideration are suitably interconnected, any judgment transformation rule satisfying a propositionwise independence condition and some other, mild conditions must be maximally conservative: it must be the identity rule, under which nobody ever changes his or her judgment on anything.

The result implies that successful group deliberation requires some kind of holism: individuals cannot generally revise their judgments on a given proposition based on judgments on that proposition alone; their revision must take judgments on other propositions into account too. I give examples of feasible judgment transformation rules and discuss their significance for group deliberation.

We consider multi-agent settings where preferences which can be partially ordered and need to be aggregated. In this context, we study properties such as fairness and manipulability, extending well-known results of voting theory.

We also consider setting where agents may hide some of their preferences, for example for privacy reasons or because preference elicitation is not yet finished. In this context, we study the problem of computing possible and necessary winners, those outcomes which can be or always are the most preferred among the agents. Possible and necessary winners are useful in many scenarios including preference elicitation. We show that computing the sets of possible and necessary winners is in general a difficult problem, and we identify sufficient conditions on the aggregation function that allow us to compute them in polynomial time.

Finally, we consider the aggregation of preferences via sequential majority voting. Here uncertainty can arise either from the choice of the voting scheme or from hidden preferences. We show that computing possible and necessary winners for this rule is easy. However, if we are interested only in balanced voting schemes, where the number of competitions for each outcome is as balanced as possible, then winner determination is difficult.

This paper presents a framework that sticks together preference aggregation and judgement aggregation. When we aggregate in this new dual framework, we simultaneously aggregate judgements and preferences. The glue between the two original frameworks is a condition called "preference compliance of judgements"; it states that the votes of an individual (over logically interconnected options in the judgement aggregation framework) should be in accordance with the preferences this individual holds over these options.Now, given a profile of such dual judgements [a] which is preference compliant for all individuals and [b] which is not susceptible to paradoxes from either judgement aggregation or preference aggregation, then still the aggregated dual judgement can violate the condition of preference compliance. The paper presents a preliminary investigation of this problem, together with other conceptual and practical difficulties that arise in this context.

This paper is devoted to the analysis of all constitutions equipped with electoral systems involving two step procedures. First, one candidate is elected in every jurisdiction by the electors in that jurisdiction, according to some aggregation procedure. Second, another aggregation procedure collects the names of the jurisdictional winners in order to designate the final winner. It appears that whenever individuals are allowed to change jurisdiction when casting their ballot, they are able to manipulate the result of the election except in very few cases. When imposing a paretian condition on every jurisdiction's voting rule, it is shown that, in the case of any finite number of candidates, any two steps voting rule that is not manipulable by movement of the electors necessarily gives to every voter the power of overruling the unanimity on its own. A characterization of the set of these rules is next provided in the case of two candidates.

Marcello D'Agostino and Valentino Dardanoni

The problem of measuring the distance between real-valued vectors arises in several areas of the social and natural sciences, as well as computer science and engineering. In particular, variants of the familiar Euclidean distance play a prominent role in many important application contexts in economics, statistics, political science and decision theory. But what's so special about Euclidean distance? How can we judge the appropriateness of adopting this conventional distance measure in some specific application context? In what contexts are we forced to use (some variant of) it as the appropriate distance measure?

In this paper we provide a characterization of a class of distance measures monotonically related to the Euclidean distance in terms of some general properties of distance functions between real-valued vectors, and discuss how naturally these properties fit some important application contexts. In particular, we show that Euclidean distance is the only additively separable distance measure between two real-valued vectors that is always sensitive to “swaps”, i.e. exchanges of values between two elements of one of the two vectors, in a way wich is monotonically related to the distance between the exchanged values. We stress the importance of this distinctive property in many areas and propose our characterization as a test for deciding whether Euclidean distance (or some variant of it) should be used in your favourite application context.

A General Approach to Aggregation Problems

Social choice theory gained momentum with Arrow's impossibility theorem and, more recently, by the interest in judgement aggregation and resulting impossibility theorems that mirror Arrow's discovery. We discuss a general approach to aggregation problems based on lattice theory. Agents choose elements of a lattice, and an aggregation procedure yields a social outcome based on these choices. The motivation for our approach is twofold. First, the settings studied traditionally in social choice theory can be thought of as implicational systems, and lattice theory provides a nice abstraction of such systems. Second, our framework provides a starting point to analyse issues of computability and of partial or incomplete information. Our aim in this paper is to systematically investigate how properties of the lattice induce constraints on aggregation procedures that lead up to impossibility results. Traditionally studied settings correspond to atomistic lattices in our framework. We allow for more general lattices and this raises some subtle issues. We will discuss how our framework fits in with the traditional approaches to social choice theory, in particular with respect to some of the well known axioms.

In this paper we tackle the question of how to merge the intuitions of a collection of experts about inference into one logic. It is often the case in the history of logic design that the agenda upon which a logic is built is a set of conflicting intuitions on the (un)desirability of the derivability of some formulae, and / or specific semantic properties. We argue that this problem can be understood as a bargaining problem where the players are trying to find a system of inference acceptable with respect to their distributed intuitions. Our point is to show how the recent combination of results from social choice and belief merging theories provides an adequate conceptual framework to capture the rational process underlying logical modelling in controversial contexts.

The Possibility of Judgment Aggregation under Subjunctive Implications

The new field of judgment aggregation aims to find group judgments on logically interconnected propositions even when group members disagree. Recent impossibility results have established limitations on the possibility to vote independently on the propositions, hence notably on the possibility to use a proposition-wise majority rule or, more generally, a proposition-wise quota rule (with arbitrary acceptance thresholds for the propositions). I show that, fortunately, the impossibilities fail to apply to a wide class of realistic decision problems once connection rules (like "if a then b") are adequately modelled, namely as subjunctive rather than material implications. For these decision problems, I characterise all quota rules with consistent outcomes, and I suggest ways to choose the acceptance thresholds.

Geodesic Revision

The class of distance based revision operators is useful for both theory and applications, as metrics are ubiquitous from mathematics to social studies. However, the class of distance based operators fails to distinguish between different metrics. The purpose of this talk is to introduce a class of distance based revision operators based on graphs that avoids the above mentioned shortcoming, that is, its operators bijectively correspond to metrics. Distance is generated by distinguishability therefore our framework is appropriate in contexts where distance is erroneous and subjective and, in particular, where human judgment is involved.

Ceteris paribus preference logic

We present a modal logic for the formalization of preferences initiated by von Wright in The logic of preference (1963). Our goal is to provide a semantics that captures von Wright's guiding principles in his logic, namely 1) the global character of preferences, 2) preference as a binary relation, and 3) ceteris paribus. Our starting language, which we call the basic preference language, is a multi-modal language containing three unary modalities, one of them being the existential modality. We show how it reduces binary preference relations to unary modal statements, making an essential use of the existential modality. We also show how we can embed in it the minimal conditional logic of Burgess and Veltman, and thus a good deal of dynamic doxastic logic for belief revision. It further allows for a natural relativization of the modalities so as to capture the strict reading of ceteris paribus. Here, we base ourselves on an idea of Doyle and Wellman to divide a space of possibilities into equivalence classes and ignore comparison links that go across these classes. We apply this idea to a specific equivalence relation: truth-valuation. The resulting logic is infinitary in character but still enjoys a finite axiomatization. We show that it is bisimulation invariant and situate it between basic modal logic and infinitary modal logic - an intermediate situation also occupied by propositional dynamic logic. We finally show that ceteris paribus logic is not embeddable in the latter.

Parallel Interpolation, Splitting, and a Criterion of Relevance for Belief Change

The splitting theorem says that any set of formulae has a finest representation as a family of letter-disjoint sets. Parikh formulated this for classical propositional logic, proved it in the finite case, used it to formulate a criterion for relevance in belief change, and showed that AGM partial meet revision can fail the criterion. We make three further contributions. We begin by establishing a new version of the well-known interpolation theorem, which we call parallel interpolation, use it to prove the splitting theorem in the infinite case, and show how AGM belief change operations may be modified so as to ensure satisfaction of Parikh's relevance criterion.

A Model of Minimal Probabilistic Belief Revision

In the literature there are at least two models for probabilistic belief revision: Bayesian updating and imaging (Lewis (1973, 1976), Gärdenfors (1988)). In this paper we focus on imaging rules that can be described by the following procedure: (1) Identify every state with some real valued vector of characteristics, and accordingly identify every probabilistic belief with an expected vector of characteristics; (2) For every initial belief and every piece of information, choose the revised belief which is compatible with this information and for which the expected vector of characteristics has minimal Euclidean distance to the expected vector of characteristics of the initial belief. This class of rules thus satisfies an intuitive notion of minimal belief revision. The main result in this paper is to provide an axiomatic characterization of this class of imaging rules.

Strategy-Proof Fuzzy Aggregation Preferences

We investigate the structure of fuzzy aggregation rules which, for every permissible profile of fuzzy individual preferences, specify a fuzzy social preference. We show that all fuzzy aggregation rules which are strategy-proof and satisfy a minimal range condition are dictatorial. In other words, there is an individual whose fuzzy preferences determine the entire fuzzy social ranking at every profile in the domain of the aggregation rule. To prove this theorem, we show that all fuzzy aggregation rules which are strategy-proof and satisfy the minimal range condition must also satisfy counterparts of independence of irrelevant alternatives and the Pareto criterion. There has been hardly any treatment of the manipulability problem in the literature on social choice with fuzzy preferences.

Merging Judgments and the Problem of Truth-Tracking

The problem of the aggregation of consistent individual judgments on logically interconnected propositions into a collective judgment on the same propositions has recently drawn much attention. The difficulty lies in the fact that a seemingly reasonable aggregation procedure, such as propositionwise majority voting, cannot ensure an equally consistent collective outcome. The literature on judgment aggregation refers to such dilemmas as the discursive paradox. So far, three procedures have been proposed to overcome the paradox: the premise-based and conclusion-based procedures on the one hand, and the merging approach on the other hand. In this paper we assume that the decision which the group is trying to reach is factually right or wrong. Hence, the question is how good the merging approach is in tracking the truth, and how it compares with the premise-based and conclusion-based procedures.

Belief Merging and Revision under Social Influence: An Explanation for Volatility Clustering Puzzle

A share price in a stock market can be thought of as arising out of an aggregation procedure. The price of a stock aggregates many individual beliefs into a collective one, the collective will of the market, so to speak. How does this aggregation come about? And is this aggregation fair in the sense that it correctly reflects the value? Furthermore, in the context of a stock market, it becomes immediately clear that belief merging cannot be separated from belief revision since investors in the market have a direct stake in what others think and clearly find it optimal to revise their beliefs in the light of the information about what others believe. We show that if investors are revising their beliefs not only after receiving new exogenous information but also after their social interactions with other investors and these revised beliefs are getting merged to generate the stock price under the accepted principles of finance (no arbitrage) then the resulting price dynamics explain a long standing puzzle in finance, the volatility clustering puzzle.

Revising Non-Monotonic Rule-Based Belief Databases

The update of a belief database with disjunctive knowledge which is contradictory with the beliefs of an agent poses some problems when we want to perform belief-revision with minimal changes.We define a representation of beliefs based on rules. Clauses have already been used to represent beliefs. We combine them with defaults, which allows a simple treatment of disjunctive beliefs. The behaviour of the system is analysed in view of the Katsuno-Mendelzon postulates.

Rankings from Merging

We introduce an extended merging paradigm based on so-called rankers. These are functions mapping multi-source evidence and background knowledge about its origins to quasi-probabilistic epistemic valuations, namely kp-measures. To identify the more reasonable instances, we propose a list of rationality postulates. We pay special attention to the constructive kp-rankers, which are inspired by Spohn's revision paradigm, and we exemplify them with the well-justified ranker RJ.

Judgment Aggregation by Merging Knowledge: An Objective Bayesian Account

In this paper I argue that judgements are best aggregated by merging the evidence and knowledge on which the judgements are based rather than by directly merging the judgements themselves. In fact, the theories of belief revision and merger are in any case better suited to the revision and merger of knowledge than to the revision and merger of beliefs or judgements, so the following strategy becomes plausible. First, merge the knowledge bases of the various agents using some theory of belief merger. Second, determine which degrees of belief one should adopt on the basis of this merged knowledge base, by applying objective Bayesian theory. Third, determine which judgements are appropriate given these degrees of belief by applying a decision-theoretic account of rational judgement formation.