The Condorcet Dimension of Metric Spaces

Technische Samenvatting: De Condorcet-dimensie van Metrische Ruimtes

Probleemdefinitie
Het artikel onderzoekt de Condorcet-dimensie van een verkiezing, gedefinieerd als de minimale kardinaliteit van een Condorcet-winnende verzameling. Een Condorcet-winnende verzameling $S \subseteq C$ (waarbij $C$ de verzameling kandidaten is) is een deelverzameling zodanig dat voor elke kandidaat $j \notin S$, meer dan de helft van de kiezers ten minste één kandidaat in $S$ verkiest boven $j$. Hoewel Elkind, Lang en Saffidine [16] hebben vastgesteld dat er altijd een Condorcet-winnende verzameling van grootte ten hoogste $\lceil \log m \rceil$ bestaat (waarbij $m$ het aantal kandidaten is), blijft de exacte bovengrens voor de Condorcet-dimensie in algemene verkiezingen een open vraag. De auteurs merken op dat hoewel instanties met een Condorcet-dimensie van 3 bekend zijn, er geen instanties met een dimensie groter dan 3 zijn gevonden, wat leidt tot een vermoeden dat de dimensie in het algemeen maximaal 3 is.

Het artikel richt zich specif{%elijk op het ruimtelijke model van stemmen, waarbij kiezers en kandidaten zijn gelokaliseerd in een metrische ruimte, en voorkeuren worden bepaald door nabijheid (dichtere kandidaten worden verkozen). De studie beperkt zich tot 2-dimensionale metrische ruimtes ($D=2$) onder specifieke normen, wat contrasteert met het algemene geval waar de inbeddingsdimensies hoog kunnen zijn ($D = \min[m-1, n]$).

Methodologie
De auteurs maken gebruik van een combinatie van graaftheoretische argumenten en geometrische analyse binnen specifieke metrische ruimtes:

1. Graaftheoretisch Kader: Het probleem wordt gemodelleerd met behulp van een meerderheids-digraaf (een toernooi waar een boog $(j, i)$ bestaat als een meerderheid van de kiezers $i$ verkiest boven $j$). Een Condorcet-winnende verzameling komt overeen met een dominante verzameling in deze digraaf. De auteurs maken gebruik van de eigenschap dat een dominante verzameling in een toernooi van grootte $m$ een grootte heeft van ten hoogste $\lceil \log m \rceil$.
2. Geometrische Constructie (Manhattan-norm): Voor de 2-dimensionale Manhattan-norm ($L_1$) verdelen de auteurs het vlak in vier kwadranten op basis van de mediane coördinaten van de kiezers (verschoven naar de oorsprong). Ze definiëren een kandidaatverzameling $S = \{c_1, c_2, c_3, c_4\}$, waarbij elke $c_i$ de kandidaat in kwadrant $Q_i$ is die het dichtst bij de oorsprong ligt.
   • Ze bewijzen via een casusanalyse dat voor elke kandidaat $c$ in een kwadrant, de kandidaat $c_i$ die het dichtst bij de oorsprong in datzelfde kwadrant ligt, door ten minste de helft van de kiezers (specifiek die in de aangrenzende of tegenovergestelde kwadranten) wordt verkozen.
   • Dit stelt vast dat $S$ een dominante verzameling is in de meerderheids-digraaf.
3. Geometrische Transformatie (Oneindigheidsnorm): Voor de 2-dimensionale Oneindigheidsnorm ($L_\infty$) maken de auteurs gebruik van een geometrisch rotatie-argument. Ze tonen aan dat het roteren van de coördinatenassen met 45 graden de $L_\infty$-afstand transformeert in een geschaalde $L_1$ (Manhattan) afstandmetriek. Bijgevolg blijven de voorkeursstructuren behouden, waardoor het $L_1$-resultaat direct kan worden toegepast op het $L_\infty$-geval.
4. Constructie van de Ondergrens: Om vast te stellen dat de dimensie niet altijd 1 is, construeren de auteurs een specifieke 2-dimensionale instantie met 3 kiezers en 3 kandidaten onder elke $p$-norm ($p \ge 1$) die resulteert in een Condorcet-cyclus, waarmee bewezen wordt dat de dimensie ten minste 2 is.
5. Inbeddingsconstructies: Het artikel behandelt het inverse probleem: het inbedden van willekeurige voorkeuren van kiezers in een metrische ruimte. Het biedt polynomiale-tijd constructies voor het inbedden van elke set strikte voorkeuren in een $p$-norm metrische ruimte van dimensie $D = \min[m, n]$. Dit breidt eerdere resultaten, bekend voor Euclidische ($L_2$) en Manhattan ($L_1$) normen, uit naar algemene $p$-normen.

Belangrijkste Bijdragen en Resultaten

• Bovengrens voor $D=2$: Het primaire resultaat is dat in een 2-dimensionale metrische ruimte onder ofwel de Manhattan-norm of de Oneindigheidsnorm, de Condorcet-dimensie ten hoogste 4 is. Dit is een significante verbetering ten opzichte van de algemene logaritmische bovengrens voor deze specifieke ruimtelijke settings.
• Ondergrens voor $D=2$: De auteurs bewijzen dat er voor elke $p$-norm in 2 dimensies instanties van verkiezingen bestaan waarbij de Condorcet-dimensie ten minste 2 is (dat wil zeggen, er is niet noodzakelijkerwijs een Condorcet-winnaar).
• Algemene Inbeddingstellingen:
  • Stelling 7: Elke verkiezing met $m$ kandidaten en $n$ kiezers kan in polynomiale tijd worden ingebed in een metrische ruimte van dimensie $D=m$ voor elke $p$-norm ($p \ge 0$).
  • Stelling 8: Elke dergelijke verkiezing kan in polynomiale tijd worden ingebed in een metrische ruimte van dimensie $D=n$ voor elke $p$-norm ($p > 1$).
  • Deze constructies generaliseren de bevindingen van Bogomolnaia en Laslier [7] en Chen et al. [11] naar willekeurige $p$-normen.

Betekenis en Claims
Het artikel claimt de eerste constante bovengrens te bieden voor de Condorcet-dimensie voor specifieke, laag-dimensionale ruimtelijke modellen van stemmen. Door de inbeddingsdimensie te beperken tot $D=2$ en natuurlijke normen (Manhattan en Oneindigheid) te gebruiken, demonstreren de auteurs dat de complexiteit van het vinden van een winnende verzameling begrensd wordt door een kleine constante (4), in plaats van logaritmisch te groeien met het aantal kandidaten.

De auteurs geven expliciet aan dat hun resultaten het algemene vermoeden dat de Condorcet-dimensie universeel maximaal 3 is voor alle verkiezingen (waar $D$ onbegrensd is), niet oplossen. Ze erkennen dat recent onafhankelijk werk door Charikar et al. [10] en Nguyen et al. [28] een constante bovengrens van 5 (verbeterd van 6 en 16) heeft vastgesteld voor algemene verkiezingen met behulp van probabilistische bemonstering en minimax-stellingen. De betekenis van dit artikel ligt in de geometrische benadering van het $D=2$ geval, die een strakkere bovengrens (4) biedt voor ruimtelijke modellen en de relatie tussen metrische dimensie en de existentie van kleine Condorcet-winnende verzamelingen verduidelijkt.

Het artikel concludeert door de kloof tussen de bewezen ondergrens van 2 en de bovengrens van 4 voor $D=2$ te identificeren als een open probleem, evenals de algemene vraag of de dimensie universeel begrensd is door 3.