The problem of merging several ontologies has important applications in the Semantic Web, medical ontology engineering and other domains where information from several distinct sources needs to be integrated in a coherent manner.We propose to view ontology merging as a problem of social choice, i.e. as a problem of aggregating the input of a set of individuals into an adequate collective decision. That is, we propose to view ontology merging as ontology aggregation. As a first step in this direction, we (...) formulate several desirable properties for ontology aggregators, we identify the incompatibility of some of these properties, and we define and analyse several simple aggregation procedures. Our approach is closely related to work in judgment aggregation, but with the crucial difference that we adopt an open world assumption, by distinguishing between facts not included in an agent’s ontology and facts explicitly negated in an agent’s ontology. (shrink)

We analyse the computational complexity of three problems in judgment aggregation: (1) computing a collective judgment from a profile of individual judgments (the winner determination problem); (2) deciding whether a given agent can influence the outcome of a judgment aggregation procedure in her favour by reporting insincere judgments (the strategic manipulation problem); and (3) deciding whether a given judgment aggregation scenario is guaranteed to result in a logically consistent outcome, independently from what the judgments supplied by the individuals are (the (...) problem of the safety of the agenda). We provide results both for specific aggregation procedures (the quota rules, the premisebased procedure, and a distance-based procedure) and for classes of aggregation procedures characterised in terms of fundamental axioms. (shrink)

We analyze the expressivity, succinctness, and complexity of a family of languages based on weighted propositional formulas for the representation of utility functions. The central idea underlying this form of preference modeling is to associate numerical weights with goals specified in terms of propositional formulas, and to compute the utility value of an alternative as the sum of the weights of the goals it satisfies. We define a large number of representation languages based on this idea, each characterized by a (...) set of restrictions on the syntax of formulas and the range of weights. Our aims are threefold. First, for each language we try to identify the class of utility functions it can express. Second, when different languages can express the same class of utility functions, one may allow for a more succinct representation than another. Therefore, we analyze the relative succinctness of languages. Third, for each language we study the computational complexity of the problem of finding the most preferred alternative given a utility function expressed in that language. (shrink)

In preference aggregation a set of individuals express preferences over a set of alternatives, and these preferences have to be aggregated into a collective preference. When preferences are represented as orders, aggregation procedures are called social welfare functions. Classical results in social choice theory state that it is impossible to aggregate the preferences of a set of individuals under different natural sets of axiomatic conditions. We define a first-order language for social welfare functions and we give a complete axiomatisation for (...) this class, without having the number of individuals or alternatives specified in the language. We are able to express classical axiomatic requirements in our first-order language, giving formal axioms for three classical theorems of preference aggregation by Arrow, by Sen, and by Kirman and Sondermann. We explore to what extent such theorems can be formally derived from our axiomatisations, obtaining positive results for Sen’s Theorem and the Kirman-Sondermann Theorem. For the case of Arrow’s Theorem, which does not apply in the case of infinite societies, we have to resort to fixing the number of individuals with an additional axiom. In the long run, we hope that our approach to formalisation can serve as the basis for a fully automated proof of classical and new theorems in social choice theory. (shrink)

We show how to embed a framework for multilateral negotiation, in which a group of agents implement a sequence of deals concerning the exchange of a number of resources, into linear logic. In this model, multisets of goods, allocations of resources, preferences of agents, and deals are all modelled as formulas of linear logic. Whether or not a proposed deal is rational, given the preferences of the agents concerned, reduces to a question of provability, as does the question of whether (...) there exists a sequence of deals leading to an allocation with certain desirable properties, such as maximising social welfare. Thus, linear logic provides a formal basis for modelling convergence properties in distributed resource allocation. (shrink)

We show that linear logic can serve as an expressive framework in which to model a rich variety of combinatorial auction mechanisms. Due to its resource-sensitive nature, linear logic can easily represent bids in combinatorial auctions in which goods may be sold in multiple units, and we show how it naturally generalises several bidding languages familiar from the literature. Moreover, the winner determination problem, i.e., the problem of computing an allocation of goods to bidders producing a certain amount of revenue (...) for the auctioneer, can be modelled as the problem of finding a proof for a particular linear logic sequent. (shrink)

Many collective decision making problems have a combinatorial structure: the agents involved must decide on multiple issues and their preferences over one issue may depend on the choices adopted for some of the others. Voting is an attractive method for making collective decisions, but conducting a multi-issue election is challenging. On the one hand, requiring agents to vote by expressing their preferences over all combinations of issues is computationally infeasible; on the other, decomposing the problem into several elections on smaller (...) sets of issues can lead to paradoxical outcomes. Any pragmatic method for running a multi-issue election will have to balance these two concerns. We identify and analyse the problem of generating an agenda for a given election, specifying which issues to vote on together in local elections and in which order to schedule those local elections. (shrink)

Under approval voting, each voter can nominate as many candidates as she wishes and the election winners are those candidates that are nominated most often. A voter is said to have voted sincerely if she prefers all those candidates she nominated to all other candidates. As there can be a set of winning candidates rather than just a single winner, a voter’s incentives to vote sincerely will depend on what assumptions we are willing to make regarding the principles by which (...) voters extend their preferences over individual candidates to preferences over sets of candidates. We formulate two such principles, replacement and deletion, and we show that, under approval voting, a voter who accepts those two principles and who knows how the other voters will vote will never have an incentive to vote insincerely. We then discuss the consequences of this result for a number of standard principles of preference extension in view of sincere voting under approval voting. (shrink)

We examine a variety of dialogue protocols, taking inspiration from two fields: natural language dialogue modelling and multiagent systems. In communicative interaction, one can identify different features that may increase the complexity of the dialogue structure. This motivates a hierarchy of abstract models for protocols that takes as a starting point protocols based on deterministic finite automata. From there, we proceed by looking at particular examples that justify either an enrichment or a restriction of the initial model.

We analyse the incentives of individuals to misrepresent their truthful judgments when engaged in collective decision-making. Our focus is on scenarios in which individuals reason about the incentives of others before choosing which judgments to report themselves. To this end, we introduce a formal model of strategic behaviour in logic-based judgment aggregation that accounts for such higher-level reasoning as well as the fact that individuals may only have partial information about the truthful judgments and preferences of their peers. We find (...) that every aggregation rule must belong to exactly one of three possible categories: it is either (i) immune to strategic manipulation for every level of reasoning, or (ii) manipulable for every level of reasoning, or (iii) immune to manipulation only for everykth level of reasoning, for some natural number kgreater than 1. (shrink)