Approximate Judgement Aggregation

In this paper we analyze judgement aggregation problems in which a group of agents independently votes on a set of complex propositions that has some interdependency constraint between them(e.g., transitivity when describing preferences). We consider the issue of judgement aggregation from the perspective of approximation. That is, we generalize the previous results by studying approximate judgement aggregation. We relax the main two constraints assumed in the current literature, Consistency and Independence and consider mechanisms that only approximately satisfy these constraints, that is, satisfy them up to a small portion of the inputs. The main question we raise is whether the relaxation of these notions significantly alters the class of satisfying aggregation mechanisms. The recent works for preference aggregation of Kalai, Mossel, and Keller fit into this framework. The main result of this paper is that, as in the case of preference aggregation, in the case of a subclass of a natural class of aggregation problems termed `truth-functional agendas', the set of satisfying aggregation mechanisms does not extend non-trivially when relaxing the constraints. Our proof techniques involve Boolean Fourier transform and analysis of voter influences for voting protocols. The question we raise for Approximate Aggregation can be stated in terms of Property Testing. For instance, as a corollary from our result we get a generalization of the classic result for property testing of linearity of Boolean functions. An updated version (RePEc:huj:dispap:dp574R) is available at http://www.ratio.huji.ac.il/dp_files/dp574R.pdf


Abstract Judgement Aggregation
Judgement Aggregation deals in scenarios in which one should aggregate a set of opinions/judgement done by independent judges or agents to one opinion. For instance, assume a committee needs to decide whether to deploy a suggested network protocol. It is acceptable by all voters that the protocol should be deployed if and only if it stands in two criteria: security (resistance to attacks) and scalability (supports several sizes of a network). We assume that each voter decides his opinion on the two criteria independently and based on this decides on whether to deploy the protocol. The voters cast their votes simultaneously and we assume no strategic behavior on their behalf. Now assume that a third of the voters are convinced that the protocol 1 stands in the two criteria and hence think it should be deployed while the other voters think it should not be deployed but disagree on the criterion that is violated. One third of the voters think it is not secure enough and hence should not be deployed although it is scalable. On the other hand, a third of the voters think it is secure but not scalable enough and hence should not be deployed. Then we have that although a minority of the committee (a third of the voters) thinks the protocol should be deployed, for each criterion separately there is a supporting majority (two thirds) that thinks the protocol passes. This discrepancy between the majority vote on premises (security and scalability) and the majority vote on the conclusion (deploy) was presented by Kornhauser and Sager in 1986 [28] and was later named 'The Doctrinal Paradox'. The deploy-network scenario is an example for a case when the decision is based on several arguments (while the logical connection between the arguments and the decision is commonly accepted) and we need to aggregate the decisions of (many) individuals into one decision. In general, one can think of scenarios in which the accepted opinions do not have this premise-conclusion structure ,for instance the Arovian agenda of preferences. A discrepancy phenomena as described above can happen for a lot of such sets of 'accepted opinions' (e.g., Condorcet Paradox for preference aggregation) and is the subject of a growing body of works in economics, political science, philosophy, law, and other related disciplines. (A survey of this field can be found in [32] and [30]) Abstract aggregation is the field that deals with such problems that arise when aggregating several opinions (constrained to be in some given group, the agenda) to one opinion. It can be formalized in the following way. There is a committee of n individuals (also called voters) that needs to decide on m binary issues (that is, each question has exactly two possible answers True and False 1 ). Each individual holds an opinion which is an answer for each of the issues. We denote the answer of the i th voter for the j th issue by X j i and the vector of all opinions in the committee (called profile) by X ∈ ({0, 1} m ) n (For the ease of presentation we will identify True with 1 and False with 0). Like in the example above, not all opinions are acceptable (one cannot accept a network protocol if it is not secure). We assume a non-empty set X of {0, 1} m called the agenda is given. The opinions in X are called the consistent opinions and only these opinions are held by voters 2 . For instance the conjunction agenda, which is the agenda described in the example, is defined to be the set {000, 010, 100, 111} 3 . A related model (that is more common in the literature) is 'Judgement Aggregation'. In this model the issues are logical propositions over a set of variables and a consistent opinion is an assignment to these variables (so not every combination of truth values for the proposition is achievable). We feel that the logical model is more suitable in cases where one searches for aggregation mechanisms that respect the semantics of the agenda (which is represented by the propositions). Since our work can be stated as impossibility results, we prefer using the more general model. In [16] Dokow and Holzman prove that the two models are equivalent in the sense that each set of consistent opinions can be described using a proposition set (although not uniquely).
An aggregation mechanism is a function that defines for any profile the aggregated opinion (F : ({0, 1} m ) n → {0, 1} m ). In this work we concentrate on two properties of aggregation mechanisms, which were the first to be studied, independence and consistency. Independence states that the aggregated opinion on the j th issue, (F (X)) j depends solely on the opinions on that issue X j . For instance, issue-wise majority that was presented above satisfies independence. Consistency of the aggregation mechanism states that whenever all the members of the committee hold consistent opinions, i.e., X ∈ X n , F returns a consistent opinion as well, i.e., F (X) ∈ X. For instance, for the conjunction agenda issue-wise majority , as can be seen in the deploy-protocol example, does not satisfy consistency. The consistency criterion is commonly accepted as regarding a system of agents as an agent and hence requiring it the same rationality constraint we require from the individual agents. For instance, firms(in which decisions are formed by aggregating opinions of different board members) act as a unit and it matters to the firms's credibility if it can be expected to behave coherently. The independence criterion, while not being uncontroversial, has some appeal in that it guarantees a proposition-wise approach to aggregation. In section 2.1 we discuss further this criterion and claim that it can be justified in many scenarios.
A natural question is to characterize the aggregation mechanisms that satisfy independence and consistency (for a given agenda). For the conjunction agenda (under mild and natural constraint 4 ) the only aggregation mechanisms that satisfy independence and consistency are the oligarchies (The oligarchy of a coalition S returns for each issue True iff all voters in S voted True for that issue). Since, the set of consistent and independent aggregation mechanisms is small and unnatural this characterization theorem is referenced as an impossibility result. Such impossibility results are quite strong. They shows the impossibility of finding any aggregation mechanism that satisfies the conditions. In other words: for each mechanism there will always be some judgement profiles that lead to a breakdown of the mechanism. In this work we deal with this point (and we think we even strengthening the impossibility result) by quantifying the number of profiles that lead to such breakdown.
For the conjunction agenda we prove: Theorem. 5 For any ǫ > 0, n 1, δ < Cn −2 ǫ 4 (for some constant C that does not depend on n), no aggregation mechanism F for the conjunction agenda over n voters satisfies the following five conditions: • F is δ-close to being independent.
I.e., there exists an independent (not necessarily consistent) aggregation mechanism G that returns the same aggregated opinion as F for at least (1 − δ) fraction of the profiles. • F is δ-close to being consistent.
I.e., F returns a consistent result for at least (1 − δ) fraction of the profiles. • F is ǫ-far from returning always False on one of the basic premises.
-F returns True as an aggregated opinion for the first issue for at least at least ǫ fraction of the profiles.
-F returns True as an aggregated opinion for the second issue for at least at least ǫ fraction of the profiles.
• F is ǫ-far from being an oligarchy. I.e., for any oligarchy G of a coalition S, F returns the same aggregated opinion as G for at most (1 − ǫ) fraction of the profiles.
In this paper we prove similar theorems for a family of agendas: truth-functional agendas in which every issue is either a premise or a conclusion defined as conjunction or xor of several premises (up to input & output negation). In a truth-functional agenda the issues are divided into two types: premises and conclusions. Each conclusion j is characterized by a binary function Φ j over the premises and an opinion is consistent if the answers to the conclusion issues are attained by applying the function Φ j on the answers to the premise issues.
For instance the conjunction agenda is a truth-functional agenda with two premises and one conclusion and we mark this by notating the agenda as A, B, A ∧ B . We restrict ourselves to truth-functional agendas in which the conclusions are either conjunction or xor up to negation of inputs and outputs 6 .

Approximate Judgement Aggregation
Lately there is a series of works coping with impossibility results in Social Choice using approximations (e.g., [7] and [22]). The version of approximation we define in this work is studying aggregation mechanisms that are almost consistent and almost independent. We quantify being almost consistent by defining δconsistency of an aggregation mechanism as having a consistent aggregation mechanism G that disagrees with F on at most δ fraction of the inputs 7 . Similarly, we quantify being almost independent by defining δ-independence of an aggregation mechanism as having an independent aggregation mechanism that disagrees with F on at most δ fraction of the inputs. Both terms can be equivalently defined as the failure probability of tests as we show in section 2 and actually the second versions of the definitions are those we use in the analysis since they are easier to work with.
Both definitions use the Hamming distance d X (F, G) = Pr [F (X) = G(X) | X ∈ X n ] which includes an assumption of uniform distribution over the opinions for each voter and that voters draw their opinions independently (Impartial Culture Assumption). This assumption, while certainly unrealistic, is the natural choice in this kind of work and is discussed further in section 2.
Trivially, if F is close to G and G is independent and consistent, F is δ-independent and δ-consistent for δ linear in d(F, G). Our main question is whether there are aggregation mechanisms that are close to being independent and consistent that are not close the (usually small) set of consistent and independent aggregation mechanisms.
In several agendas the set of consistent independent aggregation mechanisms is a very small set(E.g., dictatorship or oligarchies) and hence this question is equivalent to asking whether we can look for aggregation mechanisms that are close to being independent and close to being consistent without collapsing to the known small (perturbed) set of consistent independent aggregation mechanisms.

Connection to Approximate Preference Aggregation
Preceded our work is the works by Kalai [24], Mossel[35], and Keller [25] that proved similar approximate aggregation theorems for preference aggregation. In this agenda the consistent opinions represent the linear orders over a set of candidates {c 1 , c 2 , . . . , c s } and the issues are the s 2 pair-wise comparisons between candidates 8 .Similarly to the doctrinal paradox, the Condorcet Paradox [10] shows that issue-wise majority might lead to an inconsistent result for preference aggregation as well. Arrow's theorem [1] shows that (under mild and natural constraint 9 ) the only aggregation mechanisms that satisfy independence and consistency are the dictatorships.
The recent works of Kalai [24], Mossel[35], and Keller [25] proved similar results to the results we prove here.
Theorem ( [25]). There exists an absolute constant C such that the following holds: For any ǫ > 0 and k 3, if f is an aggregation mechanism for the preference agenda over k candidates that satisfies independence and C · ǫ/k 2 3 -consistency, , then there exists an aggregation mechanism G that satisfies independence and consistency such that d(F, G) < ǫ.

Connection to Property Testing
We think it is useful to phrase the question of approximate aggregation using terms of property testing. In this field we query a function at a small number of (random) points testing for a global property (In our case, the property is being a consistent independent aggregation mechanism). We discuss this connection further is section 5. For example a corollary of the results we present in this paper (in property testing terms): For any three binary functions f, g, h : (when the addition is in Z 2 and Z n 2 , respectively), then there exists three binary functions , and Pr[h(x) = h ′ (x)] are smaller than Cǫ for some constant C independent of n and Notice a special case of this result (for f = g = h) is the classic result of Blum, Luby, and Rubinfeld ( [4], [2]) for linear testing of boolean functions.

Techniques
We prove the main theorem by proving the specific case of independent aggregation mechanism for two basic agenda families: the conjunction agendas (agendas in which there is exactly one conclusion with is constrained to be the conjunction of the premises. 7.1) and the xor agendas (agendas in which there is exactly one conclusion with is constrained to be the xor of the premises. theorem 7.3). Later we show how to extend these theorems to the general theorem of relaxing both constraints (theorem 7.4).
We use two different techniques in the proofs. For the conjunction agendas we study influence measures 10 of voters on the issue-aggregating functions and for the xor agendas we use Fourier analysis of the issueaggregating functions.
An open question is whether one can find such bounds for any agenda or whether there exists an agenda for which the class of aggregation mechanisms that satisfy consistency and independence expands non trivially when we relax the consistency and independence constraints.
We proceed to describe the structure of the paper. In Section 2 we describe the formal model of aggregation mechanisms. In section 3 we give present the main agendas we deal with, truth-functional agendas, and specifically conjunction agendas and xor agendas. In section 4 we state the motivation to deal with approximate aggregation, and describe the known results for preference approximate aggregation by Kalai, Mossel, and Keller. In section 5 we describe the connection we find between Approximate Aggregation and the field of Property Testing. In sections 6 and 7 we describe our main theorems and outline the proof. Section 8 concludes.

The Model
We define the model similarly to [16] (which is Rubinstein and Fishburn's model [43] for the binary case) We consider a committee of n individuals that needs to decide on m issues. An opinion is a vector x = (x 1 , x 2 , . . . , x m ) ∈ {0, 1} m denoting an answer to each of the issues. An opinion profile is a matrix 10 Both the known influence (Banzhaf power index) and a new measure we define: The ignorability of a voter. X ∈ ({0, 1} m ) n denoting the opinions of the committee members so an entry X j i denotes the vote of the i th voter for the j th issue, the i th row of it X i states the votes of the i th individual on all issues, and the j th column of it X j states the votes of each of the individuals on the j th issue. In addition we assume that an agenda X ∈ {0, 1} m of the consistent opinions is given.
The basic notion in this field is an aggregation mechanism which is a function that returns an aggregated opinion (not necessarily consistent) for every profile (F : An aggregation mechanism satisfies Independence (and we say that the mechanism is independent) if for any two consistent profiles X and Y and an issue j, if X j = Y j (all individuals voted the same on the j th issue in both profiles) then (F (X)) j = (F (Y )) j (the aggregated opinion for the j th issue is the same for both profiles). This means that F satisfies independence if one can find m binary functions . . , f (X m ) for some issue aggregating function f , i.e., all issues are aggregated using the same function. We will use the notation f 1 , f 2 , . . . , f m for the independent aggregation mechanism that aggregates the j th issue using f j .
The main two measures we study in this paper are the inconsistency index IC X (F ) and the dependence index DI X (F ) of a given aggregation mechanism F and a given agenda X. These measures are relaxations of the consistency and independence criterion that are usually assumed in current works 13 . We define the measures by For an agenda X and an aggregation mechanism F for that agenda, the inconsistency index is defined to be the probability to get an inconsistent result.

Definition 2.2 (dependency index).
For an agenda X and an aggregation mechanism F for that agenda, the dependency vector DI j,X (F ) is defined as The definition can be seen as a test for independence of the j th issue as discussed in section 5 The dependency index DI X (F ) is defined by In contexts where the agenda is clear we omit the agenda superscript and notate these as IC(F ), DI j (F ), and DI(F ), respectively.
We define these two indexes using local tests. We prove that the more natural definition of distance to he class of aggregation mechanisms that satisfy consistence (or independence) is equivalent to the above (up to multiplication by δ by constant). Proposition 2.3. Let F be an aggregation mechanism for an agenda over m issues. Then F satisfies IC(F ) δ iff there exists a consistent aggregation mechanism H that satisfies d(F, H) δ. 11 We define the function for all profiles for simplicity but we are not interested in the aggregated opinion in cases one of the voters voted an inconsistent opinion. 12 Notice this property is a generalization of the IIA property for social welfare functions (aggregation mechanism for the preference agenda) so a social welfare function satisfies IIA iff it satisfies independence as defined here (when the issues are the pair-wise comparisons). 13 F satisfies consistency iff IC(F ) = 0 and independence iff DI(F ) = 0 Proposition 2.4. Let F be an aggregation mechanism and j an issue. If DI j (F ) ǫ, then there exists an aggregation mechanism H that satisfies DI j (H) = 0 and d(F, H) 2ǫ. If DI j (F ) ǫ, then every aggregation mechanism H that satisfies DI j (H) = 0, also satisfies d(F, H) 1 2 ǫ Proposition 2.5. Let F be an aggregation mechanism for an agenda over m issues that satisfies DI(F ) δ.
Then there exists an independent aggregation mechanism H that satisfies d(F, H) 2mδ.
These definitions include two major assumptions on the opinion profile distribution. First, we assume the voters pick their opinions independently and from the same distribution. Second, we assume a uniform distribution over the (consistent) opinions for each voter (Impartial Culture Assumption). The uniform distribution assumption, while certainly unrealistic, is the natural choice for proving 'lower bounds' on IC(F ). That is, proving results of the format 'Every aggregation mechanism of a given class has inconsistency index of at least γ(n)'. In particular, the lower bound, up to a factor δ, applies also to any distribution that gives each preference profile at least a δ fraction of the probability given by the uniform distribution. 14 Note that we cannot hope to get a reasonable bound result for every distribution. For instance, since for every aggregation mechanism we can take a distribution on profiles for which it returns a consistent opinion.

The Independence Property
The independence criterion is sometimes criticized as being unjustified normatively in most real-life scenarios 15 . The impossibility results of judgement aggregation can also be seen as 'empirical' argument against independence since they show that it contradicts the more natural assumption of consistency. While we accept this argument, we think our work quantifies the tradeoff between the two criteria. Moreover, in this section we claim that in the general case this criterion can be justified on several different grounds.
First, in a lot of cases it is justified to expect due to normative or legal reasons that changing an individual judgement on an issue should not change the collective judgement on another issue.
Secondly, there are works that defend this criterion by using manipulation-resistance arguments. In [15] Dietrich and List define the notion of manipulability of an aggregation mechanism 16 and proved that any aggregation mechanism that does not satisfy independence is manipulable. In this paper they further prove that this manipulability property is equivalent to a more game-theoretic property of strategy-proofness under some assumptions on players' preferences.
On the ground of simplicity of representation one can justify independence as a criterion that returns aggregation mechanisms that are easy to represent, calculate, or justify (For instance, justify a voting method to the public).
Other grounds of justification for such aggregation mechanisms are from the voter point of view. There might be a situations in which the decisions are made over time (different meetings) or place (different representatives of the same voting identity) so it is fair to assume that when voting on an issue or aggregating the votes it is unreasonable to depend on votes on other issues. Another argument might be than there are scenarios in which you need to define the aggregation method and only at a later stage choose from the 14 In successive works we relax this assumption and prove similar results for more general distributions. 15 Chapman( [8]) and Mongin([34]) attack this criterion and claim it removes the discipline of reason from social choice since it disregards the intra-issue dependencies which is the essence of the problem. According to this criterion the aggregation of 'complex' issues is done without regarding the reasons of the voters for their opinions and hence lacks the information for good aggregation. 16 An aggregation mechanism F is manipulable at the profile X by individual i(the manipulator) on issue j if X i j = (F (X)) j (The manipulator disagrees with the aggregated opinion on issue j), but X i j = (F (X ′ )) j for some profile X ′ that differs form X in i's vote only.(I.e. the manipulator can get his will on j by voting differently) set of issues the relevant one (For instance, the definition of Social Welfare Functions as returning a choice function so only at a later stage the society is faced with the menu of alternatives).

Binary Functions
Since this work deals with binary functions (for aggregating issues), we need to define several notions for this framework as well. To ease the presentation, throughout this paper we will identify True with 1 and False with 0 and use logical operators on bits and bit vectors (using entry-wise semantics). In addition we define a distance function over the binary functions. The distance between two functions f, g : {0, 1} n → {0, 1} is defined to be the probability of getting a different result (normalized Hamming distance). d(f, g) = Pr [f (x) = g(x)]. From this measure we will derive a distance from a function to a set of functions by d(f, G) = min g∈G d(f, g) One more notation we are using in this paper is x J for a binary vector x ∈ {0, 1} n and a coalition J ⊆ {1, 2, . . . n} for notating the entries of x that correspond to J. 17 An equivalent definition is: ∀x, y : f (x)+f (y) = f (x+y) when the addition is in Z2 and Z n 2 , respectively. 18 In the literature this criterion is sometimes referred to as Unanimity, e.g., in [32]. We choose to follow [17] and refer to it as Pareto to distinguish between it and the unanimity function which is the oligarchy of {1, 2, . . . , n}. 19 In the simple cooperative games regime, this is also called the Banzhaf power index of player i in the game f .

Agenda Examples
A lot of natural problems can be formulated in the framework of aggregation mechanisms. It is natural to divide the agendas to two major classes Truth-Functional Agendas and Non Truth-Functional Agendas.

Truth-Functional Agendas
In a truth-functional agenda the issues are divided into two types: k premises and (m − k) conclusions. The conclusion issues are binary functions over the k premises, Φ : An opinion is consistent if the answers to the conclusion issues are attained by applying the function Φ on the premise issues.
There are cases in which there might be more than one way to classify the issues to premises and conclusions. For instance, the 2-premises xor agenda described below X = {001, 010, 100, 111} can be defined both as A, B, A ⊕ B and as A, A ⊕ C, C . Since we choose to analyze the agenda as opinion sets (and not as a proposition set) we do not handle this point and notice that it is irrelevant for our results.
These agendas ,due their structure, seems to be a good point to start our work on approximate aggregation and in this paper we prove basic results for the following two families of truth-functional agendas. Later we derive results to a more general family of truth-functional agendas.

Conjunction Agendas
In the (m-premises) conjunction agenda A 1 , . . . , A m , m ∧ j=1 A j there are m + 1 issues to decide on and the consistency criterion is defined to be that the last issue is a conjunction of the other issues. For instance the Doctrinal Paradox agenda is the 2-premises conjunction agenda. A common description of the problem is of a group of judges or jurors that should decide whether a defendant is liable under a charge of breach of contract. Each of them should decide on three issues: whether the contract was valid (p), whether there was a breach (q) and whether the defendant is liable (r). In their decision making they are constrained by the legal doctrine that the defendant is only liable if the contract was valid and if there was indeed a breach (r ⇐⇒ (p ∧ q)).

Xor Agendas
Similarly, in the (m-premises) xor agenda A 1 , . . . , A m , m ⊕ j=1 A j there are m + 1 issues to decide on and the consistency criterion is defined to be that the third issue is True if the number of true-valued opinions for the first m is even. An equivalent way to define this agenda is constraining the number of True answers to be odd.

Non Truth-Functional Agendas
One can think on a lot of agendas that cannot be represented as a truth-functional agenda. Among such interesting natural agendas that were studied one can find the equivalence agenda [21], the membership agenda [42] [33], and the preference agenda described below.

Preference Aggregation
Aggregation of preferences is one of the oldest aggregation frameworks studied. In this framework there are s candidates and each individual holds a full strict order over them. We are interested in Social Welfare Functions which are functions that aggregate n such orders to an aggregated order. As seen in [36] and [12], this problem can be stated naturally in our framework by defining s 2 issues 20 .

Motivation & Known Results
We find the motivation for dealing with the field of approximate aggregation in three different disciplines.
• The consistent characterization are often regarded as 'impossibility results' in the sense that they 'permit' a very restrictive set of aggregation mechanisms. (e.g., Arrow's theorem tells us that there is no 'reasonable' way to aggregate preferences). Extending these theorems to approximate aggregation characterizations sheds light on these impossibility results by relaxing the constraints.
• , and a generalization of them to non-truth-functional agendas called sequential priority aggregation( [29], [14]). Another procedure in the literature is the distance-based aggregation( [40]) which is a well known for preference aggregation (E.g., Kemeny voting rule [26], Dodgson voting rule [3], and lately a more systematic analysis in [19]). Our work contribute to this discussion by pointing out where one should search for solutions while not leaving the consistency and independence constraints entirely.
• Connections to Property Testing as discussed in section 5 The first work studying approximate aggregation was done for the preference agenda over three candidate by Kalai [24] (although without stating the general framework of approximate aggregation). This work was generalized by Mossel[35], and Keller [25].
Theorem ([25] theorem 1.3). There exists an absolute constant C such that the following holds: For any ǫ > 0 and k 3, if f is an aggregation mechanism for the preference agenda over k candidates that satisfies independence and C · ǫ/k 2 3 -consistency, , then there exists an aggregation mechanism G that satisfies independence and consistency such that d(F, G) < ǫ.

Connection to Property Testing
In the words of [41], the field of property testing deals with the following: Given the ability to perform (local) queries concerning a particular object (e.g., a function or a graph), the task is to determine whether the object has a predetermined (global) property (e.g., linearity or bipartiteness), or is far from having the property. The task should be performed by inspecting only a small (possibly randomly selected) part of the whole object, where a small probability of failure is allowed. Property testing trades accuracy (the distance parameter) for efficiency (number of queries).
We think it is useful to view the Approximate Aggregation problem in the framework of Property Testing. Below we highlight the connection between Approximate Aggregation and a special case of Property testing 20 The issue i, j (for i < j) represents whether an individual prefers ci over cj .
In our case the global property we are trying to test is 'consistency and independence' of an aggregation mechanism. The class of satisfying aggregation mechanism is characterized by the current state of research. It is clear that each of the components of this property separately, consistency and independence of an issue, can be tested trivially. The consistency test consists of picking a (consistent) profile uniformly at random and checking whether the aggregated opinion is consistent. The test for independence of issue j consists of picking a (consistent) profile uniformly at random altering the opinion for each voter without changing the j th bit and check whether the aggregated opinion on the j th issue is changed due to the altering. For each of the two tests the probability to accept a non-satisfying mechanism is linear in the distance to the satisfying set (and equals IC(F ) and DI j (F ), respectively). The main question of this work (in property testing terms) can be stated as follows: What is the best test for being 'consistent and independent' one can assemble from running the (m+1) tests as black boxes (and therefore get information only on IC(F ) and DI j (F )). Similar question was asked lately in [9]. In [9] the authors query (among other similar questions) the conditions needed in order to deduce from testability of two properties the testability of the intersection of the two properties. Our work can be seen as studying this question for a specific domain in which the question seems to be natural and while adding the constraint that the test of the intersection property should be defined as a sequence of tests for the basic properties.
The main result of this paper is that for a class of mechanisms (corresponding to a natural class of agendas) one can assemble those tests to a test for the property 'consistent and independent'.
Similarly one can state questions dealing with sub-families of aggregation mechanisms. For example, as we stated in the introduction, the classic result of Blum, Luby, and Rubinfeld for linearity testing of boolean functions is a direct corollary of our result for the 2-premises xor agenda when considering systematic aggregation mechanisms.
Still, the target of the two fields is different. While Property Testing deals with finding the most efficient (query-wise) algorithm for testing a property (functions family), Approximate Aggregation deals with analyzing a specific family of tests.

Main Results
The main result of this paper is Theorem 6.1. For any ǫ > 0 and m, n 1, there exists δ IC , δ DI = n −2 ǫ m poly(m) , such that for every truth-functional agenda X over m issues, in which each non-premise issue is defined to be either conjunction of several premises or xor of several premises(up to negation of inputs or output) 21 , if F is an aggregation mechanism for X over n voters satisfying δ-independence and δ-consistency, then there exists an aggregation mechanism G that satisfies consistency and independence such that d(F, G) < ǫ Moreover, one can take δ IC = n −2 (1−βǫ)ǫ 5m m 2 +m−1 −β ǫ ǫ and δ DI = 1 2m β ǫ ǫ for any β ǫ ∈ 0, n −2 ǫ m m 2 +m−1 .
A direct corollary is the following impossibility result. X over m issues, in which each non-premise issue is defined to be either conjunction of several premises or xor of several premises(up to negation of inputs or output), no aggregation mechanism F for X over n voters satisfies the following three conditions: • δ-independence • δ-consistency • F is ǫ-far from any independent and consistent aggregation mechanism for X .
In the case of xor agenda (and its generalization, a truth-functional agenda in which all the conclusions are xor) we can get a much better result (e.g., no dependence on the number of voters) Theorem 6.3. Let m 3 and let the agenda be X = A 1 , . . . , A m−1 , A j . For any ǫ < 1 6 and any aggregation mechanism F : If F is an aggregation mechanism for X over n voters satisfying ǫ-independence and ǫ-consistency, then there exists an aggregation mechanism G that satisfies consistency and independence such that d(F, G) < m(2m + 3)ǫ Noticing that any affine agenda (i.e., an agenda that is an affine subspace) can be represented as a truth-functional agenda that uses xor conclusions only (lemma C.5) we can get the following corollary Corollary 6.4. For any ǫ > 0 and m, n 1, there exists δ = ǫ m(2m+3) , such that for every affine agenda X over m issues, if F is an aggregation mechanism for X over n voters satisfying δ-independence and δ-consistency, then there exists an aggregation mechanism G that satisfies consistency and independence such that d(F, G) < ǫ

Proof Sketch of the Main Theorem
In this section we sketch the techniques behind our proofs. The full proofs can be found in the appendices.
We prove the main theorem by proving three independent theorems. An approximation result for independent aggregation mechanisms for conjunction agendas (theorem 7.1). An approximation result for independent aggregation mechanisms for xor agendas (theorem 7.3). An agenda independent method of converting results for the independent case to the general case of relaxing both constraints (theorem 7.4). Using induction on the number of conclusions and noticing that negating (of the inputs and of the output) is renaming of opinions in our framework (and hence does not change the approximation results) we get theorem 6.1. For any ǫ > 0 and any independent aggregation mechanism F : If IC(F ) ǫ, then there exists an aggregation mechanism G that satisfies consistency and independence such that d(F, G) < 5m n 2 ǫ 1 m 2 +m−1 .

Conjunction Agenda
Technique: The main insight in the proof is that for any two different issue-aggregating functions, f and g, in F for two of the m premises, we can bound the product of the influence of a voter on f and the ignorability of the same voter for g using the inconsistency index of F by P i (f ) · I i (g) 4IC(F ).

Proof sketch.
Let F = f, g, h be an aggregation mechanism that satisfies IC(F ) ǫ. In case that f (or g) is close enough to the constant zero function, F is close to the consistent aggregation mechanism 0, g, 0 .
Otherwise, we define for a given function f : {0, 1} n → {0, 1} and a coalition J (the junta), the junta function f →J : {0, 1} n → {0, 1}. It is derived from f in the following way: I.e., for a given input, f →J reads only the votes of the junta members, iterates over all the possible votes for the members outside the junta, and returns the more frequent result (assuming uniform distribution over the votes of the voters outside J). We define f →J and g →J with regard to the junta of all the voters with small ignorability for either f or g.
We prove that f →J and g →J are close to f and g, respectively and that there exists an issue aggregation function h ⋆ such that f →J , g →J , h ⋆ is a consistent aggregation mechanism that is close to F .
There is a known characterization of the consistent independent aggregation mechanism for the conjunction agenda. (This characterization is a direct corollary from a series of works in the more general framework of aggregation, E.g., [37], [16]. We include a proof of it in the appendix) A corollary from this theorem and theorem 7.1 is a characterization of the approximate aggregation mechanisms for this agenda. Actually ,in the proof of theorem 7.1 we get a tighter characterization that distinguishes between the two cases of consistent independent aggregation mechanism. For any ǫ < 1 6 and any independent aggregation mechanism F : If IC(F ) ǫ, then there exists an aggregation mechanism G that satisfies consistency and independence such that d(F, G) mǫ.

Proof sketch.
Given an independent aggregation mechanism F = f, g, h we analyze the expression E [f (x)g(y)h(xy)] when x and y are sampled uniformly and independently.
On one hand we show that E [f (x)g(y)h(xy)] = 1−2IC(F ). On the other hand we show that E [f (x)g(y)h(xy)] = χ∈Lin f (χ) g(χ) h(χ) when f (χ) equals 1−2 min (d (f, χ) , d (f, −χ)). Hence, when IC(F ) is small then this sum is close to one 22 The proof is similar to the analysis of the BLR (Blum-Luby-Rubinfeld) linearity test done in [2]. and hence there exists a linear function such that f ,g, and h are close to it (up to negation). Noticing that for any linear function χ, χ, χ, χ and the permutations of −χ, −χ, χ are consistent independent aggregation mechanism for this agenda gives us the result.

Extending to δ-independence Results
Theorem 7.4. If there exists a function δ(ǫ, n) s.t. for any ǫ > 0 and n 1, if F is an aggregation mechanism for X over n voters satisfying independence and IC(F ) δ(ǫ), then there exists an aggregation mechanism G that satisfies consistency and independence such that d(F, G) < ǫ.
Then, for any ǫ > 0 and n 1, there exist δ IC , δ DI > 0, such that if F is an aggregation mechanism for X over n voters satisfying IC(F ) δ IC and DI(F ) δ DI , then there exists an aggregation mechanism G that satisfies consistency and independence such that d(F, G) < ǫ. Moreover, one can take In order to extend the results for the δ-dependent case (DI(F ) = 0) we prove the following agendaindependent proposition.
Proposition (Proposition 2.5). Let F be an aggregation mechanism for an agenda over m issues that satisfies DI(F ) δ. Then there exists an independent aggregation mechanism H that satisfies d(F, H) 2mδ.
I.e., if F is δ-independent we can find a close consistent aggregation mechanism H and since it is close we can deduce bounds on the proximity of F to the consistent and independent aggregation mechanisms from bounds on this proximity of H. Similarly, since H is close to F , we can deduce that if F is δ-consistent than H is δ ′ -consistent for δ ′ close to δ. Combining these we get the theorem.

Summary and Future Work
In this paper we defined the issue of approximate aggregation which is a generalization of the study of aggregation mechanisms that satisfy consistency and independence. We defined measures for the relaxation of the consistency constraint (inconsistency index IC) and for the relaxation of the independence constraint (dependency index DI). To our knowledge, this is the first time this question is stated in its general form.
We proved that relaxing these constraints does not extend the set of satisfying aggregation mechanisms in a non-trivial way for any truth-functional agenda in which every conclusion is either conjunction or xor up to negation of inputs or output. We saw that every conclusion of two premises can be stated as such. We also saw that any affine agenda can be represented as truth-functional agenda with xor conclusions only and derived a better approximate aggregation characterization for this family. Particulary we calculated the dependency between the extension of this class (ǫ) and the inconsistency index (δ(ǫ)) (although probably not strictly) for two families of truth-functional agendas with one conclusion. The relation we proved includes dependency on the number of voters (n). In the works that preceded us for preference agendas ( [24], [35], [25]) the relation did not include such a dependency. An interesting question is whether such a dependency is inherent for conjunction agendas or whether it is possible to prove a relation that does not depend on n.
A major assumption in this paper is the uniform distribution over the inputs which is equivalent to assuming i.i.d uniform distribution over the premises. We think that our results can be extended for other distributions (still assuming voters' opinions are distributed i.i.d) over the space over premises' opinions which seem more realistic.
Immediate extensions for this work can be to extend our result to more complex truth-functional agendas and generalize our results to non-truth-functional agendas to get a result unifying our work and Kalai, Mossel, and Keller's works for the preference agenda.
A major open question is whether one can find an agenda for which relaxing the constraints of independence and consistency extends the class of satisfying aggregation mechanisms in a non-trivial way.

A.1 Propositions A.1,A.3
For a given pair of independent aggregation mechanisms, the following propositions connect between the pairwise distance between respective issue-aggregating functions (which we found easier to analyze in most cases) and both the distance between the mechanisms and the inconsistency indices of them.
Proof of Proposition . Direct use of the union-bound inequality.
Proof of Proposition .
As a corollary of the above we get
Let F be an aggregation mechanism and j an issue. If DI j (F ) ǫ, then there exists an aggregation mechanism H that satisfies DI j (H) = 0 and d(F, H) 2ǫ. If DI j (F ) ǫ, then every aggregation mechanism H that satisfies DI j (H) = 0, also satisfies d(F, H) 1 2 ǫ

Proof of Proposition .
With no loss of generality assume that j = 1.
• Let F be an aggregation mechanism. We define the functions G 1 , . . . , G m : X n → {0, 1} by: and an aggregation mechanism G(X) = G 1 (X), . . . , G m (X) . Clearly • Let F be an aggregation mechanism that is ǫ-close to satisfy DI 1 (F ) = 0. That is, we can find an aggregation mechanism G such that d(F, G) ǫ and DI 1 (G) = 0.

Proposition.
Let F be an aggregation mechanism for an agenda over m issues that satisfies DI(F ) δ. Then there exists an independent aggregation mechanism H that satisfies d(F, H) 2mδ.

A.4 Id Agenda
For completeness we add here an approximate aggregation theorem for the id agenda A, A Theorem A.4. For any ǫ > 0 and any independent aggregation mechanism F : If IC A,A ǫ, then there exists an aggregation mechanism G that satisfies consistency and independence such that d(F, G) ǫ.
Proof. This theorem is trivial since Noticing that any aggregation mechanism of the form f, f is consistent for this agenda so we get the theorem. For any ǫ > 0 and any independent aggregation mechanism F : If IC(F ) ǫ, then there exists an aggregation mechanism G that satisfies consistency and independence such that d(F, G) < 5m n 2 ǫ I.e., for a given input, f →J reads only the votes of the junta members, iterates over all the possible votes for the members outside the junta, and returns the more frequent result (assuming uniform distribution over the votes of the voters outside J). We prove the following lemma: . . , f m , h is ∆-close to F = 0, f 2 , . . . , f m , h and (ǫ + ∆)-close to F = 0, f 2 , . . . , f m , 0 which is a consistent mechanism.
We will use the following isoperimetric inequality on the boolean cube: Proposition (The Isoperimetric Inequality for The Boolean Cube [5]).
Assume that for issues j, f j is not the constant zero function. We will prove that f 1 = f 2 = .
. . = f m = h ∈ Olig by proving the following series of claims.
• For all issues j f j (1) = 1 With no loss of generality, assume for contraction that f 1 (1) = 0. Let x ∈ {0, 1} n . Then I.e. h ≡ 0. From that we can conclude that there exists an issue j s.t. f j ≡ 0 and get a contradiction.
• For all issues j f j = h We will prove that f 1 = h. The proof is similar for all j. For any ǫ < 1 6 and any independent aggregation mechanism F : If IC(F ) ǫ, then there exists an aggregation mechanism G that satisfies consistency and independence such that d(F, G) mǫ.

Proof.
The theorem is a corollary of the following lemma: Noticing that a j χ is a consistent mechanism for any linear function χ and signs a j s.t. f j (S). 23 Fourier transforms are widely used in mathematics, computer science, and engineering. The main idea is representing the function f over an orthonormal basis χ S when the inner product is define to be f, g = E[f (x)g(x)] and the basis vectors χ S are defined to be χ S (x) = i∈S xi for S ⊆ {1, . . . , n}. The coefficients of f according to the Fourier basis are notated f (S). I.e., f ≡ S f (S)χ S . For a good introduction to the subject see [38], [11].
In this proof we are using the following: • χ S (xy) = χ S (x)χ S (y)