--- title: "Representation Matters: Characterisation and Impossibility Results for Interval Aggregation" authors: - "Ulle Endriss" - "Arianna Novaro" - "Zoi Terzopoulou" doi: "10.24963/ijcai.2022/41" url: "https://ijcai.org/proceedings/2022/41" pdf: "https://ijcai.org/proceedings/2022/0041.pdf" venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence" year: 2022 pages: "286-292" track: "Main Track" keywords: - "Agent-based and Multi-agent Systems: Computational Social Choice" --- # Representation Matters: Characterisation and Impossibility Results for Interval Aggregation Ulle Endriss, Arianna Novaro, Zoi Terzopoulou *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 286-292. DOI: [10.24963/ijcai.2022/41](https://doi.org/10.24963/ijcai.2022/41) ## Abstract In the context of aggregating intervals reflecting the views of several agents into a single interval, we investigate the impact of the form of representation chosen for the intervals involved. Specifically, we ask whether there are natural rules we can define both as rules that aggregate separately the left and right endpoints of intervals and as rules that aggregate separately the left endpoints and the interval widths. We show that on discrete scales it is essentially impossible to do so, while on continuous scales we can characterise the rules meeting these requirements as those that compute a weighted average of the endpoints of the individual intervals. ## Full text ## 1 Introduction We often need to perform some form of interval aggregation. Examples include people agreeing on a time slot for a meeting or pollsters aggregating confidence intervals. For other applications, the agents reporting the intervals could be autonomous software agents. In this paper, we think of interval aggregation as a problem of social choice and use methods developed in social choice theory to identify attractive aggregation rules [Arrow et al., 2002; Brandt et al., 2016]. An issue that has received little to no attention in prior work is the chosen form of representation for an interval. Which representation is most appropriate often depends on the application. For example, when scheduling a meeting, it is natural to talk about its starting time (the left endpoint of the interval) and its duration (the width). But when discussing an investment, we tend to think of upper and lower bounds on the amount of money to be spent (right and left endpoints). We call an aggregation rule F faithful to a given form of representation if we can define F in terms of "local" aggregators that each operate on just one of the components of this representation. Most rules proposed in the literature and used in practice are of this kind (see Example 2 in Section 2). The core question we investigate in this paper is how the choice of representation impacts the faithful rules we can design. Example 1. Three agents have to report intervals on the scale S = {1, 2, 3, 4, 5}, representing afternoon hours, to organise a meeting. Consider a first profile on the left, where agent 1 reports [1, 2], agent 2 reports [2, 4], and agent 3 reports [2, 3]; while in the second profile, agent 3 switches to [4, 5]: ![Image](https://ijcai.org/proceedings/2022/fulltext/41/image_000000_97c4952f9494336f53c26702e57b55262a3a5574ebf60158b0a939daab6c9192.png) ![Image](https://ijcai.org/proceedings/2022/fulltext/41/image_000001_8e0aa0791d66b6125c6be14aff64620d74cd554b8cf0e7c73bf3f054a08a078e.png) If we think of intervals as being represented by their endpoints, then a very natural choice of aggregation rule is to return as left endpoint the median of the individual left endpoints, and to do likewise for the right endpoints. This median-endpoint rule, which by its very definition is faithful to the left/right-endpoint representation, returns [2, 3] for the first profile and [2, 4] for the second profile. Now suppose we instead want to think of an interval as being represented by its left endpoint and its width. Is there a natural formulation of our rule that is faithful to this new representation? The answer is "no". To see why, observe that we would have to compute the appropriate width based only on the individual widths reported, yet for both interval profiles, the corresponding profile of widths is the same: (1, 2, 1). △ We thus cannot separate the choice of aggregation rule from the choice of representation: the "framing" of the aggregation problemmatters. Is this specific to the median-endpoint rule? Or can we find natural rules that are faithful to more than one representation? This is an important question, because a positive answer would provide protection against strategic exploitation of such framing effects. 1 As we shall see, the answer depends heavily on the type of scale used. For example, on the continuous scale S = [0, 1], i.e., the scale of real numbers between 0 and 1, the rule that computes the average left and right endpoints can alternatively be thought of as the rule that computes the average left endpoint and the average width. But this would not be a well-defined rule on a discrete scale such as S = {1, 2, 3, 4, 5}, as here computing averages can take us outside of the scale. The fact that the notion of representation has been neglected in prior work on interval aggregation might, at least in part, be due to the origins of the field of social choice theory in Economics, where such questions are not routinely investigated. But when considered from the point of view of Computer Science and AI, giving centre stage to the matter of how to represent information is very natural. Indeed, the representation-oriented perspective we advocate here is crucial both for the transparency of aggregation rules for people and when implementing aggregation rules on a computer. 1 This issue is related to the problem of strategic agenda setting, which has been studied in the context of both parliamentary floor voting [Rasch, 2000] and judgment aggregation [Dietrich, 2016]. Related work. There appears to be no prior work on representational issues in interval aggregation, although related questions have been considered in other fields [Cariani et al., 2008; Marquis and Schwind, 2014]. In much of the literature, intervals are used to model uncertainty and the objective of aggregation is to approximate a ground truth. Instead, our interest is in intervals themselves (e.g., time intervals with a beginning and a duration) and normative questions that can be addressed using the axiomatic method [Thomson, 2001]. Farfel and Conitzer [2011] study interval aggregation in a model very similar to ours. They represent intervals by their endpoints and champion the aforementioned medianendpoint rule. Further afield, the literature on opinion pooling deals with individual probability functions over an event space being aggregated into a collective probability function [Dietrich and List, 2016]. One axiomatic result is that an aggregation rule behaving as a weighted average for every event-what Stone [1961] calls the linear opinion pool-is the only kind that satisfies the normative principles of independence and unanimity [Acz´el and Wagner, 1980; McConway, 1981]. Another stream of research concerns the aggregation of confidence intervals, where a single point (rather than an interval) is required as the outcome. Yaniv [1997] introduced the popular unweighted average of midpoints, a more general version of which is the precisionweighted average of midpoints. In fuzzy systems, various arithmetical operations have been proposed for combining pairs of fuzzy intervals [Dubois and Prade, 1993], while work in multi-criteria decision analysis has dealt with the aggregation of interval orders [Pirlot and Vincke, 1997]. Contribution. We introduce a formal model to study the aggregation of intervals via representation-oriented rules. We focus on rules that are faithful to two different representations, namely the one based on left and right endpoints, and the one based on left endpoints and interval widths. Our main technical results show that (i) on discrete scales it is essentially impossible to design rules that are faithful to both representations (the only exceptions are so-called dictatorships), while (ii) on continuous scales a rule is faithful to both representations if and only if it is a weighted averaging rule. Paper outline. In Section 2 we introduce our model of interval aggregation and define the central concept of representation-faithfulness. Then Section 3 is devoted to our impossibility results for discrete scales and Section 4 to our characterisation results for continuous scales. Section 5 concludes. ## 2 The Model We are interested in the aggregation of multiple intervals, defined on a common scale, into a single such interval by means of rules that are faithful to the chosen representation of intervals. Let us define these concepts one by one. Scales. A scale is simply a nonempty set S ⊆ R of real numbers with a minimum and a maximum element. Examples include S = [0, 1] and the modern 7-point Danish grading scale S = {-3, 0, 2, 4, 7, 10, 12} [UFM, 2007]. Scales can be finite or infinite. We also refer to finite scales as discrete scales. We call infinite scales S = [a, b] that include all real numbers from a ∈ R to b ∈ R continuous scales, and S = [0, 1] the standard continuous scale. For the definitions that follow, suppose we have fixed a concrete scale S. Intervals. A (closed) interval is a nonempty subset I ⊆ S with {z ∈ S | x < z < y} ⊆ I for all x, y ∈ I, as well as inf(I), sup(I) ∈ I. For example, on the Danish grading scale both {0, 2, 4} and {4} are intervals (even though the latter is degenerate), but {4, 10} is not. For a given scale S, let I(S) denote the set of all intervals definable on S. For ease of exposition, we often refer to concrete intervals by their two endpoints in the familiar manner. So the interval {0, 2, 4} on the Danish grading scale becomes [0, 4]. Representation. There are many different ways in which one can represent an interval. For example, we can identify an interval by its endpoints, or by its midpoint and its width. A component is a function γ : I(S) → D, for some (component-specific) domain D. Examples include: - left endpoint ℓ : I ↦→min(I) - right endpoint r : I ↦→max(I) - width w : I ↦→max(I) -min(I) - midpoint m : I ↦→ [min(I) +max(I)] / 2 Given a vector γ = (γ1, . . . , γq) of components of the form γk : I(S) → Dk and an interval I, we write γ(I) to denote the vector (γ1(I), . . . , γq(I)) ∈ D1 × · · · ×Dq. A representation formalism (or simply: a representation) is a vector of components γ = (γ1, . . . , γq) for which γ(I) = γ(I ′ ) implies I = I ′ for all I, I ′ ∈ I(S). That is, it must be possible to uniquely identify an interval from its components. Rules. Fix a set N = {1, . . . , n} of agents. Each i ∈ N supplies us with an interval Ii ∈ I(S), giving rise to a profile I = (I1, . . . , In). We are interested in aggregation rules F : I(S)n → I(S) to map any such profile to a single interval. Faithfulness. We call a rule F : I(S)n → I(S) faithful to a representation γ = (γ1, . . . , γq) with components γk : I(S) → Dk for k ∈ {1, . . . , q}, if there exist functions fk : Dn k → Dk, one for each k ∈ {1, . . . , q}, such that for any profile I = (I1, . . . , In) we can compute F(I) by first computing one profile (γk(I1), . . . , γk(In)) for each component γk and then aggregating each of these profiles: To be precise, this procedure will return the representation γ(F(I)) rather than F(I) itself. By definition, for any (γ1, . . . , γq)-faithful rule F, the corresponding vector (f1, . . . , fk) is uniquely determined by F. By a slight abuse of notation, we write F = (γ1, . . . , γq) ◦ (f1, . . . , fq). Example 2. The median-endpoint rule of Example 1, also advocated by Farfel and Conitzer [2011], can be written as F = (ℓ, r) ◦ (med,med), where med returns the (lower) median of any given vector of numbers. The rule F = (ℓ, r) ◦ (min, max) amounts to computing the convex hull of the union of the input intervals; in risk analysis this is known as an enveloping method [Ferson and Kreinovich, 2001]. The unweighted average-midpoint rule of Yaniv [1997] is F = (m,w) ◦ (avg, null), where avg returns the arithmetic mean and null is a constant function that always returns 0. △ Component-unanimity. We call a rule F = (γ1, . . . , γq) ◦ (f1, . . . , fq) component-unanimous if each componentaggregator fk is unanimous, i.e., if fk(x, . . . , x) = x for every x ∈ Dk. Component-unanimity is a natural requirement, but it is violated, e.g., by the unweighted average-midpoint rule. Note that component-unanimity implies unanimity of F in the sense of enforcing F(I, . . . , I) = I for every interval I. Basic results. We often refer to a rule that is both faithful to γ and component-unanimous simply as a γ-rule. We conclude this section by establishing some basic results for γ-rules. We use γ ⊕ γ ′ to denote the concatenation of two vectors γ and γ ′ ; and we write γ ⊒ γ ′ if {γ1, . . . , γq} ⊇ {γ ′1 , . . . , γ ′q′} for γ = (γ1, . . . , γq) and γ ′ = (γ ′1 , . . . , γ ′q′). Lemmas 1 and 2 follow immediately from our definitions: Lemma 1. Let γ and γ ′ be vectors of components. Then F is both a γ- and a γ ′ -rule if and only if it is a γ ⊕ γ ′ -rule. Lemma 2. Let γ and γ ′ be vectors of components such that γ ⊒ γ ′ . Then every γ-rule F is also a γ ′ -rule. These lemmas imply that the task of designing a rule that is both an (ℓ, r)- and an (ℓ, w)-rule is equivalent to designing an (ℓ, r, w)-rule. The next lemma will simplify this task. Lemma 3. For the component-aggregators fℓ and fr of any given (ℓ, r, w)-rule, it must be the case that fℓ = fr. Proof. When all agents submit a degenerate interval with width 0, fℓ and fr receive the same profile of points as input and must both return the same single point as output (as by component-unanimity of the (ℓ, r,w)-rule, the collective interval also must have width 0). But assuming that agents submit degenerate intervals does not restrict the range of point profiles we might encounter, so the claim follows. When min(S) = 0, for every point x ∈ S the interval [0, x] has width x, which means that fw must be defined on all points in S (and possibly more). So we can speak of fw↾S, the restriction of the function fw to the domain S. Lemma 4. For the component-aggregators fℓ, fr, and fw of any given (ℓ, r,w)-rule that is defined on a scale S with min(S) = 0, it must be the case that fℓ = fr = fw↾S. Proof. We must account for the possibility that every agent submits an interval that starts at 0. Observe that for any such interval, its right endpoint is represented by the same number as its width. So, as in the proof of Lemma 3, we must have fr = fw↾S (and fℓ = fr follows from that lemma). The next lemma can be used, under certain conditions, to obtain bounds on the range of a component-aggregator. Lemma 5. For any given (ℓ, r)-rule F with fℓ = fr that is defined on a scale S and any point profile x ∈ Sn , it is the case that min(x) ⩽ f(x) ⩽ max(x) for f := fℓ = fr. Proof. Note that [min(x), xi] and [xi,max(x)] are wellformed intervals for all i ∈ N. Due to unanimity, we obtain: As the intervals on the right need to be well-formed as well, we obtain min(x) ⩽ fr(x) and fℓ(x) ⩽ max(x). Together with f = fℓ = fr this establishes the claim. Finally, we establish a simple monotonicity property. For two vectors x, y ∈ Sn , we say that x dominates y and write x ⩾ y if it is the case that xi ⩾ yi for all i ∈ N. Lemma 6. For any given (ℓ, r)-rule F with fℓ = fr defined on a scale S and any point profiles x, y ∈ Sn with x ⩾ y, it is the case that f(x) ⩾ f(y) for the function f := fℓ = fr. Proof. If x ⩾ y, then [yi, xi] is a well-formed interval for every i ∈ N, so we can apply F to ([y1, x1], . . . , [yn, xn]). As the outcome [fℓ(y), fr(x)] must be a well-formed interval as well, we obtain f(x) = fr(x) ⩾ fℓ(y) = f(y). ## 3 Impossibility Results: Discrete Scales We saw in Example 1 that the median-endpoint rule, which is an (ℓ, r)-rule, cannot be cast as an (ℓ, w)-rule-at least not for the specific five-point scale used in that example. In this section we prove a powerful impossibility theorem for arbitrary discrete scales that generalises this observation: there in fact exists no reasonable interval aggregation rule that is both an (ℓ, r)-rule and an (ℓ, w)-rule. The only exceptions are dictatorial (thus not "reasonable") rules, which simply return the interval reported by some fixed agent i⋆ (the dictator). Two agents. We first prove our impossibility result for the special case of n = 2 and then use an inductive argument to generalise to arbitrary (but finite) numbers of agents. Lemma 7. For n = 2 and any given discrete scale S, every (ℓ, r, w)-rule is a dictatorship. Proof. Take a discrete scale S, let m = |S|, let N = {1, 2}, and let F be a rule of the required kind. We write f for both fℓ and fr (which by Lemma 3 coincide). We will make repeated use of the fact that, due to F being (ℓ,w)-faithful, for any two profiles I and I ′ with w(Ii) = w(I ′ i ) for all i ∈ N we must have w(F(I)) = w(F(I ′ )). Let us first establish a useful fact. For any x, y ∈ S with x ⩽ y, due to unanimity, F([x, x], [x, y]) = [x, f(x, y)] and F([y, y], [x, y]) = [f(y, x), y]. In both cases, the first agent submits an interval of width 0 and the second agent one of width y-x. So the widths of the two outcomes must coincide: Now, for any pair (x, y), let us call i ∈ N a local dictator for (x, y) if it is the case that f(z1, z2) = zi whenever {z1, z2} ⊆ {x, y}. Local dictatorships are transitive: for x ⩽ y ⩽ z, if agent i is a local dictator for both (x, y) and (y, z), then she also is a local dictator for (x, z). To see this, suppose i = 1 (the case of i = 2 is analogous) and consider the profiles ([x, x], [y, z]) and ([y, y], [y, z]), which have the same width profile (0, z - y). The outcomes for these two profiles are [x, f(x, z)] and [y, y]. As the latter has width 0, we must have f(x, z) = x. Similarly, by considering profiles ([y, z], [x, x]) and ([y, z], [y, y]), we obtain f(z, x) = z. So agent 1 really is the local dictator for (x, z) as well. We now show that every pair (x, y) has a local dictator. We do so by induction on the number k of points in [x, y]. 2 Base case (k = 1): When k = 1, i.e., when x = y, then by unanimity every agent is a local dictator for (x, y). Induction step: Suppose there exists a local dictator for every pair (x, y) with |[x, y]| ⩽ k, for some fixed k ∈ {1, . . . ,m1}. We need to show that the same is true for k + 1. W.l.o.g., suppose f(x, y) ⩽ f(y, x). So, by Lemma 5, x ⩽ f(x, y) ⩽ f(y, x) ⩽ y. We distinguish three cases: - f(x, y) = f(y, x). Then equation (1) implies f(x, y) = f(y, x) = y-x 2 . This is only possible if z := y-x 2 ∈ S. By the induction hypothesis, the claim holds for (x, z) and (z, y). By considering the profiles ([x, z], [z, y]) and ([z, y], [x, z]), which both have the same profile of widths and thus must result in outcomes of the same width, the local dictators for both pairs must coincide. By the transitivity of local dictatorships, this common dictator must be the local dictator for (x, y) as well. - x ⩽ f(x, y) < f(y, x) ⩽ y and at least one of the weak inequalities is an equality. Then equation (1) implies that both are equalities, so agent 1 is a local dictator. - x < f(x, y) < f(y, x) < y. We will see that this is in fact impossible. Let z := f(x, y) and z′ := f(y, x). By the induction hypothesis, there are local dictators for all ordered pairs in {x, z, z′ , y}-except possibly (x, y). By the transitivity of local dictatorships, there must be a single local dictator i ruling all five of them. Suppose i = 1 (the case of i = 2 is analogous). Then F([x, x], [x, y]) = [x, z] and F([z, z], [x, y]) = [z, z]. As both profiles have the same width profile, we must have x = z, contradicting our assumption that x < z. As our case distinction is exhaustive, the inductive proof is complete: there must be a local dictator for every pair (x, y). Given that n = 2, for any three pairs (x, y), (y, z), (x, z) at least two must have the same local dictator. If this holds for (x, y) and (y, z), then all three pairs must have the same dictator due to transitivity; if it holds for (x, z) and (x, y) (analogously for (y, z)), then we can show that all three pairs must have the same dictator with a proof like the one employed to establish transitivity, by instead considering the profiles ([x, z], [x, x]) and ([x, z], [y, y]). To summarise, there must be a single (global) dictator for all possible intervals. Inductive lemma. The next lemma shows that, if we can design a rule of the required kind for n + 1 agents, then also for n agents. 3 We note that we prove this lemma for scales S with min(S) = 0 only (but we are going to be able to lift this restriction later on in our proof of Theorem 9). 2 Note how here we make use of the assumption that S is discrete, meaning that there are only finitely many points between x and y. 3 The proof of Lemma 8 has a similar structure to that of Lemma 6.8 in the PhD thesis of Tang [2010] used for a computersupported inductive proof of the Gibbard-Satterthwaite Theorem. Lemma 8. For any given n ⩾ 2 and any given scale S with min(S) = 0, if there exists a nondictatorial (ℓ, r, w)-rule for n + 1 agents, then also for n agents. Proof. Let n ⩾ 2 and let S be a scale with min(S) = 0. Suppose F is a nondictatorial (ℓ, r, w)-rule for n + 1 agents for this scale. By Lemma 4, we know that fℓ = fr = fw↾S holds for the component-aggregators of F. Let us use the letter f to refer to this function. For each i ∈ {1, . . . , n}, we define a function f ′ i : Sn → S with f ′ i (x) = f(x, xi). That is, we append a copy of xi at the end of the input profile and then query f on that extended point profile. Observe that each f ′ i is unanimous, because f is. By aggregating left and right endpoints using f ′ i we obtain an interval aggregation rule F ′ i . By construction, every such F ′ i is an (ℓ, r,w)-rule for n agents. We are done if we can show that at least one of the F ′ i (or equivalently: at least one f ′ i ) is nondictatorial. We first show that, in case a given f ′ i happens to be dictatorial, its dictator must be i, i.e., the agent whose ballot gets duplicated before querying f. Let i⋆ ∈ {1, . . . , n} be the dictator of f ′ i , meaning that f(x) = xi⋆ for every point profile x ∈ Sn+1 with xi = xn+1. For the sake of contradiction, suppose i⋆ ̸= i. As f is nondictatorial, there exists an x ∈ Sn+1 with f(x) ̸= xi⋆ (and thus xi ̸= xn+1). Suppose f(x) > xi⋆ (the proof for the case of f(x) < xi⋆ is entirely analogous). Now consider what happens when we let the agent amongst i and n + 1 who reported the lower number instead copy the ballot of the other agent. This new profile is x′ ∈ Sn+1 with x′i = x′n+1 = max{xi, xn+1} and x′j = xj for all other agents j (including i⋆ ). So x′ ⩾ x, and thus, by Lemma 6, we must have f(x′ ) ⩾ f(x). Putting everything together, we get f(x′ ) ⩾ f(x) > xi⋆ = x′i⋆ . But f(x′ ) > x′i⋆, together with the fact that x′ is a profile with x′i = x′n+1 , contradicts our assumption that i⋆ is the dictator of f ′ i . So we really must have i⋆ = i as claimed. Recall that we need to show that at least one f ′ i is nondictatorial. So, for the sake of contradiction, suppose that for every i ∈ {1, . . . , n} the component-aggregator f ′ i is dictatorial. (As shown just now, for each such function f ′ i the dictator of must then be i.) This means that agent n+1 can ensure that a given point is selected whenever at least one other agent proposes that point (she can ensure this by copying that other agent's ballot). We are going to show that this implies that agent n + 1 in fact is a dictator for f (which will provide the required contradiction). So consider an arbitrary point profile x ∈ Sn+1 . We need to show that f(x) = xn+1. - First, suppose x1 ⩽ xn+1. We use the values within x to construct an interval profile and apply F to that profile: To see that [0, xn+1] is indeed the only possible outcome, observe that agents 2 and n + 1 agree on the left endpoint being 0, while agents 1 and n + 1 agree on the right endpoint being xn+1. 4 The width profile corresponding to this interval profile is (x1, x2, . . . , xn+1) = x, while the width of the outcome is xn+1. So it must be the case that fw(x) = xn+1 and thus f(x) = xn+1. 4 Observe how here, and in the corresponding step of the next case in our case distinction, we rely on the assumption that n ⩾ 2. - Second, suppose x1 > xn+1. We again construct a profile of intervals and apply F to that profile: To see that this is correct, observe that agents 2 and n+1 agree on the left endpoint being 0, while agents 1 and n + 1 agree on the width being xn+1. The profile of right endpoints corresponding to this interval profile is x, so we obtain fr(x) = xn+1 and thus f(x) = xx+1. Thus, in both cases agent n + 1 can dictate the outcome of f for the arbitrarily chosen point profile x. As this contradicts our assumption of f being nondictatorial, we are done. General impossibility. We are now ready to prove our main result for this section. In a nutshell, we are going to use the inductive lemma we just proved to "spread" the impossibility for n = 2 to scenarios with arbitrary numbers of agents. This will establish the result for discrete scales that start at 0. To conclude the proof, we then exploit the fact that every discrete scale S is the image of some discrete scale S′ with min(S′ ) = 0 under some affine transformation. Theorem 9. For any given discrete scale S, every interval aggregation rule that is both an (ℓ, r)-rule and an (ℓ, w)-rule must be a dictatorship. Proof. We first prove the claim under the additional assumption that min(S) = 0. For n = 1, it follows directly from component-unanimity. The case of n = 2 is covered by Lemma 7. For any finite n > 2 the claim now follows by induction, with n = 2 serving as the base case and the contrapositive reading of Lemma 8 as the inductive step. Now suppose min(S) ̸= 0. Let b := min(S) and construct a second scale S′ = {x - b | x ∈ S }. Observe that min(S′ ) = 0 by construction, so the theorem holds for S′ . Now, for the sake of contradiction, suppose there exists a nondictatorial rule F for S that is both an (ℓ, r)-rule and an (ℓ, w)-rule. Let the corresponding component-aggregators be fℓ, fr, and fw. We define a rule F ′ for S′ in terms of its component-aggregators f ′ ℓ , f ′r , and f ′w as follows: By construction, F ′ is an (ℓ, r)-rule, an (ℓ,w)-rule, and nondictatorial. But we know that no such rule can exist for S′ ; so this is a contradiction and we are done. Discussion. This impossibility persists even for the simplest of discrete scales, such as S = {0, 1}. Interestingly though, if we add a mild restriction on profiles, then the impossibility can be circumvented for certain kinds of scales: Example 3. Let S = {0, 1, 5} and suppose agents cannot submit degenerate intervals. What is special about S is that every interval is uniquely identified by its width: only [0, 1] has width 1; only [1, 5] has width 4; only [0, 5] has width 5. Then, starting with the (ℓ, r)-median rule, we can define an equivalent (ℓ, w)-rule by using the profile of widths to recover the full profile of intervals, computing the outcome interval under the (ℓ, r)-median rule, and reading off its width. △ What about other representations? One immediate corollary of Theorem 9 is that, by Lemma 2 and given that (ℓ, r, m, w) ⊒ (ℓ, r, w), there also exists no nondicatorial rule that is both an (ℓ, r)-rule and an (m, w)-rule. ## 4 Characterisation Results: Continuous Scales The proof of our impossibility theorem applies to discrete scales only. But maybe the result itself still extends to other natural scales, such as S = [0, 1]? The brief answer is "no". In this section, we are going to show that there are reasonable rules for continuous scales that are faithful to both the (ℓ, r)- and the (ℓ, w)-representation, and fully characterise them. Continuity. Consider a continuous scale S and a representation γ = (γ1, . . . , γq) with components γk : I(S) → R. We say that a γ-rule F is continuous if all its componentaggregators fk : Rn → R are continuous in the standard mathematical sense. We are going to restrict attention to such continuous rules. This is a mild and reasonable requirement (indeed, all rules discussed in this paper are continuous). Cauchy's functional equation. In the proof of our characterisation theorem we are going to encounter Cauchy's functional equation [Cauchy, 1821]: Cauchy asked: For a given set S ⊆ R, which functions f : S → R satisfy equation (2) for all x, y ∈ S with (x+y) ∈ S? Clearly, every function f for which there exists an a ∈ R such that f(x) = a · x for all x ∈ S does. But are these the only solutions? It turns out that, yes, for certain choices of S these indeed are the only solutions. Examples include S = N or S = Q (while for S = R this is only the case under certain additional assumptions on f ). 5 We now prove a minor variant of these classical results for functions f that are continuous (rather than arbitrary) and that map into S (rather than R). Lemma 10. Let S be the standard continuous scale. Then a continuous function f : S → S satisfies f(x) + f(y) = f(x+y) for all x, y ∈ S with (x+y) ∈ S if and only if there exists an a ∈ [0, 1] such that f(x) = a · x for all x ∈ S. Proof. Let a := f(1). Note that a ∈ [0, 1], given that f maps into S. From f(0)+f(1) = f(0+1) it follows that f(0) = 0. Now take an arbitrary rational number q = α/β ∈ S\{0} with α, β ∈ N. From repeated application of Cauchy's equationfirst to α- and then to β-many "copies" of f(1/β)-we get f(α/β) = α · f(1/β) and f(1) = β · f(1/β). Thus, f(α/β) = α · f(1)/β and f(q) = a · q. As q was chosen arbitrarily, this proves the claim for every x ∈ S ∩ Q. For x ∈ S \ Q, consider any sequence (xn) of rational numbers in S ∩ Q with limit x. By continuity of f, f(x) = limn→∞ f (xn) = limn→∞ a·xn = a·x, so we are done. Weighted averages. We call an (ℓ, r)-rule F, defined by its component-aggregators fℓ and fr, an (ℓ, r)-weighted averaging rule if there exist constants a1, . . . , an ∈ [0, 1] with a1 + · · ·+an = 1 such that fℓ(x) = fr(x) = a1 ·x1+· · ·+an ·xn for every point profile x ∈ Sn . 5 Consult Small [2007] for a modern exposition of these results. Observe that every (ℓ, r)-weighted averaging rule is also an (ℓ, w)-rule. Indeed, the width of the collective interval under F can be obtained by the exact same weighted averaging operation. Remarkably, (ℓ, r)-weighted averaging rules are also the only continuous rules that are faithful to both representations, i.e., that are (ℓ, r,w)-rules. We first prove this for the special case of the standard continuous scale S = [0, 1]. 6 Lemma 11. For the standard continuous scale S, every continuous (ℓ, r, w)-rule is an (ℓ, r)-weighted averaging rule. Proof. Let S = [0, 1] and let F : I(S)n → I(S) be any continuous (ℓ, r, w)-rule with component-aggregators fℓ, fr, and fw. What is special about this scale is that the domain of fw is exactly S, so fw = fw↾S. By Lemma 4, we thus get fℓ = fr = fw; we use f to refer to any of these three functions. Note that f is a function of type f : Sn →S. If x is the left endpoint of an interval and y its width, then x+y is its right endpoint. This relationship must be respected for the n intervals fed to F and the single interval it returns. So suppose F is applied to a profile of intervals with left endpoints (x1, . . . , xn), widths (y1, . . . , yn), and right endpoints (x1 + y1, . . . , xn + yn). Then applying f to each of these three profiles must return values that also respect the proper relationship between left endpoint, width, and right endpoint: This generalisation of Cauchy's functional equation must be satisfied for all (x1, . . . , xn), (y1, . . . , yn) ∈ Sn for which it is the case that (x1 + y1, . . . , xn + yn) ∈ Sn . Let us write (0-i, xi) for the vector of length n consisting solely of 0's, except that its ith element is equal to xi. Now consider a scenario in which everyone except for agent i submits the degenerate interval [0, 0]. Then equation (3) reduces to the following family of equations (one for each i ∈ N): Each equation in (4) is an instance of Cauchy's functional equation in its standard form, applied to a function f(0-i, ) taking a single variable as input. Each such function is a mapping from S to S. So Lemma 10 applies and allows us to infer that, for each i ∈ N, there exists an ai ∈ [0, 1] such that the following is true for all z ∈ S: Now consider an arbitrary (z1, . . . , zn) ∈ Sn . If we rewrite each zi as a sum of the form 0 + · · · + 0 + zi + 0 + · · · + 0, with zi in the ith position, and if we then apply f, we obtain: Repeatedly applying equation (3), and then (5), yields: As f is unanimous (given that F is component-unanimous), and as we need to account for cases where z1 = · · · = zn, we must have a1 + · · · + an = 1. So F, defined in terms of f, really must be an (ℓ, r)-weighted averaging rule. 6 Owing to the fact that points in [0, 1] can be interpreted as probabilities, Lemma 11 is reminiscent of results on probabilistic opinion pooling with general agendas by Dietrich and List [2017]. Generalising from the standard continuous scale [0, 1] to arbitrary continuous scales S is possible by exploiting the fact that any such S can be obtained as the image of [0, 1] under some affine transformation. We formulate this fact as a characterisation result for the family of weighted averaging rules: Theorem 12. For any continuous scale S, a continuous interval aggregation rule is both an (ℓ, r)-rule and an (ℓ, w)-rule if and only if it is an (ℓ, r)-weighted averaging rule. Proof. As previously noted, every (ℓ, r)-weighted averaging rule is is both an (ℓ, r)-rule and an (ℓ,w)-rule. For the other direction, consider an arbitrary continuous scale S. W.l.o.g., assume |S| > 1. Let a := max(S) - min(S) > 0 and b := min(S). Then we can generate S as follows: For the sake of contradiction, suppose there exists a continuous (ℓ, r,w)-rule F on S (with component-aggregators fℓ, fr, and fw) that is not a weighted averaging rule. Construct an (ℓ, r, w)-rule F ′ on [0, 1] in terms of f ′ ℓ , f ′r , and f ′w : By construction, F ′ is a continuous (ℓ, r, w)-rule, yet it is not a weighted averaging rule (as otherwise F would be as well). But this contradicts Lemma 11, so we are done. Note that the only (ℓ, r)-weighted averaging rule that is anonymous (i.e., treats all agents symmetrically) has ai = 1/n for all i ∈ N. So if we require anonymity, this is the unique continuous rule that is both an (ℓ, r)-rule and an (ℓ, w)-rule. ## 5 Conclusion We introduced the notion of representation-faithfulness into the study of interval aggregation and found that the choice of representation heavily influences the aggregation rules we can design: for discrete scales it is impossible to define a nondictatorial rule that is simultaneously faithful to two natural representations, while for continuous scales only weighted averaging rules meet this requirement. The extent to which the latter should be interpreted as a positive result is open to debate. On the one hand, taking (weighted) averages is often used in practice and has been argued for in cognitive psychology [Yaniv, 1997] and risk analysis [Ferson and Kreinovich, 2001]. On the other hand, it is well-understood in social choice theory that averages tend to be less well-behaved than medians [Black, 1948; Moulin, 1980], and this also applies to interval aggregation [Farfel and Conitzer, 2011]. Our work paves the way to the investigation of several questions for future research. A natural first direction would be the study of other representations (e.g., involving components such as volume, counting the number of points in a finite interval, which subtley differs from an interval's width). Another direction of interest concerns restricted domains (cf. the constraints on the input in Example 3). ## Acknowledgments This research has been partly supported by NWO Vici grant 639.023.811 ("Collective Information"). Zoi Terzopoulou is a fellow of the Paris Region Fellowship Programme, supported by the Paris Region, which is a project that has received funding from the European Union's Horizon 2020 research and innovation programme under Marie SkłodowskaCurie grant agreement No. 945298-ParisRegionFP. We are grateful to Simon Rey for pointing us to Cauchy's functional equation, and we would like to thank several anonymous reviewers for their helpful feedback. ## References 1. [Aczél and Wagner, 1980] János Aczél and Carl Wagner. A characterization of weighted arithmetic means. SIAM Journal on Algebraic Discrete Methods, 1(3):259-260, 1980. 2. [Arrow et al., 2002] Kenneth J. Arrow, Amartya K. Sen, and Kotaro Suzumura, editors. Handbook of Social Choice and Welfare, volume 1. Elsevier, 2002. 3. [Black, 1948] Duncan Black. On the rationale of group decision-making. Journal of Political Economy, 56(1):23- 34, 1948. 4. [Brandt et al., 2016] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016. 5. [Cariani et al., 2008] Fabrizio Cariani, Marc Pauly, and Josh Snyder. Decision framing in judgment aggregation. Syn- these, 163(1):1-24, 2008. 6. [Cauchy, 1821] Augustin Louis Cauchy. Cours d'Analyse de l' École Royale Polytechnique. I. re Partie: Analyse Algébrique. L'Imprimerie Royale, Paris, 1821. 7. [Dietrich and List, 2016] Franz Dietrich and Christian List. Probabilistic opinion pooling. In Alan Hájek and Christo- pher Hitchcock, editors, The Oxford Handbook of Proba- bility and Philosophy. Oxford University Press, 2016. 8. [Dietrich and List, 2017] Franz Dietrich and Christian List. Probabilistic opinion pooling generalized. Part one: Gen- eral agendas. Social Choice and Welfare, 48(4):747-786, 2017. 9. [Dietrich, 2016] Franz Dietrich. Judgment aggregation and agenda manipulation. Games and Economic Behavior, 95:113-136, 2016. 10. [Dubois and Prade, 1993] Didier Dubois and Henri Prade. Fuzzy numbers: An overview. In Didier Dubois, Henri Prade, and Ronald R. Yager, editors, Readings in Fuzzy Sets for Intelligent Systems, pages 112-148. 11. Morgan Kauf- mann, 1993. 12. [Farfel and Conitzer, 2011] Joseph Farfel and Vincent Conitzer. Aggregating value ranges: Preference elicitation and truthfulness. Autonomous Agents and Multiagent Systems, 22(1):127-150, 2011. 13. [Ferson and Kreinovich, 2001] Scott Ferson and Vladik Kreinovich. Representation, elicitation, and aggregation of uncertainty in risk analysis-from traditional probabilistic techniques to more general, more realistic approaches: A survey. Technical Report UTEP-CS-01-33, University of Texas at El Paso, 2001. 14. [Marquis and Schwind, 2014] Pierre Marquis and Nicolas Schwind. Lost in translation: Language independence in propositional logic-Application to belief change. Artifi- cial Intelligence, 206:1-24, 2014. 15. [McConway, 1981] Kevin J. McConway. Marginalization and linear opinion pools. Journal of the American Sta- tistical Association, 76(374):410-414, 1981. 16. [Moulin, 1980] Hervé Moulin. On strategy-proofness and single peakedness. Public Choice, 35(4):437-455, 1980. 17. [Pirlot and Vincke, 1997] Marc Pirlot and Philippe Vincke. Semiorders: Properties, Representations, Applications. Springer, 1997. 18. [Rasch, 2000] Bjørn Erik Rasch. Parliamentary floor voting procedures and agenda setting in Europe. Legislative Stud- ies Quarterly, 25(1):3-23, 2000. 19. [Small, 2007] Christopher G. Small. Functional Equations and How to Solve Them. Springer, 2007. 20. [Stone, 1961] Mervyn Stone. The opinion pool. The Annals of Mathematical Statistics, 32(4):1339-1342, 1961. 21. [Tang, 2010] Pingzhong Tang. Computer-Aided Theorem Discovery: A New Adventure and its Application to Eco- nomic Theory. PhD thesis, Hong Kong University of Sci- ence and Technology, 2010. 22. William Thomson. On the axiomatic method and its recent applications to game theory and re- source allocation. Social Choice and Welfare, 18(2):327- 386, 2001. 23. [UFM, 2007] UFM. Ministerial Order on the Grad- ing Scale and Other Forms of Assessment of Study Programmes Offered under the Ministry of Higher Education and Science (the Grading Scale Order). Danish Ministry of Higher Education and Science (UFM), 2007. Available at https://ufm.dk/en/ education/the-danish-education-system/ grading-system/. Site visited on 7 January 2022. 24. [Yaniv, 1997] Ilan Yaniv. Weighting and trimming: Heuris- tics for aggregating judgments under uncertainty. Or- ganizational Behavior and Human Decision Processes, 69(3):237-249, 1997.