Combinatorial Aggregation

Combinatorial Aggregation

Umberto Grandi

Institute for Logic, Language and Computation University of Amsterdam u.grandi@uva.nl

Social Choice Theory (SCT), and the study of collective methods for decision making in general, have received a lot of attention in the AI community in recent years. The reasons for this focus are clear: SCT provides tools for the analysis of collective choices of groups of agents, and as such is of immediate relevance to the study of multiagent systems. At the same time, studies in AI have led to a new and broadened perspective on classical results in SCT, e.g., via the use of knowledge representation languages for modelling preferences in social choice problems or via the complexity-theoretic analysis of the implementation of social choice rules (Chevaleyre et al., 2007). Particularly close to the interests of AI is the problem of social choice in combinatorial domains (Chevaleyre et al., 2008), where the space of alternatives the individuals have to choose from has a combinatorial structure.

Definition 1. A combinatorial domain D is a finite product D = D1 × · · · × Dm where each Dj is finite.

My work aims at carrying out a complete analysis of problems of combinatorial aggregation, with particular attention to the binary case. In this general framework a set of individuals each make a choice over a finite number of issues, and such choices have to be aggregated into a collective one. Given a combinatorial domain D and a set of individuals N an aggregation procedure is a function F : DN → D.

I believe that such problems of combinatorial aggregation are crucial to the study of both voting in combinatorial domains and more classical frameworks in SCT, like preference and judgment aggregation. First, several situations of decision making are instances of combinatorial aggregation, such as referenda and voting for committees. Second, aggregation problems where individuals express complex ballots, such as preferences or judgments, can be modelled as combinatorial aggregation problems for suitably enriched domains. This suggests that combinatorial aggregation is a general framework for the study of situations of collective decision making. Third, on a more practical level this work makes it possible for mechanism designers to analyse situations of decision making using a general framework to point out possible inconsistencies and avoid paradoxical situations.

I intend to approach the study of combinatorial aggregation in the following way. First, carry out a thorough analysis of aggregation in binary combinatorial domains, proving several results in this general setting and apply them to classical frameworks of SCT. Second, extend these results to more complex combinatorial domains. Finally, explore possible uses of combinatorial aggregation in sequential voting, and discuss theoretical generalisations to more complex logical languages and practical applications.

Binary Aggregation with Integrity Constraints

Binary aggregation builds on the easiest example of combinatorial domain, where D={0, 1}m, and has been recently studied in detail by Dokow and Holzman (2010).

In contrast to the classical use of the axiomatic method, Grandi and Endriss (2010) put forward a different approach to study binary aggregation procedures, inspired by research in AI. As long as we do not know the intended application of the model, there is no appropriate set of axioms to concentrate on. Instead, we prove characterisation results concerning one single axiom at a time, and we explore ways to combine different results together, depending on the application at hand.

We therefore introduce a propositional language to define domains of aggregation (i.e.,subsets of D) by expressing a rationality assumption common to all individuals. We call an aggregation procedure collectively rational (CR) with respect to an integrity constraint IC if whenever all the ballots submitted by the individuals satisfy the formula IC, so does the outcome of aggregation. A procedure is CR with respect to IC if it lifts the integrity constraints from the individual to the collective level. We call a procedure CR with respect to a language L if it is CR with respect to all formulas in L.

Consider the following example: Let IC = ¬(p1 ∧p2 ∧p3) and suppose there are three individuals, choosing (1, 1, 0), (1, 0, 1) and (0, 1, 1), respectively, i.e., their choices are rational (they all satisfy IC). If we use issue-wise majority (accepting pi if a majority of individuals do) to aggregate their choices, however, we obtain (1, 1, 1), which fails to be rational. Thus issue-wise majority is not CR with respect to IC.

Classical axioms can be adapted for binary aggregation procedures and we characterise, for several simple fragments L of the language of propositional logic, the associated class of collectively rational procedures as the set of procedures satisfying a certain set of axioms. Call CR[L] the class of collectively rational procedures for L, and FL[AX] the set of procedures satisfying axioms AX on domains defined by L. We prove several characterisation results like the following:

Proposition 1. CR[cubes] = Fcubes[unanimity].

This proposition characterises the class of CR procedures for the language of cubes (conjunctions of literals) as the class of unanimous procedures. Similar results hold for the language of positive and negative bi-implications (the corresponding axioms being two versions of neutrality). As a negative counterpart, we show that there exists no language that characterises the classes of anonymous and independent procedures.

Such results can be seen as characterisations of classical axioms in terms of collective rationality. This suggests that a classification of axioms can be carried out, exploring to what extent axiomatic requirements for aggregation procedures can be expressed as collective rationality wrt. a certain language.

Preference and Judgment Aggregation

Classical frameworks of SCT like preference aggregation (Arrow, 1963) and judgment aggregation (List and Puppe, 2009) can be seen as instances of binary aggregation by devising suitable integrity constraints (Grandi and Endriss, 2011). For instance, aggregation of linear orders can be seen as binary aggregation over a set of issues {pab | a, b∈X}, where X is the set of alternatives. The properties of linear orders can be enforced by using integrity constraints such as pab ∧pbc→pac (transitivity). Classical paradoxical situations, like the Condorcet and the doctrinal paradox, can be seen as instances of a general definition of paradox in terms of collective rationality.

Employing characterisation results proved for binary aggregation we can obtain new results in preference aggregation and, more importantly, devise a new proof method. By identifying a clash between the syntactic shape of integrity constraints defining this framework and a number of axiomatic postulates we aim at formalising the argument that sees Arrovian impossibilities arise from the incompatibility between the axiom of independence and the constraints of transitivity.

The same method applies to judgment aggregation: Various properties that characterise safe agendas (Endriss et al., 2010) have a syntactic analogous requirement for the corresponding set of binary integrity constraints.

I will explore to what extent similar results can be proved for other frameworks (e.g., aggregation of weak or partial orders) exploring general results by representing relations over sets as binary ballots satisfying suitable integrity constraints.

General Combinatorial Domains

We put forward the following language for the study of aggregation in general combinatorial domains: let LPS be the propositional language built on the following set of propositional symbols PS = {xj=aj | j=1 . . .m aj∈Dj}. By devising suitable integrity constraints we are able to express ballots for plurality and approval voting on combinatorial domains and axioms for aggregation in combinatorial domains can be adapted from the literature (Lang, 2007). We obtained preliminary results for the more simple case of voting for committees, where all domains Dj are equal and D = Dm.

A more complex language could be devised from LPS to express preferences in combinatorial domains by adding a binary predicate <. A study of the expressivity of the language and of the properties of the aggregation represents an interesting idea for future work, building for instance on work by Bienvenu et al. (2010).

Sequential Vote

Airiau et al. (2011) identify and analyse the problem of generating an agenda for sequential vote in a given election on a combinatorial domain, specifying which issues to vote on together in local elections and in which order to schedule those elections. A possible application of the framework of binary aggregation with integrity constraints is the analysis of aggregation of dependency graphs, a crucial part of that work.

Applications

The framework of combinatorial aggregation has strong links and similarities with some of the techniques employed in multi-criteria decision analysis (Figueira et al., 2004). I believe a great potential lies in the definition of a language for individuals to analyse situations and avoid paradoxical (i.e., unexpected) results. An interesting experimental direction lies in the definition of concrete procedures to analyse decision making processes in combinatorial domains.

Aggregation of Logical Structures

In the first part of this work we expressed rationality assumptions using a simple propositional language, but as models for agents gets more and more refined, this language is no more sufficiently expressive. A preliminary study of the aggregation of logical structures more complex than simple propositional models can be carried out, building, for instance, on results in multiagent modal epistemic logic.