TL;DR
This paper explores how the way we represent intervals (e.g., by their endpoints or by their start point and duration) affects our ability to aggregate them. They prove that for discrete scales, it's impossible to create fair aggregation rules that are consistent across different representations, while for continuous scales, only weighted averaging rules work.
What Problem Does This Paper Address?
When multiple agents need to agree on a single interval (like a meeting time or a range of values), we often use aggregation rules to combine their individual intervals. However, the way an interval is described can vary. For instance, one might think of an interval by its minimum and maximum values (endpoints), while another might consider its starting point and its length (width). This paper investigates whether aggregation rules that work well for one representation can also work for another, and what the implications are if they don't. The core problem is understanding how the "framing" of interval data impacts the design and fairness of aggregation mechanisms, drawing parallels to social choice theory.
Methods
The authors introduce the concept of "representation-faithfulness," meaning an aggregation rule can be defined using separate "local aggregators" for each component of a chosen representation. They focus on two key representations:
- Endpoint Representation: Using the left (minimum) and right (maximum) endpoints.
- Start-Width Representation: Using the left endpoint and the interval's width.
They then analyze rules that are faithful to both representations simultaneously. For discrete scales, they use a combination of inductive proofs and specific lemmas (like those establishing dictatorship for two agents) to show impossibility results. For continuous scales, they leverage properties of Cauchy's functional equation and continuity to characterize the rules that are faithful to both representations, identifying them as weighted averaging rules.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Representation Framing Matters: The way an interval is described isn't just a cosmetic choice; it fundamentally constrains what aggregation rules are possible and fair.
- Discrete vs. Continuous Scales: The mathematical properties of the underlying scale (discrete vs. continuous) lead to drastically different outcomes regarding representation-faithfulness.
- Impossibility on Discrete Scales: For discrete scales, there's a strong trade-off. You generally can't have a fair (non-dictatorial) aggregation rule that works consistently whether you think of intervals by their endpoints or by their start point and width. The only rules that satisfy both are dictatorships, where one agent's input always determines the outcome.
- Weighted Averages on Continuous Scales: On continuous scales, the situation is much more flexible. Rules that are faithful to both endpoint and start-width representations are precisely the weighted averaging rules. This means the aggregated interval's components are calculated as a weighted average of the individual agents' components.
- Anonymity Implies Unique Rule: If we add the requirement of anonymity (all agents are treated symmetrically) to continuous scales, there's a unique rule: the simple average.
Key Results
- Impossibility Theorem for Discrete Scales: For any discrete scale, any interval aggregation rule that is faithful to both the (left, right) endpoint representation and the (left endpoint, width) representation must be a dictatorship. This holds even for simple scales like {0, 1}.
- Characterization for Continuous Scales: For any continuous scale, a rule is faithful to both the (left, right) endpoint representation and the (left endpoint, width) representation if and only if it is a weighted averaging rule.
- Lemma 11: For the standard continuous scale [0, 1], any continuous (l, r, w)-rule is an (l,r)-weighted averaging rule.
Limitations and Future Work
- Discrete Scale Limitations: The impossibility results for discrete scales are quite strong, essentially ruling out fair aggregation rules that are representation-agnostic. The authors note that mild restrictions on input profiles could circumvent this for certain scales, but the general impossibility remains.
- Future Directions: The authors suggest exploring other representations (e.g., volume, number of points in finite intervals) and investigating restricted domains for intervals. They also point out that while weighted averages are characterized for continuous scales, social choice theory suggests medians might be more robust, hinting at further research into the trade-offs between different types of aggregation rules.
Summary updated