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)

Judgment aggregation studies how to aggregate individual judgments on logically correlated propositions into collective judgments. Different logics can be used in judgment aggregation, for which Dietrich and Mongin have proposed a generalized model based on general logics. Despite its generality, however, all nonmonotonic logics are excluded from this model. This paper argues for using nonmonotonic logic in judgment aggregation. Then it generalizes Dietrich and Mongin’s model to incorporate a large class of nonmonotonic logics. This generalization broadens the theoretical boundaries of (...) judgment aggregation by proving that, even if these nonmonotonic logics are employed, certain typical impossibility results still hold. (shrink)

A version of strong negation is introduced into Categorial Grammar. The resulting syntactic calculi turn out to be systems of connexive logic.

This introduction to the basic ideas of structural proof theory contains a thorough discussion and comparison of various types of formalization of first-order logic. Examples are given of several areas of application, namely: the metamathematics of pure first-order logic (intuitionistic as well as classical); the theory of logic programming; category theory; modal logic; linear logic; first-order arithmetic and second-order logic. In each case the aim is to illustrate the methods in relatively simple situations and then apply them elsewhere in much (...) more complex settings. There are numerous exercises throughout the text. In general, the only prerequisite is a standard course in first-order logic, making the book ideal for graduate students and beginning researchers in mathematical logic, theoretical computer science and artificial intelligence. For the new edition, many sections have been rewritten to improve clarity, new sections have been added on cut elimination, and solutions to selected exercises have been included. (shrink)

The aggregation of individual judgments on logically interconnected propositions into a collective decision on the same propositions is called judgment aggregation. Literature in social choice and political theory has claimed that judgment aggregation raises serious concerns. For example, consider a set of premises and a conclusion where the latter is logically equivalent to the former. When majority voting is applied to some propositions (the premises) it may give a different outcome than majority voting applied to another set of propositions (the (...) conclusion). This problem is known as the discursive dilemma (or paradox). The discursive dilemma is a serious problem since it is not clear whether a collective outcome exists in these cases, and if it does, what it is like. Moreover, the two suggested escape-routes from the paradox—the so-called premise-based procedure and the conclusion-based procedure—are not, as I will show, satisfactory methods for group decision-making. In this paper I introduce a new aggregation procedure inspired by an operator defined in artificial intelligence in order to merge belief bases. The result is that we do not need to worry about paradoxical outcomes, since these arise only when inconsistent collective judgments are not ruled out from the set of possible solutions. (shrink)

We can formalize judgments as logical formulas. Judgment aggregation deals with judgments of several agents, which need to be aggregated to a collective judgment. There are several logical formalizations of judgment aggregation. This paper focuses on a modal formalization which nicely expresses classical properties of judgment aggregation rules and famous results of social choice theory, like Arrow’s impossibility theorem. A natural deduction system for modal logic of judgment aggregation is presented in this paper. The system is sound and complete. As (...) an example of derivation, a formal proof of Arrow’s impossibility theorem is given. (shrink)

We investigate under what conditions a given set of collective judgments can arise from a specific voting procedure. In order to answer this question, we introduce a language similar to modal logic for reasoning about judgment aggregation procedures. In this language, the formula expresses that is collectively accepted, or that is a group judgment based on voting. Different judgment aggregation procedures may be underlying the group decision making. Here we investigate majority voting, where holds if a majority of individuals accepts, (...) consensus voting, where holds if all individuals accept, and dictatorship. We provide complete axiomatizations for judgment sets arising from all three aggregation procedures. (shrink)

Judgment aggregation theory, or rather, as we conceive of it here, logical aggregation theory generalizes social choice theory by having the aggregation rule bear on judgments of all kinds instead of merely preference judgments. It derives from Kornhauser and Sager’s doctrinal paradox and List and Pettit’s discursive dilemma, two problems that we distinguish emphatically here. The current theory has developed from the discursive dilemma, rather than the doctrinal paradox, and the final objective of the paper is to give the latter (...) its own theoretical development along the line of recent work by Dietrich and Mongin. However, the paper also aims at reviewing logical aggregation theory as such, and it covers impossibility theorems by Dietrich, Dietrich and List, Dokow and Holzman, List and Pettit, Mongin, Nehring and Puppe, Pauly and van Hees, providing a uniform logical framework in which they can be compared with each other. The review goes through three historical stages: the initial paradox and dilemma, the scattered early results on the independence axiom, and the so-called canonical theorem, a collective achievement that provided the theory with its specific method of analysis. The paper goes some way towards philosophical logic, first by briefly connecting the aggregative framework of judgment with the modern philosophy of judgment, and second by thoroughly discussing and axiomatizing the ‘general logic’ built in this framework. (shrink)

This introduces the symposium on judgment aggregation. The theory of judgment aggregation asks how several individuals' judgments on some logically connected propositions can be aggregated into consistent collective judgments. The aim of this introduction is to show how ideas from the familiar theory of preference aggregation can be extended to this more general case. We first translate a proof of Arrow's impossibility theorem into the new setting, so as to motivate some of the central concepts and conditions leading to analogous (...) impossibilities, as discussed in the symposium. We then consider each of four possible escape-routes explored in the symposium. (shrink)

Suppose that the members of a group each hold a rational set of judgments on some interconnected questions, and imagine that the group itself has to form a collective, rational set of judgments on those questions. How should it go about dealing with this task? We argue that the question raised is subject to a difficulty that has recently been noticed in discussion of the doctrinal paradox in jurisprudence. And we show that there is a general impossibility theorem that that (...) difficulty illustrates. Our paper describes this impossibility result and provides an exploration of its significance. The result naturally invites comparison with Kenneth Arrow's famous theorem (Arrow, 1963 and 1984; Sen, 1970) and we elaborate that comparison in a companion paper (List and Pettit, 2002). The paper is in four sections. The first section documents the need for various groups to aggregate its members' judgments; the second presents the discursive paradox; the third gives an informal statement of the more general impossibility result; the formal proof is presented in an appendix. The fourth section, finally, discusses some escape routes from that impossibility. (shrink)

Belief merging aims at combining several pieces of information coming from different sources. In this paper we review the works on belief merging of propositional bases. We discuss the relationship between merging, revision, update and confluence, and some links between belief merging and social choice theory. Finally we mention the main generalizations of these works in other logical frameworks.

A proof-theoretical treatment of collectively accepted group beliefs is presented through a multi-agent sequent system for an axiomatization of the logic of acceptance. The system is based on a labelled sequent calculus for propositional multi-agent epistemic logic with labels that correspond to possible worlds and a notation for internalized accessibility relations between worlds. The system is contraction- and cut-free. Extensions of the basic system are considered, in particular with rules that allow the possibility of operative members or legislators. Completeness with (...) respect to the underlying Kripke semantics follows from a general direct and uniform argument for labelled sequent calculi extended with mathematical rules for frame properties. As an example of the use of the calculus we present an analysis of the discursive dilemma. (shrink)

In the framework of judgment aggregation, we assume that some formulas of the agenda are singled out as premisses, and that both Independence (formula-wise aggregation) and Unanimity Preservation hold for them. Whether premiss-based aggregation thus defined is compatible with conclusion-based aggregation, as defined by Unanimity Preservation on the non-premisses, depends on how the premisses are logically connected, both among themselves and with other formulas. We state necessary and sufficient conditions under which the combination of both approaches leads to dictatorship (resp. (...) oligarchy), either just on the premisses or on the whole agenda. This framework is inspired by the doctrinal paradox of legal theory and arguably relevant to this field as well as political science and political economy. When the set of premisses coincides with the whole agenda, a limiting case of our assumptions, we obtain several existing results in judgment aggregation theory. (shrink)

The new …eld of judgment aggregation aims to …nd collective judgments on logically interconnected propositions. Recent impossibility results establish limitations on the possibility to vote independently on the propositions. I show that, fortunately, the impossibility results do not apply to a wide class of realistic agendas once propositions like “if a then b” are adequately modelled, namely as subjunctive implications rather than material implications. For these agendas, consistent and complete collective judgments can be reached through appropriate quota rules (which decide (...) propositions using acceptance thresholds). I characterise the class of these quota rules. I also prove an abstract result that characterises consistent aggregation for arbitrary agendas in a general logic. (shrink)

Informational semantics were first developed as an interpretation of the model-theory of substructural (and especially relevant) logics. In this paper we argue that such a semantics is of independent value and that it should be considered as a genuine alternative explication of the notion of logical consequence alongside the traditional model-theoretical and the proof-theoretical accounts. Our starting point is the content-nonexpansion platitude which stipulates that an argument is valid iff the content of the conclusion does not exceed the combined content (...) of the premises. We show that this basic platitude can be used to characterise the extension of classical as well as non-classical consequence relations. The distinctive trait of an informational semantics is that truth-conditions are replaced by information-conditions. The latter leads to an inversion of the usual order of explanation: Considerations about logical discrimination (how finely propositions are individuated) are conceptually prior to considerations about deductive strength. Because this allows us to bypass considerations about truth, an informational semantics provides an attractive and metaphysically unencumbered account of logical consequence, non-classical logics, logical rivalry and pluralism about logical consequence. (shrink)

This text is an outgrowth of notes prepared by J. Y. Girard for a course at the University of Paris VII. It deals with the mathematical background of the application to computer science of aspects of logic (namely the correspondence between proposition & types). Combined with the conceptual perspectives of Girard's ideas, this sheds light on both the traditional logic material & its prospective applications to computer science. The book covers a very active & exciting research area, & it will (...) be essential reading for all those working in logic & computer science. (shrink)

The initial sections of this text deal with syntactical matters such as logical formalism, cut-elimination, and the embedding of intuitionistic logic in classical linear logic. Concluding chapters focus on proofnets for the multiplicative fragment and the algorithmic interpretation of cut-elimination in proofnets.

Are companies, churches, and states genuine agents? Or are they just collections of individuals that give a misleading impression of unity? This question is important, since the answer dictates how we should explain the behaviour of these entities and whether we should treat them as responsible and accountable on the model of individual agents. Group Agency offers a new approach to that question and is relevant, therefore, to a range of fields from philosophy to law, politics, and the social sciences. (...) Christian List and Philip Pettit argue that there really are group or corporate agents, over and above the individual agents who compose them, and that a proper approach to the social sciences, law, morality, and politics must take account of this fact. Unlike some earlier defences of group agency, their account is entirely unmysterious in character and, despite not being technically difficult, is grounded in cutting-edge work in social choice theory, economics, and philosophy. (shrink)

Structural proof theory is a branch of logic that studies the general structure and properties of logical and mathematical proofs. This book is both a concise introduction to the central results and methods of structural proof theory, and a work of research that will be of interest to specialists. The book is designed to be used by students of philosophy, mathematics and computer science. The book contains a wealth of results on proof-theoretical systems, including extensions of such systems from logic (...) to mathematics, and on the connection between the two main forms of structural proof theory - natural deduction and sequent calculus. The authors emphasize the computational content of logical results. A special feature of the volume is a computerized system for developing proofs interactively, downloadable from the web and regularly updated. (shrink)

This book introduces an important group of logics that have come to be known under the umbrella term 'susbstructural'. Substructural logics have independently led to significant developments in philosophy, computing and linguistics. _An Introduction to Substrucural Logics_ is the first book to systematically survey the new results and the significant impact that this class of logics has had on a wide range of fields.The following topics are covered: * Proof Theory * Propositional Structures * Frames * Decidability * Coda Both (...) students and professors of philosophy, computing, linguistics, and mathematics will find this to be an important addition to their reading. (shrink)

This book introduces the reader to relevant logic and provides the subject with a philosophical interpretation. The defining feature of relevant logic is that it forces the premises of an argument to be really used in deriving its conclusion. The logic is placed in the context of possible world semantics and situation semantics, which are then applied to provide an understanding of the various logical particles and natural language conditionals. The book ends by examining various applications of relevant logic and (...) presenting some interesting open problems. It will be of interest to a range of readers including advanced students of logic, philosophical and mathematical logicians, and computer scientists. (shrink)

This is a long-awaited new edition of one of the best known Oxford Logic Guides. The book gives an introduction to intuitionistic mathematics, leading the reader gently through the fundamental mathematical and philosophical concepts. The treatment of various topics, for example Brouwer's proof of the Bar Theorem, valuation systems, and the completeness of intuitionistic first-order logic, have been completely revised.

I propose a relevance-based independence axiom on how to aggregate individual yes/no judgments on given propositions into collective judgments: the collective judgment on a proposition depends only on people’s judgments on propositions which are relevant to that proposition. This axiom contrasts with the classical independence axiom: the collective judgment on a proposition depends only on people’s judgments on the same proposition. I generalize the premise-based rule and the sequential-priority rule to an arbitrary priority order of the propositions, instead of a (...) dichotomous premise/conclusion order resp. a linear priority order. I prove four impossibility theorems on relevance-based aggregation. One theorem simultaneously generalizes Arrow’s Theorem (in its general and indifference-free versions) and the well-known Arrow-like theorem in judgment aggregation. (shrink)

Our aim in this survey article is to provide an accessible overview of some key results and questions in the theory of judgment aggregation. We omit proofs and technical details, focusing instead on concepts and underlying ideas.

The widely discussed "discursive dilemma" shows that majority voting in a group of individuals on logically connected propositions may produce irrational collective judgments. We generalize majority voting by considering quota rules, which accept each proposition if and only if the number of individuals accepting it exceeds a given threshold, where different thresholds may be used for different propositions. After characterizing quota rules, we prove necessary and sufficient conditions on the required thresholds for various collective rationality requirements. We also consider sequential (...) quota rules, which ensure collective rationality by adjudicating propositions sequentially and letting earlier judgments constrain later ones. Sequential rules may be path-dependent and strategically manipulable. We characterize path-independence and prove its essential equivalence to strategy-proofness. Our results shed light on the rationality of simple-, super-, and sub-majoritarian decision-making. (shrink)

Relevant logics provide an alternative to classical implication that is capable of accounting for the relationship between the antecedent and the consequence of a valid implication. Relevant implication is usually explained in terms of information required to assess a proposition. By doing so, relevant implication introduces a number of cognitively relevant aspects in the de nition of logical operators. In this paper, we aim to take a closer look at the cognitive feature of relevant implication. For this purpose, we develop (...) a cognitively-oriented interpretation of the semantics of relevant logics. In particular, we provide an interpretation of Routley-Meyer semantics in terms of conceptual spaces and we show that it meets the constraints of the algebraic semantics of relevant logic. (shrink)

The new field of judgment aggregation aims to merge many individual sets of judgments on logically interconnected propositions into a single collective set of judgments on these propositions. Judgment aggregation has commonly been studied using classical propositional logic, with a limited expressive power and a problematic representation of conditional statements ("if P then Q") as material conditionals. In this methodological paper, I present a simple unified model of judgment aggregation in general logics. I show how many realistic decision problems can (...) be represented in it. This includes decision problems expressed in languages of classical propositional logic, predicate logic (e.g. preference aggregation problems), modal or conditional logics, and some multi-valued or fuzzy logics. I provide a list of simple tools for working with general logics, and I prove impossibility results that generalise earlier theorems. (shrink)

This essay is structured around the bifurcation between proofs and models: The first section discusses Proof Theory of relevant and substructural logics, and the second covers the Model Theory of these logics. This order is a natural one for a history of relevant and substructural logics, because much of the initial work — especially in the Anderson–Belnap tradition of relevant logics — started by developing proof theory. The model theory of relevant logic came some time later. As we will see, (...) Dunn’s algebraic models [76, 77] Urquhart’s operational semantics [267, 268] and Routley and Meyer’s relational semantics [239, 240, 241] arrived decades after the initial burst of activity from Alan Anderson and Nuel Belnap. The same goes for work on the Lambek calculus: although inspired by a very particular application in linguistic typing, it was developed first proof-theoretically, and only later did model theory come to the fore. Girard’s linear logic is a different story: it was discovered though considerations of the categorical models of coherence.. (shrink)

All existing impossibility theorems on judgment aggregation require individual and collective judgment sets to be consistent and complete, arguably a demanding rationality requirement. They do not carry over to aggregation functions mapping profiles of consistent individual judgment sets to consistent collective ones. We prove that, whenever the agenda of propositions under consideration exhibits mild interconnections, any such aggregation function that is "neutral" between the acceptance and rejection of each proposition is dictatorial. We relate this theorem to the literature.

Several recent results on the aggregation of judgments over logically connected propositions show that, under certain conditions, dictatorships are the only propositionwise aggregation functions generating fully rational (i.e., complete and consistent) collective judgments. A frequently mentioned route to avoid dictatorships is to allow incomplete collective judgments. We show that this route does not lead very far: we obtain oligarchies rather than dictatorships if instead of full rationality we merely require that collective judgments be deductively closed, arguably a minimal condition of (...) rationality, compatible even with empty judgment sets. We derive several characterizations of oligarchies and provide illustrative applications to Arrowian preference aggregation and Kasher and Rubinsteinís group identification problem. (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 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)

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)

The impossibility results in judgement aggregation show a clash between fair aggregation procedures and rational collective outcomes. In this paper, we are interested in analysing the notion of rational outcome by proposing a proof-theoretical understanding of collective rationality. In particular, we use the analysis of proofs and inferences provided by linear logic in order to define a fine-grained notion of group reasoning that allows for studying collective rationality with respect to a number of logics. We analyse the well-known paradoxes in (...) judgement aggregation and we pinpoint the reasoning steps that trigger the inconsistencies. Moreover, we extend the map of possibility and impossibility results in judgement aggregation by discussing the case of substructural logics. In particular, we show that there exist fragments of linear logic for which general possibility results can be obtained. (shrink)