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

Technische Samenvatting: Lokalisatie van Conflicten in Preferentie-aggregatie via Discrete Sheaves

Probleemstelling
Het artikel behandelt de uitdaging van het aggregeren van ordinale preferentiedata van meerdere bronnen die slechts een gedeeltelijke zichtbaarheid van de alternatieven bezitten. In tegenstelling tot traditionele sociale keuzeproblemen, waarbij het doel is om legitieme meningsverschillen tussen kiezers op te lossen, richt dit werk zich op datafusie: bepalen of gedeeltelijke rangschikkingen van overlappende bronnen kunnen worden gecombineerd tot één coherente globale rangschikking. Een conflict ontstaat hier niet louter door uiteenlopende meningen, maar door inconsistenties waarbij bronnen van mening verschillen over de alternatieven die zij delen. Het centrale probleem is het diagnosticeren van waar deze inconsistenties optreden binnen de interactiestructuur en te bepalen of een globale oplossing bestaat, met name wanneer paarwijze overeenkomsten diepere structurele onmogelijkheden kunnen maskeren.

Methodologie
De auteurs stellen een discreet sheaf-theoretisch raamwerk voor dat direct werkt op ordinale data zonder linearisatie (in tegen tegenstelling tot HodgeRank).

1. Discrete Order Sheaf:

   • Het systeem wordt gemodelleerd als een graaf $G=(V, E)$ waarbij knopen (vertices) kiezers (bronnen) vertegenwoordigen en randen (edges) overlappingen (gedeelde alternatieven) vertegenwoordigen.
   • Een Discrete Order Presheaf wordt gedefinieerd waarbij:
     • Knopen-stalks ($F_v$): De verzameling van alle totale orden op de alternatieven die zichtbaar zijn voor kiezer $v$.
     • Rand-stalks ($F_e$): De verzameling van alle totale orden op de intersectie van de alternatieven die zichtbaar zijn voor beide eindpunten van een rand.
     • Restrictiemappen: Mappen die een lokale totale orde beperken tot de deelverzameling van alternatieven die gedeeld wordt met een buur.
   • Een preferentieprofiel wordt behandeld als een 0-cochain (een toewijzing van een specifieiautale lokale orde aan elke knoop).

2. Obstruction Locus ($\Omega_1$) en Incompatibility Index:

   • De Obstruction Locus $\Omega_1(\sigma)$ wordt gedefinieerd als de verzameling randen waar de gerestringeerde lokale orden van aangrenzende kiezers verschillen ($\sigma_u|_{A_{uv}} \neq \sigma_v|_{A_{uv}}$).
   • De Incompatibility Index $|\Omega_1|$ is de kardinaliteit van deze verzameling.
   • Cruciaal is dat deze metriek lokalisatie biedt: het identificeert specifieke paren kiezers die niet coherent zijn, in plaats van enkel een enkele globale scalar van inconsistentie te leveren.

3. Pushforward en Globale Oplosbaarheid:

   • Om aan te pakken of een globale rangschikking bestaat, maken de auteurs gebruik van de pushforward-operatie ($\pi_*$) onder een graaf-quotientmap (bijv. het samenvoegen van kiezers).
   • De pushforward sheaf $\pi_*F$ op een samengevoegde knoop $v'$ bevat de verzameling van alle totale orden op de unie van alternatieven die compatibel is met alle oorspronkelijke kiezers in de preimage.
   • Lege Stalks: Als de restricties van de samengevoegde kiezers tegenstrijdig zijn, wordt de stalk bij de samengevoegde knoop leeg ($\emptyset$). Dit signaleert een lokale onmogelijkheid, zelfs als geen enkele paarwijze rand in de oorspronkelijke graaf geobstruerd was.
   • Algoritmische Implementatie: De pushforward wordt efficiënt berekend met behulp van een constraint digraph. Constraints van lokale orden worden geaggregeerd in een gerichte graaf. Als deze graaf een gerichte cyclus bevat, zijn de constraints tegenstrijdig, en is de stalk leeg. Deze detectie van cycli draait in polynomiale tijd ($O(|A|^2 \cdot |P|)$), waardoor de factoriële complexiteit van het enumereren van permutaties wordt vermeden.

Belangrijkste Bijdragen

1. Formalisering van de Discrete Order Sheaf: Een raamwerk voor preferentieprofielen dat ordinale data behandelt als een cellulaire sheaf, waardoor het verlies van combinatorische structuur dat inherent is aan linearisatiemethoden wordt vermeden.
2. Definitie van de Obstruction Locus: Introductie van $\Omega_1$ en de Incompatibility Index om paarwijke conflicten te kwantificeren en te lokaliseren. De auteurs verduidelijken dat hoewel $|\Omega_1|$ geen cohomologische invariant is, het dient als een precieze "localizer" van conflict, verschillend van globale topologische invarianten zoals de dimensie van harmonische ruimtes in HodgeRank.
3. Pushforward Mechanisme voor Samenvoegen: Ontwikkeling van een sheaf-theoretische pushforward die het samenvoegen van kiezers modelleert. Dit onthult dat conflicten kunnen transformeren van rand-gebaseerde onenigheid naar lege stalks (lokale onmogelijkheden) bij vergroving (coarsening), een fenomeen dat ondetecteerbaar is door eenvoudige paarwijze controles.
4. Polynomial-Time Algoritme: Implementatie van de constraint digraph-aanpak voor het detecteren van lege stalks, wat een enorme versnelling biedt ten opzichte van naïeve enumeratie voor het bepalen van globale oplosbaarheid.

Experimentele Resultaten
De auteurs valideren het raamwerk via computationele experimenten:

• Basale Voorbeelden: Het raamwerk identificeert correct bekende paradoxen (bijv. Condorcet-cycli) en berekent $|\Omega_1|$ voor diverse graaftopologieën (bijv. $K_4$, $C_3$).
• Stochastische Interpolatie (Mallows Model): Door het Mallows-model te gebruiken om preferentieprofielen te genereren met variërende niveaus van consensus, laat de studie zien dat de gemiddelde Incompatibility Index $|\Omega_1|$ voldoet aan een vloeiende en voorspelbare respons op veranderingen in de dispersieparameter.
• Consistentiecijfers: Experimenten op willekeurige profielen tonen aan dat globale consistentie (het bestaan van een globale sectie) wordt bepaand door het aantal kiezers in een verbonden component (specifiek $(1/|A|!)^{|V|-1}$ voor volledige zichtbaarheid), terwijl de gemiddelde Incompatibility Index schaalt met het aantal randen.
• Schaalbaarheid: De constraint digraph-algoritme schaalt efficiënt. Voor 12 alternatieven is de digraph-aanpak ongeveer 149.000 keer sneller dan naïeve enumeratie.
• De "Onzichtbare" Obstruction: Een specifiek voorbeeld (Appendix D) demonstreert een profiel waarbij $|\Omega_1| = 0$ (alle paarwijke overlappingen zijn consistent), maar het samenvoegen van alle bronnen resulteert in een lege stalk. Dit bevestigt dat paarwijke controles onvoldoende zijn voor het detecteren van globale fusie-onmogelijkheden.

Betekenis en Claims
De auteurs stellen dat de sheaf-theoretische benadering twee duidelijke voordelen biedt ten opzichte van bestaande methoden zoals HodgeRank:

1. Lokalisatie: Het identificeert welke specifieke interacties (randen) verantwoordelijk zijn voor inconsistenties, in plaats van enkel te rapporteren dat er een globale obstructie bestaat.
2. Functorialiteit: De pushforward-operatie maakt het mogelijk om conflicten consistent te volgen naarmate het systeem wordt vergroef (bijv. het samenvoegen van kiezers). Het legt de transitie vast van gedistribueerde rand-conflicten naar gelokaliseerde onmogelijkheden (lege stalks), en biedt daarmee een certificaat voor globale oplosbaarheid dat paarwijke controles niet kunnen bieden.

De auteurs verklaren expliciet dat het raamwerk geen vervanging is voor cohomologische invarianten, maar een instrument voor het lokaliseren en diagnosticeren van specifieke structurele fouten in preferentie-aggregatie. Ze benadrukken dat hoewel hogere-orde obstructies ($\Omega_k$ voor $k \ge 2$) triviaal verdwijnen op grafen vanwege de aard van de Čech-constructie, de pushforward-mechanisme de niet-triviale globale obstructies vangt die ontstaan wanneer paarwijke consistentie faalt om samen te voegen tot een globale orde. Het werk wordt gepresenteerd als een fundamentele stap voor de analyse van preferentie-aggregatie waarbij de locatie van het conflict even cruciaal is als het bestaan ervan.