📈 economics

Localizing Preference Aggregation Conflicts: A Graph-Theoretic Approach Using Sheaves

This paper introduces a graph-theoretic framework using discrete sheaves to diagnose and localize inconsistencies in preference aggregation by identifying specific voter pairs that fail to cohere through an Obstruction Locus and Incompatibility Index, offering a purely ordinal alternative to linearization methods like HodgeRank.

Original authors: Karen Sargsyan

Published 2026-07-16

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Karen Sargsyan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, jigsaw puzzle, but instead of one box, you have a hundred different people, each holding a small, overlapping piece of the picture. Some people only see the sky, others only see the grass, and a few see where the sky meets the grass. The goal is to snap all these pieces together to see the whole image. This is the heart of preference aggregation, a field in social science that asks: "How do we combine many different opinions into one single, fair decision?"

For a long time, scientists knew this was tricky. If Person A likes Apples more than Bananas, and Person B likes Bananas more than Cherries, you might think Person A must like Apples more than Cherries. But sometimes, logic breaks down, and you get a loop where everyone prefers the next item in a circle, making a single "best" choice impossible. This is known as a paradox. Usually, mathematicians try to fix this by turning opinions into numbers (like giving apples a score of 9 and bananas a 7) and adding them up. But this paper argues that turning opinions into numbers can hide the real problem. Instead, the authors suggest looking at the connections between people as a map, treating the whole situation like a tangled web of promises that need to be kept.

The Map of Mismatched Promises

In this paper, Karen Sargsyan introduces a new way to look at these messy voting situations using a mathematical tool called a sheaf. Think of a sheaf not as a complex equation, but as a "promise tracker." Imagine a group of friends planning a trip. Each friend has a list of places they want to visit (their preferences). When two friends share a destination, they make a promise to agree on which one is better.

The paper builds a map where every friend is a dot (a vertex) and every pair of friends who share a destination is a line connecting them (an edge). The "sheaf" is the system that checks if the promises on these lines actually match up.

The "Obstruction Locus": Finding the Knots

The authors' main discovery is a way to pinpoint exactly where the group is failing to agree. They call this the Obstruction Locus.

Imagine you are trying to braid three strands of hair. If the middle strand gets crossed over the wrong way, the whole braid falls apart. In the paper's language, the "Obstruction Locus" is the specific spot where the hair got crossed. Instead of just saying, "Hey, this braid is messy," this method points a finger and says, "The knot is right here, between Friend A and Friend B."

They measure this messiness with something called the Incompatibility Index. It's simply a count of how many pairs of friends are arguing about the things they both see. If the index is zero, everyone agrees on their shared items. If it's high, there are lots of arguments.

Why Not Just Add Up Scores?

The paper argues against a popular method called HodgeRank, which turns preferences into numbers and flows them like water through pipes. While that method is good at finding that there is a problem, it's like a weather report that says "it's raining somewhere" without telling you where to put your umbrella.

The new method stays purely "ordinal," meaning it only cares about the order (A is better than B), not the intensity (A is much better than B). This keeps the data honest. The authors show that by staying in the world of simple rankings, they can locate the exact edges of the map where the logic breaks, rather than just seeing a blurry cloud of inconsistency.

The Magic of Merging: When Friends Become One

The most fascinating part of the paper happens when the group decides to merge. Imagine two friends, Alice and Bob, decide to vote as a single unit. In the old way of thinking, you might just average their votes. But the authors use a "pushforward" operation to see what happens to the promises when Alice and Bob become one person.

Here is the twist: Sometimes, Alice and Bob might not be arguing with anyone else, but when they merge, their combined rules create a logical loop that makes it impossible to have a single ranking.

The paper demonstrates this with a clever trick using a constraint digraph (a map of "must come before" rules).

Alice says: "Apples must come before Bananas."
Bob says: "Bananas must come before Cherries."
But wait, if they also have a hidden rule that "Cherries must come before Apples," the moment you merge them, you get a cycle: Apples > Bananas > Cherries > Apples.

The paper shows that this cycle creates an empty stalk. In plain English, the "slot" where the merged person's opinion should live becomes empty because no single opinion can satisfy all the rules. The conflict didn't disappear; it just moved from the line between two people to the person themselves.

What the Experiments Showed

The authors didn't just theorize; they ran thousands of computer simulations to see how this works in the real world.

Random Chaos: When they simulated groups of 200,000 people with random preferences, they found that the number of arguments (the Incompatibility Index) grew predictably with the number of connections. More connections meant more chances to argue.
The Smooth Transition: They used a model called the Mallows model to slowly shift a group from total chaos to total agreement. They found that as the group got closer to agreeing, the number of arguments didn't just drop suddenly; it smoothed out, giving a clear picture of how consensus forms.
Speed: They proved their new method is incredibly fast. While older methods would take minutes or hours to check if a group of 12 people could agree, their "constraint digraph" method did it in less than a millisecond.

The Bottom Line

This paper doesn't claim to have solved the problem of voting forever. Instead, it gives us a better flashlight. It shows us that when a group can't agree, the problem isn't always a big, global mess. Sometimes, the problem is a tiny, specific knot between two people, or a hidden loop that only appears when we try to merge groups together.

By mapping these conflicts exactly where they happen, the authors provide a tool to diagnose why a decision fails. Whether it's a committee trying to pick a project, a search engine combining results, or friends deciding where to eat, this method helps us find the exact spot where the logic breaks, so we can fix it before the whole plan falls apart.

Technical Summary: Localizing Preference Aggregation Conflicts via Discrete Sheaves

Problem Statement
The paper addresses the challenge of aggregating ordinal preference data from multiple sources that possess only partial visibility of the alternatives. Unlike traditional social choice problems where the goal is to resolve legitimate disagreements among voters, this work focuses on data fusion: determining whether partial rankings from overlapping sources can be combined into a single, coherent global ranking. A conflict arises not merely from differing opinions, but from inconsistencies where sources disagree on the alternatives they share. The central problem is to diagnose where these inconsistencies occur within the interaction structure and to determine if a global solution exists, particularly when pairwise agreements might mask deeper structural impossibilities.

Methodology
The authors propose a discrete sheaf-theoretic framework that operates directly on ordinal data without linearization (unlike HodgeRank).

Discrete Order Sheaf:
- The system is modeled as a graph $G=(V, E)$ where vertices represent voters (sources) and edges represent overlaps (shared alternatives).
- A Discrete Order Presheaf is defined where:
  - Vertex stalks ( $F_v$ ): The set of all total orders on the alternatives visible to voter $v$ .
  - Edge stalks ( $F_e$ ): The set of all total orders on the intersection of alternatives visible to both endpoints of an edge.
  - Restriction maps: Maps that restrict a local total order to the subset of alternatives shared with a neighbor.
- A preference profile is treated as a 0-cochain (an assignment of a specific local order to each vertex).
Obstruction Locus ( $\Omega_1$ ) and Incompatibility Index:
- The Obstruction Locus $\Omega_1(\sigma)$ is defined as the set of edges where the restricted local orders of adjacent voters disagree ( $\sigma_u|_{A_{uv}} \neq \sigma_v|_{A_{uv}}$ ).
- The Incompatibility Index $|\Omega_1|$ is the cardinality of this set.
- Crucially, this metric provides localization: it identifies specific voter pairs that fail to cohere, rather than providing a single global scalar of inconsistency.
Pushforward and Global Solvability:
- To address whether a global ranking exists, the authors utilize the pushforward operation ( $\pi_*$ ) under a graph quotient map (e.g., merging voters).
- The pushforward sheaf $\pi_*F$ on a merged vertex $v'$ contains the set of total orders on the union of alternatives that are compatible with all original voters in the preimage.
- Empty Stalks: If the constraints from the merged voters are contradictory, the stalk at the merged vertex becomes empty ( $\emptyset$ ). This signifies a local impossibility even if no pairwise edge was obstructed in the original graph.
- Algorithmic Implementation: The pushforward is computed efficiently using a constraint digraph. Constraints from local orders are aggregated into a directed graph. If this graph contains a directed cycle, the constraints are contradictory, and the stalk is empty. This cycle detection runs in polynomial time ( $O(|A|^2 \cdot |P|)$ ), avoiding the factorial complexity of enumerating permutations.

Key Contributions

Formalization of the Discrete Order Sheaf: A framework for preference profiles that treats ordinal data as a cellular sheaf, avoiding the loss of combinatorial structure inherent in linearization methods.
Definition of the Obstruction Locus: Introduction of $\Omega_1$ and the Incompatibility Index to quantify and localize pairwise conflicts. The authors clarify that while $|\Omega_1|$ is not a cohomological invariant, it serves as a precise "localizer" of conflict, distinct from global topological invariants like the dimension of harmonic spaces in HodgeRank.
Pushforward Mechanism for Merging: Development of a sheaf-theoretic pushforward that models voter merging. This reveals that conflicts can transform from edge-based disagreements into empty stalks (local impossibilities) upon coarsening, a phenomenon undetectable by simple pairwise checks.
Polynomial-Time Algorithm: Implementation of the constraint digraph approach to detect empty stalks, offering a dramatic speedup over naive enumeration for determining global solvability.

Experimental Results
The authors validate the framework through computational experiments:

Basic Examples: The framework correctly identifies known paradoxes (e.g., Condorcet cycles) and calculates $|\Omega_1|$ for various graph topologies (e.g., $K_4$ , $C_3$ ).
Stochastic Interpolation (Mallows Model): Using the Mallows model to generate preference profiles with varying consensus levels, the study shows that the mean Incompatibility Index $|\Omega_1|$ responds smoothly and predictably to changes in the dispersion parameter.
Consistency Rates: Experiments on random profiles demonstrate that global consistency (existence of a global section) is governed by the number of voters in a connected component (specifically $(1/|A|!)^{|V|-1}$ for full visibility), whereas the mean Incompatibility Index scales with the number of edges.
Scaling: The constraint digraph algorithm scales efficiently. For 12 alternatives, the digraph approach is approximately 149,000 times faster than naive enumeration.
The "Invisible" Obstruction: A specific example (Appendix D) demonstrates a profile where $|\Omega_1| = 0$ (all pairwise overlaps are consistent) yet merging all sources results in an empty stalk. This confirms that pairwise checks are insufficient for detecting global fusion impossibilities.

Significance and Claims
The paper claims that the sheaf-theoretic approach offers two distinct advantages over existing methods like HodgeRank:

Localization: It identifies which specific interactions (edges) are responsible for inconsistencies, rather than just reporting the existence of a global obstruction.
Functoriality: The pushforward operation allows for the consistent tracking of conflicts as the system is coarsened (e.g., merging voters). It captures the transition of distributed edge conflicts into localized impossibilities (empty stalks), providing a certificate for global solvability that pairwise checks cannot provide.

The authors explicitly state that the framework is not a replacement for cohomological invariants but a tool for localizing and diagnosing the specific structural failures in preference aggregation. They emphasize that while higher-order obstructions ( $\Omega_k$ for $k \ge 2$ ) vanish trivially on graphs due to the nature of the Čech construction, the pushforward mechanism captures the non-trivial global obstructions that arise from pairwise consistency failing to glue into a global order. The work is presented as a foundational step for analyzing preference aggregation where the location of conflict is as critical as its existence.