What aggregation rules can be classified as logical concepts?

This paper utilizes methods from universal algebra and the theory of closed classes of discrete functions to provide a complete classification of aggregation rules characterized by nontrivial symmetric classes of invariant sets and a logical nature.

The Gist

The Big Question: What Makes a Voting Rule "Logical"?

Imagine you are trying to build a machine that takes in the opinions of a group of people and spits out a single group decision. In the world of math and economics, this is called an aggregation rule (like a voting system).

For a long time, famous theorems (like Arrow's Impossibility Theorem) have told us: "If you want a fair voting system that works for any group of people, you're out of luck. The only way to get a result is to let one person (a dictator) decide everything."

But this paper asks a different question: What if we restrict the types of opinions people can have? What if we only look at specific, "sensible" groups of opinions? The author wants to find out which voting rules are "logical."

In this paper, a rule is "logical" if it treats every option (Candidate A, B, C) exactly the same. It doesn't have a secret favorite. It doesn't care if the options are called "Pizza" or "Burgers"; it only cares about the structure of the choices. If you swap the names of the options, the rule should swap its output in the exact same way.

The Analogy: The "Fair Judge" vs. The "Biased Judge"

Think of a Logical Aggregation Rule as a Fair Judge in a courtroom.

• The Fair Judge: If the defendant is named "Bob," the judge follows the law. If the defendant is renamed "Steve," the judge follows the exact same law. The judge doesn't care about the name; they care about the pattern of the evidence.
• The Biased (Non-Logical) Judge: This judge secretly hates the name "Bob." Even if the evidence is identical, they rule differently just because of the name.

The paper tries to find all the "Fair Judges" that can exist when we limit the types of cases (the "restricted domains") they have to handle.

The Setup: The "Rock-Paper-Scissors" of Choices

The author focuses on the simplest possible scenario:

1. The Options: A list of things to choose from (like candidates).
2. The Voters: People who pick between pairs of options (e.g., "I prefer A over B").
3. The Rule: A machine that takes everyone's pairwise choices and decides the group's winner.

The author uses a tool from Universal Algebra (a branch of math that studies patterns and structures) to classify these rules. Think of this tool as a Lego Master. Instead of looking at the specific colors of the bricks (the specific names of candidates), the Lego Master looks at how the bricks snap together (the logical structure).

The Main Discovery: The "Big Four"

The paper proves that if you have a large enough group of options (at least 5), there are only four types of "Logical" voting rules that work on these restricted, sensible groups.

If a rule is "logical" (fair and structure-based), it must be one of these:

1. The Dictator (Rule $\delta$): One person's vote counts for everything. (This is the "boring" logical rule).
2. The Majority (Rule $\mu$): The option that wins the most pairwise votes wins. (This is the standard democratic rule).
3. The "Odd Man Out" (Rule $\lambda$): Imagine a game where you count how many people voted for an option. If an odd number of people (who aren't "dummies") voted for it, it wins. It sounds weird, like a children's counting-out game ("Eenie, meenie, miny, moe"), but mathematically, it's a valid logical structure.
4. The "Special Pair" (Rule $\nu$): A slightly more complex version where two specific voters have a special relationship, but the rule still treats all options fairly.

The Big Takeaway:
The paper says: "If you want a voting rule that is truly fair (logical) and works on sensible groups of opinions, you are stuck with these four options. You can't invent a new, complex, magical voting system that fits this description."

Why Does This Matter?

The author compares this to Logic itself.

• In logic, you have rules like "If A is true and B is true, then C is true." These rules work no matter what A, B, and C are.
• In voting, a "Logical Rule" is one that works no matter what the candidates are named.

The paper shows that fairness (neutrality) is a very strict requirement. It forces voting systems to be very simple. If you try to make a voting system that is too complex or tries to be "smart" in a way that breaks the symmetry, it stops being "logical" and starts behaving like a dictatorship or a broken machine.

The "Gotchas" (Where the Math Gets Tricky)

The author notes that this "Big Four" list only works if you have 5 or more options.

• If you have 2 options: It's too simple; almost anything goes.
• If you have 3 or 4 options: The math gets messy. You can create weird, non-fair rules that look fair because the group is so small. It's like a game of Rock-Paper-Scissors where the rules change depending on who is playing.

Summary in a Nutshell

Imagine you are designing a robot to decide what movie the class should watch.

• The Goal: The robot must be fair. It shouldn't care if the movie is called "The Matrix" or "The Matrix 2."
• The Finding: The author proves that if you want your robot to be truly fair and handle a decent number of movie choices, your robot's brain can only be programmed in four specific ways.
  1. Listen to the class president (Dictator).
  2. Listen to the majority (Majority Rule).
  3. Count votes in a specific "odd-number" pattern (The Paradoxical Rule).
  4. A slightly tweaked version of the above.

Any other way of programming the robot will either be unfair (biased toward specific movie titles) or will fail to work consistently. The paper uses advanced math to prove that true fairness is rare and highly structured.

Technical Summary

1. Problem Statement

The paper addresses a fundamental question in Social Choice Theory: Which aggregation rules possess a "logical" nature?

While standard impossibility theorems (like Arrow's Theorem) suggest that non-dictatorial aggregation rules are generally impossible under broad conditions, the author seeks to identify a specific class of rules that are "logical." Drawing on Alfred Tarski's definition of logical notions (notions invariant under all permutations of the universe of discourse), the author posits that an aggregation rule is logical if it operates effectively on non-trivial, symmetric restricted domains.

The core problem is to characterize aggregation rules $f: C^n \to C$ that preserve a symmetric class of non-trivial invariant sets (domains of preferences), distinguishing them from "trivial" rules (which preserve only empty or inconsistent sets) and "dictatorial" rules.

2. Methodology

The author employs a Universal Algebraic approach, specifically utilizing the theory of closed classes of discrete functions (clones) and Post's classification theorem.

• Model Definition: The paper defines a model of individual choice as a quadruple $(A, B, C, *)$, where $A$ is the set of alternatives, $B$ is the set of conditions (e.g., pairs of alternatives), $C$ is the set of choice functions, and $*$ embeds the permutation group of $A$ into the permutation group of $B$.
• Logicality Criterion: An aggregation rule is deemed "logical" if there exists a symmetric class $\mathcal{D}$ of non-trivial invariant sets $D \subseteq C$ such that the rule preserves every set in $\mathcal{D}$.
  • Trivial sets are defined as those where all functions coincide on a specific subset of conditions (essentially fixing the outcome regardless of the rule).
  • Symmetric sets are those closed under permutations of the alternatives.
• Reduction to 2-Clones: For the specific case of local aggregation rules (where the collective choice on a pair depends only on individual choices on that pair), the author establishes a bijection between aggregation rules and conservative 2-functions (functions defined on pairs of alternatives that return one of the inputs).
• Algebraic Tools: The proof relies on:
  • Clones: Sets of functions closed under composition and containing projections.
  • Symmetric Clones: Clones invariant under permutations of the domain.
  • Post's Lattice: The classification of Boolean function clones, extended to the context of $k$-valued logic and 2-functions.

3. Key Contributions and Results

A. The Simplest Case: $\mathcal{C}_2(A)$

The paper focuses on the model where $B$ is the set of all 2-element subsets of $A$ (pairs), and $C$ is the set of all choice functions on these pairs. The main result is Theorem 1, which provides a complete classification for finite sets $A$ where $5 \le |A| < \omega$.

Theorem 1 (Equivalence Conditions):
For a local aggregation rule $f$ on $\mathcal{C}_2(A)$ with $|A| \ge 5$, the following are equivalent:

1. $f$ has a non-trivial symmetric rational class of invariant sets.
2. $f$ has a non-trivial symmetric class of invariant sets (i.e., $f$ is logical).
3. $f$ is neutral (invariant under permutations of alternatives).
4. $f$ is invariantly equivalent to one of four specific rules:
   • $\delta$: Dictatorship (projection).
   • $\mu$: Majority rule.
   • $\nu$: A rule based on a specific decisive coalition structure (agents 2 and 3 vs. agent 1).
   • $\lambda$: A rule resembling a "counting-out" game (odd number of non-dummy agents).

Key Insight: The existence of a non-trivial symmetric invariant domain forces the aggregation rule to be neutral. Conversely, all local neutral rules fall into one of these four equivalence classes regarding their invariant sets.

B. Classification via Universal Algebra (Theorem 2)

The proof relies on Theorem 2, which classifies symmetric conservative 2-clones on a set $A$ ($|A| \ge 5$).

• Any such clone is either a free extension or a dependent extension of specific Boolean clones ($O_1, D_1, D_2, L_4, A_4, C_4$).
• The "logical" rules correspond specifically to the self-dual Boolean clones ($O_1, D_1, D_2, L_4$), which map to the four rules ($\delta, \nu, \mu, \lambda$) mentioned in Theorem 1.

C. Boundary Conditions and Counterexamples

The paper rigorously analyzes cases where the classification fails:

• $|A| < 5$: The theorem does not hold.
  • For $|A|=2$, there are no non-trivial sets.
  • For $|A|=3$ and $|A|=4$, non-neutral local rules can possess symmetric non-trivial invariants (counterexamples are constructed using specific Cayley tables).
• Infinite Sets: The results differ for infinite $A$ (referenced as [27]).
• Higher Order ($r > 2$): For choice functions on subsets of size $r > 2$, local aggregation rules generally do not have symmetric invariants (referencing [7, 16]), suggesting the "logical" nature is specific to pairwise interactions in this context.

4. Significance and Implications

1. Bridging Logic and Social Choice: The paper successfully formalizes the intuitive notion of "logical" aggregation rules by linking them to neutrality and symmetry. It demonstrates that logicality in social choice is not just a philosophical concept but a mathematically rigorous property defined by the preservation of symmetric, non-trivial domains.
2. Refining Impossibility Theorems: While Arrow's Theorem states that only dictatorial rules work for rational preferences, this paper shows that if we relax the requirement to "rationality" and focus on "logicality" (symmetric invariance), a small, well-defined class of non-dictatorial rules (Majority, $\nu$, $\lambda$) emerges as valid.
3. Algebraic Characterization: The work provides a powerful method for classifying aggregation rules using Post's classification and clone theory. It reduces complex social choice problems to the classification of closed classes of discrete functions.
4. Paradoxical Rules: The analysis highlights that "logical" rules can include seemingly paradoxical mechanisms (like rule $\lambda$, which acts like a children's counting-out game), suggesting that the mathematical definition of logicality is broader than intuitive fairness.

Conclusion

Polyakov concludes that for finite sets of alternatives with cardinality 5 or greater, logical aggregation rules are precisely the local and neutral rules. These rules are structurally limited to four equivalence classes derived from specific self-dual Boolean functions. This result offers a "possibility theorem" within a restricted but logically significant domain, contrasting with the broader impossibility results of classical social choice theory. The universal algebraic framework presented offers a promising path for extending these results to more complex models, though the author notes significant combinatorial challenges remain for higher-order choice functions.